2026-10-10T21:17:38Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27709 2026-10-10T19:48:19Z ddc:004 open_access

Multi-Agent Path Finding with Tasks Under Time Uncertainty Albore, Alexandre Grand, Christophe Ramuzat, Noëlie Sumic, Ajdin Multi-Agent Path Finding Temporal Uncertainty Conflict Based Search Simple Temporal Network 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Alexandre Albore and Christophe Grand and Noëlie Ramuzat and Ajdin Sumic 2026 Is Part Of OASIcs, Volume 146, 33rd International Symposium on Temporal Representation and Reasoning (TIME 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/OASIcs.TIME.2026.13 urn:nbn:de:0030-drops-277090 https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.TIME.2026.13 eng https://creativecommons.org/licenses/by/4.0/legalcode