spacer spacer

Updates

XML/RSS feedXML/RSS feed
Last update: 10 August 2009

General information

The seminar Path Planning is given as a part of the GMT Master program at the Utrecht University. The course is given in the 4th period on Monday (13.15-15.00) and Thursday (11.00-12.45) in BBL-501.

Course overview

Path planning plays an important role in computer games and virtual environments. Characters in such environments have to plan their paths to move from one location to another. These paths must avoid collisions with the environment and with other characters. Also it is important that these paths are natural, that is, they look similar to paths humans would take. In this seminar we will study a number of the recent results on path planning and crowd simulation.

Schedule

The presentations in the following schedule have been removed :-)
Week Date Topic Paper Speaker Deadline
 17 April 20 Introduction   Mark Overmars  
  April 23 Current problems   Everyone Assignment 1
 18 April 27 No seminar      
  April 30 No seminar      
 19 May 4 CMM 0, 1, 2 Roland Geraerts Abstracts
  May 7 Path planning 3, 4 Wiratma, Weijermans Abstracts
 20 May 11 Path planning 5, 6 Tromp, Toxopeus Abstracts
  May 14 PP/Social force models 7, 8 Spoel, Peters Abstracts
 21 May 18 Social force models 9, 10 Kok, Doornenbal Abstracts
  May 21 No seminar      
 22 May 25 Social force models 11, 12 Demir, Wiratma Abstracts
  May 28 SFM, Flow 13, 14 Anantharam, Albers Abstracts
 23 June 1 No seminar      
  June 4 No seminar      
 24 June 8 Flow 15, 16 Weijermans, Tromp Abstracts
  June 11 Flow/Crowds 17, 18 Toxopeus, Spoel Abstracts
 25 June 15 Crowds 19, 20 Peters, Kok Abstracts
  June 18 No seminar      
 26 June 22 Crowd behavior 21, 22 Doornenbal, Demir Abstracts
  June 25 Crowd rendering 23, 24 Anantharam, Albers Abstracts
 27 July 3 No seminar     Assignment 2

Assignments

To develop some insights about current problems and challenges in the field of path planning, you will be studying a game in the first assignment. Next, you have to write a short document for each paper that will be discussed. Each student will discuss two papers. At the end of the seminar, you have to create and hand in a paper on how some interesting problems can be solved.

Assignment 1

In the first assignment you have to collect some footage from a game in which path planning issues went dramatically wrong. These issues include general path planning, crowd planning and camera planning. While some examples can be found on the web (see for example these path finding bugs or even better this overview [pdf]), you need to create the footage yourself. You can use Fraps to capture a relevant part. If that fails you could use a (web/photo/film) camera to record a piece. Next, take a representative picture of it and put it, together with a short discussion of what went wrong and how it could be fixed, onto three PowerPoint slides. The movie and slides must be handed in on April 23 at the start of the meeting. Your work will be discussed during this meeting.

Abstracts

For each paper presentation (starting at May 4), except for your own presentations, you have to write a 1 page document including a short summary in your own words, some challenges, shortcomings, suprising and innovative elements, and a few relevant questions of the paper. (For May 4, write a 2 page document). A printed copy must be handed in at the start of the presentation.

Assignment 2

The goal of the second assignment is to write a document on how the techniques that you have seen during the seminar can be used to solve path planning and crowd simulation problems in actual games. In the first assignment you have all created videos of problems with path planning in games. From these we have selected the most interesting/relevant issues:

  • Unnatural crowd movements in Warcraft III: Reign of Chaos; see Pieter’s contribution.
  • Unnatural global behavior in Resident Evil 4; see Cetin’s contribution.
  • Unnatural local path planning/steering in Halo; see Geerten’s contribution.

For each of these three issues you need to write a 5-page document describing how you think the problems can be solved or at least improved using the techniques that have been discussed during this seminar. (So the total document should be 15 pages in length.) You should write the paper as if it was meant as a recommendation for the programmer of the game. So it should have enough details to convince the programmer that this is a good idea and that he should investigate the approach further. Explain the problems you observe, give a global description of the techniques you suggest for improvement, and indicate why you think they would solve the problems. Give references to the papers from which you have taken the techniques. In your writing assume that the reader has a good knowledge of computer science but no knowledge of the techniques discussed in the seminar.

This paper must be mailed to Roland preferrably before or on July 3 at 18.00. Since this is a strict deadline, make sure you start in time. Note that you do not need papers 23 and 24 for this assignment.

Presentations of research papers

Each student will be assigned two research papers which have to be presented. A PC and projector will be present. When you're preparing your presentation, do it in such a way that people who don't know the paper (but have a computer science background) can still follow your presentation. So, explain the algorithms and definitions clearly and give some examples. Also, do not put too much text on your slides. If you are displaying charts or tables, please explain all axes, legend, etc. You're of course free to steal additional information (such as movies and java applets) from the Internet. Try to speak for about 30 minutes. The remainder (15 minutes) should be used for discussions. The following papers are discussed.

# Topic Title Author(s)
0 CMM The corridor map method: a general framework for real-time high-quality path planning R. Geraerts and M.H. Overmars
1   Enhancing Corridor Maps for Real-Time Path Planning in Virtual Environments R. Geraerts and M.H. Overmars
2   Planning Short Paths with Clearance using Explicit Corridors R. Geraerts
3 Path planning Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces L.E. Kavraki et al
4   RRT-connect: An efficient approach to single-query path planning J.J. Kuffner and S.M. LaValle
5   Adding Variation to Path Planning Algorithms I. Karamouzas and M.H. Overmars
6   Finding Paths for Coherent Groups using Clearance A. Kamphuis and M.H. Overmars
7   Indicative Routes for Path Planning and Crowd Simulation I. Karamouzas et al
8 Social force models Steering Behaviors For Autonomous Characters C.W. Reynolds
9   Social Potential Fields A Distributed Behavioral Control for Autonomous Robots J.H. Reif and H. Wang
10   Simulating dynamical features of escape panic D. Helbing et al
11   A Physically-Based Particle Model of Emergent Crowd Behaviors L. Heïgeas et al
12   Controlling Individual Agents in High-Density Crowd Simulation N. Pelechano et al
13   Local methods (requires user/password) movie I. Karamouzas and M. Overmars
14 Flow Flow Tiles S. Chenney
15   Intuitive Crowd Behaviour in Sense Urban Environments using Local Laws C. Loscos et al
16   The Flow of Human Crowds (requires user/password) R.L. Hughes
17   Continuum Crowds A. Treuille et al
18 Crowds Real-time Navigation of Independent Agents Using Adaptive Roadmaps A. Sud et al
19   Real-time crowd motion planning: Scalable Avoidance and Group Behavior B. Yersin et al
20   Crowd Patches: Populating Large-Scale Virtual Environments for Real-Time Applications B. Yersin et al
21 Behavior Scalable Behaviors for Crowd Simulation M. Sung et al
22   Hierarchical Model for Real Time Simulation of Virtual Human Crowds S.R. Musse and D. Thalmann
23 Rendering Survey of Real-Time Rendering Techniques for Crowds G. Ryder and A.M. Day
24   Visualizing Crowds in Real-Time F. Tecchia et al

Grading

There will be no exam but grading will depend on the quality of the given presentations (40%), the first assignment (5%), the second assignment (25%), abstracts (20%), and the active participation in the meetings (10%). To qualify for second change exam the original mark should at least be a 4. Also you must actively participate in at least 75% of the meetings and give both presentations satisfactory.

Teachers

For additional information about the seminar, please contact Roland Geraerts or Mark Overmars.

A natural path inside a virtual environment. I can imagine that you wonder why I have placed this nice green large ball here.