Crowd simulation, motion planning and path planning

One of the fundamental tasks characters have to perform is planning their motions while avoiding collisions with obstacles in the environment. We conduct research on motion planning for two- and three-dimensional rigid bodies and articulated robots moving in dynamic virtual environments.


Crowd simulation

A huge challenge is to simulate tens of thousands of characters in real-time where they pro-actively and realistically avoid collisions with each other and with obstacles present in their environment. This environment contains semantic information (e.g. roads and bicycle lanes, dangerous and pleasant areas), is three-dimensional (e.g. contains bridges where people can walk over and under as well) and can dynamically change (e.g. a bridge partially collapses). We currently study how to create a generic framework centered around a navigation mesh, for such environments and how it can be updated dynamically and efficiently. Next, we study how (groups of) people move and avoid collisions in such environments, based on character profiles and semantics. We run our simulations in realistic environments (e.g. soccer stadiums or train stations) and game levels to study the effectiveness of our methods. Finally, we have created a software package that integrates this research.

Using the Corridor Map Method and Indicative Route Method allows flexible path planning and crowd simulation: smooth paths, short paths, obstacle and collision avoidance, coherent groups, path variations and camera paths. (The image was created by INCONTROL Simulation Solutions.)

Roland Geraerts. A computational model of human navigation. Keynote given at the Conference on Pedestrian and Evacuation Dynamics 2014 (PED 2014).
Presentation [pdf]

Norman S. Jaklin, Mark tibboel, Roland Geraerts.
Computing High-Quality Paths in Weighted Regions.
new In ACM SigGraph Conference on Motion in Games (MIG 2014), 2014.

Rudi Bonfiglioli, Wouter G. van Toll, Roland Geraerts.
GPGPU-Accelerated Construction of High-Resolution Generalized Voronoi Diagrams and Navigation Meshes.
new In ACM SigGraph Conference on Motion in Games (MIG 2014), 2014.

Norman S. Jaklin, Wouter G. van Toll, Roland Geraerts.
Way to go - A framework for multi-level planning in games.
new In 3rd International Planning in Games Workshop (ICAPS'13 | PG2013), pp 11-14, 2013.
Full text [pdf] | Presentation [pptx]

Norman S. Jaklin, Atlas F. Cook IV, Roland Geraerts.
Real-Time Path Planning in Heterogeneous Environments.
new Computer Animation and Virtual Worlds (CAVW), 24(3):285-295, 2013.
Full text [pdf] | Presentation CASA [pdf]

Jordi Janer, Roland Geraerts, Wouter G. van Toll, Jordi Bonada.
Talking soundscapes: Automatizing voice transformations for crowd simulation.
In Proceedings AES 49th Conference Audio for Games (AES49), London, 2013.
Full text [pdf]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Real-Time Density-Based Crowd Simulation.
Computer Animation and Virtual Worlds (CAVW), 23(1):59-69, 2012.
new Full text [pdf]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
A Navigation Mesh for Dynamic Environments.
Computer Animation and Virtual Worlds (CAVW), 23(6):535-546, 2012.
new Full text [pdf] | Presentation [ppt]

Ioannis Karamouzas, Roland Geraerts, and A. Frank van der Stappen.
Space-time Group Motion Planning.
In Workshop on the Algorithmic Foundations of Robotics (WAFR2012), Algorithmic Foundations of Robotics X, Springer Tracts on Advanced Robotics Vol 86, pp. 227-243, 2013.
Full text: [pdf] | Presentation [pptx]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Navigation Meshes for Realistic Multi-Layered Environments.
In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'11), pp. 3526-3532, 2011.
Full text [pdf] | Presentation pitch [ppt]

Marjan van den Akker, Roland Geraerts, Han Hoogeveen, and Corien Prins.
Path Planning for Groups using Column Generation.
In Motion in Games (MIG'10), Springer Lecture Notes in Computer Science (LNCS) 6459, pp. 94-105, 2010.
Full text [pdf] | Presentation [ppt]

Marjan van den Akker, Roland Geraerts, Han Hoogeveen, and Corien Prins.
Path Planning in Games.
In 10th Workshop on Models and Algorithms for Planning and Scheduling Problems (MAPSP'11), 2011.
Full text [pdf]


Bard van de Weijer.
Crowd-management: De Meute ontward. De Volkskrant (Wetenschap), 17 April 2013.
new Full text in Dutch [pdf]

Rob Blaauboer.
new Mensenmassa's simuleren: voorbereid op de ergste rampen. Scientias.nl, 8 June 2013.


The Corridor Map Method / Indicative Route Method

Current applications require a path planner that is fast (to ensure real-time interaction with the environment) and flexible (to avoid local hazards). In addition, paths need to be natural, i.e. smooth and short. Our framework, the Corridor Map Method, meets these requirements.

A smooth, short path with clearance inside an Explicit Corridor. Click on the image for finer details.

Roland Geraerts.
Planning Short Paths with Clearance using Explicit Corridors.
In IEEE International Conference on Robotics and Automation (ICRA'10), pp. 1997-2004, 2010.
Full text [pdf] | Presentation [ppt]

José Manuel Cabello, José María Franco, Antonio Collado, Jordi Janer, Samuel Cruz-Lara, David Oyarzun, Albert Armisen, and Roland Geraerts.
Standards in Virtual Worlds Virtual Travel Use Case Metaverse1 Project.
Virtual Worlds Research (JVWResearch) - MPEG-V and Other Virtual Worlds Standards, 4(3):1-29, 2011.
Full text [pdf]

Roland Geraerts and Erik Schager.
Stealth-Based Path Planning using Corridor Maps.
In Computer Animation and Social Agents (CASA'10), 2010.
Full text [pdf] | Presentation [ppt]

Ioannis Karamouzas, Roland Geraerts and Mark Overmars.
Indicative Routes for Path Planning and Crowd Simulation.
In The Fourth International Conference on the Foundations of Digital Games (FDG'09), pp. 113-120, 2009.
Full text [pdf] | Presentation [ppt]

Roland Geraerts and Mark H. Overmars.
The Corridor Map Method: A General Framework for Real-Time High-Quality Path Planning.
Computer Animation and Virtual Worlds (CAVW), 18:107-119, 2007.
Full text [pdf]

Roland Geraerts and Mark H. Overmars.
Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments.
In Computer Animation and Social Agents (CASA'08), pp. 64-71, 2008.
Full text [pdf] | Presentation [ppt]

Mark H. Overmars, Ioannis Karamouzas and Roland Geraerts.
Flexible Path Planning Using Corridor Maps.
D. Halperin, K. Mehlhorn (Eds): Algorithms - (ESA) 2008, Springer Lecture Notes in Computer Science (LNCS) 5193, pp. 1-12, 2008.
Full text [pdf]

Roland Geraerts, Arno Kamphuis, Ioannis Karamouzas and Mark H. Overmars.
Using the Corridor Map Method for Path Planning for a Large Number of Characters.
In Motion in Games (MIG'08), Springer Lecture Notes in Computer Science (LNCS) 5277, pp. 11-22, 2008.
Full text [pdf] | Presentation [ppt]

Roland Geraerts and Mark H. Overmars.
The Corridor Map Method: Real-Time High-Quality Path Planning.
In IEEE International Conference on Robotics and Automation (ICRA'07), pp. 1023-1028, 2007.
Full text [pdf, ps.gz] | Presentation [ppt]

Roland Geraerts.
Camera Planning in Virtual Environments using the Corridor Map Method.
In The Second International Workshop on Motion in Games (MIG'09), Springer Lecture Notes in Computer Science (LNCS) 5884, pp. 194-209, 2009.
Full text [pdf]


Comparative studies and analyses

We conduct a comparative study of different techniques that are used in the Probabilistic Roadmap Method. In addition, we give a reachability analysis for sampling based planners which leads to a better understanding of the success of the planners.

Comparative studies and analyses

Roland Geraerts and Mark H. Overmars.
Reachability-based Analysis for Probabilistic Roadmap Planners.
Robotics and Autonomous Systems (RAS), 55:824-836, 2007.
Full text [pdf]

Roland Geraerts and Mark H. Overmars.
Reachability Analysis of Sampling Based Planners.
In IEEE International Conference on Robotics and Automation (ICRA'05), pp. 406-412, 2005.
Full text [pdf, ps.gz] | Presentation [zip]

Roland Geraerts and Mark H. Overmars.
Sampling and Node Adding in Probabilistic Roadmap Planners.
Robotics and Autonomous Systems (RAS), 54:165-173, 2006.
Full text [pdf]

Roland Geraerts and Mark H. Overmars.
Sampling Techniques for Probabilistic Roadmap Planners.
In Conference on Intelligent Autonomous Systems (IAS-8), pp. 600-609, 2004.
Full text [pdf] | Presentation [ppt]

Roland Geraerts and Mark H. Overmars.
A Comparative Study of Probabilistic Roadmap Planners.
In Proc. Workshop on the Algorithmic Foundations of Robotics (WAFR'02), pp. 43-57, 2002.
Full text [pdf] | Presentation [ppt]


High-quality paths

We present algorithms that increase the quality of a path. That is, we focus on decreasing the path length and increasing the clearance along a path. The techniques can be applied to a broad range of robots which may reside in arbitrary high-dimensional configuration spaces.

High-quality paths

Roland Geraerts and Mark H. Overmars.
Creating High-Quality Paths for Motion Planning.
International Journal of Robotics Research (IJRR), 26:845-863, 2007.
Full text [pdf]

Roland Geraerts and Mark H. Overmars.
On Improving the Clearance for Robots in High-Dimensional Configuration Spaces.
In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'05), pp. 4074-4079, 2005.
Full text [pdf, ps.gz] | Presentation [ppt]

Roland Geraerts and Mark H. Overmars.
Clearance Based Path Optimization for Motion Planning.
In IEEE International Conference on Robotics and Automation (ICRA'04), pp. 2386-2392, 2004.
Full text [pdf] | Presentation [ppt]


High-quality roadmaps

The Reachability Roadmap Method is a new and efficient algorithm that creates small roadmaps for two- and three-dimensional problems. The algorithm ensures that a path can always be found if one exists. We extend the algorithm such that short paths and high-clearance paths can be extracted from the roadmap in real-time.

High-quality roadmaps

Roland Geraerts and Mark H. Overmars.
Creating High-quality Roadmaps for Motion Planning in Virtual Environments.
In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS'06), pp. 4355-4361, 2006.
Full text [pdf, ps.gz] | Presentation [ppt]

Roland Geraerts and Mark H. Overmars.
Creating Small Graphs for Solving Motion Planning Problems.
In IEEE International Conference on Methods and Models in Automation and Robotics (MMAR'05), pp. 531-536, 2005.
Full text [pdf, ps.gz] | Presentation [ppt]


Ph.D. thesis

The thesis deals with comparing and analyzing sampling-based motion planning techniques, in particular variants of the Probabilistic Roadmap Method (PRM). In addition, quality aspects of paths and roadmaps are investigated.

Ph.D. thesis Roland Geraerts

Roland Geraerts.
Sampling-based Motion Planning: Analysis and Path Quality.
Ph.D. thesis. Utrecht University. 2006.
Full text [pdf low compression; 11.5MB, pdf high compression; 3MB]


Experimental research

In robotics research, it is often difficult to compare and evaluate techniques experimentally. We identify these difficulties and provides solutions based on our work during the last four years in the field of sampling-based motion planning.

Roland Geraerts.
On Experimental Research in Sampling-based Motion Planning.
In (IROS'06) Workshop on Benchmarks in Robotics Research, pp. 31-34, 2006.
Full text [pdf, ps.gz] | Lecture notes [pdf] | Presentation [ppt]


Animation

We study techniques for combining path planning with motion synthesis.

Combining Path Planners and Motion Graphs

Ben J.H. van Basten, Arjan Egges and Roland Geraerts.
Combining Path Planners and Motion Graphs.
Computer Animation and Virtual Worlds (CAVW), 22:59-78, 2011.
Full text [pdf]


National ASCI/ICT.OPEN conferences

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Game-Changing: Fast Dynamic Updates in a Flexible Navigation Mesh.
ICT.OPEN 2013 (ICT.OPEN 2013).
Full text: [pdf] | Presentation [pptx] | Poster [pdf|png]

Norman S. Jaklin, Atlas F. Cook IV, Roland Geraerts.
Stay off the lawn! Creating smooth paths based on region preferences.
ICT.OPEN 2013 (ICT.OPEN 2013).
Full text [pdf] | Presentation [pdf] | Poster [pdf|png]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Realistic Crowd Simulation with Density-Based Path Planning.
ASCI - IPA - SIKS tracks, ICT.OPEN (ICT.OPEN 2012), pp. 3-9, 2012.
This paper has received the best presentation award ASCI 2012.
Full text [pdf] | Presentation [ppt] | Poster [pdf]

Wouter G. van Toll, Atlas F. Cook IV, Roland Geraerts.
Multi-Layered Navigation Meshes.
In ASCI - IPA - SIKS tracks, ICT.OPEN (ICT.OPEN 2011), pp. 317-323, 2011.
This paper has received the best paper award ASCI 2011.
Full text [pdf] | Presentation [ppt]

Roland Geraerts and Mark H.Overmars.
On the Analysis and Success of Sampling Based Motion Planning.
In Conference of the Advanced School for Computing and Imaging (ASCI'05), pp. 313-319, 2005.
Full text [pdf, ps.gz] | Poster [pdf]

Roland Geraerts and Mark H. Overmars.
On Improving the Path Quality for Motion Planning.
In Conference of the Advanced School for Computing and Imaging (ASCI'04), pp. 211-217, 2004.
Full text [pdf]


Last update: October 27, 2014.

Valid HTML 4.01 Transitional Valid CSS!