| 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:

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.

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