We consider the problem of planning paths of multiple agents in a dynamic but predictable environment. Typical scenarios are evacuation, reconfiguration, and containment. We present a novel representation of abstract path-planning problems in which the stationary environment is explicitly coded as a graph (called the arena) while the dynamic environment is treated as just another agent. The complexity of planning using this representation is pspace-complete. The arena complexity (i.e., the complexity of the planning problem in which the graph is the only input, in particular, the number of agents is fixed) is np-hard. Thus, we provide structural restrictions that put the arena complexity of the planning problem into ptime(for any fixed number of agents). The importance of our work is that these structural conditions (and hence the complexity results) do not depend on graph-theoretic properties of the arena (such as clique- or tree-width), but rather on the abilities of the agents.
Multi-agent path planning in known dynamic environments / Murano, Aniello; Giuseppe, Perelli; Sasha, Rubin. - 9387:(2015), pp. 218-231. (Intervento presentato al convegno 18th International Conference on Principles and Practice of Multi-Agent Systems, PRIMA 2015 tenutosi a Bertinoro, Italia nel Ottobre 26–30, 2015) [10.1007/978-3-319-25524-8_14].
Multi-agent path planning in known dynamic environments
MURANO, ANIELLO;
2015
Abstract
We consider the problem of planning paths of multiple agents in a dynamic but predictable environment. Typical scenarios are evacuation, reconfiguration, and containment. We present a novel representation of abstract path-planning problems in which the stationary environment is explicitly coded as a graph (called the arena) while the dynamic environment is treated as just another agent. The complexity of planning using this representation is pspace-complete. The arena complexity (i.e., the complexity of the planning problem in which the graph is the only input, in particular, the number of agents is fixed) is np-hard. Thus, we provide structural restrictions that put the arena complexity of the planning problem into ptime(for any fixed number of agents). The importance of our work is that these structural conditions (and hence the complexity results) do not depend on graph-theoretic properties of the arena (such as clique- or tree-width), but rather on the abilities of the agents.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
