Robot Planning System Based on Problem Solvers

1. Introduction

l 2 3 4 Papers ' ' ' have been p r esented hitherto concerning robot planning systems that understand instructions from an ope rator and which make plans for attaining goals.

Thi s paper 'describes a robot planning system developed for us e in a robot. This system is concerned with a robot with a hand and an eye which manipulates building-blocks in response to the orders of an operator.

Two different kinds of theorem provers are used to demonstrate the effectiveness of this planning system. One is based on the resolution principle, the other on pattern matching . The former is us ed in a problem solver whi ch understands the meaning of a statement and which decides a goal state corresponding to the statement. The latter is applied to a problem solver which effects a concrete job sequence to realize the goal state described above. These problem solvers are called GOAL-FINDER and JOB- SCHEDULER respectively .

The reason why two theorem provers are used in a robot planning system is that it is not necessarily profitable to process two operations, for example that of representing a state and of obtaining a job sequence, with

only one method.

A further feature of this planning system is that the procedural data structure is used for increasing efficiency in problem so lving processes. An outline of the robot planning system, descriptions of each of the problem solvers and future considerations are given in

the following chapters .

The problem solvers and the robo t plann­ ing system discussed in this paper would undoubtedly b e applicable in many fields .

2. The outlines of the robot planning system

The following problem is presented as an example of the working of a robot planning system. There are many blocks, of various shapes and colours, and working desks upon which a robot manipulates the blocks. The robot is made to build structures, such as a tower, a house, a bridge, etc . , in response to task instruction given by an operator to the robot in a resticted form as follows;

"BUILD A TOWER"

"BUILD A HOUSE WITH A RED ROOF", etc .

The robot attempts to determine the meanings of words or phrases, such as "a tower", "a house" and "with a r ed roof", from its knowl ­ edge. If it fails, it asks the operator to explain the meanings . The meanings of the concepts, "tower", "hous e " and "roof", are given to the robot as axioms in the form of first- order predicate calculus wffs. Inter­ preting the statement, the robot decides on a suitable state- representation for a bl ock building . This state-representation is called a ~oal state and is shown in the form of "(ON A tON CD))", whe r e (ON X Y) means "X is on Y".

The theorem prover based on the r esolu­ tion principle and on the functional data structure is used as a main tool in this part of the robot planning system . This part in the sys tern is called "GOAL-FINDER". Finding the goal state suitable for the statement, the robot must define a job sequence for construct­ ing the building. That is, a robot must decide the procedure to r ealiz e the goal state unde r some constraints. A theo r em prover bas ed on pattern matching is applied to this process. The theorem prover that constitutes this part of the system is called "JOB­ SCHEDULER II ·

Taking the goal state and the present state, JOB- SCHEDULER decides a job sequence given the constraints of the block world.

A diagram of the robot planning system is shown in Fig. l. The details of GOAL-FINDER and JOB- SCHEDULER are described in chapters 3 and 4 .

The relationships b etween the blocks manipulated by a robot and the characteristics of the blocks ( ex . shape, colour, position, etc .) are represented by FDS*. FDS forms a network and blocks with similar charact e ristics are connected. Therefore, the suitabl e problem domain may b e effectively established by the problem solver. For example, the problem domain composed of only red blocks can be ext racted from the block worl d in r e sponse to the statement .

3. An input interpreter and GOAL- FINDER

In this chapter, we shall describe an interpreter which construes input statements given by an operator and a state- oriented problem solver, GOAL-FINDER, which finds a

goal state to fulfill the statements .

GOAL-FINDER is made up of three major parts, a world model, a sto r age , which memorizes knowledge of concepts of block buildings, and the resolution theorem prover . This theorem prover is similar to QA35.

* FDS is an abbreviation of functional ~ata ~tructure.

3.1 An input interpreter and a world model

The main functions of this interpreter are to translate .statements into list forms and to deliver them to GOAL-FINDER. In the present stage, task statements given by an operator are restricted to the following two types for the sake of simplicity.

BUILD adjective noun with adjective~

MOVE adjective noun to E·

(where each adjective word or clause may be missing, and E represents the place where objects should be moved.) For example,

"BUILD A TALL TOWER WITH A RED PILLAR" is transformed into

BUILD (TOWER TALL (PILLAR RED)),

and such a statement as

"MOVE BLUE BLOCK TO PLACE- A" yields

MOVE PLACE-A (BLOCK BLUE).

In addition to imperative statements, this interpreter construes two types of declarative sentences written in the form of well formed formulas (wffs) in the predicate calculus . One type is a statement for chang­ ing the world model and the other is for changing knowledge. The interpreter also prints out the message when the planning system fails to perform its function, and requires further instructions .

FDS is employed to describe such world models as those described by shape, name, colour, position and spatial relationships of the blocks. One feature of this program is its ability to make up an associative network of current information in the world.

Because of this structure, all features of the block can be seen easily, and blocks having specific features can be selected.

3 . 2 Algorithms used in a problem solver which finds goal states

Here, we shall discuss the algorithms used in this problem solver, and explain how it finds a goal state which is suitable for task statement . An outline of the problem solving process is illustrated in Fig . 2. In explanation, let us briefly outline its processes .

First, the problem solver generates theorems to be proved corresponding to the statement, and

second it chooses the axioms which are necessary to prove the theorems and sets them up in each pr.oblem domain.

Thirdly it selects appropriate blocks from a world model and sets them up in each problem domain .

In conclusion, it proves theorems and produces a solution, i.e. a goal state .

• Thes e algorithms have the following three notable characteristics .
• (l) Because axioms are constructed in a tree structure, the meanings of statements are reflected systematically in the theorem proving process .
• Some adjective words in a statement are reflected in the process of selecting axioms . For example, an additional axiom which can produce tall building will be selected to build a "TALL TOWER" rather than an ordinary TOWER.
• Other adjective words are reflected in the processes by which blocks are selected . For example, only blue blocks are selected from a world model--:ro-build a "BLUE HOUSE".

Let us briefly describe the knowledge shown in Fig,. 2. The knowledge, we discuss here, involves the axioms, which the theorem prover is to use, and the generalized solu­ tions, where the generalized solution means a wffs which has been obtained by replacing constants in a so lution by the corresponding predicate letters.

For example, suppose a solution is "(ON A B)" and the following descriptions are given;

PRISM (A) and BLOCK (B).

"\ON PRISM BLOCK)" is stored as a general ­ ized solution and utilized in subsequent processes . Each piece of knowledge concerning an axiom consists of the name, the level, the corresponding adjective and the axiom itself and is stored in the form of list structures.

The axioms are given to the problem solver (GOAL-FINDER) in the form of predicate calculus wffs. Each axiom may or may not have leveling marks to represent the concepts, for example, "HOUSE", "TOWER" etc . , in the tree structures .

Using the axioms with the leveling marks, efficiency of procedure in GOAL- FINDER can be greatly increased.

In this case, the theorem prover inter­ prates the tree structure of a concept and introduces a solution containing the real objects .

As further explanations, we shall use a simple example.

[Example l)

Suppose the task statement is

"BUILD A TALL TOWER WITH A BLUE PILLAR ."

and the world model is as shown in Fig . 3-(2). In this example, the following two theorems to be proved are induced;

(aX) TOWER (X)

(ax) PILLAR (X).

The axioms are gathered in the following manner;

TOWER; level 0 (VXVY) (((ROOF X)(PILLAR Y))

~(TOWER (ON X Y)))*,

ROOF; level l (VX)((PRISM X) ~ (ROOF X)),

PILLAR; level l (VX) ((BRICK X):::> (PILLAR X)), PILLAR: level 1 tall (VXVY) (((PILLAR X)

(PILLAR Y)) ~ (PILLAR (ON X Y)))*

The last axiom is selected because there exists an adjective word TALL in the instruc­ tion.

The tree structure of axioms and theorems is shown in Fig . 4 .

In this figure, the adjective TALL belongs to the TOWER but it actually has an effect on the axiom of PILLAR with level 1. In addition, the adjective BLUE has an effect on the process of setting up the problem domain . That is, GOAL-FINDER sets up the world of only blue blocks as the solution

thus -

PILLAR (ON A C).

This is substituted into the axiom of TOWER using only PRISMs.

The solution obtained is as follows;

TOWER (ONE (ON A C)).

GOAL- FINDER delivers the following expression;

(ON E (ON A C ) ) ,

to JOB- SCHEDULER.(Fig. 3- (3))

4 . JOB-SCHEDULER

Suppose we supply the robot with the world model, the initial state and the goal state, and ask it to decide a sequence of actions to achieve the goal state. There are, of course, many constraints in the world of the robot . These constraints can be classi ­ fied into the following two categories;

1. actions - -- restrictions which are invariably accompanied by an action, and
2. states - -- limitations which are provided by the world.

In this chapter a problem solver, JOB- SCHED­ ULER, is used to produce a sequence of actions to attain the goal state.

4.1 Theorem prover used in JOB- SCHEDULER

A PLANNNER- like theorem prover6 is used to solve a job sheduling problem in order to obtain an action- sequence which will arrive at a goal state from a current state whilst under some constraints . Because of the flexibility of describing algorithms, two kinds of theorems are used in this theorem prover. They are as follows:

1. A theorem of which the result is described as a state when the action has a clear effect on the world . For example, such an action as "Put X on Y" creates a state "X is on Y" --- ; the pair of the action and the state becomes a general knowledge whereby the action corresponding to a state is directly obtained; and

* In these expressions existential quantifiers

had already been eliminated and the Skolem functions which repr esent the meanings of these quantifiers introduced.

1. A theorem which describes procedures; this theorem gives the procedure of execution, so that it is suitable for the description of an algorithm . As far as the control of execution is concerned, the constraint is described (1) in a theorem, as a precondition peculiar to the robot system . Or the con­ straint is described (2) as a variable condition to be referred according to the situations.

When a conditional expression in a theorem is not satisfied, the control of the program may be changed according to the indi­ cation for "F". If the indication is the name of a label used in the same theorem, the control becomes a simple jump like .the "GO TO" statement of the FORTRAN . On the other hand, if it is not, it will be interpreted as a branch of a new theorem and the following behaviours processed. The directed process is peformed and then the control returns to the branching point . If the conditional expres­ sion is still not satisfied, the control returns to last decision point and a new

decision is made.

4.2 Basic algorithm of JOB- SCHEDULER

The motivation for job schedulin~ is the difference between the current state { Sc ) and the goal state ( Sg ). Abstracting a new state, JOB-SCHEDULER sets up a subgoal . That is, within the basic framework JOB-SCHEDULER operates in a GPS- like manner7 . Let us out­ line the algorithm of JOB- SCHEDULER:

1. Transform the goal state ( Sg ) ~roduced in GOAL- FINDER and the world model ( Sp ) in FDS into prefix notations.
2. Set up restrictions to be duly considered in the process of the problem solving (job scheduling) and give effective means of settling trouble, for example, such a constraint as "more blocks than two cannot be put on the block !" is given in this theorem prover as follows;

(ADVICE (RANGE (?X ?Y)

(ALL ?Y)

(COND (AND ((ON ?X A) :F SUCCESS)

((ON ?Y ?X) :T FAIL F SUCCESS))))),

where "SUCCESS" and "FAIL" mean that this theorem ends in success and in failure respectively.

1. If the current state ( Sc ) coincides with the goal state ( Sg ), the algorithm terminates .
2. If there is any state, not previously selected, in the differences between Sc and Sg, select a new subgoal ( Ss ) out of the d~fferences . Otherwise, if it is impossible to select a new subgoal, backtrack to the preceding subgoal and reselect the other subgoal. If it is impossible, the algorithm terminates in unsolvability .
3. Try to get to Ss. If this fails, return to step (4). Otherwise, return to step ( 3) .

4 . 3 Algorithm to select a subgoal

Let us define the state ( Sa ) as the following equation ;

This represents the differences between the current state ( Sc ) and the goal state ( Sg ) . Suppose a subgoal ( Ss ) is defined according to a criterion, i.e .

An understanding of this algorithm is greatly aided by an simple example as follows: Su~pose Sc and Sg are given as shown in Fig . 5-(1) and 5-(2) respective ly. Representing Sc and Sg in the form of the prefix notation, we obtain the following;

Moreover, from the equation (1) we get

We give an ord~r of priority for each element of Sa in selecting a subgoal. For example, blocks must be succesively laid upon one another from bottom to top, therefore, ( ON A 3 ) is given the priority over ( ON D B) in this example. ( see Fig. 5-(4)). In fact, whether or not "?X" in ( ON ?X ?Y ) really exists at the suitable position in the goal state is checked, and then only elements suitable for this condition are selected as possibilities for the subgoal . Lastly, the order of priority of thes e possibilities is given to decide a subgoal .

In selection of a subgoal it sometimes happens that the same action is repeated and the goal state is not achieved . A special means of avoiding this inconvenience is devised in JOB-SCHEDULER ·as shown briefly in the next section .

4 . 4 Procedure to achieve a subgoal

In JOB-SCHEDULER, when such a subgoal as "( ON ?X ?Y )" is se lected, the theorem "FUTON" is implicitly called to realize the state "( ON ?X ?Y )".

The remainder of this section is a brief description of the representative theorems us ed to attain subgoals.

FUTON . [ ?X ; ?Y 1 : Putting ?X on ?Y, ?X must have no blocks on it, as it is picked up in the first place . Moreover, this applies to ?Y, too . After execution of this theorem, the world model varies.

TOPLESS [ ?X ; ?Y 1* : If there is no blocks on ?X, it can be said that ?X is top­ l ess. If not , blocks on ?X must b e removed to places other than ?Y.

REMOVE [ ?X ; ?Y 1* Removing ?X to any other place except ?Y, a space has to b e found and then ?X is put there .

SEARCHPLACE 1 [ ?U ; ?X 1* This theorem finds out a block other than ?X on which other blocks can be put.

SEARCHPLACE 2 [ ?U ; ?X 1 * : This pro­ vides a new intermediate desk other than ?X .

By using these theorems, a subgoal can be selected in JOB-SCHEDULER without the repeti­ tion of the same action. Because a prohibi­ tive position can be indicated in theorems.

As an example, we shall take up the same task as shown in [Example 11 of 3.2.

[Example 2 1

Suppose the goal state is a block building on the desk w 0 shown in Fig . 3-(3), i.e. it is

the initial state is given in Fig. 3-(1), that is,

and the intermediate desks are

We give JOB-SCHEDULER such an advice that more blocks than three cannot b e put on an intermediate desk;

(ADVICE (RANGE (?X ?Y ?Z ?U ?V)

(ALL ?X ?Y ?Z)

(<== ?V DESKS)

A (<== (?U ?V) ?V)

(COND ((EQUAL ?U NIL) : S SUCCESS F B))

B (COND (AND ((ON ?X ?U): FA)

((ON ?Y ?X): FA) ((ON ?Z ?Y): S FAIL FA))))) .

Using the preceding theorems as shown in Appendix, JOB-SCHEDULER produces a sequence of macro actions as follows;

( FUTON E W1 ) , ( FUTON D Wz ) , ( FUTON C Wo ), ( FUTON B D ), ( FUTON A C ), and ( FUTON E A ).

The transitions of states are shown in Fig. 6 .

Hereaft e r theorems of category 1 (actions) are intended to be partly learned by a robot itself in executing tasks, and it will be able to perform tasks more intelligently.

4. Conclusion and future considerations

The robot planning system developed by the robotics group in the Electrotechnical Laboratory has been described in this paper . The features of this system are as follows:

(1) A theorem prover based on the resolu­ tion principle is used to find the goal state of the problem . Another theorem prover based on pattern matching is applied to obtain a job sequence with which the goal state is achieved . That is, the former is to interpret concepts (states), and the latter is concerned with actions. As a result, both of these theorem provers do a share of the work according to their features.

* We can also use theorems with fewer arguments than shown in the preceding descriptions. For example, "TOPLESS [ ?X 1" means that an object on "?X" can be put on any other place in the world without restriction.

1. The efficiency of robot planning is increased by the structuring of axioms into trees in GOAL- FINDER and the modifying the theorem prover in JOB- SCHEDULER after the suitable manner for this system.

(3) FDS is adopted to raise efficiency of the system by setting up the problem domain.

The robot planning system described here is being combined with a hardware system developed in our laboratory and integrated into a total robot system.

Acknowledgement

The authors would like to express their gratitudes to the members of the robotics group of the Electrotechnical Laboratory for their helpful discussions and criticisms.