Planning Robot Control Parameter Values with Qualitative Reasoning

1 Introduction

Model-based intelligent robotic systems typically make use of numerical-especially geometric-representations of the robot and the workspace when planning robot motions in detail. Such plans, even after successful computer simulation with the model, frequently fail to achieve the intended results when actually executed by the robot. Approaches to overcoming this problem in­ clude precise calibration, more detailed modeling, error recovery, and human intervention.

The qualitative reasoning paradigm can help overcome some of the difficulties associated with error and uncer­ tainty by reasoning about the behavior of the physical equations describing a system, thereby providing the sys­ tem with intelligence about its own behavior and how to achieve desirable states.

·The research described in this paper wa.s performed a.t the Electrotechnical Laboratory, with support from the Jet Propulsion Laboratory, California. Institute of Technology, under contract with the N a.tional Aeronautics and Space Ad­ ministration of the United States of America, and support from the Agency of Industrial Science and Technology, Min­ istry of International Trade and Industry of Japan.

tElectrotechnical Laboratory 1-1-4 Umezono, Tsukuba Ibaraki 305, JAPAN

A considerable amount of theoretical work has been done on qualitative reasoning [De Kleer and Brown, 1984, Forbus, 1984, Kuipers; 1984, Kuipers, 1986, Sacks, 1990], but much of this work has focussed on simulation and has not specifically addressed planning issues. A topic currently receiving attention as real applications are attempted is the coordination of qualitative and nu­ merical elements [Kuipers and Berleant, 1988] to achieve a complete reasoning system.

This paper describes a qualitative reasoning plan­ ner which has been developed and integrated into the MEISTER (Model Enhanced Intelligent and Skillful TEieoperational Robot) system [Hirai and Sato, 1988, Hirai et al., 1990] and has been demonstrated for a match striking task. A qualitative reasoner and a numerical ex­ ecution history work together to search for effective con­ trol parameter values. The present work makes use of earlier studies on the application of qualitative reason­ ing to manipulation planning and the relevant fhysical equations [Ornata et al., 1987, Hirai et al., 1989 .

In the following sections we describe a match striking network and the qualitative math used. Then the plan­ ning algorithm is presented. Descriptions of the teler­ obot, workspace, and an execution example follow. Fi­ nally, this work is placed in context with the qualitative reasoning literature.

2 A Network for Match Striking

A qualitative reasoning network was proposed [Hirai et al., 1989] to represent a single match striking motion. The network represents the physical equations describing bending moment on the match stick and the total accu­ mulated heat at the contact point of the match head with the striking surface. The physical parameters considered were the force perpendicular to the striking surface, the velocity along the striking surface, and the angle from perpendicular that the match is inclined in the direction of motion (figure 1) . The possible outcomes were match breakage and match ignition, represented as the absolute value of bending moment on the match and the amount of accumulated heat respectively.

The proposed network has been extended here (fig­ ure 2) to include an additional preliminary motion to the starting position and force. Representations of the parameters actually used for controlling the ETA2 robot and the results of actual trial execution-match break­ age and match ignition-were also added. Note that the match can break as a result of either motion. Both ac­ tions are in the same network because they share control parameters related to angle and force.

In the figure, nodes with wide shaded arrows indicate the interface with the external system; other nodes are entirely internal to the qualitative reasoning network it­ self. The robot control system does not support servoing to force and velocity during the brief match striking ac­ tion so the corresponding monotonically increasing dig­ ging depth (distance of position control trajectory into the match box) and jumping gap (distance between servo samples) robot control parameters are used. Angle, dig­ ging depth, and jumping gap are all parameters con­ trolled by-and therefore known to-the robot system. Match ignition and breakage are results observed by the human operator or an appropriate sensing system.

3 Qualitative Math with "Likelihoods"

Eight network node types are defined: sum, product, 1\f +, negative, absolute-value, constant, control, and threshold. Each node logically consists of two parts: {1) a value for a parameter and {2) the relationship between the parameter itself and its cause nodes. This relation­ ship provides for reasoning in both directions through the network. Relationships with effect nodes are con­ tained in those effect nodes as relationships with causes. Ultimate cause nodes, control and constant, have a rela­ tionship part of nil.

Four qualitative values are defined: +, 0, -, and ? for unknown. All nodes in the network have qualit.a­ tive values, and the externally visible control and thresh­ old nodes have additional actual values. The qualitative value of each control node is the sign of the actual nu­ merical value. The qualitative value of each threshold node is + when its actual logical value is true, indicating that an unknown real number has exceeded an unknown positive threshold, and - when the actual value is false.

Relation-tables (figure 3) have been constructed to represent the qualitative function for each node type. Reasoning functions use these tables both to propagate current qualitative values through the network and for planning changes to control values for subsequent trials. Values in shaded triangles in the figure are qualitative values of the parameters; other values are qualitative val­ ues of numerical change consistent with the associated shaded values.

The heart of the qualitative math engine is the likely­ potentials function, described through an example be­ low. This function is used both for propagating quali­ tative values through the network and as an aid in se­ lecting among alternatives during the planning process. The analogous likely-change-potentials function is used for propagating and planning change.

Figure 4 illustrates the computation performed by the likely-potentials function for the example of the sum re­ lation, given inputs + and ? and a result of+. A triple of potentials is assigned to each entry in the tahle, repre­ senting the relative likelihoods that a result of+, 0, and - will occur when inputs match the table entry. These triples always add up to 3, embodying an assumption that each combination of inputs is equally likely. Triples defined for results +, 0, -, and ? all appear in step 3 of the example. Three possibility factors are assigned to each of the input and result arguments, with I represent­ ing the possibility of a match with the values+, 0, and-, and 0 representing a mismatch . For inputs, these factors are multiplied into all three triplet values of the table en­ tries of corresponding rows and columns; for the result, the factors are multiplied into the corresponding triplet values of each table entry. The resulting table is shown in step 4 of the example. The final likelihood potentials returned by the function are, for the inputs, the sums of all triplet values in the rows and columns and, for the result, the sums of corresponding triplet values over the entire table. In step 6, the original argument value + becomes (7 0 0), indicating that only + is possible, and the original argument? becomes (3 3 1), indicating that explicit values + and 0 are more likely than the also possible-.

Likelihood potentials do not represent probabilities that numerical values consistent with known constraints fall .within qualitative intervals, but represent the rela­ tive number of combinations of qualitative values which are consistent with known constraints. If the likelihood potentials for all three possible values of any argument are zero, a logical inconsistency is detected. If the like­ lihood potential of only one of the three possible values for an argument is non-zero, the qualitative value of the argument must be the corresponding value. If the like­ lihood potentials of more than one of the three possible values for an argument are non-zero, the corresponding qualitative values are all possible and the one with the highest likelihood is consistent with the greatest num­ ber of combinations of qualitative values for the other arguments of the relation.

4 The Planning Algorithm

4.1 Problem Definition

The planning problem can be viewed as a search in the multi-dimensional space of control parameters from an initial starting point for a region where the set of goals is satisfied (figure 5).

The planner performs this search one step at a time in a series of trials ; We define the problem of planning each step: given a most recent trial (with known control values and observed results), a history of previous trials (if any), and the results desired upon a next trial, deter­ mine the directions of numerical change to make to the controls.

4.2 Data Structures Supporting Planning

Each node haa three slots containing qualitative values: current, change, and next. They represent the current state and the actual plan.

It is easy to become confused about the meaning of "qualitative change" --especially for network parameters which are not externally visible and have no numeric value. current=next can be described as: "there is no qualitative change to the parameter." But this does not specify anything about the qualitative value of the nu­ merical change to the parameter. It is this qualita­ tive value of numerical change that is used for change. When current=next=+, change can be+, 0, or- because +sum+=+, +sumO=+, and +sum-=+ can all be true.

An additional slot in each node contains a planning­ status list. It is initialized to nil and can accumulate properties must-change, resist-change, cycle-back, at­ maximum, and at-minimum. These indicate topologi­ cal relationships of the node to the changes in behavior desired from one trial to the next.

The network itself contains a history of all trials made. Each entry in the history contains an indication of the goal space (the logical value desired for each of the threshold nodes), the numerical control values used for a most recent trial, the result of the trial (logical threshold values), and the qualitative plan derived from the trial (qualitative values of numerical change). There is also provision for a user-supplied comment. Each entry in the history can be thought of as a qualitative vector in the multi-dimensional numerical control space, labeled with the goal region to which it "points."

4.3 The Algorithm

Define the starting point and the goal region.

1. Pick up the set of numerical control values actually used for the last trial and the logical values of results actually observed.
2. Define the goal region in terms of a set of logical values desired for the results.
3. Search the history of trials to determine numerical limits within which the control values must fall to achieve the desired results (explained in more detail in the next section) . This is a contextual set of numerical ranges for controls which applies to this particular starting point.
4. Derive qualitative values for as much of the network as possible, propagating from the newly set actual values for the externally visible nodes. Tag the net­ work nodes with various properties:
5. Each node for which all paths to ultimate causes pass through its own effects is marked cycle-back. The planner uses this property to avoid looping in cyclic networks.
6. Nodes which lie on all paths from an ultimate effect which is not as desired to all of its ultimate causes ate marked must-change. All successful plans will change all of these nodes.
7. Ultimate effect nodes which are already as desired are marked resist-change. This property is prop­ agated toward causes but stops at nodes marked must-change. The planner uses this to avoid un­ wanted side-effects.

1. Control nodes (ultimate causes) which are at phys­ ical or contextual limits are marked with the at­ maximum and at-minimum properties as appropri­ ate. These properties are propagated toward effects and depend upon the actual relations in the net­ work.

Plan qualitative change, propagating through the net­ work from all must-change results toward ultimate cause nodes.

1. Planning for this trial is complete if all nodes marked must-change are changed and at least one change to an ultimate cause node has been made.
2. Propagation of this thread is complete if a change has already been planned for one of the causes of this node.
3. Select an immediate cause of this node to propagate change through according to the following selection preferences:
4. highest nodes marked must-change

intermediate nodes not marked

low nodes marked resist-change

• very low nodes for which a change of 0 has the highest likelihood potential
• lowest nodes for which no change is possible con­ sistent with the current known values, changes, and at-maximum and at-minimum limit con­ straints

lowest nodes marked cycle-back

1. For the selected cause, choose the change ( + or -) which has the higher likelihood potential.
2. Make the change to the selected node and propa­ gate.

Record, choose numerical value, and execute.

1. Put the last trial and this plan (goals, numerical control values, results, and qualitative plan) on the history.
2. Choose a numerical value to use in the next trial (within the contextual numerical range) for the con­ trol parameter selected for change.
3. Execute the newly planned trial.

5 Utilization of Numerical Experience

The most important feature of the planner is the mecha­ nism of coordination of qualitative and numerical infor­ mation for planning.

Qualitative information is embedded within the nu­ merical execution history in the form of a qualitative vector at a point in the numerical search space which in­ dicates the qualitative direction of the goal region from that point. Numerical information influences qualita­ tive search by asserting constraints on qualitative motion when numerical limits are exceeded.

The key is the use of limits. For the 2-dimensional example in figure 6, the limits visible from a most re­ cent trial are the physical limits above, below, and to the right, but to the left, an earlier trial asserts a tighter limit. Only the region in white is considered for the next trial. When limits overlap, the planner must consider an­ other direction. The qualitative reasoning engine easily handles limits by zeroing out the likelihood potentials for changes in nodes which would attempt to exceed limits.

6 The MEISTER Telerobot and Experiment Workspace

The qualitative reasoning planner and match-striking network described have been integrated into the MEIS­ TER (Model Enhanced Intelligent and Skillful TEle­ operational Robot) telerobot system [Hirai and Sa to, 1988, Hirai et al., 1990].

MEISTER hardware includes the 6-DOF ETA2 slave manipulator, a Lord gripper with force/torque sensors at the base of each finger, a 6-DOF master manipula­ tor, several cameras, some on pan-tilt heads, and sev­ eral monitors including a Sun workstation and a custom Multi-Media Display, which supports real-time stereo graphics overlay.

MEISTER high-level software is written in object­ oriented EusLisp [Matsui and Inaba, 1990]. The match­ striking network was added into the match-box object.

Among a variety of objects in the workspace for a flame-test chemical experiment is a match box in a clamp on a stand and several matches lined up for easy grasp- D . trlals2-4

ing by the manipulator. Figure 7 shows the robot just before executing a striking motion.

With EusLisp running on a Spare station equipped with 24Mb of memory and evaluating uncompiled qual­ itative planner lisp code, it took less than 3 seconds to plan each trial. The qualitative reasoning software consists of approximately 2000 lines of general-purpose qualitative reasoning code, 200 lines of match-striking network definition, and roughly 200 lines of MEISTER interface code.

7 A Match Striking Example

Figure 8 presents the data and the search performed dur­ ing actual execution of the qualitative reasoning planner while directing the robot for the match-striking task. The vertical dimension in each frame is the angle in de­ grees and the horizontal dimension is the digging depth in millimeters. All frames represent the plane where the jumping gap is at the maximum physical limit of 20mm.

The match neither ignited nor broke upon a first trial at a digging depth of 8mm and angle of 20deg. The qualitative reasoning planner determined that the dig­ ging depth should be increased. This trial is represented by a point and an arrow. The half-tone bar indicates a limit due to non-ignition/non-breakage visible along the angle=20deg line. The 2nd and 3rd trials were similar, successively increasing the digging depth. The match broke upon the striking action of the 4th trial. At this point, the planner decided to decrease the angle, assert­ ing a limit (striped bar) along the digging dept.h=12mm line. A new match, on the 5th trial , broke on the move to the starting force and position, at an angle of -lOdeg. Again the planner asserted a limit (cross-hatched bar) visible from the 12mm line, but in the opposite direction. The angle at this digging depth must now lie between 20deg and -lOdeg. Breakage on the striking action in the 6th and 7th trials further narrowed the angle range until on the 8th trial the angle was fixed at -lOdeg. Notice that there were two trials at this precise location in the control space with different results. Now the qualitative reasoner was constrained from changing the angle and decided to reduce the digging depth instead. The 9th and lOth trials both resulted in breakage on the striking action and an 11th trial was successful at an angle of -50deg and a digging depth of lOmm.

This example illustrates the narrowing of numerical search and the need for contextual limits to achieve suc­ cess. Overlapping of failure regions is also evident .

8 Relationship to Other Qualitative Reasoning Work

Sacks [1990] characterized qualitative simulation as a trajectory through phase space. Here, we view plan­ ning similarly as a search for a path through the space of control parameters.

De Kleer and Brown [1984] mentioned the use of addi­ tional network nodes to represent landmarks. The con­ stant node (figure 2) is just such a landmark correspond­ ing to the angle where, during the striking motion , the force is directed along the match stick and the bending moment is zero.

Forbus [1984] uses the term "quantity space" to rep­ resent a relative ordering of comparable values. A sin­ gle representation is used to express qualitative values of multiple physical parameters. In the present work, the state of the entire system is represented in terms of ranges of control parameters, ranges whose values vary with position in the control space.

Kuipers [1984, 1986] uses a network to describe the physical equations governing the system, and defines a set of network node types. We do the same here, adding, in the same spirit, absolute-value and threshold node types. Our approach is similar to Kuipers', with differ­ ences deriving from the use for planning rather than sim­ ulation. We use only the values+, 0, and - instead of a system of general intervals, and so do not generate land­ marks during simulation. Indeed, we are concerned only with where the goal region is relative to any "current" region, and are not interested in the topologies of paths through the various regions as embodied in the series of intervals of Kuipers' simulation . Also, the development of qualitative math functions which return "likelihood potentials" in place of simple Boolean values is a direct consequence of their application to planning.

Kuipers and Berleant [1988] propagate constraints on the numerical value each node in the network can take. We do not attempt to imbue network nodes whose nu­ merical values are not externally visible with numeri­ cal information beyond the constraints of the qualitative representation.

9 Conclusions

A simple planner utilizing qualitative reasoning and nu­ ml.'rical experience has been developed and integrated into the MEISTER telerobot system and demonstrated for a match striking task. The primary contribution of this work is the identification of a mechanism uti­ lizing limits for coordinating numerical and qualitative information to direct search. Qualitative math functions which return " likelihood possihilities" facilitate the use of qualitative constraints in the planning process.

Directions for the future include work on more robust search algorithms, exploring expanded use of likelihoods for planning, and more extensive testing of applications to a variety of tasks.

Acknowledgements

The authors would like to thank T. Yuba, Director of the Information Systems Division, and T. Matsui and all the other members of the robotics group at the Elec­ trot.echnical Laboratory for their comments and support. They would also like to thank W. Schober, Manager of Rohot.ics and A ut.omat.ion Advanced Development, and S. Grenander and the many other members of the Jet Propulsion Laboratory Automation and Robotics Pro­ gram and the Sequence Automation Research Group who have given support, and especially R. Doyle for tech­ nical guidance.