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

Publication Type:

Conference Paper

Authors:

Bekris, K.E.; Tsianos, K.I.; Kavraki, L.E.

Source:

First International Conference on Robot Communication and Coordination (ROBOCOMM 07), Athens, Greece (2007)

URL:

http://www.kavrakilab.org/sites/default/files/bekris_tsianos_robocomm07.pdf

Keywords:

distributed safe replanning

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.