Decentralized probabilistic multi-robot collision avoidance using buffered uncertainty-aware Voronoi cells

Hai Zhu*, Bruno Brito, Javier Alonso-Mora

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)
26 Downloads (Pure)


In this paper, we present a decentralized and communication-free collision avoidance approach for multi-robot systems that accounts for both robot localization and sensing uncertainties. The approach relies on the computation of an uncertainty-aware safe region for each robot to navigate among other robots and static obstacles in the environment, under the assumption of Gaussian-distributed uncertainty. In particular, at each time step, we construct a chance-constrained buffered uncertainty-aware Voronoi cell (B-UAVC) for each robot given a specified collision probability threshold. Probabilistic collision avoidance is achieved by constraining the motion of each robot to be within its corresponding B-UAVC, i.e. the collision probability between the robots and obstacles remains below the specified threshold. The proposed approach is decentralized, communication-free, scalable with the number of robots and robust to robots’ localization and sensing uncertainties. We applied the approach to single-integrator, double-integrator, differential-drive robots, and robots with general nonlinear dynamics. Extensive simulations and experiments with a team of ground vehicles, quadrotors, and heterogeneous robot teams are performed to analyze and validate the proposed approach.

Original languageEnglish
Pages (from-to)401-420
JournalAutonomous Robots
Issue number2
Publication statusPublished - 2022

Bibliographical note

Green Open Access added to TU Delft Institutional Repository 'You share, we take care!' - Taverne project
Otherwise as indicated in the copyright section: the publisher is the copyright holder of this work and the author uses the Dutch legislation to make this work public.


  • Collision avoidance
  • Motion planning
  • Multi-robot systems
  • Planning under uncertainty


Dive into the research topics of 'Decentralized probabilistic multi-robot collision avoidance using buffered uncertainty-aware Voronoi cells'. Together they form a unique fingerprint.

Cite this