Secret Page
Congratulations! You have reached the course's secret page, on which you can find extra material and food for thought.
Olifantenpaadjes
In 2011, two students (Robin and Jessica) took a lot of pictures of an interesting phenomemon, olifantenpaadjes ('elephant paths'). This concerns the human's urge to take the shortest path. And here's another set of examples.
Videos
There are just no reasons for having traffic jams!
In this video, a large crowd in London slowly freezes, awaiting for people's reactions.
This prank was repeated in Paris. (Recall the question: what is natural behavior?)
In Japan, things got more personal.
And then there's a thing called synchronized walking, which takes real-life collision avoidance to the exteme.
A* is more powerful than you might think
An excellent tutorial on the A* algorithm is provided by Amit Patel. Since its discovery by P. Hart and colleagues in 1968, the algorithm has been extended extensively, including dynamic versions (e.g. D*-Lite) and ones that take care of path quality. Recently, a great overview has been given by Maxim Likhachev and Sven Koenig at the workshop/tutorial Real-Time Planning in Dynamic and Partially-Known Domains during the ICRA 2010 conference. (Roland's paper on the Explicit Corridor Map was also presented there.) The slides of the workshop are provided on that site but can also be downloaded here. Some nice visualisations of search algorithms are found here.
PRM power
The first paper on the PRM, called A random approach to motion planning, was published by Mark Overmars in 1992. The PRM was also referred to as the Probabilistic Path Planner, and you can imagine that the English, but the French in particular, must have laughed when they considered its acronym. While the random aspect of the algorithm was considered the key element to efficiently handle high-dimensional problems, further research showed that this was untrue because deterministic sampling methods, such as Halton sampling, performed equally well. Its succes can be explained by the fact that it did not require the construction of an explicit description of the configuration space. This description was assembled by sampling the space. Checking whether these samples were collision-free was an efficient operation in general. Further analysis showed that not coverage (by the samples) but getting the samples connected was the main problem, especially when the problems got more complicated, i.e. when a narrow passage was present.
Mi casa es su casa
A while ago, the CASA 2010 conference and its accompanying workshop on crowds was held. Their focus seemed to be the simulation of natural crowds. Rabiaa and Foudil proposed a method for creating realistic pedestrian navigation. A key element was to use semantic information of the environment, based on the characters' perception. Perception was also a key ingredient in the paper from Trinity College Dublin's group where they studied how to populate the environment. The zone of perception was studied by Sterlin et al. which led to more believable pedestrians trajectories. While these papers focused on simulation and collision avoidance, Allbeck's paper focused on creating populations that inhabit a space as opposed to passing it. Another approach to creating natural crowds is to learn and imitate its behavior. For instance, Charalambous and Chrysanthou tracked the steering behavior of crowds from video sources and generated databases of examples. These databases were then used to learn rules for steering the crowd. Similarly, Karim and Sanza used a learning approach (by imitating the user's actions) to generate the behavior of pedestrians.
Secrets from the industry
Martijn Bloemheuvel, a former student of this course, had an interesting conversation with Austin Ellis (lead engineer on Red Alert 3).
Hungry for more information?
Many high-quality resources (e.g. PhD theses) on path and motion planning can be found on the IEEE RAS Technical Committee website: Algorithms for Planning and Control of Robot Motion.