NASA's Jet Propulsion Laboratory. Pasadena, California
A qualitative-reasoning planning algorithm helps to determine the quantitative parameters that control the motion of a robot. The algorithm can be regarded as performing a search in the multidimensional space of control parameters from a starting point to a goal region in which a desired result of the robotic manipula tion is achieved. It makes use of a directed graph representing the qualitative physic al equations describing the task, and interacts, at each sampling period, with the history of quantitative control parameters and sensory data, to narrow the search for reliable values of the quantitative control parameters. The algorithm is applied to the specific robotic task of striking a match on a matchbox. The physical parameters to be controlled are the force perpendicular to the striking surface, the velocity along the striking surface, and the angle o f inclination of the match with respect to the striking surface (see Figure 1). In practice, the matchstriking action is so brief (with respect to the sampling peri od) that the control subsystem cannot exert servocontrol over the perpendicular force and velocity. Therefore, the corresponding control parameters that are used instead are the digging depth (the depth of penetration of the nominal trajectory of the matchhead into the matchbox) and the jumping gap (the distance between sample positions), respectively. The desired result of the robotic manipulation is ignition of the match; the undesired results include failure to ignite and breakage of the match. For the purpose of mathematical modeling, ignition is represented by the accumulation of sufficient frictionally generated heat in the matchhead, and breakage is deemed to occur when the absolute value of the bending moment in the matchstick exceeds an unknown and uncertain maximum value. The qualitative values represented in the algorithm are +, 0, Q, and ?. For example, with respect to a given quantitative parameter, these values could mean that the actual value of the parameter minus the desired or control value is positive, zero, negative, or unknown, respectively. The heart of the qualitative mathematics is the concept of the likelihood potential, which is a measure of the number of different combinations of qualitative inputs, to each node of the network, that satisfy the known constraints, including a given qualitative output . The likelihood potentials are used to propagate qualitative values through the nodes of the network and as aids in selecting altematives during the planning process. The most important feature of the algorithm is the way it coordinates qualitative and quantitative information in planning. Qualitative information is embedded within the numerical history in the form of a qualitative vector at a point in the numerical search space that indicates the qualitative direction of t he goal region from that point. Numerical information influences the qualitative search via the assertion of constraints on qualitative motions when numerical limits are exceeded. The key is the use of limits In the two-dimensional example of Figure 2, the limits visible from a most recent trial are the physical limits above, below, and to the right. To the left. however, an earlier trial has given rise to a tighter limit. Only the region in white is considered for the next trial. When limits overlap, another direction must be considered. The qualitative-reasoning part of the algorithm easily handles limits by zeroing out the likelihood potentials for changes in nodes that would attempt to exceed limits.
More details can be found in:
S. F. Peters, et. al, RPlanning Robot Control Parameter Values with Qualitative Reasoning,S Proceedings of the 12th International Joint Conference on Artificial Intelligence, Sydney, Australia, August 1991, pp. 1234-1240.
Point of Contact:
Stephen F. Peters,
Mail Stop 301-250D
4800 Oak Grove Drive
Pasadena, CA 91109
818-354-0157
stevep@parsec.jpl.nasa.gov
Telerobotics Program
page
Please email the site webmaster
with any comments, criticisms or corrections
for this page.
Maintained by: Dave Lavery
Last updated: May 10, 1996