DROPS

Document

DOI: 10.4230/LIPIcs.CP.2026.55

An Automata-Based Constraint Programming Framework for Optimal Classical Planning

Authors: Damien Van Meerbeeck, Arnaud Lequen, Gilles Pesant, and Jendrik Seipp

Published in: LIPIcs, Volume 379, 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)

Abstract

Recent work has shown that classical planning tasks can be compactly factored into deterministic finite automata and solved optimally with constraint programming (CP). In this setting, finding a plan reduces to finding a word accepted by all automata through Regular constraints. So far, however, these automata have had to be carefully handcrafted from PDDL tasks. In this paper, we show that they can instead be generated automatically and used as the basis of CP models. We also show that the resulting framework is easily extensible with additional constraints from the planning literature that strengthen propagation. Our approach solves more tasks than the state of the art in end-to-end CP for classical planning in almost all domains.

Cite as

Damien Van Meerbeeck, Arnaud Lequen, Gilles Pesant, and Jendrik Seipp. An Automata-Based Constraint Programming Framework for Optimal Classical Planning. In 32nd International Conference on Principles and Practice of Constraint Programming (CP 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 379, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{vanmeerbeeck_et_al:LIPIcs.CP.2026.55,
  author =	{Van Meerbeeck, Damien and Lequen, Arnaud and Pesant, Gilles and Seipp, Jendrik},
  title =	{{An Automata-Based Constraint Programming Framework for Optimal Classical Planning}},
  booktitle =	{32nd International Conference on Principles and Practice of Constraint Programming (CP 2026)},
  pages =	{55:1--55:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-432-1},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{379},
  editor =	{Beldiceanu, Nicolas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2026.55},
  URN =		{urn:nbn:de:0030-drops-266889},
  doi =		{10.4230/LIPIcs.CP.2026.55},
  annote =	{Keywords: Optimal Classical Planning, Landmark Constraints, Automata}
}

Document

DOI: 10.4230/LIPIcs.CP.2022.13

Isomorphisms Between STRIPS Problems and Sub-Problems

Authors: Martin C. Cooper, Arnaud Lequen, and Frédéric Maris

Published in: LIPIcs, Volume 235, 28th International Conference on Principles and Practice of Constraint Programming (CP 2022)

Abstract

Determining whether two STRIPS planning instances are isomorphic is the simplest form of comparison between planning instances. It is also a particular case of the problem concerned with finding an isomorphism between a planning instance P and a sub-instance of another instance P'. One application of such an isomorphism is to efficiently produce a compiled form containing all solutions to P from a compiled form containing all solutions to P'. In this paper, we study the complexity of both problems. We show that the former is GI-complete, and can thus be solved, in theory, in quasi-polynomial time. While we prove the latter to be NP-complete, we propose an algorithm to build an isomorphism, when possible. We report extensive experimental trials on benchmark problems which demonstrate conclusively that applying constraint propagation in preprocessing can greatly improve the efficiency of a SAT solver.

Cite as

Martin C. Cooper, Arnaud Lequen, and Frédéric Maris. Isomorphisms Between STRIPS Problems and Sub-Problems. In 28th International Conference on Principles and Practice of Constraint Programming (CP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 235, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{cooper_et_al:LIPIcs.CP.2022.13,
  author =	{Cooper, Martin C. and Lequen, Arnaud and Maris, Fr\'{e}d\'{e}ric},
  title =	{{Isomorphisms Between STRIPS Problems and Sub-Problems}},
  booktitle =	{28th International Conference on Principles and Practice of Constraint Programming (CP 2022)},
  pages =	{13:1--13:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-240-2},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{235},
  editor =	{Solnon, Christine},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2022.13},
  URN =		{urn:nbn:de:0030-drops-166426},
  doi =		{10.4230/LIPIcs.CP.2022.13},
  annote =	{Keywords: planning, isomorphism, complexity, constraint propagation}
}

Search Results

Documents authored by Lequen, Arnaud

An Automata-Based Constraint Programming Framework for Optimal Classical Planning

Abstract

Cite as

Isomorphisms Between STRIPS Problems and Sub-Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message