TU 6: From Single-Agent Pathfinding to Multi-Agent Pathfinding and in Between

Ariel Felner and Nathan Sturtevant

Monday June 23rd, 2014. (AM - half day)

The aim of the tutorial is to cover some of the heuristic search work that has been done outside of the planning community but that might very relevant to planning. We aim to focus on the different characteristics and search methods that are used for polynomial domains which are usually described explicitly and those for exponential domains which are described implicitly. In particular we will discuss single-agent pathfinding domains (e.g., GPS, game maps) where the state spaces are polynomial and related search algorithms and heuristics. We will then focus on exponential domains (e.g., Rubik's cube) and related techniques. In addition we will cover some work that has been done to combine these two aspects such as large-scale search (on disk) and the multi-agent pathfinding problem.