Planning in AI

What is planning in AI?

• The planning in Artificial Intelligence is about the decision making tasks performed by the robots or computer programs to achieve a specific goal.
• The execution of planning is about choosing a sequence of actions with a high likelihood to complete the specific task.

Blocks-World planning problem

• The blocks-world problem is known as Sussman Anomaly.
• Noninterleaved planners of the early 1970s were unable to solve this problem, hence it is considered as anomalous.
• When two subgoals G1 and G2 are given, a noninterleaved planner produces either a plan for G1 concatenated with a plan for G2, or vice-versa.
• In blocks-world problem, three blocks labeled as 'A', 'B', 'C' are allowed to rest on the flat surface. The given condition is that only one block can be moved at a time to achieve the goal.
• The start state and goal state are shown in the following diagram.

Components of Planning System

The planning consists of following important steps:

• Choose the best rule for applying the next rule based on the best available heuristics.
• Apply the chosen rule for computing the new problem state.
• Detect when a solution has been found.
• Detect dead ends so that they can be abandoned and the system’s effort is directed in more fruitful directions.
• Detect when an almost correct solution has been found.

Goal stack planning

This is one of the most important planning algorithms, which is specifically used by STRIPS.

• The stack is used in an algorithm to hold the action and satisfy the goal.  A knowledge base is used to hold the current state, actions.
• Goal stack is similar to a node in a search tree, where the branches are created if there is a choice of an action.

The important steps of the algorithm are as stated below:

i. Start by pushing the original goal on the stack. Repeat this  until the stack becomes empty. If stack top is a compound goal, then push its unsatisfied subgoals on the stack.
ii. If stack top is a single unsatisfied goal then, replace it by an action and push the action’s precondition on the stack to satisfy the condition.
iii. If stack top is an action, pop it from the stack, execute it and change the knowledge base by the effects of the action. 
iv. If stack top is a satisfied goal, pop it from the stack.

Non-linear planning

This planning is used to set a goal stack and is included in the search space of all possible subgoal orderings. It handles the goal interactions by interleaving method. 

Advantage of non-Linear planning
Non-linear planning may be an optimal solution with respect to plan length (depending on search strategy used). 

Disadvantages of Nonlinear planning

• It takes larger search space, since all possible goal orderings are taken into consideration.
• Complex algorithm to understand.

Algorithm 
1. Choose a goal 'g' from the goalset 
2. If 'g' does not match the state, then

• Choose an operator 'o' whose add-list matches goal g
• Push 'o' on the opstack
• Add the preconditions of 'o' to the goalset

3. While all preconditions of operator on top of opstack are met in state

• Pop operator o from top of opstack
• state = apply(o, state)
• plan = [plan; o]