# Multi-Agent Pathfinding

Quoting from Wang and Botea 2011:

An instance is characterized by a graph representation of a map, and a non-empty collection of mobile units $$U$$. Units are homogeneous in speed and size. Each unit $$u \in U$$ has an associated start-target pair $$(s_u, t_u)$$. All units have distinct starting and target positions.

The objective is to navigate all units from their start positions to the targets while avoiding all fixed and mobile obstacles.

The MAPP algorithm presented in this paper is complete for most instances of this (Multi-Agent Path Planning) problem.

After implementing MAPP myself (even using the suggested "replanning with counting" technique), it seemed that many of the solutions obtained were far from optimal in path length, having many units that went near their goals than back near their starts multiple times.

Specifically, I'm interested in the subset of this problem that has groups of units very near each other and groups of goals very near each other, as you might see in an RTS, for example. Are there better algorithms for these kinds of instances, or better repositioning strategies for MAPP?

• You are asking a lot of things in one question (I count 9 questions, here), is it possible to focus on one specific point? It is alright to split up into several different posts here or on CS.SE for those parts that are not research level or are implementation oriented (like the questions in point 3). The more precise you make your question, the more likely we are to give you a useful answer. Mar 2 '14 at 12:52
• That makes sense, thanks - I shortened it down to what seemed like the most relevant theoretical portion. Mar 2 '14 at 23:12