Efficient Reciprocal Collision Avoidance between Heterogeneous Agents Using CTMAT
This work addresses collision avoidance in multi-agent systems like road traffic scenarios, offering improved accuracy for heterogeneous agents, though it is incremental as it builds on existing reciprocal velocity obstacle formulations.
The paper tackles reciprocal collision avoidance for heterogeneous agents of varying shapes and sizes by introducing a CTMAT representation based on medial axis transform to compute tight bounding shapes, reducing the problem to low-dimensional linear programming. The algorithm achieves runtime performance comparable to prior methods while being less conservative and resulting in fewer false collisions.
We present a novel algorithm for reciprocal collision avoidance between heterogeneous agents of different shapes and sizes. We present a novel CTMAT representation based on medial axis transform to compute a tight fitting bounding shape for each agent. Each CTMAT is represented using tuples, which are composed of circular arcs and line segments. Based on the reciprocal velocity obstacle formulation, we reduce the problem to solving a low-dimensional linear programming between each pair of tuples belonging to adjacent agents. We precompute the Minkowski Sums of tuples to accelerate the runtime performance. Finally, we provide an efficient method to update the orientation of each agent in a local manner. We have implemented the algorithm and highlight its performance on benchmarks corresponding to road traffic scenarios and different vehicles. The overall runtime performance is comparable to prior multi-agent collision avoidance algorithms that use circular or elliptical agents. Our approach is less conservative and results in fewer false collisions.