Question

Given a planning problem

a. Why forward total order planning is inefficient?

b. Will the planning graph have the same problem? Why?

Answer 1

a) Total-order planning maintains a total ordering between all actions at every stage of planning. 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 between actions only where necessary. It was 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.

For Example: Consider the following situation where a person must travel from the start to the end of an obstacle course. This obstacle course is composed of a bridge, a see-saw and a swing-set. The bridge must be traversed before the see-saw and swing-set are reachable. Once reachable, the see-saw and swing-set can be traversed in any order, after which the end is reachable. In a partial-order plan, ordering between these obstacles is specified only when necessary. The bridge must be traversed first. Second, either the see-saw or swing-set can be traversed. Third, the remaining obstacle can be traversed. Then the end can be traversed. Partial-order planning relies upon the Principle of Least Commitment for its efficiency.

Therefore we can say that Total-order planning is not much efficient in some cases.

_____________________________________________________________________________________

b) A Planning graph consists of a sequence of levels that correspond to time steps inthe plan where level 0 is the initial state. Each level contains a set of literals and a set of actions Planning graphs are an efficient way to create a representation of a planning problem that can be used to

• Achieve better heuristic estimates
• Directly construct plans
• Planning graphs only work for propositional problems.