基于改进A*算法下的多Agent系统路径规划

基于改进 A*算法下的多 Agent系统路径规划

朱志鹏

（扬州大学，江苏扬州）

摘要：针对移动机器人A *算法的路径规划算法搜索路径节点效率不高的问题，提出了一种改进的方法来改变距离函数的计算方法。 MATLAB仿真系统的实验数据表明，经过改进的A *算法大大减少了无用访问节点的数量，加快了耗时的搜索过程，并将搜索时间减少了约12-15％。

一、引言

伴随着科学技术的快速发展，路径规划问题的研究成果已经广泛应用于机器人、地理信息系统、军事等各种领域。传统A*算法节点之间距离的计算方式为曼哈顿距离、欧几里得距离、切比雪夫距离，采用这几种计算方式会造成搜索区域过大，从而导致算法效率变低。所以在此基础上本文提出了一种改进的距离计算公式——复杂对角线距离，降低了搜索节点数和搜索面积。

二、传统A*算法特点

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

对A*搜索的启发式函数的研究在多Agent路径规划中也是非常重要的。最简单的全局启发式函数是所有Agent各自的启发式函数的求和，这在格点图上表现为曼哈顿距离求和，而在欧几里得图上表现为欧几里得距离求和。在Agent数量很多的路径规划研究中，采用了更为复杂的全局启发式函数。然而，采用过于复杂的启发式函数不一定是有积极意义的，因为提高启发式函数的计算复杂度可能会降低算法的执行效率。可以发现传统A*算法在寻找最短路径时所存在的两种缺陷分别是：

a．传统节点之间距离计算方式为曼哈顿距离、欧几里得距离、切比雪夫距离，采用这几种方式会造成搜索区域过大，使算法效率变低；

b．传统A*算法的启发函数存在一定的缺陷，没有考虑到Agent实际运行过程中行进方向的改变会造成Agent不同角度的转弯，在这个过程中会产生一定的时间延迟。

三、改进A*算法

A *算法中常用的距离算法包括欧几里得距离，曼哈顿距离和切比雪夫距离。欧几里德距离算法计算当前节点n和目标节点t的两点之间的真实距离。它是当前起始节点n和目标节点t之间的横坐标和纵坐标的算术平方和。该算法考虑了从当前节点n到目标节点t的移动距离和移动步数，并执行加权计算。曼哈顿算法计算当前节点n和目标节点t之间的移动距离，该距离是两个轴之间的差的绝对值之和。切比雪夫距离算法计算从当前节点n到目标节点t的步数，该步数是两点之间水平和垂直坐标之间的差的绝对值的最大值

通过改进上述三种距离算法，提出了一种新的距离计算方法，称为复杂对角线距离算法。 该算法考虑了从当前节点n到目标节点t的移动距离和移动步数，并执行加权计算。 其启发式功能表示为：

其中，H1表示当前节点与目标节点在x轴和y轴方向上的最小距离； H2表示当前节点与目标节点之间在x轴和y轴方向上的水平距离和垂直距离的总和。

在仿真过程中，假设起点和目标点相同，启发式函数距离算法基于曼哈顿距离，欧几里得距离，切比雪夫距离和改进的复对角线距离来规划道路。通过matlab仿真使用不同的计算公式计算出的搜索区域中改进的距离公式更加优越。

四、结语

通过对多Agent协同路径的规划研究，在基于改进A*算法下多Agent协同路径规划实现了效率的提升，但仍需要做进一步的工作，例如，在实际生活中，Agent数量不是固定的，需要在更多数量的Agent下进行协同路径规划，但是本文所研究的内容首先基于少量Agent。另外，本文的研究问题只考虑了根据预设地图设定目标点执行任务的情况，实际生产生活中，地图信息并不一定完全，因此还需要讨论在动态的实时变化的环境中建立合理的模型，多Agent如何更好的规划出最优路径。

【参考文献】

1. Seng-Beng Ho, Fiona Liausvia, "A ground level causal learning algorithm," Proc. IEEE, 1-6(2016).

2. Lu, H. Li, Y. Mu, S. et al., "Motor Anomaly Detection for Unmanned Aerial Vehicles Using Reinforcement Learning," Proc. IEEE Internet of Things Journal, 2315-2322 (2018).

3. Yuqing Lin, Fuji Zhang, "A linear algorithm for a perfect matching in polyomino graphs," Theoretical Computer Science, 675(2017).

4. Huimin Lu, Dong Wang, Yujie, Li. et al., "CONet: A Cognitive Ocean Network," Proc. IEEE Wireless Communications, 90-96 (2019).

5. Yoshiyuki Kozuka, Toshiyuki Hayashi, Takashi Syamoto, Nobuhiro Ito, Kazunori Iwata, Yoshinobu Kawabe, "A Algorithm with Expected Value: Path Planning That Avoids Stochastic Traffic Obstacles," Proc. IEEE International Conference on Agents (ICA), 104-105(2016).

【基金项目】

扬州大学大学生创新创业训练计划项目（学术科技创新基金项目）

【作者简介】

朱志鹏  2000  男     江苏徐州   扬州大学   计算机科学与技术