1st International ICST Conference on Robot Communication and Coordination

Research Article

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

Download11 downloads
  • @INPROCEEDINGS{10.4108/ICST.ROBOCOMM2007.2087,
        author={Kostas E. Bekris and Konstantinos I. Tsianos and Lydia E. Kavraki},
        title={A Distributed Protocol for Safe Real-Time Planning of  Communicating Vehicles with Second-Order Dynamics},
        proceedings={1st International ICST Conference on Robot Communication and Coordination},
        proceedings_a={ROBOCOMM},
        year={2010},
        month={5},
        keywords={},
        doi={10.4108/ICST.ROBOCOMM2007.2087}
    }
    
  • Kostas E. Bekris
    Konstantinos I. Tsianos
    Lydia E. Kavraki
    Year: 2010
    A Distributed Protocol for Safe Real-Time Planning of Communicating Vehicles with Second-Order Dynamics
    ROBOCOMM
    ICST
    DOI: 10.4108/ICST.ROBOCOMM2007.2087
Kostas E. Bekris1,*, Konstantinos I. Tsianos1,*, Lydia E. Kavraki1,*
  • 1: Computer Science Department, Rice University, Houston, TX, 77005
*Contact email: bekris@cs.rice.edu, konstantinos@cs.rice.edu, kavraki@cs.rice.edu

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 realtime 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 messagepassing 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.