Planning as Search

Planning as Search:

There are two main approaches to solving planning problems, depending on the kind of search space that is explored:

1. Situation-space search

2. Planning-space searchIn situation space search

In Situation-Space search

• the search space is the space of all possible states or situations of the world

• initial state defines one node

• a goal node is a state where all goals in the goal state are satisfied

• a solution plan is the sequence of actions (e.g. operator instances) in the path 

  from the start node to a goal node.

In Plan-Space Search

• the search space is the space of all possible plans

• a node corresponds to a partial plan

• initially we will specify an "initial plan" which is one node in this space

• a goal node is a node containing a plan which is complete, satisfying all of the

  goals in the goal state

• the node itself contains all of the information for determining a solution plan  

   (e.g.sequence of actions)

Goal Interaction

Most planning algorithms assume that the goals to be achieved are independent or nearly independent in the sense that each can be solved separately and then the solutions concatenated together. If the order of solving a set of goals (either the original goals or a  set of sub-goals which are the preconditions of an operator) fails because solving a latter goal undoes an earlier goal, then this version of the STRIPS algorithm fails. Hence, situation-space planners do not allow for interleaving of steps in any solution it finds.

Principle of Least Commitment:The principle of least commitment is the idea of never making a choice unless required to do so. The advantage of using this principle is you won't have to backtrack later! In planning, one application of this principle is to never order plan steps unless it's necessary for some reason. So, partial-order planners exhibit this property because constraint ordering steps will only be inserted when necessary. On the other hand, situation-space progression planners make commitments about the order of steps as they try to find a solution and therefore may make mistakes from poor guesses about the right order of steps.