Sequencing operator counts

Toby O. Davies, Adrian R. Pearce, Peter Stuckey, Nir Lipovetzky

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


Operator-counting is a recently developed framework for analysing and integrating many state-ofthe- art heuristics for planning using Linear Programming. In cost-optimal planning only the objective value of these heuristics is traditionally used to guide the search. However the primal solution, i.e. the operator counts, contains useful information. We exploit this information using a SATbased approach which given an operator-count, either finds a valid plan; or generates a generalized landmark constraint violated by that count. We show that these generalized landmarks can be used to encode the perfect heuristic, h∗, as a Mixed Integer Program. Our most interesting experimental result is that finding or refuting a sequence for an operator-count is most often empirically efficient, enabling a novel and promising approach to planning based on Logic-Based Benders Decomposition (LBBD). This paper originally appeared at ICAPS 2015 and is reproduced with the permission of the Association for Artificial Intelligence ([Davies et al., 2015]

Original languageEnglish
Title of host publicationIJCAI-16 - Proceedings of the 25th International Joint Conference on Artificial Intelligence, IJCAI 2016
Subtitle of host publicationNew York, New York, USA 9–15 July 2016
EditorsSubbarao Kambhampati
Place of PublicationPalo Alto CA USA
PublisherInternational Joint Conferences on Artificial Intelligence
Number of pages5
ISBN (Electronic)9781577357704, 9781577357711
Publication statusPublished - 2016
Externally publishedYes
EventInternational Joint Conference on Artificial Intelligence 2016 - New York, United States of America
Duration: 9 Jul 201615 Jul 2016
Conference number: 25th


ConferenceInternational Joint Conference on Artificial Intelligence 2016
Abbreviated titleIJCAI 2016
CountryUnited States of America
CityNew York
Internet address

Cite this