Notes Tue. 4 Feb 2003 (scribe -- Andrew Davis, drewdavis00@hotmail.com) A partial-order planner is a least-commitment regression planner. Nobody has ever bothered to build a least-commitment progression planner. Apparently there are good reasons for this. It is a regression planner in the sense that an action is added only if it is relevant. That is, if it gives some required effect. But a partial-order planner is different from an ordinary regression planner in the sense that an action's position is not constrained, so its position can continue to change with respect to other actions. The "least-commitment" refers to least-commitment in terms of the position of the action, not in terms of objects or parameters of the action. The only constraints on the positions of the actions is that they may not interfere with other actions' preconditions and effects. In the PDDL specification, actions are represented in a parameterized way. For example, you can say unstack(x,y) rather than unstack(a,b) (where a and b refer to specific blocks, but x and y can each be instantiated as any block). But plans that we have seen use "ground actions," meaning that they would only say unstack(a,b) and not unstack(x,y). Since the idea behind partial-order planning is the principle of least-commitment, it would seem being able to express partial-order plans in terms of uninstantiated variables would reduce the amount of commitment even more. However, there is a difference between least-commitment with respect to position and least-commitment with respect to object names. In a regression planner, if one of the goals is clear(b), it could be possible to have a number of actions saying unstack(a,b), unstack(c,b), unstack(d,b), and so on. Any of these could produce clear(b). But this means creating a new branch for every other block in the world. One option to simplifying this would seem to be to have an action unstack(x,b). This kind of plan would be called a "partially instantiated" plan. This enters into the realm of "ground actions" versus "partially instantiated" actions, where some of the variables don't have values. Plans which contain partially instantiated actions are called "partially instantiated plans." But any solution that we would be looking for would have to be a completely instantiated plan. It is not enough to simply say "lift something from b." It is necessary to specify what to lift from b. A value has to be given for x. Even so, while searching for the plan, it is possible to search through the space of "partially instantiated suffixes," as opposed to ground -- or fully instantiated -- suffixes. Where a partial-order planner is "least committed," this is even less commitment. When you don't commit to any decision before you have to, that means less commitment than otherwise. That's what the basic concept of "commitment" is all about. Any unstack action where the second argument is b will satisfy the subgoal clear(b). So it seems logical that it would not be necessary to specify what, exactly, the first argument to unstack is until we need to later on. Or if we opportunistically find something which could work. The textbook chapter that we read incorrectly states that only partially ordered planning is capable of handling partially instantiated actions. However, this is not the case. As the logic above shows, regression can be done with partially instantiated actions. To implement an action such as unstack(x,b) using regression, the effects of the action would be clear(b) holding(x) ~handempty ~clear(x) and the preconditions would be on(x,b) handempty clear(x) So these preconditions must hold in the state preceding the action. Regression searches in the space of sets of states. The space of ground regression states is a subset of the space of all complete states. So the space of ground regression states can be thought of as a "lifted" version of the space of all complete states. The space of partially instantiated regression states is a subset of the space of ground regression states. So the space of partially instantiated regression states can be thought of as a "lifted" version of the space of ground regression states. Lifting means thinking in terms of sets of states, rather than individual states. The motivation for searching in a lifted space is that the number of states is hopefully smaller. But the downside is that a lifted space can include the empty set. It can include sets of states that are logically inconsistent. This problem is only exacerbated when searching a lifted space of a lifted space. The tradeoff for searching in sets of states is that it is possible that much fewer states will be searched, but that a great deal of time can be wasted expanding dead states. If another subgoal clear(d) is added, then regression becomes more complicated. In the state prior to the unstack(x,b) action, the conditions would now need to be on(x,b) handempty clear(x) x != d clear(d) This is not really a world state, but rather a set of constraints that must be satisfied by any world state that would precede unstack(x,b). This changes the definition of regression to something more complicated, because now variables must be taken into consideration. The situation could be further complicated if the unstack(x,b) were changed to unstack(x,y) y = b Prior to taking into consideration partially insantiated variables, there was only one possible reason for a partial state to be empty -- because some subset of ground literals could be inconsistent in some world state. With partially instantiated variables, there is an additional reason that a partial state could be the empty set. This is because we now have equality and inequality constraints to contend with. Some set of inequality constraints could be inconsistent with some set of equality constraints. For example, in a world with only 4 blocks, a, b, c, and d, we could have x != a x != b x != c x != d This is a dead state, because x has no value. For a planner to realize this requires reasoning with the constraints. Theoretically, one could do much better than a ground search if these constraints could be dealt with in an efficient manner. Currently, there is no planner which can efficiently search in the space of lifted actions. The only advantage to using such an approach would be if it could significantly outperform a ground search. Answering the question, "is there an assignment of values to the variables such that all constraints are satisfied" is an NP-complete problem. If each variable can only take on a finite number of possible values, then this becomes a CSP problem. This embeds the CSP problem into the search problem. When dealing with partially instantiated variables in partial order planning, the difficulty arises that the action unstack(x,b) may or may not be a threat to the goal clear(d), depending on whether or not x = d. So if some action is supporting clear(d), it is not apparent whether or not the action unstack(x,b) may come after clear(d). This problem can be dealt with by either promotion, demotion, or placing the precondition x != d on the action unstack(x,b). So, when dealing with partially instantiated variables, the per-node cost increases to a point where it makes searching too inefficient. Because ground search planners currently work as well as they do, lifted planners have no real advantage because they have so many outstanding problems at this time. **************************************************************** The following example comes from "An Introduction to Least Commitment Planning" by Daniel S. Weld in the readings listed on the class website. The Sussman Anomaly has initial state on(c,a) clear(b) clear(c) on(a,table) on(b,table) and goal state on(a,b) on(b,c) Partial order planning looks for a flaw -- either an open condition or an unsafe link -- to resolve. At the beginning, there are only the two open conditions on(a,b) and on(b,c) and there are no unsafe links. The order of selection of open conditions does not affect the completeness of the plan, although it can significantly affect the size of the total search space. (Fig. 6) Suppose that the open condition on(b,c) is picked to be satisfied. There are no existing actions in the plan which can support on(b,c). The action move(b,table,c) (which means move b from the table to c) will satisfy on(b,c). In actuality, the action move(b,a,c) would also support on(b,c), and the planner would need to consider both branches. But for this example, only the action move(b,table,c) will be considered for the sake of simplicity. If there were other blocks in the world, d, e, f, g, etc. A separate branch would need to be generated to move b from each of those different blocks to c. The ordering of these different search branches in the queue would be determined by some heuristic. The selection of the action move(b,table,c) creates three new open conditions clear(b), clear(c), and on(b,table). So there are now a total of four open conditions clear(b) clear(c) on(b,table) on(a,b) The new action also has effects clear(table) ~on(b,table) ~clear(c) (Fig. 7) If the next initial condition selected to be satisfied is clear(b), then that can be supported by the initial state which gives clear(b). This creates no new open conditions. (Fig. 8) Next, the open condition on(a,b) can be supported by introducing the new action move(a,table,b). At this point, all actions must come between the start state and the end state. No other ordering constraints have been specified yet. However, an unsafe link has just been introduced into the problem. In general, whenever a new step is added to the plan, it is necessary to look and see if the new step causes threats to existing causal links to appear. In this case, the action move(a,table,b) has effects on(a,b) clear(table) ~on(a,table) ~clear(b) So this threatens the causal link from the inital state, which supports clear(b) for the action move(b,table,c). The options for resolving this threat are promotion, demotion, and confrontation. Confrontation is not an option, because no effects are conditional. Promotion is not an option, because no action can come before start. (Fig. 9) So demotion, placing move(a,table,b) after move(b,table,c) is the best and only option. This removes all unsafe links. However, there are still many open conditions to be satisfied. The action move(a,table,b) has preconditions clear(b) clear(a) on(a,table) The action move(b,table,c) has preconditions clear(c) on(b,table) (Fig. 10) clear(a) is supported by adding the action move(c,a,table), which has preconditions on(c,a) clear(c) and effects on(c,table) At this point, all open conditions can be supported by existing actions in the plan. For every open condition to be supported, every possible choice that could satisfy it must be considered. If you think in terms of one level for each block, then there are at least as many levels as there are open conditions. In addition, there are levels for all the unsafe links. One advantage, however, of partial order planning is that the position of the actions does not need to be considered up front. In addition to achievement goals, there can also be maintenance goals to be considered. Maintenance goals are conditions which must remain true throughout the entire course of the plan. If at any time while the action is played out, some maintenance goal should become untrue only for a moment, the plan does not work. An example of a maintenance goal might be that in the course of the plan, nobody's leg gets broken. If at any point somebody's leg gets broken, then the plan is no good. Maintenance goals must remain satisfied at all times. Maintenance goals can be dealt with easily by setting an extra causal link at the very beginning from the initial state to the goal state saying that that condition must hold. That way, any action which is introduced must be concerned with creating an unsafe link. This kind of simplicity is another reason that partial order planning is so popular. Similarly, actions with duration can be handled more easily by partial order planning. Progression and regression do not deal as well with actions with duration, because it is possible that it would be necessary to consider the state for each millisecond. This could be very problematic when dealing with a time period of days, for example. The search space for partial order planning is much more complicated than for progression or regression, because individual conditions are worked on one at a time and it is necessary to consider open conditions and unsafe links. In every case there are extra choices. But it has advantages in that it is not necessary to commit to the position of an action, or to be concerned as to whether or not an action is instantaneous. And it can deal with maintenance goals as well as normal goals. ***** _________________________________________________________________ Help STOP SPAM with the new MSN 8 and get 2 months FREE* http://join.msn.com/?page=features/junkmail