How to find shortest path in dynamic situation

Question

Some days ago, Someone ask me, If we have some agents in our environment, and they want go from their sources to their destinations, how we can find the total shortest path for all of them such that they shouldn't have conflict during their walk.

The point of problem is all agents simultaneously walking in environment (which can be modeled by undirected weighted graph), and we shouldn't have any collision. I thought about this but I couldn't find optimum path for all of them. But sure there are too many heuristic ideas for this problem.

Assume input is graph G(V,E), m agents which are in: S₁, S₂,...,S_m nodes of graph in startup and they should go to nodes D₁,...D_m at the end. Also may be there is conflict in nodes S_i or D_i,... but these conflicts are not important they shouldn't have conflict when they are in their internal nodes of their path.

If their path shouldn't have same internal node, It will be kind of k-disjoint paths problem which is NPC, but in this case paths can have same nodes, but agent shouldn't be in same node in same time. I don't know I can tell the exact problem statement or not. If is confusing tell me in comments to edit it.

Is there any optimal and fast algorithm (by optimal I mean sum of length of all paths be as smallest as possible, and by fast I mean good polynomial time algorithm).

Answer 1

A Google search reveals two links that might be helpful:

• Cooperative path planning for multi-robot systems in dynamic domains
• Optimizing schedules for prioritized path planning of multi-robot systems

Edit: From the book chapter (first link):

There are various approaches to path planning in multi-robot system [sic], however, finding the optimal solution is NP-hard. Hopcraft et al. (1984) simplify the planning problem to the problem of moving rectangles in a rectangular container. They proved the NP-hardness of finding a plan from a given configuration to a goal configuration with the least amount of steps. Hence, all feasible approaches to path planning are a compromise between efficiency and accuracy of the result.

I can't find the original paper by Hopcroft online, but given that quote, I suspect the problem they reduced the navigation task to is similar to Rush Hour, which is PSPACE-complete.