Partial-order planning

From Wikipedia, the free encyclopedia

"Partial-order planning", not to be confused with linear or total-order planning, is the process by which the brain incrementally orders actions needed to complete a specific task[4]. To complete any task, the brain needs to plan out the sequence by which to execute the behavior. One way the brain does this is with a partial-order plan. In a partial-order plan, the relationships between the actions of the behavior are not set until absolutely necessary[3]. 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[4]. An important distinction to be made is between ordering steps of an action and conceptualizing those steps. Partial order planning doesn’t sequin actions until it is absolutely necessary, however these actions are conceived of much before they are sequenced[4]. This type of planning system is simply a relation structure between actions[3]. It is not the mechanism by which these actions mentally come to fruition.

Algorithms

Partial-order plan algorithms need to have six components to work properly: a goal, an initial state, operators, bindings, causal links, and a search in a plan space.

Goal

The goal of the algorithm is simply the final action that needs to be accomplished, like setting the table[4].

Initial State

The initial state of the algorithm can be thought of as the precondition to step 1 of accomplishing the task at hand. For the setting the table task, the initial state of the algorithm would be a clear table[4]. This initial state allows the algorithm to start.

Operators

The operators of the algorithm are the actions by which the task is accomplished. In this case there are two operators: lay (tablecloth), and put-out (glasses, plates, and silverware)[4].

Bindings

The bindings of the algorithm are the connections between specific variables in the action[7]. Bindings, as ordering, only occur when absolutely necessary.

Causal Links

Causal links in the algorithm are those that categorically order actions. They are not the specific order (1,2,3) of the actions, rather the general order as in Action 2 must come somewhere after Action 1, but before Action 2.

Plan Space

The plan space of the algorithm is constrained between its start and finish. The algorithm starts, producing the initial state[7] and finishes when all parts of the goal have been achieved[4]. In the setting a table example, there are two types of actions that need to be addressed—the put-out and lay operators[4]. 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)[4]. 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[4]. Thus, there are constraints that need to be added to the algorithm that force Actions 2, 3, and 4 to come after Action 1[4]. 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.[5] Demotion orders the possible threat before the connection it threatens.[5]

Overview of Algorithm

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.[4]

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[5]. 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[5]. Trivial serializability facilitates a planner’s ability to perform quickly when dealing with goals that contain subgoals[5]. Planners perform more slowly when dealing with laboriously serializable or nonserializable subgoals[5]. The determining factor that makes a subgoal trivially or laboriously serializable is the search space of different plans[5]. 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[4]. 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.[1] This higher per-node cost occurs because the algorithm for partial-order planning is more complex than others[4]. 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

  1. ↑ [5]
  1. Kambhampati, S., Knoblock, C.A., Yang, Q. (1994). Planning as Refinement Search: A Unified Framework for Evaluating Design Tradeoffs in Partial-Order Planning. Elsevier Science. http://www.isi.edu/info-agents/papers/kambhampati95-joint-aij.ps
  2. Poole, D., Mackworth, A. (2010). Partial-Order Planning in Artificial Intelligence Foundations of Computational Agents. Cambridge University Press. http://artint.info/html/ArtInt_209.html#partial-order-planner-fig-2
  3. Dyer, C. R. “Partial-Order Planning (Chapter 11).”(2003) CS 540. University of Wisconsin-Madison. Madison, Wisconsin. http://pages.cs.wisc.edu/~dyer/cs540/notes/pop.html
  4. Barrett, A., and Weld, D. (1993). Partial-Order Planning: Evaluating Possible Efficiency Gains. University of Washington: Department of Computer Science and Engineering. Notes. http://citeseerx.ist.psu.edu/viewdoc/download?rep=rep1&type=pdf&doi=10.1.1.50.8915
  5. Simmons, Reid. (2001). “Planning, Execution & Learning 1. Partial Order Planning.” Carnegie Mellon University. Pittsburgh. Notes. http://www.cs.cmu.edu/~reids/planning/handouts/Partial_Order.pdf

External links

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.