hongyi-zhou/orca

An attempt at a simple implementation of the ORCA algorithm

Optimal Reciprocal Collision Avoidance

The Optimal Reciprocal Collision Avoidance (ORCA) algorithm, formulated at the University of North Carolina [1], is a fully decentralized collision avoidance algorithm designed with key principles in mind:

• Agents compute their velocities in real-time and can react to a dynamic environment
• Each agent runs the algorithm locally and independently, and does not need to communicate with other agents or a central coordinating unit
• The algorithm is optimal, in the sense that every agent deviates as little as possible from its "preferred" route to avoid collisions
• The algorithm guarantees collision-free navigation, under certain conditions

The aim of this project is to build a simple C++ implementation of the ORCA algorithm, based on the original formulation [1] as well as the algorithm for solving the Linear Program, as described in Computational Geometry, Algorithms and Applications, Third Edition [2].

References

[1] van den Berg J., Guy S.J., Lin M., Manocha D. (2011) Reciprocal n-Body Collision Avoidance. In: Pradalier C., Siegwart R., Hirzinger G. (eds) Robotics Research. Springer Tracts in Advanced Robotics, vol 70. Springer, Berlin, Heidelberg

[2] M. de Berg, O. Cheong, M. van Kreveld, M. Overmars. Computational Geometry: Algorithms and Applications. Springer-Verlag, 2008.