Search Results

Documents authored by Sumic, Ajdin

Artifact
Software
DOI: 10.4230/artifacts.27850
Multi-agent Path Finding with Tasks under Time Uncertainty

Authors: Ajdin Sumic and Noëlie Ramuzat

Abstract
Cite as

Ajdin Sumic, Noëlie Ramuzat. Multi-agent Path Finding with Tasks under Time Uncertainty (Software). Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@misc{dagstuhl-artifact-27850,
   title = {{Multi-agent Path Finding with Tasks under Time Uncertainty}}, 
   author = {Sumic, Ajdin and Ramuzat, No\"{e}lie},
   note = {Software, version 1.0., ANR-23-DMRO-0006, swhId: \href{https://archive.softwareheritage.org/swh:1:dir:b90831099c338304e218af5159b6add58ed219b1;origin=https://github.com/ajdin14200/MAPF_TTU_TIME;visit=swh:1:snp:37ad480d96968340182c263c9bb0f6da6b0ffc97;anchor=swh:1:rev:10cc58ec7e0ce78479089eaaf8a19c1ad2fa7b7f}{\texttt{swh:1:dir:b90831099c338304e218af5159b6add58ed219b1}} (visited on 2026-10-10)},
   url = {https://github.com/ajdin14200/MAPF_TTU_TIME},
   doi = {10.4230/artifacts.27850},
}
Document
DOI: 10.4230/OASIcs.TIME.2026.13
Multi-Agent Path Finding with Tasks Under Time Uncertainty

Authors: Alexandre Albore, Christophe Grand, Noëlie Ramuzat, and Ajdin Sumic

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

Abstract
Multi-Agent Path Finding under Time Uncertainty (MAPF-TU) extends classical MAPF by considering uncertain traversal duration. However, existing approaches, such as the Conflict Based Search with Time Uncertainty (CBS_TU) method, assume that uncertainty only arises while agents move between locations, overlooking uncertainty induced by executing tasks. In many real-world applications, agents must not only navigate but also perform tasks of uncertain duration at specific locations, leading to additional temporal dependencies. In this paper, we introduce Multi-Agent Path Finding with Tasks under Time Uncertainty (MAPF-TTU), a new extension of MAPF-TU in which agents must execute tasks of uncertain duration at intermediate goals. We first analyze the computational complexity of MAPF-TU and MAPF-TTU. We then propose two complementary solution approaches. The first extends CBS_TU to explicitly reason about uncertain task execution during planning. The second transforms an MAPF-TU solution into a Simple Temporal Network with Uncertainty (STNU) and computes a robust execution schedule through Strong Controllability. Finally, we experimentally evaluate both approaches under varying levels of traversal and task time uncertainty, highlighting the tradeoff between solution quality and scalability.
Cite as

Alexandre Albore, Christophe Grand, Noëlie Ramuzat, and Ajdin Sumic. Multi-Agent Path Finding with Tasks Under Time Uncertainty. In 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026). Open Access Series in Informatics (OASIcs), Volume 146, pp. 13:1-13:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{albore_et_al:OASIcs.TIME.2026.13,
  author =	{Albore, Alexandre and Grand, Christophe and Ramuzat, No\"{e}lie and Sumic, Ajdin},
  title =	{{Multi-Agent Path Finding with Tasks Under Time Uncertainty}},
  booktitle =	{33rd International Symposium on Temporal Representation and Reasoning (TIME 2026)},
  pages =	{13:1--13:21},
  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.13},
  URN =		{urn:nbn:de:0030-drops-277090},
  doi =		{10.4230/OASIcs.TIME.2026.13},
  annote =	{Keywords: Multi-Agent Path Finding, Temporal Uncertainty, Conflict Based Search, Simple Temporal Network}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.8
A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty

Authors: Ajdin Sumic and Thierry Vidal

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Simple Temporal Networks with Uncertainty (STNU) are a well-known constraint-based model expressing sets of activities (e.g., a schedule or a plan) related by temporal constraints, each having possible durations in the form of convex intervals. Uncertainty comes from some of these durations being contingent, i.e., the agent executing the plan cannot decide the actual duration at execution time. To check that execution will satisfy all the constraints, three levels of controllability exist: the Strong and Dynamic Controllability (SC/DC) has proven both useful in practice and provable in polynomial time, while Weak Controllability (WC) is co-NP-complete and has been left aside. Moreover, controllability checking algorithms are propagation strategies, which have the usual drawback, in case of failure, to prove unable to locate the contingents that explain the source of non-controllability. This paper has three contributions: (1) it substantiates the usefulness of WC in multi-agent systems (MAS) where another agent controls a contingent, and agents agree just before execution on the durations; (2) it provides a new WC-checking algorithm whose performance in practice depends on the network structure and is faster in loosely connected ones; (3) it provides the failing cycles in the network that explain non-WC.
Cite as

Ajdin Sumic and Thierry Vidal. A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 8:1-8:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sumic_et_al:LIPIcs.TIME.2024.8,
  author =	{Sumic, Ajdin and Vidal, Thierry},
  title =	{{A More Efficient and Informed Algorithm to Check Weak Controllability of Simple Temporal Networks with Uncertainty}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{8:1--8:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.8},
  URN =		{urn:nbn:de:0030-drops-212151},
  doi =		{10.4230/LIPIcs.TIME.2024.8},
  annote =	{Keywords: Temporal constraints satisfaction, uncertainty, STNU, Controllability checking, Explainable inconsistency, Multi-agent planning}
}
Document
DOI: 10.4230/LIPIcs.TIME.2024.13
Introducing Interdependent Simple Temporal Networks with Uncertainty for Multi-Agent Temporal Planning

Authors: Ajdin Sumic, Thierry Vidal, Andrea Micheli, and Alessandro Cimatti

Published in: LIPIcs, Volume 318, 31st International Symposium on Temporal Representation and Reasoning (TIME 2024)

Abstract
Simple Temporal Networks with Uncertainty are a powerful and widely used formalism for representing and reasoning over convex temporal constraints in the presence of uncertainty called contingent constraints. Since their introduction, they have been used in planning and scheduling applications to model situations where the scheduling agent does not control some activity durations or event timings. What needs to be checked is then the controllability of the network, i.e., that there is a valid execution strategy whatever the values of the contingents. This paper considers a new type of multi-agent extension, where, as opposed to previous works, each agent manages its own separate STNU, and the control over activity durations is shared among the agents: what is called here a contract is a mutual constraint controllable for some agent and contingent for others. We will propose a semantically enriched version of STNUs that will be composed into a global Multi-agent Interdependent STNUs model. Then, controllability issues will be revisited, and we will focus on the repair problem, i.e., how to regain failed controllability by shrinking some of the shared contract durations, here in a centralized manner.
Cite as

Ajdin Sumic, Thierry Vidal, Andrea Micheli, and Alessandro Cimatti. Introducing Interdependent Simple Temporal Networks with Uncertainty for Multi-Agent Temporal Planning. In 31st International Symposium on Temporal Representation and Reasoning (TIME 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 318, pp. 13:1-13:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{sumic_et_al:LIPIcs.TIME.2024.13,
  author =	{Sumic, Ajdin and Vidal, Thierry and Micheli, Andrea and Cimatti, Alessandro},
  title =	{{Introducing Interdependent Simple Temporal Networks with Uncertainty for Multi-Agent Temporal Planning}},
  booktitle =	{31st International Symposium on Temporal Representation and Reasoning (TIME 2024)},
  pages =	{13:1--13:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-349-2},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{318},
  editor =	{Sala, Pietro and Sioutis, Michael and Wang, Fusheng},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.TIME.2024.13},
  URN =		{urn:nbn:de:0030-drops-212200},
  doi =		{10.4230/LIPIcs.TIME.2024.13},
  annote =	{Keywords: Temporal constraints satisfaction, uncertainty, STNU, Controllability checking, Explainable inconsistency, Multi-agent planning}
}

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact