DROPS

Document

DOI: 10.4230/OASIcs.TIME.2026.9

Dynamic Quantitative Skill Distribution in Multi-Agent Temporal Planning as SMT

Authors: Josselin Guéneron and Frédéric Maris

Published in: OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)

Abstract

We introduce a new framework for multi-agent temporal planning, based on event-based temporal planning, dynamic team formation and Multi-Robot Task Allocation (MRTA). Unlike existing approaches, team formation is directly integrated into the planning and scheduling process. Then, both the teams and agents' skills may evolve over time. In particular, our framework allows us to address complex and dynamic multi-agent problems, such as cooperative task execution, where heterogeneous agents with qualitative and quantitative skills must cooperate dynamically. We propose an SMT encoding of these team temporal planning problems that utilizes the linear arithmetic theory over the rational numbers, QF-LRA. Next, to demonstrate that our approach is suitable for real-world applications, we present experimental results on disaster response problems.

Cite as

Josselin Guéneron and Frédéric Maris. Dynamic Quantitative Skill Distribution in Multi-Agent Temporal Planning as SMT. In 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026). Open Access Series in Informatics (OASIcs), Volume 146, pp. 9:1-9:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{gueneron_et_al:OASIcs.TIME.2026.9,
  author =	{Gu\'{e}neron, Josselin and Maris, Fr\'{e}d\'{e}ric},
  title =	{{Dynamic Quantitative Skill Distribution in Multi-Agent Temporal Planning as SMT}},
  booktitle =	{33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)},
  pages =	{9:1--9:20},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-448-2},
  ISSN =	{2190-6807},
  year =	{2026},
  volume =	{146},
  editor =	{Orlandini, AndreA and Pinchinat, Sophie},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.9},
  URN =		{urn:nbn:de:0030-drops-277052},
  doi =		{10.4230/OASIcs.TIME.2026.9},
  annote =	{Keywords: Multi-Agent Temporal Planning, Multi-Agent Task Allocation, SMT-based Planning, Dynamic Team Formation}
}

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 Maris, Frédéric

Dynamic Quantitative Skill Distribution in Multi-Agent Temporal Planning as SMT

Abstract

Cite as

Isomorphisms Between STRIPS Problems and Sub-Problems

Abstract

Cite as

Thanks for your feedback!

Could not send message