Yuexin Ma1    Dinesh Manocha2    Wenping Wang1

The University of Hong Kong1, University of North Carolina at Chapel Hill2

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, which is less conservative and results in fewer false collisions. The overall runtime performance is comparable to prior multi-agent collision avoidance algorithms that use circular or elliptical agents. Based on CTMAT representation, we present a novel algorithm AutoRVO for computing collision-free navigation for heterogeneous road-agents such as cars, tricycles, bicycles, and pedestrians in dense traffic. Our approach currently assumes the positions, shapes, and velocities of all vehicles and pedestrians are known and computes smooth trajectories for each agent by taking into account the dynamic constraints. We describe an efficient optimization-based algorithm for each road-agent based on reciprocal velocity obstacles that takes into account kinematic and dynamic constraints. We evaluate the performance of AutoRVO in real-world dense traffic scenarios and highlight the benefits over prior reciprocal collision avoidance schemes.


Efficient Reciprocal Collision Avoidance between Heterogeneous Agents Using CTMATs [PDF]
Yuexin Ma, Dinesh Manocha and Wenping Wang.
AAMAS 2018

AutoRVO: Local Navigation with Dynamic Constraints in Dense Heterogeneous Traffic [PDF]
Yuexin Ma, Dinesh Manocha and Wenping Wang.
arXiv report: arXiv:1804.02915