More Web Proxy on the site http://driver.im/

Article

Real-time navigation of independent agents using adaptive roadmaps

Authors:

Dinesh ManochaAuthors Info & Claims

VRST '07: Proceedings of the 2007 ACM symposium on Virtual reality software and technology

Pages 99 - 106

https://doi.org/10.1145/1315184.1315201

Published: 05 November 2007 Publication History

Abstract

We present a novel algorithm for navigating a large number of independent agents in complex and dynamic environments. We compute adaptive roadmaps to perform global path planning for each agent simultaneously. We take into account dynamic obstacles and inter-agents interaction forces to continuously update the roadmap by using a physically-based agent dynamics simulator. We also introduce the notion of 'link bands' for resolving collisions among multiple agents. We present efficient techniques to compute the guiding path forces and perform lazy updates to the roadmap. In practice, our algorithm can perform real-time navigation of hundreds and thousands of human agents in indoor and outdoor scenes.

References

[1]

Ashida, K., Lee, S. J., Allbeck, J., Sun, H., Badler, N., and Metaxas, D. 2001. Pedestrians: Creating agent behaviors through statistical analysis of observation data. Proc. Computer Animation.

[2]

Bayazit, O. B., Lien, J.-M., and Amato, N. M. 2002. Better group behaviors in complex environments with global roadmaps. Int. Conf. on the Sim. and Syn. of Living Sys. (Alife).

Digital Library

[3]

Bon, G. L. 1895. The Crowd: A Study of the Popular Mind. Reprint available from Dover Publications.

[4]

Cordeiro, O. C., Braun, A., Silveria, C. B., Musse, S. R., and Caval-heiro, G. G. 2005. Concurrency on social forces simulation model. First International Workshop on Crowd Simulation.

[5]

Funge, J., Tu, X., and Terzopoulos, D. 1999. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. Proc. of ACM SIGGRAPH.

Digital Library

[6]

Garaerts, R., and Overmars, M. H. 2007. The corridor map method: Real-time high-quality path planning. In ICRA, 1023--1028.

[7]

Gayle, R., Lin, M., and Manocha, D. 2005. Constraint based motion planning of deformable robots. IEEE Conf. on Robotics and Automation.

[8]

Gayle, R., Sud, A., Lin, M., and Manocha, D. 2007. Reactive deformation roadmaps: Motion planning of multiple robots in dynamic environments. In Proc IEEE International Conference on Intelligent Robots and Systems.

[9]

Helbing, D., Buzna, L., and Werner, T. 2003. Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum 12.

Digital Library

[10]

Helbing, D., Buzna, L., Johansson, A., and Werner, T. 2005. Self-organized pedestrian crowd dynamics: experiments, simulations and design solutions. Transportation science, 1--24.

Digital Library

[11]

Hoogendoorn, S. P., Luding, S., Bovy, P., Schrecklenberg, M., and Wolf, D. 2000. Traffic and Granular Flow. Springer.

[12]

Jakobsen, T. 2001. Advanced character physics. In Game Developer's Conference.

[13]

Kamphuis, A., and Overmars, M. 2004. Finding paths for coherent groups using clearance. Proc. of ACM SIGGRAPH / Eurographics Symposium on Computer Animation.

Digital Library

[14]

Khatib, O. 1986. Real-time obstable avoidance for manipulators and mobile robots. IJRR 5, 1, 90--98.

Digital Library

[15]

Lamarche, F., and Donikian, S. 2004. Crowd of virtual humans: a new approach for real-time navigation in complex and structured environments. Computer Graphics Forum 23, 3 (Sept).

[16]

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

Digital Library

[17]

Lerner, A., Chrysanthou, Y., and Lischinski, D. 2007. Crowds by example. Computer Graphics Forum (Proceedings of Eurographics) 26, 3.

[18]

Li, Y., and Gupta, K. 2007. Motion planning of multiple agents in virtual environments on parallel architectures. In ICRA, 1009--1014.

[19]

Loscos, C., Marchal, D., and Meyer, A. 2003. Intuitive crowd behaviour in dense urban environments using local laws. Theory and Practice of Computer Graphics (TPCG'03).

Digital Library

[20]

MUSSE, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation.

[21]

Pelechano, N., O'Brien, K., Silverman, B., and Badler, N. 2005. Crowd simulation incorporating agent psychological models, roles and communication. First International Workshop on Crowd Simulation.

[22]

Pettre, J., Laumond, J.-P., and Thalmann, D. 2005. A navigation graph for real-time crowd animation on multilayered and uneven terrain. First International Workshop on Crowd Simulation.

[23]

Quinlan, S., and Khatib, O. 1993. Elastic bands: Connecting path planning and control. Proc. of IEEE Conf. on Robotics and Automation.

[24]

Reynolds, C. W. 1987. Flocks, herds, and schools: A distributed behavioral model. Comput. Graph. 21, 4, 25--34. Proc. SIGGRAPH '87.

Digital Library

[25]

Reynolds, C. 2006. Big fast crowds on ps3. In sandbox '06: Proceedings of the 2006 ACM SIGGRAPH symposium on Videogames, ACM Press, New York, NY, USA, 113--121.

Digital Library

[26]

Rodriguez, S., Lien, J.-M., and Amato, N. M. 2006. Planning motion in completely deformable environments. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (May).

[27]

Schreckkenberg, M., and Sharma, S. D. 2001. Pedestrian and Evacuation Dynamics. Springer.

[28]

Shao, W., and Terzopoulos, D. 2005. Autonomous pedestrians. In SCA '05: Proceedings of the 2005 ACM SIGGRAPH/Eurographics symposium on Computer animation, ACM Press, New York, NY, USA, 19--28.

Digital Library

[29]

Sud, A., Govindaraju, N., Gayle, R., and Manocha, D. 2006. Interactive 3d distance field computation using linear factorization. In Proc. ACM Symposium on Interactive 3D Graphics and Games, 117--124.

Digital Library

[30]

Sud, A., Andersen, E., Curtis, S., Lin, M., and Manocha, D. 2007. Realtime path planning for virtual agents in dynamic environments. Proc. of IEEE VR.

[31]

Sugiyama, Y., Nakayama, A., and Hasebe, K. 2001. 2-dimensional optimal velocity models for granular flows. In Pedestrian and Evacuation Dynamics, 155--160.

[32]

Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 (Sept).

[33]

Sung, M., Kovar, L., and Gleicher, M. 2005. Fast and accurate goal-directed motion synthesis for crowds. Proc. of SCA 2005, 291--300.

Digital Library

[34]

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

[35]

Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. Proc. of ACM SIGGRAPH.

Digital Library

[36]

Tu, X., and Terzopoulos, D. Artificial fishes: Physics, locomotion, perception, behavior. In Proceedings of SIGGRAPH '94, A. Glassner, Ed., 43--50.

Digital Library

[37]

Verlet, L 1967. Computer experiments on classical fluids. I. Thermodynamical properties of Lennard-Jones molecules. Phys. Rev., 159, 98--103.

[38]

Yang, Y., and Brock, O. 2006. Elastic roadmaps: Globally task-consistent motion for autonomous mobile manipulation. Proceedings of Robotics: Science and Systems (August).

[39]

Zucker, M., Kuffner, J., and Branicky, M. 2007. Multipartite rrts for rapid replanning in dynamic environments. Proc. IEEE Int. Conf. on Robotics and Automation.

Cited By

Wang XWang X(2024)Social Force Model-Based Video Anomaly Detection ApproachesAnomaly Detection in Video Surveillance10.1007/978-981-97-3023-0_11(273-286)Online publication date: 7-Aug-2024
https://doi.org/10.1007/978-981-97-3023-0_11
Löhner RAntil HGimenez JIdelsohn SOñate E(2022)A deterministic pathogen transmission model based on high-fidelity physicsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.114929401(114929)Online publication date: Nov-2022
https://doi.org/10.1016/j.cma.2022.114929
Torrens P(2022)Agent models of customer journeys on retail high streetsJournal of Economic Interaction and Coordination10.1007/s11403-022-00350-z18:1(87-128)Online publication date: 9-May-2022
https://doi.org/10.1007/s11403-022-00350-z
Show More Cited By

Recommendations

Real-time navigation of independent agents using adaptive roadmaps
SIGGRAPH '08: ACM SIGGRAPH 2008 classes

We present a novel algorithm for navigating a large number of independent agents in complex and dynamic environments. We compute adaptive roadmaps to perform global path planning for each agent simultaneously. We take into account dynamic obstacles and ...
Interactive Navigation of Heterogeneous Agents Using Adaptive Roadmaps

We present a novel algorithm for collision-free navigation of a large number of independent agents in complex and dynamic environments. We introduce adaptive roadmaps to perform global path planning for each agent simultaneously. Our algorithm takes ...
Real-time navigation using randomized kinodynamic planning with arrival time field

In this paper, we propose a novel path planning algorithm for a mobile robot in dynamic and cluttered environments with kinodynamic constraints. We compute the arrival time field as a bias which gives larger weights for shorter and safer paths toward a ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

VRST '07: Proceedings of the 2007 ACM symposium on Virtual reality software and technology

November 2007

259 pages

ISBN:9781595938633

DOI:10.1145/1315184

Conference Chairs:
Aditi Majumder
UC Irvine
,
Larry Hodges
UNC - Charlotte
,
Daniel Cohen-Or
Tel Aviv University
,
Editor:
Stephen N. Spencer
University of Washington

Copyright © 2007 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

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 November 2007

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

VRST07

Sponsor:

VRST07: The ACM Symposium on Virtual Reality Software and Technology

November 5 - 7, 2007

California, Newport Beach

Acceptance Rates

Overall Acceptance Rate 66 of 254 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

85
Total Citations
View Citations
789
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Wang XWang X(2024)Social Force Model-Based Video Anomaly Detection ApproachesAnomaly Detection in Video Surveillance10.1007/978-981-97-3023-0_11(273-286)Online publication date: 7-Aug-2024
https://doi.org/10.1007/978-981-97-3023-0_11
Löhner RAntil HGimenez JIdelsohn SOñate E(2022)A deterministic pathogen transmission model based on high-fidelity physicsComputer Methods in Applied Mechanics and Engineering10.1016/j.cma.2022.114929401(114929)Online publication date: Nov-2022
https://doi.org/10.1016/j.cma.2022.114929
Torrens P(2022)Agent models of customer journeys on retail high streetsJournal of Economic Interaction and Coordination10.1007/s11403-022-00350-z18:1(87-128)Online publication date: 9-May-2022
https://doi.org/10.1007/s11403-022-00350-z
Löhner RAntil HSrinivasan AIdelsohn SOñate E(2021)High-Fidelity Simulation of Pathogen Propagation, Transmission and Mitigation in the Built EnvironmentArchives of Computational Methods in Engineering10.1007/s11831-021-09606-6Online publication date: 5-Jul-2021
https://doi.org/10.1007/s11831-021-09606-6
Löhner RAntil H(2021)High fidelity modeling of aerosol pathogen propagation in built environments with moving pedestriansInternational Journal for Numerical Methods in Biomedical Engineering10.1002/cnm.342837:3Online publication date: 6-Jan-2021
https://doi.org/10.1002/cnm.3428
van Toll WPettre J(2019)Connecting Global and Local Agent Navigation via TopologyProceedings of the 12th ACM SIGGRAPH Conference on Motion, Interaction and Games10.1145/3359566.3360084(1-10)Online publication date: 28-Oct-2019
https://dl.acm.org/doi/10.1145/3359566.3360084
Chen CLiu YKreiss SAlahi A(2019)Crowd-Robot Interaction: Crowd-Aware Robot Navigation With Attention-Based Deep Reinforcement Learning2019 International Conference on Robotics and Automation (ICRA)10.1109/ICRA.2019.8794134(6015-6022)Online publication date: May-2019
https://doi.org/10.1109/ICRA.2019.8794134
Sun LZhai JQin W(2019)Crowd Navigation in an Unknown and Dynamic Environment Based on Deep Reinforcement LearningIEEE Access10.1109/ACCESS.2019.29334927(109544-109554)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2019.2933492
Schaumann DKapadia MDavis PO'Mahony APfautz J(2019)Modeling Social and Spatial Behavior in Built Environments: Current Methods and Future DirectionsSocial‐Behavioral Modeling for Complex Systems10.1002/9781119485001.ch29(673-695)Online publication date: 29-Mar-2019
https://doi.org/10.1002/9781119485001.ch29
Zhang GLu DLv LYu HLiu H(2018)Knowledge-Based Crowd Motion for the Unfamiliar EnvironmentIEEE Access10.1109/ACCESS.2018.28824356(72581-72593)Online publication date: 2018
https://doi.org/10.1109/ACCESS.2018.2882435
Show More Cited By

View Options

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