网站开发环境有哪些,门户网站 建设 如何写,电商站外推广平台有哪些,深圳高端设计公司0. 简介
作为路径规划而言#xff0c;不单单有单个机器人自主路径规划#xff0c;近年来随着机器人行业的兴起#xff0c;多机器人自主路径规划也越来越受到关注#xff0c;对于多智能体寻路(MAPF)。一般的操作会给定一个地图、机器人集群、以及它们的初始位置和目的地不单单有单个机器人自主路径规划近年来随着机器人行业的兴起多机器人自主路径规划也越来越受到关注对于多智能体寻路(MAPF)。一般的操作会给定一个地图、机器人集群、以及它们的初始位置和目的地MAPF会最终输出一组没有碰撞的路径用于控制机器人集群完成运动。《Iterative Refinement for Real-Time Multi-Robot Path Planning》文中认为迭代细化MAPF是可取的原因有三:1)多智能体优化是棘手的2)次优解可以立即获得3)在线场景中需要考虑的时间有限所以要求MAPF是实时规划的。
文中的方案使用次优MAPF求解器来快速获得初始解然后迭代两个过程:1)选择代理子集2)使用最优MAPF求解器来优化所选代理的路径同时保持其他路径不变。由于单个最优求解器只会优化所选代理机器人的路径因此该方案可以快速生成足够有效的解决方案同时提供高可伸缩性。相应的代码也在Github上开源了可以这么说这套方法还是很有意义的
1. 文章贡献
文中提出了一个通用的框架基于现有求解器的有效组合可以快速的提供anytimeMAPF求解。 文中的框架首先使用次优MAPF求解器快速获得初始可行解然后使用最优MAPF求解器找到良好的邻域解。精确地说该框架通过选择一组代理并使用最优求解器来细化它们的路径同时保持其他路径固定迭代地细化解决方案。尽管在细化过程使用了最优求解器但是每次细化都能快速完成因为它解决的是一个子问题其大小取决于选择的代理机器人数量通常比原问题小得多。我们还提出了合理的候选人用于选择代理子集。文中研究了在各种基准测试中该方法的有效性并经验地发现在小型实例中该框架在短时间内几乎收敛到最优并且即使对于非常大的实例即大环境和/或许多代理也保持着高效响应。换句话说它比先前的技术带来了许多实际优势。从更广泛的角度来看我们的研究也可以被看作是解决一个非常大规模的邻域搜索[24]。更接近我们的概念Balyo等人[25]研究了针对独立于领域的规划问题的局部重新规划以优化最长时间。它重复以下操作创建一个子问题通过基于SAT的技术获得一个最优子解并用新的解决方案替换原来的部分解决方案。
2. 主要框架
该框架首先使用次优MAPF求解器获得初始解决方案然后迭代地细化解决方案的选定部分即选定代理子集的路径使用最优MAPF求解器。我们在算法1中给出了伪代码 下面我们来详细的看一下第1行输入的是次优求解器快速获得初始可行解决方案。在第二行中我们称所用的次优MAPF求解器为初始求解器。如果初始求解器未能获得解决方案则框架以失败告终;否则开始细化也就是3-6行里面的内容。细化重复以下两个过程直到中断:
使用当前解决方案π [第4行]创建修改集M ⊆ A。使用最优MAPF求解器[第5行]改变M中代理的路径来细化当前解决方案π。我们称这个求解器为细化求解器。细化求解器只改变M中代理的路径M中代理以外的路径不变。细化继续进行直到中断例如超时、达到预定迭代次数、不再有改进时、用户中断等。 最终框架返回最终解决方案[第7行]。
上文中提到的初始求解器可以是任何次优MAPF求解器只要它能提供可行解即可。作为细化求解器最好使用从最优求解器改编的版本。改编很简单让它为M中的代理规划路径并将其他代理视为动态障碍。例如对于CBS算法只为M中的代理求解MAPF同时禁止低级别搜索使用M中代理以外的所有空间时间对。确切地说细化求解器并不局限于最优MAPF求解器可以使用单机器人的求解器。要求是细化解决方案从原始解决方案不变差。考虑到M中代理以外的路径成本不变要求是M中代理的路径成本在细化之前和之后都不会增加。
3. 细化求解器性质与要求
下面有一些性质显然是由对细化求解器的要求所设定的。
3.1 定理1(单调性)
对于算法1中的每次迭代解决方案成本都是不增加的。 一个关键点是细化求解器重新计算所选子集M一部分机器人中代理的路径而不是所有代理的集合A所有机器人。与直接使用最优求解器解决原问题相比细化求解器在每次迭代中解决的问题明显小得多确保框架即使对于大量代理也是可扩展的。同时下面有几种方法来有效的降低计算的时间。
A.提前终止早停 即使细化求解器解决的子问题与原问题相比计算量已经是较小的了但是如果本身的 ∣ M ∣ |M| ∣M∣仍然太大细化仍然可能需要很长时间。在这种情况下最好通过返回当前解决方案来中止当前细化然后使用新的集合 M M M开始新的迭代。标准可以是超时或使用细化求解器中搜索树大小的阈值。
B.局限性 作为一个限制该框架可能具有局部最小值并且没有来自最优解的次优性界限。 命题1(没有次优性界限)考虑最优成本 c ∗ c^* c∗。在算法1中总是 c ≤ w c ∗ c≤wc^* c≤wc∗除非将 A A A本身选为修改集 M M M其中 c c c是每次迭代中的解决方案成本。 证明考虑图1中的一个例子。假设初始解决方案将 a 1 a_1 a1分配给顺时针路径(成本 k k k)和 a 2 a_2 a2分配给逆时针路径(成本1)。当k≥6时这就不是最优的模型了因为 a 1 a_1 a1可以采取逆时针路径并经过 a 2 a_2 a2来移动到目标处总成本6。除非 M ≠ A M ≠ A MA否则细化的解决方案不变。假设 w ≥ 1 w≥1 w≥1使得 c ≤ w c ∗ c≤wc^* c≤wc∗。我们可以取任意 k k k与 w w w的存在相矛盾。
3.2 定理2局部最小值存在
根据初始解决方案除非将A本身选为M否则可能无法达到最优解。
注意当 M A M A MA时细化求解器必须能够解决原始MAPF问题。
4. 修改集选择
我们从上面可以看到在优化的时候修改集的选择会影响到整个系统的性能而如何有效的选择修改集这个就非常重要了。修改集是框架的重要组成部分其设计会影响计算时间和解决方案质量等性能。本节定义了几个选择规则以提供合理的候选修改集。
4.1 随机的
一个天真的方法是随机挑选一个代理子集。然后修改集的大小 M M M就是一个用户指定的参数。需要注意的是大的 M M M修改有机会在一次迭代中很大程度上降低成本但由于子问题变得具有挑战性因此需要花费时间进行细化。
4.2 单一代理
这个规则总是选择一个单一的代理因为 M M M可以被视为前一个规则随机的一个特例。即使只有一个代理成本也可能因细化而降低。在这种情况下细化只是一个单一代理的路径寻找问题可以在没有 M A P F MAPF MAPF求解器的情况下有效地计算出来例如通过 A ∗ A^∗ A∗来计算即可可以简化为一个机器人在其余障碍物机器人中规划出来的最优路径。
4.3 着重目标
考虑图2中的一个例子。假设当前的解决方案是 π 1 ( v 2 , v 3 , v 6 , v 3 , v 3 ) π1 (v2, v3, v6, v3, v3) π1(v2,v3,v6,v3,v3) 和 π 2 ( v 1 , v 2 , v 3 , v 4 , v 5 ) π2 (v1, v2, v3, v4, v5) π2(v1,v2,v3,v4,v5) 。代理人 a 1 a_1 a1不能实现更短的路径因为代理人 a 2 a_2 a2在第2个时间步长(第三个值)使用了 a 1 a_1 a1的目标即v3。一般来说对于 a i a_i ai来说理想成本 d i s t ( π i [ 0 ] , g i ) dist(π_i[0], g_i) dist(πi[0],gi)和实际成本成本 ( a i , π ) (a_i, π) (ai,π)之间存在差距的一个原因可能是另一个代理人 a j a_j aj在时间步骤 t ≥ d i s t ( π i [ 0 ] , g i ) t≥dist(π_i[0], g_i) t≥dist(πi[0],gi)时使用了 a i a_i ai的目标即 g i g_i gi。至少在 t t t之前 a i a_i ai不能到达 g i g_i gi并留在那里。在这种情况下需要联合完善 a i a_i ai和 a j a_j aj的路径。这一观察促使我们创建了一个简单的规则将当前的解决方案 π π π和一个代理 a i a_i ai作为输入。
4.4 围绕目标的局部修复
这是上一条规则关注目标的一个特例。再次假设图2的例子 π 1 ( v 2 , v 3 , v 6 , v 3 , v 3 ) π1(v2, v3, v6, v3, v3) π1(v2,v3,v6,v3,v3) π 2 ( v 1 , v 2 , v 3 , v 4 , v 5 ) π2 (v1, v2, v3, v4, v5) π2(v1,v2,v3,v4,v5)。在聚焦目标focus-at-goals中 a 1 a_1 a1的 M M M是 { a 1 , a 2 } \{a_1, a_2\} {a1,a2}因此细化求解器必须用两个代理解决一个子问题然而这种努力可以减少。考虑为 a 1 a_1 a1获得一个更好的路径忽略 π 2 π_2 π2。在这个例子中通过目标周围的局部修复获得一条新的路径不需要搜索 ( v 2 , v 3 , v 3 , v 3 , v 3 ) (v2, v3, v3, v3, v3) (v2,v3,v3,v3,v3)。接下来为 a 2 a_2 a2计算一条路径同时避免与这条新路径和其他代理的路径发生碰撞。如果两条新路径的成本之和小于原始路径就用新路径替换 π 1 π_1 π1和 π 2 π_2 π2。由于搜索工作量减少预计细化工作会更快完成。一般来说当 π i . . . g i v g i . . . g i π_i...g_ivg_i...g_i πi...givgi...gi其中 v ≠ g i v ≠ g_i vgi而另一个代理 a j a_j aj在该时间步长使用 g i g_i gi时可以应用这一规则。
4.5 使用MDD
给定一个单一的路径成本 c c c从 π i [ 0 ] π_i[0] πi[0]到 g i g_i gi的一组路径可以紧凑地表示为一个多值决策图MMDD[35]一个有向无环图其中一个顶点是一对位置 v ∈ V v∈V v∈V和一个时间步长 t ∈ N t∈N t∈N。
在该时间段从起点出发的可达位置从该时间段到目标的可达位置。 让MDDc i是一个成本为 c c c的 a i a_i ai的MDD图3显示了两个例子。 M D D 1 2 MDD^2_1 MDD12和 M D D 1 3 MDD^3_1 MDD13。MDD在MAPF求解器中经常使用[28], [36]。
…详情请参照古月居
