Real-time reciprocal collision avoidance with elliptical agents
Andrew Best, Sahil Narang, Dinesh Manocha
Abstract
We present a novel algorithm for real-time collision-free navigation between elliptical agents. Each robot or agent is represented using a tight-fitting 2D ellipse in the plane. We extend the reciprocal velocity obstacle formulation by using conservative linear approximations of ellipses and derive sufficient conditions for collision-free motion based on low-dimensional linear programming. We use precomputed Minkowski Sum approximations for real-time and conservative collision avoidance in large multi-agent environments. Finally, we present efficient techniques to update the orientation to compute collision-free trajectories. Our algorithm can handle thousands of elliptical agents in real-time on a single core and provides significant speedups over prior algorithms for elliptical agents. We compare the runtime performance and behavior with circular agents on different benchmarks.
BibTeX
@inproceedings{icra2016_realtimereciproc,
title = {Real-time reciprocal collision avoidance with elliptical agents},
author = {Andrew Best and Sahil Narang and Dinesh Manocha},
booktitle = {ICRA 2016},
year = {2016}
}