A Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with Second-Order Dynamics

TitleA Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with Second-Order Dynamics
Publication TypeConference Paper
Year of Publication2007
AuthorsBekris, KE, Tsianos, K, Kavraki, LE
Conference NameFirst International Conference on Robot Communication and Coordination (ROBOCOMM 2007)
Date PublishedOct. 15-17
Conference LocationAthens, Greece
Abstract

This work deals with the problem of planning in real-time, collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment. A challenging aspect of this problem is how to utilize communication so that vehicles do not reach states from which collisions cannot be avoided due to second-order motion constraints. This paper provides a distributed communication protocol for real-time planning that guarantees collision avoidance with obstacles and between vehicles. It can also allow the retainment of a communication network when the vehicles operate as a networked team. The algorithm is a novel integration of sampling-based motion planners with message-passing protocols for distributed constraint optimization. Each vehicle uses the motion planner to generate candidate feasible trajectories and the message-passing protocol for selecting a safe and compatible trajectory. The existence of such trajectories is guaranteed by the overall approach. Experiments on a distributed simulator built on a cluster of processors confirm the safety properties of the approach in applications such as coordinated exploration. Furthermore, the distributed protocol has better scalability properties when compared against typical priority-based schemes.

URLhttp://www.cs.rutgers.edu/~kb572/pubs/distributed_safety_communication.pdf
Refereed DesignationRefereed