基于冲突的搜索,以实现最佳的多智能体寻路

Submitted by neurta on Tue, 01/12/2021 - 16:31
启发式搜索

1 。介绍

单主体寻路是在图中两个顶点之间找到路径的问题。它是AI中一个基本而重要的问题,已经得到了广泛的研究,因为这个问题可以在GPS导航[49],机器人路由[8][3],计划[6][23]和网络路由[ 7],以及许多组合问题(例如难题)[28][27]。通常使用基于A *算法的搜索算法来最佳解决寻路问题[22]。此类算法执行由F(ñ)=G(ñ)+H(ñ),在哪里 G(ñ)是从开始状态到状态n的最短已知路径的成本,并且H(ñ)是一个启发式函数,用于估计从n到最接近目标状态的成本。如果启发式函数h可允许的,这意味着它永远不会高估从n到目标的最短路径,那么A *(以及由相同成本函数指导的其他算法)可以保证找到从开始状态到目标的最佳路径。目标状态(如果存在)[11]

多代理寻路(MAPF)的问题是单剂寻路问题为的推广ķ>1个代理商。它由一个图和许多代理组成。对于每个代理,给出了一个唯一的起始状态和一个唯一的目标状态,任务是在代理在其移动过程中不会发生冲突的约束下,查找所有代理从其起始状态到目标状态的路径。在许多情况下,还有一个附加目标,即最小化累积成本函数,例如每个代理商达到其目标所需的时间步长之和。MAPF在视频游戏,交通控制[43][12],机器人技术[1]和航空[31]中具有实际应用。

求解MAPF的算法可以分为两类:最优次优求解器。为MAPF问题找到最佳解决方案是NP-hard [56],因为状态空间随代理的数量呈指数增长。当代理数量很大时,通常使用次优求解器。在这种情况下,目标是快速找到不同代理的路径,并且通常很难保证给定的解决方案是最佳的。

本文解决的问题是找到MAPF问题的最佳解决方案。最佳求解器通常在代理数量相对较小且任务是找到最优,成本最低的解决方案时应用。可以将其形式化为一个全局的单代理搜索问题。因此,传统的求解MAPF的最佳方法是使用基于A *的搜索[35][45]。搜索树中的节点由所有代理在时间t处的一组位置组成。起始状态和目标状态分别由不同代理的初始位置和目标位置组成。给定一个具有分支因子b的图,有Ø(b) 任何单个代理的可能移动,因此A *搜索的分支因子为 Ø(bķ)这是代理商数量的指数。自然,基于A *的搜索算法可以最佳地解决此问题,但是它们可能运行很长时间或耗尽可用内存。

本文的第一部分对MAPF研究进行了调查。我们将所有现有工作分为两个主要类别:最优和次优。然后,我们进一步对解决次优问题的不同方法进行了分类。这可以通过有助于这些分类的一致术语来完成。在本文的第二部分,我们介绍了一种用于最优求解MAPF的新方法。首先,我们提出了一种针对MAPF的新颖的基于冲突的形式化方法,以及一种相应的新算法,称为基于冲突的搜索(CBS)。CBS是一种两级算法,分为高级搜索和低级搜索。代理使用默认路径初始化,其中可能包含冲突。在高级搜索是在执行约束树(CT),其节点包含单个代理的时间和位置约束。在CT中的每个节点上,对所有代理执行低级搜索。低级搜索返回的单代理路径与在任何CT节点上给出的约束集一致。如果在运行低级别代理之后仍存在冲突,即两个或多个代理同时位于同一位置,则将关联的高级节点声明为非目标节点,然后进行高级搜索通过添加更多具有解决新冲突的约束的节点来继续操作。

与基于A *的方法以及其他方法相比,我们研究了CBS算法的行为并讨论了其优缺点。基于问题的特征,我们显示了CBS比以前的方法有效得多的情况。我们还将讨论CBS的局限性,并展示CBS劣于基于A *的方法的情况。提供的实验结果支持了我们的理论理解。尽管CBS在某些情况下无效,但在许多情况下CBS优于EPEA * [15][20],这是针对此问题的基于A *的最新方法。具体来说,我们在开放式网格以及Sturtevant寻路数据库中的许多基准游戏地图上进行了实验[47]。结果表明,在许多领域中,CBS优于基于A *的方法和最新的ICTS [42]

接下来,我们通过将CBS推广到称为元代理CBS(MA-CBS)的新算法中来缓解CBS的最坏情况性能。在MA-CBS中,任何一对代理之间允许的冲突数由预定义参数B限制。当冲突数超过B时,冲突代理将合并为元代理,然后由低级求解器将其视为联合复合代理。在低级搜索中,MA-CBS使用任何可能的完整MAPF求解器来查找元代理的路径。因此,MA-CBS可以看作是插入了低级求解器的求解框架。不同的合并策略会导致不同的特殊情况。原始的CBS算法对应于极端情况,其中乙=∞(永远不会合并代理),而独立检测(ID)框架[45]是另一种极端情况,乙=0(总是在发生冲突时合并代理)。最后,我们介绍了MA-CBS的实验结果,该结果表明MA-CBS在所有领域都比其他方法优越。另外,在附录A中,我们介绍了CBS的一种变体,它的存储要求在CT深度上是线性的。

该研究的初步版本先前已经出现[38][39]。本文包含对CBS算法和MA-CBS框架的更全面描述,并与其他MAPF算法进行了更广泛的理论分析和实验比较。

2 。问题定义和术语

存在MAPF问题的许多变体。现在,我们定义问题,并在问题的一般常用变体中描述算法[45][46][42][38][39]。此变体尽可能通用,以允许CBS适用,并且它包含许多子变体。然后,在第6.1节中,我们描述了在实验环境中使用的特定子变量。最后,在第7节中,我们简要讨论了如何将我们的新算法修改为其他MAPF变体。

2.1 。问题输入

输入多代理寻路问题(MAPF)为:

(1)

有向图 G(V,Ë)。图的顶点是代理的可能位置,而边是位置之间的可能过渡。

(2)

k个代理商已标记一种1个,一种2…一种ķ。每个代理商一种一世 有一个起始顶点 开始一世∈V 和目标顶点 目标一世∈V。

时间被离散为时间点。在时间点Ť0 代理人 一种一世 位于位置 开始一世。

2.2 。动作

在连续的时间点之间,每个代理可以执行到相邻顶点的移动动作或等待动作,以使其当前顶点保持空闲。在给定的时间步长中,有很多方法可以解决一系列代理相互跟随的可能性。这可能是不允许的,可能仅在链中的第一个代理移动到空位时才被允许,甚至在不包含任何空位的循环链中也可能被允许。我们的算法适用于所有这些变体。

2.3 。MAPF约束

MAPF中的主要限制在于,每个顶点在给定时间最多只能被一个代理占据。也可能存在一种约束,不允许多个代理在连续的时间步长之间穿越同一边。一个冲突就是一个违反约束的情况下。

2.4 。MAPF任务

MAPF问题的解决方案是一组无冲突的路径,每个代理一个路径,其中一个代理路径 一种一世 是一个序列 {移动,等待} 行动,如果 一种一世 从以下开始执行此一系列操作 开始一世,它将最终以 目标一世。

2.5 。成本函数

我们旨在解决给定的MAPF实例,同时最大程度地降低全局累计成本函数。我们在共同成本函数的上下文中描述了本文中的算法,我们称其为成本总和 [12][45][42][38][39]成本总和是所有业务代表对最后一次达到目标且不再离开目标所需的时间步长的总和。找到最优解决方案,即最小的成本总和,已经证明是NP难的[56]

其他成本函数也已在文献中使用。完工时间,例如,是另一种常见MAPF成本函数,直到最后剂到达其目的地,其最小化的总时间(即,最大的单个成本的)。另一个成本函数称为燃料 [16],它对应于所有代理商行进的总距离(等于所消耗的燃料)。实际上,“燃料成本”功能是所有座席的成本总和,其中仅移动动作会产生成本,而等待动作是免费的。另外,也可以对不同的试剂赋予不同的权重。在第7节中,我们展示了如何针对此类成本函数修改算法。

MAPF的某些变体没有要优化的全局成本函数,而是有一组单独的成本函数,每个代理都一个[29]。在这样的变体中,解决方案是成本的向量,每个代理一个。这种成本函数是多目标优化更广泛领域的一部分,不在本文讨论范围之内。在其他MAPF变体中,代理可能是自私的,任务是设计一种机制,使他们合作[5]。在这项工作中,我们假设代理人是完全协作的,并不自私。

Yu和Lavelle [54]研究了MAPF变体,在该变体中,不是给每个代理分配目标位置,而是给出一组目标位置,任务是找到一种将每个代理都带到任何目标位置的解决方案。他们表明,使用网络流可以在多项式时间内解决此MAPF变体。

2.6 。分布式与集中式

MAPF问题可以分为两类:分布式集中式。在分布式设置中,每个代理都有其自己的计算能力,并且可以采用不同的通信模式(例如,消息传递,广播等)。大量工作解决了分布式环境[18][21][2]。相比之下,集中式设置假定具有单个中央计算能力,需要为所有代理找到解决方案。同样,集中式设置还包括以下情况:我们为每个代理提供了一个单独的CPU,但假定完全共享知识,并且由集中式问题解决者控制所有代理。本文的范围仅限于集中式方法,我们将在下一节中介绍许多方法。

2.7 。MAPF问题的示例

图1显示了一个示例2-agent MAPF实例,该实例将在本文中使用。每个代理商(鼠标)必须计划一条通向其各自奶酪的完整路径。代理商一种1个 必须从 小号1个 至 G1个 特工 一种2 必须从 小号2 至 G2。这两个代理都有各自的长度为3的路径:〈小号1个,一种1个,d,G1个〉 和 〈小号2,乙1个,d,G2〉, 分别。但是,这些路径存在冲突,因为它们在时间点都包含状态DŤ2。这些代理之一必须等待一步。因此,最佳的解决方案成本⁎C⁎在此示例中为7。

Image removed.

  1. 下载:下载全图

图1。具有2个代理的MAPF实例的示例。小鼠1和2必须分别到达奶酪1和2的碎片。

3 。集中式MAPF算法概述

假设采用集中式方法的工作可以分为三类。在最近的工作中使用的第一类求解器将MAPF简化为计算机科学中已充分研究的其他问题。第二类求解器由MAPF特定的次优求解器组成。求解器的第三类是最优求解器。本文的重点是最优求解器,但是我们在下面包括对其他类的简要调查。

3.1 。基于约简的求解器

在最近的工作中使用的这类求解器将MAPF减少到计算机科学中已充分研究的其他问题。突出的例子包括降低到布尔可满足性(SAT)[50],整数线性规划(ILP)[55]和答案集编程(ASP)[13]。这些方法返回最佳解决方案,通常是针对制造成本函数设计的。它们效率较低,甚至不适用于成本函数的总和。另外,这些算法通常仅在小问题实例上才具有很高的效率。在大型问题实例上,从MAPF实例到所需问题的转换过程具有非常大的多项式开销,这使这些方法效率低下。

3.2 。MAPF特定的次优求解器

此类算法通常非常高效,但在某些情况下不能保证最优性甚至完整性。当代理数量很大且最佳解决方案难以解决时,通常使用它们。特定于MAPF的次优求解器可以进一步分类为子类。

3.2.1 。基于搜索的次优求解器

基于搜索的求解器通常旨在提供高质量的解决方案(接近最佳),但是在许多情况下它们并不完整。这些求解器的不同之处在于它们对待代理之间的冲突的方式。基于搜索的次优算法的一个突出示例是层次合作A *(HCA *)[43]。在HCA *中,根据某个预定义的顺序一次计划一个代理。一旦第一个代理找到到达其目标的路径,就将该路径写入(保留)到全局保留表中。更具体地说,如果找到任何代理的路径一种一世 是 v一世0=开始一世,v一世1个,v一世2,…,v一世升=目标一世,然后算法记录该状态 v一世Ĵ 被代理商占用 一种一世 在时间点 ŤĴ。预留表可以实现为#vË[RŤ一世CËs×#Ť一世米ËsŤËps,或者使用更紧凑的表示形式,例如用于保留项目的哈希表。在搜索后继代理的路径时,前任代理选择的路径将被阻止。也就是说,代理程序可能无法遍历与先前代理程序冲突的位置。先前已经提出了一种类似于HCA *的方法,用于多主体运动计划[14]。Windowed-HCA *(WHCA *)[43]是几种HCA *变体之一,仅在有限的窗口内执行协作寻路,此后其他代理将被忽略。完美的单一代理启发法通常用于指导此搜索。因为HCA *是为内存有限的游戏而设计的,所以启发式算法无法预先计算,必须在运行时进行计算。

后来的工作通过抽象状态空间的大小扩展了HCA *,以减少构建启发式算法的运行时成本[48]。最后,对WHCA *进行了增强,以便仅将窗口动态地放置在已知的冲突周围,并根据参与冲突的可能性对代理进行优先级排序[4]。。HCA *的想法有一些缺点。首先,当代理程序太多时,可能会发生死锁,并且不能保证HCA *是完整的。其次,HCA *无法为其解决方案的质量提供任何保证,因此解决方案可能远非最佳。最后,HCA *甚至可能大大降低搜索速度。对于HCA *,WHCA *的窗口变体尤其如此。由于各个代理程序都在独立寻找最小长度的解决方案,因此,在有大量可用空间时,代理程序可能会不必要地发生冲突,从而需要花费大量计算成本才能解决。保留表的想法也已用于管理交通路口,在该路口,汽车(代理人)必须越过路口而不会引起碰撞[12]。该系统解决了该问题的在线版本,即汽车到达路口后,一旦驶过路口便消失了。

3.2.2 。基于规则的次优求解器

基于规则的方法包括针对不同场景的特定移动规则,通常不包括大量搜索。代理商根据特定规则计划其路线。基于规则的求解器比计算质量更倾向于以较低的计算成本实现完整性。

TASS [25]和Push and Swap(及其变体)[30][37][10]是两个最近提出的基于规则的MAPF次优算法,它们在多项式时间内运行。1两种算法都使用一组“宏”运算符。例如,推送和交换算法使用“交换”宏,该宏是在两个相邻代理之间交换位置的一组运算符。TASS和Push and Swap都不返回最佳解决方案,仅保证特殊情况下的完整性。TASS仅对于树图是完整的,而Push和Rotate [10]是Push和Swap的变体,对于至少两个顶点始终未被占用的图,即TASS是完整的。ķ≤|V|-2。

在完成所有这些工作之前,需要完成多项式时间算法,该算法对于所有图形[9][34]都是完整的。之前的工作重点是MAPF的一个特定变体,称为卵石运动协调问题(PMC)。PMC与MAPF相似,在MAPF中,每个代理都被视为一个小卵石,每个小卵石都需要移动到其目标位置。

3.2.3 。混合求解器

一些次优的求解器是混合求解器,包括特定的运动规则以及重要搜索。例如,如果图形是网格,则建立类似于交通法规的流量限制可以简化问题[52][24]。网格中的每个行/列都分配有两个方向。建议或迫使代理在每个位置朝指定方向移动,以显着减少冲突的机会和每个顶点的分支因子。这些方法将避免碰撞的优先级放在更短的路径上,并在具有较大开放区域的状态空间中很好地工作。对于一般情况,这些方法并不完整,因为可能会在瓶颈中发生死锁。

Wang和Botea [53]提出了另一种混合求解器。基本思想是预先计算完整路径(P一世),每个代理商(一种一世)。对于每对连续的步骤(pĴ,pĴ+1个∈P)替代子路径也已预先计算。如果代理的原始计算路径一种一世 被其他代理商阻止 一种Ĵ,我们重定向代理 一种一世通过替代路径之一进入旁路。这种方法的主要局限性在于,仅对具有可滑动属性(在[53]中定义)的网格证明它是完整的。目前尚不清楚如何将这种算法推广到不可滑动的网格。

Ryan引入了一种基于搜索的方法来解决MAPF问题,该方法使用抽象来减少状态空间的大小[35]。输入图G分为具有特殊结构的子图,例如集团,大厅和圆环。每个结构代表某种拓扑(例如,大厅是具有任意数量的入口和出口的单链接点的链)。每个结构都有一组基于规则的运算符,例如EnterLeave。一旦在抽象空间中找到了计划,就可以使用基于规则的运算符来得出解决方案。使用这些抽象的一般方法是将整个MAPF问题作为约束满足问题(CSP)解决。每个特殊的子图为CSP求解器增加了约束,使CSP求解器更快[36]。子图分解的效率(就运行时而言)取决于输入图的分区。寻找最佳分区是一个难题,并非总是可行的。开放空间不适用于按定义的结构进行划分,因此该算法在具有开放空间的图上效果较差。

3.3 。最佳MAPF求解器

最佳MAPF求解器通常会搜索一个全局搜索空间,该空间组合了所有k个代理的各个状态。该状态空间被称为k-agent状态空间。在各州ķ -agent状态空间是不同的方式来放置ķ特工潜入|V|顶点,每个顶点一个代理。在开始状态和目标状态中一种一世 位于顶点 开始一世 和 目标一世, 分别。状态之间的运算符是所有代理具有的所有不冲突的动作(包括wait)。给定这个一般状态空间,任何基于A *的算法都可以用来最佳地解决MAPF问题。

我们用这个词 b基础表示单个代理的分支因子,即单个代理可以在一个时间步中移动到的位置数。本文重点介绍4连通网格b基础=5,因为每个特工都可以朝四个基本方向移动或在其当前位置等待。k个代理的最大可能分支因子为b潜在=b基础ķ。当在k -agent状态空间中扩展状态时,所有b潜在可以考虑合并,但只有没有冲突(与其他代理或障碍)的是合法邻居。合法邻居的数量表示为b法律。 b法律=Ø(b基础ķ),因此对于最坏情况的分析,可以考虑 b法律 与...的顺序相同 b潜在,即代理数量(k)呈指数形式。另一方面,在密集图(具有许多代理且具有少量空状态)中,b法律 可以比 b潜在。通常,确定b法律 可能的邻居 b潜在邻居是约束满足问题(CSP),其中变量是代理,值是他们采取的行动,约束是为了避免冲突。此后,我们仅表示b法律由b

3.3.1 。MAPF的允许启发式

为了使用A *更有效地解决MAPF,需要一种非平凡的可允许试探法。一个简单的可允许的启发式方法是对单个代理的单个启发式求和,例如对于4个连接网格的曼哈顿距离或对于欧式图的欧式距离[35]。HCA *通过计算每个代理到目标的最佳距离而忽略了其他代理,从而对此进行了改进。由于此任务严格比使用其他代理进行搜索容易,因此可以将其用作允许的启发式方法。HCA *对每个代理增量执行此计算,而Standley在解决MAPF问题之前先验性地穷举执行计算[45]

我们将这种启发式表示为个人成本启发式(SIC)的总和。形式上,SIC启发式计算如下。对于每个代理一种一世 我们假设不存在其他代理,并计算从状态空间中的所有状态到 目标一世; 这通常是通过反向搜索目标来完成的。多代理A *搜索中采用的启发式方法是所有代理上这些成本的总和。对于图1中的示例问题,SIC启发式为3+3=6。注意,对于上述制造期变体,单个成本的最大值是可允许的启发式方法,其中任务是使经过总时间最小化。

对于较小的输入图,可以通过预先计算输入图G所有对最短路径矩阵,将任何问题配置的SIC启发式存储为查找表。对于较大的图,我们计算从每个状态到给定实例的目标状态的最短路径。但是,必须针对每个目标状态集针对每个问题实例重新计算该值。

3.3.2 。MAPF的A *的缺点

A *总是从扩展状态并将其后继项插入打开列表(表示为OPEN)开始。所有展开的状态都保存在一个封闭列表中(表示为CLOSED)。因此,用于MAPF的A *具有两个缺点。首先,状态空间的大小与代理程序的数量(k)成指数关系,这意味着对于大问题,无法在内存中维持CLOSED。其次,给定状态的分支因子在k中可能是指数的。考虑一个在4个连接的网格上具有20个代理的状态。每个特工最多可以进行5个动作(4个基本方向并等待)。完全生成所有520=9.53×1014甚至起始状态的邻居在计算上也不可行。已经提出以下增强来克服这些缺点。

3.3.3 。通过独立检测减少代理的有效数量

由于MAPF的状态空间在代理数量上是指数级的,因此可以通过减少问题中的代理数量来获得指数级加速。为此,斯坦德利介绍了独立检测框架(ID)[45]

如果每个组都有一个最佳解决方案,则两组代理是独立的,以使两个解决方案不会冲突。ID尝试检测独立的代理组。算法1提供ID的伪代码。首先,每个业务代表都放在自己的组中(第1行)。每个组使用A *(第2行)分别求解。对于给定的一组代理,由A *返回的解决方案是最佳的。然后检查所有组的路径相对于彼此的有效性。如果发现冲突,则将冲突的组合并为一组,并使用A *(第6-7行)进行最佳求解。重复进行重新计划和合并组的过程,直到所有组的计划之间没有冲突为止。产生的组彼此独立。请注意,ID并不完美,因为在ID返回的组中可能没有发现更多独立的子组。

Image removed.

  1. 下载:下载全图

算法1。ID框架。

由于MAPF问题的复杂性通常是代理数量的指数,因此,求解具有ID的MAPF问题的时间取决于解决最大的独立子问题的运行时间[45]。ID可以识别出可以由几个独立子问题的解决方案来构成对k- agent MAPF问题的解决方案。我们用ķ′表示代理有效数量,即最大独立子问题中的代理数量(ķ′≤ķ)。由于问题是代理数量的指数,ID将指数从k减少到ķ′。

考虑 一种*+ID关于我们在图1中的示例问题(第2.7节),但带有其他代理。假设第三代理一种3位于状态D,其目标状态为小号1个。ID将按以下方式工作。为代理商找到成本3的各个最佳路径一种1个 (路径 〈小号1个,一种1个,d,G1个〉)和 一种2 (路径 〈小号2,乙1个,d,G2〉),并为代理商找到了成本为2的路径 一种3 (路径 〈d,一种2,小号1个〉)。验证代理路径时一种1个 和 一种2,状态D发生冲突,并且代理一种1个 和 一种2被合并为一组。在该组上调用A *并返回成本为7的解决方案(代理一种2 在等 乙1个)。该解决方案现已通过代理解决方案进行验证一种3。找不到冲突,算法停止。A *调用的最大组的大小为2。如果没有ID,则A *必须解决3个代理的问题。因此,最坏情况的分支因子从b基础3 至 b基础2。

重要的是要注意,ID框架可以在第7行的任何最佳MAPF求解器(可以保证返回最佳解决方案)的顶部实现。因此,ID可以看作是利用MAPF求解器的通用框架。因此,ID也适用于本文提出的算法(CBS),而不适用于A *。确实,在CBS的实验评估中,我们在CBS之上运行了ID。

3.3.4 。增强ID

为了提高识别独立座席组的机会,Standley提出了使用避免冲突表(CAT)的平局决胜规则,如下所述。为代理找到的路径存储在CAT中。当新成立的合并组使用A *(第7行)求解时,A *搜索会打破联系,而有利于将与其他组(不属于合并的业务代表)的现有计划路径产生最少冲突的州组),存储在CAT中。这种改进的结果是,A *使用避免冲突平局打破的解决方案不太可能引起与其他代理的冲突。结果,代理程序路径更可能是独立的,从而导致实质性的加速。

Standley还提出了ID(EID)的增强版本[45]。在此版本中,一旦发现两组代理发生冲突,则在合并这些组之前调用解决冲突过程。EID尝试通过尝试重新计划一个小组以避免另一小组的计划来解决冲突,反之亦然。为了保持最佳状态,在重新计划期间发现的计划成本必须与该组原始最佳解决方案的成本完全相同。如果组之间的冲突没有解决,则将组合并并一起解决,就像在基本ID中一样。如果解决过程能够解决冲突,则不合并组,并且主循环继续。

3.3.5 。M *

与ID相关的算法是M * [51]。它是基于A *的算法,可根据冲突动态更改分支因子。通常,扩展节点仅生成一个子节点,每个代理都在该子节点中向目标最佳移动。这一直持续到q≥2节点n上的代理。在这种情况下,需要局部增加搜索维数。M *迹线从备份Ñ通过所有的祖先向上Ñ直到根节点和所有这些节点放回OPEN。如果这些节点之一再次扩展,它将生成bq孩子们在q冲突的代理人作出一切可能的行动和ķ-q 无冲突的代理人将采取最佳行动。

称为递归M *(RM *)[51]的增强版本将q个冲突的代理分为多个代理子组,每个代理具有独立的冲突。然后,在每个组上递归调用RM *。名为ODRM * [17]的变体在RM *的基础上结合了Standley的算子分解(请参阅第3.3.7节)。

3.3.6 。避免多余的节点

在某些限制下,已知A *会扩展找到最佳解决方案所需的最少节点数[11]。关于由A *生成的节点数,没有这样的陈述。为了找到最佳解决方案,必须生成某些节点。具有的节点⁎F>C⁎称为剩余节点 [15] ,不需要为了找到一个最佳的解决方案。

剩余节点是所有已生成但从未扩展的节点。生成的节点数是扩展的节点数乘以分支因子。因此,在MAPF中,分支因子在代理程序数量上是指数级的,而剩余节点的数量则可能很大,避免生成它们会大大提高速度[20][19]。挑战在于如何在搜索过程中识别多余的节点。接下来,我们描述尝试检测剩余节点的现有技术。

3.3.7 。算子分解

Standley在他的算子分解技术(OD)中引入了减少多余节点数量的第一步[45]。代理被分配了任意(但固定)的顺序。扩展常规A *节点后,OD将仅考虑并应用第一个特工的移动。这样做会引入一个中间节点。在中间节点,仅考虑单个代理的移动,从而生成其他中间节点。将运算符应用于最后一个代理时,将生成一个常规节点。一旦找到解决方案,OPEN中的中间节点就不会进一步发展为常规节点,因此,常规剩余节点的数量将大大减少。

3.3.8 。增强部分扩展

增强的局部扩展A *(EPEA *)[20]是一种避免生成多余节点的算法,据我们所知,它是MAPF的最佳基于A *的求解器。EPEA *使用先验领域知识来避免生成多余节点。扩展节点N时,EPEA *仅生成子级ñC 与 F(ñC)=F(ñ)。N的其他子项(与F(ñC)≠F(ñ))被丢弃。这是借助域相关的操作员选择功能(OSF)来完成的。OSF返回的运算符的确切列表将生成具有所需f值的节点(即,F(ñ))。然后将N重新插入到打开列表中,其f成本等于下一个最好的孩子的f成本。当N的新f值在打开列表中变为最佳时,N可能会在以后重新扩展。这避免了多余节点的生成,并大大减少了所生成节点的数量。

在MAPF问题中,当使用SIC启发式方法时,可以有效地计算在给定方向上移动单个代理对f值的影响。在[20]中可以找到有关如何计算和实现用于MAPF的OSF的确切细节。

3.3.9 。不断增加的成本树搜索

我们最近提出了一种解决MAPF实例的新颖方法,该方法使用相应的搜索算法(称为增加成本树搜索(ICTS)[40][42])来最佳地搜索称为增加成本树(ICT)的。ICTS是一种两级搜索算法。

高层次: ICTS在较高层次上搜索不断增长的成本树(ICT)。ICT中的每个节点都包含一个k矢量[C1个,…Cķ]代表所有可能的解决方案,其中代理的个人路径成本一种一世 正是 C一世。ICT的根源是[选择1个,。。。,选择ķ],在哪里 选择一世 是代理商的最佳个人路径成本 一种一世,即距离的最短路径长度 s一世 至 G一世而忽略其他代理商。通过将其中一位特工的成本限制增加一个(或某个单位成本)来产生ICT中的孩子。ICT节点[C1个,。。,Cķ]如果有一个完整的,无冲突的解决方案是一个目标,那么一种一世 正是 C一世。图2说明了具有3个代理的ICT,所有代理的最佳单个路径成本均为10。节点的总成本为C1个+…+Cķ。对于根,这恰好是起始状态的SIC启发式,即集成电路(开始)=选择一世+选择2+…+选择ķ。我们使用Δ表示成本最低的ICT目标节点的深度。ICT树的大小是Δ的指数。由于处于相同高度的所有节点的总成本相同,因此对ICT进行广度优先搜索将找到最佳解决方案。

Image removed.

  1. 下载:下载全图

图2。ICT的三个代理商。

低级别:低级别充当高级别的目标测试。对于每个ICT节点[C1个,。。,Cķ]在高层访问时,将调用较低级别。低层次的任务是找到一个无冲突的完整解决方案,以使代理的单个路径的成本一种一世 正是 C一世。对于每个代理一种一世,ICTS会存储所有单代理成本路径C一世在称为多值决策图(MDD)的特殊紧凑数据结构中[44]。底层搜索MDD的叉积,以便为不同代理找到一组k条非冲突路径。如果存在这样一组无冲突的路径,则低级别返回true,并且搜索暂停。否则,将返回false,并且高级继续到下一个高级节点(具有不同的成本组合)。

修剪规则:针对高级节点引入了特殊的修剪技术[42]。这些技术为i代理搜索子解决方案,其中一世<ķ。如果存在不存在有效解决方案的子组,那么就不可能对所有k个代理都存在有效解决方案。因此,无需在k代理路径空间中搜索解决方案,就可以将高级节点声明为非目标。ICTS的增强版(信息技术委员会+修剪)[41][42]比Standley的A *方法(最多)提高了两个数量级(一种*+外径+ID)[45]

4 。基于冲突的搜索算法(CBS)

现在我们来描述我们的新算法,即基于冲突的搜索算法(CBS)。稍后,在第8节中,我们将介绍对CBS的概括,称为基于元代理冲突的搜索(MA-CBS)。另外,附录A中介绍了CBS的内存有效变体。

回想一下,MAPF中A *所跨越的状态空间以k(代理数)为指数。相比之下,在单主体寻路问题中,ķ=1个,并且状态空间在图形大小中仅是线性的。CBS通过将MAPF分解为大量受约束的单代理寻路问题来解决它。这些问题中的每一个都可以在时间上与图的大小和解决方案的长度成比例地解决,但是这种单代理问题的数量可能成倍增加。

4.1 。CBS的定义

本文的其余部分使用以下定义。

我们仅在单个代理的上下文中使用术语路径,并使用术语解决方案来表示给定的k个代理集合的k个路径集合。

一个约束是一个元组(一种一世,v,Ť) 哪里代理 一种一世被禁止在时间步t占据顶点v。在算法过程中,代理将与约束关联。代理的一致路径一种一世是一条满足其所有约束的路径。同样,一致的解决方案是由路径组成的解决方案,例如,任何代理的路径一种一世 与...的约束一致 一种一世。

一个冲突是一个元组(一种一世,一种Ĵ,v,Ť) 哪里代理 一种一世 和代理 一种Ĵ在时间点t占据顶点v。如果其所有路径都没有冲突,则(k个路径)解决方案有效。如果尽管单个路径与其代理关联的约束一致,但这些路径仍然存在冲突,则一致的解决方案可能无效

CBS的关键思想是增加一组约束并找到与这些约束一致的路径。如果这些路径有冲突,因此是无效的,则可以通过添加新的约束来解决冲突。CBS分为两个级别。在高层次上,发现了冲突并添加了约束。低层级为各个代理查找与新约束一致的路径。接下来,我们将更详细地描述此过程的每个部分。

4.2 。高水平

在以下部分中,我们将介绍CBS的高级过程及其搜索的搜索树。

4.2.1 。约束树

在较高级别,CBS搜索一棵称为约束树(CT)的。CT是二叉树。CT中的每个节点N包括:

1。

一组约束(ñ。约束)。这些约束中的每一个都属于一个代理。CT的根包含一组空约束。CT中节点的子节点继承父节点的约束,并为一个代理添加一个新约束。

2。

解决方案(ñ。解)。一组k条路径,每个代理一个路径。代理之路一种一世 必须符合以下约束 一种一世。这些路径是通过低级搜索找到的。

3。

总费用(ñ。成本(目前所有解决方案的总费用)。该成本称为节点Nf值。

CT中的节点N是目标节点,当ñ。解是有效的,即所有代理的路径集没有冲突。高级别在CT上执行最佳优先搜索,其中CT节点按其成本排序。在我们的实现中,打破了联系,而使用了关联的解决方案包含较少冲突的CT节点。进一步的联系以FIFO方式中断。

4.2.2 。在CT中处理节点

给定CT节点N的约束列表,将调用低级搜索。低级搜索(下面将详细介绍)为每个代理返回一条最短路径,一种一世,这与与 一种一世在节点N中。一旦找到了每个代理的一致路径(关于其自身的约束),就可以相对于其他代理验证这些路径。该验证是通过所有的时间步长的迭代和匹配由所有代理保留的位置上进行。如果没有两个代理计划同时位于同一位置,则将该CT节点N声明为目标节点,并且当前解决方案(ñ。解)(包含此路径集)将返回。但是,如果在执行验证时发生冲突C=(一种一世,一种Ĵ,v,Ť) 找到两个或更多代理商 一种一世 和 一种Ĵ,验证暂停,并且该节点被声明为非目标节点。

4.2.3 。解决冲突

给定非目标CT节点N,其解ñ。解包括冲突 Cñ=(一种一世,一种Ĵ,v,Ť) 我们知道,在任何有效的解决方案中,最多只有一个冲突的代理(一种一世 和 一种Ĵ)在时间t可能占据顶点v。因此,至少有一个约束(一种一世,v,Ť) 要么 (一种Ĵ,v,Ť) 必须添加到 ñ。约束。为了保证最优性,检查了两种可能性,并将节点N分为两个子节点。两个孩子都从N继承约束集。左孩子通过添加约束来解决冲突(一种一世,v,Ť) 合适的孩子增加了约束 (一种Ĵ,v,Ť)。

注意,对于给定的CT节点N,不必保存其所有累积约束。相反,它只能保存其最新约束,并通过其祖先遍历从N到根的路径来提取其他约束。同样,除了根节点,低级搜索仅应针对代理执行一种一世与新添加的约束相关联。其他代理的路径保持不变,因为没有为它们添加新的约束。

4.2.4 。的冲突ķ>2 代理商

在不同路径之间执行验证时,可能会发现k-agent冲突ķ>2。有两种方法可以处理这种k代理冲突。我们可以生成k个子元素,每个子元素都对ķ-1个代理(即,每个孩子在时间t仅允许一个代理占据冲突的顶点v)。或者,等效的形式化是仅关注发现冲突的前两个代理,并且仅根据它们的冲突进行分支。这为树的更深层次留下了进一步的冲突。这在图3中示出。顶部的树表示CT的一种变体,其中对于单个冲突,允许k向分支,其中包括k个代理,ķ=3。每个新的继任者都添加ķ-1个(= 2)个新约束(除一个以外的所有代理)。底部的树显示了针对同一问题的二进制CT。请注意,底部中间状态是重复状态,如果不应用重复检测,则此节点将出现两次,而不是一次。可以看出,两棵树中最深层的大小是相同的。两种方法的复杂度相似,因为它们都将以k个节点结束,每个节点具有ķ-1个新的限制。为简单起见,我们仅实现和描述了第二个选项。

Image removed.

  1. 下载:下载全图

图3。对于同一问题,(k  =  3)路分支CT(上)和二进制CT(下)。

4.2.5 。边缘冲突

为简单起见,我们仅描述了在顶点中发生的冲突。但是,如果根据问题定义,不允许代理以相反的方向越过相同的边缘,则也会发生边缘冲突。我们定义一个边缘冲突为元组(一种一世,一种Ĵ,v1个,v2,Ť) 两个代理商“交换”位置的位置(一种一世 从 v1个 至 v2 而 一种Ĵ 从 v2 至 v1个)在时间步长t至时间步长之间Ť+1个。边缘约束定义为(一种一世,v1个,v2,Ť),哪里代理 一种一世 禁止从边缘开始沿边缘移动 v1个 至 v2在时间步t(并达到v2 在时间步 Ť+1个)。如果适用,边缘冲突将以与顶点冲突相同的方式由高层处理。

4.2.6 。伪代码和示例

算法2给出了CBS的伪代码,以及稍后将在第8节中介绍的更高级的MA-CBS 。第11–18行仅与MA-CBS有关。现在,假设应该合并()函数(第11行)始终返回false,跳过第11-18行。高级别具有最佳优先搜索的结构。

Image removed.

  1. 下载:下载全图

算法2。高水平的CBS(和MA-CBS)。

我们使用图1(第2.7节)中的示例描述CBS ,在此示例中,小鼠需要拿到各自的奶酪块。对应的CT在图4中示出。根包含一组空约束。在第2行中,低级别返回了每个代理的最佳解决方案,〈小号1个,一种1个,d,G1个〉 对于 一种1个 和 〈小号2,乙1个,d,G2〉 对于 一种2。因此,该节点的总成本为6。所有这些信息都保留在该节点内。然后将根插入OPEN,然后将其展开。

Image removed.

  1. 下载:下载全图

图4。约束树(CT)的示例。

验证由两条单独路径给出的双重代理解决方案(第7行)时,两个代理在时间步骤2到达顶点D时都会发现冲突。这会产生冲突(一种1个,一种2,d,2)(第10行)。结果,根被声明为非目标,并生成了两个子节点以解决冲突(第19行)。左孩子,添加约束(一种1个,d,2) 而合适的孩子增加了约束 (一种2,d,2)。现在为左孩子调用低级搜索(第23行),以找到一条也满足新约束的最佳路径。为了这,一种1个 必须在以下位置等待一个时间步长 一种1个 或 小号1个 和路径 〈小号1个,一种1个,一种1个,d,G1个〉 返回 一种1个。的路径一种2, 〈小号2,乙1个,d,G2〉左孩子保持不变。现在,左子项的总成本为7。以类似的方式,生成了右子项,其成本也为7。两个子项均插入OPEN(第26行)。在while循环的下一次迭代(第5行)中,选择左子级进行扩展,并验证基础路径。由于不存在冲突,因此将左子节点声明为目标节点(第9行),并将其解决方案作为最佳解决方案返回。

4.3 。低级:查找CT节点的路径

低级搜索被赋予一个代理, 一种一世,以及与 一种一世。它在基础图形中执行搜索以找到代理的最佳路径一种一世在完全忽略其他代理的情况下满足所有约束。低级搜索的搜索空间具有两个维度:空间维度和时间维度。2可以使用任何单代理寻路算法来查找代理的路径一种一世,同时验证是否满足约束条件。我们使用A *实施CBS的低级搜索,该搜索处理了以下约束。每当一个状态(v,Ť)生成,其中v是位置,t是时间步长,并且存在约束(一种一世,v,Ť)在当前CT(高级别)节点中被丢弃。我们使用的启发式方法是空间维度中最短的路径,而忽略了其他代理和约束。

对于两个低级A *状态具有相同f值的情况,我们使用了基于Standley的平局决胜冲突避免表(CAT)的平局决胜策略(在3.3.4节中进行了介绍)。与其他代理数量较少的国家/地区应优先考虑。例如,如果状态s1个=(v1个,Ť1个) 和 s2=(v2,Ť2)具有相同的f值,但是v1个 被其他两个代理同时使用 Ť1个 而 v2 当时未被任何其他代理使用 Ť2, 然后 s2将首先扩展。与任意打破平局相比,该打破平局策略将总运行时间缩短了2倍。重复状态检测和修剪(DD)加快了底层过程的速度。与单代理寻路不同,低级状态空间还包括时间维度和由约束引起的动态“障碍”。因此,如果两个位置的两个位置都被视为重复,一种一世 两种状态下的时间步长相同。

5 。理论分析

在本节中,我们讨论CBS的理论方面。我们首先从CBS返回最佳解决方案的证明开始,然后再是完整性的证明。然后,我们将讨论与其他算法相比时CBS的优缺点。本节中的所有索赔均采用成本总和成本函数。在第7节中讨论了如何将这些索赔适用于其他成本函数。

5.1 。CBS的最优性

我们首先提供一些证明最优性的证明。

 

定义1

对于约束树中的给定节点N,令简历(ñ)是满足以下条件的所有解决方案的集合:(1)与N的约束集合一致,并且(2)也是有效的(即,无冲突)。

如果N不是目标节点,则N处的解决方案将不属于简历(ñ)因为解决方案无效。例如,考虑根节点。根没有约束因此简历(根)等于所有可能的有效解的集合。如果为根选择的解决方案无效,因此不属于简历(根),则不会将根声明为目标。

 

定义2

我们说点ñ允许的解决方案p如果p∈简历(ñ)。

例如,CT的根具有一组空约束。任何有效的解决方案都满足空约束集。因此,根节点允许所有有效的解决方案。

解决方案的成本 简历(ñ)是各个代理商费用的总和。让minCost(简历(ñ)) 是所有解决方案中的最低成本 简历(ñ)。如果是简历(ñ)=∅ 然后 minCost(简历(ñ))=∞。

 

引理1

CT中节点N的成本是 minCost(简历(ñ))

 

证明

以来 ñ。成本是所有最佳一致单代理解决方案的总和,在所有一致解决方案中成本最低。相比之下,minCost(简历(ñ))在所有一致且有效的解决方案中成本最低。由于所有一致和有效解决方案的集合是所有一致解决方案的子集,因此必须ñ。成本≤minCost(简历(ñ))。□

 

引理2

对于每个有效解p,在 OPEN 中至少存在一个节点N,使得N允许p。

证明

通过对扩展周期的归纳:在基本情况下,OPEN仅包含没有约束的根节点。因此,根节点允许所有有效的解决方案。现在,假设在第一次一世-1个扩展。在扩展过程中,假设节点N被扩展。节点N的后继者–ñ1个 和 ñ2生成。令p为有效解。如果OPEN中的另一个节点允许p,我们就完成了。否则,假设pN允许。我们需要证明p必须由其至少一个后继者允许。的新约束ñ1个 和 ñ2共享相同的时间和位置,但限制了不同的特工。假设N所允许的解p有代理一种1个在约束的位置。代理商一种1个 只能限制在 ñ1个 和 ñ2,但不能同时使用两者,因此这些节点之一必须允许p。因此,归纳成立。□

结果:在所有时间中的至少一个节点CT OPEN 允许最优解(作为一种特殊情况引理2)。

 

定理1

CBS返回最佳解决方案。

证明

当节点中的目标ģ被选择用于由高电平扩展,所有有效的解决方案是允许由至少一个节点从OPEN(引理2)。令p是一个有效的解决方案(含成本p。成本) 然后让 ñ(p)是该节点允许p在OPEN。让ñ。成本是节点N的成本。ñ(p)。成本≤p。成本(引理1)。由于G是目标节点,G。成本是有效解决方案的成本。由于高级搜索根据那里的成本以最佳优先的方式探索节点,因此我们得到G。成本≤ñ(p)。成本≤p。成本。□

5.2 。CBS的完整性

CBS高层搜索的状态空间是无限的,因为可以为无限数量的时间步添加约束。这就提出了完整性问题。CBS的完整性包括两个主张:

声明a:如果存在,CBS将返回解决方案。

要求b: CBS将确定一个无法解决的问题。

现在我们将证明,要求a始终是正确的,而要求b需要独立于CBS的测试。

5.2.1 。要求

 

定理2

对于每个成本C,都有数量有限的CT节点。

证明

假定一个CT节点Ñ成本Ç。在时间步骤C之后,所有代理均位于其目标位置。因此,在时间步骤C之后不会发生冲突。由于约束是从冲突得出的,因此对于大于C的时间步长不会生成约束。由于每一个CT节点的成本是单调非减,所有的CT节点的前身Ñ具有成本≤ Ç。因此,N或其任何前任都不能为大于C的时间步长生成约束。由于此类约束的数量有限(最多ķ⋅|V|⋅C 顶点约束和 ķ⋅|Ë|⋅C边缘约束),也有有限数量的CT节点包含此类约束。□

 

定理3

如果存在,CBS将返回一个解决方案。

证明

CBS使用系统的最佳优先搜索,并且CT节点的成本单调不变。因此,对于每对成本XY,如果X<ÿ然后CBS将在扩展成本Y的节点之前扩展所有具有成本X的节点。由于对于每种成本,都有有限数量的CT节点(定理2),因此必须在扩展有限数量的CT节点后找到最佳解决方案。□

5.2.2 。要求b

索赔b并不总是适用于CBS。例如,考虑图5中提出的问题,其中两个代理需要切换位置。CT将无限增长,增加越来越多的约束,永远无法达成有效的解决方案。幸运的是,Yu和Rus [57]最近提出了一种算法,该算法可以检测给定MAPF实例是否可求解的天气。在CBS之前运行其算法将满足权利要求b,因为仅当实例可解决时才会调用CBS。

Image removed.

  1. 下载:下载全图

图5。无法解决的MAPF实例的示例。

5.3 。与其他算法的比较

本节将CBS和A *的工作进行了比较,这两个工作都是为了使成本和功能最小化并且都使用SIC启发式方法。假设我们对MAPF使用A *。令χ为具有以下项的(多主体)A *节点的集合⁎F<C⁎当使用SIC启发式方法执行A *时。另外,让X=|χ|。众所周知,A *必须扩展χ中的所有节点才能保证最优性[11]

在先前的工作中,我们分析了A *和ICTS的最坏情况行为[42]。在最坏的情况下,A *最多生成X×(b基础)ķ节点。在最坏的情况下,ICTS最多搜索X×ķΔ低层节点(其中Δ是成本最低的ICT目标节点的深度)。注意,ICTS访问的低级节点是k代理MDD搜索空间中的状态,与A *访问的节点相似但不相同。有关更多详细信息,请参见[42]。我们将讨论限制在仅将CBS与A *进行比较,因为已经研究了A *和ICTS之间的关系[42]。令ϒ为具有⁎成本<C⁎ 在CT中,让 ÿ=|ϒ|。作为由节点成本指导的最佳优先搜索,并且由于成本单调不变,CBS必须扩展ϒ中的所有节点。我们限制自己给Y的上限。由于CT的分支因子为2,2d在最坏的情况下必须扩展节点,其中d是找到解的CT深度。在CT的每个节点上,恰好添加了一个约束。在最坏的情况下,将限制代理避免在解决方案的每个时间步中都避开每个顶点。所有座席合计的时间步骤总数为⁎C⁎。因此,CBS必须扩展的CT节点数Y的上限为⁎2|V|×C⁎。对于这些节点中的每个节点,最低级别都会被调用并最多扩展⁎|V|×C⁎(单个代理)每个时间步的状态。让ÿ¯ 是基础图中扩展的状态数(低级状态)。 ⁎⁎ÿ¯=Ø(2|V|×C⁎×|V|×C⁎)。注意,我们计算了在扩展的高级节点内扩展的低级节点。如果我们也要考虑生成的高级节点,则应将其乘以2,因为每个扩展的CT节点都会生成2个新节点。同样,在实践中,Y和ÿ¯ 可以大大缩小。

CBS在CT中执行高级搜索,然后在基础图形中执行低级搜索,并扩展 ÿ¯低级状态。因此,如果ÿ¯≪X,也就是说,如果在所有单代理搜索中扩展的状态数量远小于具有以下条件的(多代理)A *状态的数量: ⁎F<C⁎,则CBS的表现将优于A *,反之亦然。人们可能会对这一结果感到惊讶,这表明CBS可能考虑的状态少于A *,因为已知A *是“最佳有效的”,因为A *仅扩展了寻找最佳解决方案所需的节点集。但是,只有将A *与搜索相同状态空间,使用相同,一致,启发式函数的另一个BFS进行比较,并且忽略具有相同状态的平局决胜的影响时,A *的“最佳有效”属性才成立f[11]。CBS搜索与传统A *完全不同的状态空间,因此可以比A *更好。

接下来我们展示一些特殊情况 ÿ¯≪X (瓶颈)和位置 X≪ÿ¯(开放空间)。对于MAPF而言,总体趋势似乎很典型,因为该领域的拓扑会极大地影响算法的行为。

5.3.1 。CBS表现优于A *(瓶颈)的示例

我们的图1(第2.7节)示例演示了一种情况,其中ÿ¯≪X也就是说,CBS扩展的节点数少于A *的情况。如上所述,CBS总共生成三个CT节点(如第4.2.6节的图4所示)。从根本上说,两个代理都调用了低级。低层搜索为两个代理(长度均为3)中的每一个找到一条最佳路径,并为CT根扩展了总共8个低层状态。现在,在D发现冲突。生成两个新的CT子节点。在左孩子中,低层级搜索代理的替代路径一种1个在步骤2中没有通过D。小号1个加上所有m个州一种1个,…,一种米 用扩展 F=3。然后,D和G1个 用扩展 F=4 搜索停止并返回路径 〈小号1个,一种1个,一种1个,d,G1个〉。

因此,在左侧的孩子总共 米+3节点被扩展。类似,米+3状态会针对合适的孩子展开。将所有这些添加到从根开始扩展的8个状态中,我们总共得到ÿ¯=2米+14 低级状态被扩展。

现在,考虑在2代理状态空间中运行的A *。根 (小号1个,小号2) 具有 F=6。它产生米2 节点,所有形式 (一种一世,乙Ĵ) 对于 (1个≤一世,Ĵ≤米)。所有这些节点都用F=6。现在,节点(一种1个,d) 与 F=7 展开(代理 一种1个 等待在 一种1个)。然后节点(d,G2) 和 (G1个,G2)展开并返回解决方案。因此,总A *扩大了X=米2+3节点。对于米≥5 这个比 2米+14因此,CBS将扩展更少的节点。A *必须扩展单代理路径的笛卡尔积F=3。相比之下,CBS仅尝试了两条这样的路径来认识到成本6的解决方案无效。

此外,CBS每个(低级)节点的恒定时间比A *每个节点的恒定时间小得多,这有两个原因:A *扩展多主体节点,而CBS扩展单主体状态。其次,CBS维护的开放列表要小得多,因为单个代理搜索空间在输入图的大小上是线性的。相比之下,A *的开放列表处理的是多代理状态空间,该空间呈指数增长。因此,在CBS中,从打开列表中插入和提取节点更快。CBS还直接在高层节点上产生开销。每个非目标高层节点都需要验证给定的解决方案并生成两个后继节点。与低层节点相比,高层节点的数量非常少。因此,高层的开销可以忽略不计。

5.3.2 。A *表现优于CBS(开放空间)的示例

图6展示了一种情况ÿ¯≫X而A *将胜过CBS。中间有一个空白区域(灰色),所有特工都必须越过该区域。对于每个代理,有四个长度为4的最佳路径,因此起始状态的SIC启发式为8。但是,这些路径的16种组合中的每一种在一个灰色单元格中都有冲突。所以,⁎C⁎=9因为一个特工必须至少等待一步才能​​避免冲突。对于这个问题,A *将扩展5个节点F=8: {(d2,C1个),(d3,C2),(d3,乙1个),(C2,乙1个),(C3,乙2)} 和3个节点 F=9 {(乙3,乙2),(一种3,乙3),(一种3,乙4)} 直到找到目标并扩展了总共8个节点。

Image removed.

  1. 下载:下载全图

图6。CBS效率极低的病理情况。

现在,考虑CBS。CBS将建立一个CT,如图7所示。CT由5个成本为8的非目标CT节点和6个成本为9的目标CT节点(虚线框)组成。根CT节点将对每个代理执行低级搜索,总共进行8个低级扩展。除根节点外,每个非目标CT节点都将对单个代理进行低级搜索,以进行总共4个低级扩展。每个目标CT节点将扩展5个低层节点。总体而言,CBS将扩大8+4⋅4+6⋅5=54 低层节点。

Image removed.

  1. 下载:下载全图

图7。对于CBS效率极低的病理病例的CT。

由于冲突树在遇到的冲突数量中呈指数增长,因此,当一组座席紧密耦合时,即,当组中的座席之间内部冲突发生率很高时,CBS的行为将很差。

虽然很难预测算法在实际域中的性能,但以上观察可以提供一些指导。如果存在更多瓶颈,则CBS将比基于A *的方法更具优势,因为它将排除代理很快在瓶颈中发生冲突的f值,然后转向绕过瓶颈的解决方案。如果有更多开放空间,A *将比CBS具有优势,因为它将很快排除冲突的解决方案。接下来,我们显示支持两种情况的实验结果。

6 。CBS实证评估

CBS以及本文介绍的其他算法都适用于MAPF问题的许多变体。接下来,我们描述用于经验分析的MAPF变量和实验设置。选择该特定的MAPF变体和设置以符合先前的工作[42][38][39][45][46]

6.1 。实验性问题设定

在每个时间步骤,所有座席都可以同时执行移动或等待动作。我们的实现假设移动和等待都具有单位成本。我们还做出以下两个假设:

1。

代理商永远不会消失。即使一个代理达到了目标,它也会阻止其他代理通过它。

2。

仅当代理程序以后再也没有离开目标时,以目标为目标的等待操作的成本为零。否则,它们将花费一。

另外,在我们的实验环境中,允许试剂相互跟随。即代理一种一世如果同时代理可以将xy移到y一种Ĵ也从y移到z。在[45][42][55][13]之后,我们允许代理在循环链中互相跟随。我们认为,此策略更适合表示多机器人场景,因为实际上机器人可以同时在一个圆圈内移动(没有空白)。在卵石运动文献[9]中,不允许顺着链条运动是很普遍的,卵石一个接一个地运动,因此至少需要一个空白空间来启动运动。边缘冲突也被禁止。那是代理一种一世如果同时代理,则禁止从x移到y一种Ĵ从y移到x。我们的实现没有在高层使用重复的检测和修剪过程(DD),因为我们发现它的开销很大,而改进却可以忽略不计。另一方面,低级确实使用DD。

我们的实验中使用的特定全局累积成本函数是2.4节中说明的成本总和函数。例如,如果需要代理商一种1个 和 一种2 2个和3个时间步骤分别达到其目标,则这两个代理商的费用总和为 2+3=5。请注意,对于每个业务代表,要计算时间步长,直到到达目标的时间步长为止。一个达到目标但后来又被迫离开的代理商可能会导致总成本的急剧增加。为了解决这个问题,我们使用了EPEA * [15]的相同机制,该机制根据它们的f值一次生成一个高级节点。

对于低级搜索的可允许启发式方法,我们在所有实验中均使用了SIC启发式方法(请参阅第3.3.1节)。

6.2 。实验结果

我们实施并尝试了A *,EPEA *, 信息技术委员会+修剪(表示为ICTS)和CBS。对于ICTS,我们使用了所有三元组修剪 [42],已发现它非常有效。除ICTS之外,所有算法均基于SIC启发式算法。ICTS使用了更高级的修剪功能,将来有可能将其应用于CBS和A *作为高级启发式方法。尽管如此,没有这种高级启发式方法的CBS在许多情况下仍胜过ICTS。

6.2.1 。8×8 4联电网

我们从 8×84连接的开放式网格,代理人数从3到21。我们将时间限制设置为5分钟。如果算法无法在时限内解决实例,则会将其暂停并返回失败。我们的目的是研究给定数量的代理程序不同算法的行为。当ID框架应用于k个代理(起始位置和目标位置是随机的)时,所产生的有效代理数ķ′嘈杂,其差异很大。因此,对于本实验,我们遵循[42]并根据ID框架创建了所有代理都依赖的问题实例。3在这种情况下ķ′≡ķ 并且运行ID框架是多余的。

图8显示了成功率,即当代理程序数量增加时,在5分钟内可以通过不同算法解决的实例百分比。在这些简单的问题中,A *明显较差,而CBS相对于其他方法而言则略占优势。

Image removed.

  1. 下载:下载全图

图8。成功率与代理数量8  ×  8网格的关系。

表1列出了生成的节点数和100多个实例的平均运行时间。对于CBS,报告了高级(hl)节点和低级(ll)状态。“ NA”表示对于给定数量的代理,A *获得的成功率小于80%(失败的大于20%)的问题。计数列说明了所有算法在该时限内解决的实例数。仅针对那些实例显示平均结果。与[42]类似,我们没有报告ICTS变体的节点数量,因为该算法并非仅基于搜索。

表1。在8  ×  8网格上生成节点并运行时间。

ķ′#生成的节点运行时间(毫秒)

计数一种*EPEA *CBS(hl)CBS(ll)一种*EPEA *信息技术委员会哥伦比亚广播公司p值

31006401510490801个70.01

41003965252410482071个1个140.02

510021,85135512385395031个320.01

68992,3213945135437,39848200.09

7100不适用881173994不适用1520600.00

8100不适用2932668644不适用751001480.00

9100不适用1053136245,585不适用4447578790.01

1099不适用23723225111,571不适用1340315224290.02

1194不适用79238789321,704不适用8157731877120.44

1292不适用13,17812,980451,770不适用13,78719,00212,3630.36

1386不适用14,98915,803552,939不适用18,67628,38116,4810.50

1483不适用13,87221,068736,278不适用15,40735,80124,4410.14

1571不适用2296724,871826,725不适用33,56954,81830,5090.45

1664不适用26,80524,602822,771不适用41,36065,57834,2300.32

1749不适用25,61517,775562,575不适用42,38275,04025,6530.22

EPEA *和CBS的结果相对相似。为了研究它们之间差异的统计显着性,我们对这两种算法的运行时结果进行了配对t检验。所得的p值显示在“ p-val”列中。可以看出,对于较大的问题,算法之间差异的显着性变小(高p值对应于较小的显着性)。这是因为某些问题很难解决,而其他问题很容易并且可以快速解决。这一事实,加上MAPF的指数性质,导致运行时结果差异很大。显然,纯A *是最差的算法,而EPEA *是最强的A *变体。对于11个以上的座席,CBS比ICTS更快。请注意,尽管CBS生成的节点多于EPEA *,ķ′>14),因为低级CBS的每个节点的恒定时间(单代理状态,小的打开列表)比EPEA *(多个代理,大的打开列表)要小得多。CBS的速度分别比EPEA *和ICTS快2倍和3倍。

6.2.2 。DAO地图

我们还在《龙腾世纪:起源》 [47]游戏中测试了3张基准地图。在这里,我们旨在展示评估算法的整体性能。与上面的结果不同,这里我们在每个评估算法的顶部执行ID。给不同的算法一个具有给定数量的k个代理的问题实例,其中开始和目标位置被统一随机化。ID将这些问题分解为子问题,并分别在每个子问题上执行关联的算法。我们仅显示三种最强算法的结果:EPEA *,ICTS和CBS。

图9(右)显示了给定三个地图的座席人数的成功率。在这里结果好坏参半,没有全球冠军。可以清楚地看到,ICTS总是比EPEA *好。CBS在这些地图上的性能支持了我们的理论主张,即CBS在处理走廊和瓶颈时非常有效,而在开放空间中效率很低。对于den520d(上),没有瓶颈,但是有很大的开放空间;CBS排名第三。对于ost003d(中),几乎没有瓶颈和小的开放空间;在大多数情况下,CBS处于中间水平。最后,对于brc202b(底部),有许多狭窄的走廊和瓶颈,但只有很少的开放空间,因此CBS是最好的。请注意,虽然den520和ost003都有开放空间,但瓶颈数量有所不同。

Image removed.

  1. 下载:下载全图

图9。对于不同的DAO映射den520d(顶部),ost003d(中间),brc202d(底部),所有算法都在ID之上运行的不同算法的成功率。

图10说明了CBS解决过程中遇到的冲突。发生冲突的单元格显示为红色。红色的暗处对应于单元中发生的冲突数。深红色表示更多冲突。如在开放空间(den520d,ost003d)中可以看到的,冲突蔓延并覆盖了地图的很大一部分。相比之下,在brc202d中,冲突集中在走廊和瓶颈处。这说明了开放空间如何引发更多冲突,因此不太适合CBS。

Image removed.

  1. 下载:下载全图

图10。DAO映射den520d(左),ost003d(中),brc202d(右)及其冲突的位置。

7 。使用不同成本函数的CBS

让SoC表示第2.4节中定义的成本总和函数。到目前为止,我们一直专注于最小化SoC功能的任务。尽管如此,CBS仍可以归纳为以下其他成本函数。

7.1 。高水平

将CBS泛化为制造成本函数需要对高层进行一次更改-根据其相应解决方案的制造期而不是SoC计算CT节点的成本(算法2中的第24行,第4.2.6节)。更一般而言,让Φ为将成本分配给MAPF解决方案的函数。找到最小化的解决方案Φ,我们修改CBS计算每CT节点,成本Ñ,要Φ(ñ。解)。我们表示CBS的成本函数的执行Φ为哥伦比亚广播公司Φ。

7.2 。低级

回想一下,每个高级节点N都有一个多代理解决方案,ñ。解。每个多主体解决方案均由k条单主体路径组成。如上针对我们的成本函数(SoC)定义的低级求解器,将返回给定代理的单个代理路径。从低级返回的单代理路径必须保持最佳状态Φ(ñ。解)最小。但是,可以针对给定的成本函数改善低电平。在低级搜索过程中,我们建议根据与其他特工遇到的最少冲突来打破关系。这可以使用上述冲突避免表(CAT)来完成。

7.3 。最优性

稍作修改,成本函数之和的最优性证明(见第5.1节)适用于哥伦比亚广播公司Φ适用于各种成本函数。Φ被认为是允许的Φ(ñ)≤minCost(简历(ñ))对于每个CT节点Ñ

定理4

如果允许Φ,则 哥伦比亚广播公司Φ 保证返回最佳解决方案。

证明

哥伦比亚广播公司Φ根据Φ执行最佳优先搜索。根据定义,CT子树中N以下的任何解决方案的成本都不能小于minCost(简历(ñ))。保证了由可接受的评估函数指导的BFS返回最优解[11]。□

SoC,makepan和燃料成本功能都是可以接受的,因为在后续CT节点中添加更多约束不能导致成本更低的解决方案。因此,根据定理4,哥伦比亚广播公司Φ 将为所有这些成本函数返回最佳解决方案。

7.4 。完整性

5.2节中提供的完整性证明适用于任何成本函数Φ,只要根据Φ每给定成本存在有限数量的解决方案即可。此条件适用于没有零成本操作的任何成本函数。SoC和makepan是此类功能的示例。另一方面,燃料成本函数不具有此属性。对于燃料成本函数,可以有无数个具有给定成本的高级节点,因为等待动作不会花费任何成本。由于燃料成本函数不满足上述条件,因此需要一种稍微不同的方法。Yu和Rus [57]在他们的论文中建议,对于任何可解决的MAPF实例,最多不超过Ø(|V|3)所有代理商都必须达到单一代理商的步骤才能实现其目标。这个事实可以用于我们的需求,如下所述。对于每个节点N,如果片上系统(ñ)>|V|4,则可以安全地忽略该节点。解决方案大于|V|4(根据SoC)必须包含一个时间步,所有代理同时执行等待操作。在这种情况下,有一个更便宜的解决方案,其中删除了此时间步骤。

8 。基于元代理冲突的搜索(MA-CBS)

现在我们来解释一个称为Ceta的通用框架,该框架称为基于元代理冲突的搜索(MA-CBS)。首先,我们通过关注上述基本版本的CBS的行为来为MA-CBS提供动力。

8.1 。元代理CBS的动机

如前所述,CBS对于某些MAPF问题非常有效(与其他方法相比),而对其他问题则非常低效。先前已经讨论了不同的MAPF算法在不同的环境或拓扑下表现不同的一般趋势[42][38][39]。此外,给定域可能具有具有不同拓扑的不同区域。这就需要一种算法,该算法将根据确切的任务及其当前搜索的区域动态更改其策略。在理解地图拓扑与MAPF算法性能之间的关系方面,还有大量的研究空间。MA-CBS是朝着动态适应算法迈出的第一步。

如上一节中所示,当一组特工紧密耦合时,即,当该组特工之间的内部冲突发生率很高时,CBS的表现较差。在这种情况下,基本CBS可能必须处理大量冲突才能产生最佳解决方案。MA-CBS通过自动识别强耦合代理集并将它们合并为元代理来纠正CBS的这种行为。然后,高级CBS继续进行,但是从CBS角度来看,此元代理被视为单个代理。因此,MA-CBS的低级求解器必须是MAPF求解器,例如,一种*+外径 [45],EPEA * [15],M * [51]。因此,MA-CBS实际上是可以在另一个MAPF求解器之上使用的框架。接下来,我们提供MA-CBS的技术细节。

8.2 。将代理合并为元代理

基本CBS和MA-CBS之间的主要区别是将代理合并为元代理的新操作。元代理由M个代理组成。因此,单个代理只是大小为1的元代理。回到算法2(第4.2.6节),我们介绍了在发现新冲突后立即发生的合并动作(第10行)。此时,MA-CBS有两种选择:

分支:在此选项中,我们根据新的冲突(第19–26行)分为两个节点。这是基本CBS始终执行的选项。

合并: MA-CBS还有另一个选择,可以将两个有冲突的(元)代理合并为一个元代理(第12-18行)。

合并过程如下。假设有k个代理的CT节点N。假设在代理之间发现了冲突一种1个 和 一种2,并且选择了这两个代理进行合并。现在我们有ķ-1个其中包括一个新的大小为2的新元代理,标记为一种{1个,2}。此元代理将永远不会在CT的N之下的子树中再次分裂;但是,它可以与其他(元)代理合并以形成新的元代理。由于其他未合并的代理没有任何变化,因此我们现在仅再次调用该新的元代理的低级搜索(第14行)。实际上,对大小为M的元代理进行低级搜索实际上是M个代理的最佳MAPF问题,应使用最佳MAPF求解器解决。注意,由于元代理的最优路径可能大于这些代理中的每个代理的最优路径之和,因此此CT节点的f成本可能会由于此合并动作而增加。因此,f重新计算并存储此节点的值(第15行)。然后将该节点再次添加到OPEN中(第17行)。

MA-CBS具有两个重要组件(除了CBS组件之外):决定选择(分支或合并)选项的合并策略(第11行),以及用于定义对新元数据施加的约束的约束合并机制。 -agent(第13行)。必须设计此约束合并机制,以使MA-CBS仍能返回最佳解决方案。接下来,我们讨论如何实现这两个组件。

8.3 。合并政策

我们实施了以下合并政策。两名特工一种一世,一种Ĵ 被合并为元代理 一种{一世,Ĵ} 如果之间的冲突次数 一种一世 和 一种Ĵ在搜索过程中记录超过一个参数。我们称B冲突约束参数,并使用符号MA-CBS(B)表示边界为B的MA-CBS 。请注意,基本CBS实际上是MA-CBS(∞)。也就是说,我们从不选择合并并且总是根据冲突进行分支。

为了实现该面向冲突约束的合并策略,维护冲突矩阵CM。厘米[一世,Ĵ] 累积代理之间的冲突数量 一种一世 和 一种Ĵ 到目前为止,MA-CBS可以看到。 厘米[一世,Ĵ] 每当之间发生新的冲突时,将增加1 一种一世 和 一种Ĵ找到(算法2,第4.2.6节,第10行)。现在,如果厘米[一世,Ĵ]>乙 的 应该合并() 函数(第11行)返回true, 一种一世 和 一种Ĵ 合并成 一种{一世,Ĵ}。如果两个元代理之间发生冲突,一种1个 和 一种2,由于有两个简单的代理, 一种Ť∈一种1个 和 一种ķ∈一种2, 厘米[Ť,ķ] 增加1,并且 应该合并() 如果函数将返回true ∑厘米[X,ÿ]>乙 总体 X∈一种1个,ÿ∈一种2。此政策简单有效。但是,其他合并策略也是可能的,并且可能会显着提高速度。

为了说明MA-CBS,请再次考虑图1所示的示例(第2.7节)。假设我们正在使用MA-CBS(0)。在这种情况下,一旦出现冲突,(一种1个,一种2,d,2) 被发现 应该合并()返回true,代理一种1个 和 一种2 合并到新的元代理中 一种{1个,2}。

接下来,调用低级求解器来求解新创建的元代理,并找到两个代理的(无冲突)最佳路径。如果使用A *,将为此执行2-agent A *。现在,将高级节点重新插入OPEN,将其f值从8更新为9。由于它是OPEN中唯一的节点,因此接下来将对其进行扩展。在第二个扩展中,由于不存在冲突,因此搜索停止了–根据定义,只有一个meta-agent不包含任何冲突。因此,返回来自根节点的解决方案。相比之下,对于MA-CBS(B)乙>0根节点将根据上述第4.2.6节中所述的冲突进行拆分。

8.4 。合并约束

表示元代理 X¯。我们使用以下定义:

元约束的元代理X¯ 是一个元组 (X¯,Xˆ,v,Ť) 代理商的子集 Xˆ⊆X¯被禁止在时间步t占据顶点v

同样,元冲突就是元组(X¯,ÿ¯,v,Ť) 个别代理商 X′∈X¯ 和个人代理 ÿ′∈ÿ¯两者都在时间点t占据顶点v

考虑与(元)代理相关的一组约束 一种一世 和 一种Ĵ合并之前。它们是由于代理之间的冲突而生成的。这些冲突(以及由此产生的约束)可以分为三类。

1。

内部:之间的冲突一种一世 和 一种Ĵ。

2。

external(i):之间的冲突一种一世 和其他代理商 一种ķ (哪里 ķ≠Ĵ)。

3。

external(j):之间的冲突一种Ĵ 和其他代理商 一种ķ (哪里 ķ≠一世)。

以来 一种一世 和 一种Ĵ 现在将要合并,不应将内部冲突视为 一种一世 和 一种Ĵ将通过低级耦合解决。因此,从那时起,我们仅考虑外部约束。

8.4.1 。合并外部约束

假设代理商 一种一世 和 一种Ĵ 将合并到新的元代理中 一种{一世,Ĵ} 然后 一种一世 有外部约束 (一种一世,v,Ť)。这种限制意味着在CT的更远处,一种一世 与其他特工有冲突 一种[R在时间t在位置v处,因此一种一世不允许在时间t处位于位置v

新的元代理必须包括所有外部约束。假设一个外部约束(一种一世,v,Ť)。合并后一种一世 和 一种Ĵ 此约束应仅适用于原始代理, 一种一世,并且不适用于整个meta-agent,即 {一种一世}∪{一种Ĵ}。因此,合并约束的形式为(一种{一世,Ĵ},一种一世,v,Ť)。这是在算法2(第4.2.6节)的第13行中完成的。

合并时 一种一世 和 一种Ĵ 人们很想引入一个元约束 (一种{一世,Ĵ},{一种一世}∪{一种Ĵ},v,Ť) 两位代理商 一种一世 和 一种Ĵ在时间t禁止进入位置v。但是,由于以下情况,这可能会破坏算法的最优性。假设一个3代理问题,在最佳解决方案代理中一种3必须在时间步t穿过顶点v。调用MA-CBS解决此问题将创建根CT节点。假设在为根CT节点中的每个代理选择的路径中,两个代理一种1个 和 一种2在时间步长t被分配了顶点v。接下来,MA-CBS根据冲突分支(一种1个,一种2,v,Ť)。生成两个新的CT节点{ñ1个,ñ2}。在ñ1个 (ñ2)代理 一种1个 (一种2)限制在时间tv。接下来,代理一种1个 (一种2)与代理合并 一种3 在节点 ñ1个 (ñ2)。如果我们允许对代理商施加约束一种1个 和 一种2 申请代理 一种3 我们将在这两个方面阻止最佳解决方案 ñ1个 和 ñ2 这是OPEN中仅有的两个节点。

相比之下,假设有冲突 (X¯,ÿ¯,v,Ť) 被检测到之间 X¯ 和 ÿ¯,在元代理之后 X¯已创建。冲突代理的确切身份X′∈X¯ 和 ÿ′∈ÿ¯是无关紧要的。对两个元代理的约束应包括整个元代理,即(X¯,v,Ť) 或类似地 ÿ¯(算法2的第20行,第4.2.6节)。这样做将保留完整性,因为所有可能的解决方案都存在于其中的所有代理中。X¯ 要么 ÿ¯限制在时间t处于v处。

8.5 。低级求解器

底层查找给定代理的路径。在使用元代理的情况下,底层需要解决由组成元代理的内部代理提供的MAPF实例。具有以下三个属性的任何MAPF求解器都可以在低级别使用:

1。

完整性–如果一个解决方案存在,则求解器必须返回一个解决方案,否则必须返回false。

2。

约束处理–求解器绝不能返回违反约束的解决方案。

3。

最优性–求解器必须返回最优解。

许多已知的MAPF算法适用于低级MA-CBS,例如, 一种*+外径 [45],EPEA * [15],M * [51]。基本形式的ICTS [42]和CBS不适合低层次的人员,因为它们无法检测到无法解决的问题实例。在5.2节中,我们提出了一种通过应用检测无法解决的MAPF实例的算法来解决此问题的方法[57]。但是,此方法不适用于传递给低级求解器的受约束MAPF实例。有趣的是,可以将合并边界小于无穷大的MA-CBS配置为充当低级求解器,从而生成MA-CBS的递归结构。为避免MA-CBS求解器无限期调用另一个MA-CBS求解器的情况,将MA-CBS用作低级求解器需要增加连续递归调用之间的合并阈值。增加阈值的方式是一个深层次的问题,需要大量研究。

8.6 。MA-CBS的完整性和最优性

5.2节中提供的完整性证明也适用于MA-CBS。为了证明MA-CBS的最优性,我们将使用第5.1节中定义和证明的支持性声明和引理。5.1节中的所有引理适用于MA-CBS案例。合并选项不会影响证明。唯一的例外是引理2,它说:“对于每个有效解p,至少存在一个节点N,使得N允许p。” 证明是通过对分支作用的归纳。但是,对于MA-CBS,扩展高级节点可能会导致合并代理而不是分支。因此,我们通过处理合并动作案例来完成证明。在这种情况下,节点N展开,执行合并操作,然后将节点N重新插入OPEN。中的任何有效解决方案VS(ñ) 必须保留在新的 VS(ñ) 扩展过程之后,因为没有添加新的约束。

8.7 。MA-CBS作为连续体

如上所述,MA-CBS的极端情况(∞)等同于基本CBS。现在我们注意到,另一个极端情况MA-CBS(0)等同于Standley [45]引入的基本独立性检测机制(请参阅第3.3.3节)。在MA-CBS(0)中,一旦发生冲突,我们就会合并代理。在根节点中,MA-CBS(0)分别解决每个代理。然后,MA-CBS(0)展开CT根节点。验证此节点时,会发现单个代理的解决方案之间存在冲突(如果存在)。冲突的代理将合并为乙=0。合并的组将使用低级MAPF求解器求解。接下来,将根重新插入OPEN并进行验证。以来乙=0分支选项将永远不会被选择,并且冲突总是通过合并有冲突的(元)代理来解决。因此,此变体将仅具有一个CT节点,该节点将重新插入OPEN,合并发生冲突的代理,直到没有冲突发生为止。这与ID的行为相同。

3.3.4节中介绍的增强ID版本尝试通过重新计划到其中一个冲突代理的路径来解决冲突。这种重新计划让人想起MA-CBS(1),因为一旦发现冲突,我们将尝试通过分支绕过它。如果发现更多冲突,则合并代理。

因此,MA-CBS(B)是一个连续体,具有这两个先前算法作为极端情况。然而,MA-CBS()具有变化值可以显著优于ID,当它解决了仅松耦合,通过分别添加约束到这些药剂。例如,在瓶颈(例如图1,第2.7节)中,个体的解决方案发生冲突时,ID(≡MA-CBS(0))会将这些个体合并为一个组,并在耦合的方式。相比之下,MA-CBS(B)(乙>0)可以通过向其中一个代理添加单个约束来避免此瓶颈。因此,使用MA-CBS(B)并选择合适的乙≥0增加了更多的灵活性,并且可能大大胜过ID。在下面描述的实验结果部分中可以清楚地看到这一点。

9 。MA-CBS实验结果

在本节中,我们在游戏《龙腾世纪:起源》 [47]中的三个标准基准地图上以经验方式研究MA-CBS的行为。回想一下,再次在图11中显示的三个映射中的每个映射都表示不同的拓扑。地图den520d(顶部)具有许多大的开放空间,没有瓶颈,地图ost003d(中部)具有一些开放空间和一些瓶颈,而地图brc202d(底部)几乎没有开放空间和许多瓶颈。我们的主要目标是研究冲突绑定参数B对MA-CBS性能的影响。我们在实验中使用MA-CBS(B)乙=0,1个,5,10,100,500和∞。由于MA-CBS是可以在任何基于A *的求解器之上运行的框架,因此我们尝试了两个这样的求解器:A *和增强的部分扩展A *(EPEA *)[15]。两个求解器都使用了SIC启发式(如上定义)。选择A *作为基准,而选择EPEA *是因为它是当前基于A *的最先进的MAPF求解器。

Image removed.

  1. 下载:下载全图

图11。使用IDEA *作为低级求解器,MA-CBS在ID之上的成功率。

对于每张地图,我们都改变了代理商人数k。我们针对k的每个值在100个随机实例上运行算法。如果算法在五分钟内没有解决给定的问题实例,则将其暂停。报告的数字是所有能够解决70%以上实例的算法所解决的所有实例的平均值。如果算法求解的结果少于70%,我们将其平均结果报告为下限(包括由于时间限制而导致求解器停止运行的情况)。这些情况在下表中用“>”表示。

表2表3显示了上述实验的运行时间(以毫秒为单位)。所述ķ栏表示的在实验中的代理的数量。MA-CBS(x)由B(x)表示。对于给定数量的代理,最佳性能算法的结果以粗体显示。表3显示了使用A *进行低级搜索时的结果,而表2报告了使用EPEA *时的结果。表格中的每一帧都呈现不同的地图。

表2。DAO问题的运行时间(毫秒)。EPEA *作为低级求解器。

ķden520d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5899190180181180180256

1016331782470467469469632

151621224117081702171317381807

203393372515271515155315551867年

257675832717011620173120713264

3012,57413,30839553773527616,191> 38,707

3515,73612,65549744993719918,998> 50,050

4014,63515,45248604971768620,860> 50,891

ķost003d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5187231168168169169222

1017181983年764753757757935

154888459315971592156815701909年

2010,46313,42637013654362335984119

25> 60,140> 58,902> 28,88115,10918,15935,536> 73,860

30> 84,473> 80,248> 30,78125,86027,52546,328> 92,209

35> 90,703> 81,633> 39,66021,46628,24147,544> 95,262

ķbrc202d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

51834年235112861276126812671664

106034805945804530449845085495

1512,35415,38969036871682067938685

20> 70,003> 73,51135,09521,72919,84631,229> 43,625

表3。DAO问题的运行时间(毫秒)。A *作为低级求解器。

ķden520d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5223273218220219222219

1010991458553552549552546

15118216201838年1810182917031672

20479243751996年2011年2020年1857年1708

25763314,74921932255232028883046

30> 62,717> 60,21480828055810780137745

35> 65,947> 51,81513,67013,58715,98128,274> 45,954

40> 81,487> 82,86018,4731839920,39131,189> 45,857

ķost003d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5470631220218220219222

10819216,2701006995981977935

15897115,67916401619162415511458

2029,50747,20432933234320830743000

25> 122,166> 125,417> 73,014> 53,48128,44338,422> 59,923

30> 162,290> 170,094> 63,963> 51,16729,91243,405> 69,681

ķbrc202d

B(0)B(1)B(5)B(10)B(100)B(500)B(∞)

5738212,20016821665年164016571664

1022,55439,34653725312526352265318

1547,82284,46088518746873687018681

20> 116,675> 159,039> 51,59224,01124,81731,069> 34,726

25> 197,268> 223,838> 146,301> 85,89163,16263,835> 66,178

结果清楚地表明,随着问题变得越来越难(解决时间更长),具有非极值的MA-CBS,即 乙≠0 和 乙≠∞,比MA-CBS(0)(ID)和MA-CBS(∞)(基本CBS)能够更快地解决大多数实例。新的变体在MA-CBS(∞)上达到了一个数量级的加速(例如,在使用EPEA *作为低级求解器的35和40个代理的den520d中),在MA-CBS上达到了4倍。 (0)(例如,在具有25个代理的ost003d中)。

接下来,考虑增加使用EPEA *的den520d图的代理数k的效果(表2第一帧)。代理很少的实例(ķ<25)可使用具有大B值的MA-CBS更快地解决。随着问题变得越来越严重(ķ>30)B值较小的MA-CBS速度更快。此外,相对于最佳变体,基本CBS(∞MA-CBS(∞))和MA-CBS(500)的相对性能下降。解释如下。在密集的问题实例中,相对于地图大小有许多代理,会发生许多冲突。回想一下,基本的CBS在遇到的冲突数量上是指数级的。因此,与具有较小B值的变体相比,增加代理数量会降低具有较大B值(其行为更接近于基本CBS)的MA-CBS的相对性能。在极端情况下的单独实验(此处未报告)中,ķ=|V|-1个,我们观察到MA-CBS(0)表现最佳。

现在,考虑将A *用作低级求解器的结果(表3)。在这里,我们看到了与EPEA *结果相同的总体趋势。但是,B的最佳性能值大于带有EPEA *的MA-CBS(表2)。例如,在具有30个代理的den520d映射中,以A *作为低级求解器的MA-CBS(5)并未获得比CBS明显的加速。对于EPEA *作为低级求解器,MA-CBS(5)比CBS获得了数量级的加速。在其他地图中也可以观察到相同的趋势。原因是对于相对较弱的MAPF求解器(例如A *),求解大量代理是非常低效的。因此,我们希望避免合并代理并以更分离的方式运行。对于这些情况,更高B是优选的。另一方面,使用速度更快的MAPF求解器(例如EPEA *),较低的B值将表现更好。在MA-CBS(∞)中,永远不会为元代理调用低级别(仅对于单个代理)。因此,以低水平运行A *或EPEA *不会有任何区别。运行时的差异是由于考虑了一组不同的问题造成的。对于B(5),EPEA *比A *可以解决更多问题(较难的问题)。由于这些问题在表1中得到了解决,因此运行时结果要比表2更高。

图11显示了具有以下条件的MA-CBS的成功率,即超时之前解决的实例数:乙=0,1个,10,100和∞。低层求解器设置为EPEA *,因此乙=0用EPEA *表示。另外,为了进行比较,我们还报告了最佳ICTS变体的成功率[42]。请注意,图例是根据给定地图中的性能排序的。

可以看出,在所有具有中间值的MA-CBS实验中, 0<乙<∞,与EPEA *(* MA-CBS(0))和基本CBS(≡MA-CBS(∞))两种极端情况相比,它能够解决更多实例。此外,具有中间值的MA-CBS也优于ICTS求解器。考虑MA-CBS变体的性能乙<∞ 与基本CBS相比(乙=∞)。基本CBS在den520d(顶部)中的性能非常差,在ost003d(中部)的性能中有些差,而在brc202d(底部)的性能则很差。这是因为在没有瓶颈和较大开放空间的地图(例如den520d)中,CBS效率低下,因为在许多不同位置都会发生许多冲突。在图6中给出的CBS病理示例中对此现象进行了解释(第5.3.2节))。因此,由于避免了很多冲突,因此在den520d中合并代理程序的好处很高。相比之下,对于没有较大开放空间和许多瓶颈的地图(例如brc202d),CBS遇到的冲突很少,因此合并代理仅会减少很小的冲突。实际上,如结果所示,对于brc202d,基本CBS(MA-CBS(∞))的性能几乎与设置B的较低值相同。

通常,在冲突率较高的问题中,合并代理会更有帮助,因此B的值越低越好。B-CBS(10)的成功率最高,例如den520d(上)。相比之下,B-CBS(100)在ost003d和brc202d中获得了最高的成功率。

9.1 。实验结论

实验清楚地表明,没有普遍的赢家。每个已知算法的性能在很大程度上取决于问题特征,例如:密度,地图拓扑,初始启发式错误以及CBS解决过程中遇到的冲突数量。尚不完全了解这些不同功能与每种算法的性能之间的关系,这是我们将来打算研究的重点。同时,我们正在尝试提出新功能,以在搜索之前评估每种算法的性能。但是,我们提出了以下观察到的一般趋势:

具有中间B值的MA-CBS(0<乙<∞)优于以前的算法A *,EPEA *和CBS。在大多数情况下,它也胜过ICTS。

密度。在具有许多代理的密集地图中,较低的B值更为有效。

拓扑结构。在开放空间较大且瓶颈很少的地图中,较低的B值更为有效。

低级求解器。如果将弱MAPF求解器(例如,纯A *)用于低级搜索,则B的高值是首选。

10 。总结,结论和未来工作

在本文中,我们处理了多智能体寻路问题(MAPF)。我们提供了关于MAPF问题的先前工作的简短调查,并引入了一个分类,该分类有助于将所有先前的工作归为以下几类:

1。

最佳求解器[45][15][42][38][39]

2。

基于次优搜索的求解器[43][12]

3。

基于次优过程的求解器[9][30][25][37][10]

4。

次优混合求解器[52][24][53][35]

接下来,介绍了CBS算法。CBS是一种新颖的最佳MAPF求解器。CBS的独特之处在于,所有低级别搜索都作为单代理搜索执行,但它可以产生最佳解决方案。CBS的性能取决于问题的结构。我们已经证明了CBS表现良好的瓶颈(图1,第2.7节)和CBS表现较差的开放空间(图6,第5.3.2节)的情况。我们分析并解释了这些情况以及它们如何影响CBS的绩效。

然后,我们转向介绍MA-CBS框架,这是CBS算法的概括。MA-CBS可以在任何MAPF求解器的顶部使用,它将用作低级求解器。此外,MA-CBS可以看作是Standley [45]引入的独立检测(ID)框架的概括。

MA-CBS充当CBS与其他最佳MAPF求解器(例如A *, 一种*+外径 [45]和EPEA * [15]。它从常规CBS求解器开始,其中一次由单个代理执行低级搜索。如果MA-CBS识别出一对座席经常发生冲突,则将它们分组在一起。低级求解器将此组视为一个复合代理,并使用给定的MAPF求解器(例如A *)找到该组的解决方案。因此,MA-CBS具有灵活性,并且可以通过选择何时将座席分组在一起来享受CBS和传统最佳求解器的互补优势。作为一种简单而有效的机制,在决定要组业务,我们介绍了冲突的约束参数。的参数对应于MA-CBS的倾向来创建的代理大基团和解决它们作为一个单元。什么时候乙=0 MA-CBS收敛到ID,何时收敛 乙=∞MA-CBS等效于CBS。设置0<乙<∞提供了MA-CBS的灵活性,因此,在仅发生少量冲突的情况下,MA-CBS可以像CBS一样工作,而如果冲突很普遍,则MA-CBS可以收敛到一个包含所有或大部分冲突的元代理问题代理商。试验台地图问题的实验结果支持了我们的理论主张。呈现的域具有不同的开放空间和瓶颈率。在走廊和瓶颈更为主要的情况下,具有高B值(100、500)的MA-CBS优于其他算法。此外,实验结果表明,MA-CBS的B非极值(即乙=0 也不 乙=∞)的性能优于CBS和其他最新的MAPF算法。结果得出结论,在一般情况下,在一定程度上对代理进行分组最有利。与从不对代理进行分组(如在CBS中)和对所有代理进行分组(如在所有先前的最佳求解器中)相比,这导致更快的求解过程。

总体上,关于MAPF以及CBS和MA-CBS算法的工作面临许多公开挑战:

1。

当前,没有启发式方法可指导高级约束树中的搜索。提出允许的高级别启发法可能会导致显着提高速度。

2。

可以做进一步的工作来了解B参数对MA-CBS的影响,这可以深入了解B如何动态变化。

3。

使用单个B参数合并代理相对简单。一个开放的问题是否是更复杂的合并策略是否可以显着提高性能。例如,合并可能基于地图区域而不是单个代理。

4。

继费纳等。[17]有必要进行实验和比较不同的低层求解器,包括ICTS [42],ODrM * [17],布尔可满足性(SAT)[50],整数线性规划(ILP)[55]和答案集编程(ASP)[13]

5,

在更大的范围内,约束的使用与CSP和SAT的工作重叠,这种联系尚未得到很好的探索。这些领域之间存在理论联系[33],需要进一步研究。

致谢

这项研究是由支持以色列科学基金会(ISF)拨款305/09至阿里尔Felner。

附录A 。内存受限的CBS

最近提出的许多最佳MAPF求解器都需要指数级的内存。对于A *变型,内存用于存储OPEN和CLOSED。对于ICTS,内存用于ICT。两者都是指数的(Δ中的ICTS和k中的A *变体)。在没有换位的域中,可以通过运行迭代加深A *(IDA *)轻松解决此内存问题[26]。但是,IDA *的效率会因为遇到更多重复节点而大大降低。在地图和网格等领域(MAPF最常见的领域)中,重复节点非常频繁。例如,在4个连接的网格中,距给定位置半径r处的唯一状态数为Ø([R2) 但是路径数是 Ø(4[R)。因此,所有先前的最佳MAPF求解器都占用大量内存。接下来,我们描述如何将MA-CBS修改为需要内存大小的有效最优求解器⁎Ø(ķ⋅C⁎⋅|V|),即代理商数量k的乘积,即最佳解决方案费用的费用,⁎C⁎ 以及输入图的大小 |V|。

与A *及其变体不同,CBS搜索概念上不同的状态空间–约束空间。但是,在此空间中也可能会遇到重复状态。图12显示了MAPF实例(左)和具有重复状态的对应CT(右)。在此问题中,存在三个代理。每个都有一个起始位置,小号一世,以及目标位置, G一世。CT的根无限制,并且为代理找到了解决方案(一种1个, 一种2, 一种3)是 {〈小号1个,一种,G1个〉,〈小号2,一种,G2〉,〈小号3,乙,G3〉}。根包含冲突(一种1个,一种2,一种,1个) 和一个新的CT节点 ñ1个 用约束创建 (一种1个,一种,1个)。 ñ1个 包含冲突 (一种1个,一种3,乙,1个)。因此,另一个CT节点ñ2 用约束创建 (一种2,一种,1个) 但它包含了冲突 (一种2,一种3,乙,1个)。接下来,CT节点ñ1个 展开,创建CT节点 ñ3 有约束 (一种1个,一种,1个), (一种3,乙,1个)。然后,CT节点ñ2 扩展生成CT节点 ñ4 有约束 (一种2,一种,1个), (一种3,乙,1个)。CT节点ñ3 创建CT节点 ñ5 有约束 (一种1个,一种,1个), (一种3,乙,1个), (一种2,一种,1个)。CT节点ñ4 创建CT节点 ñ6 有约束 (一种2,一种,1个), (一种3,乙,1个), (一种1个,一种,1个)。可以看出CT节点ñ5 和 ñ6 包含相同的约束集,因此是重复的。

Image removed.

  1. 下载:下载全图

图12。CBS具有周期的MAPF实例示例。

即使上面的示例证明约束树中可能存在重复项,但实际上在4个连接的网格上,我们遇到的重复项很少。我们使用重复检测机制运行了本文报道的所有实验。由于有少量重复数据,有和没有重复检测的结果在所有参数上几乎相同。因此,我们尝试使用迭代加深作为高级搜索算法。迭代加深是深度优先搜索,需要深度与解决方案深度成线性关系。与作为高级求解器的最佳优先搜索相比,迭代加深的平均运行时间高出约12%。

A.1 。具有许多重复状态的域

尽管4连通网格几乎没有重复状态,但其他域(例如随机图)可能包含许多重复状态。对于这些域,DFID作为高级求解器将效率低下。为了解决这个问题,我们开发了一种新的CT分支技术,它将完全防止重复。在CBS中,当发生冲突时(一种1个,一种2,v,Ť) 发现在添加约束的同时将节点拆分为两个子节点 (一种1个,v,Ť) 一个孩子 (一种2,v,Ť)在另一个孩子。对于内存高效型,我们定义了一个新约束(一种一世,v,Ť¯) 这意味着那个代理 一种一世 在时间步t必须位于位置v。现在,当冲突(一种1个,一种2,v,Ť)被发现产生了三个孩子。第一个孩子添加约束{(一种1个,v,Ť),(一种2,v,Ť¯)},即 一种1个在时间t不能位于v中,但是一种2 必须在时间t处在v处。第二个增加了约束{(一种2,v,Ť),(一种1个,v,Ť¯)},即 一种2在时间t不能位于v中,但是一种1个 必须在时间t处在v处。第三个孩子增加了约束{(一种1个,v,Ť),(一种2,v,Ť)},即两者都不 一种1个 也不 一种2允许在时间t处在v中。

这种机制可防止重复发生的可能性,同时仍保持最佳性和完整性。对于包含许多重复项的受内存限制的环境和域,我们建议将此格式与DFID一起用作高级CT搜索算法。

参考文献

[1]

麻仁 Bennewitz ,钨 Burgard ,塞巴斯蒂安· 史朗为移动机器人团队的去耦路径规划技术找到并优化可解决的优先级方案

机器人。自动。Syst。,41 (2 )(2002 ),第89 - 99

文章下载PDF查看Scopus中的记录谷歌学术

[2]

Subhrajit Bhattacharya ,Vijay Kumar ,Maxim Likhachev成对约束的分布式优化及其在多机器人路径规划中的应用

机器人:科学和系统(2010 ),第87 - 94

查看Scopus中的记录谷歌学术

[3]

Subhrajit 查亚,美心 利哈乔夫,维杰 ·库马尔基于搜索的机器人路径规划中的拓扑约束

自动。机器人,33 (3 )(2012 ),第273 - 290

交叉引用查看Scopus中的记录谷歌学术

[4]

Zahy Bnaya和Ariel Felner面向冲突的窗口式分层合作社A *

国际机器人与自动化会议(ICRA)(2014 )

谷歌学术

[5]

Zahy Bnaya ,Roni Stern ,Ariel Felner ,Roie Zivan ,Steven Okamoto自利代理的多代理路径查找

组合搜索(SOCS)研讨会(2013 )

谷歌学术

[6]

Blai Bonet的,埃克托 Geffner规划启发式搜索

Artif。智力 ,129 (1 )(2001 ),第5 - 33

文章下载PDF查看Scopus中的记录谷歌学术

[7]

乔希 石塔,大卫· 马尔兹,戴维· 约翰逊,弘毅春 虎,Jorjeta Jetcheva多跳无线自组织网络路由协议的性能比较

在移动计算和网络国际会议论文集,ACM (1998年),第85 - 97

交叉引用查看Scopus中的记录谷歌学术

[8]

本杰明· 科恩,萨钦 Chitta ,马克西姆 利哈乔夫具有启发式搜索的单臂和双臂运动计划

诠释 J.机器人。Res。(2013年)

谷歌学术

[9]

保罗· 斯皮拉基斯(Paul Spirakis),丹尼尔·科恩豪斯(Daniel Kornhauser),加里· 米勒协调图上的卵石运动,排列组的直径和应用

研讨会计算机科学基础,IEEE (1984 ),第241 - 250

谷歌学术

[10]

鲍里斯· 德·王尔德,阿德里安·W· 之三MORS ,塞斯· 维特芬推动和旋转:协作式多智能体路径规划

AAMAS (2013 ),第87 - 94

查看Scopus中的记录谷歌学术

[11]

丽娜 Dechter ,犹太 珍珠广义最佳优先搜索策略和A *的最优性

J. ACM ,32 (3 )(1985 ),第505 - 536

查看Scopus中的记录谷歌学术

[12]

库尔特M. Dresner ,彼得· 斯通多主体自治路口管理方法

J.Artif。智力 Res。,31 (2008 ),第591 - 656

查看Scopus中的记录谷歌学术

[13]

ESRA 埃德姆,多加G. 克萨,了Umut Oztok ,彼得· 舒莱尔解决多主体问题的通用形式框架

AAAI (2013 )

谷歌学术

[14]

迈克尔· 埃德曼(Tom Lozano-Perez)在多个运动物体上

Algorithmica ,2 (1-4 )(1987 ),第477 - 521

交叉引用查看Scopus中的记录谷歌学术

[15]

Ariel Felner ,Meir Goldenberg ,Guni Sharon ,Roni Stern ,Tal Beja ,Nathan R.Sturtevant ,Jonathan Schaeffer ,Robert Holte具有选择性节点生成的部分扩展A *

AAAI (2012 )

谷歌学术

[16]

阿里尔 Felner ,罗尼 斯特恩,沙立 克劳斯,亚萨 奔亚伊尔,弥敦道S. 内塔尼亚胡PHA *:在未知的物理环境中找到具有A *的最短路径

J.Artif。智力 Res。,21 (2004年),第631 - 670

交叉引用查看Scopus中的记录谷歌学术

[17]

Cornelia Ferner ,Glenn Wagner ,Howie Choset低维搜索空间中的ODrM *最优多机器人路径规划

国际会议机器人与自动化(ICRA) (2013 ),第3854 - 3859

交叉引用查看Scopus中的记录谷歌学术

[18]

嫩 吉尔博亚,阿姆农 Meisels ,林依晨 Felner未知物理环境中的分布式导航

AAMAS ,ACM (2006年),第553 - 560

交叉引用查看Scopus中的记录谷歌学术

[19]

梅尔 ·戈登伯格,阿里尔· 费尔纳,罗尼 ·斯特恩,乔纳森· 舍弗A *变体可实现最佳的多智能体寻路

组合搜索(SOCS)研讨会(2012 )

谷歌学术

[20]

梅厄 登堡,阿里尔 Felner ,罗尼 斯特恩,尼 沙龙,弥敦道R. 斯特蒂文特,罗伯特· 霍尔特,乔纳森· 谢弗增强的局部扩展A *

J.Artif。智力 Res。,50 (2014 ),第141 - 187

交叉引用查看Scopus中的记录谷歌学术

[21]

德文K. 格雷迪,科斯塔斯E. Bekris ,莉迪亚E. Kavraki二阶动力学下具有安全保证的异步分布式运动计划

机器人IX的算法基础,施普林格(2011 ),第53 - 70

谷歌学术

[22]

彼得· 哈特(Peter E.Hart),尼尔斯· 尼尔森(Nils J.Nilsson),贝特拉姆 ·拉斐尔(Bertram Raphael)启发式确定最小成本路径的正式基础

Syst。科学 赛伯恩。,4 (2 )(1968 ),第100 - 107

交叉引用查看Scopus中的记录谷歌学术

[23]

马尔特· 赫尔默特了解计划任务:领域复杂性和启发式分解

卷 4929 ,施普林格(2008 )

谷歌学术

[24]

蕾妮 詹森,弥敦道R. 斯特蒂文特协作寻路的新方法

AAMAS (2008年),第1401 - 1404中

查看Scopus中的记录谷歌学术

[25]

穆赫塔尔M. Khorshid ,罗伯特· 霍尔特,弥敦道R. 斯特蒂文特非最优多智能体寻路的多项式时间算法

组合搜索(SOCS)研讨会(2011 )

谷歌学术

[26]

理查德· 科夫深度优先迭代加深:最佳可允许树搜索

Artif。智力 ,27 (1 )(1985 ),第97 - 109

文章下载PDF查看Scopus中的记录谷歌学术

[27]

理查德· 科夫使用模式数据库找到魔方的最佳解决方案

AAAI / IAAI (1997年),第700 - 705

查看Scopus中的记录谷歌学术

[28]

理查德· 科夫(Richard E.Korf),拉里· 泰勒(Larry A.Taylor)寻找二十四个难题的最佳解决方案

AAAI (1996年),第1202 - 1207

查看Scopus中的记录谷歌学术

[29]

史蒂文· 拉瓦勒(Steven M.LaValle),赛斯· 哈钦森(Seth A.Hutchinson)具有独立目标的多个机器人的最佳运动计划

机器人。自动 ,14 (6 )(1998 ),第912 - 925

查看Scopus中的记录谷歌学术

[30]

瑞安 月神,科斯塔斯·E. Bekris高效,完整的集中式多机器人路径规划

《智能机器人与系统(IROS)(2011 )》,第3268至3275页

查看Scopus中的记录谷歌学术

[31]

露西娅·帕洛蒂诺(Lucia Pallottino),文森佐(Vincenzo Giovanni Scordio),安东尼奥·比基(Antonio Bicchi),埃米利奥·弗拉佐利(Emilio Frazzoli)多车系统中解决冲突的分散合作策略

机器人学,23 (6 )(2007 ),第1170至1183页

交叉引用查看Scopus中的记录谷歌学术

[32]

麦克· 皮斯古德(Mike Peasgood),约翰· 麦克菲(John McPhee),克里斯托弗· 克拉克(Christopher M.Clark)隧道环境中完整且可扩展的多机器人规划

计算 科学 软。。(2006 ),p。75

查看Scopus中的记录谷歌学术

[33]

朱西· 林塔宁(Jussi Rintanen)使用SAT进行规划,可允许的启发式方法和A *

IJCAI (2011 ),页。到2015年-到2020年

查看Scopus中的记录谷歌学术

[34]

加布里埃尔· 勒格(GabrieleRöger),马尔特· 赫尔默特(Malte Helmert)解决了非最优的多智能体寻路(自1984年)

组合搜索(SOCS)研讨会(2012 )

谷歌学术

[35]

马尔科姆RK 瑞安在多机器人路径规划中利用子图结构

J.Artif。智力 Res。,31 (2008 ),第497 - 542

查看Scopus中的记录谷歌学术

[36]

马尔科姆RK 瑞安基于约束的多机器人路径规划

国际会议机器人与自动化(ICRA) (2010 ),第922 - 928

查看Scopus中的记录谷歌学术

[37]

Qandeel Sajid ,Ryan Luna ,Kostas E.Bekris同时执行单代理原语的多代理寻路

组合搜索(SOCS)研讨会(2012 )

谷歌学术

[38]

尼 沙龙,罗尼 斯特恩,阿里尔 Felner ,弥敦道R. 斯特蒂文特基于冲突的搜索,以实现最佳的多智能体路径查找

AAAI (2012 )

谷歌学术

[39]

尼 沙龙,罗尼 斯特恩,阿里尔 Felner ,弥敦道R. 斯特蒂文特基于元代理冲突的搜索,用于最佳多代理路径查找

组合搜索(SOCS)研讨会(2012 )

谷歌学术

[40]

尼 沙龙,罗尼 斯特恩,梅厄 登堡,林依晨 Felner成本增加树搜索以实现最佳多智能体寻路

IJCAI (2011 ),第662 - 667

查看Scopus中的记录谷歌学术

[41]

尼 沙龙,罗尼 斯特恩,梅厄 登堡,林依晨 Felner用于增加成本树搜索的修剪技术,以实现最佳多智能体寻路

组合搜索(SOCS)研讨会(2011 )

谷歌学术

[42]

尼 沙龙,罗尼 斯特恩,梅厄 登堡,林依晨 Felner成本增加树搜索以实现最佳多智能体寻路

Artif。智力 ,195 (2013 ),第470 - 495

文章下载PDF查看Scopus中的记录谷歌学术

[43]

戴维· 西尔弗合作寻路

人工智能和互动数字娱乐(AIIDE) (2005年),第117 - 122

查看Scopus中的记录谷歌学术

[44]

Arvind Srinivasan ,Timothy Ham ,Sharad Malik ,Robert K.Brayton离散函数操纵的算法

计算机国际会议计算机辅助设计(ICCAD) (1990年),第92 - 95

查看Scopus中的记录谷歌学术

[45]

特雷弗· 斯坦德利寻找合作寻路问题的最佳解决方案

AAAI (2010 )