Planning in Artificial Intelligence
In Artificial Intelligence, there are agents which perceive the environment via sensors and act upon the environment through actuators or effectors. Just like humans have sensors through which we sense our surroundings (eyes, ears, nose, tongue, and skin) and actuators (limbs) to perform actions on these surroundings. The agent starts from the initial state and performs a series of actions in order to reach the goal state. For instance, a vacuum cleaner agent will perform actions of moving right and left, and sucking in dirt to reach the goal of successfully cleaning the environment.
Planning and its types
This activity of coming up with a sequence of actions in order to accomplish the target or goal is called as Planning. Planning can be Classical or Non-classical. In case of Classical Planning, the environment is fully observable, deterministic, static and discrete, whereas in case of Non-classical Planning, the environment is partially observable (i.e. the entire state of the environment is not visible at a given instant) or non- deterministic (or stochastic, i.e. the current state and chosen action cannot completely determine the next state of the environment).
Planning languages
Representation of Planning problems is often done using STRIPS (Stanford Research Institute Problem Solver). It consists of:
A set of states- It is a conjunction of positive ground literals.
A set of goals- partially specified state represented as a conjunction of positive literals, and
A set of actions- For each action, there is a precondition that must be satisfied and an effect which reflects the impact the action has on the environment after it has been performed.
Planning problems can also be represented using PDDL (Planning Domain Definition Language).
Planning using State Space Search
State space consists of the initial state, set of goal states, set of actions or operations, set of states and the path cost. This state space needs to be searched to find a sequence of actions leading to the goal state. This can be done in the forward or backward direction.
Forward State Space Search
It is also called Progression. It starts from the initial state and searches in the forward direction till we reach the goal. It uses STRIPS representation. This is how the problem formulation looks like.
Initial state: start state
Actions: Each action has a particular precondition to be satisfied before the action can be performed and an effect that the action will have on the environment.
Goal test: To check if the current state is the goal state or not.
Step cost: Cost of each step which is assumed to be 1.
FSSS starts from the initial state and applies actions to reach the next state. It then checks whether this state is the goal state or not. If not, it continues to apply other actions till the goal is reached.
Let’s take an example of the Air cargo problem. Here P1 and P2 are the two planes and A and B are the two airports. We start from the initial state and use the problem’s actions to search forward for the goal state.
Backward State Space Search
It is also called as Regression. It uses STRIPS representation. The problem formulation is similar to that of FSSS and consists of the initial state, actions, goal test and step cost. In BSSS, the searching starts from the goal state, and moves in the backward direction until the initial state is reached. It starts at the goal, checks if it is the initial state. If not, it applies the inverse of the actions to produce sub goals until start state is reached. For instance,
Total Order planning (TOP)
FSSS and BSSS are examples of TOP. They only explore linear sequences of actions from start to goal state, They cannot take advantage of problem decomposition, i.e. splitting the problem into smaller sub-problems and solving them individually.
Partial Order Planning (POP)
It works on problem decomposition. It will divide the problem into parts and achieve these sub goals independently. It solves the sub problems with sub plans and then combines these sub plans and reorders them based on requirements. In POP, ordering of the actions is partial. It does not specify which action will come first out of the two actions which are placed in the plan. Let’s look at this with the help of an example. The problem of wearing shoes can be performed through total order or partial order planning.
Init: Barefoot
Goal: RightShoeOn ^ LeftShoeOn
Action: 1. RightShoeOn
Precondition: RightSockOn
Effect: RightShoeOn
2. LeftShoeOn
Precondition: LeftSockOn
Effect: LeftShoeOn
3. LeftSockOn
Precondition: Barefoot
Effect: LeftSockOn
4. RightSockOn
Precondition: Barefoot
Effect: RightSockOn
The TOP consists of six sequences, one of which can be taken in order to reach the finish state. However, the POP is less complex. It combines two action sequences. The first branch covers the left sock and left shoe. To wear left shoe, wearing the left sock is a precondition. Similarly the second branch covers the right sock and right show. Once these actions are taken, we achieve our goal and reach the finish state.
Defining a Partial Order Plan
- A set of actions, that make up the steps of the plan. For instance, {RightShoe, RightSock, LeftShoe, LeftSock, Start, Finish}.
- A set of ordering constraints, A before B. For instance, {RightSock < RightShoe, LeftSock < LeftShoe}.
- A set of causal links, A achieves P for B.
- A set of open preconditions. A precondition is open if it is not achieved by some action in the plan.
Hierarchical Planning
Here the plans are organized in a hierarchical format. It works on plan decomposition. Complex actions are decomposed into simpler or primitive ones and it can be denoted with the help of links between various states at different levels of the hierarchy. This is called operator expansion.
Primitive tasks- these correspond to the actions of STRIPS,
Compound tasks- these are a set of simpler tasks,
Goal tasks- these correspond to goals of STRIPS.
In Hierarchical Planning, we find a sequence of primitive tasks by decomposition of compound tasks, in order to reach the goal. For example, in case of building a house, hierarchical planning is used as shown below.
Conditional Planning
It works regardless of the outcome of an action. It deals with uncertainty by inspecting what is happening in the environment at predetermined points in the plan. It can take place in fully observable and non-deterministic environments. It will take actions and must be able to handle every outcome for the action taken. For instance, If <test-cond> then plan A else plan B. In case of a vacuum cleaner problem, If At Left ^ Clean then Right else Suck.
Gain Access to Expert View — Subscribe to DDI Intel
