From: Lilja Maria Sigurdardottir (liljamaria_at_hotmail.com)
Date: Tue May 27 2003 - 11:23:00 PDT
Smith and Weld
Temporal planning with mutual exclusion reasoning
IJCAI '99
Summary - This paper presents an algorithm to solve temporal planning problems using a planning graph-based approach.
- Plan expansion is altered to produce a cyclic bipartite (instead of leveled) graph, where one side represents propositions, the other represents actions, and edges represent preconditions and action effects. Nodes are annotated with temporal information, e.g. start times and durations for actions and the earliest time a proposition can be realized. The bipartite action-proposition graph is augmented with another set of edges representing pair-wise mutual exclusivity between any two nodes (at which point the graph is no longer bipartite). Mutexes are annotated with durations.
- Solution extraction is altered to take into account varying action duration, by organizing the backward chaining search according to constraints on the latest times by which subgoals must be achieved.
Key ideas - The main contributions are (a) the formulation of the richer, yet more space-efficient planning graphs which lend themselves to less discrete problems (but see questions, the Fox/Long comment), and (b) the exploration of planning graph mutexes for efficiency in temporal planning, along with the introduction of action-proposition mutexes.
- The idea behind collapsing the conventional leveled action-proposition planning graph into a cyclic, bipartite graph is that the set of nodes only grows, and the set of mutexes only shrinks, so instead of having levels it is sufficient to employ simple annotations representing the first time a node is reachable and the last time a mutex exists. Real number annotations are more expressive than (discrete) graph levels, which means the new structure is not only more space-efficient and easier to construct, it also lends itself to more expressive planning languages - e.g. temporal problems.
- The authors then augment the graphplan mutex types with action-proposition mutexes, which exist for example when a proposition can't be realized until an action has finished execution.
Questions/flaws
- Figure 2 caption, B is cmutex with Q when Theta should say B is cmutex with P when Theta.
- Section 6 paragraph 2 the shortest plan requires three unites of time, and A can start any time between 0 and 2 inclusive but only as long as the A-B and A-Q mutexes aren't being considered yet.
- Talk about section 7, pretty please? Three (or more?) readings and I still haven't made my way through that.
- This is complex stuff. I can't really ask any smart questions about the data structures etc. because I don't understand well enough. A rich example would have solved that problem, but also exploded the paper well beyond the page limits. Where is the journal version...?
Directions
- The paper points towards multiple directions for future work.
- I did a citeseer search and found ca. 15 citations for this paper. One mentions that the cyclic planning graph is the basis for a number of efficient graphplan derivatives. One mentions that the representation doesn't lend itself to metric constructs, but the two completeness-preserving filters mentioned at the end of section 6 seem to point the other way? I found, but haven't read a Fox/Long Journal of AI '99 publication about efficient plan graphs, did the bi-level planning graph surface here or there or simultaneously?
- I'm entertained by the possibility of adopting TGP to metric resources and uncertainty. It would seem like a hairy process, due to the prevalence of time-ordered data structures etc.
This archive was generated by hypermail 2.1.6 : Tue May 27 2003 - 11:39:59 PDT