RealPlan Home Page

Abstract

In most real-world reasoning problems, planning and scheduling phases are loosely coupled . For example, in project planning, the user comes up with a task list and schedules it with a scheduling tool like Microsoft Project. One can view automated planning in a similar way in which there is an action selection phase where actions are selected and ordered to reach the desired goals, and a resource allocation phase where enough resources are assigned to ensure the successful execution of the chosen actions. On the other hand, most existing automated planners studied in Artificial Intelligence do not exploit this loose-coupling and perform both action selection and resource assignment employing the same algorithm. The current work shows that the above strategy severely curtails the scale-up potential of existing state of the art planners which can be overcome by leveraging the loose coupling.

Specifically, a novel planning framework called RealPlan is developed in which resource allocation is de-coupled from planning and is handled in a separate scheduling phase. The scheduling problem with discrete resources is represented as a Constraint Satisfaction Problem (CSP) problem, and the planner and scheduler interact either in a master-slave manner RealPlan-MS or in a peer-peer relationship RealPlan-PP . In the former, the scheduler simply tries to assign resources to the abstract causal plan passed to it by the planner and returns success. In the latter, a more sophisticated ``multi-module dependency directed backtracking'' approach is used where the failure explanation in the scheduler is translated back to the planner and serves as a nogood to direct planner search.

RealPlan not only preserves both the correctness as well as the quality (measured in length) of the plan but also improves efficiency. Moreover, the failure-driven learning of constraints can serve as an elegant and effective approach for integrating planning and scheduling systems. Beyond the context of planner efficiency, the current work can be viewed as an important step towards merging planning with real world problem solving where plan failure during execution can be resolved by undertaking only necessary resource re-allocation and not complete re-planning.

Papers

  1. Planning the Project Management Way: Efficient Planning by
    Effective Integration of Causal and Resource Reasoning in RealPlan.
    Biplav Srivastava, Subbarao Kambhampati, Binh Minh Do
    ASU CSE Technical Report (Postscript) (PDF)

    Summary: This paper describes RealPlan , RealPlan-MS and RealPlan-PP in
    detail and draws parallels with project management.

  2. RealPlan: Decoupling Causal and Resource Reasoning in Planning
    Biplav Srivastava.
    Appears in AAAI-00.

    Summary: This paper describes RealPlan and RealPlan-MS with declarative
    scheduling and improved control flow.

  3. Scaling up planning by teasing out resource scheduling
    Biplav Srivastava & Subbarao Kambhampati.
    Appears in ECP-99. A shorter version presented at AAAI Spring
    Symposium on Search Strategies.

    Summary: This paper describes RealPlan and RealPlan-MS with procedural scheduling.

Talk

  1. Here are the slides from a talk on RealPlan-MS with procedural scheduling
    given at ECP-1999.
Biplav Srivastava
Last modified: Mon Jul 17 11:04:56 MST 2000