如何在动态情况下找到最短路径 [英] How to find shortest path in dynamic situation

问题描述

几天前，有人问我，如果我们的环境中有一些特工，他们想从他们的源头到目的地，我们如何才能找到所有这些人的最短路径，从而使他们不应该拥有

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.

假设输入是图G（V，E），其中m个代理位于：S _{1 <图中的/ sub>，S 2 ，...，S m 个节点，它们应转到节点D 1 ..。 .D m 结尾。也可能在节点 S i 或 D i 中存在冲突，但是这些冲突不是重要的是，当它们位于路径的内部节点中时，它们应该不会发生冲突。}

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.

如果其路径中不应具有相同的内部节点，这将是< a href = http://www.shannarasite.org/kb/kbse48.html rel = noreferrer> k不相交的路径 问题是NPC，但在这种情况下，路径可以具有相同的节点，但是代理不应同时位于同一节点中。我不知道我能否说出确切的问题陈述。如果感到困惑，请在评论中告诉我进行编辑。

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).

推荐答案

Google搜索显示了两个可能有用的链接：

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

编辑：：从书籍章节（第一个链接）：

From the book chapter (first link):

多机器人系统中路径规划的方法[原文如此]，但是，找到
最优解是NP-har d。 Hopcraft等。 （1984）将规划问题简化为在矩形容器中移动矩形的
问题。他们证明了
的NP难度，可以找到从给定配置到目标配置的计划，而该配置的步阶最少。因此，所有可行的路径规划方法都是效率
与结果准确性之间的折衷。

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.

在网上找到Hopcroft的原始论文，但鉴于此报价，我怀疑他们将导航任务简化为类似于高峰时间，已完成PSPACE。

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.

这篇关于如何在动态情况下找到最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！