Decentralized Safe Navigation for Multi-agent Systems via Risk-aware Weighted Buffered Voronoi Cells

Abstract

In this paper, we propose Risk-aware Weighted Buffered Voronoi tessellation, a variant of Generalized Voronoi tessellation, for decentralized multi-agent collision-free navigation. Inherited from
the traditional Voronoi tessellation, a safety guarantee in terms of inter-robot collision avoidance is achieved by partitioning the joint state space of the multi-agent system into individual cells that
constrain each individual agent’s motion in a distributed manner. Different from many existing Voronoi tessellations-based collision avoidance approaches, our Risk-aware Weighted Buffered Voronoi
Cell (Risk-aware WBVC) partition not only takes agent positional information into account, but also the motion information when determining the cell boundaries between pairwise robots. Our riskaware WBVC relies on the novel use of Control Barrier Functions (CBF) as a measure of risk evaluation that captures to what extent the safety constraints are satisfied between pairwise robots. With that, the cell boundaries of risk-aware WBVC are determined by (1) the varying levels of relative efforts between pairwise agents to respond to potential collisions, and (2) the accumulated risk each agent experiences that is caused by the surrounding agents. This allows for an adaptive constrained space partition among robots that balances between individual’s efforts in respecting the safety constraints and the overall threats due to other agents in the environment, e.g. an aggressive robot moving with higher speed requires a relatively larger space for responding to potential collisions, and a less-threatened robot may be expected to yield and make more room for those exposed to higher risk. Rigorous proofs of formal safety guarantees are provided and simulations are demonstrated on up to 16 robots to show the effectiveness of our method.