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
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.
Related Publications
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, and Nancy M. Amato, IEEE International Conference on Robotics and Automation, Shanghai, China, May 2011. DOI: 10.1109/ICRA.2011.5980467 @inproceedings{rodriguez2011toward, In this work, we describe an approach for modeling and simulating group behaviors for pursuit-evasion that uses a graph-based representation of the environment and integrates multi-agent simulation with roadmap-based path planning. Our approach can be applied to more realistic scenarios than are typically studied in most previous work, including agents moving in 3D environments such as terrains, multi-story buildings, and dynamic environments. We also support more realistic three-dimensional visibility computations that allow evading agents to hide in crowds or behind hills. We demonstrate the utility of this approach on mobile robots and in simulation for a variety of scenarios including pursuit-evasion and tag on terrains, in multi-level buildings, and in crowds.
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published] BibTex
title={Toward realistic pursuit-evasion using a roadmap-based approach},
author={Rodriguez, Samuel and Denny, Jory and Burgos, Juan and Mahadevan, Aditya and Manavi, Kasra and Murray, Luke and Kodochygov, Anton and Zourntos, Takis and Amato, Nancy M},
booktitle={2011 IEEE International Conference on Robotics and Automation},
pages={1738--1745},
year={2011},
organization={IEEE}
}Abstract
Utilizing Roadmaps in Evacuation Planning, Samuel Rodriguez, Nancy M. Amato, The International Journal of Virtual Reality, Vol: 10, Issue: 1, Jan 2011. DOI: https://doi.org/10.20870/IJVR.2011.10.1.2804 @article{rodriguez2011utilizing, In this paper we describe utilization of roadmaps in a general evacuation planning system for complex 3D environments. The problem consists of heterogeneous groups of agents whose behaviors and properties affect usage of the environment when creating evacuation plans. This planning system includes behaviors for those agents evacuating and directors that may be guiding the agents to improve evacuation. One aspect we focus on is modeling different forms of direction and communication between agents.
Keywords: Motion Planning
Links : [Published] BibTex
title={Utilizing roadmaps in evacuation planning},
author={Rodriguez, Samuel and Amato, Nancy M},
journal={International Journal of Virtual Reality},
volume={10},
number={1},
pages={67--73},
year={2011}
}Abstract
Roadmap-Based Pursuit-Evasion in 3D Structures, Samuel Rodriguez, Jory Denny, Aditya Mahadevan, Jeremy Vu, Juan Burgos, Takis Zourntos, and Nancy M. Amato, International Conference on Computer Animation and Social Agents, Jan 2011. @inproceedings{rodriguez2011roadmap, We present an approach to the pursuit-evasion problem which is applicable to complex, multi-level environments. Studying each aspect of this problem in 3D structured environments is a distinct extension over many previous approaches. We also utilize our roadmap-based approach to multi-agent behavior when tracking agents of interest. Results are presented in three multi-level environments to highlight the search, pursuit and evasion components of the problem.
Keywords: Motion Planning
Links : [Published] BibTex
title={Roadmap-based pursuit-evasion in 3d structures},
author={Rodriguez, Samuel and Denny, Jory and Mahadevan, Aditya and Vu, Jeremy and Burgos, Juan and Zourntos, Takis and Amato, Nancy M},
booktitle={24th Intern. Conf. on Computer Animation and Social Agents (CASA)},
year={2011},
organization={Citeseer}
}Abstract
Toward Simulating Realistic Pursuit-Evasion Using a Roadmap-Based Approach, amuel Rodriguez, Jory Denny, Takis Zourntos, Nancy M. Amato, International Conference on Motion in Games, pp. 82-93, Utrecht, Netherlands, Nov 2010. DOI: https://doi.org/10.1007/978-3-642-16958-8_9 @inproceedings{rodriguez2010toward, In this work, we describe an approach for modeling and simulating group behaviors for pursuit-evasion that uses a graph-based representation of the environment and integrates multi-agent simulation with roadmap-based path planning. We demonstrate the utility of this approach for a variety of scenarios including pursuit-evasion on terrains, in multi-level buildings, and in crowds.
Keywords: Motion Planning
Links : [Published] BibTex
title={Toward simulating realistic pursuit-evasion using a roadmap-based approach},
author={Rodriguez, Samuel and Denny, Jory and Zourntos, Takis and Amato, Nancy M},
booktitle={International Conference on Motion in Games},
pages={82--93},
year={2010},
organization={Springer}
}Abstract
Behavior-Based Evacuation Planning, Samuel Rodriguez, Nancy M. Amato, IEEE International Conference on Robotics and Automation, May 2010. DOI: 10.1109/ROBOT.2010.5509502 @inproceedings{rodriguez2010behavior, In this work, we present a formulation of an evacuation planning problem that is inspired by motion planning and describe an integrated behavioral agent-based and roadmap-based motion planning approach to solve it. Our formulation allows users to test the effect on evacuation of a number of different environmental factors. One of our main focuses is to provide a mechanism to investigate how the interaction between agents influences the resulting evacuation plans. Specifically, we explore how various types of control provided by a set of directing agents effects the overall evacuation planning strategies of the evacuating agents.
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published] BibTex
title={Behavior-based evacuation planning},
author={Rodriguez, Samuel and Amato, Nancy M},
booktitle={2010 IEEE International Conference on Robotics and Automation},
pages={350--355},
year={2010},
organization={IEEE}
}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), Vol: 4, pp. 4159-4164, New Orleans, Louisiana, USA, Apr 2004. DOI: 10.1109/ROBOT.2004.1308924 @INPROCEEDINGS{1308924, Shepherding behaviors are a type of flocking behavior in which outside agents guide or control members of a flock. Shepherding behaviors can be found in various forms in nature. For example, herding, covering, patrolling and collecting are common types of shepherding behaviors. In this work, we investigate ways to simulate these types of behaviors. A shepherd uses roadmaps to steer the flock and to re-group separated flock members. This paper focuses on improving the shepherd's movements to gain better control of the flock's motion and use this improved control to demonstrate a wider variety of shepherding behaviors.
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published] BibTex
author={ {Jyh-Ming Lien} and O. B. {Bayazit} and R. T. {Sowell} and S. {Rodriguez} and N. M. {Amato}},
booktitle={IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA '04. 2004}, title={Shepherding behaviors},
year={2004},
volume={4},
number={},
pages={4159-4164 Vol.4},
doi={10.1109/ROBOT.2004.1308924}}Abstract
Better Group Behaviors Using Rule-Based Roadmaps, Osman Burçhan Bayazit, Jyh-Ming Lien, Nancy M. Amato, In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR), Vol: 7, pp. 95-111, Nice, France, Dec 2002. DOI: 10.1007/978-3-540-45058-0_7 @INPROCEEDINGS{10.1007/978-3-540-45058-0_7, While techniques exist for simulating group behaviors, these methods usually only provide simplistic navigation and planning capabilities. In this work, we explore the benefits of integrating roadmap-based path planning methods with flocking techniques. We show how group behaviors such as exploring can be facilitated by using dynamic roadmaps (e.g., modifying edge weights) as an implicit means of communication between flock members. Extending ideas from cognitive modeling, we embed behavior rules in individual flock members and in the roadmap. These behavior rules enable the flock members to modify their actions based on their current location and state. We propose new techniques for three distinct group behaviors: homing, exploring (covering and goal searching) and passing through narrow areas. Animations of these behaviors can be viewed at http://parasol.tamu.edu/dsmft.
Keywords: Group Behavior, Multi-Agent, Sampling-Based Motion Planning
Links : [Published] BibTex
author={Osman Burçhan {Bayazit}, Jyh-Ming {Lien}, Nancy M. {Amato}},
booktitle={In Proc. Int. Wkshp. on Alg. Found. of Rob. (WAFR)},
title={Better Group Behaviors Using Rule-Based Roadmaps},
year={2002}, volume={7}, number={}, pages={95-111},
doi={10.1007/978-3-540-45058-0_7}}Abstract