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.
- Find path for each agent separately with DeepQN approach.
- 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.