Distance Optimal Formation Control on Graphs with a Tight Convergence Time Guarantee

Abstract

For the task of moving a set of indistinguishable agents on a connected graph with unit edge distance to an arbitrary set of goal vertices, free of collisions, we propose a fast distance optimal control algorithm that guides the agents into the desired formation. Moreover, we show that the algorithm also provides a tight convergence time guarantee (time optimality and distance optimality cannot be simultaneously satisfied). Our generic graph formulation allows the algorithm to be applied to scenarios such as grids with holes (modeling obstacles) in arbitrary dimensions. Simulations, available online, confirm our theoretical developments.

Brought to be in-sync with final version submitted to CDC 2012 with only minor updates

Cited by in corpus (6)

• Motion Planning for Unlabeled Discs with Optimality Guarantees
• Planning Optimal Paths for Multiple Robots on Graphs
• Graph Policy Gradients for Large Scale Unlabeled Motion Planning with Constraints
• DDM: Fast Near-Optimal Multi-Robot Path Planning using Diversified-Path and Optimal Sub-Problem Solution Database Heuristics
• Target Assignment in Robotic Networks: Distance Optimality Guarantees and Hierarchical Strategies
• Shortest Path Set Induced Vertex Ordering and its Application to Distributed Distance Optimal Multi-agent Formation Path Planning