随着人工智能技术的不断发展，多智能体路径规划^[1]在自动仓库^[2-4]、数字游戏^[5]、火车调度^[6]、城市道路网络^[7]、多机器人系统^[8]等方面有广泛的应用前景。多智能体路径规划是指在给定地图下，为给定的所有智能体，以最小路径代价或者最小化最大完工时间为目标，求解无冲突路径。其中，最大完工时间表示最后一个智能体到达目标点的时间。

基于冲突的搜索(conflict-based search, CBS)算法^[9]是近年来多智能体路径规划备受关注的算法之一，许多已有文献在它的基础上进行了一系列研究^[10–18]，包括优先解决关键冲突、绕过冲突、向高层添加启发值、对称推理技术等。CBS算法的中心思想是低层使用解耦路径规划算法为每个智能体规划路径，高层在约束树(constraint tree, CT)上检测并解决路径冲突。冲突的选择会影响CBS的运行效率，选择一个“好”的冲突，能够快速地增加约束树的下界，避免陷入相同代价节点的泥潭，从而更快地扩展到目标节点找到最优解。针对这个问题，Boyarski等^[10]提出使用多值决策图(multi-value decision diagram, MDD)将冲突分类，并先消解优先级高的冲突，被广泛应用到其他改进CBS算法的文献中。Huang等^[19]提出了一个新的冲突选择策略，并首次采用新的机器学习框架来学习该策略，其效果相较于文献[10]，表现更佳，有效地提高了算法的求解效率和成功率。为了进一步提高算法的求解效率，本文在文献[19]的基础上，针对使用其冲突选择策略，可能会出现一个节点中所有冲突都应被选择，即有时冲突的区分度不明显的问题，提出一个新的冲突选择策略，并采用RankNet算法^[20]学习该策略，改进算法使用学习得到的排序模型为CBS算法选择冲突，能更快地选择“好”的冲突，能大幅缩短算法的总运行时间和缩小搜索空间，有效提高算法的求解效率。仿真验证所提的改进算法在运行时间、搜索空间和成功率上的有效性。

1.   预备知识

1.1   多智能体路径规划

多智能体路径规划(multi-agent path finding, MAPF)^[21]是为一组智能体 $\{ {a_1},{a_2}, \cdots ,{a_k}\} $ 在指定的无向图 $G = (V,E)$ 下寻找一组无冲突的路径，其中 $k$ 为智能体的数量， $V$ 是图中顶点的集合， $E$ 是图中顶点之间连接边的集合，用 $v \in V$ 表示智能体可以在图中占据的顶点，用 $e = ({v_i},{v_j}) \in E$ 表示智能体可以从 ${v_i}$ 移动到 ${v_j}$ 或相反。每个智能体 ${a_i}$ 都有其起始位置 ${s_i} \in V$ 和终点位置 ${g_i} \in V$ 。时间被离散化为时间步，在每一个时间步，智能体可以移动到非障碍节点的邻节点也可以停在原地等待，不论移动还是等待，路径代价都增加1。单个智能体的路径代价等于智能体从起点到达终点并且之后不再移动所花的总时间步长。本文考虑两种智能体之间发生的冲突：顶点冲突和边冲突。顶点冲突 $ < {a_i},{a_j}, u,t > $ ，即智能体 ${a_i}$ 和 ${a_j}$ 在相同的时间 $t$ 都处在位置 $u$ ；边冲突 $ < {a_i},{a_j},u,v,t > $ ，即智能体 ${a_i}$ 和 ${a_j}$ 相向而行， ${a_i}$ 在时间 $t$ 处在位置 $u$ ， $t + 1$ 时间处在位置 $v$ ，而智能体 ${a_j}$ 在时间 $t$ 处在位置 $v$ ， $t + 1$ 时间处在位置 $u$ 。本文以最小路径代价为目标，为所有智能体找到从起点到终点总路径代价最小的一组无冲突路径。

1.2   基于冲突的搜索

CBS算法是两层算法，高层检测所有路径中是否存在冲突，低层使用space-time A*算法^[22]解耦地为智能体求解有约束下的最优路径。高层对CT进行搜索，CT是一颗二叉树，CT中的每个节点 $N$ 由以下信息组成：

1) 约束集 $ {N_{{\text{cons}}}} $ ：约束由冲突分裂而来，且每个约束都只与一个智能体有关。顶点冲突会分裂为 $ < {a_i},u,t > $ 和 $ < {a_j},u,t > $ ，表示为不允许智能体 ${a_i}({a_j})$ 在时间 $t$ 处在位置 $u$ 。边冲突则分裂为 $ < {a_i},u,v,t > $ 和 $ < {a_j},v,u,t > $ ，表示为不允许智能体 ${a_i}({a_j})$ 在时间 $t \to t + 1$ 从位置 $u(v)$ 到位置 $v(u)$ 。CT中根节点的约束集为空，其他节点的约束集 $ {N_{{\text{cons}}}} $ 除继承父节点的所有约束外，还包括一个新约束，它来自父节点所选冲突分裂生成的约束。

2) 解决方案 ${N_{{\text{sol}}}}$ ：含有每一个智能体 ${a_i}$ 的路径，且每一条路径都满足 $ {N_{{\text{cons}}}} $ 中所有与 ${a_i}$ 有关的约束条件。

3) 冲突集 ${N_{{\text{conf}}}}$ ： ${N_{{\text{sol}}}}$ 中存在的所有冲突。

4) 总路径代价 ${N_{{\text{cost}}}}$ ： ${N_{{\text{sol}}}}$ 中所有路径的代价总和。

CBS算法首先生成根节点，根节点的 $ {N_{{\text{cons}}}} $ 为空， ${N_{{\text{sol}}}}$ 由低层算法为每个智能体规划的路径构成，并计算总路径代价 ${N_{{\text{cost}}}}$ ，而后检测 ${N_{{\text{sol}}}}$ 存在的路径冲突并构成 ${N_{{\text{conf}}}}$ 。每次都在CT中选择最小 ${N_{{\text{cost}}}}$ 的节点进行扩展，并检测当前扩展节点的 ${N_{{\text{conf}}}}$ 是否为空，若 ${N_{{\text{conf}}}}$ 为空也即无冲突存在，则CBS算法停止运行并返回解 ${N_{{\text{sol}}}}$ ；相反，CBS算法默认情况下随机在 ${N_{{\text{conf}}}}$ 选择一个冲突，将其分裂的两个约束分别作为左右子节点的新约束，并继承父节点的约束集构成两个子节点的约束集 $ {N_{{\text{cons}}}} $ 。子节点只为新约束所涉及的智能体重新规划满足当前子节点 $ {N_{{\text{cons}}}} $ 的路径，其余智能体的路径不变，以此构成子节点的 ${N_{{\text{sol}}}}$ ，若子节点有解则将其加入CT中等待被扩展。CBS算法具有完整性和最优性，它通过解决每个冲突的两种情况来保证其完整性，通过在高层和低层中都使用最佳优先搜索来保证其最优性。

2.   改进CBS多智能体路径规划算法

对于CBS算法，选择一个“好”的冲突能更快地扩展到目标节点，从而有效地缩小搜索空间，提高算法在路径规划中的求解效率。由此提出一种改进冲突选择策略，并验证其消解冲突的有效性；然后，为了发挥改进冲突选择策略的优势和进一步缩短算法的运行时间，采用基于神经网络的RankNet算法学习该改进策略，用训练好的排序模型为CBS算法选择冲突。

2.1   冲突选择策略

为了与已有冲突选择策略展开比较，也便于后续问题的阐述，事先给出以下2种冲突选择策略的定义。定义1来自文献[10]，将冲突划分优先级，并优先选择高优先级冲突进行消解。定义2来自文献[19]，通过假使每个冲突被选择，其生成的相应两个子节点的 $g + h$ 的最小值作为该冲突的得分，优先选择得分高的冲突。

定义1^[10] 　对给定的CT中节点 $N$ ， ${S _0}$ 使用MDD^[23]将 ${N_{{\text{conf}}}}$ 中的冲突的优先级从高到低分类为关键冲突，半关键冲突及非关键冲突。存在相同优先级的冲突时，优先选择冲突发生时间更小的冲突。

定义2^[19] 　对给定的CT中节点 $N$ ， ${S _1}$ 计算 ${N_{{\text{conf}}}}$ 中每个冲突的得分 $ {v_c} = \min \{ g_c^l + h_c^l,g_c^r + h_c^r\} $ ，其中 $g_c^l + h_c^l$ 和 $ g_c^r + h_c^r $ 分别表示如果该冲突被选中，生成的左右两个子节点的 $g + h$ 值， $g$ 为 ${N_{{\text{cost}}}}$ ， $h$ 由加权依赖图(weighted pairwise dependency graph, WDG)^[24]给出。并将得分由高到低进行排序，优先选择得分最高的冲突。

使用 ${S _1}$ 作为冲突选择策略求解实例的过程中有时会出现一个节点中所有的冲突得分都相同，而这些冲突对应的子节点的总路径代价不同，包含的冲突数差异较大，未做进一步区分可能选择的冲突会使其子节点包含更多的冲突数，以至于需要扩展更多节点来消解冲突的情况。

为了更直观地展示这一情况，下面给出一个具体实例。如图1(a)所示，智能体0、1、2分别从起点 ${{{B}}_{\text{2}}}$ 、 ${{{D}}_{\text{2}}}$ 、 ${{{D}}_{\text{1}}}$ 出发，到目标点 ${{{C}}_{\text{2}}}$ 、 ${{{B}}_1}$ 、 ${{{A}}_{\text{2}}}$ 。使用CBS的改进算法CBS+PC^[10]+BP^[25]+WDG^[24]算法（以下仍简写为CBS算法）求解，使用 ${S _1}$ 选择冲突，得到的约束树如图1(b)所示。在调用低层算法单独为每个智能体规划最优路径后，高层检测到路径间存在两个冲突 $ < 0,1,{{{C}}_{\text{1}}},2 > $ 和 $ < 0,2,{{{C}}_2},2 > $ 。分别选择这两个冲突进行消解，得到相应的子节点信息位于冲突集一栏该冲突的右侧。其中， $l$ 和 $r$ 分别表示该冲突的左、右子节点的信息即子节点的 $g + h$ 和子节点中包含的冲突数。可以看出使用 ${S _1}$ 计算得到两个冲突的得分均为10，若不做进一步区分，选择 $ < 0,1,{{{C}}_{\text{1}}},2 > $ 进行消解，则生成的左右两个子节点中分别含有2个和5个冲突，需要扩展更多的节点来消解冲突，最终生成5个节点才能找到目标节点。

图  1  多智能体路径规划实例及其约束树

Fig.  1  MAPF instance and its constraint tree

下载: 全尺寸图片

若根据冲突的子节点的信息进一步区分，在冲突的得分相同的情况下，优先选择能使子节点更靠近目标节点的冲突，也即选择能生成 $g$ 更大，冲突数更少的子节点所对应的冲突。在此情况下，选择 $< 0,2,{{{C}}_2},2 >$ 进行消解，其约束树如图1(c)所示，则只需生成3个节点就能够找到目标节点。因此，从进一步对冲突进行区分的角度出发，对现有冲突选择策略进行改进使其更具有优越性。

2.2   改进冲突选择策略

接下来具体说明如何改进冲突选择策略。

定义3即改进冲突选择策略仍按照定义2优先考虑 $g + h$ ，其次考虑 $g$ ， $g$ 越大 $h$ 越小则意味着生成的子节点的总代价更接近目标节点的总代价。在两个子节点 $g + h$ 相同的情况下优先扩展 $g$ 更大的节点，更可能使整个约束树更快地找到最优解。在此基础上，为了充分利用子节点的信息，还考虑另一个子节点的 $g$ 。其目的是向约束树中添加 $g$ 更大（更接近目标节点）的CT节点，以加速求解最优解的过程。

定义3　对给定的CT中节点 $N$ ， ${S _2}$ 不仅计算 ${N_{{\text{conf}}}}$ 中每个冲突 $c$ 的得分 ${v_c}$ （同定义2），还要收集该冲突 $c$ 的得分 ${v_c}$ 对应的子节点的 $g$ 值，与另一个子节点的 $g$ 记为 $g'$ 。首先将每个冲突的得分 ${v_c}$ 从高到低排序，再将相同的 ${v_c}$ 按 $g$ 从高到低排序，再将相同的 $g$ 按 $g'$ 从高到低排序。优先选择 ${v_c}$ 最高的冲突，其次选择 $g$ 最高的冲突，最后选择 $g'$ 最高的冲突。

为了验证改进冲突策略的有效性，选择CBS算法为多智能体规划路径，使用Python语言编程和实现，仿真实验在处理器为Intel(R) Core(TM) i5-12500H CPU @ 2.50 GHz，RAM为16 GB的计算机上运行，分别采用冲突选择策略 ${S _0}$ 、 ${S _1}$ 和 ${S _2}$ 在随机地图上进行测试。随机地图大小为20×20，存在有25%的随机障碍物，如图2所示。在此随机地图上生成50组随机起点和终点的实例，每个实例的运行时间限制为20 min，每个实例中智能体数固定为17。为了凸显改进冲突策略和排序模型的优势，大致将总的运行时间分为选择时间和搜索时间。选择时间精准记录了算法在整个求解过程中所有用于运行冲突选择策略的时间，而搜索时间等于运行时间减去选择时间。搜索空间主要由CT大小来衡量，它表示CBS算法成功求解实例时生成CT节点的数量。仿真实验结果如表1所示，其中运行时间、CT大小、选择时间和搜索时间每一栏具体数值均为该50组相应数据的平均值。可以看出，改进策略 ${S _2}$ 与 ${S _1}$ 的搜索时间和CT都小于 ${S _0}$ ，均可有效缩小搜索空间和缩短搜索时间，且 ${S _2}$ 在CT大小上优于 ${S _1}$ ，体现出改进策略的有效性。总的来说，改进策略 ${S _2}$ 表现更好。

图  2  随机地图

Fig.  2  Random map

下载: 全尺寸图片

2.3   机器学习算法学习冲突选择策略

使用文献[19]中使用的SVM方法与本文所用RankNet算法两种机器学习算法来分别学习冲突选择策略 ${S _1}$ 和 ${S _2}$ 。使用机器学习算法学习冲突选择策略主要分为两个部分：构建数据集和训练排序模型。

2.3.1   构建数据集

需构建两个数据集：训练集 ${I_{{\text{train}}}}$ 和测试集 ${I_{{\text{test}}}}$ 。 ${I_{{\text{train}}}}$ 和 ${I_{{\text{test}}}}$ 是由若干实例 $I$ 的数据集 ${D_I}$ 连接而成，每个实例均由在指定地图上随机生成的始末点构成。仅在数据收集和模型学习阶段，固定实例的智能体数。CBS算法在求解实例 $I$ 时，需收集如下数据来构建数据集 ${D_I}$ ，具体步骤如下：

1) 收集CT中所有生成的节点 ${{\cal{N}}}$ ；

2) $\forall N \in {{\cal{N}}}$ ，收集节点 $N$ 的冲突集合 ${N_{{\text{conf}}}}$ ；

3) $\forall N \in {{\cal{N}}}$ ，对每个冲突 $c \in {N_{{\text{conf}}}}$ 收集其特征向量 $\boldsymbol{\varPhi}_N: N \in {\cal{N}} \rightarrow[0,1]^p$ ，每个冲突 $c$ 均有 $p$ 个特征值；

4) $\forall N \in {{\cal{N}}}$ ，对每个冲突 $c \in {N_{{\text{conf}}}}$ 收集其二值标签 ${y_c} \in \{ 0,1\} $ ，对每个节点 $N$ ， ${y_N} \in {\{ 0,1\} ^{|{N_{{\text{conf}}}}|}}$ 。

对步骤3)和4)中的特征值和标签值的具体说明如下：

特征值　本文使用 $p$ 维特征向量来表示一个冲突 $c$ ，参考文献[19]列出的特征指标对每个冲突生成其相应的特征值，一个冲突包含67个特征值。这67个特征值主要包括以下几个方面：

1) 冲突的性质。主要有冲突的类型（顶点冲突和边冲突）和优先级（关键冲突、半关键冲突和非关键冲突）。

2) 在当前CT节点之前已经扩展的所有CT节点中，统计与冲突有关的智能体或点被选中的频率。

3) 与当前CT节点 ${N_{{\text{sol}}}}$ 相关的，CT节点 $N$ 、与冲突有关的两个智能体 ${a_i}$ 和 ${a_j}$ 以及顶点 $u$ 或边 $(u,v)$ 的信息。

4) 冲突的MDD特性和WDG。

5) 对于当前冲突中的顶点 $u$ 或边 $(u,v)$ ，统计地图 $G$ 中距离 $u$ （距离 $u$ 或 $v$ ）最短路径为1~5的所有顶点的数量。

由上述5个方面可知，生成特征值所需要的信息有部分依赖于所处的地图环境，但生成特征值的方法并不依赖于地图环境。因此，可以使用同样的方法在其他地图上收集相应的特征值与标签值，经训练得到与其他地图有关的排序模型。

对于每个冲突 $c$ 的特征值，需以 ${N_{{\text{conf}}}}$ 为一组将特征值归一化为 $[0,1]$ ，以消除奇异样本数据导致的不好影响。

标签值　标签值由选定的冲突选择策略生成，并将其二值化。本文使用的标签二值化策略参考文献[19]，将排序后 ${N_{{\text{conf}}}}$ 中前20%的冲突的标签为1，其余标签为0，若其他的冲突和标签已经转化为1的冲突都有着相同的得分，则将其他冲突的标签也设置为1。这样设置使得排序模型能更专注于评分较高的冲突，尽可能少被不相关的冲突干扰。

将收集好的特征数据和标签数据一一对应，以一定的格式构建数据集。

2.3.2   训练排序模型

训练SVM排序模型的方法与文献[19]类似，这里不做赘述，下面重点介绍使用RankNet算法训练排序模型。

RankNet算法^[20]是一个经典的排序学习算法，本文使用该算法预测每个冲突和它所属节点的相关性大小，并依此来对冲突进行排序，进而选择“好”的冲突。训练出较为准确的排序模型具体来说是要确定函数 $f(x,w)$ ，其中 $x$ 为冲突特征， $w$ 为排序模型参数。通过多次训练，使 $f$ 所计算出的结果尽可能和真实值接近，即让训练集中所有冲突的偏序对 $P$ 经计算后排序概率误差最小：

其损失函数 ${C_{ij}}$ 为交叉熵损失函数：

其中，因RankNet算法是基于pairwise的排序学习方法，故需将数据集中的冲突转换为冲突的偏序对 $ P $ 作为输入。 ${P} $ 由 $ P_{N} $ 连接而成， ${P_N} = \{ ({c_i},{c_j})|{c_i}, {c_j} \in {N_{{\text{conf}}}} \wedge {S_{ij}} = 1\} $ ， $ S_{i j}=1 $ 表示冲突 $ c_{i} $ 比冲突 $ c_{j} $ 真实更相关。 $ n $ 为冲突的偏序对的总数， ${\bar y}_{i j} $ 为冲突 $ c_{i} $ 比冲突 $ c_{j} $ 排序更靠前的真实概率， ${\bar y_{ij}} = 0.5 \times ({S_{ij}} + 1)$ ， $ y_{i j} $ 为经模型计算后冲突 $ c_{i} $ 比冲突 $ c_{j} $ 排序更靠前的预测概率。

2.4   排序模型指导CBS算法选择冲突

利用得到的排序模型为CBS算法选择冲突的具体步骤如下：对每个当前节点 $N$ ，当其冲突集 ${N_{{\text{conf}}}}$ 中所含冲突数大于1时，先计算每个冲突的特征向量，并将其归一化后输入到排序模型中，经排序模型打分得到 ${N_{{\text{conf}}}}$ 中所有冲突的得分，因排序模型打分越高代表该冲突与当前节点相关性越高，即分数越高的冲突标签为1的可能性越大，故选择排序模型打分最高的那个冲突 $c$ 。

2.5   机器学习算法的选择

2.5.1   SVM参数设定

为了与文献[19]对照，SVM参数设定与文献[19]相同，即选择线性核， $\mathfrak{c}$ 为0.01。

2.5.2   RankNet 模型设计

采用Python语言以及PyTorch框架实现RankNet算法。网络参数设置如表2设置。使用Xavier初始化，使用momentum为0.9的SGD优化器，将初始学习率设为0.01，使用L2正则化和dropout减少过拟合。

2.5.3   训练结果

分别构建使用 $S _1 $ 和 $S _2 $ 策略的数据集，训练集收集5000个节点，训练集与测试集的比例为3∶2。训练结果如表3所示。主要从测试集的P@1来考虑，P@1表示经排序模型选取的冲突，标签为1的概率。

表  3  SVM和RankNet分别学习 ${S _1}$ 、 ${S _2}$ 的结果

Table  3  Comparison of SVM and RankNet with conflict selection strategie ${S _1}$ , ${S _2}$

机器学习算法	冲突选择策略	P@1/%
SVM	${S _1}$	85.98
RankNet	${S _1}$	92.60
SVM	${S _2}$	69.84
RankNet	${S _2}$	78.20

从结果上看，在相同机器学习算法不同冲突选择策略的情况下，学习S₁的效果整体上优于S₂；在相同冲突选择策略不同机器学习算法的情况下，使用RankNet得到的排序模型，其P@1均比SVM高。

下面对比分析训练的模型应用到CBS算法中表现，分别将训练好的排序模型为CBS算法选择冲突。使用 ${\text{NE}}{{\text{T}}_{\text{1}}}$ 表示利用RankNet算法学习冲突选择策略S₁得到的排序模型，其余类似。得到的结果如表4所示。

由表4可知，在学习相同的冲突选择策略的情况下，运行RankNet排序模型的时间多于运行SVM排序模型的时间。这是因为RankNet排序模型实质为网络层的权重参数，冲突的特征值要通过三层网络的计算才能得到得分。而SVM排序模型实质为1个一维权重列表，冲突的特征值只需与其一一对应相乘就能够得到冲突的得分。尽管使用RankNet排序模型会产生额外的时间开销，但由于其选择冲突标签为1的准确率往往较高，从而在求解实例的过程中表现优于SVM排序模型。不论是选择SVM排序模型还是RankNet排序模型，学习改进冲突选择策略S₂的整体表现均优于S₁。故选择RankNet算法学习改进冲突策略S₂来为CBS算法选择冲突。

3.   仿真结果与分析

为验证改进CBS算法的有效性，进行多组仿真实验。首先对比分析在指定地图下训练得到的排序模型，在相同地图不同智能体数的情况下，所提改进算法与已有改进算法的表现；其次对比分析在指定地图下训练得到的排序模型，在其他地图上，所提改进算法与已有改进算法的表现。

3.1   相同地图不同智能体数的实验对比

与2.2节仿真实验部分设置相同，仍使用相同的CBS算法，使用图2所示的随机地图。为防止实例过于简单，无法明显地突出所提改进算法的优势，或者过于复杂，每次求解的时间太长，故设置智能体数分别为18、20、22和24，并在该地图上随机生成相应智能体数的100组实例，分别使用CBS+ ${\text{NE}}{{\text{T}}_{\text{1}}}$ 和CBS+ ${\text{NE}}{{\text{T}}_2}$ 求解。每个实例的运行时间均限制为10 min。表5为两个算法在运行时间、CT大小，成功率方面的数据对比。其中，成功率为算法在指定时间内成功求解的实例总数占总实例数的比例。运行时间和CT大小均为共同求解实例数据的平均值。

由表5可知，与CBS+ ${S _0}$ 相比，CBS+ ${\text{NE}}{{\text{T}}_2}$ 能够使运行时间缩短61.9%，搜索空间缩小80.1%并有效提高算法的成功率；与CBS+ ${\text{NE}}{{\text{T}}_{\text{1}}}$ 相比，CBS+ ${\text{NE}}{{\text{T}}_2}$ 能够使运行时间缩短46.2%，搜索空间缩小51.9%。所提改进算法在智能体数不同的实例下，仍能有效地提高了算法在路径规划方面的求解效率。

3.2   不同地图不同智能体数的实验对比

使用学到的排序模型在不同地图不同智能体数的情况下为CBS算法选择冲突，验证所训练的模型是否依赖于地图。地图选择标准地图的Maze地图，其大小为32×32，如图3所示。选择由图1学习到的排序模型，智能体数分别设置为6、8、10和12在上随机生成50组实例，分别使用CBS+ ${S _0}$ 、CBS+ ${\text{NE}}{{\text{T}}_{\text{1}}}$ 和CBS+ ${\text{NE}}{{\text{T}}_2}$ 求解。每个实例的运行时间均限制为10 min。表6为两个算法在运行时间、CT大小、成功率方面的数据对比。

图  3  迷宫地图

Fig.  3  Maze map

下载: 全尺寸图片

由表6可知，与CBS+ ${S _0}$ 相比，CBS+ ${\text{NE}}{{\text{T}}_2}$ 能够使运行时间缩短39.2%，搜索空间缩小59.6%并能够有效地提高算法的成功率；与CBS+ ${\text{NE}}{{\text{T}}_{\text{1}}}$ 相比，CBS+ ${\text{NE}}{{\text{T}}_2}$ 能够使运行时间缩短15.2%，搜索空间缩小25.4%。由此可知，所学模型在未学习过的地图上，仍能有效提高路径规划的求解效率。

此外，本文所提的方法均可应用到其他地图中，因为排序模型与冲突的特征值和冲突的得分密切相关。而获取特征值和得分的方法均为独立的，因此该方法在不同地图中也具有很好的适应性。

4.   结束语

本文主要聚焦于如何优化CBS算法中冲突选择的问题，提出一种改进CBS算法的多智能体路径规划算法。首先提出一种新的冲突选择策略，缩小了搜索空间。其次使用RankNet算法学习该策略，得到一个既快速又准确的排序模型，该模型能选到“好”的冲突。最后改进算法使用该排序模型为CBS算法选择冲突。仿真实验结果表明，当在同一地图下，所提改进算法在不同智能体数的情况下，总体表现比之前的改进算法好，求解效率和成功率得到有效提升。当地图变化时，相较于之前的改进算法，本文所提改进算法仍有很高的求解效率和成功率。未来工作考虑实际场景的动态性，开展在动态环境下提高多智能体路径规划效率的研究。