Planning and Execution in ROGUE

 

There are a few approaches to creating plans for execution. Shakey [Nilsson1984] was the first system to use a planning system on a robot. This project was based on a classical planner that ignored real world uncertainty [Fikes, Hart, & Nilsson1972] and followed a deterministic model to generate a single executable plan. When execution failures occurred, replanning was invoked.

This pioneering approach has been acknowledged as partly successful, but also has been criticized for its lack of reactivity, and has led to significant research into planning systems that can handle the uncertainty of the real world. Conditional planning is one approach that aims at considering in the domain model all the possible contingencies of the world and planning ahead for each individual one [Atkins, Durfee, & Shin1996, Mansell1993, Pryor1994, Schoppers1989]. In most complex environments, the large number of possible contingencies means that complete conditional planning becomes infeasible, but may nevertheless be appropriate in particularly dangerous domains.

Probabilistic planning takes a more moderate approach in that it only creates conditional plans for the most likely problems [Blythe1994, Dean & Boddy1988, Gervasio & DeJong1991, Kushmerick, Hanks, & Weld1993]. It relies on replanning when unpredictable or rare events take place. Although this approach generates fast responses to most contingencies, it may miss potential opportunities that arise from changes in the world. It should be noted that none of these systems have ever been applied to a real robotic system.

Another moderate approach is that of parallel planning and execution, in which the planner and the executor are decoupled [Drummond et al. 1993, Lyons & Hendriks1992, McDermott1992, Pell et al. 1997]. The executor can react to the environment without a plan. The planner continually modifies the behaviour of the executor to increase the goal satisfaction probability. This approach leads to a system with fast reactions, but a set of default plans need to be pre-prepared, and in some situations may lead away from the desired goal. Furthermore, the planner creates its plans based on assumptions about the world that may have changed during planning time.

We take a third approach: that of interleaving planning and execution, as do several other researchers [Ambros-Ingerson & Steel1988, Dean et al. 1990, Georgeff & Ingrand1989, Nourbakhsh1997]. Interleaving planning with execution allows the system to reduce its planning effort by pruning alternative possible outcomes immediately, and also to respond quickly and effectively to changes in the environment. For example, the system can notice limited resources such as battery power, or notice external events like doors opening and closing. In these ways, interleaving planning with execution can create opportunities for the system while reducing the planning effort.

One of the main issues raised by interleaved planning and execution is when to stop planning and start executing. Dean [1990] selects between alternative actions by selecting the one with the highest degree of information gain, but is therefore limited to reversible domains. Nourbakhsh [1997],

on the other hand, executes actions that prefix all branches of a conditional plan created after making simplifying assumptions about the world. The assumptions are built so that the planner always preserves goal reachability, even in an irreversible world.

ROGUE has two methods for selecting when to take an action. The first method selects an action when it is the first in a chain of actions that are known to lead towards the goal. PRODIGY4.0 uses means-ends analysis to build plans backwards, working from the goal towards the initial state. Each action is described in terms of required preconditions and possible effects; actions are added to the plan when their effects are desirable. When all the preconditions of an action are believed to be true in the current state, ROGUE executes the action. Since PRODIGY4.0 already has a partial plan from the initial state to the goal state, the action ROGUE selects is clearly relevant to achieving the goal. Actions whose failures may lead to irreversible states are avoided until it has exhausted all other possible ways of reaching the goal. The second method is used when there are multiple actions available for selection. ROGUE selects between these actions in order to maximize overall expected execution efficiency.

When ROGUE selects an action for execution, it executes a procedure that confirms the preconditions of the action, then executes the action, and finally confirms the effects. In addition to the explicit confirmation of preconditions and effects of actions, our system also monitors events that may affect pending goals. Each goal type has a set of associated monitors that are invoked when a goal of that type enters the system. These monitors run parallel to planning and may modify the planner's knowledge at any time. A given monitor may, for example, monitor battery power or examine camera images for particular objects.

The ability to handle asynchronous goals is a basic requirement of a system executing in the real world. A system that only handles asynchronous goals in a first-come-first-served manner is inefficient and loses many opportunities for combined execution. ROGUE easily incorporates asynchronous goals into its system without losing context of existing tasks, allowing it to take advantage of opportunities as they arise. By intelligent combining of compatible tasks, ROGUE can respond quickly and efficiently to user requests.

Amongst the other interleaving planners, only PRS [Georgeff & Ingrand1989] handles multiple asynchronous goals. ROGUE however abstracts much of the lower level details that PRS explicitly reasons about, meaning that ROGUE can be seen as more reliable and efficient because system functionality is suitably partitioned [Pell et al. 1997, Simmons et al. 1997]. NMRA [Pell et al. 1997] and [Bonasso & Kortenkamp1996] both function in domains with many asynchronous goals, but both planners respond to new goals and serious action failures by abandoning existing planning and restarting the planner. As stated by Pell et al. , establishing standby modes prior to invoking the planner is ``a costly activity, as it causes [the system] to interrupt the ongoing planned activities and lose important opportunities.'' Throwing out all existing planning and starting over not only delays execution and but also can place high demands on sensing to determine current status of partially-executed tasks.

In summary, ROGUE's interleaving of planning and execution can be outlined in the following procedure for accomplishing a set of tasks:

1. A user submits a request, and ROGUE adds the task information to PRODIGY4.0's state.
2. PRODIGY4.0 creates a plan to achieve the goal(s), constrained by ROGUE's priority and compatibility knowledge, incorporating any new requests.
3. ROGUE sends selected actions to the robot for execution, confirming that its preconditions are valid.
4. ROGUE confirms the outcome of each action. If failure, ROGUE notifies PRODIGY4.0 and forces replanning.

In this section we have motivated our work and summarized the most relevant related work. In Section 2, we describe PRODIGY4.0, present how it plans for multiple asynchronous goals, and introduce ROGUE's priority and compatibility rules (steps 1 and 2 above). We include a detailed example of the system's behaviour for a simple two-goal problem, when the goals arrive asynchronously. In Section 3 we present execution, monitoring and how the system detects, processes and responds to failure (steps 3 and 4). Finally we provide a summary of ROGUE's capabilities in Section 4.