Integrating Planning and Scheduling: Towards Effective Coordination in Complex Resource-Constrained Domains

Abstract

In this note, we summarize current research at CMU aimed at extending constraint-based scheduling frameworks and heuristics to enable effective integration of resource allocation and plan synthesis processes. Similar to prior work in opportunistic scheduling, our approach assumes the use of dynamic analysis of problem space structure as a basis for heuristic focusing of problem solving search. This methodology, however, is grounded in representational assumptions more akin to those adopted in recent temporal planning research, and in a problem solving framework which similarly emphasizes constraint posting in an explicitly maintained solution constraint network. We summarize recent experimental results that indicate that such problem formulation assumptions can in fact lead to better heuristic solutions than have been obtained with more-classical assignment problem formulations on benchmark problems previously studied within both the Artificial Intelligence and Operations Research communities. We conclude with a brief discussion of some important open research questions in this area.