Network-guided multi-robot path planning in discrete representations

This work deals with problems where multiple robots move on a roadmap guided by wireless nodes that form a communication network. The nodes compute paths for the robots within their communication range given information about robots only in their vicinity and communicating only with neighbors. The objective is to compute paths that are collision-free, minimize the occurrence of deadlocks, as well as the time it takes to reach the robots' goals. This paper formulates this challenge as a distributed constraint optimization problem. This formulation lends itself to a message-passing solution that guarantees collision-avoidance despite only local knowledge of the world by the network nodes. Simulations on benchmarks that cannot be solved with coupled or simple decoupled schemes are used to evaluate parameters and study the scalability, path quality and computational overhead of the approach.

Authors

• Ryan Luna
• Kostas E. Bekris

Keywords

• Robot sensing systems
• Robot kinematics
• Collision avoidance
• Path planning
• Optimization
• Protocols
• Multi-robot Path
• Communication Range
• Computational Efficiency
• Local Information
• Shortest Path
• Sensor Networks
• Neighboring Nodes
• Multiple Agents
• Short Path
• Payoff Function
• Dense Grid
• Agent Interactions
• Dense Environments
• Belief Propagation
• Robot Path
• Candidate Paths
• Static Nodes