最短経路集合が誘導する頂点順序と分散距離最適マルチエージェント編隊経路計画への応用
Shortest Path Set Induced Vertex Ordering and its Application to Distributed Distance Optimal Multi-agent Formation Path Planning
単位辺長グラフ上で区別不能なエージェント群を目標編隊へ移動させる際、最短経路集合が頂点の順序を誘導することを示し、それに基づく分散スケジューリングアルゴリズムを提案した。非単位容量・辺長の一般グラフにも拡張し、収束時間を保証する。
著者: Jingjin Yu
分類: cs.RO, cs.SY, eess.SY
原文アブストラクト
For the task of moving a group of indistinguishable agents on a connected graph with unit edge lengths into an arbitrary goal formation, it was previously shown that distance optimal paths can be scheduled to complete with a tight convergence time guarantee, using a fully centralized algorithm. In this study, we show that the problem formulation in fact induces a more fundamental ordering of the vertices on the underlying graph network, which directly leads to a more intuitive scheduling algorithm that assures the same convergence time and runs faster. More importantly, this structure enables a distributed scheduling algorithm once individual paths are assigned to the agents, which was not possible before. The vertex ordering also readily extends to more general graphs - those with non-unit capacities and edge lengths - for which we again guarantee the convergence time until the desired formation is achieved.
