CBF-inspired Weighted Buffered Voronoi Cells for Distributed Multi-agent Collision Avoidance

Abstract

In this paper, we introduce Risk-aware Weighted Buffered Voronoi tessellation, a variant of the Generalized Voronoi tessellation. Inherited from traditional Voronoi tessellation, safety guarantees in terms of collision avoidance are provided by partitioning the joint state space of the multi-agent system into individual cells to constrain each individual agent’s motion in a distributed manner. Different from existing Weighted Buffered Voronoi tessellations, our CBF-inspired Weighted Buffered Voronoi Cell (CBF-inspired WBVC) partition not only takes agent positional information into account, but also their motion information when determining the cell boundaries. Cell partitioning is conducted based on risk evaluation of the possibility to collide, in which Control Barrier Function is leveraged to capture the behavior of how the agents approach their safety boundaries in a model-based way. In other words, for any point in the joint state space, the cell assignment criteria are not solely based on how close it is to each agent, but on how much risk it experiences generated by each agent. With our Control Barrier Functioninspired risk measurement, the weight of CBF-inspired WBVC is dynamically updated and biases the boundary towards the agents exposed to higher accumulated risk caused by interagent interactions. In this way, by taking the neighbors of
the neighbors into account with aggregated risk evaluation, agents facing higher risk from multi-agent interaction can have larger relative cells compared to agents exposed to lower risk. With our proposed CBF-inspired WBVC, multi-agent systems are able to perform tasks in a risk-aware manner with the enhanced knowledge of risk provided by the CBF-inspired risk evaluation framework, but without requiring the use of a CBFbased controller. It is therefore generally applicable to various agent controllers while providing safety guarantees.