Anytime Sensing Planning and Action: A Practical Model for Robot Control

1 Introduction

There is a wide gap between theory and practice in planning and control of robotic systems. Early theoretical work has concentrated on the analysis of systems with perfect sensors and effectors and with unlimited computational power. This paper outlines the implementation of a model of anytime com­ putation that provides a more realistic theoretical foundation for robot planning and control. The model is based on any­ time algorithms [Dean and Boddy, 1988; Horvitz, 1987] that introduce a new tradeoff in programming - between compu­ tation time and quality of results. This degree of freedom is especially useful when developing the performance elements and the control mechanism of a robotic system. The flexi­ bility offered by anytime algorithms allows accurate sensing and extended planning when time is available, and coarse, fast sensing and planning under time pressure. It is based on the observation that in order to cope with complex environments in real-time, there is no need to sacrifice the ability to do pre­ cise sensing and planning. But, as time allocation becomes a degree of freedom, incremental scheduling and constant mon­ itoring are necessary in order to guarantee the optimal opera­ tion of the robot In [Russell and Zilberstein, 1991] we intro­ duced a compilation scheme for optimal composition of any­ time algorithms. It offered a new approach to the construction of complex real-time systems that separated the arrangement of the performance components from the optimization of their scheduling, and automated the latter task.

In this paper we use the compilation of anytime algorithms as part of a model for robot control. We have implemented a navigation system in which the scheduling of anytime aJ. gorithms is performed by a run-time monitoring component that uses performance information produced by the off-line compilation process. In order to reason efficiently at run-time about time allocation, we use conditional performance pro· files that give a probabilistic description of the quality of the results of an algorithm as a function of run-time and input quality (or any set of input properties). This is an extension of an earlier notion of performance profile that depends de­ terministically on run-time only [Dean and Boddy, 1988].

Figure 1 shows the data flow between the main components of the system. Sensory input is used to update the description of the environment This description is used both as input to the anytime planner and as one of the factors that detennine the allocation of time by the monitor. The other factors are: the compiled performance profile of sensing and planning, the model of the environment, and the quality of the current best plan.

To demonstrate this model we have selected one of the fun. damental problems facing any autonomous mobile robot: the capability to plan its own motion with noisy sensors. Sec· tion 2 describes the anytime sensing module. In Section 3, we describe the simulated environment in which the robot is situated and how the path planning problem is solved by an anytime abstract planner. In Section 4, we explain the com· pilation scheme that optimally integrates the anytime compo­ nents of the system. Section 5 presents the run-time system. We conclude with a summary of the benefits of our approach.

2 Anytime sensing

A primary goal of this work has been to extend the notion of gradual improvement of quality to sensing. The supposition that sensors produce a perfect domain description, as much as the assumption of perfect planning and plan execution, con­ stitutes a major disadvantage in any model for robot control. In our model, the presence of sensory errors is not an excep­ tion but rather the normal situation. Moreover, in order to optimally control the quality of sensing, the model includes a quantitative evaluation of its effect on the other components of the system.

This section describes the model of anytime sensing that we implemented. It produces a domain description whose quality measures the probability that an elementary (base level) po­ sition would be wrongly identified, that is, identified as free space while actually blocked by an obstacle or vice versa. We assume that within the area in which the sensors are effective, the quality of sensing is not affected by the robot's position. Our general model, however, does not require this assump­ tion.

Figure 2 shows the pedormance profile of the vision mod­ ule. It is characterized by several parameters: Ta , n, Q a, Q b. Ta is the minimal amount of time needed for the sensor to pro­ duce an initial domain description with quality Q a· Given a shorter run-time, the sensor does not produce any description of the domain. For a run-timet, Ta ~ t ~ n. the quality of vision improves from Q a to the maximal quality Q b, which is 1.00 in this example. Detailed analysis of anytime sens­ ing shows that in our domain sensing can be treated just as an anytime computational module for the purpose of compi­ lation and monitoring. However, this proprty does not hold in general [Zilberstein, 1993].

3 Anytime abstract planning

Our robot is situated in a simulated, two dimensional envi­ ronment with random obstacles. The robot does not have an exact map of the environment but it has a vision capability that allows it to create an approximate map. The accuracy of the domain description depends on the time allocated to the vision module. The environment is represented by a matrix of Tb elementary positions. The robot can move between adjacent cells of the matrix at a varying speed which affects the execu­ tion time of the plan as well as the energy consumption. When the simulation starts, the robot is presented with a certain task that requires it to move to a particular position and perform a certain job. Associated with each task is a reward function that determines the value of the task as a function of comple­ tion time. The system is designed to control the movement of the robot, that is, determine its direction and speed at each point of time, while maximizing the overall utility. The over­ all utility depends on the value of the task (a time dependent function), and on the amount of energy consumed in order to complete it.

The run-time monitor has to determine at each point how much time to allocate to vision and path-planning based on factors such as the current location r . the robot, the estimated distance to the goal position, the urgency of the task, and the quality of the plan produced so far.

Path planning is performed using an algorithm which is a variant of the coarse-to-fine search algorithm [Lozano-Ftrez and Brooks, 1984 J that allows for unresolved path segments. In order to make it an anytime algorithm, we vary the ab­ straction level of the domain description. This allows the al­ gorithm to find quickly a low quality plan and then repeatedly refine it by replanning a segment of the plan in more detail. The rest of this section describes the algorithm and its perfor­ mance profile.

3.1 Abstract description of the domain

In our hierarchical (quad trees) representation, the nth level of abstraction corresponds to a certain coarse grid in which every position, ( i, j), is an abstraction of a 2" x 2" matrix of base-level positions. Each high level position has a certain degree of "obstacleness" associated with it which is simply the proportion of the matrix that is covered by obstacles.

3.2 The anytime planning algorithm

The interruptible anytime planner (ATP), shown in Figure 3, constructs a series of plans from start to goal, whose quality improves over time. It starts with a plan generated by per­ forming best-first search at the highest level of abstraction (Lma:c ). Then, it repeatedly refines the plan created so far by selecting the worst segment of the plan, dividing it into two segments (of identical length), and replacing each one of those segments by more detailed plans at a lower abstraction level. The worst segment of the plan is selected according to the degree to which the segment is blocked by obstacles and according to its abstraction level. A special data struc­ ture, called a multi-path, is used in order to keep intermediate results. It is a list of successive path segments of arbitrary abstraction level. Note that the length of each segment of an intermediate plan is invariant. As a result, the run-time of the refinement step is approximately the same for any segment of the plan regardless of its level of abstraction.

The PATH-FINDER is a search procedure that returns the best path between any two positions in the same abstraction level. The path is represented as a list of positions at the same abstraction level. A base-level path must be obstacle-free and hence is a route that the robot can follow. A path at a higher level of abstraction, on the other hand, is the result of an A* search that minimizes the length as well as the obstacleness of the result It does not correspond to a particular list of base­ level positions.

3.3 Plan execution

In order to follow an abstract path, the robot must use an ob­ stacle avoidance procedure that may lengthen the route. As long as there exists a path that connects the start and goal po­ sitions, the obstacle avoidance procedure can bring the robot to its destination. Therefore, any abstract plan is completable and executable - even when blocked by obstacles. Obstacle avoidance is not a smart navigation method, but it can always substitute for missing details in an abstract plan. The quality of a plan P is defined as follows:

where length(P) is the length of the plan and P opt is the optimal plan. Note that the higher the level of abstraction the lower the quality of the plan. At the same time, high-level ab­ stract planning reduces (exponentially) the search space and hence it is performed much faster.

The notion of executable abstract plans -regardless of their arbitrary level of detail - is made possible by using plans as advice that direct the base level execution mechanism but does not impel a particular behavior. This idea was promoted by [Agre and Chapman, 1990] and was experimentally sup­ ported by [Gat, 1992]. In practice, uncertainty makes it im· possible to use plans except as a guidance mechanism.

3.4 Performance with perfect vision

We now examine the performance of the abstract planner un· der the assumption of perfect domain description. Figure 4 shows the paths generated by the path finder when activated with the start and goal positions being the lower left and up­ per right comers respectively. The upper frame shows (by the large squares drawn in broken line) an abstract plan at level3. The quality of the plan, 0.826, is determined by the length of the route the robot would have followed if guided by this plan (shown in the figure by a heavy broken line) compared to the length of the shortest route. The lower frame shows a more precise abstract plan with segments at levels 0 and 1. Notice that in this example the quality of the plan reached 0.985 - almost as good as the quality of the shortest path.

The typical performance of the planner is summarized by its performance profile in Figure 5. The graph shows the ex· pected quality of the plan as a function of run-time. When run until completion, the expected quality of the plan produced by the abstract planner is 0.93. At the same time, its expected completion time is only 27% of the the expected run-time needed to compute the optimal path using the standard A' algorithm. These figures show that anytime algorithms offer not only more flexibility but also a better cost/performance ratio.

3.5 Performance with imperfect vision

We now turn to examine the effect of vision errors on the qual· ity of planning. The following demonstration is based on vi­ sion quality of 0.96. This figure is a measure of the sensor's noise level as described in the previous section. The physical domain is identical to the one used in the previous example, however, the map constructed by the vision module is erro­ neous.

Figure 6 shows snapshots of the plan generated by the al· gorithm and their qualities. Notice that as a result of lower quality of sensing, the quality of the initial plan is only 0.760 compared to 0.826 with perfect vision. On average, as a result of the error in the domain description, the planner produces plans of lower quality.

Based on statistics gathered by running the planning algo­ rithm many times on randomly generated domains, we de­ rived its conditional performance profile. It describes the ex· pected quality of a plan based on the quality of the domain description and run-time. Figure 7 shows the conditional per· formance profile. Each curve shows the expected plan quality as a function of run-time for a particular quality of vision.

4 Compilation of sensing and planning

The compilation of anytime algorithms is a process that essen· tially extends the idea of functional composition to anytime computation. It allows the programmer to compose a sys· tern using anytime algorithms as components without deal· ing directly with the time allocation problem. To explain the compilation process we must first make a distinction between

Figure 4: Abstract plans with perfect vision

... ....

interruptible algorithms and contract algorithms. Interrupt­ ible algorithms produce results of the quality "advertised" by their performance profiles even when interrupted unexpect­ edly; whereas contract algorithms, although capable of pro­ ducing results whose quality varies with time allocation, must be given a particular time allocation in advance. The greater freedom of design makes it easier to construct contract algo­ rithms than interruptible ones. The compilation process cre­ ates a contract algorithm. In those cases where it is necessary to use an interruptible algorithm, the contract algorithm can be transformed into an interruptible one using a construction method presented in [Russell and Zilberstein, 1991]. Having made this distinction, we can define compilation as follows:

Definition: Compilation of anytime algorithms is the process of deriving a contract algorithm with an optimal performance profile from a program composed of several anytime algo­ rithms whose conditional performance profiles are given.

The input to the compiler includes a user defined function that we call the program schema. It looks like a regular code but some of the functions it uses may be anytime algorithms. The compiler also gets a set of conditional performance profiles stored in a library. The task of the compiler is to produce a new version of the program that includes code to control the distribution of time between the components so as to maxi­ mize the overall performance for any given time allocation. It also creates a performance profile for the complete system, based on the optimal time allocation.

The hardest part of the compilation is finding the time al­ location to the components that yields maximal quality. This problem has been solved in [Zilberstein, 1993] with respect to a rich compositional language. In the case of composition of n modules, the global optimization problem is shown to be NP-complete by transformation from the partially ordered knapsack problem (which is known to be NP-complete in the strong sense [Garey and Johnson, 1979]). However, a local compilation technique, that works on a single program struc­ ture at a time, significantly improves the efficiency of compi­ lation and is proved to yield optimal performance for a large set of program structures. The composition of planning and sensing is a simple example of such program .. It is represented by the following program segment:

(find-path Start Goal (get-domain-description Sensor))

Figure 8: Compilation of vision and planning

Figure 8 shows the performance profile that we got by com­ piling this program. Also shown in that figure are the perfor­ mance profiles of two other modules: MIN, that allocates to vision a minimal amount of time, Ta, and MAX, that allo­ cates to vision a maximal amount of time, Tb. The compiled performance profile is superior to both. The reader can find a more detailed description of the compilation process in [Zil­ berstein, 1993] .

5 The run-time system

Systems composed of anytime algorithms require constant monitoring. The compilation process provides the necessary meta-level information to make the run-time monitoring more efficient. In this section we explain how the run-time system controls the time allocation to the anytime modules.

The optimization of the long-term behavior of the robot is performed by dividing a complex task into a series of small sensing, planning and plan execution episodes called frames. For each frame, we use the anytime sensing and planning modules described earlier. Since, in many cases, sensing ca­ pability is limited to a small, local segment of the environ­ ment, it is only natural to break the navigation problem into such frames.

The task of the meta-level control is to determine the opti­ mal initial contract time for each frame. This decision- inter­ frame optimization - is made in the following way: let t be the current time (real-time since the beginning of the execu­ tion of the task), let It be the (estimated) number of frames left at time t for planning and execution, let t c be the contract time for the next cycle of planning and execution, and let e1 be the energy used so far for plan execution. Then,

where VOT is the expected value of the task and COE is the expected cost of energy. Note that both the performance profile of the system and a model of the environment are nec­ essary in order to compute these functions.

Once an initial contract time is determined, the system starts allocating resoUICes to sensing, planning and plan ex­ ecution. At the same time it continues to monitor the per­ formance of the anytime modules. This constant monitoring is necessary because of the uncertainty concerning the ac­ tual quality of plans and the actual time necessary to execute them. The purpose of the meta-level control in this phase is to reach an optimal plan quality for the next frame while execut­ ing a previously derived plan. For this purpose, it can modify the initial contract time. This decision- intra-frame optimiza­ tion - is made in the following way: the monitor determines at each point whether planning is ahead of or behind expec­ tations by comparing the (estimated) plan quality to the qual­ ity advertised by the performance profile. It also determines whether plan execution is ahead of or behind expectations by comparing the (estimated) execution time to the frame con­ tract time. If planning is ahead of expectations and plan ex­ ecution is behind, the monitor accelerates plan execution by allocation more resOUICes (energy) to plan execution. If plan­ ning is behind and plan execution is ahead, the monitor slows down plan execution by reducing resource consumption.

This monitoring strategy can be modified in various ways. For example, one can consider planning more than one frame ahead, when plan execution is slow. Another possibility in this case is to replan part of the plan that is being executed to accelerate plan execution. However, our experiments with the above domain show that the monitoring strategy that was implemented is sufficient in order to achieve (within 4% er­ ror) the optimal task value that the system computes when presented with the task.

6 Conclusion

We have presented a method to construct robotic systems and to optimize their performance. The method is based on devel­ oping the performance components of the system as anytime algorithms. The control of the anytime components of the system is efficiently implemented using off-line compilation and run-time monitoring. An implementation of the model was presented that solves a particular path planning problem. Our approach offers several improvements over traditional ad hoc techniques used to construct robotic systems: it is an optimizing rather than satisficing method; it allows complex planning to be used in real-time robotic systems; it helps con­ struct systems when resource availability is unknown at de­ sign time; and it efficiently integrates sensing, planning and plan execution.

The anytime abstract planning algorithm that was pre­ sented produced high quality results with time allocation that was much shorter than the total run-time of a standard search algorithm. This shows that the flexibility of anytime algo­ rithms does not necessarily require a compromise in overall performance, even with a fixed time allocation.

By further generalizing the various components of the sys­ tem, we aim at constructing a general, flexible mechanism for developing self-optimizing autonomous robots whose per­ ception, decision making and action are implemented as any­ time modules. This approach offers a more realistic theoreti­ cal foundation for robot planning by addressing the problems of uncertainty, limited computational power, and imprecise sensing.

Acknowledgements

Support for this work was provided in part by the Na­ tional Science Foundation under grants IRI-8903146 and IRI9058427 (Presidential Young Investigator Award).