Partial-order planning

Partial-order planning is an approach to automated planning that leaves decisions about the ordering of actions as open as possible. It contrasts with total-order planning, which produces an exact ordering of actions. Given a problem in which some sequence of actions is required in order to achieve a goal, a partial-order plan specifies all actions that need to be taken, but specifies an ordering of the actions only where necessary.

Consider the following situation: a person must get from point A to point B. In between points A and B, there is an obstacle course. In a partial order plan, the specific path that this person will take to get from point A to point B will not be conceived of all at once. Instead the person will navigate the obstacle course by deciding which obstacles to master one at a time. Partial-order planning exhibits the Principle of Least Commitment, which contributes to the efficiency of this planning system as a whole. Often there are many possible plans for a problem which only differ in the order of the actions. Many traditional automated planners search for plans in the full search space containing all possible orders. In addition to the smaller search space for partial-order planning, it may also be advantageous to leave the option about the order of the actions open for later. An important distinction to be made is between ordering steps of an action and conceptualizing those steps. Partial order planning doesn’t sequence actions until it is absolutely necessary; however, these actions are conceived of much before they are sequenced. This type of planning system is simply a relation structure between actions. It is not the mechanism by which these actions mentally come to fruition.

Partial-order plan

A partial-order plan or partial plan is a plan which specifies all actions that need to be taken, but does not specify an exact order for the actions when the order does not matter. It is the result of a partial-order planner. A partial-order plan consists of four components:

In order to keep the possible orders of the actions as open as possible, the set of order conditions and causal links must be as small as possible.

A plan is a solution if the set of open preconditions is empty.

A linearization of a partial order plan is a total order plan derived from the particular partial order plan; in other words, both order plans consist of the same actions, with the order in the linearization being a linear extension of the partial order in the original partial order plan.

Example

For example, a plan for baking a cake might start:

This is a partial plan because the order for finding eggs, flour and milk is not specified, the agent can wander around the store reactively accumulating all the items on its shopping list until the list is complete.

Partial-order planner

A partial-order planner is an algorithm or program which will construct a partial-order plan and search for a solution. The input is the problem description, consisting of descriptions of the initial state, the goal and possible actions.

The problem can be interpreted as a search problem where the set of possible partial-order plans is the search space. The initial state would be the plan with the open preconditions equal to the goal conditions. The final state would be any plan with no open preconditions, i.e. a solution.

The initial state is the starting conditions, and can be thought of as the preconditions to the task at hand. For a task of setting the table, the initial state could be a clear table. The goal is simply the final action that needs to be accomplished, for example setting the table. The operators of the algorithm are the actions by which the task is accomplished. For this example there may be two operators: lay (tablecloth), and place (glasses, plates, and silverware).

Plan space

The plan space of the algorithm is constrained between its start and finish. The algorithm starts, producing the initial state and finishes when all parts of the goal have been achieved. In the setting a table example, there are two types of actions that need to be addressed—the put-out and lay operators. There are also four unsolved operators: Action 1, lay-tablecloth, Action 2, Put-out (plates), Action 3, Put-out (silverware), and Action 4, Put-out (glasses). However, there is a threat that arises if Action 2, 3, or 4 comes before Action 1. This threat is that the precondition to the start of the algorithm will be unsatisfied as the table will no longer be clear. Thus, there are constraints that need to be added to the algorithm that force Actions 2, 3, and 4 to come after Action 1. Once these steps are completed, the algorithm will finish and the goal will have been completed.

Threats

As seen in the algorithm presented above, partial-order planning can encounter certain threats, meaning orderings that threaten to break connected actions, thus potentially destroying the entire plan. There are two ways to resolve threats:

Promotion orders the possible threat after the connection it threatens. Demotion orders the possible threat before the connection it threatens.

Partial-order planning algorithms are known for being both sound and complete, with sound being defined as the total ordering of the algorithm, and complete being defined as the capability to find a solution, given that a solution does in fact exist.

Partial-order vs. total-order planning

Partial-order planning is the opposite of total-order planning, in which actions are sequenced all at once and for the entirety of the task at hand. The question arises when one has two competing processes, which one is better? Anthony Barret and Daniel Weld have argued in their 1993 book, that partial-order planning is superior to total-order planning, as it is faster and thus more efficient. They tested this theory using Korf’s taxonomy of subgoal collections, in which they found that partial-order planning performs better because it produces more trivial serializability than total-order planning. Trivial serializability facilitates a planner’s ability to perform quickly when dealing with goals that contain subgoals. Planners perform more slowly when dealing with laboriously serializable or nonserializable subgoals. The determining factor that makes a subgoal trivially or laboriously serializable is the search space of different plans. They found that partial-order planning is more adept at finding the quickest path, and is therefore the more efficient of these two main types of planning.

The Sussman Anomaly

Partial-order plans are known to easily and optimally solve the Sussman Anomaly. Using this type of incremental planning system solves this problem quickly and efficiently. This was a result of partial-order planning that solidified its place as an efficient planning system.

Disadvantages to partial-order planning

One drawback of this type of planning system is that it requires a lot more computational power for each node. This higher per-node cost occurs because the algorithm for partial-order planning is more complex than others. This has important artificial intelligence implications. When coding a robot to do a certain task, the creator needs to take into account how much energy is needed. Though a partial-order plan may be quicker it may not be worth the energy cost for the robot. The creator must be aware of and weigh these two options to build an efficient robot.

References


This article is issued from Wikipedia - version of the Monday, January 25, 2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.