A decentralized approach to space deconfliction

July 2007

A decentralized approach to space deconfliction

Authors:

Paul Scerri, Sean R. Owens, B. Yu, and Katia Sycara

Abstract:

This paper presents a decentralized approach to path planning for large numbers of autonomous vehicles in sparse environments. Unlike existing approaches, which are either computationally expensive or communication intensive, the presented approach allows large numbers of vehicles to plan independently with low communication overhead. The key to the algorithm is to observe that, in sparse environments, collisions are exceptional and that most of the time vehicles will simply not hit each other. Hence, it is reasonable to allow vehicles to plan independently and then resolve the small number of conflicts. We operationalize this by having each vehicle send their planned paths to a small number of their team mates via tokens. Each team member is required to check for conflicting paths that they have been informed about via a token and inform those involved when any conflict is detected. Both analytic and empirical results show that the approach has very high probability of detecting all potential collisions for large numbers of vehicles in both 2D and 3D environments.
@conference{Scerri-2007-9781,
author = {Paul Scerri And Sean R. Owens And B. Yu And Katia Sycara},
title = {A decentralized approach to space deconfliction},
booktitle = {Proceedings of 10th International Conference on Information Fusion (FUSION '07)},
year = {2007},
month = {July},
pages = {1617 - 1624},
}
Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.