Safe and Distributed Kinodynamic Replanning for Vehicular Networks
|Title||Safe and Distributed Kinodynamic Replanning for Vehicular Networks|
|Publication Type||Journal Article|
|Year of Publication||2009|
|Authors||Bekris, KE, Tsianos, K, Kavraki, LE|
|Journal||Mobile Networks and Applications|
|Date Published||February 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.