平面上のグラフにおける最適マルチロボット経路計画の計算困難性
Intractability of Optimal Multi-Robot Path Planning on Planar Graphs
平面上のグラフ上でのマルチロボット経路計画について、時間・距離に基づく4つの目的関数すべてがNP完全であることを示し、ロボット数が多い場合は環境を拡張して対向経路の共有を減らすアプローチが有効であると示唆した。
著者: Jingjin Yu
分類: cs.RO, cs.CC
原文アブストラクト
We study the computational complexity of optimally solving multi-robot path planning problems on planar graphs. For four common time- and distance-based objectives, we show that the associated path optimization problems for multiple robots are all NP-complete, even when the underlying graph is planar. Establishing the computational intractability of optimal multi-robot path planning problems on planar graphs has important practical implications. In particular, our result suggests the preferred approach toward solving such problems, when the number of robots is large, is to augment the planar environment to reduce the sharing of paths among robots traveling in opposite directions on those paths. Indeed, such efficiency boosting structures, such as highways and elevated intersections, are ubiquitous in robotics and transportation applications.
