DMRR: Dynamic Multi-Robot Routing for Evolving Missions - Archive ouverte HAL Access content directly
Conference Papers Year :

DMRR: Dynamic Multi-Robot Routing for Evolving Missions

(1, 2, 3) , (1, 2) , (4) , (2) , (1, 5)


The paper proposes Dynamic Multi Robot-Routing (DMRR), as a continuous adaptation of the multi-robot target allocation process (MRTA) to new discovered targets. There are few works addressing dynamic target allocation. Existing methods are lacking the continuous integration of new targets, handling its progressive effects, but also lacking dynamicity support (e.g. parallel allocations, participation of new robots). The present paper proposes a framework for dynamically adapting the existing robot missions to new discovered targets. Missions accumulate targets continuously, so the case of a saturation bound for the mission costs is also considered. Dynamic saturation-based auctioning (DSAT) is proposed for allocating targets, providing lower time complexities (due to parallelism in allocation). Comparison is made with algorithms ranging from greedy to auction-based methods with provable sub-optimality. The algorithms are tested on exhaustive sets of inputs, with random configurations of targets (for DMRR with and without a mission saturation bound). The results for DSAT show that it outperforms state-of-the-art methods, like standard sequential single-item auctioning (SSI) or SSI with regret clearing.
Fichier principal
Vignette du fichier
DMAP_ICAPS_(camera-ready).pdf (388.75 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

hal-01942845 , version 1 (06-11-2019)


  • HAL Id : hal-01942845 , version 1


Mihai-Ioan Popescu, Olivier Simonin, Gabriela Czibula, Anne Spalanzani, Fabrice Valois. DMRR: Dynamic Multi-Robot Routing for Evolving Missions. DMAP 2018 - 6th ICAPS Workshop on Distributed and Multi-Agent Planning, Jun 2018, Delft, Netherlands. ⟨hal-01942845⟩
142 View
6 Download


Gmail Facebook Twitter LinkedIn More