Abstract

Pathfinding is an important underlying task for autonomous agents such as mobile robots, computer game characters, and aircrafts on airport taxiways.  Abstracting the environment into a navigation graph enables a mobile unit to use heuristic search, such as A*, to plan a path to its goal. When multiple units move simultaneously inside the shared space, the solu-tion also involves navigating every unit to its target without collisions. In a fully known, static, two-dimensional environ-ment, finding an optimal solution to a multi-agent problem is NP-hard[Ratner and Warmuth, 1986]. With both the branch-ing factor and the number of states growing exponentially in the number of units, a centralised search in the combined state space of all units is intractable in practice even on relatively small collections of units. However, problems in applications such as robotics, logistics, military operations planning, dis-aster rescue, and massively multi-player online games often involve massively many agents. My thesis addresses scalabil-ity as well as providing tractability and completeness guaran-tees in multi-agent pathfinding.