A decentralized planner that guarantees the safety of communicating vehicles with complex dynamics that replan online

This paper considers the problem of coordinating multiple vehicles with kinodynamic constraints that operate in the same partially-known environment. The vehicles are able to communicate within limited range. Their objective is to avoid collisions between them and with the obstacles, while the vehicles move towards their goals. An important issue of real-time planning for systems with bounded acceleration is that inevitable collision states must also be avoided. The focus of this paper is to guarantee safety despite the dynamic constraints with a decentralized motion planning technique that employs only local information. We propose a coordination framework that allows vehicles to generate and select compatible sets of valid trajectories and prove that this scheme guarantees collision-avoidance in the specified setup. The theoretical results have been also experimentally confirmed with a distributed simulator where each vehicle replans online with a sampling- based, kinodynamic motion planner and uses message-passing to communicate with neighboring agents.

I. Introduction

Generating safe and effective motions for realistic automobiles and autonomous mobile platforms is an important application area of motion planning. Using multiple, coordinating vehicles can offer redundancy and robustness in the execution of many tasks (e.g. space exploration, autonomous demining). Often, both the motivation and the primary concern for deploying such systems in everyday tasks is the issue of safety. One way to achieve safe coordination is to employ inter-vehicle communication so as to avoid collisions and improve the efficiency of the planned motions. This realization has led recently to the active development of vehicle-to-vehicle communication technology [18].