复杂环境下多Agent协同路径规划研究

• 作 者: 殷嘉蔓
• 出 处: 扬州大学
• 发表日期: 2021年04期
• 关键词: 路径规划 A~*算法 K-Means聚类算法 多Agent

多Agent路径规划是一类寻找多个Agent从起始位置到目标位置且无冲突的最优路径集合的问题。本文旨在使用K-Means聚类算法和改进的A*算法解决多Agent协同路径规划问题。首先,分析路径规划算法中几类主流算法的特点,根据问题研究背景选定A*算法实现多Agent协同路径规划。本文主要研究问题是多个Agent从同一起始节点出发,遍历地图中所有的目标节点,并且回到起始节点,任务要求是时间最短,最后完成最优路径求解。其次,分析和改进传统A*算法的不足,针对A*算法搜索时间长、搜索节点数多导致的搜索效率不高的问题,提出了改进A*算法的两种优化方法:(1)传统A*算法节点之间距离的计算方式为曼哈顿距离、欧几里得距离、切比雪夫距离,采用这几种计算方式会造成搜索区域过大,从而导致算法效率变低。所以在此基础上本文提出了一种改进的距离计算公式——复杂对角线距离,降低了搜索节点数和搜索面积。(2)传统A*算法的标准启发函数,没有考虑Agent在实际运行过程中,行进方向的改变会造成Agent不同角度的拐弯,在这个过程中会产生一定的时间延迟,因此对启发函数加权以及加入常数项处理,减少了阶梯型路线的规划,减少了搜索节点数量和转弯角度,提高算法的搜索效率。最后,给出多Agent协同路径规划的具体策略。在预设地图中,用K-Means分组聚类算法将地图中的目标节点划分为四组,然后使用改进的A*算法进行路径规划,从而完成对最优路径的求解。本文在MATLAB系统中进行仿真实验:(a)栅格化地图,同时对复杂不规则障碍物进行膨胀化处理,之后对改进的A*算法与传统A*算法做比较分析,分别设置了三组不同起始节点与目标节点的地图,实验数据表明,改进的A*算法比传统A*算法的整体路径搜索效率提高了 12～15%。(b)分析实际案例,以校园宿舍区快递无人配送为背景,实现以K-Means聚类和A*算法为基础的多Agent协同路径规划。本文研究的复杂环境下多Agent协同路径规划问题,主要解决了传统A*算法搜索路径效率低、搜索面积大等缺陷;其次,运用障碍物膨胀原理处理了复杂的地图环境;然后,给出了使用K-Means聚类算法解决多Agent协同的策略,最后形成最优路径规划路线。