A Unifying Framework For Hybrid Planning And Scheduling

Proceedings of the
29th German Conference on Artificial Intelligence (KI 2006)
Bremen, Germany
June 14-19, 2006

Many real-world application domains that demand planning and scheduling support do not allow for a clear separation of these capabilities. Typically, an adequate mixture of both methodologies is required, since some aspects of the underlying planning problem imply consequences on the scheduling part and vice versa. Several integration efforts have been undertaken to couple planning and scheduling methods, most of them using separate planning and scheduling components which iteratively exchange partial solutions until both agree on a result.

This paper presents a framework that provides a uniform integration of hybrid planning – the combination of operator based partial order planning and abstraction based hierarchical task network planning – and a hierarchical scheduling approach. It is based on a proper formal account of refinement planning, which allows for the formal definition of hybrid planning, scheduling, and search strategies. In a first step, the scheduling functionality is used to produce plans that comply with time restrictions and resource bounds. We show how the resulting framework is thereby able to perform novel kinds of search strategies that opportunistically interleave what used to be separate planning and scheduling processes.

Online Copy

The paper is available online at http://dx.doi.org/10.1007/978-3-540-69912-5_27 via SpringerLink

The presentation given at KI-06 is available as PDF (2.2 MB, without animations)

@InProceedings{schattenberg:biundo:06,
  author =    {Bernd Schattenberg and Susanne Biundo},
  title =     {A Unifying Framework For Hybrid Planning And Scheduling},
  booktitle = {KI 2006: Advances in Artificial Intelligence, 
               Proceedings of the 29th German Conference on Artificial Intelligence}, 
  Editor =    {Christian Freksa and Michael Kohlhase and Kerstin Schill},
  series=     {Lecture Notes in Artificial Intelligence},
  volume=     {4314},
  pages =     {361-373},
  year =      {2007},
  address =   {Bremen, Germany},
  month =     june,
  publisher = {Springer},
  note =      {ISBN 978-3-540-69911-8}
}