Scaling the Dynamic Approach to Autonomous Path Planning: Planning Horizon Dynamics

1 Introduction

Many approaches to path planning assume e;lobal knowledge of the environment (e.g. lLatombe, 1991; Khatib, 1986; Connolly and Grupen, 1993]). Global algorithms can guar­ antee solutions to path planning problems, i.e. they can guarantee that the agent will find a path to the target if one exists. They can also find paths that meet optimality conditions such as shortest path length, minimum energy consumption, and so forth . In many interest­ ing situations, however, environment knowledge may be unavailable or incomplete [Lumelsky and Stepanov, 1987; Rimon and Koditschek, 1993]. For example, knowledge of the environment may need to be updated by the agent as task execu­ tion proceeds. Dynamic environments also vi­ olate the assumptions of global path planning. ,When targets and obstacles move freely about the world, global representations can quickly be­ come obsolete.

·This work was in part supported by: NSF Grants IRI93-07126 and SBR89-20230, as well as ARMY Grant DAAH04-96-1-0007 and ARPA Grant N00014-92-J-1647. It was carried out during a 6 month visit to the GRASP Laboratory by the sec­ ond author.

In contrast to global approaches , behavior­ based systems react to sensory input with min­ imal internal representation of the environment (e.g. [Brooks, 1989]). S:ystems are designed in terms of elementary actions, or behaviors, and sensory information feeds into movement control at a low level of processing in a way that is spe­ cific to each behavior . Purely reactive systems are not, however, able to guarantee the existence of path planning solutions. Thus, for navigation in cluttered environments, there remains a need for representation, where actions are determined not only based on immediate sensor readings , but also based on an internal model of the envi­ ronment.

The dynamical systems approach strikes an in­ teresting balance between the extremes of global path planning and purely reactive systems. The dynamic approach shares with behavior-based approaches the abi lity to control actions based upon sensory input. In addition, this formaliza­ tion includes the ability to build internal rep­ resentations of the environment [Engels and Schaner, 1995]. A memory representation makes information available so that the system can act on knowledge about the environment that is not currently registered by the system's sensors. Behavioral information, as derived from both sensed and remembered information, shapes a vector field that controls the behavior of an au­ tonomous agent. As a result , such systems per­ form well without prior global knowledge of the environment and in dynamic environments.

It is important to point out, however, that dynamic planning represents a local approach. Although the existence of a partial environment map will allow such a system to outperform a purely reactive system, in complex environments the dynamic approach will fail to find existing solutions to path planning problems. It is these situations that we investigate in this paper. In many of these situations the system can fail be­ cause it does not make use of its environment model in an appropriate way. We propose a method for improving the system's ability to uti­ lize its environment model, thus solving a larger range of problems without resorting to global path. planning.

2 The Dynamical Systems Approach to Path Planning

In the dynamic approach behavior is described in terms of a set of variables that define behav­ ioral dimensions. For the task of autonomous robot navigation one may represent the behav­ ior of the agent using heading direction, ¢ ( -1r < ¢::; 1r), and velocity, v [Schaner and Dose, 1992T Task constraints are expressed as points or pa­ rameterized sets of points in the space spanned by the behavioral variables. For example, in the navigation task, the he.ading direction 1/Jtar rep­ resents the direction to the target location, while the direction 1/Job· represents the direction to an obstacle, as illustrated in Figure 1.

The behavior of the agent is modeled as a time course of the behavioral variables generated by a behavioral dynamics that incorporates both planning and control knowledge. In this paper, we focus on a single behavioral dimension, head­ ing direction. We assume that velocity is con­ trolled by a dynamics similar to that described by [N even and Schaner, in press]. For our one­ dimensional system, the dynamics take the fol­ lowing form.

Task constraints define contributions to the vec­ tor field, J( ¢), by modeling desired behaviors as attractors and to-be-avoided behaviors as repel­ lors of the behavioral dynamics. The contribu­ tions of individual task constraints are combined additively into a single vector field, specifying the planning dynamics as shown in Figure 1.

Because certain constraints are modeled as re­ pellors, the planning dynamics is augmented by a stochastic term that guarantees escape from unstable fixed points ( repellors). For the spe­ cific functional forms corresponding to task con­ straint contributions, see [Schaner and Dose, 1992] .

To deal with spurious attractors as well as to incorporate additional task constraints, [Large et a/. , 1997] further modified the strength of each contribution with a specific weight , w; as­ signed to each type of task constraint. Weights are assigned through a competitive dynamics that determines the strength of each contribu­ tion depending upon the current situation.

The state space of this dynamical system corre­ sponds to the set of task constraints. The pa­ rameters, a; and /j ,i, are referred to as com­ petitive advantage and competitive interaction, respectively. The task dynamics operates at a faster time scale than the planning dynamics. It models decision-making regarding which task constraints are applicable at a given time, and allows the system to generate sequences of be­ haviors .

2.1 Multiple Obstacles

According to this approach, avoidance of a single obstacle is modeled by adding a range-limited repellor to the vector field (see Figure 1) , while avoidance of multiple obstacles is modeled by summing multiple range-limited repellor contri­ butions.

Here, Rob·; is a function that sets up a range limited repellor in the direction of obstacle i, and the exponential term scales the strength of the obstacle's contribution to the vector field. The parameters of the scaling term are the dis­ tance from the agent to the obstacle, r; (center to center), the radius of the obstacle, R;, and the radius of the agent Ragent. The parameter d determines the distance at which the agent begins to take an obstacle into account, and is set to a constant value, d = do. Obstacles that are very far from the agent do not affect the behavioral dynamics, whereas nearby obstacles affect the planning dynamics strongly. Thus, d determines the spatial resolution of the planning dynamics.

This strategy works because linearly depen­ dent contributions lead, through superposition, to averaging among corresponding constraints, while linearly independent contributions allow for the expression of constraints that are incom­ patible, contradictory, or independently valid. Consider the two situations depicted in Figure 2. In the left panel, the agent faces a pair of ob­ stacles that are positioned too closely together for the agent to pass between them. The con­ straints represented by the two obstacles lead to a single repellor in the vector field at their aver­ age location: behaviorally a single obstacle. In the right panel, the agent again faces two obsta­ cles, but this time they are positioned far enough apart for the agent to pass between. These two constraints are independently valid, and an at­ tractor is formed in the vector field, correspond­ ing to the behavior of steering between the two obstacles.

2.2 Environment Maps

Memory can be implemented using an Amari­ type neural field architecture [Amari , 1977], with the general purpose of cleaning up noisy perceptual information so that separate contri­ butions to the behavioral dynamics are guar­ anteed to have desired properties [Engels and Schi:iner , 1995; Schi:iner et a/., 1996]. A second function of the neural field is that it enables the system to store information about its environ­ ment in the form of a "cognitive map". As the system explores its environment, it is able to add to its knowledge. Sensed and remembered information are integrated into the vector field so that the system can make use of environmen­ tal information even when it is not being directly sensed. For the purposes of this study, it is not necessary to consider the dynamics of the the Amari field, but simply to assume that informa­ tion about the environment is represented as a non-overlapping grid of spatial locations.

3 When Local Planning Fails: Problem and Approach

Many path planning situations are well handled by the dynamic approach as described above. Consider the case depicted in Figure 3 (top), for example. The agent begins to move toward the target, but encounters a wall. It veers to the left, turns around, finds a doorway, and contin­ ues toward the target . A more difficult situation arises, however, when the doorway is removed , as shown in Figure 3 (middle). In this case the agent veers to the left, encounters the left wall and turns around. If the doorway were there, the agent would find it and successfully make its way toward the target location. In this case, however, the simple local strategy embodied in the planning dynamics fails, and the agent loops indefinitely. The reason is that do, the parame­ ter that specifies the spatial scale at which plan­ ning occurs, is a small constant. 1 Thus the agent only takes into account a few obstacles at any given time. By the time it encounters the wall to the right, the agent has forgotten the wall to the left, causing the cycling behavior.

One possible approach to this problem is to allow the planner to take all three walls into ac­ count simultaneously by increasing the spatial scale, d. Figure 3 (bottom) shows the behavior in this situation. As expected, the agent avoids the configuration and successfully reaches the target. This example also shows the difficulty with this approach. The agent was unable to find the more efficient path through the door. This is because increasing the spatial scale de­ creases spatial resolution.

Our approach will be to dynamically adapt spatial resolution in a way that is appropri­ ate to the agent's current environment. To do this, we must solve two problems. The first in­ volves detecting when the agent should plan at a larger spatial scale. The second involves chang­ ing scales in a stable fashion, so that efficient planning is achieved . The following sections ad­ dress these issues.

3.1 The Homeward Component

We detect cycling behavior by computing an in­ stantaneous estimate of homing behavior,

1 In these examples the spatial scale, do, was set to two meters, roughly corresponding to the visual capabilities of the actual robots in our laboratory. For comparison, the radius of individual obstacles in Figure 3 is one meter.

where v in the current velocity of the agent, Vmax represents the agent's maximum velocity, ¢ is the agent's current heading, and 'lj;tar is the heading direction of the current target. When the agent is heading toward the target at max­ imum velocity, h = 1, when the agent is head­ ing away from the target at maximum veloc­ ity, h = -1, When the agent has zero veloc­ ity, h = 0, and so forth. We call this measure the homeward component, because of its close relationship with a circular statistic of the same name [Batschelet, 1981) .

Next we smooth h using a simple linear dy­ namics to obtain a time-averaged estimate of homing behavior.

Here the x; represent estimates of homing be­ havior at several different time scales. The 17; de­ termine the time scales over which the point es­ timates are smoothed. When the agent enters a looping behavior the smoothed homeward com­ ponents, x;, will approach values of zero with time constants determined by the 1);. Figures 4 (top) and (bottom) show instantaneous and smoothed homeward components for the situa­ tions of Figures 3 (top) and (middle), respec­ tively. In each figure , we show smoothing at three different time scales , x1 , x2 , and x3 . Note that in the top panel the smoothed homeward components retain relatively large values, indi­ cating good homing behavior, while in the bot­ tom panel each approaches zero, indicating that the agent is not making good progress toward the target .

3.2 Planning on Multiple Spatial Scales

Next, we address the question of how to adap­ tively change spatial resolution so that the plan­ ning dynamics will take into account informa­ tion that is appropriate to its current environ­ ment. For reasons discussed below, we assume that several discrete levels of spatial resolution are required, and that at any given time the agent is to plan at a single level.

We achieve this end by utilizing the compet­ itive dynamics introduced above in conjunction with constraint competition. In this case how­ ever, we reinterpret the meaning of the variables,

where r; indicates activation of planning level i. For a local stability analysis of the competitive dynamics, see [Large et a/., 1997). In order in­ stantiate the proper switching behavior, we de­ fine the competitive advantage, a;, and compet­ itive interaction, /j,i, parameters in such a way I ::1--------J.L.\--f------Jf----:--r-'~------'l;-----;r""--j

:::A

)-·:

-o.· ·L.:;J

-·.

Thne

Figure 4 Top: The homeward component, h, and smoothed homeward components, x;, for the situation shown in Figure 3 (top). Bot­ tom: The homeward components for the situa­ tion shown in Figure 3 (middle). The smoothed values approach zero, reflecting the agent's cy­ cling behavior.

that either exactly one planning level is active, or no planning levels are active (i.e., planning is at the base level). We do this by defining the parameters as follows.

Here, IXthresh is a threshold level for the ac­ tivation of a planning level. With these pa­ rameter definitions, the spatial scale dynamics has exactly n + 1 fixed points, where n in the number of planning levels. This system is sta­ ble when exactly one planning· level is active (ri = 1; ri = 0, Vj # i) or when no planning levels are active ( r; = 0, Vi). Intuitively, the competition between planning levels works as follows. When Xi < IXthresh, planning level i attempts to activate itself. The /j,i enforce. com­ petition among planning levels such that If ~wo levels request activation, the level representmg the larger spatial resolution will win.

We can then define spatial scale, used in Equation 4, as:

Configuration

4 Examples

Next we show two examples of a simulated agent ~sing multiple lev"els of spatial resolution to escape from behavioral cycles. We used three planning levels, with parameter values do = 2, d1 = 2, d2 = 4, d3 = 6, IXthresh = 0.4, 'f/1 = .1, T}1 = .05, and 'f/1 = .025.

First we examine the example of Figure 3, in whicb the agent is enclosed by walls on three sides (Figure 5). Initially the spatial resolution of the planning dynamics is set to the base level, d = d0 . Upon encountering the long wall, the agent turns left. At the left wall the planning dynamics causes the agent to turn around. At about this point, x 1 falls below threshold , and planning level one is activated (marked ih the figure), so d = do + d1. Abou~ half .way to t?e right wall, planning level two IS activated, dis­ abling planning level 1. Once this occurs, the entire enclosure is represented in the planning dynamics simultaneously, and the agent escapes from the enclosure. As the smoothed homeward components increase above threshold, planning returns to the base level.

The second example shows a more difficult sit­ uation a circular room with the only exit oppo­ site th~ target. At first the agent moves toward the the target, and as it explores the space, plan­ ning levels one, and two are activated (Figure 6) . Once level two is activated a single attractor IS formed in the planning dynamics, corresponding to the exit. The agent makes its way through the door, and eventually to the target .

5 Discussion

We have described how to incorporate the no­ tion of planning at multiple spatial scales into a system that plans paths through a two dimen- Configuration sional workspace using nonlinear dynamics. For our simulations, we assumed that the agent pos­ sessed a partial representation of the environ­ ment , and we addressed the issue of how best to use the information represented in its internal map.

This basic strategy is applicable in a variety of different settings. First of all, it seems natu­ ral to employ the planning horizon as a mecha­ nism for selection of sensors . Many robots are equipped with a range of different sensors such as sonar, vision, laser, tactile, and so forth. Each of these sensors has a different range and reso­ lution. Thus, dynamic selection of a discrete planning level may be used for selection of sen­ sors in response to the need for spatial detail and/or range. For close range navigation either infrared sensors or vision modules such as the in­ verse perceptive mapping may be used. On our particular platform we employ ultra-sonic sonars and inverse-perspective mapping. Thus, inverse­ perspective mapping may be used for close range navigation, while sonar may be used for longer range sensing.

There are several possible applications of the planning horizon dynamics beyond those pre­ sented in the paper. Map building presents one interesting possibility. Another possibility that we have not yet explored is planning at multiple levels simultaneously. This may be useful in sit­ uations where it is necessary to take both global and local constraints into account. We are cur­ rently experimenting with several applications of this approach using the mobile platforms in our laboratory.