Fragment-based planning using column generation

Toby O. Davies, Adrian R. Pearce, Peter J. Stuckey, Harald Søndergaard

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

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 in finding 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.

Original languageEnglish
Title of host publicationICAPS 2014 - Proceedings of the Twenty-Fourth International Conference on Automated Planning and Scheduling
Subtitle of host publication21-26 June 2014 Portsmouth, New Hampshire USA
EditorsSteve Chien, Steve Chien, Wheeler Ruml, Minh Do
Place of PublicationPalo Alto CA USA
Pages83-91
Number of pages9
Publication statusPublished - 2014
Externally publishedYes
EventInternational Conference on Automated Planning and Scheduling 2014 - Sheraton Harborside Hotel, Portsmouth, United States of America
Duration: 21 Jun 201426 Jun 2014
Conference number: 24
http://icaps14.icaps-conference.org/

Conference

ConferenceInternational Conference on Automated Planning and Scheduling 2014
Abbreviated titleICAPS 2014
CountryUnited States of America
CityPortsmouth
Period21/06/1426/06/14
Internet address

Cite this