基于邻接节点聚合的多层级MQA-A*路径规划算法

杨肖宁，程承旗，陈 波，童晓冲，何 静

（1. 北京大学 工学院，北京 100871；2. 信息工程大学 地理空间信息学院，河南 郑州 450001；3. 河南大学商学院，河南 开封 475001）

0 引 言

栅格地图的路径规划问题是指在栅格地图环境中以较高效率规划出一条从起始点到目标点的最优或次优无碰撞的路径。对该问题的研究，在移动机器人、计算机游戏、人工智能等领域都具有重要意义。近年来许多学者和专家研究了多种应用于栅格地图的路径规划算法，如蚁群算法[1]、遗传算法[2]、神经网络法[3]、人工势场法[4]、A*算法[5]等，其中，A*算法作为成熟的启发式算法[6]，在移动机器人等领域已得到广泛应用和验证[7]。

A*算法[5]是Hart等人在1968年提出的一种启发式路径规划算法。A*算法在Dijkstra算法[8]的基础上引入评价函数f(n)=g(n)+h(n)考察节点n的代价，其中，g(n)表示从起始点到节点n的实际路径长度，h(n)表示在不考虑障碍物的情况下从节点n到目标点的估算路径长度，A*算法基于评价函数选择最优的移动节点，从而逐步构建完整路径。传统的A*算法可以规划从起始点到目标点的最优路径，然而，A*在算法效率上也存在以下问题：其一是内存方面，算法需要对网格节点的邻接信息及由算法引入的其他变量进行存储，其内存需求随网格规模的扩大而成比例增加，因此其用于大规模网格时内存消耗较大；其二是计算时间方面，算法扩展节点数目同样会随网格规模的扩大而成比例增加，特别地，算法在扩展节点中寻优的操作如果基于链表数据结构，扩展节点数目的增加会同时加深算法对链表的搜索深度，进而更严重地影响算法的规划路径效率。……