Research Area of Planning and Scheduling

Michael Beetz, Henrik Grosskreuz
Causal Models for Concurrent Reactive Robot Action Plans

Abstract: Temporal projection, the process of predicting what will happen when a robot executes its plan, is essential for autonomous service robots to successfully plan their missions. This paper describes a causal model of the behavior exhibited by a mobile robot when running concurrent reactive plans. The model represents aspects of robot behavior that cannot be represented by most action models used in AI planning: it represents the temporal structure of continuous control processes, several modes of their interferences, and various kinds of uncertainty. This enhanced expressiveness enables robot action planning systems to predict, and therefore forestall, various kinds of behavior flaws including missed deadlines whilst expoiting incidental opportunities. the proposed causal model is experimentally validated.

Date of Submission:   May 23, 2000

Massimo Paolucci, O. Shehory, Katya Sycara
Interleaving Planning and Execution in a Multiagent Team Planning Environment

Abstract: Agents in a multiagent system may need to share information and services. For this, they need to be able to interleave deliberative planning with execution of actions. The deliberative planning is needed to decide which actions to perform to achieve an objective, whereas execution of some of the actions is needed to make a more informed decision on the other actions and to access services provided by other agents.
HITaP is a planner that interleaves planning and execution: using HITaP an agent can, during planning, gather information by either direct inspection of the domain or by firing queries to other agents and recording their answers. Interleaving planning and execution, as provided by HITaP, plays a crucial role in an agent's ability to construct shared plans with other agents and to manage the negotiation process that leads to agreement with the agent's teammates on these plans.
HITaP is implemented and currently used as planning module for agents in the RETSINA multiagent system. These agents cooperate to solve problems in different domains that range from portfolio management to command and control decision support systems.

Date of Submission:   February 5, 2000

Richard Washington, Keith Golden, John Bresina
Plan Execution, Monitoring, and Adaptation for Planetary Rovers

Abstract: Planetary rovers must perform their missions in unknown environments with limited communication to ground controllers. To endow a rover with the capability for robust autonomous operation, we have designed an on-board executive architecture that incorporates robust flexible operation, monitoring of system and environmental state, and limited plan adaptation. The rover executive receives a plan with flexible time and resource contraints along with local and global contingency plans to handle deviations from the nominal plan. It internally monitors plan execution for communication and execution failures; through sensors and models of its operation it determines its internal state, its resource usage, and its interaction with respect to the environment. Based on the information it gathers from the sonsors, it chooses the most appropriate course of action, potentially inserting contingency plans into its current plan, thus adapting its plan to fit the current situation.

Date of Submission:   February 17, 2000

Tara Estlin, Gregg Rabideau, Darren Mutz, Steve Chien
Using Continuous Planning Techniques to Coordinate Multiple Rovers

Abstract: This paper describes a dynamic planning system for coordinating multiple rovers in collecting planetary surface data. A distributed planning system is shown to generate rover plans for achieving science goals, coordinate activities among rovers, monitor plan execution, and perform re-planning when necessary. Specifically, we describe how rover command generation can be automated to help relieve some of the burden on human operators. We describe the issues inherent in planning for a distributed set of rovers and discuss how these issues can be addressed in a dynamic and uncertain environment. Finally, we describe a prototype system for automatically generating low-level commands and monitoring their execution for a team of rovers with the overall goal of achieving a set of geology-related science requests.

Date of Submission:   February 9, 2000

Abdel-Illah Mouaddib
Multi-Criteria Decision Quality Optimization as a Scheduling Problem

Abstract: Decision quality under uncertainty is a problem that has been addressed by many researchers. But most of the works dedicated to this problem assume that there is a single quality measure to computation based on the status of an n-tuple of criteria. However, in most of real-world applications the quality is multi-criteria where each criterion captures a dimension of value in the solution. In this paper, we present a decision maker that manipulates the quality as a vector of criteria where the improvemnet of each criterion is in charge of a progressive processing agent that uses its hierarchy of processing levels to improve the quality of this criterion incrementally. We discuss the problem of optimizing the decision of sequencing processing levels of agents by transforming it to a MDP. We also present the strategy to be adopted when considering the criteria preferences. Finally, we discuss how this approach can be applied to controlling a static set of dependent progressive processing agents where there is no predetermined sequence of agents.

Date of Submission:   March 7, 2000

Michael Beetz and Henrik Grosskreutz
Causal Models of Mobile Service Robot Behavior

Abstract: Temporal projection, the process of predicting what will happen when a robot executes its plan, is essential for autonomous service robots to successfully plan their missions. This paper describes a causal model of the behavior exhibited by the mobile robot RHINO when running concurrent reactive plans for performing office delivery jobs. The model represents aspects of robot behavior that cannot be represented by most action models used in AI planning: it represents the temporal structure of continuous control processes, several modes of their interferences, and various kinds of uncertainty. This enhanced expressiveness enables XFRM (McD92; BM94), a robot planning system, to predict, and therefore forestall, various kinds of behavior flaws including missed deadlines whilst exploiting incidental opportunities. The proposed causal model is experimentally validated using the robot and its simulator.

Date of Submission:   December 23, 1997

Currently, the paper is being revised by the authors.

Austin Tate
Representing Plans as a Set of Constraints -
The < I-N-OVA > Model

Abstract: This paper presents an approach to representing and manipulating plans based on a model of plans as a set of constraints. The < I-N-OVA > ( Issues - Nodes - Orderings/Variables/Auxiliary) model is used to characterise the plan representation used within O-Plan and to relate this work to emerging formal analyses of plans and planning. This synergy of practical and formal approaches can stretch the formal methods to cover realistic plan representations, as needed for real problem solving, and can improve the analysis that is possible for production planning systems.
< I-N-OVA > is intended to act as a bridge to improve dialogue between a number of communities working on formal planning theories, practical planning systems and systems engineering process management methodologies. It is intended to support new work on automatic manipulation of plans, human communication about plans, principled and reliable acquisition of plan information, and formal reasoning about plans.

Date of Submission:   August 21, 1997

After the discussion period, the paper entered into confidential peer reviewing by January 5, 1998.

15-March-2000