research-article

ClearPath: highly parallel collision avoidance for multi-agent simulation

Authors:

Stephen. J. Guy,

Jatin Chhugani,

Nadathur Satish,

Dinesh Manocha,

Pradeep DubeyAuthors Info & Claims

SCA '09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

Pages 177 - 187

https://doi.org/10.1145/1599470.1599494

Published: 01 August 2009 Publication History

Abstract

We present a new local collision avoidance algorithm between multiple agents for real-time simulations. Our approach extends the notion of velocity obstacles from robotics and formulates the conditions for collision free navigation as a quadratic optimization problem. We use a discrete optimization method to efficiently compute the motion of each agent. This resulting algorithm can be parallelized by exploiting data-parallelism and thread-level parallelism. The overall approach, ClearPath, is general and can robustly handle dense scenarios with tens or hundreds of thousands of heterogeneous agents in a few milli-seconds. As compared to prior collision avoidance algorithms, we observe more than an order of magnitude performance improvement.

References

[1]

{BGLM09} Berg J., Guy S. J., Lin M., Manocha D.: Reciprocal n-body collision avoidance. In International Symposium on Robotics Research (To Appear) (2009), Springer.

[2]

{Ble09} Bleiweiss A.: Multi agent navigation on gpu. http://developer.download.nvidia.com/presentations/2009/GDC/MultiAgentGPU.pdf, 2009.

[3]

{BLM08} Berg J., Lin M., Manocha D.: Reciprocal velocity obstacles for realtime multi-agent navigation. Proc. of IEEE Conference on Robotics and Automation (2008), 1928--1935.

[4]

{BPS*08} Berg J., Patil S., Sewall J., Manocha D., Lin M.: Interactive navigation of individual agents in crowded environments. Proc. of ACM Symposium on I3D (2008), 139--147.

Digital Library

[5]

{Cam97} Cameron S.: Enhancing GJK: Computing minimum and penetration distance between convex polyhedra. IEEE International Conf. on Robotics and Automation (1997), 3112--3117.

[6]

{CM04} Courty N., Musse S.: FastCrowd: Real-Time Simulation and Interaction with Large Crowds based on Graphics Hardware. Tech. rep., INRIA, March 2004.

[7]

{Eri04} Ericson C.: Real-Time Collision Detection. Morgan Kaufmann, 2004.

[8]

{FN06} Foudil C., Noureddine D.: Collision avoidance in crowd simulation with priority rules. European Journal of Scientific Research 15, 1 (2006).

[9]

{FS98} Fiorini P., Shiller Z.: Motion planning in dynamic environments using velocity obstacles. International Journal on Robotics Research 17, 7 (1998), 760--772.

[10]

{FSL07} Fulgenzi C., Spalanzani A., Laugier C.: Dynamic obstacle avoidance in uncertain environment combining PVOs and occupancy grid. In ICRA (2007), pp. 1610--1616.

[11]

{FT87} Faverjon B., Tournassoud P.: A local based approach for path planning of manipulators with a high number of degrees of freedom. ICRA (1987), 1152--1159.

[12]

{HBJW05} Helbing D., Buzna L., Johansson A., Werner T.: Self-organized pedestrian crowd dynamics and design solutions: Experiments, simulations and design solutions. Transportation Science 39, 1 (2005), 1--24.

Digital Library

[13]

{Kan00} Kann V.: Maximum quadratic prog. www.nada.kth.se/~viggo/wwwcompendium/node203.html, 2000.

[14]

{KLK*08} Kanehiro F., Lamiraun F., Kanoun O., Yoshida E., Laumond H.: A local collision avoidance method for non-strictly convex polyhedral. In Robotics: Science and Systems (2008).

[15]

{KP07} Kluge B., Prassler E.: Reflective navigation: Individual behaviors and group behaviors. In Proc. of International Conf. on Robotics and Automation (2007), pp. 4172--4177.

[16]

{KSHF09} Kapadia M., Singh S., Hewlett W., Faloutsos P.: Egocentric affordance fields in pedestrian steering. In I3D '09 (2009), ACM, pp. 215--223.

Digital Library

[17]

{LaV06} LaValle S. M.: Planning Algorithms. Cambridge University Press (also at http://msl.cs.uiuc.edu/planning/), 2006.

Digital Library

[18]

{LD04} Lamarche F., Donikian S.: Crowd of virtual humans: a new approach for real-time navigation in complex and structured environments. CG Forum 23, 3 (2004), 509--518.

[19]

{Lin93} Lin M.: Efficient Collision Detection for Animation and Robotics. PhD thesis, U.C. Berkeley, December 1993.

Digital Library

[20]

{MKH90} Mohr E., Kranz D. A., Halstead Jr. R. H.: Lazy task creation: a technique for increasing the granularity of parallel programs. In Proc. of the ACM conference on LISP and functional programming (1990).

Digital Library

[21]

{MT97} Musse S. R., Thalmann D.: A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation (1997), 39--51.

[22]

{PAB08} Pelechano N., Allbeck J., Badler N.: Virtual Crowds: Methods, Simulation, and Control. M.C. Publ., 2008.

[23]

{PPD07} Paris S., Pettre J., Donikian S.: Pedestrian reactive navigation for crowd simulation: a predictive approac. Computer Graphics Forum 26 (2007), 665--674.

[24]

{QMHz03} Quinn M. J., Metoyer R. A., Hunterzaworski K.: Parallel implementation of the social forces model. In in Proceedings of the Second International Conference in Pedestrian and Evacuation Dynamics (2003), pp. 63--74.

[25]

{Rey87} Reynolds C. W.: Flocks, herds and schools: A distributed behavioral model. ACM SIGGRAPH Computer Graphics 21 (1987), 25--34.

Digital Library

[26]

{Rey99} Reynolds C. W.: Steering behaviors for autonomous characters. Game Developers Conference (1999).

[27]

{Rey06} Reynolds C.: Big fast crowds on ps3. In Sandbox '06: Proceedings of the 2006 ACM SIGGRAPH symposium on Videogames (2006), ACM, pp. 113--121.

Digital Library

[28]

{SAC*07} Sud A., Andersen E., Curtis S., Lin M., Manocha D.: Real-time path planning for virtual agents in dynamic environments. Proc. of IEEE VR (2007), 91--98.

Digital Library

[29]

{SCS*08} Seiler L., Carmean D., Sprangle E., Forsyth T., et al.: Larrabee: A Many-Core x86 Architecture for Visual Computing. ACM Trans. Graph. 27, 3 (2008), 1--15.

Digital Library

[30]

{SGA*07} Sud A., Gayle R., Andersen E., Guy S., Lin M., Manocha D.: Real-time navigation of independent agents using adaptive roadmaps. Proc. of ACM VRST (2007), 99--106.

Digital Library

[31]

{SLS01} Shiller Z., Large F., Sekhavat S.: Motion planning in dynamic environments: obstacles moving along arbitrary trajectories. In ICRA (2001), vol. 4, pp. 3716--3721.

[32]

{SNH01} Sugiyama Y., Nakayama A., Hasebe K.: 2-dimensional optimal velocity models for granular flows. In Pedestrian and Evacuation Dynamics (2001), pp. 155--160.

[33]

{TCP06} Treuille A., Cooper S., Popovic Z.: Continuum crowds. Proc. of ACM SIGGRAPH (2006), 1160--1168.

Digital Library

[34]

{TOCD06} Thalmann D., O'Sullivan C., Ciechomski P., Dobbyn S.: Populating Virtual Environments with Crowds. Eurographics Tutorial Notes, 2006.

Digital Library

[35]

{vdBLM08} van den Berg J., Lin M., Manocha D.: Reciprocal velocity obstacles for realtime multi-agent navigation. Proc. of IEEE Conference on Robotics and Automation (2008).

[36]

{YMMT08} Yersin B., Maïm J., Morini F., Thalmann D.: Real-time crowd motion planning. The Visual Computer 24 (Oct 2008), 859--870.

Digital Library

[37]

{YT07} Yu Q., Terzopoulos D.: A decision network framework for the behavioral animation of virtual humans. In Proc. of the Symposium on Computer Animation (2007), pp. 119--128.

Digital Library

Cited By

Talukdar BZhang YWeiss T(2024)Learning Crowd Motion Dynamics with CrowdsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36513027:1(1-17)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3651302
Yu BYe JOu D(2024)Consideration of Human Vision in Crowd SimulationsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.340177425:10(13364-13374)Online publication date: Oct-2024
https://doi.org/10.1109/TITS.2024.3401774
Lin XHuang YChen FEnglot B(2024)Decentralized Multi-Robot Navigation for Autonomous Surface Vehicles with Distributional Reinforcement Learning2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611668(8327-8333)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611668
Show More Cited By

Recommendations

A biologically inspired method for robot navigation in a cluttered environment

The problem of wheeled mobile robot (WMR) navigation toward an unknown target in a cluttered environment has been considered. The biologically inspired navigation algorithm is the equiangular navigation guidance (ENG) law combined with a local obstacle ...
Design and implementation of a navigation system for autonomous mobile robots

In this paper, a navigation system for autonomous mobile robots is proposed. Our navigation system is a hybrid of behaviour-based and model-based navigation systems. In our system, a behaviour-based subsystem is in charge of low-level reactive actions, ...
Navigation of mobile robots in the presence of obstacles

Robot navigation is one of the basic problems in robotics. In general, the robot navigation algorithms are classified as global or local, depending on surrounding environment. In global navigation, the environment surrounding the robot is known and the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SCA '09: Proceedings of the 2009 ACM SIGGRAPH/Eurographics Symposium on Computer Animation

August 2009

258 pages

ISBN:9781605586106

DOI:10.1145/1599470

Conference Chairs:
Bobby Bodenheimer
Vanderbilt University
,
Rasmus Tamstorf
Walt Disney Animation Studios
,
Editors:
Dieter Fellner
TU Darmstadt & Fraunhofer IGD, Germany
,
Stephen Spencer
The University of Washington
,
Program Chairs:
Eitan Grinspun
Columbia University
,
Jessica Hodgins
Carnegie Mellon University

Copyright © 2009 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGGRAPH: ACM Special Interest Group on Computer Graphics and Interactive Techniques
EUROGRAPHICS: The European Association for Computer Graphics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 August 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

SCA '09

Sponsor:

SIGGRAPH
EUROGRAPHICS

SCA '09: The ACM SIGGRAPH / Eurographics Symposium on Computer Animation

August 1 - 2, 2009

Louisiana, New Orleans

Acceptance Rates

Overall Acceptance Rate 183 of 487 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

209
Total Citations
View Citations
1,808
Total Downloads

Downloads (Last 12 months)92
Downloads (Last 6 weeks)14

Reflects downloads up to 12 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Talukdar BZhang YWeiss T(2024)Learning Crowd Motion Dynamics with CrowdsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/36513027:1(1-17)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3651302
Yu BYe JOu D(2024)Consideration of Human Vision in Crowd SimulationsIEEE Transactions on Intelligent Transportation Systems10.1109/TITS.2024.340177425:10(13364-13374)Online publication date: Oct-2024
https://doi.org/10.1109/TITS.2024.3401774
Lin XHuang YChen FEnglot B(2024)Decentralized Multi-Robot Navigation for Autonomous Surface Vehicles with Distributional Reinforcement Learning2024 IEEE International Conference on Robotics and Automation (ICRA)10.1109/ICRA57147.2024.10611668(8327-8333)Online publication date: 13-May-2024
https://doi.org/10.1109/ICRA57147.2024.10611668
Dang HGaudou BVerstaevel N(2024)A literature review of dense crowd simulationSimulation Modelling Practice and Theory10.1016/j.simpat.2024.102955134(102955)Online publication date: Jul-2024
https://doi.org/10.1016/j.simpat.2024.102955
Vesentini FMuradore RFiorini P(2024)A survey on Velocity Obstacle paradigmRobotics and Autonomous Systems10.1016/j.robot.2024.104645174(104645)Online publication date: Apr-2024
https://doi.org/10.1016/j.robot.2024.104645
Piccinelli NVesentini FMuradore R(2023)MPC Based Motion Planning For Mobile Robots Using Velocity Obstacle Paradigm2023 European Control Conference (ECC)10.23919/ECC57647.2023.10178219(1-6)Online publication date: 13-Jun-2023
https://doi.org/10.23919/ECC57647.2023.10178219
Weiss T(2023)Fast Position-based Multi-Agent Group DynamicsProceedings of the ACM on Computer Graphics and Interactive Techniques10.1145/35855076:1(1-15)Online publication date: 16-May-2023
https://dl.acm.org/doi/10.1145/3585507
Mavrogiannis CBaldini FWang AZhao DTrautman PSteinfeld AOh J(2023)Core Challenges of Social Robot Navigation: A SurveyACM Transactions on Human-Robot Interaction10.1145/358374112:3(1-39)Online publication date: 24-Apr-2023
https://dl.acm.org/doi/10.1145/3583741
Xue JZhang MYin H(2023)A Personality-based Model of Emotional Contagion and Control in Crowd Queuing SimulationsACM Transactions on Modeling and Computer Simulation10.1145/357758933:1-2(1-23)Online publication date: 28-Feb-2023
https://dl.acm.org/doi/10.1145/3577589
Mathew CBenes BAliaga D(2023)Sketching Vocabulary for Crowd MotionComputer Graphics Forum10.1111/cgf.1462941:8(119-130)Online publication date: 20-Mar-2023
https://doi.org/10.1111/cgf.14629
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents