Planning for Connected Agents in a Partially Known Environment - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2021

Planning for Connected Agents in a Partially Known Environment

Résumé

The Connected Multi-Agent Path Finding (CMAPF) problem asks for a plan to move a group of agents in a graph while respecting a connectivity constraint. We study a generalization of CMAPF in which the graph is not entirely known in advance, but is discovered by the agents during their mission. We present a framework introducing this notion and study the problem of searching for a strategy to reach a configuration in this setting. We prove the problem to be PSPACE-complete when requiring all agents to be connected at all times, and NEXPTIME-complete in the decentralized case, regardless of whether we consider a bound on the length of the execution.
Fichier principal
Vignette du fichier
halmain.pdf (661.15 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03205744 , version 1 (22-04-2021)

Identifiants

  • HAL Id : hal-03205744 , version 1

Citer

Arthur Queffelec, Ocan Sankur, François Schwarzentruber. Planning for Connected Agents in a Partially Known Environment. AI 2021 - 34th Canadian Conference on Artificial Intelligence, May 2021, Vancouver / Virtual, Canada. pp.1-23. ⟨hal-03205744⟩
73 Consultations
109 Téléchargements

Partager

Gmail Facebook X LinkedIn More