Shortest path set induced vertex ordering and its application to distributed distance optimal formation path planning and control on graphs
Jingjin Yu, Steven M. LaValle · 2013
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 shown that distance optimal paths can be computed to complete with a tight convergence time guarantee [30], using a fully centralized algorithm. In this study, we establish the existence of a more fundamental ordering of the vertices on the underlying graph network, induced by a fixed goal formation. The ordering leads to a simple distributed scheduling algorithm that assures the same convergence time. The vertex ordering also readily extends to more general graphs - those with arbitrary integer capacities and edge lengths - for which we again provide guarantees on the convergence time until the desired formation is achieved. Simulations, accessible via a web browser, confirm our theoretical developments.