Syntax and Semantics of Planning | Problem Solving | Artificial Intelligence

In this article we will discuss about the syntax and semantics of planning to solve AI problems.

Syntax of Planning:

The representation of planning problems in different separable structures (states, actions and goals) syntactically should facilitate the planning algorithms of the problem. The key is to find a language which is expressive enough to describe a wide variety of problems, but restrictive enough to allow efficient algorithms to operate over it. The basic representation language of classical planners is STRIPS. This language was one of the early robot problem solving systems and stands for Stand ford Research Institute Problem Solver.

This was one of the early robot-problem solving system. STRIPS maintains a stack of goals and focuses its problem solving effort on the top goal of the stack. Initially, the goal stack contains just the main goal. Whenever the top goal in the goal stack matches the current goal description it is eliminated from the stack and the match substitution is applied to the expressions beneath it in the stack.

If the top goal in the goal stack is a compound goal STRIPS adds each of the compound goal literals, in same order, above the compound goal in the goal stack. The idea is that STRIPS work on these component goals in the order in which they appear on the stack. When all the component goals are solved it reconsiders the compound goal relisting the components on the stack if the components goal does not match the current state description.

This reconsideration of the compound goal though primitive, is the safety feature which STRIPS used to deal with the interacting goals problem. If solving one component undoes an already solved component the undone goal is reconsidered and solved again, if needed.

When the top (unsolved) goal on the stack is a single-literal, STRIPS looks for the rules (forward) whose add list contains a literal which can be matched to it. The match instance of this rule then replaces the single-literal goal at the top of the stack. On the top of the rule is then added the match instance of its pre-condition formula. If top is compound and does not match the current state description, its components are added above it, in some order on the stock.

When the top item on the stack is a rule, it is because of the fact that precondition formula of this rule was by the current state description and removed from the stack. Thus, the rule is applicable and it is applied to the current state description and removed from the top of the stack. The new description is now used in place of the original one and the system keeps track of the rule which has been applied for later use in comparing a solving sequence.

Control Strategies for STRIPS:

Several decisions must be made by component of the STRIPS system.

We shall mention some of them briefly:

First, it must decide how to order the components of a compound goal above the compound goal stack. A reasonable approach is first to find all of those components which match the current state description. They are put on the top of the stack and then immediately stripped off.

This step leaves only the unmatched goals to be ordered. We could create a new successor node for each possible ordering or we could select just one of them arbitrarily (heuristically judged to be the hardest) and create a successor node in which only that component goal is put on the stack.

The latter approach is probably adequate because after this single goal is solved, we will confront the compound goal again and have the opportunity to select another one of its unachieved components.

When (existentially quantified) variables occur in the goal stack, the control component may need to make a choice from among several possible instantiations. We can assume that a different successor can be created for each possible instantiation. When more than one STRIPS rule would achieve the top goal on the goal stack, we are again faced with a choice. Each relevant rule can produce a different successor node.

A Graph-Search:

A graph-search control strategy must be able to make a selection of which leaf node to work on in the problem-solving graph. Any of the search methods might be used here; in particular, we might develop a heuristic evaluation function over these nodes taking into account, for example, such factors as length of the goal stack, difficulty of the problems on the goal stack, cost of the STRIPS rules, etc.

An interesting special case of STRIPS can be developed if we decide to use a backtracking control strategy instead of a graph-search control strategy. Here we can imagine a recursive function called STRIPS which calls itself to solve the top goal on the stack. In this case, the explicit use of a goal stack can be supplanted by the built-in stack mechanism of the language (such as LISP) in which recursive STRIPS is implemented.

The program for recursive STRIPS would look something like the following:

First, we set S, a global variable, to the initial state description. (We call the program initially with the argument, G, the goal that STRIPS is trying to achieve).

Recursive Procedure STRIPS (G).

1. Until S matches G So; the main loop of

STRIPS is iterative

2. Begin

3. g ← a component of G which does not match

S; a node deterministic selection and

therefore a backtracking point

4. f ← a rule whose add list contains a literal which matches g; another backtracking point

5. P ← preconditions formula of appropriate instance of S

6. STRIPS (p); a recursive call to solve the sub-problem

7. S ← result of arriving appropriate instance of f to S

8. end.

Thus, STRIPS is a kind of production system in which the global data is a combination of the current state description and the goal stack. Operations on this data base produce changes in the current state or goal stack. The process continues until the stack is empty. The rules of this production system are then the rules which transform one global data base into another.

The operation of the STRIPS system with graph, a graph-search control strategy produces a graph of global data bases and a solution corresponds to a path in this graph leading from the start to a termination node. A termination node is one labelled by a base having an empty goal stack.

Representation of States:

Planners decompose the world into logical conditions and represent a state as a conjunction of positive literals-which could be propositional literals, such as Poor Unknown or first order literals such as At (Plane 1, Mumbai) ∧ At (Plane A2, Chennai). Literals in the first order state descriptions must be ground and function free. That is literals such as At (x, y) or At (Father (Mumbai), INDIA) are not allowed. The CLOSED WORLD assumption that is any conditions which are not mentioned in a state are assumed false.

Representation of Goals:

A goal is partially specified state, represented as a conjunction of positive ground literals, such as Rich ˄ Famous or At (P2, Mumbai). A propositional state S satisfies a goal g if S contains all the atoms in g. For example, the state Rich ˄ Famous ˄ Miserable satisfies the goal Rich ˄ Famous.

Representation of Actions:

An action is specified in terms of the pre-conditions which must hold before it can be executed and the effects which ensure when the action is executed.

For example, an action for flying a plane from one location to another is:

Action; (Fly (p, from, to),

Precond: At (p, from ˄ Plane (p)˄ Airport (from) ˄ Airport (to)

Effect: ¬ At (p, from) ˄ At(p, to)

This (combination of Action, Precondition and Effect) is known as ACTION SCHEME, meaning that it represents a number of different actions which can be derived by instantiating the variables p, from and to different constants.

In general an action schema consists of three parts:

i. The action name and parameter list, for example, Fly (p, from, to) serves to identify the action.

ii. The precondition is a conjunction of the function-free positive literals stating what must be true in a state before the action can be executed. Any variables in the precondition must also appear in action’s parameter list.

iii. The effect is a conjunction of function free literals describing how the state changes when the action is executed. A positive literal P in the effect is asserted to be true in the state resulting from the action, whereas a negative literal ¬ P is asserted to be false. Variables in the effect must also appear in the action’s parameter list.

To improve readability, the action can be further sub-divided into:

i. ADD LIST for positive literal and

ii. The delete list for the negative literals.

Semantics of Planning:

This means how actions affect states. We say that an action is applicable in any state which satisfies the pre-condition otherwise, the action has no effect. For a first-order action scheme establishing applicability will involve a substitution for the variables in the precondition. For example, the current state operation.

At (P_1, Mumbai) ˄ At (P₂, Chennai) ˄ Plane (P₁) ˄ Plane (P₂)

˄ Airport (Mumbai) ˄ Airport (Chennai)

satisfies the pre-condition:

At (p, from) ˄ Plane (p) ˄ Airport (from) ˄ Airport (to),

with substitution

(p/P₁, from/Mumbai, to/Chennai).

Thus the concrete action

Fly (P₁‘ Mumbai, Chennai)

with

Pre-condition At (P₁, Mumbai)

Post-condition ¬ At (P_1, Mumbai)

is applicable.

Thus, starting in state S, the result of executing an applicable action a is a state S₁ which is the same as S except that any positive literal P in the effect of a is added to S₁ (and any negative literal ¬ P is removed from S₁. 

Thus, after the implementation of the above action Fly (P₁ Mumbai, Chennai) the current state becomes:

At (P₁, Chennai) ˄ At (P₂, Chennai) ˄ Plane (P₁) ˄ Plane (P₂) ˄ Airport (Mumbai) ˄ Airport (Chennai).

It may be pertinent to mention here that if a positive effect is already in S it is not added twice, and if a negative effect is not in S, then that part of effect is ignored. This definition of the current state embodies the STRIPS assumption: that every literal not mentioned in the effect remains unchanged. In this way, STRIPS avoids represental FRAME PROBLEM: there is no need of providing rules for those components of the state which are not affected by the operators.

That is not representing those things which stay same is called Frame Problem. The concept has taken birth from physics the assumed stationary background with respect to which motion is measured. Frame problem has also analogy to the frames of a movie, in which normally very little changes from one frame to the next.

Finally, we can define the solution for a planning problem. In its simplest form, this is just an action sequence, which when executed in the initial state results in a state which satisfies the goal.

We may note that some restrictions have been imposed on the use of STRIPS as representation language, an important one being; that the literals must be function- free. With this restriction, we can be sure that any action scheme for a given problem can be propositionalised (purely propositional action representation without any variable). For example, in the air cargo example with 10 planes and 5 airports the

Fly (p, from, to) schema

could be translated into 10 x 5 x 5 = 250 purely propositional actions.

Simple planners do work with propositionalised descriptions, but infinitely large states and actions will be involved when the function symbols are allowed, (at present no constraints regarding the order of actions have been imposed).

Over the years it has been felt that STRIPS is insufficiently expressive for some real domains. As a result, many language variants have been developed-one simple one is Action Description Language or ADL. It has relaxed some of the restrictions imposed on the STRIPS language and has made it possible to encode more realistic problems. Its main features are compared with those of STRIPS language in the following table. In both cases goals behave as the preconditions of an action, with no parameters.

The corresponding FLY action in ADL becomes:

Action (Fly (p : plane, from: Airport, to : Airport),

PRECOND: At (p, from) ˄ (from ≠ to)

EFFECT: ˄ At (p, from) ˄ At (p, to).

The notation p: plane in the parameter list is an abbreviation for Plane (p) in the precondition. Though this does not add any expressive power, but it is easy to read and also cuts down the number of possible propositional actions which can be constructed. The precondition (from: j: to) expresses the fact that a flight cannot be made from an airport to itself.

This could not be expressed succinctly in STRIPS. The various planning formalisms used in Al have been systematised within a standard syntax called the Planning Domain Definition Language or PDDL. This language allows researchers to exchange benchmark problems and compare results. PDDL includes sublanguages for STRIPS, ADL and the hierarchial networks.

The STRIPS and ADL notations are quite adequate for many real domain, though there are still some significant restrictions. The most natural being ramifications of actions. For example, there are people, packages and some gadgets in the airplane, who too change location when the plane flies.

We are representing these changes as the direct effects of flying, whereas it seems more natural to represent the location of plane’s contents as a logical consequence of location of the plane. Classical planning systems do not even attempt to address the qualification problem: impossibility of listing all the preconditions required for a real world action to have its intented effect.

Many techniques of planning are available. But in order to make a comparative studies of these methods it is worth describing some domains on which these techniques can be applied, analysed and compared for their efficacy. Two examples of different domains have been described for the purpose.

Two Examples of Syntax and Semantics:

I. Air Cargo Transport:

Fig. 8.1 shows an air cargo transport problem involving loading and unloading cargo on to and off of planes and flying them from place-to-place.

The problem can be defined with three actions:

i. Load,

ii. Unload, and

iii. Fly.

The actions affect two predicates. In (c, p) meaning that cargo c is inside the plane p and At (x, a) meaning that object x (plane or cargo) is at airport a. However, cargo is not at anywhere when it is in a plane, so it really means available for use at a given location.

Taking into consideration these concepts the following plan is a solution to the problem:

[Load (C₁, P₁) Chennai), Fly (P₁Chennai, Mumbai),

Load (C₂, P₂, Mumbai), Fly (P₂, Mumbai, Chennai)]

Our representation is pure STRIPS. In particular it allows a plane to fly to and from the same airport. Inequality literals support in ADL could prevent this.

Block-World Description:

The block world (Fig. 8.2) has been discussed here briefly as this is one of the most famous planning domains.

There is a flat surface on which the blocks can be placed. There are a number of cube-shaped or square blocks, all of the same size sitting on a table top. They can be stacked one upon another. There is robot arm which can manipulate the blocks.

The actions it can do include:

i. Unstack (A, B):

Pick up block A, from its current position, on block B. The arm must be empty and block A must have no blocks on top of it.

ii. Stack (A, B):

Place block A on block B. The arm must already be holding A and the surface B must be clear.

iii. Pickup (A):

Pickup blocks from the table and hold it. The arm must be empty and there must be nothing on top of block A.

iv. Putdown (A):

Put block A down on table. The arm must have been holding block A.

v. The goal will always be to build one or more stalls of blocks, specified in terms of what blocks are M top of what other blocks.

Conditions:

(i) The robot arm can hold only one block at a time.

(ii) Each block can at most have one block directly on it. (all blocks being of equal size).

In order to satisfy these conditions under which an operation is performed and the results are obtained we need to have the following predicates:

Various logical statements are also true in this block world, for example: