Safe and Distributed Kinodynamic Replanning for Vehicular Networks

TitleSafe and Distributed Kinodynamic Replanning for Vehicular Networks
Publication TypeJournal Article
Year of Publication2009
AuthorsBekris, KE, Tsianos, K, Kavraki, LE
JournalMobile Networks and Applications
Start Page292-308
Date PublishedFebruary 2009

This work deals with the problem of planning collision-free motions for multiple communicating vehicles that operate in the same, partially-observable environment in real-time. 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 initially shows how it is possible to provide theoretical safety guarantees with a priority-based coordination scheme. Safety means avoiding collisions with obstacles and between vehicles. This notion is also extended to include the retainment of a communication network when the vehicles operate as a networked team. The paper then progresses to extend this safety framework into a fully distributed communication protocol for real-time planning. The proposed algorithm integrates 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. The theoretical results have also been experimentally confirmed with a distributed simulator built on a cluster of processors and using applications such as coordinated exploration. Furthermore, experiments show that the distributed protocol has better scalability properties when compared against the priority-based scheme.

Refereed DesignationRefereed