<p>Quoting from <a href="http://www.jair.org/papers/paper3370.html" rel="nofollow noreferrer">Wang and Botea 2011</a>:</p>
<blockquote>
<p>An <em>instance</em> is characterized by a graph representation of a map, and a non-empty collection of mobile units <span class="math-container">$U$</span>. Units are homogeneous in speed and size. Each unit <span class="math-container">$u \in U$</span> has an associated start-target pair <span class="math-container">$(s_u, t_u)$</span>. All units have distinct starting and target positions.</p>
<p>The objective is to navigate all units from their start positions to the targets while avoiding all fixed and mobile obstacles.</p>
</blockquote>
<p>The MAPP algorithm presented in this paper is complete for most instances of this (Multi-Agent Path Planning) problem.</p>
<p>After implementing MAPP myself (even using the suggested &quot;replanning with counting&quot; 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.</p>
<p>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 <a href="http://en.wikipedia.org/wiki/Real-time_strategy" rel="nofollow noreferrer">RTS</a>, for example. Are there better algorithms for these kinds of instances, or better repositioning strategies for MAPP?</p>

CC BY-SA 3.0
2014-03-02T12:52:32.737Z
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](http://cs.stackexchange.com/) 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.
Artem Kaznatcheev
CC BY-SA 3.0
2014-03-02T23:12:28.500Z
That makes sense, thanks - I shortened it down to what seemed like the most relevant theoretical portion.
Phylliida
<ds.algorithms><graph-algorithms><shortest-path>
Multi-Agent Pathfinding
Phylliida
# Multi-Agent Pathfinding

(Asked by: username_0 on 2014-02-27)

Quoting from [Wang and Botea 2011](http://www.jair.org/papers/paper3370.html):

> 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](http://en.wikipedia.org/wiki/Real-time_strategy), for example. Are there better algorithms for these kinds of instances, or better repositioning strategies for MAPP?

**Tags:** ds.algorithms, graph-algorithms, shortest-path
> **Comments:**
> **username_1**: 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](http://cs.stackexchange.com/) 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.  
> **username_0**: That makes sense, thanks - I shortened it down to what seemed like the most relevant theoretical portion.  

---

## 0 answers

