swMATH ID: 1619
Software Authors: Srivastava, Biplav; Kombhampati, Subbarao; Do, Minh B.
Description: 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.
Homepage: http://rakaposhi.eas.asu.edu/realplan.html
Keywords: scheduling; constraint satisfaction problem
Related Software: Graphplan; STAN; CPlan; Optiplan; CPLEX; SAPA; UCPOP; QOCA; Walksat
Referenced in: 9 Publications

Referencing Publications by Year