In this article we will discuss about:- 1. Issues Involved In Planning 2. Planning With Situation Calculus 3. Hierarchical Planning.
Issues Involved In Planning:
Let us assume that an agent using some standard search algorithm, say A*, is required to solve a tough real world problem; the obvious realisation would be the generation of irrelevant actions which should be avoided. To illustrate this consider the task of guiding a robot around in a house. Even description of a simple state is very large since we must describe the location of each and every object in the house surrounding the robot.
A given action of the robot changes only a small part of the total state, for example the robot pushes a table across the room then the location of the table and of all the objects on it will change. But the locations of other objects in the house will not change.
So instead of writing rules which describe transformation from one state into another we would write only those rules which describe the affected parts of the state to avoid unnecessary actions. For complete robot problem, if there are primitive propositions of each robot and there are d robots in the space, each one having the properties of ternary relations (at, on, between) there will be 2d3 states.
ADVERTISEMENTS:
So in order to solve such hard problems there are two choices- The first is just take things one step at a time and not really try to plan ahead. This approach is taken in reactive systems.
In reactive systems complete planning for the entire problems is avoided, rather the observable situation is used as a clue for further solution. A reactive system must have access to a knowledge base of some sort which describes what actions should be taken and under what circumstances. So the reactive systems select actions one at a time rather than anticipating and selecting an entire action sequence before it does the first thing.
A simple example of reactive system can be a thermostat in a refrigerator or in room heating system. Its purpose is to keep temperature constant in the refrigerator/room. Depending upon how the external temperature changes during the day, how many times the door of the refrigerator/house opens etc., setting of the thermostat requires a lot of planning. Thus, the reactive systems are capable of surprisingly complex behaviour.
A reactive system with two interactive goals is shown in Fig. 8.7. If we work on the component goal ON (B, C) first, we easily find the solution PICKUP (B), STACK (B, C). When we apply this sequence of operators the state of the world would change so that a solution to the other component goal, ON (A, B) would become more difficult. Further, any solution to ON (A, B) from this state would “undo” the achieved goal ON (B, C).
On the other hand, if we work on the goal ON (A, B) first, we can achieve it by the sequence of operators (UN-STACK(C, A) ON(C, A), PUTDOWN(C), STACK (A, B). Again the state of the block world would change to one from which the other component goal ON (B, C) would become harder to solve. There seems no way to solve this problem by selecting one component, solving it and then solving the other component without undoing the solution to the first.
We say that the component goals to the problem interact. Solving one goal undoes an independently derived solution to the other. In general, when a forward production system is non-commutative, the corresponding backward system is not decomposable and cannot work on component goals independently. Interactions caused by the non-commutative effects of forward rule applications prevent us from being able to use successfully the strategy of combining independent solution for each component.
The main advantage of reactive systems over the traditional planners is that they operate robustly in domains which are otherwise difficult to model completely and accurately. They dispense with modeling altogether and base their actions directly on their perception of the world. Yet another advantage is that they are extremely responsive, since they avoid the combinational explosion involved in deliberative planning. However they are not useful in many AI tasks which require significant deliberation implemented as internal search.
ADVERTISEMENTS:
That is why a purely reactive system is not expected to play expert chess. It is however possible to provide a reactive system with rudimentary planning capability and that too by explicitly storing whole plans along with the situations which should initiate them.
The second alternative is to generate a plan which is likely to succeed. But if this strategy too fails then what to do? One way is to throw away the rest of the plan and start the process of planning afresh taking current solution as the initial states. Sometimes this is workable. But when the unexpected consequence does not invalidate the entire rest of the plan, perhaps a small change, such as an additional step is all which is necessary to make it possible for the rest of plan to be workable.
This is particularly true for decomposable or nearly decomposable problems. If the final plan is really a composite of many smaller plans for solving a set of sub-problems, then if one step of plan fails, the only part of the remaining plan which can be affected is the rest of the plan for solving that sub-problem.
The rest of the plan is unrelated to that step. If the problem was only partially decomposable, then any sub-plans which interact with the affected one may also be affected. So, just as it is important during the planning process to keep track of interactions as they arise, it is equally important to record information about interactions along with final plan so that if unexpected events occur at execution time the interactions can be considered during re-planning.
ADVERTISEMENTS:
Hardly any problem solving is completely predictable. So we must be always prepared to have plans fail. But if the plan has been prepared by decomposing our problem into as many separate or nearly separate sub-problems as is quite possible, then the impact of failure of one particular step may be quite local and repairable.
Thus, the problem decomposition and its consequent change in the plan at local-level has the following advantages in planning in an unpredictable world:
I. Reduces the complexity of problem-solving process.
II. Reduces the complexity of the dynamic plan revision process.
ADVERTISEMENTS:
Thus, in addition to recording steps to be performed, associate with each step the reasons why this was performed. The advantage of doing this is that if any step fails at the final stage, using dependency-directed backtracking, it can be known which of the remaining parts of the plan were dependent on it and so may need to be changed.
Moreover, the plan generation can proceed either in the forward direction or in the backward direction. It is known that in the forward going branching factor is more than that in the backward going. Moreover, the necessary dependencies may be difficult in the forward direction, so mostly planning systems work in a goal directed mode in which they search backwards from a goal state to the initial (achievable) state.
The problem of planning is thus quite demanding, involving many hurdles, a few being:
1. It is over whelmed by many irrelevant actions.
2. So needs a good heuristic function.
3. Needs decomposing a problem into non-interactive components, as problem decomposing technique contributes significantly to the efficacy of constraints under which the plan is bound to work.
Planning With Situation Calculus:
Situation calculus theorem states that given the initial state and the successor state axioms which define the effects of actions, the goal will be true in a situation which results from a certain action sequence.
Add to situation calculus the assumption of the satisfiability of a logical sentence then the planning, using propositional calculus will look like:
initial state ˄ all possible action descriptions ˄ goal.
The sentence will contain proposition symbols corresponding to every possible action taking place. A model which satisfies this sentence will assign true to the actions which form part of the correct plan and false to other actions.
In the air-transport problem in the initial state (time 0) plane P1 is airport regret in convenience Chennai and the plane P2 at Mumbai. The goal is to have plane P1 at Mumbai and plane P2 at Chennai that is the planes are to swap their positions. So, we need to have distinct proposition symbols for assertion about each time step, here we use superscripts to denote time steps. Thus, the initial state will be
At(P1, Chennai)0 ˄ At(P2, Mumbai)0
At (P1, Mumbai)0 is an atomic symbol. Since propositional logic has no closed world assumption we must specify the propositions which are not true in the initial state.
So the following propositions must also be specified:
¬ At(P1 Mumbai)0 ˄ ¬ At(P2, Chennai)0
Moreover, the goal must also be associated with a time step. Since we do not know a priori how many steps it takes to achieve the goal we can try asserting that goal is true even in the initial state, Time = 0. That is
At (P1 Mumbai) 0 ˄ At (P2, Chennai)0
If that fails we try again with T = 1 and continue with the next time step till we reach the minimum possible time length. For each value of T, the knowledge base will include only sentence covering the time steps from T = 0 to T = T, including Tmax‘ the upper time limit, to mark the termination.
Another issue is how to encode action descriptions in propositional logic. A simple approach is to have one propositional symbol for each action, that is,
Fly (P1 Chennai, Mumbai)0
is true if plane P1 flies from Chennai to Mumbai at time 0.
Then, using the situation calculus the successor – state axioms are:
At (P1, Mumbai)1 ↔ (At (P1, Mumbai)0 ˄ ¬ (Fly (P1, Mumbai, Chennai)0
˄ At(P1 Mumbai)0)) v (Fly(P1, Chennai, Mumbai)
˄ At(P1 Chennai)0)
In English, it translates into that a plane P1 will be at Mumbai at time step 1 if it was at Mumbai at time step 0 and did not flyaway or it was at Chennai at time step 0 and flew to Mumbai. We need such an axiom for each plane, airport and time step. Moreover, each additional airport adds more disjuncts to the right hand side of each axiom.
After having the axioms we can run the satisfiability algorithm to find a plan. There need to be a plan which achieves the goal at time T = 1, the plan in which the two planes swap their places. Now suppose the KB is
initial state ˄ successor-state axiom ˄ goal’
which means that the goal is true at time T = 1. We can verify that if the assignments
Fly (P1Mumbai, Chennai)0
and Fly(P1 Chennai, Mumbai)0
are true and other action symbols are false then that is a model of the given KB. There are other possible models returned by satisfiability algorithm but which may not give satisfactory plans. To avoid such plans which generate all sorts of actions, including illegal ones, we must add pre-condition axioms. When such pre-condition axioms are added then there is exactly one model which satisfies all the axioms when the goal is to be achieved in a time step.
More surprises come when a third airport, say Delhi is to be added. Now each plane has two legal actions in each state.
Then, a model with:
Fly (P1 Mumbai, Chennai)0
Fly (P1Chennai, Mumbai)0 and
Fly (P1 Mumbai, Delhi)0
satisfies all the axioms. That is, the successor state and pre-condition axioms allow a plane to fly to two airports simultaneously. So action exclusion axioms, to prevent such simultaneous action, must be added.
For example, axioms like
¬ Fly (P2, Mumbai, Chennai)0 ˄ Fly(P2, Mumbai, Delhi)0
should be added to achieve complete exclusion. They in addition, force every plan to be ordered but the time steps increase, thus lengthening the computation.
Yet another better exclusion method can be, to rule out simultaneous actions, only if they interfere with each other, stated as:
ᗄp, x, y, t, x ≠ y →¬ (At (p, x)t ˄ At(p, y)t)
That is since no object can be in two places at the same time, a single plane cannot fly to two airports simultaneously. This fact combined with successor-state axioms implies that a plane cannot fly to two airports at the same time. Facts such as these are called state constraints (another type of constraints already dealt with in non-linear planning). These state constraints are often much more compact than action exclusion axioms.
Complexity of Propositional Encoding:
The principal drawback of the propositional approach is the bulky size of the KB. The action schema Fly (p, a1 a2) becomes T x │Planes | x | Airports |2 propositional symbols. In general, the total number of action symbols is
T x |Act| x │O│p
where, Act is the number of action schema,
|0| is the number of objects in the domain,.
p is the maximum arity of any action schema.
For example, with 10 time steps, 12 planes and 30 airports, the complete action schema has 583 million clauses.
Because the number of action symbols is exponential in the arity of the action schema, one way to reduce this number is to reduce the arity. This can be done by borrowing the idea from semantic networks. Semantic networks use only binary predicates; predicates with more arguments are reduced to a set of binary predicates which describe each argument separately.
Applying this idea to action symbol such as:
Fly (P1Chenna i, Mumbai) 0
We get three new symbols:
Fly 1 (P1)0: plane P1 flew at time 0
Fly 2 (Chennai) 0: the origin of the flight was Chennai
Fly 3 (Mumbai) 0: the destination of the flight was Mumbai.
This process, called symbol splitting eliminates the need of exponential number of symbols. Now we need
T x |Act| x |O| symbols.
Symbol splitting, by itself, does reduce the number of symbols but the number of axioms in the knowledge base are not reduced automatically. That is, if each action symbol in each clause were simply replaced by conjunction of three symbols then the total size of the KB would remain roughly the same.
But symbol splitting does actually reduce the size of the KB because some of the split symbols will be irrelevant to certain axioms and can be omitted. Similar reductions occur within precondition axioms and action exclusion axioms.
Planning programs based on satisfiability can handle large planning problems. One most interesting finding which has emerged from such planning programs is that backtracking algorithms such as PDDL are often better at solving planning problems than local search algorithms such as WALKSTAT.
This is because the majority of propositional axioms are horn clauses which are handled efficiently by the unit propagation technique. This observation has led to the development of hybrid algorithms combining some random search with backtracking and unit propagation. These are not dealt with here.
Hierarchical Planning:
Thus, we have seen that in order to solve hard problems the planner may have to generate long plans. It is possible to eliminate some of the details of the problem till the solution which addresses the main issue is found. Then an attempt is made to fill in the appropriate details.
Earlier attempts in this direction were based on macro-operators. Later approach was in ABSTRIPS system, which was planned in a hierarchy of abstraction spaces, in each of which preconditions at a lower level of abstraction were ignored and it planned in a hierarchy of abstraction spaces.
ABSTRIPS works as follows:
First solve the problem completely, considering only preconditions whose criticality value is the highest possible. These values reflect the expected difficulty of satisfying the preconditions. Preconditions having lower than the peak criticality are ignored.
The constructed plan is used as the outline of a complete plan and consider preconditions at the next-lowest criticality level. Argument the plan with operators which satisfy those preconditions. Again, in choosing operators, we ignore all preconditions whose criticality is less than the level we are now considering.
We continue with this process of considering less and less critical preconditions until all of the preconditions of the original rules have been considered. Because this process explores the entire plans at one level of detail before it looks at the lower- level details of any of them, it is called length-first search. The assignment of appropriate criticality values is crucial to the success of this hierarchial approach. The conditions which no operator(s) can satisfy are clearly the most crucial.
For a hierarchial planning system to work with STRIPS-like rules it must include the appropriate criticality value for each term which may occur in a precondition, in addition to the rules. By making use of this criticality value the hierarchial planning process becomes as simple as non-hierarchial planning. This avoids wasting of effort in filling in the details of plans which are not useful in solving the problem.
Work in AI planning which arose from investigation into state space search, theorem proving and control theory and from practical needs of robotics, scheduling and other domains is still continuing. Helmert (2001) analyses several classes of planning problems and shows that constraint-based approaches such as GRAPHPLAN and STAPLAN are best for NP-board domains, while search-based approaches do better in domains where feasible solutions can be found without backtracking.