刘庆周,吴 锋

(中国科学技术大学 计算机科学与技术学院,合肥 230027)

0 概述

多智能体路径规划(Multi-Agent Path Planning,MAPP)问题是一类寻找多个智能体从起始位置到目标位置且无冲突的最优路径集合的问题,其在机场拖航[1]、物流仓储[2]、交通控制[3]、机器人[4]、电子游戏[5]等领域都有广泛的应用。近年来,研究人员在多智能体路径规划问题的研究中取得了众多突破性进展,但国内对这些工作进行整理形成的综述较少,最近的相关综述[6]只给出该问题的形式化定义和相关算法的简单分类,没有涉及算法的具体原理和最新进展。

在机器人领域,存在一类被称作多机器人路径规划的问题。多机器人路径规划与多智能体路径规划2类问题存在许多相似之处,例如,两者都关注如何求解问题、提高求解效率与结果质量等。但是,多机器人路径规划同时关注机器人的视觉、定位、通信、运动控制等实际约束和设定,而多智能体路径规划则将这些设定进行抽象化,其将研究的重点集中在问题的求解方式、求解效率和求解质量上。

本文研究多智能体路径规划问题。首先给出多智能体路径规划的问题定义和问题属性,概述主流的4类最优多智能体路径规划算法,解析算法的基本原理,然后分析2类近似多智能体路径规划算法的优缺点。在此基础上,总结多智能体路径规划问题的现有求解算法并对未来的研究方向进行展望。

1 多智能体路径规划

1.1 问题定义

一个经典的多智能体路径规划问题可以被定义为一个四元组〈G,k,S,T〉。其中,G=(V,E)是一个无向图,无向图中的节点v∈V是智能体可以占据的位置,边e=(vi,vj)∈E是vi和vj之间的连线,表示智能体可以在vi和vj之间移动。k代表问题中的智能体数量,即智能体{a1,a2,…,ak}。每个智能体ai都有独一无二的起始位置si∈S∈V和目标位置gi∈T∈V。S是所有智能体初始位置的集合,T是所有智能体目标位置的集合。

在多智能体路径规划问题中,时间被离散化为时间步的形式。在每个时间步中,每个智能体可以采取一次行动。一般来说,有等待和移动2种行动。在多智能体路径规划问题中,存在智能体之间的冲突,且冲突主要有2种,即图1所示的碰撞冲突和图2所示的交换冲突。

图1 碰撞冲突

图2 交换冲突

智能体ai从si移动到gi的行动序列构成一条路径pi。多智能体路径规划问题的一个可行解是k个智能体的k条路径的集合P={p1,p2,…,pk},其中,智能体ai对应于路径pi,路径集合中的任意2条路径pi和pj之间不存在冲突。

多智能体路径规划问题通常都需要最小化某个全局累积代价函数,常用的代价函数有如下4种:

(1)

(2)

(3)

(4)

代价函数式(1)表示最晚到达目标位置的智能体所花费的时间,代价函数式(2)表示路径集合中长度最长的路径长度,代价函数式(3)表示所有智能体分别从各自起始位置到达各自目标位置所花费时间之和,代价函数式(4)表示路径集合中所有路径长度之和。

1.2 问题属性

多智能体路径规划问题的状态空间随着问题中智能体的增多而指数增长,该问题也被证明是NP-hard问题[7]。因此,最优的多智能体路径规划算法只有在智能体相对较少的情况下才有较好的实际应用价值。尽管如此,最优的多智能体路径规划算法仍然有很大的研究价值。适当牺牲多智能体路径规划算法的最优性可以大幅提高算法的执行效率,这也是有边界的次优多智能体路径规划算法的核心思想。除此之外,对最优多智能体路径规划算法的研究可以更深刻地揭示多智能体路径规划问题的特点。

在多智能体路径规划问题的研究中,有2个非常重要的性质,即完整性和最优性。完整性指当问题存在解时,算法能够找到可行解;当问题不存在解时,算法能够终止。最优性指当问题有解时,算法返回的一定是最优解。一般来说,最优的多智能体路径规划算法需要同时满足完整性和最优性,而近似算法没有这种要求,一部分近似算法具有完整性,另一部分则不具备完整性。

2 最优多智能体路径规划算法

如表1所示,最优的多智能体路径规划算法可以分为A*搜索的扩展、代价增长树搜索、基于冲突的搜索和基于规约的方法4类。

表1 最优多智能体路径规划算法对比

2.1 A*搜索的扩展

2.1.1 多智能体路径规划中的A*搜索

A*搜索是一种经典的搜索算法,也同样适用于多智能体路径规划问题。A*搜索在多智能体路径规划中的状态空间一般被称为k-agent状态空间,其状态数等于将k个智能体分别放置在|V|个不同的节点上的状态数,一种放置方法对应于一种状态。A*搜索的初始状态节点表示所有智能体都在各自的初始位置,目标状态节点表示所有智能体都到达各自的目标位置。A*搜索中状态的后继表示所有智能体各自采取一组无冲突的行动从当前状态转移到新的状态。

对A*搜索启发式函数的研究在多智能体路径规划中非常重要。最简单的全局启发式函数是所有智能体各自的启发式函数之和,这在格点图上表现为曼哈顿距离之和,而在欧几里得图上表现为欧几里得距离之和[8]。在很多的多智能体路径规划研究中,采用了更为复杂的全局启发式函数,如SIC[9]和基于模式-数据库的启发式函数[10-11]。然而,采用过于复杂的启发式函数不一定具有积极意义,因为提高启发式函数的计算复杂度可能会降低算法的执行效率。

2.1.2 A*搜索的缺陷和改进

在多智能体路径规划问题的求解中,A*搜索主要有两大缺陷,这些缺陷也使得A*的求解能力严重受到问题中智能体数量的制约。第1个缺陷是搜索状态空间的指数增长,A*搜索的状态空间随着问题中智能体的增多而指数增长,这使得A*中的open-list在智能体过多的情况下会发生溢出;第2个缺陷是搜索分支因子的指数增长,由于每个智能体在每个时间步能够采取b(b>1)种行动,扩展到多个智能体时,A*搜索的分支因子也会随着智能体的增多而指数增长,即bk。上述缺陷导致A*搜索无法求解较多智能体的路径规划问题。

目前,对A*搜索的缺陷进行改进主要通过4种方法,即OD(Operator Decomposition)[9]、EPEA*(Enhanced Partial Expansion)[10-11]、ID(Independence Detection)[9]和M*[12],4种方法的对比见表2。

表2 A*算法的主要改进方法

OD改进的是A*搜索中分支因子指数增长的缺陷。当A*搜索扩展初始状态(si,s2,…,sk)时,只考虑第1个智能体的下一步行动,这样会生成当前状态的一系列后继状态,即一共b个后继状态。在这些后继状态中,只有第一个智能体执行行动,其余的k-1个智能体仍然保持t=0时刻的位置。将生成的这些后继状态节点加入到open-list中,当扩展这些状态节点时,只考虑第2个智能体的行动,并生成新的一系列后继状态。新生成的后继状态代表第1个和第2个智能体可能处于的所有位置,其他智能体仍然处于t=0时刻的位置。按照这样的规则继续进行搜索,直至搜索树上的第k层状态节点能够表示所有智能体在t=1时刻的所有可能位置分布。第k层状态节点表示同一时刻所有智能体的位置分布,这类状态节点被称为满状态节点,其他状态节点被称为中间状态节点。搜索在到达满状态节点(gi,gi+1,…,gk)时终止。OD大幅减小了A*搜索的分支因子。原始A*的分支因子是bk,而ODA*的分支因子是b。相应地,ODA*也引入了大量的中间状态节点,并且使得A*搜索的深度加深了k倍。然而,在多智能体路径规划中,这些中间状态节点一般会因为其启发式函数值过大而被剪枝。因此,OD的引入起到了很大的作用。

EPEA*改进的也是分支因子指数增长的缺陷。EPEA*和A*的不同之处在于,在扩展一个状态节点时,EPEA*生成的后继状态节点不完整,也就是只将一部分的后继状态节点加入open-list中。文献[10]证明了OD是EPEA*的特例,EPEA*的实现细节可以参考文献[11]。

ID改进了A*搜索状态空间的指数增长缺陷,其本质上是一种智能体之间的独立性检测。ID尝试将包含k个智能体的多智能体路径规划问题分解成多个包含更少智能体的子问题。在开始阶段,每个智能体不考虑其他智能体,各自计算自己的最优路径,然后对计算出的k条最优路径进行独立性检测,如果两组路径之间发生了冲突,就将对应的智能体合并为一组,不断地进行合并分组,直到剩下的智能体分组对应的路径组之间不存在冲突,检测终止。使用ID的A*在最坏情况下等于朴素的A*,当不是最坏情况时,ID将原来包含k个智能体的多智能体路径规划问题成功分解,大幅提高了A*算法的执行效率。ID在多智能体路径规划中是一种常用的方法,可以提高多数多智能体路径规划算法的效率。

M*同时改进了状态空间的指数增长和分支因子的指数增长缺陷,其核心思想和ID类似。M*大幅提高了A*算法的性能上限,可以较快地求解规模为20个左右智能体的路径规划问题。M*中存在一个重要的数据结构——冲突集合,冲突集合初始为空,当开始扩展状态节点时,M*中所有智能体依照不考虑其他智能体的各自的最优路径行动,这意味着搜索状态空间的维度是1,分支因子的维度也是1。这样的扩展会使q≥2个智能体在节点v发生冲突时中止。此时,发生冲突的这q个智能体会被加入到冲突集合中,然后重启整个搜索过程。在搜索重启时,冲突集合中的q个智能体会执行朴素的多智能体A*搜索,其余的k-q个智能体依旧按照各自的最优路径参与全局状态扩展,这时状态空间的维度是q,分支因子为bq。M*在所有智能体到达目标位置时终止,M*的最坏情况仍然是回归到朴素的A*。M*的改进型rM*[12]将冲突的智能体分割为没有冲突的分组,递归地解决生成的子问题,从而加速了算法执行。另一种改进型ODrM*[13]在搜索层面上采用ODA*取代朴素的A*,将A*类最优算法求解问题的规模扩大到30个智能体。

上述A*的改进方法之间并非互斥,所有方法都可以同时使用。这些方法仍然是在k-agent状态空间中求解,这也是这类方法的一个显著特征。

2.2 代价增长树搜索

与基于A*的算法不同,代价增长树搜索[14]没有直接在k-agent状态空间中进行搜索。代价增长树搜索分为高层次搜索和低层次搜索2层。高层次搜索的目的是找到每个智能体ai在问题的最优解中所花费的代价ci,即(c1,c2,…,ck)。低层次搜索的目的是验证对于给定的(c1,c2,…,ck),是否存在一组最优解(π1,π2,…,πk),使得∀i∈{1,2,…,k},πi=ci。

2.2.1 高层次搜索

高层次搜索是在代价增长树上进行搜索。代价增长树的状态节点是一组k维向量(c1,c2,…,ck),代表每个智能体ai从起始位置si到目标位置gi花费代价为ci的所有可能的路径集合。代价增长树的根节点是(o1,o2,…,ok),oi是智能体ai不考虑其他智能体的最优路径的代价。(o1,o2,…,ok)是全局最优解的下限。代价增长树通过选取当前状态节点中的一个智能体ai,令ci+1,生成后继的状态节点。对于代价搜索树的一个状态节点(c1,c2,…,ck),如果通过低层次搜索的验证,那么(c1,c2,…,ck)就是一个可行解。因为代价增长树中同一层次的状态节点的代价总和相等,所以在高层次搜索中可以采用宽度优先搜索来找到全局最优解。因此,当找到第一个通过低层次搜索验证的状态节点(c1,c2,…,ck)时,(c1,c2,…,ck)就是全局最优解,算法终止。

2.2.2 低层次搜索

低层次搜索是对高层次搜索的状态节点(c1,c2,…,ck)的验证。低层次搜索首先计算每个智能体ai从起始位置si到目标位置gi花费代价为ci且不考虑其他智能体的所有路径集合,分别使用MDD[15]存储。所有MDD的交叉乘积结果就是所有满足(c1,c2,…,ck)的全局路径集合,这其实是k-agent状态空间中的一个子空间。低层次搜索对MDD叉乘的结果进行搜索,寻找可行解。低层次搜索是验证的过程而非最优化的过程,因此,可以采用有界深度优先搜索来实现。

2.2.3 剪枝加速

代价增长树搜索存在的一个问题是不能很快地验证给定状态节点是否存在解。这个问题可以通过在低层次搜索中验证其子问题是否存在可行解来改进。常用的一种策略是选取所有的智能体对(ai,aj),i,j∈{1,2,…,k},i≠j,当某对智能体(ai,aj)之间不存在无冲突的路径组合时,低层次搜索就可以返回(c1,c2,…,ck)无解。

2.3 基于冲突的搜索

基于冲突的搜索(CBS)[16]和代价增长树搜索有些相似,同样分为高层次搜索和低层次搜索,不同之处在于,CBS求解的是一系列的单智能体路径规划问题。

2.3.1 约束与一致路径

在基于冲突的搜索中,智能体会受到一些约束。对智能体ai的一组约束可以表示为〈ai,v,t〉,表示智能体ai在t时刻不能处于位置v。智能体ai的一致路径指的是满足关于ai的所有约束的路径。全局可行解中每个智能体的路径必须是一致路径,反之则不成立,原因是无法保证智能体的一致路径之间不存在冲突。

2.3.2 高层次搜索

基于冲突的搜索的高层次搜索是在约束树上进行的。约束树是一棵二叉树,树上的每个状态节点包含一个约束集合、一组智能体的一致路径(每个智能体对应一条一致路径)和目前为止的全局代价。约束树根节点中的约束集合是空集。CBS中当前状态节点的后继状态节点会继承当前状态节点的约束集合并加入对某个智能体的一组新约束。一组智能体的一致路径只有在任意一组路径之间都不存在冲突时才是全局可行解。

对于约束树中的某个状态节点,低层次搜索为其寻找一组智能体的一致路径,然后按照时间步模拟每个智能体的行动。如果整个模拟过程中没有发生冲突,那么当前状态节点就是目标状态节点;如果发生了冲突,就需要进行分割操作。分割操作指当约束树中的某个状态节点中的一致路径包含一个冲突〈ai,aj,v,t〉时,需要生成2个约束〈ai,v,t〉和〈aj,v,t〉。对于这2个约束,当前状态节点会分别生成2个后继状态节点,它们的约束集合相比于当前状态节点的约束集合分别增加了〈ai,v,t〉和〈aj,v,t〉。2个后继状态节点将继承当前状态节点中新加入约束中的智能体之外的其他智能体的一致路径,拥有新约束的智能体将会通过低层次搜索生成新的一致路径。

CBS的高层次搜索一般采用最优优先搜索,优先扩展全局代价最小的状态节点。

2.3.3 低层次搜索

CBS的低层次搜索根据约束树节点中的约束集合,寻找满足每个智能体相关约束的一组一致路径。但是低层次搜索无法保证一致路径之间不存在冲突。在低层次搜索中,所有的单智能体路径规划算法都适用。

2.3.4 改进的基于冲突搜索

在加入了上述这些对CBS的优化之后,CBS能够求解30个～60个智能体的路径规划问题。基于冲突的搜索是多智能体路径规划领域中比较新颖的方法,也是目前研究的热点。

2.4 基于规约的方法

上述3类最优多智能体路径规划算法本质上都是基于搜索的算法,而基于规约的方法与它们不同。因为多智能体路径规划问题是NP-hard的问题,可以将多智能体路径规划问题规约为其他的标准问题,如SAT、CSP和ASP等。完成规约的正确性证明后,便可以利用这些问题已有的高质量求解器来求解多智能体路径规划问题。

文献[21]将多智能体路径规划问题规约成了CSP问题,但是该过程对问题中的地图有所要求,只有地图可以被抽象为已知的子图,如环和团等形状时,规约才是正确的。文献[22]将多智能体路径规划问题规约为SAT问题,将问题中地图的结构、智能体的位置和约束编码为布尔变量,然后用这些布尔变量生成标准的SAT问题来验证是否存在全局代价为C的可行解,遍历所有可能的全局代价C就能够生成全局最优解。文献[23]通过改进问题的编码方式,成为较早能够解决求和代价函数的多智能体路径规划问题的SAT求解器。文献[24]将ID用于基于SAT的方法中来求解问题。文献[25]提出新的代价估计方法并减少SAT模型中变量的数量,从而加速了算法执行。文献[26]通过将多智能体路径规划问题中2个智能体之间的约束转化为ASP中的程序P来求解问题,P的答案集就是问题的解集。文献[27-28]将多智能体路径规划问题规约为一个网络流问题,规约后网络流中流的深度和多智能体路径规划中的时间步相关,然后将多智能体路径规划问题的形式转变为一系列等式和一个目标函数,利用整数线性规划来求解最优解。文献[29]将多智能体路径规划问题规约为TSP问题,改进了IPL模型,提出了有效的模型绩效评价指标,利用已有的ILP求解器求解变形之后的问题。

基于规约的方法的难点在于规约的证明,一般需要极强的数理功底。在一般情况下,这类方法的求解速度高于上述基于搜索的最优算法,但是它们无法保证完成规约证明之后使用相应求解器时的高效性。

3 近似的多智能体路径规划算法

因为多智能体路径规划问题是NP-hard问题,求解最优解的算法需要很长的执行时间,为了加速问题的求解,往往需要牺牲一些结果的最优性。近似的多智能体路径规划算法可以分为无边界次优的和有边界次优的算法。多数近似算法都是无边界次优的,而有边界的次优算法一般都是最优算法的衍生算法。一般来说,有边界的次优算法的速度会快于最优算法,但是慢于无边界次优的算法;在结果的最优性上,有边界的次优算法会略逊于最优算法,但是优于无边界的次优算法。

3.1 无边界次优的多智能体路径规划算法

无边界次优的多智能体路径规划算法能够快速地计算出一个可行解,但是无法保证结果的质量。早期研究的局限性都较大,比如文献[30]能够保证算法具备完整性,但是结果的质量可能远低于最优结果,并且在每个时间步中只允许一个智能体采取行动。无边界次优算法分类与对比如表3所示。

表3 各类无边界次优的多智能体路径规划算法对比

3.1.1 基于搜索的无边界次优算法

文献[31]提出了CA*及其改进型HCA*和WHCA*。这类算法顺序地为每个智能体单独规划路径,已经规划的路径会被记录在留存表中,后续在智能体规划路径时不能和留存表中的路径发生冲突,但上述算法并不具备完整性。文献[32]提出了一种具备完整性的无边界次优算法,其本质上是对A*算法的约束放松。文献[33]将状态空间进行抽象化来减少启发式函数的计算时间。文献[34]提出了一种动态修改路径的2段协调方法,在第1阶段使用A*搜索每个智能体的最优路径,在第2阶段采用增量式A*算法解决路径之间的冲突问题。文献[35]在文献[31]的基础上,将窗口放置于已知的冲突位置附近,并将所有智能体根据参与到冲突中的可能性大小进行优先级排序,按照优先级来为智能体规划路径。文献[36]提出了一种基于保留区域的分布式多智能体路径规划算法,解决了多智能体路径之间高度耦合的问题。一般而言,与基于规则的算法相比,基于搜索的无边界次优算法的速度没有特别大的优势,但是结果的质量会更好。

3.1.2 基于规则的无边界次优算法

在基于规则的无边界次优算法中,智能体在不同的场景下有不同的行动规则,并且不需要进行大规模的搜索。基于规则的无边界次优算法能够很快地求解问题,但是其结果质量可能远逊于最优解。

基于规则的无边界次优算法的一个重要性质就是完整性,但是这类算法的完整性往往对问题中地图的性质有特殊的要求。文献[37]提出一种基于规则且具备完整性的无边界次优算法,但是其实际实现时难度极大。文献[38]算法只有在树形图上才具备完整性。文献[39]算法只有在双连通图上才具备完整性。文献[40]算法只有在强双连通图上才具备完整性。

文献[41- 43]只有在地图中至少存在2个未被智能体占据的空位置节点时才具备完整性。文献[41]引入2个macro操作符,macro可以将智能体推到空位置节点,还可以交换2个智能体的位置。文献[42]提出文献[41]的改进算法,不同于文献[41]中每个时间步内只允许一个智能体行动,文献[42]可以并行地为所有智能体规划路径。文献[43]通过引入新的旋转操作符来改进文献[41]算法。

此外,还存在一些混合类型的算法,即算法中既存在智能体行动的规则也存在大规模的搜索,比如文献[44]通过引入交通规则来减少搜索。目前,对混合方法的研究较少,但是这类混合方法给多智能体路径规划的研究带来了很大的启发。

上述基于规则的无边界次优算法的求解速度一般较快,但是无法保证其结果的质量。

3.1.3 基于规约的无边界次优算法

文献[45]通过将问题规约为CSP问题,即令每个智能体对应一个变量,变量的值域就是智能体从起始位置到目标位置的所有可能路径的集合,则问题的约束就是智能体的路径之间不能存在冲突。文献[46]通过使用矩阵计算加速变量值域的缩减,引入动态变量排序和快速随机重启等技巧,取得了较好的效果。文献[47]提出了一种基于ASP的无边界近似分布式多智能体路径规划算法,其能够处理很大规模的多智能体路径规划问题。文献[48]提出基于SAT的无边界次优算法,其通过移除文献[23]中的数量约束,从而将文献[23]算法从最优算法转变为无边界次优的算法。

3.1.4 其他无边界次优算法

其他无边界次优算法主要包括基于强化学习、基于遗传算法、基于协同进化和基于蚁群算法的算法。

国内近期提出了一类基于强化学习的多智能体路径规划算法。文献[49]通过采用无模型的在线Q学习方法,使得多个智能体重复“探索-学习-利用”过程,积累历史经验评估动作策略并优化决策。文献[50]提出了一种基于分层强化学习和人工势场的多智能体路径规划算法,其将多智能体的所在环境虚拟为一个人工势能场,根据先验知识确定每个节点的势能值,代表最优策略可获得的最大回报,利用分层强化学习方法中的无环境模型学习和局部更新能力,将策略更新过程限制在规模较小的局部空间或维度较低的高层空间中。

在早期的基于遗传算法中,文献[51]采用链接图法建立了智能体工作空间模型,采用遗传算法规划多智能体运动路径,引入适应值调整矩阵的新概念,实现了对多智能体路径的全局优化。近期,文献[52]以多智能体执行任务的自身代价与任务间的关联代价为优化目标,使用遗传算法求解问题。

在基于协同进化的算法中,文献[53]通过采用协同进化算法、设计适应度评价函数和引入一系列新的变异操作算子,以求解问题。

在基于蚁群的算法中,文献[54]通过建立有权图模型,采用蚁群算法求解多智能体路径规划问题。文献[55]提出了一种多步长的改进蚁群算法,以改进文献[54]算法收敛速度慢、容易陷入局部最优的缺陷。

上述算法的主要问题是容易陷入局部最优,并且无法保证结果的质量与算法的完整性。

3.2 有边界次优的多智能体路径规划算法

有边界次优的多智能体路径规划算法指对于常量ε>0,算法给出结果的代价最多是最优结果代价的1+ε倍,一般称这类算法为ε次优的算法。理论上而言,当ε变大,算法的速度也会变快。因此,在算法的速度和结果质量上存在均衡。现有有边界次优的多智能体路径规划算法都是在前述最优算法的基础上牺牲最优性得来的次优算法。4种主要的有边界次优算法的对比结果如表4所示。

表4 有边界次优的多智能体路径规划算法对比

3.2.1 基于A*的有边界次优算法

多数基于A*的有边界次优算法都是通过修改A*搜索的启发式函数来实现的。文献[56]通过使用g+(1+ε)h的启发式函数来选择待扩展的状态节点。前述所有基于A*的最优算法都可以使用这种估计函数转变为有边界次优算法,比如文献[12]提出的inflated M*。

文献[57]使用(C-g)/h的启发式函数,并且将算法次优的边界改进为问题要求的次优边界与open-list中最小的启发式函数值的积。

3.2.2 基于代价增长树搜索的有边界次优算法

因为代价增长树搜索的高层次搜索是宽度优先搜索,低层次搜索只是高层次搜索的验证,不存在启发式函数,所以对于基本的多智能体路径规划问题不存在有边界次优的算法。但是如果在多智能体路径规划问题的定义中加入新的约束,比如保证问题中地图的所有边权值不同,则文献[58]算法可以看作是代价增长树搜索的一个有边界次优衍生算法。

3.2.3 基于冲突搜索的有边界次优算法

CBS的低层次搜索通常是最优的单智能体最短路径算法,比如A*。因此,所有基于A*的有边界次优算法都可以在CBS的低层次搜索中实现,这是实现基于CBS的有边界次优算法的一种途径。

如果要在高层次搜索中引入次优性,比较常用的方法是引入FS(Focal Search)[59]。FS在每次扩展时从focal-list中选择状态节点,而不是从open-list中选择。对于常数ω,focal-list中存储的是open-list中代价小于等于ω倍open-list中最优状态节点代价的状态节点。因此,在引入FS之后,高层次搜索就有2个启发式函数可以引入次优性,即open-list的启发式函数和focal-list的启发式函数。

文献[60]在CBS的高层次搜索和低层次搜索中引入了次优性,为ω1次优。文献[61]算法是文献[60]算法的改进,其加入了直连边,使得算法是ω1ω2次优。文献[62]算法在文献[61]的基础上进行优化,使得算法仍然是ω1次优。

3.2.4 基于规约的有边界次优算法

在多智能体路径规划算法中,单独研究基于规约的有边界次优算法的工作较少,因为只要证明了规约的正确性,那么相关规约的有边界次优算法都可以应用于多智能体路径规划问题的求解中。比如,文献[48]通过放松文献[23]中的数量约束,赋予其更松弛的代价边界,将最优算法转变为有边界次优的算法。

4 研究展望

近年来,传统的基于搜索的算法虽然仍然是研究热点,但是基于规约的方法以及其他方法也引起了学者们的关注,比如文献[63]使用深度强化学习和卷积神经网络来求解多智能体路径规划问题,文献[64]将基于搜索的方法和基于SAT的方法相结合,以求解多智能体路径规划问题。值得注意的是,现有所有多智能体路径规划算法都不能在所有类型的问题中取得超过其他所有算法的性能,即不同算法适用的问题类型不同。本文将未来的研究方向归纳为以下5个方面:

1)多智能体路径规划理论需要系统地对问题中相应参数(比如智能体数量、智能体密度和地图尺寸等)对问题求解难度的影响进行量化分析,上述研究可以采用控制变量法来实现。在相关参数中,本文认为智能体密度和地图中的障碍物密度可能是影响问题求解的主要因素。

2)新算法逐渐涌现,但是对于目标函数之间的差异,目前研究比较少,多数研究都只针对其中一种来验证算法的性能。在前述的4种目标函数中,求和形式的目标函数在研究中被广泛应用,但是求最值形式的目标函数才是最具有实际应用价值的,这就使得在理论研究和实际应用中存在鸿沟。求和形式的目标函数在研究中最受欢迎,是因为该类型的目标函数容易求导并证明算法的最优性,这也意味着部分最优的算法可能无法适用最值型的目标函数。因此,需要对不同目标函数在不同算法中的兼容性进行研究。

3)不同算法擅长求解的问题一般不同,需要对已有算法之间的关联性和性能差异做出量化分析,目前也缺少被广泛接受的标准测试集。由于多智能体路径规划算法的开源较少,且论文一般不会提供相关代码,在算法之间进行比较的工作量会非常大。

4)对于经典多智能体路径规划问题的变形进行研究正在逐渐受到重视。经典模型对现实生活中问题的建模能力比较弱,在实际生活中,路径规划问题可能会包含信号灯、优先级、概率等因素,使得经典算法不再适用。因此,为了更好地在实际问题中应用多智能体路径规划算法,主流的研究不能只局限于经典模型。

5)类似于机器学习中的模型融合,考虑到各类多智能体路径规划算法对不同特点问题的求解性能差异,可以对各类算法的融合进行研究。本文认为,多智能体路径规划算法之间的融合主要有2种方法:第1种方法是对于给定的问题,可以利用多线程使用各种算法来求解,当某种算法求解成功之后终止所有算法,但是,考虑到这些算法对计算资源的需求较大,融合算法的计算代价可能极高;第2种方法是在求解问题之前,先分析问题以获得问题参数,然后根据参数来选取求解算法,问题中的部分参数如智能体数量、地图尺寸等一般已知,但是在问题中还会存在一些未知的参数,如智能体密度、障碍物密度等,对于这类参数可以通过采样来估计。在获得上述参数之后,通过建立决策树模型来决定采取何种算法求解问题。

5 结束语

本文介绍多智能体路径规划问题以及最优算法、无边界的次优算法和有边界的次优算法3类求解算法。最优算法能够保证结果的最优性,但是速度最慢,无边界的次优算法速度最快,但是结果质量无法保证,有边界的次优算法能够保证结果的质量,速度处于最优算法与无边界的次优算法之间。在实际应用中,只有当问题规模较小时,才适合使用最优算法,而当问题规模较大时,可以根据对结果质量的需求使用有边界或无边界的次优算法。鉴于不同算法适用问题的类型不同,下一步除了探究性能更好的算法之外,还将深入分析已有算法适用问题的差异性,量化问题参数对规划结果影响的大小,推动融合算法的进一步发展。