论文拾萃|多目标A*算法解决多模式多目标路径规划问题(MMOPP)

1引言

多目标决策在现实生活中有着普遍的应用。解决一个多目标最优化问题需要同时考虑多个往往会相互冲突的目标。在大多数情况下，想要同时达到每个目标的最优情况是不现实的。因此，解决多目标最优化问题的目标是找到尽可能多的、权衡各个目标的解，以此方便决策者在发现的解中做出合理的抉择。

假设我们研究的多目标优化问题可以表示如下：

最小化   其中

表示个需要同时最小化的实值函数，决策空间在函数上的映射为目标空间，记为。由此，每一个可行解就对应一个M维目标向量.

若对向量和向量，对所有的 ,有，且对若干 ,有，则称绝对优于。相应地，若对于可行解，绝对优于，则称绝对优于。

由此，若在决策空间上没有任何可行解绝对优于可行解，则称是帕累托最优(Pareto optimal)的。所有决策空间内的帕累托最优解的集合为帕累托集，记为，其在目标空间上相应的点构成帕累托前沿面(Pareto front)，记为。

过去的几十年中，遗传算法(evolutionary algorithm)已经成为解决多目标优化问题的主流算法。然而，绝大多数现存的遗传算法只以刻画帕累托前沿面为目标，忽略了解在决策空间中的分布。正如前文所提到的，多个可行的帕累托解有助于形成可靠的决策。如果这些解在决策空间中分布很广，它们就能为决策者提供更加直观的信息。因此，我们需要同时刻画帕累托前沿面和帕累托集，以此帮助决策者发现隐藏的性质并做出决策。包含这一特殊目标的优化问题就是所谓的多模式多目标优化问题。

多目标路径规划问题是一个典型的优化问题。在运动规划、城市交通、车辆路径规划等领域都有该问题的体现。一般来说，单一目标函数不足以刻画实用的路径规划问题。而可能需要优化的多个衡量因素，例如路径长度、花费时间、总费用、耗油量等，往往会相互冲突。论文研究的主题即为 IEEE CEC 2021特别活动的主题之一——多模式多目标路径规划问题[Multimodal multi-objective path planning(MMOPP)]。

2问题描述

简单来说，多模式多目标路径规划问题即为：找出在栅格图中从起点出发，经过给定的若干个关键点，最终到终点的所有帕累托最优路径。

下面给出问题的数学模型：

给定一个栅格图，其中，坐标左起第x列，自上往下第y行的方格区域。二进制矩阵用于表示原始栅格图：表示区域可以通行，则相反。一条路径即为一串相邻可通行区域的序列。图中每一个区域都带有一个M维非负花费向量，表示为。相应地，路径花费也是M维的，为序列中区域花费的总和。花费向量的每个维度都代表某个需要降到最小值的目标函数，例如路径长度、交通拥堵程度、路口数量等等人们在选择路径时会注意的偏好。

一个旅行者要从起始区域出发，以任意顺序途径个关键区域，到达目标区域。一般地，关键区域一定是可通行区域，且异于起始区域和目标区域。下文中，我们将起始区域、关键区域、目标区域统称强制性区域。

以下图为例：

其中，起始区域标为蓝色，3个关键区域标为黄色，目标区域标为绿色，其他可通行区域标为黑色。 下图为可行解的一例：

多模式多目标路径规划优化问题的目标即为找出所有帕累托最优路径。正如前文所说的，图中的其他任意可行路径都不会绝对优于这些路径。

3整体算法流程

1. 检查可行性
2. 图简化建模
3. 多目标A*算法
4. 路径重构

3.1 可行性检查与图简化

在开始解决问题前，我们先要检查是否存在可行解。判定方法很简单：如果所有强制性区域相互间均相连，则必定存在可行解。这一过程可以通过分析相连的区域，在多项式时间内完成。

同时，为了降低问题的规模，我们要将不必要的区域移除。不必要的区域分为两类：

• 从起点出发无法达到的区域
• 由关节点分隔且不包含强制性区域的区域

以下图为例：

灰色区域为移除的区域，其中，红色框内为第一类区域，蓝色框内为第二类区域。

以下为伪代码：

这个过程以深度优先生成树为主体，根节点为起始区域。 其中：

• depth[x][y]区域(x,y)在树中的深度。depth[x][y]=0表示区域(x,y)未被搜索过；
• low[x][y]表示最远的与区域(x,y)的子树相邻的祖先的深度；
• flag[x][y]表示区域(x,y)的子树中是否存在强制性区域；
• children[x][y]表示区域(x,y)的子节点的集合；
• retained[x][y]表示区域(x,y)是否在缩减后的图中保留，初始值为不保留；

相应地，若所有的强制性区域都在树中，则表明问题存在可行解。

而在图简化过程中，我们同样采用深度优先搜索的方式，顺着刚才的生成树搜索，对符合条件的区域进行保留处理。第一类省去的区域为不在树中的区域，不会被搜索到，从而不会被保留；对于第二类区域，若对搜索到的一个区域(x,y)及其子节点，满足并且，则整个以为根的子树都可以省略，即不再继续顺着该结点往下搜索保留。

由此，我们得以将原先的栅格图简化为无向图，缩小了问题的规模。其中，是顶点的集合，是边的集合。每一个顶点对应一个强制性区域或度为3或4的区域，而每一条边则对应两个节点间度为2的连续相邻区域的一串序列。对于每一个顶点，我们用表示该节点，用代表与该节点相连的边的集合。特别地，用,和,...,分别表示起始点、目标点和关键点。对每条与节点相连的边，用表示该条边的另一个端点，用表示该条边除去两端点后的花费之和，用表示从节点n到节点的中间部分的序列。

缩减后的无向图如图：

3.2 多目标A*算法

多目标A*算法[Multi-Objective A* Algorithm(MOA*)]是整个算法的核心。所谓“A*”算法，可以理解为带提示的搜索算法。也就是说，通过综合已知花费和估算剩余花费决定下一步搜索方向，以此高效地接近目标，减少“南辕北辙”。

下面引入一些有关概念：

“状态”：用以表示路径中已经经过的关键区域。用K位二进制数组(等价于整数0至)即可表示。其中，第k位若为1表示已经经过第k个关键区域，反之亦然。用表示所有种可能的状态。特别地， , .同时，用代表状态s的第k位，用表示状态s中未经过区域的集合。

对于所有可能的节点-状态对，用表示位于节点n且状态为s时的试探性花费向量的集合。该集合存储在整个搜索过程中，所有从起始节点-状态对，到节点-状态对的确定路径的不被占绝对优势的花费向量。

当算法终止时，目标节点-状态对的试探性集合即为我们所求的帕累托前沿面，即.

为了满足“多模式”优化的需求，我们需要记录所有从起始节点-状态对到任意中间的节点-状态对的帕累托最优路径。因此，我们用表示通向节点-状态-花费三联体的“前身”的列表，其中.其中的每个前身以的形式表示，其中表示原先的节点-状态-花费三联体，为转变时经过的边。

根据以上定义，每个节点-状态-花费三联体代表一组同样以起始状态从起始节点出发，以状态到达节点且累计花费为的一组路径。

而在主循环的每次迭代时，算法需要决定哪个节点-状态-花费三联体是接下来最值得拓展的。特别地，算法会选取带有不会被绝对优于的估计花费。其中为估计从当前节点-状态对到目标节点-状态对的理想花费（即花费的下界）的启发式函数。我们会在后面详细介绍该函数。

以下为MOA*算法的伪代码：

其中，为包含所有需要拓展的节点-状态-花费三联体的优先队列。初始时，我们将起始花费插入起始试探性集合，将三联体插入优先队列。在算法的每一次迭代中，我们选取拥有按照字典顺序比较（即以各个因素依次比较）最小的估计花费的节点-状态-花费三联体。这样，我们就可以保证选取的三联体总是拥有一个不被占绝对优势的花费。

对选取的三联体，有如下情况：

• 若其已经达到目标节点-状态对，就意味着为目标空间内的一个帕累托最优点，该次迭代就此终止。此时，我们并不立即筛除所有试探性集合中被新确定的帕累托最优点绝对优于的所有花费向量，而是采取一种延迟筛除策略，在它们从优先队列被取出时才筛除它们；
• 若任意一个目标试探集内的存在的花费向量绝对优于其估计花费，就意味着拓展该三联体将不可能发现任何帕累托最优解，该次迭代也就此终止。根据刚刚提到的延迟筛除策略，我们将剔除出试探集，同时删除前身列表；
• 若以上两种情况均不满足，我们将对该三联体进行拓展。对于节点相连的每条边，接下来的节点-状态-花费三联体也将随之确定。有以下三种情况：
  • 若任意一个试探集内的存在的花费向量绝对优于其花费,就意味着不是节点-状态对的最优花费（之一）；
  • 若已经在中存在，则将作为三联体的一个新的前身；
  • 若以上两种情况均不满足，首先，从中除去被占绝对优势的花费向量以及，同时删去可能在中存在的。接着，计算估计花费。若任意一个目标试探集内的存在的花费向量绝对优于其估计花费，同样意味着拓展该三联体将不可能发现任何帕累托最优解，该次迭代也就此终止。否则，相应地更新（即将对应格式的数据分别放入）、和。

当变为空队列时，MOA*终止。正如上文所说的，目标试探集就是问题所求的帕累托前沿面。

下面介绍启发式函数：

在刚才的算法过程中，我们可以发现估计花费在搜索的过程中起到了重要的引导作用，一方面决定了拓展顺序，另一方面通过比较避免了不必要的计算过程，节约了时间。

在构造启发式函数前，我们首先计算一个特殊节点间的距离矩阵。对于每个维度和每个节点，我们通过在中解决一个单目标最短路径问题来计算仅考虑第个目标函数时，节点与节点之间的最小花费，用表示。需要注意，并不包括两端点节点和的花费。

以下为启发式函数的伪代码：

函数的参数为需要求得理想花费的节点-状态对。显然，若就是目标节点-状态对，函数返回值应为0。除了这种特殊情况，计算每个维度的理想花费相当于找到从节点出发，经过所有中的关键节点，到达的汉密尔顿最短路。然而，这个过程具有指数时间复杂度，当较大时找出其最短总长度是不切实际的。

权衡估计强度和计算效率后，我们采用一个混合策略。理想花费初始值为所有中的关键节点和目标节点自身的花费之和。接着，理想花费通过加上从节点出发，经过所有未经过的关键节点，到达的总距离的最小值。

• 若，总距离最小值即为得到；
• 若，假设中的节点为，总距离最小值即为；
• 若，假设中的节点为和，通过比较仅可能的两条路径和，在M个维度上分别选取较小值为理想花费。
• 若，对于每个维度，我们通过解决最小生成树[minimum spanning tree(MST)]问题来计算连接所有中的关键节点的总距离的最小值。接着，理想花费的第i维加上节点到MST的距离最小值、目标节点到MST的距离最小值和MST内的总距离。

关于最小生成树问题，可参考该推文：基础算法 | 关于图论中最小生成树(Minimum Spanning Tree)那些不可告人的秘密

3.3 路径重构

基于前文中算出的帕累托前沿面以及所有前身列表，我们得以重构路径，从而得到帕累托集。

以下为伪代码：

可以看到，构造路径函数为递归结构，通过一步步倒推最终到达起始节点-状态对。其中，符号表示单个节点或序列的连接，集合用以避免在构造的路径中重复同一个节点-状态对，从而避免进入0花费循环。

4计算效果

为了验证图简化以及启发式函数对计算的优化效果，我们将该算法与两个退化的版本“naive approach”和“blind approach”相比较。两个版本的算法均不采用启发式函数，因此它们都是“未经提示的”搜索。同时，“naive approach”不采用完整的图简化算法，仅将初始的栅格图转化为无向图，而“blind approach”采用与我们提出的算法同样的图简化技术。

以下为实验结果：

可以看到，完整图简化后的“naive approach”的迭代次数(MOA* Iterations)约是“naive approach”的十分之一，而采用了启发式函数的算法效率又是“naive approach”的两倍。这充分说明了两个技术的高效性。

以上即为的全部内容，你看明白了吗？

源代码链接（或点击阅读原文）

⬇️

https://github.com/jinboszu/mmopp

参考文献：

原论文：

[1]Bo Jin (2021). Multi-objective A* algorithm for the multimodal multi-objective path planning optimization. In 2021 IEEE Congress on Evolutionary Computation (CEC), pp. 1704–1711.

-The End-

文案&排版：吕其乐（华中科技大学管理学院本科一年级）

指导老师：秦虎老师 （华中科技大学管理学院）

如对文中内容有疑问，欢迎交流。PS：部分资料来自网络。 如有需求，可以联系： 秦虎老师（华中科技大学管理学院，微信号43340630） 吕其乐（华中科技大学管理学院本科一年级：1286550580@qq.com）

欢迎大家加入数据魔术师粉丝群，我们的活动将会通过粉丝群优先发布， 学习资料将通过粉丝群分享。

欲入群，请转发此文，然后扫描下方二维码联系数据魔术师小助手