Jur van den Berg
ABSTRACT
We present a novel approach for interactive navigation and planning of multiple agents in crowded scenes with moving obstacles. Our formulation uses a precomputed roadmap that provides macroscopic, global connectivity for wayfinding and combines it with fast and localized navigation for each agent. At runtime, each agent senses the environment independently and computes a collision-free path based on an extended "Velocity Obstacles" concept. Furthermore, our algorithm ensures that each agent exhibits no oscillatory behaviors. We have tested the performance of our algorithm in several challenging scenarios with a high density of virtual agents. In practice, the algorithm performance scales almost linearly with the number of agents and can run at interactive rates on multi-core processors.
- Abe, Y., and Matsuo, Y. 2001. Collision avoidance method for multiple autonomous mobile agents by implicit cooperation. In Proc. IEEE Int. Conf. on Robotics and Automation, 1207--1212.Google Scholar
- 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.Google Scholar
- 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), 362--370. Google ScholarDigital Library
- Cordeiro, O. C., Braun, A., Silveria, C. B., Musse, S. R., and Cavalheiro, G. G. 2005. Concurrency on social forces simulation model. First International Workshop on Crowd Simulation.Google Scholar
- Ferguson, D., Kalra, N., and Stentz, A. 2006. Replanning with RRTs. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (May).Google Scholar
- Feurtey, F. 2000. Simulating the Collision Avoidance Behavior of Pedestrians. Master's thesis, University of Tokyo.Google Scholar
- Fiorini, P., and Shiller, Z. 1998. Motion planning in dynamic environments using velocity obstacles. Int. Journal of Robotics Research 17, 7, 760--772.Google ScholarCross Ref
- Funge, J., TU, X., and Terzopoulos, D. 1999. Cognitive modeling: Knowledge, reasoning and planning for intelligent characters. Proc. of ACM SIGGRAPH, 29--38. Google ScholarDigital Library
- Garaerts, R., and Overmars, M. H. 2007. The corridor map method: Real-time high-quality path planning. In ICRA, 1023--1028.Google Scholar
- 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.Google Scholar
- Helbing, D., Buzna, L., and Werner, T. 2003. Self-organized pedestrian crowd dynamics and design solutions. Traffic Forum 12.Google Scholar
- Hsu, D., Kindel, R., J.-C.Latombe, and Rock, S. 2002. Randomized kinodynamic motion planning with moving obstacles. International Journal of Robotics Research.Google Scholar
- Jaillet, L., and Simeon, T. 2004. A PRM-based motion planning for dynamically changing environments. Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS).Google Scholar
- Kallmann, M., and Mataric, M. 2004. Motion planning using dynamic roadmaps. Proceedings of the IEEE Conference on Robotics and Automation (ICRA) (April).Google Scholar
- Kamphuis, A., and Overmars, M. 2004. Finding paths for coherent groups using clearance. Proc. of ACM SIGGRAPH/Eurographics Symposium on Computer Animation, 19--28. Google ScholarDigital Library
- Khatib, O. 1986. Real-time obstable avoidance for manipulators and mobile robots. IJRR 5, 1, 90--98. Google ScholarDigital Library
- Kluge, B., and Prassler, E. 2007. Reflective navigation: Individual behaviors and group behaviors. In Proc. IEEE Int. Conf. on Robotics and Automation, 4172--4177.Google Scholar
- Koenig, S., and Likhachev, M. 2002. Improved fast replanning for robot navigation in unknown terrain. Proceedings of the IEEE International Conference on Robotics and Automation (ICRA) (May).Google Scholar
- 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, 509--518.Google ScholarCross Ref
- Latombe, J. 1991. Robot Motion Planning. kluwer Academic Publishers. Google ScholarDigital Library
- Lau, M., and Kuffner, J. J. 2006. Precomputed search trees: Planning for interactive goal-driven animation. In Proc. of the 2006 ACM SIGGRAPH/Eurographics Symposium on Computer animation, Eurographics Association, Aire-la-Ville, Switzerland, Switzerland, 299--308. Google ScholarDigital Library
- LaValle, S., and Kuffner, J. 2001. Randomized kinodynamic planning. International Journal of Robotics Research.Google Scholar
- LaValle, S. M. 2006. Planning Algorithms. Cambridge University Press (also available at http://msl.cs.uiuc.edu/planning/). Google ScholarDigital Library
- Leven, P., and Hutchinson, S. 2000. Toward real-time path planning in changing environments. Proceedings of the fourth International Workshop on the Algorithmic Foundations of Robotics (WAFR).Google Scholar
- Li, Y., and Gupta, K. 2007. Motion planning of multiple agents in virtual environments on parallel architectures. In ICRA, 1009--1014.Google Scholar
- Loscos, C., Marchal, D., and Meyer, A. 2003. Intuitive crowd behaviour in dense urban environments using local laws. In Theory and Practice of Computer Graphics (TPCG'03), 122--129. Google ScholarDigital Library
- MASSIVE, 2006. http://www.massivesoftware.com.Google Scholar
- Musse, S. R., and Thalmann, D. 1997. A model of human crowd behavior: Group inter-relationship and collision detection analysis. Computer Animation and Simulation, 39--51.Google Scholar
- Overmars, M. H. 1992. Point location in fat subdivisions. Inf. Process. Lett. 44, 261--265. Google ScholarDigital Library
- 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.Google Scholar
- Pelechano, N., Allbeck, J., and Badler, N. 2007. Controlling individual agents in high-density crowd simulation. Proc. of ACM SIGGRAPH / Eurographics Symposium on Computer Animation (SCA). Google ScholarDigital Library
- 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.Google Scholar
- Petty, S., and Fraichard, T. 2005. Safe motion planning in dynamic environments. In Proc. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 3726--3731.Google Scholar
- Quinlan, S., and Khatib, O. 1993. Elastic bands: Connecting path planning and control. Proc. of IEEE Conf. on Robotics and Automation.Google Scholar
- Reynolds, C. W. 1987. Flocks, herds, and schools: A distributed behavioral model. In Computer Graphics (SIGGRAPH '87 Proceedings), M. C. Stone, Ed., vol. 21, 25--34. Google ScholarDigital Library
- Reynolds, C. 1999. Steering behaviors for autonomous characters. In Proc. Game Developers Conference, 763--782.Google Scholar
- 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. Google ScholarDigital Library
- Schreckkenberg, M., and Sharma, S. D. 2001. Pedestrian and Evacuation Dynamics. Springer.Google Scholar
- 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. Google ScholarDigital Library
- Shiller, Z., Large, F., and Sekhavat, S. 2001. Motion planning in dynamic environments: obstacles moving along arbitrary trajectories. In Proc. IEEE Int. Conf. on Robotics and Automation, 3716--3721.Google Scholar
- Simeon, T., Leroy, S., and Laumond, J. 1999. Path coordination for multiple mobile robots: a geometric algorithm. Proc. of IJCAI. Google ScholarDigital Library
- Stentz, A. 1995. The focussed D* algorithm for real-time replanning. Proceedings of the International Joint Conference on Artificial Intelligence (IJCAI). Google ScholarDigital Library
- Still, G. 2000. Crowd Dynamics. PhD thesis, University of Warwik, UK. Ph.D. Thesis.Google Scholar
- Sung, M., Gleicher, M., and Chenney, S. 2004. Scalable behaviors for crowd simulation. Computer Graphics Forum 23, 3 (Sept), 519--528.Google ScholarCross Ref
- Sung, M., Kovar, L., and Gleicher, M. 2005. Fast and accurate goal-directed motion synthesis for crowds. Proc. of SCA 2005, 291--300. Google ScholarDigital Library
- Thalmann, D., O'Sullivan, C., Ciechomski, P., and Dobbyn, S. 2006. Populating Virtual Environments with Crowds. Eurographics 2006 Tutorial Notes.Google Scholar
- Tolman, E. C. 1948. Cognitive maps in rats and men. The Psychological Review 55, 4, 189--208.Google ScholarCross Ref
- Treuille, A., Cooper, S., and Popovic, Z. 2006. Continuum crowds. Proc. of ACM SIGGRAPH, 1160--1168. Google ScholarDigital Library
- Tu, X., and Terzopoulos, D. 1994. Artificial fishes: Physics, locomotion, perception, behavior. In Proceedings of SIGGRAPH '94, A. Glassner, Ed., 43--50. Google ScholarDigital Library
- van den Berg, J., Lin, M., and Manocha, D. 2008. Reciprocal velocity obstacles for real-time multi-agent navigation. In Proc. IEEE Int. Conf. on Robotics and Automation.Google Scholar
- Warren, C. W. 1990. Multiple path coordination using artificial potential fields. Proc. of IEEE Conf. on Robotics and Automation, 500--505.Google ScholarCross Ref
- Yang, Y., and Brock, O. 2006. Elastic roadmaps: Globally task-consistent motion for autonomous mobile manipulation. Proceedings of Robotics: Science and Systems (August).Google Scholar
- Zucker, M., Kuffner, J., and Branicky, M. 2007. Multipartite rrts for rapid replanning in dynamic environments. Proc. IEEE Int. Conf. on Robotics and Automation.Google Scholar
Index Terms
- Interactive navigation of multiple agents in crowded environments
Recommendations
Robotic navigation in crowded environments: key challenges for autonomous navigation systems
PerMIS '08: Proceedings of the 8th Workshop on Performance Metrics for Intelligent SystemsCrowded environments provide significant challenges for autonomous navigation systems. The robot must be fully aware of its surroundings and incorporate this knowledge into its decision-making and planning processes. The purpose of this paper is to ...
SLAM and navigation in indoor environments
PSIVT'11: Proceedings of the 5th Pacific Rim conference on Advances in Image and Video Technology - Volume Part IIn this paper, we propose a system for wheeled robot SLAM and navigation in indoor environments. An omni-directional camera and a laser range finder are the sensors to extract the point features and the line features as the landmarks. In SLAM and self-...
Comments