What Is New in RVO2 Library

Local Collision Avoidance

The main difference between RVO2 Library and RVO Library 1.x is the local collision avoidance technique used. RVO2 Library uses Optimal Reciprocal Collision Avoidance (ORCA), whereas RVO Library 1.x uses Reciprocal Velocity Obstacles (RVO). For legacy reasons, and since both techniques are based on the same principles of reciprocal collision avoidance and relative velocity, we did not change the name of the library.

A major consequence of the change of local collision avoidance technique is that the simulation has become much faster in RVO2 Library. ORCA defines velocity constraints with respect to other agents as half-planes, and an optimal velocity is efficiently found using (two-dimensional) linear programming. In contrast, RVO Library 1.x uses random sampling to find a good velocity. Also, the behavior of the agents is smoother in RVO2 Library. It is proven mathematically that ORCA lets the velocity of agents evolve continuously over time, whereas RVO Library 1.x occasionally showed oscillations and reciprocal dances. Furthermore, ORCA provides stronger guarantees with respect to collision avoidance.

Global Path Planning

Local collision avoidance as provided by RVO2 Library should in principle be accompanied by global path planning that determines the preferred velocity of each agent in each time step of the simulation. RVO Library 1.x has a built-in roadmap infrastructure to guide agents around obstacles to fixed goals. However, besides roadmaps, other techniques for global planning, such as navigation fields, cell decompositions, etc. exist. Therefore, RVO2 Library does not provide global planning infrastructure anymore. Instead, it is the responsibility of the external application to set the preferred velocity of each agent ahead of each time step of the simulation. This makes the library more flexible to use in varying application domains. In one of the example applications that comes with RVO2 Library, we show how a roadmap similar to RVO Library 1.x is used externally to guide the global navigation of the agents. As a consequence of this change, RVO2 Library does not have a concept of a "goal position" or "preferred speed" for each agent, but only relies on the preferred velocities of the agents set by the external application.

Structure of RVO2 Library

The structure of RVO2 Library is similar to that of RVO Library 1.x. Users familiar with RVO Library 1.x should find little trouble in using RVO2 Library. However, RVO2 Library is not backwards compatible with RVO Library 1.x. The main reason for this is that the ORCA technique requires different (and fewer) parameters to be set than RVO. Also, the way obstacles are represented is different. In RVO Library 1.x, obstacles are represented by an arbitrary collection of line segments. In RVO2 Library, obstacles are non-intersecting polygons, specified by lists of vertices in counterclockwise order. Further, in RVO Library 1.x agents cannot be added to the simulation after the simulation is initialized. In RVO2 Library this restriction is removed. Obstacles still need to be processed before the simulation starts, though. Lastly, in RVO Library 1.x an instance of the simulator is a singleton. This restriction is removed in RVO2 Library.

Smaller Changes

With RVO2 Library, we have adopted the philosophy that anything that is not part of the core local collision avoidance technique is to be stripped from the library. Therefore, besides the roadmap infrastructure, we have also removed acceleration constraints of agents, orientation of agents, and the unused "class" of agents. Each of these can be implemented external of the library if needed. We did maintain a kd-tree infrastructure for efficiently finding other agents and obstacles nearby each agent.

Also, RVO2 Library allows accessing information about the simulation, such as the neighbors and the collision-avoidance constraints of each agent, that is hidden from the user in RVO Library 1.x.