基于规范排序树的自适应A*算法:面向未知栅格地形导航的增量启发式搜索新方法

《Chinese Journal of Electronics》:Canonical Ordering Tree Adaptive A*

【字体: 大 中 小 】 时间:2026年01月04日 来源:Chinese Journal of Electronics 3

编辑推荐:

  为解决未知或部分已知栅格地形中智能体路径规划效率低下的问题,研究人员开展了“规范排序树自适应A(COTAA)”算法的研究。该研究通过融合树自适应A(TAA)与跳点搜索(JPS)家族算法的优势,提出惰性树自适应A(LTAA)和COTAA两种新算法。实验证明,COTAA及其早终止变体在迷宫、随机障碍等多种地图类型中均表现出优越的每轮搜索运行时性能,成为栅格地图未知地形目标导向导航领域最先进的增量启发式搜索算法之一。

  
在机器人学和视频游戏开发等领域,智能体(如机器人、游戏角色)常常需要在初始未知或部分已知的地形中导航,从起始点移动到已知目标点。这些智能体通常具备感知周围障碍物的能力。在自由空间假设下,智能体会假设整个地形都是可通行的,除了已探测到的阻塞区域。然而,随着智能体的移动和环境感知的更新,其知识会发生变化,导致当前路径计划失效,因此需要重新规划路径。一种常见的方法是智能体反复地搜索并找到从其当前位置到目标位置的成本最小路径,并沿着该路径移动直至到达目标。这些搜索必须快速进行,否则智能体的移动会不流畅。
传统的A搜索算法在已知地形中表现优异,但在未知环境中重复使用A搜索(即重复A)非常耗时。增量启发式搜索算法应运而生,它们利用先前和当前的搜索经验来更快地解决未来类似的搜索问题,其性能远超重复A这类孤立解决单个搜索问题的传统算法。增量启发式搜索算法主要分为三类:第一类算法在整个导航问题期间维护一个搜索树,每次搜索都重用并修改这棵树,避免了每次都从头开始构建,其代表是D* Lite算法;第二类算法通过更新状态点的启发式值(Heuristic)使其更具信息性,从而让未来的搜索更加聚焦,自适应A是其中的代表;第三类算法则结合前两类的优点,其代表是树自适应A(TAA*),它既更新状态的启发式值,又维护一个可重用的搜索树。
栅格地图因其易于实现而被广泛用于路径规划任务中的环境表示。然而,在栅格地图上求解单对最短路径问题具有挑战性,其中一个难点是路径对称性。跳点搜索(JPS)家族算法能够消除栅格地图上由路径对称性引起的冗余。此外,还有单行压缩(SRC)、收缩层次(CH)、子目标图、JPS+、边界查找JPS(BLJPS)、压缩路径数据库(CPDs)和JPS+BB+等多种加速技术,但它们都需要离线预处理,因此不适用于未知地形中的问题。
在此背景下,上海科技大学和中国科学院上海微系统与信息技术研究所仿生视觉系统实验室的研究团队在《Chinese Journal of Electronics》上发表了题为“Canonical Ordering Tree Adaptive A”的论文。该研究旨在结合TAA和JPS家族算法的优势,针对栅格表示的未知或部分已知地形中的目标导向导航问题,提出一种新的增量启发式搜索算法。
为了回答如何更高效地在未知栅格地形中进行路径规划的问题,研究人员主要采用了算法设计与比较分析的研究方法。具体而言,他们首先提出了TAA的一种惰性版本,称为惰性树自适应A(LTAA)。与TAA急切地更新所有已扩展状态的启发式值不同,LTAA仅在必要时才更新状态的启发式值,从而减少了不必要的开销,实现了更快的执行速度。接着,研究人员创新性地提出了规范排序树自适应A(COTAA)及其早终止变体。COTAA的核心思想是将JPS家族算法中的规范排序(或称剪枝规则)与TAA相结合。规范排序规则偏好先进行对角线移动再进行基数移动的路径,从而有效消除路径对称性带来的冗余。此外,研究还采用了有界跳点搜索的思想,通过参数pbound来限制跳跃的距离,以平衡每次扩展的耗时和总扩展次数。实验部分,研究团队从Moving AI Lab的2D路径规划基准中选取了迷宫图、随机障碍图、房间图、街道图和游戏图五种类型的栅格地图(尺寸均为512x512)进行测试,并将提出的算法与当前最先进的增量启发式搜索算法(如DLite和TAA*)以及重复有界JPS(RBJPS)进行了全面的性能比较,评估指标包括每轮搜索的运行时、每次扩展的运行时、总运行时、扩展的单元格数量等。
研究结果部分通过理论证明和实验对比展示了算法的性能。
理论性质:论文证明了COTAA*具有最优性。即智能体每次移动都位于基于其当前知识的最优路径上,这源于算法保持了一致性保持特性。
算法对比与案例展示:通过在一个简单例子和一个复杂例子上的运行结果图示,研究直观地比较了TAA、LTAA和COTAA(pbound=2)的行为差异。对比表明,LTAA相比TAA更新启发式值的次数更少(惰性更新的效果)。而COTAA相比LTAA,由于引入了规范排序,扩展的状态数量显著减少,搜索更加高效,尽管有界跳跃可能会引入一些冗余的触及状态,但总体上消除了TAA中存在的大量冗余搜索。
参数影响分析:实验结果揭示了参数pbound的权衡效应。pbound过小会导致每轮搜索的扩展次数可能增多,产生负面影响;pbound过大则可能使每次扩展的运行时变长,降低算法效率。对于COTAA*的早终止变体,其通过增加一个与OPEN集中最高优先级状态的f值比较的早终止准则,有助于算法聚焦于低f值区域,减少不必要的跳跃,从而在一定程度上缓解了大pbound参数的负面影响,这种现象在迷宫类地图中尤为明显。
综合性能评估:与D* Lite、重复有界JPS(RBJPS)、TAA和LTAA的对比表明,RBJPS由于不是增量式算法,其性能在所有地图类型上均逊于其他算法。LTAA始终优于TAA,验证了惰性启发式更新策略的有效性。D* Lite的第一轮搜索运行时最长,但其在后续轮次中表现优异,在迷宫这种困难地图中,其性能优势明显,能够分摊首轮搜索的成本。在简单地图(如随机障碍、街道)上,TAA和LTAA表现最佳。在中等难度地图(如游戏地图)上,各算法结果接近,COTAA-早终止变体性能最优。在困难地图(如房间地图)上,DLite优于COTAA,但COTAA仍具竞争力,而COTAA-早终止变体表现最佳,TAA和LTAA则因排除首轮后的扩展次数过多而效率较低。在极度困难的迷宫地图中,DLite性能最优,COTAA和COTAA-早终止变体的每轮搜索运行时约为D* Lite的4.9倍,但仍远优于TAA和LTAA(后者约为D* Lite的55-62倍)。
归纳研究结论和讨论部分,本研究的主要贡献在于提出了一种优化版本的TAA(即LTAA)和一种新颖的增量启发式搜索算法COTAA。LTAA通过惰性更新策略提高了效率。COTAA则创新性地将TAA与JPS家族算法的规范排序思想相结合,在未知栅格地形导航问题上实现了高效的路径规划。实验结果表明,COTAA及其早终止变体在多种地图环境下,特别是在房间图和游戏图等中等难度地图中,其每轮搜索的运行时性能达到了 state-of-the-art 的水平。在街道图和随机障碍图中,其性能优于DLite。即使在极具挑战性的迷宫地图中,COTAA系列算法也比TAA和LTAA*快一个数量级。因此,这项研究为解决未知栅格地形中的路径规划问题提供了强有力的新工具,显著提升了智能体在动态未知环境中导航的实时性和效率。该算法的优势在于既利用了增量搜索的历史信息,又通过规范排序有效压缩了搜索空间,为机器人导航、游戏AI等领域的实际应用提供了重要的算法支持。
相关新闻
生物通微信公众号
微信
新浪微博

热点排行

    今日动态 | 人才市场 | 新技术专栏 | 中国科学人 | 云展台 | BioHot | 云讲堂直播 | 会展中心 | 特价专栏 | 技术快讯 | 免费试用

    版权所有 生物通

    Copyright© eBiotrade.com, All Rights Reserved

    联系信箱:

    粤ICP备09063491号