Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Multiagent connected path planning : pspace-completeness and how to deal with it

Tateo, Davide LU orcid ; Banfi, Jacopo ; Riva, Alessandro ; Amigoni, Francesco and Bonarini, Andrea (2018) 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 In 32nd AAAI Conference on Artificial Intelligence, AAAI 2018 p.4735-4742
Abstract

In the Multiagent Connected Path Planning problem (MCPP), a team of agents moving in a graph-represented environment must plan a set of start-goal joint paths which ensures global connectivity at each time step, under some communication model. The decision version of this problem asking for the existence of a plan that can be executed in at most a given number of steps is claimed to be NP-complete in the literature. The NP membership proof, however, is not detailed. In this paper, we show that, in fact, even deciding whether a feasible plan exists is a PSPACE-complete problem. Furthermore, we present three algorithms adopting different search paradigms, and we empirically show that they may efficiently obtain a feasible plan, if any... (More)

In the Multiagent Connected Path Planning problem (MCPP), a team of agents moving in a graph-represented environment must plan a set of start-goal joint paths which ensures global connectivity at each time step, under some communication model. The decision version of this problem asking for the existence of a plan that can be executed in at most a given number of steps is claimed to be NP-complete in the literature. The NP membership proof, however, is not detailed. In this paper, we show that, in fact, even deciding whether a feasible plan exists is a PSPACE-complete problem. Furthermore, we present three algorithms adopting different search paradigms, and we empirically show that they may efficiently obtain a feasible plan, if any exists, in different settings.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
32nd AAAI Conference on Artificial Intelligence, AAAI 2018
series title
32nd AAAI Conference on Artificial Intelligence, AAAI 2018
pages
8 pages
publisher
AAAI Press
conference name
32nd AAAI Conference on Artificial Intelligence, AAAI 2018
conference location
New Orleans, United States
conference dates
2018-02-02 - 2018-02-07
external identifiers
  • scopus:85060453453
ISBN
9781577358008
language
English
LU publication?
no
id
7562f31c-488a-4028-a9a6-61b5b77e37e1
date added to LUP
2025-10-16 14:42:28
date last changed
2025-10-24 03:39:45
@inproceedings{7562f31c-488a-4028-a9a6-61b5b77e37e1,
  abstract     = {{<p>In the Multiagent Connected Path Planning problem (MCPP), a team of agents moving in a graph-represented environment must plan a set of start-goal joint paths which ensures global connectivity at each time step, under some communication model. The decision version of this problem asking for the existence of a plan that can be executed in at most a given number of steps is claimed to be NP-complete in the literature. The NP membership proof, however, is not detailed. In this paper, we show that, in fact, even deciding whether a feasible plan exists is a PSPACE-complete problem. Furthermore, we present three algorithms adopting different search paradigms, and we empirically show that they may efficiently obtain a feasible plan, if any exists, in different settings.</p>}},
  author       = {{Tateo, Davide and Banfi, Jacopo and Riva, Alessandro and Amigoni, Francesco and Bonarini, Andrea}},
  booktitle    = {{32nd AAAI Conference on Artificial Intelligence, AAAI 2018}},
  isbn         = {{9781577358008}},
  language     = {{eng}},
  pages        = {{4735--4742}},
  publisher    = {{AAAI Press}},
  series       = {{32nd AAAI Conference on Artificial Intelligence, AAAI 2018}},
  title        = {{Multiagent connected path planning : pspace-completeness and how to deal with it}},
  year         = {{2018}},
}