<p>In general, your problem is NP-hard, naturally (if you have arbitrarily many agents and an arbitrary arena, of course).</p>
<p>Combining paths will naturally cause collisions (otherwise we wouldn't need centralized planners, or clever decentralized approaches). So just thinking of clever ways to combine existing paths may prove difficult.</p>
<p>A relatively straightforward approach you can take is to adapt CBS (Conflict-based search) to your approach, as follows:</p>
<ol>
<li>First, plan for each agent separately.</li>
<li>Check if the combined plan violates the condition of being 1 block away at any point. If it does (say if agents <span class="math-container">$i$</span> and <span class="math-container">$j$</span> are within distance 1 of each other at time <span class="math-container">$t$</span>) create a set of &quot;collision constraints&quot; as CBS does, that prevent agent <span class="math-container">$i$</span> from being within 1 step of the location of agent <span class="math-container">$j$</span> at time <span class="math-container">$t$</span>, and vice-versa.</li>
<li>Choose one of the collision constraints you defined, and replan for the agent that violates the constraint (e.g., <span class="math-container">$i$</span> in the first constraint, or <span class="math-container">$j$</span> in the second).</li>
<li>Repeating this process, build a &quot;constraint tree&quot;, and keep replanning until you have no more collisions.</li>
</ol>
<p>The fact that agents are allowed to stay in place might be technically helpful, but in theory it doesn't matter much, if the arena has many obstacles, since e.g., if an agent is blocking some corridor, it has to move in order to clear the way for the others.</p>

CC BY-SA 4.0
2021-02-07T19:16:53.380Z
Oh thanks for such a clarifying detailed response. I got your point looking into CBS then.
Sayan Dey
CC BY-SA 4.0
2021-02-07T19:35:12.277Z
btw, I have to take all the paths in consideration for each agent until I get a combination for all obeying the constraints. As I will be providing the paths for each agent to the high level planner in an ordered fashion. (first shorter paths, then longer paths)
Sayan Dey
CC BY-SA 4.0
2021-02-07T19:40:06.670Z
@SayanDey - not sure I understand. When you're replanning for each agent, you simply look for the shortest path to the target, while satisfying the constraints of the nodes in the constraint tree. It might create additional collisions.
Shaull
CC BY-SA 4.0
2021-02-08T06:01:13.760Z
Yah that answers my doubt.
Sayan Dey
CC BY-SA 4.0
2021-02-07T18:48:35.650Z
2021-02-07T19:40:35.353Z
2021-02-07T19:40:35.353Z
Shaull
<p>I am working on a multi-agent pathfinding algorithm. I am aware of other techniques, but planned on the folowing strategy only.</p>
<p>The problem:
There is 12x12 grid, with a few solid blockades within them. 12 agents, each have a predefined start and goal cell. I need to find a sub optimal path for all the agents. <strong>Two agents need to have atleast one blank cell between them. Each agent takes one cell at a time only. Agent stalling is allowed.</strong></p>
<p>My strategy:</p>
<ol>
<li>Find path for each agent separately with DeepQN approach.</li>
<li>Combine the single paths to make the agents reach their destination.</li>
</ol>
<p>My problem:
I have found optimal path for each agent separately with DeepQN approach.
But backtrack type approach for combining the paths is taking impractically huge amount of time to converge (converges for max 4 agents only).</p>
<p>I am looking for an algorithm that will help me combine the single paths of each agent with collision avoidance.</p>
<p>P.S. All agents have to be present in the grid at 1st timestep. Stalling is allowed. An agent can be removed from the grid once it reaches it's goal.</p>

<graph-theory><graph-algorithms><shortest-path><reinforcement-learning>
Multi agent path following with collision avoidance with pre-determined path
Sayan Dey
# Multi agent path following with collision avoidance with pre-determined path

(Asked by: username_0 on 2021-02-07)

I am working on a multi-agent pathfinding algorithm. I am aware of other techniques, but planned on the folowing strategy only.

The problem:
There is 12x12 grid, with a few solid blockades within them. 12 agents, each have a predefined start and goal cell. I need to find a sub optimal path for all the agents. **Two agents need to have atleast one blank cell between them. Each agent takes one cell at a time only. Agent stalling is allowed.**

My strategy:

1. Find path for each agent separately with DeepQN approach.
2. Combine the single paths to make the agents reach their destination.

My problem:
I have found optimal path for each agent separately with DeepQN approach.
But backtrack type approach for combining the paths is taking impractically huge amount of time to converge (converges for max 4 agents only).

I am looking for an algorithm that will help me combine the single paths of each agent with collision avoidance.

P.S. All agents have to be present in the grid at 1st timestep. Stalling is allowed. An agent can be removed from the grid once it reaches it's goal.

**Tags:** graph-theory, graph-algorithms, shortest-path, reinforcement-learning


---

## 1 answers

### Answer by username_1 on 2021-02-07. Score: 1 | Accepted answer

In general, your problem is NP-hard, naturally (if you have arbitrarily many agents and an arbitrary arena, of course).

Combining paths will naturally cause collisions (otherwise we wouldn't need centralized planners, or clever decentralized approaches). So just thinking of clever ways to combine existing paths may prove difficult.

A relatively straightforward approach you can take is to adapt CBS (Conflict-based search) to your approach, as follows:

1. First, plan for each agent separately.
2. Check if the combined plan violates the condition of being 1 block away at any point. If it does (say if agents $i$ and $j$ are within distance 1 of each other at time $t$) create a set of "collision constraints" as CBS does, that prevent agent $i$ from being within 1 step of the location of agent $j$ at time $t$, and vice-versa.
3. Choose one of the collision constraints you defined, and replan for the agent that violates the constraint (e.g., $i$ in the first constraint, or $j$ in the second).
4. Repeating this process, build a "constraint tree", and keep replanning until you have no more collisions.

The fact that agents are allowed to stay in place might be technically helpful, but in theory it doesn't matter much, if the arena has many obstacles, since e.g., if an agent is blocking some corridor, it has to move in order to clear the way for the others.

> **Comments:**
> **username_0**: Oh thanks for such a clarifying detailed response. I got your point looking into CBS then.  
> **username_0**: btw, I have to take all the paths in consideration for each agent until I get a combination for all obeying the constraints. As I will be providing the paths for each agent to the high level planner in an ordered fashion. (first shorter paths, then longer paths)  
> **username_1**: @SayanDey - not sure I understand. When you're replanning for each agent, you simply look for the shortest path to the target, while satisfying the constraints of the nodes in the constraint tree. It might create additional collisions.  
> **username_0**: Yah that answers my doubt.  

---

