Fragment-Based Planning Using Column Generation

Authors

  • Toby Davies NICTA ICT Australia and The University of Melbourne
  • Adrian Pearce NICTA ICT Australia and The University of Melbourne
  • Peter Stuckey NICTA ICT Australia and The University of Melbourne
  • Harald Søndergaard The University of Melbourne

DOI:

https://doi.org/10.1609/icaps.v24i1.13628

Keywords:

Fragment Based Planning

Abstract

We introduce a novel algorithm for temporal planning in Golog using shared resources, and describe the Bulk Freight Rail Scheduling Problem, a motivating example of such a temporal domain. We use the framework of column generation to tackle complex resource constrained temporal planning problems that are beyond the scope of current planning technology by combining: the global view of a linear programming relaxation of the problem; the strength of search infinding action sequences; and the domain knowledge that can be encoded in a Golog program. We show that our approach significantly outperforms state-of-the-art temporal planning and constraint programming approaches in this domain, in addition to existing temporal Golog implementations. We also apply our algorithm to a temporal variant of blocks-world where our decomposition speeds proof of optimality significantly compared to other anytime algorithms. We discuss the potential of the underlying algorithm being applicable to STRIPS planning, with further work.

Downloads

Published

2014-05-10

How to Cite

Davies, T., Pearce, A., Stuckey, P., & Søndergaard, H. (2014). Fragment-Based Planning Using Column Generation. Proceedings of the International Conference on Automated Planning and Scheduling, 24(1), 83-91. https://doi.org/10.1609/icaps.v24i1.13628