IPA-A^(*):带有理想路径面积约束的改进A^(*)算法  

IPA-A^(*):Improved A^(*)Algorithm with Ideal Path Area Constraint

作　　者：曹一波 杨正东 范敬文 赵佳恒 CAO Yibo;YANG Zhengdong;FAN Jingwen;ZHAO Jiaheng(School of Software,South China Normal University,Foshan 538200,China)

机构地区：[1]华南师范大学软件学院,广东佛山538200

出　　处：《软件导刊》2025年第4期75-80,共6页Software Guide

基　　金：宁波市重点技术研发项目(2021E007)。

摘　　要：在已知环境中规划最优可行路径仍是自主移动机器人领域一个具有挑战性的问题。传统的A^(*)算法是在全局路径规划领域使用最广泛且知名度最高的算法之一。然而,传统的A^(*)算法存在一些局限性。例如,由于在大规模地图上进行了过多的节点探索,可能导致计算成本过高。此外,即使考虑运行时优化,其也可能生成过于靠近障碍物的路径,并且不能有效地与局部路径规划算法如动态窗口法(DWA)集成。因此,提出一种改进的A^(*)算法,称为理想路径区域A^(*)算法(IPA-A^(*))。IPA-A^(*)算法通过将理想区域约束纳入传统的启发式搜索函数,解决了过度且不必要的节点探索问题。为了评估其性能,将IPA-A^(*)算法与全局路径规划领域广泛使用的3种算法进行了比较,包括Dijkstra算法、最佳优先搜索(BFS)算法和传统的A^(*)算法。在3种不同复杂程度的地图上进行的仿真实验结果表明,与上述算法相比,IPA-A^(*)算法探索的节点数量、生成路径长度与搜索耗时均显著减少。Planning the optimal feasible path in a known environment remains a challenging problem in the field of autonomous mobile robot‐ics.The traditional A^(*)algorithm is one of the most widely used and well-known algorithms in the domain of global path planning.However,the traditional A^(*)algorithm has some limitations.For instance,it may incur high computational costs due to excessive node exploration on large-scale maps.Moreover,even with runtime optimizations,it may generate paths that are too close to obstacles and cannot be effectively in‐tegrated with local path planning algorithms,such as the Dynamic Window Approach(DWA)algorithm.In this paper,we propose an im‐proved A^(*)algorithm,called the Ideal Path Area A^(*)(IPA-A^(*))algorithm.The IPA-A^(*)algorithm addresses the issue of excessive and unnec‐essary node exploration by incorporating ideal area constraints into the traditional heuristic search function.To evaluate its performance,we compared the IPA-A^(*)algorithm with three algorithms widely used in global path planning:the Dijkstra algorithm,the Best-First Search(BFS)algorithm,and the traditional A^(*)algorithm.Simulation experimental results on maps with three different levels of complexity show that,compared to the aforementioned algorithms,the IPA-A^(*)algorithm significantly reduces the number of explored nodes,the length of the generated path,and the time spent on searching.

关 键 词：改进A^(*)算法 动态窗口法 路径规划 移动机器人 

分 类 号：TP391.4[自动化与计算机技术—计算机应用技术]