Path Planning 2016-2017
|Updates | General information | Course overview | Schedule | Assignments | Papers | Grading | Teacher|
This course will be renamed to Crowd simulation in 2017-2018.
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.
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.
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.
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.
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
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
you need to create the footage yourself. You can use e.g.
Fraps to capture a relevant part.
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:
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.
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:
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:
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:
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.
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:
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.
There will be no exam but grading will depend on the
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.
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!
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.