Efficient Reciprocal Collision Avoidance between Heterogeneous Agents Using CTMAT

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 lowdimensional 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.

Authors

• Yuexin Ma ShanghaiTech University
• Dinesh Manocha University of Maryland, College Park
• Wenping Wang Department of Computer Science, The University of Hong Kong, China Texas A&M University, USA

Keywords

• multi-agent simulation
• heterogeneous agents
• collision avoidance
• autonomous vehicles
• traffic simulation