Multi agent path following with collision avoidance with pre-determined path

Question

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.

Answer 1

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.