Neil C. Rowe
Code CS/Rp, Naval Postgraduate School, Monterey, CA 93943 USA
(This paper appeared in the AAAI 1990 Spring Symposium on Planning in Uncertain, Unpredictable, or Changing Environments, Stanford, CA, March.)
Planning can be considered a many-to-one mapping from the space of possible problems to the space of possible plans. For most interesting problems, the mapping is too complicated to formulate other than procedurally. But we can do it for means-ends analysis, where the notion of the difference between the current state and a goal state determines the next planning action. Focusing on differences makes means-ends analysis a step-at-a-time planner, so even when results unexpected by the planner arise from actions, a solution can still usually be found from the new unexpected states.
Our recent research on robot navigation has tried to find analogous ideas for planning with real-valued quantities like position and orientation of a robot. Our approach has been to define "path fields" over the configuration space for the robot, "fields" in the physics sense of electrical or gravitational ones but now extended to plans as well as vectors for every point in the space. For example, for high-level robot path planning to a particular goal point in some terrain, we can define a "path field" at every point in the terrain which indicates the best path or best direction to head from there to reach the goal point. Then if we accidently wander from the path planned when trying to follow it in the real world, or unexpected accident forces us from it, we can just reassess where we are and look up the best way to go from this new location, analogously to means-ends analysis.
Figure 1 (from (Alexander 1989) which in turn uses the path-planning program of (Rowe 1990)), shows an example path-direction field for two-dimensional terrain with an obstacle (the checkered triangle) and a crossable but costly "river" (the bumpy vertical line in the lower left), where all non-obstacle and non-river areas are considered equal-cost-per-distance to traverse, and where the goal is the small circle on the right just below the middle. The small lines indicate the direction of the optimal path to the goal point from evenly-spaced start points. The smooth thin longer lines indicate boundaries between abrupt changes in optimal-path behavior, determined by methods that will be explained later; for instance, the gently curved line in the lower left distinguishes optimal-path behavior that crosses the river from optimal-path behavior that avoids the river by going around its endpoint.
Construction of plan fields that would tell you what to do next from any state would seem to be a difficult or impossible issue for many problems, because nontrivial search spaces are either enormous or infinite. For instance, robot navigation involves real numbers, so there are an infinity of states. One approach is to impose a regular tessellation on the space of possible states (for a robot, the terrain) and then associate every point within a particular cell with the same field direction (next behavior) as that of the center of the cell. This heuristic approach will not always work, as when an impassable obstacle crosses a terrain cell. Another approach is to define irregular cells of intuitive meaning like the terrain bounded by a ridge and two roads, but this requires expert judgment, and cannot be relied on to give regions of similar path behavior.
Fortunately, a rigorous alternative exists based on terrain-partition algorithms for path planning such as (Rowe and Lewis 1989), (Rowe and Richbourg 1990), and (Rowe and Ross 1990). These algorithms find an optimal path from a start point to a goal point by partitioning polygonally-modeled terrain (or polyhedrally-modeled airspace, for the three-dimensional program of (Rowe and Lewis 1989)) into equivalence classes of points whose path behavior to the goal is fundamentally similar. We can extend these algorithms to find paths from everywhere in the terrain to that same goal point, since they recursively decompose paths to the goal point into "wedges" or "corridors" of similarly-behaving paths, eventually decomposing terrain into a set of "well-behaved path subspaces" whose behavior can be summarized by the sequence of terrain features it encounters. Each wedge is composed of irregular subregions between features, which can be considered "behavioral regions", equivalence classes of points that cross exactly the same terrain features in the same order on their way to the goal. A path field is the mapping from points to their associated behavioral regions and hence to a sequence of terrain-feature crossings. Note that finding the exact optimal paths is then straightforward with homogeneous-cost-per-unit-distance regions, because the paths can only turn on the boundary of cost regions, and those turns must obey Snell's Law.
Thus the seemingly infinitely variable plan fields for a real-valued multi-dimensional space can be reduced to a finite number of "behavior classes" narrow enough in definition so that once a situation's class is known, computing the optimal plan for the situation is straightforward. Thus behavior classes are a kind of problem abstraction. However, the whole trick is determining the class of a situation, because such spaces need not have "nice" shapes. Thus much of our recent work, exemplified by (Alexander 1989) and (Rowe and Ross 1990), has tried to develop mathematical methods for finding behavioral boundaries, since once these are found, the region shapes follow. The methods of the last paragraph are not sufficient, because generally the wedges found will overlap, so new theorems must be developed. For instance, for Figure 1 we can prove that the boundaries not emanating from obstacle or river endpoints are hyperbolas; for "weighted regions", regions with homogeneous cost-per-unit distance, boundaries also include parabolas and a variety of curves describable only by parametric functions.
Path fields and plan fields can also address a more fundamental uncertainty, state and world-feature uncertainty, that means-ends analysis and kindred planning techniques cannot directly address. If we can create separate plan fields for possible world situations, we could combine them into a consensus plan field. In other words, we could draw an analogy to the methods of superposition of electrical fields of multiple charged objects by calculating the fields separately for each object and adding the field vectors at every point. For instance in the robot path-planning problem, suppose we are not sure where or whether a bridge crosses the river in the vicinity. We could create a separate path field for each reasonably possible siting of the bridge, then take the weighted average of the initial vector directions at every point in the terrain, based on our degree of belief in the likelihood of each possibility. This would be best when we are not close to the river, but otherwise we would probably be able to see any bridges and then create a new plan field. Such an approach is appealing, but it is easy to forget that it is heuristic and has no formal mathematical basis; for one thing, path fields are not even continuous. However, this idea does have appealing analogies to recent ideas for robot subsumption architectures like those of Rosenblatt and Payton at Hughes, for which similar "higher-level" plan ideas can be weighted against lower-level concerns like avoidance of immediate obstacles.
Reaching a consensus between the recommendations of competing plan fields is actually a problem of multiple inheritance at each point in the plan space, and many standard approaches are applicable. If one plan inherited subsumes all the others, then there is no conflict and that more general plan can be used. We could set priorities among fields that depend on location in the field, giving a consensus field consisting of pieces of the component fields stitched together. That would be appropriate if plans cannot be "diluted" without damage; for instance, if you're not sure whether an obstacle is blocking the road at a point P, you should still slow down when you approach P. If the plans differ only quantitatively, then some sort of weighted averaging can be used, where the weighting is their probabilities, as in (Rowe 1982). We may be able to guarantee even a result that does not subsume the others. If a vector field is truly an "optimal-path field", besides having the field direction represent the best path direction, we can let its vector magnitude represent the difference between the cost of going in this direction versus the cost of going in the second-best locally-optimal direction at that point. Then the vector magnitude is the relative goodness of the recommended direction at that point. If the total weight in some direction is more than the sum of weights in all other directions, it is guaranteed that that is the best direction because the other effects could never cancel it out.
A multiple-inheritance consensus between possible world situations requires that we compute complete path fields in advance. But frequently the terrain itself restricts possibilities to a finite set, like places for a bridge or ways to cross a mountain ridge. We can also exploit experiments. For instance, if we are not sure how far a forest extends to the right of us, we can pick evenly-scaled extents for the forest and derive path fields for each. If in two path fields the direction is the same, at corresponding points, it must be the same (with a few known exceptions) for any "intermediate" field in which the extent of the features is intermediate between the extents in the two original fields. So when we find two path fields whose vector directions are point-for-point nearly identical, we do not need to store any intermediate fields between them. Furthermore, even when two sample fields have significant differences, we need only study the areas in which those differences occur to obtain intermediate fields between them, which saves much time.
This work was supported in part by the U.S. Army Combat Developments Experimentation Center under MIPR ATEC 88-86. Also in part this work was prepared in conjunction with research conducted for the Naval Air Systems Command and funded by the Naval Postgraduate School.
R. Alexander, "Construction of optimal-path maps for homogeneous-cost-region path-planning problems", Ph.D. thesis, Dept. of Computer Science, U.S. Naval Postgraduate School, September 1989.
N. C. Rowe, "Inheritance of statistical properties", Proceedings of the National Conference, AAAI, Pittsburgh, PA, August 1982, 221-224.
N. C. Rowe, Roads, rivers, and rocks: optimal two-dimensional route planning around linear features for a mobile agent. To appear in International Journal of Robotics Research, 1990.
N. C. Rowe and D. H. Lewis, Vehicle path-planning using optics analogs for optimizing visibility and energy cost. NASA Conference on Space Telerobotics, Pasadena CA, January 1989.
N. C. Rowe and R. F. Richbourg, An efficient Snell's-law method for optimal-path planning across multiple two-dimensional irregular homogeneous-cost regions. To appear in International Journal of Robotics Research, 1990.
N. C. Rowe and R. S. Ross, Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects. Accepted to IEEE Transactions on Robotics and Automation, January 1990.
Go up to paper index