| Algorithms & Applcations Group | Home | Research | Publications | People | Resources | News
Algorithms & Applications Group
Reciprocally-Rotating Velocity Obstacles

Project Personnel:Nancy Amato

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.

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.

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

Examples:
 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. Download 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. Download 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. Download 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. Download 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. Download 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. Download Animated Character Scenario: 500 rectangular agents attempt to reach their diametric position on a circle shown with aniamted characters. Download 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 Download 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. Download Animated Character Scenario: 500 rectangular agents exchange positions shown with aniamted characters. Download

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.

Interaction Templates for Multi-Agent Systems, James Motes, Read Sandstrom, William Adams, Tobi Ogunyale, Shawna Thomas, Nancy M. Amato, Technical Report, TR18-002, Parasol Laboratory, Department of Computer Science, Texas A&M University, Jul 2018.
Technical Report(pdf, abstract)

Reciprocally-Rotating Velocity Obstacles, Andrew Giese, Daniel Latypov, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. to appear, Hong Kong, China, Jun 2014. Also, Technical Report, TR13-009, Parasol Laboratory, Department of Computer Science, Texas A&M University, College Station, TX U.S.A., Oct 2013.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Reciprocally-Rotating Velocity Obstacles, Andrew Giese, Masters Thesis, Department of Computer Science and Engineering, Texas A&M University, College Station, USA, May 2014.
Masters Thesis(ps, pdf, abstract)

Multi-Robot Caravanning, Jory Denny, Andrew Giese, Aditya Mahadevan, Arnaud Marfaing, Rachel Glockenmeier, Colton Revia, Samuel Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 5722 - 5729, Tokyo, Japan, Nov 2013.
Proceedings(pdf, abstract)

Optimizing Aspects of Pedestrian Traffic in Building Designs, Samuel Rodriguez, Yinghua Zhang, Nicholas Gans, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), Nov 2013.
Proceedings(pdf, abstract)

Improving Aggregate Behavior in Parking Lots with Appropriate Local Maneuvers, Samuel Rodriguez, Andrew Giese, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), Nov 2013.
Proceedings(pdf, abstract)

Environmental Effect on Egress Simulation, Samuel Rodriguez, Andrew Giese, Nancy M. Amato, Saeid Zarrinmehr, Firas Al-Douri, Mark Clayton, In Proc. of the 5th Intern. Conf. on Motion in Games (MIG), 2012, in Lecture Notes in Computer Science (LNCS), pp. to appear, Rennes, Brittany, France, Nov 2012.
Proceedings(ps, pdf, abstract)

A Sampling-Based Approach to Probabilistic Pursuit Evasion, Aditya Mahadevan, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 3192 - 3199, St. Paul, Minnesota, USA, May 2012.
Proceedings(pdf, abstract)

Roadmap-Based Techniques for Modeling Group Behaviors in Multi-Agent Systems, Samuel Rodriguez, Ph.D. Thesis, Department of Computer Science and Engineering, Texas A&M University, Jan 2012.
Ph.D. Thesis(ps, pdf, abstract)

Roadmap-Based Level Clearing of Buildings, Samuel Rodriguez, Nancy M. Amato, In Proc. of the 4th Intern. Conf. on Motion in Games (MIG), 2011, in Lecture Notes in Computer Science (LNCS), pp. 340-352, Edinburgh, UK, Oct 2011.
Proceedings(ps, pdf, abstract)

Toward Realistic Pursuit-Evasion Using a Roadmap-Based Approach, Samuel Rodriguez, Jory Denny, Juan Burgos, Aditya Mahadevan, Kasra Manavi, Luke Murray, Anton Kodochygov, Takis Zourntos, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 1738-1745, May 2011.
Proceedings(ps, pdf, abstract)

Roadmap-Based Pursuit-Evasion in 3D Structures, Samuel Rodriguez, Jory Denny, Aditya Mahadevan, Jeremy (Cong-Trung) Vu, Juan Burgos, Takis Zourntos, Nancy M. Amato, In Proc. of 24th Intern. Conf. on Computer Animation and Social Agents (CASA), 2011, in Transactions on Edutainment, pp. to appear, May 2011.
Proceedings(ps, pdf, abstract)

Utilizing Roadmaps in Evacuation Planning, Samuel Rodriguez, Nancy M. Amato, In Proc. of 24th Intern. Conf. on Computer Animation and Social Agents (CASA), 2011, in Intern. J. of Virtual Reality (IJVR), pp. 67-73, May 2011.
Proceedings(ps, pdf, abstract)

Toward Simulating Realistic Pursuit-Evasion Using a Roadmap-Based Approach, Samuel Rodriguez, Jory Denny, Takis Zourntos, Nancy M. Amato, In Proc. of the 3rd Intern. Conf. on Motion in Games (MIG), 2010, in Lecture Notes in Computer Science (LNCS), pp. 82-93, Nov 2010.
Proceedings(ps, pdf, abstract)

Behavior-Based Evacuation Planning, Sam Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 350-355, Anchorage, AK, May 2010.
Proceedings(ps, pdf, abstract)

A Framework for Planning Motion in Environments with Moving Obstacles, Sam Rodriguez, Jyh-Ming Lien, Nancy M. Amato, In Proc. IEEE Int. Conf. Intel. Rob. Syst. (IROS), pp. 3309-3314, Oct 2007.
Proceedings(ps, pdf, abstract)

Swarming Behavior Using Probabilistic Roadmap Techniques, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, Lecture Notes in Computer Science, 3342/2005:112-125, Jan 2005.
Journal(ps, pdf, abstract)

Shepherding Behaviors, Jyh-Ming Lien, O. Burchan Bayazit, Ross T. Sowell, Samuel Rodriguez, Nancy M. Amato, In Proc. IEEE Int. Conf. Robot. Autom. (ICRA), pp. 4159-4164, New Orleans, Apr 2004. Also, Technical Report, TR03-006, Parasol Laboratory, Department of Computer Science, Texas A&M University, Nov 2003.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Better Group Behaviors using Rule-Based Roadmaps, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), pp. 95-111, Nice, France, Dec 2002.
Proceedings(ps, pdf, abstract)

Roadmap-Based Flocking for Complex Environments, O. Burchan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Pacific Conf. on Computer Graphics and App. (PG), pp. 104-113, Beijing, China, Oct 2002. Also, Technical Report, TR02-003, Parasol Laboratory, Department of Computer Science, Texas A&M University, Apr 2002.
Proceedings(ps, pdf, abstract) Technical Report(ps, pdf, abstract)

Supported by NSF

Project Alumni:Andrew Giese,Daniel Latypov

 Parasol Home | Research | People | General info | Seminars | Resources   Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112  parasol-admin@cse.tamu.edu      Phone 979.458.0722     Fax 979.458.0718  Department of Computer Science and Engineering | Dwight Look College of Engineering | Texas A&M University     Privacy statement: Computer Science and Engineering Engineering TAMU Web Accessibility Policy and Law - Web Accessibility and Usability Standards  -   Contact Webmaster