Decentralized Multi-Agent Path Selection Using Minimal Information

TitleDecentralized Multi-Agent Path Selection Using Minimal Information
Publication TypeConference Paper
Year of Publication2014
AuthorsKimmel, A, Bekris, K
Conference NameInternational Symposium on Distributed Autonomous Robotic Systems (DARS)
Date Published11/2014
Conference LocationDaejeon, Korea

This work aims to avoid conflicts between moving, non-communicating agents, which employ minimum sensing information. Since safety can be guaranteed by reactive obstacle avoidance for holonomic systems, the focus is on deadlock avoidance given proper selection of global paths in cluttered scenes. A method to compute the “interaction cost” of a path is proposed, which considers only the neighboring agents’ observed positions. Minimizing the interaction cost in a prototypical challenge involving two agents moving through two corridors from opposing sides guarantees the selection of non-conflicting paths. Complex scenes, however, where agents have many paths to follow are more challenging. This leads to a study of alternatives for decentralized path selection. Simulated experiments indicate that following a “minimum-conflict” path given the other agents’ observed positions results in deadlock avoidance. A scheme that selects between the minimum-conflict path and a set of shortest paths given their interaction cost improves path quality while still achieving deadlock avoidance. Finally, learning to select between the minimum-conflict and one of the shortest paths can also be achieved by reasoning using regret minimization. This hindsight learning method allows agents to be adaptive to the behavior of their neighbors.

Refereed DesignationRefereed