A Robot Planning Structure Using Production Rules

A ROBOT PLANNING STRUCTURE USING PRODUCTION RULES

Ralph P. Sobek*

Laberateire d'Automatique et d'Analyse des Systemes du C.N.R.S. 7, avenue du Colonel-Reche

F-31077 Toulouse CEDEX, FRANCE

select processing strategies appropriate to each situation encountered and be able to handle complex goal descriptions.

FPS is rule-based principally for the follow­ ing reasons. Production System (PS) rules allo'l' ' for a neat solution to the frame problern when we use the STRIPS assumption (Waldinger, 1981) in that all updates in the model are done explicitly through rules. Since rules can react in one PS cycle PSs can adapt to new situations very rapidly, the rules acting like deamons. In planning or execution monitaring this fact allows the system to deal with unexpected/serependitious situations. In addition, rule interactions may permit parallel searchs for a best solution or may allow rapi d responses to recognized problern situations (~. planning goal conflicts). In a PS the addition of knowledge is incremental. Therefore, the evolution of our robotic environment will be easily charac­ terizable to FPS. Also, in the future our use of a PS architecture will permit FPS to organize and generalize the plans that it has created as new rules.

Some may say that PSs are inefficient. It has been shown that by the use of compilation strategies significant gains in execution speed are attainable (Gupta and Forgy, 1983). FPS is imple­ mented in the PSI production system lan?uage (Sobek, 1983). It does not have to sacrifice effi­ ciency for flexibility in its representation since

PSI is a compiled PS. Rule patterns are compiled into a parallel-match tree similar to but more general than OPS (Forgy, 1982). The advantages of PSs have been adequately described in (Davis and King, 1976). Some planners and expert syste~s have opted for a frame-based approach (Minsky, 1975). It should be noted that there is a similarity between PSs and frame-based systems.

PLANHING STRUCTURE

We present a robot planner (FPS) which deals with the dynamics of a plan. FPS has in its ances­ try STRIPS (Fikes, et al, 1971), NOAH (Sacerdoti, 1977), and especiaTIYJASON (Sobek, 1975). It generalizes these planners in representation and flexibility. FPS is used in a real-world mobile­ rebot 'blocks-world' paradigm: the HILARE project. Superficially, FPS is similar to NOAH and its gel'­ eralization JASON in that they are goal-oriented. Where plans for NOAH consist of a directed graph of procedures (procedural net), in FPS plans may be

Abstract

Robot plan generation is a field which engen­ dered the development of AI languages and rule­ based expert systems. Utilization of these latter concepts permits a flexible formalism for robot planning research. We present a robot plan-genera­ tion architecture and its application to a real­ world mobile robot system. The system undergoes tests through its utilization in the HILARE robot project (Giralt, et al, 1984). Though the article concentrates on planning, execution monitaring and error recovery are discussed. The system inc lud es models of its synergistic environment as well as of its sensors and effectors (i.e. operators). Its rules embody both planning specific and domain specific knowledge. The system gains generality and adaptiveness through the use of planning vari­ ables which provide constraints to the plan genera­ tion system. It is implemented in an efficient compiled Production System language (PSI).

INTRODUCTIOH

In general, a problern is a situation for which an organism (or program) does not have a ready response. Problem solving involves 1) sensing and identification of a problern, 2) formulation of the problern in werkable terms, 3) utilization of rele­ vant information, and 4) generation and evaluation of hypotheses. A planner is a program that at­ tempts to deal with points 2 through 4. In this paper we present a rule-based plan generation sys­ tem called FPS (for Flexible Planning System). This system undergoes tests in a real-world robotic environment (the HILARE project [Giralt, ~ ~.

1984)).

In such an environment what is a plan? It has to be a flexible and extensible structure which permits quick adaptation to unexpected situations. It must per~it goal-directed as well as data-di­ rected processing. Goal simultaneity and interac­ tion must be verified during planning and before attempted execution. In a real-world environment a multitude of error situations may arise. Besides correction of planning errors a planner must try to determine when an error is recoverable or when replanning is necessary. Planners must be able to described as a directed rraph of prccesses. Each process contains its state in 2 structure called a "planninp node" each with its associated goal (see Table 1). A process characterizes the dynamics of a plan step while the planning node representes the data aspects. A process gets its node's entries filled from three principal sources: 1) from the parent node, 2) when an operator is selected for a node, or 3) by the executive, critic, task communi­ cation, and screduling rules. The processes are manaped by 2 taskin~t executive which arran~tes the processes on a priority a~tenda takin~ into account for each process the importance, success, cost expended, 2nd estimated allocated cost. The inter­ process ccordination and high-level conflict reso­ lution knowled~te are called planninp specific and are represented in rules. For examp1e:

* The author is presently on visit from the Univer­ supported in part by Agence de l'Informatique

sity of California at Berkeley. This research is contract 84/723.

If all siblinp* children of a process have achieved its preconditions then check if the process can be decomposed into sub­ processes.

1. Goal Pattern
2. Goal Instantiations
3. Preconditions/Enablements
4. Continuation Conditions
5. Post-Conditions (including goal pattern)
6. Constraint Conditions
7. Parent
8. Children associated by each decomposition
9. Importance
10. Allocated Cost Estimate
11. Cost Expended
12. Success Rate for each Post-Condition
13. Error Recovery Handles: reason, source, locally recoverable
14. Operator List
15. Script

Table I. Planning Node Entries

Simple ~toals in FPS may consist of a relation­ Al predicate, ~· (INROOM BLOCK! RM3), i ts nega­ ticn, or the application of a specific operator to a poal. Compound goals may be conjunctions or seouences of goals. Compound goals let FPS search for possible conflicts whereas sequences specify an explicit required erdering of the goals involved.

A relational predicate may also contain "plan­ ning variables" sitr.i lar to those developed by the author in (Sobek, 1975) and those reinvented in SIPE (Wilkins, 1983). These variables do not actu­ ally contain values; they may specify restrictions upon the allowed values (bindings) that their posi­ tions in a predicate may take, ~· in the predi­ cate (INROOM ROBOT $RM) the variable $RM may speci­ fy a nurober of possible instantiations for the predicate. The planning variables serve three f~;nctions: 1) an c-.ltern.o.tive to disj~·nctive goals with simi lar di sjuncts, 2) a method for the post­ ponement of decisions, and 3) constraint expres­ sions.

* The sibl inp processes are all chi ldren of a process which are conjoined by the same goal in­ stantiation ofthe parent. The parent process might have multiple instantiations for its goal descrip­ tion and then would have a disjunctive group of siblinps for each instantiation.

Ccnstraints may be attached to goals, planninp nodes, and Operators. Constraints are similar to ~toals except that they must be satisfied for the preccnditior.s of a possible Operator as weil as durinp and after the operator's execution. They are taken into account in the node expansion proce­ dure ard can cause the insertion of additional plan steps before a node.

Planninp involves iteratior. of node expansion with plan criticism. Criticism tr.ay start as soon as a node is expanded, which eases a shortcoming of NOAH. NOAH could only apply its critics at the end of each expansion cycle. The critics in FPS are considered a major part of the planner's "planninp executive." They contain knowledge that i s rele­ vant to the entire planning process, i.e. both planninp specific and domain specific. Co~mitant and overlapping with critics are heuristic rules. For example:

• Hl. If multiple choices are possible then select one which minitr.izes cost, effort, or distance
• H2. If robot moves an object then it should not bleck a door

Hl is a general rule whereas H2 is domain specific.

The planner presents a model of the robot's possible actions within its environment; it cur­ rently does not model the robot's interactions. There is no representation for other purposive (goal oriented) organisms or causality cither than the robot's. The possible actions are modelled by operators.

Operators are dynamically selected for each planning node; no ~ priori connection between Oper­ ators and goals exists. Associated with operators

are preconditions (environmental context), Continu­ ation conditions, post-conditions, and constraints. The operators are erdered in a specialization/ generalization hierarchy. Operators may have scripts which specify how they should be reduced; the scripts may define conditionals, parallel paths, goals, constraints, and Sub-operator appli­ cations. If they contain subgoals then a sub­ process will be created for each subpoal. Other­ wise, the script will be checked by "critics" against the surrounding plan structure.

An example operator is GOTOROOM (see Fig. 1). Given a room ?ras argument, if the robot is in an adjoining room then it will try to apply sequen­ tially the two sub-scripts GOTODOOR and GOTHRUDOOR. These latter two scripts are Subordinate to GOTOROOM ~ in the current node's dynamic con­ text: a different call sequence would create another hierarchy of goals and operators. FPS would fan out from the goal state, ~· (INROOM ROBOT RMl), using the connexity graph pro­ vided by CONNECTS until it finds the currer.t state.

GOTOROOM:

argument:

preconditions:

script:

post-conditions:

?r

(INROOM ROBOT ?r2)

(CONNECTS ?d ?r ?r2)+

(SEQ (GOTODOOR ?d)

(GOTHRUDOOR ?d))

(INROOM ROBOT ?r)*

NOT (INROOM ROBOT ?r2)

• - primary result (goal condition)
• - static data

Figare I. GOTOROOM operator specification

The search could be breadth- first, depth-f i rst or depending on the situation it could even require heuristic rules which would remernher efficient routes once found. After a route is found the two sub-ordinate scripts are tried in order to assure that the robot can get to and through the door. If there are multiple doors to a room, each would cause two parallel descendant nodes to be created.

An operator's goal is specified to the system as the primary post-condition. The above operator can also be invoked to get the robot out of a particular room. Each time that an operator succeeds with respect to a goal its correspondent level of importance or competence is rewarded.

EIECUTION MONITOR

What distinguishes planning from execution monitoring is that in the former a coherent plan­ ning structure is established, whereas in the lat­ ter the necessary verifications of coherence must come from the real-world environment. Note that a large part of the representation for both planning and execution monitoring must be the same in both in order to facilitate their communicat i on and aharing of models. Thus, execution monitoring uses the same planning structures to establish when error recovery should be initiated. An error situ­ ation is detected when there is a discrepancy be­ tween an operator's expected possible outcomes and the real-world responses (Srinivas, 1977). These di screpancies are analysed by execution-error critics which determine whether the error is 1) unimportant, 2) has a fixed solution, or that 3) replanning will be necessary.

CONCLUSION

FPS combines domain-independent plan structuring critics with domain specific con­ straints and critics. They watch over a general and flexible plan structure. Since the system is rule-based, heuristics may be added at any level; for the moment few exist. Their usefulness should become apparent when FPS performs error recovery and replanning. Current work includes making the system more robust and the addition of the execu­ tion monitor.

Acknovledgements

The author would like to thank everyone involved with the HILARE project for providing the necessary support for a real-world testbed for FPS .

HEFERENCES

• Davis, R. and J. King. An Overview of Production Systems, in E. W. Elcock and D. Mich i e (Eds.) Machine Intelligence, 8 (Wiley, New York, 1976), 300 332.
• Fikes, R. et al. Learning and Execut i ng Gener­ alizedRobot Plans, in N. Nilsson and B. Webher (Eds.) Resdings in Artificial Intelli­ gence (Tioga Publishing, Palo Alto, CA, 1981), 231-249.
• Forgy, C. Rete: A Fast Algorithm for the Many Pattern/Many Object Pattern Match Problem, Artificial Intelligence, 12 (1982) 17- 37.
• Giralt, G. et al. An Integrated Navigation and Motion-control System for Autonomous Multisen­ sory Mobile Robots, in M. Brady and R. Pau1 (Eds.) Robotics Research: The First Interna­ tional Symposium (MIT PreS"s,"" Mass.), 191-214.
• Gupta, A. and C. Forgy. Measurements on Production Systems, Technical Report CMU-CS-83-167, Carnegie-Mellon University, December 1983.
• Minsky, M. Framewerk for Representing Knowledge, in P. Winston (Ed.) The Psychology of Computer Vision (McGraw-Hill, 1975).
• Sacerdoti, E. A Structure for Plans and Behavior, Elsevier, North-Hollan~New Yor~1977.
• Sobek, R. Automatie Generation and Execution of Complex Robot Plans, Master's Project Report, Electrical Engineering and Computer Seiences Dept., University of California, Berkeley (September 1975).
• ---------- Achieving Generality and Efficiency in a Production System Architecture. LAAS-CNRS Interna! Memo, 1983.
• Srinivas, S. Error Recovery in Robot Systems. Ph.D. Thesis, Computer Science Dept., California Institute of Technology (1977).
• Waldinger, R. Achieving Several Goals Simulta­ neously, in N. Ni lsson and B. Webher (Eds.) Readings in Artificial Intelligence (Tioga Publishing, Palo Alto, CA, 1981) , 250-271.
• Wilkins, D. Representation in a Domain-Independent Planner, IJCAI-83, Karlsruhe, West Germany, 1983, 733-740.-