Reciprocally-Rotating Velocity Obstacles (RRVO)

Modern multi-agent systems frequently use high-level planners to extract basic paths for agents, and then rely on local collision avoidance to ensure that the agents reach their destinations without colliding with one another or dynamic obstacles. We introduce Reciprocally-Rotating Velocity Obstacles (RRVO), an extension to Optimal Reciprocal Collision Avoidance (ORCA), which is a state-of-the-art local collision avoidance technique.

RRVO allows agents to actively rotate in order to avoid collision with each other. Whereas before, agents were generally assumed to be represented as circles, RRVO relaxes this assumption to allow for any convex polygon. The resulting method allows one to more accurately model their agents, and permits more realistic motion in the form of rotation. RRVO has application in any multi-agent simulation, including evacuation, pursuit-evasion, urban planning, and more.

The Reciprocal Velocity Obstacles approach works well in general, but can lead to deadlock when sufficiently large agents with opposing goals meet. When agents are modeled as polygons other than circles, though, deadlocks become even more common. Reciprocally-Rotating Velocity Obstacles overcomes the deadlocking problem by permitting agents to rotate. Such rotation results in more asymmetry, which is a crucial condition for choosing deadlock-resolving velocities.

Algorithm Overview

Reciprocally-Rotating Velocity Obstacles (RRVO) works by considering agents as convex polygons that may rotate. Should those agents rotate 360 degrees, their swept volumes would form circles. ORCA only considers agents as these circles. Such a consideration may be overly conservative when agents are very close. Instead, agents employing RRVO only assume that neighboring agents rotate at most as much as themselves, until either the agent has reached its maximum rotation or has collided with a reciprocally-rotating neighbor. Such an assumption allows agents to intelligently choose orientations that are not only collision-free, but also maximize clearance from other agents.

Evaluation

Below we show a few examples of how RRVO overcomes the deadlocking problem faced by ORCA.

RRVO vs ORCA (Humanoid)

Scenario: Demonstration of how RRVO overcomes the shortfalls of ORCA. 50 agents are arranged in lines of 5. 25 agents on left side attempt to exchange positions with 25 agents on the right side. The agents are assumed to be humanoid. First, we show how the problem becomes very difficult for ORCA because it uses bounding circles (rendered as spheres) to represent the agents. Next, we show how, even when we change the representation of agents to be rectangular, ORCA still deadlocks. Finally, we show how RRVO allows agents to rotate, form lanes, and permit agents to reach their goals.

Antipodal Circle (Shape Study)

Scenario: We run Reciprocally-Rotating Velocity Obstacles (RRVO) for agents in the Antipodal Circle scenario, where agents must reach the diametric position on the circle from where they started. Agent shape is varied from a triangle to a 64gon (32gon shown in video). RRVO has excellent performance in all cases.

ORCA Shape Study

Scenario: We run Optimal Reciprocal Collision Avoidance (ORCA) for agents of varying polygon-type. As the shape of the agents approaches circular, the method performs better. However, performance is very poor for anything less than a circle.

RRVO Shape Study 2

Scenario: In this scenario, lines of agents must exchange positions with their horizontally-symmetric counterpart. We vary the shape of the agents from triangles to 32gons. Agents employ Reciprocally Rotation Velocity Obstacles (RRVO) to avoid collision. As agent shape approaches circular, performance actually worsens, because the rotations that RRVO enables agents to perform have less effect, whereas the area covered by each agent increases to make the problem more difficult.

ORCA Shape Study 2

Scenario: In this scenario, lines of agents must exchange positions with their horizontally-symmetric counterpart. We vary the shape of the agents from triangles to 32gons. Agents employ Optimal Reciprocal Collision Avoidance (ORCA) to avoid collision. As agent shape approaches circular, performance improves. However, increasing the side count of agents to more closely approximate a circle also results in a more difficult problem, as agents take up more area. ORCA fails to allow all agents to reach their goals.

1000 Agents Antipodal Circle

Scenario: 1000 rectangular agents attempt to reach their diametric position on a circle. This scenario demonstrates how RRVO works for even large groups of agents. Congestion initially forms in the center, but as the agents rotate and swirl, eventually it resolves itself and all agents reach their goals.

Animated Character Scenario

500 rectangular agents attempt to reach their diametric position on a circle shown with animated characters.

1000 Agents ORCA Antipodal Circle

Scenario: 1000 rectangular agents using ORCA attempt to reach their diametric position on a circle. This video is intended to be used for motion comparison against RRVO.

500 Agents Exchange (Lines)

Scenario: In this scenario, 500 agents on the left attempt to exchange positions with 500 agents on the right. The agents are arranged into 25 parallel lines of 20 agents on each side. Optimal Reciprocal Collision Avoidance (ORCA) results in a great deal of interference between agents as the two groups meet. We sped up the scenario 5x and yet the scenario still shows no signs of resolving. Next, we show Reciprocally-Rotating Velocity Obstacles for the same scenario. Lanes naturally form in the crowd as agents easily pass each other on the way to their goals. Not every agent reaches their goal, but for the most part the scenario is quickly completed.

Animated Character Scenario (Lines)

500 rectangular agents exchange positions shown with animated characters.

Reciprocally-Rotating Velocity Obstacles does result in more computation time overall, which means lower agent counts in a real-time system. However, the method is ripe for parallelism, which is an avenue we are currently exploring.

Publications

• Ngui, I. , McBeth, C. , Motes, J.D. , Morales, M. , & Amato, N.M. (2026). Scalable Multi-robot Motion Planning via Hierarchical Subproblem Expansion and Workspace Decomposition Refinement. arXiv
• McBeth, C. , Motes, J. , Ngui, I. , Morales, M. , & Amato, N.M. (2024). Scalable Multi-Robot Motion Planning Using Guidance-Informed Hypergraphs. ArXiv Preprint. arXiv
• Motes, J. , Chen, T. , Bretl, T. , Morales, M. , & Amato, N.M. (2023). Hypergraph-Based Multi-robot Task and Motion Planning. IEEE Transactions on Robotics (TRO) , 6(4) , 7001--7008. https://doi.org/10.1109/TRO.2023.3297011
• McBeth, C. , Motes, J. , Uwacu, D. , Morales, M. , & Amato, N.M. (2023). Scalable Multi-robot Motion Planning for Congested Environments With Topological Guidance. In IEEE Robotics and Automation Letters , 1-8. https://doi.org/10.1109/LRA.2023.3312980
• Lee, H. , Motes, J. , Morales, M. , & Amato, N.M. (2021). Parallel Hierarchical Composition Conflict-Based Search. IEEE/RSJ International Conference on Intelligent Robots and Systems , 6(4) , 7001--7008. https://doi.org/10.1109/LRA.2021.3096476.
• Solis, I. , Motes, J. , Sandström, R. , & Amato, N.M. (2021). Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search. IEEE Robotics and Automation Letters. https://doi.org/https://doi.org/10.1109/LRA.2021.3068910
• Motes, J. , Sandstrom, R. , Lee, H. , Thomas, S. , & Amato, N.M. (2020). Multi-Robot Task and Motion Planning with Subtask Dependencies. IEEE Robotics and Automation Letters (RA-L) , 5(2) , 3338--3345. https://doi.org/10.1109/LRA.2020.2976329
• Motes, J. , Sandstrom, R. , Adams, W. , Ogunyale, T. , Thomas, S. , & Amato, N.M. (2019). Interaction Templates for Multi-Robot Systems. IEEE Robotics and Automation Letters , 4(3) , 2926--2933. https://doi.org/10.1109/LRA.2019.2923386
• Giese, A. , Latypov, D. , & Amato, N.M. (2014). Reciprocally-Rotating Velocity Obstacles. 2014 IEEE International Conference on Robotics and Automation (ICRA) , 3234-3241. https://doi.org/10.1109/ICRA.2014.6907324
• Rodriguez, S. , Denny, J. , Burgos, J. , Mahadevan, A. , Manavi, K. , Murray, L. , Kodochygov, A. , Zourntos, T. , & Amato, A.N.M. (2011). Toward Realistic Pursuit-Evasion Using a Roadmap-Based Approach. IEEE International Conference on Robotics and Automation , 1738--1745. https://doi.org/10.1109/ICRA.2011.5980467
• Rodriguez, S. & Amato, N.M. (2010). Behavior-Based Evacuation Planning. IEEE International Conference on Robotics and Automation , 350--355. https://doi.org/10.1109/ROBOT.2010.5509502
• Bayazıt, O.B. , Lien, J. , & Amato, N.M. (2005). Swarming Behavior Using Probabilistic Roadmap Techniques. Lecture Notes in Computer Science , 3342 , 112--125. https://doi.org/10.1007/978-3-540-30552-1_10
• Walter, J.E. , Brooks, M.E. , Little, D.F. , & Amato, N.M. (2004). Enveloping multi-pocket obstacles with hexagonal metamorphic robots. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA) , 3 , 2204-2209 Vol.3. https://doi.org/10.1109/ROBOT.2004.1307389
• Lien, J. , Bayazit, O.B. , Sowell, R.T. , Rodriguez, S. , & Amato, N.M. (2004). Shepherding Behaviors. In Proc. IEEE Int. Conf. Robot. Autom. (ICRA) , 4 , 4159-4164 Vol.4. https://doi.org/10.1109/ROBOT.2004.1308924
• Walter, J.E. , Brooks, M.E. , Little, D.F. , & Amato, N.M. (2003). Enveloping Obstacles with Hexagonal Metamorphic Robots. Proc. IEEE Int. Conf. Robot. Autom. (ICRA) , 1 , 741-748 vol.1. https://doi.org/10.1109/ROBOT.2003.1241682
• Bayazit, O.B. , Lien, J. , & Amato, N.M. (2002). Better Group Behaviors Using Rule-Based Roadmaps. In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR) , 7 , 95-111. https://doi.org/10.1007/978-3-540-45058-0_7