mm_spacer

Updates

Please subscribe to our news feed to receive the latest information: XML/RSS feed HTML feed
Last update: 30 January 2017.

This course will be renamed to Crowd simulation in 2017-2018.

General information

The course Path Planning is given as a part of the GMT Master program at Utrecht University. A better name for the course would be Crowd simulation, but is seems hard to change its name. The course is given in the second period on Monday (11.00-12.45) in BBG-023 and Wednesday (9.00-10.45) in Ruppert-C. There is no exam, and, as the meetings are highly interactive, presence is mandatory. The course starts on Monday, 14 November 2016.

Sitemap

Course overview

A huge challenge in computer games and virtual environments 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. Also it is important that these paths are visually compelling or even realistic, that is, the characters must move around in ways similar to real people (or monsters). In this course we will study a number of the recent results on path planning and crowd simulation, and how they can be applied in computer games and in the safety/security domains.

Besides knowing the state of the art in path planning and crowd simulation, you will become a critical reader, discover where the holes in the research are, participate in discussions and lead them, give better presentations, know how to set up experiments better, and write better review reports and assessments.

Schedule

The papers have been assigned on November 14. For example, Alex and Rogier will present paper 4 on November 30; Manuel and Simon will present paper 5 on the same day.

Week Date Topic Paper Speaker Deadline
46 Nov 14 Introduction, Path planning and crowd simulation 0 Roland Geraerts Read paper 0
  Nov 16 Path planning and crowd simulation (cont.), Experimental research 1 Roland Geraerts Read paper 1
47 Nov 21 Crowd simulation errors I   All students Assignment 1
  Nov 23 Crowd simulation errors II   All students
48 Nov 28 Workshop I: Giving presentations   Roland Geraerts, Everyone  
  Nov 30 Path planning 4, 5 Alex Klein & Rogier Wuijts, Manuel Merino Silva & Simon Seidel Abstracts
49 Dec 5 Path planning 6, 7 Kevin Ouwehand & Mathijs Molenaar, Andreas Bauer & Lorenzo Migliorino Abstracts
  Dec 7 Workshop II: UU Crowd Simulation Framework   Wouter van Toll, Angelos Kremyzas  
50 Dec 12 Social force-based models 8, 9 Irena Cirkovic & Klaas Hidde van den Berg, Juan Fonseca Mendez & Guillermo Ibaner de Aldeco Marin Abstracts
  Dec 14 Velocity-based models 12, 13 Kylian Kuijer & Bram Jonkers, Ermis Chalkiadakis & Jeroen Huisen Abstracts
51 Dec 19 Vision-based models 34, 35 Enrique Bernalte Mestre & Pedro Moura, Christian Knaapen & Teus van Oosterom Abstracts
  Dec 21 Flow 17, 18 Dimitrios Loubos & Georgios Kokkinos, Victor Veldstra & Robert Groot Abstracts
52 Dec 26 No lecture      
  Dec 28 No lecture      
1 Jan 2 No lecture      
  Jan 4 No lecture      
2 Jan 9 Crowds 19, 20 Rutger Kraaijer & Jan Geestman, David van der Sar & Timon van Zanten Abstracts
  Jan 11 Crowds, behavior 22, 23 Kevin van Mastrigt & Olaf Schalk, Chrit Hameleers & Yorick Kooij Abstracts
3 Jan 16 Behavior, Massive crowds 24, 26 Bob Reimink, An Li & Ruud Asseldonk Abstracts
  Jan 18 Evaluation and validation 30, 31 Wouter van der Waal & Marjolein Zwerver, Andrey Obolenskiy & Dustin Meijer Abstracts
4 Jan 23 Evaluation and validation 36, 37 Finn van der Heide & patrick van Eijk,  Jasper Kraimaat & Joep Hamersma Abstracts
  Jan 25 Crowd disasters 38, 39 Peter de Keijzer, Winand Renkema & Yiran Zhao Abstracts
5 Jan 30 Game demo's   All students  
  Feb 1 Workshop III: A*   Wouter van Toll, Arne Hillebrand Assignment 2

Assignments

In the zeroth assignment, you have to read an introduction paper to grasp some preliminaries on motion planning (try to read it before the first meeting), but don't write an abstract for this one. To develop some insights about current problems and challenges in the field of path planning and crowd simulation, you will be studying a game in the first assignment. Next, you have to write a one-page assessment for each paper that will be discussed. Each student will discuss one paper which will be assigned in the first meeting. At the end of the course, you have to hand in ans present a game in which you solve a crowd simulation problem discovered in the first assignment.

Assignment 1

In the first assignment you have to collect some footage from a (preferably modern) game in which the simulation of the crowd goes dramatically wrong. You need to work in pairs. For example, you could look

  • at natural crowds that fill up the game to make it more realistic. The NPCs might behave strangely around the player, or behave in unnatural ways in general;
  • near places in the environment where an obstacle has appeared, disappeared or moved. NPCs typically behave unrealistically around such dynamic places;
  • at situations with crossing flows or narrow passages. Often, this leads to deadlock or undesired collision-avoidance behavior. For instance, NPCs may get blocked, pass through an obstacle or another NPC, take an illogical detour, walk on undesired terrain, make sudden undesired directional changes, et cetera;
  • at advanced AI behaviors in which multiple NPCs are involved.

Such issues sometimes reveal themselves when you deliberately try to create 'problems'. For example, stand in the way of moving characters, park a car on the sidewalk, move to difficult camera positions, or destroy an object or building. While some examples can be found on the web (see for example this overview), you need to create the footage yourself. You can use e.g. Fraps to capture a relevant part.
When you create the movie, please take the following guidelines into account, because we are going to assemble your movies into one big movie:

  • Convert the result to a `standard' format like WMV to ensure that your movie can be played;
  • Use a 720p or 1080p resolution if possible;
  • Don't use transitions (e.g. fades) between clips or overlays (e.g. text); When you want to use these, make two versions, and them in both;
  • The shorter the movie, the better. It should capture the essence of the problem;
  • Compress your movie with a mpeg4-based codec, but don't make it too blurry. Create a file that isn't too big (e.g. 30MB usually works out nicely).

Next, take a representative picture of it and put it, together with a short discussion of what went wrong, why it went wrong, and how it could be fixed, onto three PowerPoint slides. (Please don't include the video in the slides, and ensure that the presentation works in Microsoft PowerPoint.) The movie and slides must be handed in before Sunday, 20 November, 17:00 by sending the teacher an e-mail (with topic MPAP assignment 1) with a direct download link to the movie and slides. (Don't forget to give me access to the files. Usually DropBox or WeTransfer works best since these programs allow downloading all files at once; Google drive often goes wrong due to not having the right rights, so check yourself in a browser's incognito tab if you manage to download the files yourself.) The teacher will assemble them so that they can be discussed during the next two meetings (so presenting it on your own laptop is not allowed due to time constraints). You'll present and discuss your results during at most 6 minutes.

We'll use the following score sheet. So you've to focus on answering four questions:

  • What does the video show?
  • What went wrong?
  • Why did it go wrong (according to you)?
  • How could it be fixed?

From the movies of the course's predecessor, we assembled a movie demonstrating how many games fail in planning high-quality motions for groups.

Your movies and presentations can be downloaded here. Use your solidID to log on to this webpage.

Abstracts

For each paper presentation (starting at November 30), except at meetings where you give a presentation, you need to write a 1-page document, including:

  • A short summary (at most half a page) in your own words. Please don’t forget to include a few lines on the experiments;
  • Next --and this is the part where you can score valuable points-- you need to spent a few paragraphs on a critical assessment of the paper, i.e. include some challenges, shortcomings, surprising and innovative elements. Don't forget to include a few lines on some frequently occurring 'errors', e.g. many authors claim too much, make many assumptions, draw conclusions that are too general, don't setup their experiments correctly, etcetera;
  • Finally, include three relevant questions you can ask during the presentation.
To ease the grading process, please include the following headings: Summary, Assessment, Questions, and, of course, your student name and number. A printed copy must be handed in at the end of the meeting.

For the second half of the papers (starting at January 9), you only need to spend 5 lines of text on the Summary. In addition, spend at least half a page (but preferably more) on the assessment. When you've read more than half of all papers, it's easier to put your paper in the right perspectives. Besides the mentioned points, you could also take a look at this paper (and in particular Section 4), which provides some additional reviewing criteria. Also, try to put the paper into perspective with other papers you have read.

Here are some tips to improve your abstracts even more:

  • See the presentation on experimental research to see some common errors. It lists many things that can go wrong in an experimental setup and during the experiments. Please try to incorporate some in your assessments.
  • I'm a bit in the war - on writing bad English. Also read the document on Dutch speakers. Please scan your abstracts and assignment 2's report for these mistakes.

Assignment 2

You have to create a computer game where the key gameplay element is crowd simulation (and write a report about that). You have to work in groups of 5 students. You will present the game on January 30th. You may decide to slightly adopt the game and report based on the feedback you get. Submit your work (the complete Unity3D project, executable, presentation, and report) by sending the teacher an e-mail (with topic MPAP assignment 2) with a direct download link to the corresponding zip file before or on February 1 at 23.59.

Crowd simulation game

The game has to be created with Unity3D and our UU Crowd simulation plug-in for Unity3D. A download link will be provided to you personally later. Note that Unity3D's programming language is C#. The game should include a solution for at least one situation that went wrong in Assignment 1. This can be any situation described by students from this class. You will notice that the crowd simulation software probably will not solve the problem at hand completely, so you have to work around that. You're free to use other resources (such as tutorials, assets, plug-ins, previously made own work, etc.), as long as you properly acknowledge the sources you have used, and as long as the UU Crowd simulation plug-in is used in the game. I would advise to embed the simulation in a virtual world where all walkable areas can be seen from above to ease making the navigation mesh. You are free to pick the genre, style, etc. Bonus points are given when the game is fun to play. We expect that each student spends 70 hours on the game, so start early!

Note that the UU Crowd simulation plug-in is in active development and may contain bugs. If you have questions or remarks about the plug-in, you are free to stop by at BBG 4.19 (the office of Angelos Kremyzas and Wouter van Toll) on Wednesdays between 11.00 and 12.45, starting from December 14.

How to get started?

On December 7th, we will give a workshop on how to use Unity3D, the plugin-in and some example projects. To complete the Unity/UUCS tutorial, you will at least need the following things in advance:

  • A working laptop that runs on Windows.
  • An installation of the 64-bit version of the Unity editor, version 5.4.1 or higher.
  • The 64-bit DLL of our UUCS crowd simulation framework. We will provide this file later.
  • The Unity C# example scripts that we have prepared for you. We will provide these files later.
  • A basic understanding of how the Unity interface works (see https://unity3d.com/learn/tutorials/topics/interface-essentials). The Unity website contains extensive documentation, so we will focus on details specific to the usage of UUCS.

You are encouraged to work on the tutorial individually, so bring your own laptop. (If it turns out that this does not fit in the room, we may resort to working in pairs.) Please ensure that its battery is fully charged.

Write a paper

The goal is to write a document in which you explain the observed issues, what solutions exists in literature, what solution(s) you did have in mind, how you solved the problem(s). Also elaborate on what elements were useful in the plug-in and what elements were missing. How did you work around the (limited) functionality?

The number of pages should be between 4 and 10. You should write the paper as if it was meant as a recommendation for the programmer of the game that has some issues. So it should have enough details to convince the programmer that this is a good idea and that (s)he should investigate the approach further. In your writing assume that the reader has a good knowledge of computer science but no knowledge of the techniques discussed in the course. Try to be as critical on your own paper as you were on the papers you have reviewed.

Present your work

Monday (30 January), you need to present the second assignment. There are 9 groups, and we have 90 minutes in total. I would suggest to follow the following 10-minute agenda per group: discuss problem (1) and solution (1), give a live demo of your game (4), questions and answers (2), receiving feedback (1), change team (1). You can use the feedback to improve your report and game. You will not get a grade for this performance. Please try to make it pleasurable and educational for your audience.

HTML feed

Presentations of research papers

Each student will be assigned one research paper which have to be presented. A PC and projector will be present. Your presentation will take 40 minutes, decomposed into the contents (10 minutes), a critical review (15 minutes), and a discussion (15 minutes) which you will lead. The remainder (5 minutes) will be used by the teacher.

Keep the content part short (since you may assume that everybody has read the paper), but still understandable (as if you are talking to a bachelor student who has not read the paper). Try to put the paper in the right (historic) perspective. Explain the global idea, algorithms and definitions clearly and give some examples. Also, try to give the intuition/motivation behind the formulas you show (e.g. decompose the formula and explain each term and create a picture which clarifies the formula, or use the blackboard).  You can make this part even more interesting by including some additional pictures and movies (e.g. from the author's website, or from a paper that cites your paper), personal information about the author(s), citation count, anecdotes, demo's, etc. Please also consider related or future work (i.e. work that refers to your paper).

The critical review is the most important part of your presentation. In the section on Abstracts, you can find many tips. A high grade can be obtained if you are very critical about the paper and put it in the right perspectives with other research papers.

In the discussion phase, you can ask questions to the audience yourself. However, if you receive a question from the audience, please repeat this question in your own words. Give a conclusion after each discussed point. Also ensure that you give the word to different students.

In general, do not put too much text on your slides (i.e. at most 7 lines of text) and include a picture. If you are displaying charts or tables, please explain all axes, legend, etc.

We'll use the following score sheet.

A selection of the following papers is discussed:

# Topic Title Author(s)
0 Introduction Motion Planning L.E. Kavraki and S.M. LaValle
1 Path planning Towards Believable Crowds: A Generic Multi-Level Framework for Agent Navigation. W.G. van toll et al
2   Planning Short Paths with Clearance using Explicit Corridors [more info] R. Geraerts
3   Navigation Meshes for Realistic Multi-Layered Environments (background material; an abstract is not required.) W.G. van Toll et al
4   Probabilistic Roadmaps for Path Planning in High-Dimensional Configuration Spaces
More info; paper analyzes the PRM:
Reachability-based analysis for Probabilistic Roadmap planners
L.E. Kavraki et al
5   Rapidly-exploring random trees: Progress and prospects
More info: LaValle's website
S.M. LaValle and J.J. Kuffner and
6   Finding Paths for Coherent Groups using Clearance
More info: taxonomy, PhD thesis on formations
A. Kamphuis and M.H. Overmars
7   Real-time path planning in heterogeneous environments N. Jaklin et al
8 Social force models Steering Behaviors For Autonomous Characters C.W. Reynolds
9   Social force model for pedestrian dynamics D. Helbing and P. Molnar
10   A Physically-Based Particle Model of Emergent Crowd Behaviors L. Heïgeas et al
11   Controlling Individual Agents in High-Density Crowd Simulation N. Pelechano et al
12 Velocity-based models Reciprocal n-body Collision Avoidance. See also this link or their project page. J. van den Berg et al
13   Simulating Human Collision Avoidance Using a Velocity-Based Approach [more info] I. Karamouzas and M. Overmars
14 Flow Flow Tiles S. Chenney
15   The Flow of Human Crowds R.L. Hughes
16   Crowd Sculpting: A space-time sculpting method for populating virtual environments K. Jordao et al
17   Continuum Crowds A. Treuille et al
18   Directing Crowd Simulations Using Navigation Fields S. Patil et al
19 Crowds Real-time Navigation of Independent Agents Using Adaptive Roadmaps A. Sud et al
20   Real-time crowd motion planning: Scalable Avoidance and Group Behavior B. Yersin et al
21   Crowd Patches: Populating Large-Scale Virtual Environments for Real-Time Applications B. Yersin et al
22 Behavior Scalable Behaviors for Crowd Simulation M. Sung et al
23   Hierarchical Model for Real Time Simulation of Virtual Human Crowds S.R. Musse and D. Thalmann
24   Composite Agents H. Yeh et al
25   Intuitive Crowd Behaviour in Sense Urban Environments using Local Laws C. Loscos et al
26 Massive crowds Aggregate Dynamics for Dense Crowd Simulation R. Narain et al
27   The Virtual Marathon: Parallel Computing Supports Crowd Simulations E. Yilmaz et al
28 GPU techniques Multi Agent Navigation on the GPU A. Bleiweiss
29   GPU Accelerated Path-planning for Multi-agents in Virtual Environments L.G. Fischer
30 Evaluation Data Driven Evaluation of Crowds A. Lerner et al
31   SteerBench: a benchmark suite for evaluating steering behaviors S. Singh et al
32 Rendering Survey of Real-Time Rendering Techniques for Crowds G. Ryder and A.M. Day
33   Visualizing Crowds in Real-Time F. Tecchia et al
34 Vision-based models How simple rules determine pedestrian behavior and crowd disasters M. Moussaid et al
35   A Synthetic-Vision Based Steering Approach for Crowd Simulation J. Ondrej et al
36 Realistic models A Statistical Similarity Measure for Aggregate Crowd Dynamics S.J. Guy et al
37   Realistic following behaviors for crowd simulation S. Lemercier et al
38 Crowd disasters Pedestrian, Crowd and Evacuation Dynamics D. Helbing and A. Johansson
39   Crowd disasters as systemic failures: analysis of the Love Parade disaster D. Helbing and P. Mukerji

Workshops

We will give three workshops. These were requested by many students who already have followed the course. The first workshop is on giving presentations. In the course, you will get much feedback on your presentation skills, but this will not be part of your grade. The second one is about using the UU crowd simulation software in Unity3D. You need these skills in the second assignment. The third workshop will be centered around the famous A* algorithm. You will learn to understand the A* algorithm, reason about its properties, and apply it to a range of problems.

Grading

There will be no exam but grading will depend on the

  • quality of the given presentation (15%);
  • first assignment (10%);
  • the second assignment (35%);
  • abstracts (40%).

To qualify for second chance exam, the original mark should at least be a 4. Also you must actively participate in at least 75% of the meetings and give your presentation satisfactory.

The grades will be published here. Use your solidID to log on to this webpage.

Gammon and spinach

There are in total 20 meetings and it is mandatory to be there (in time) because there is no exam. You cannot pass the course if you are absent for 6 or more times (for whatever reason).

There are in total 24 abstracts to be handed in. You cannot pass the course if you skipped 6 or more abstracts.

If it occurs that you know in advance that you will not be able to give your presentation at a specific date, please swap with somebody else and notify the teacher.

Bonus points

A maximum of 0.5 bonus point can be obtained by organizing a well-conducted flash mob where a game situation from the first assignment is 'replayed'. A movie and a small document (with the used idea and set up) needs to be handed in before/on February 1 at 23.59. You are strongly encouraged to work together!

Teacher

For additional information about the course, please contact Roland Geraerts. Also two PhD students, i.e. Wouter van Toll (also scientific programmer) and Arne Hillebrand, and our scientific programmer, Angelos Kremyzas, will be involved.

A crowd at the Dom square in Utrecht.