融合椭圆约束的快速行进树路径规划算法  

Fast marching tree path planning algorithm with elliptic constraints

作　　者：袁雷 贾小林[1,2] 顾娅军 徐正宇[1,2] Yuan Lei;Jia Xiaolin;Gu Yajun;Xu Zhengyu(School of Computer Science&Technology,Southwest University of Science&Technology,Mianyang Sichuan 621010,China;Mobile Internet of Things&Radio Frequency Identification Technology Key Laboratory of Mianyang(MIOT&RFID),Mianyang Sichuan 621010,China)

机构地区：[1]西南科技大学计算机科学与技术学院,四川绵阳621010 [2]绵阳市移动物联射频识别技术重点实验室,四川绵阳621010

出　　处：《计算机应用研究》2024年第12期3595-3599,共5页Application Research of Computers

基　　金：国家自然科学基金面上项目(61471306);四川省自然科学基金面上项目(2022NSFSC0548);绵阳市移动物联射频识别技术重点实验室专项资助项目(MYZD23032302)。

摘　　要：为解决快速行进树算法(fast marching tree,FMT^(*))生成路径拐点多,且由于冗余探索导致路径规划时间长的问题,提出一种融合椭圆约束的快速行进树算法(ellipse constraints FMT^(*),EC-FMT^(*))。首先引入椭圆约束限制算法探索范围,并结合直连策略避免冗余探索,缩短了路径规划时间;对于路径拐点多的问题,通过父节点重选策略修正路径,去除不必要的拐点。仿真实验表明:采样点数量为1000、1500、2000个时,EC-FMT^(*)与FMT^(*)、RRT^(*)、APF-Dynamic FMT^(*)相比,在平均规划时间上分别降低了81.9%~86.76%、86.15%~89.78%、77.12%~85.76%,并且拐点数量也有所降低;同时,EC-FMT^(*)与FMT^(*)、APF-Dynamic FMT^(*)相比,迭代次数分别减少了84.72%~87.03%、80.89%~85.55%。说明EC-FMT^(*)能够有效减少冗余探索,缩短路径规划时间,提高路径质量。To address the issues of excessive inflection points and long planning times in paths generated by the FMT^(*)algorithm due to redundant exploration,this paper proposed an EC-FMT^(*)algorithm.The EC-FMT^(*)algorithm firstly introduced ellipse constraints to limit the exploration range of the algorithm and incorporated a direct connection strategy to minimize unnece-ssary searches,thereby shortening the path planning time.To tackle the problem of numerous inflection points,the algorithm employed a parent node reselection strategy to refine the path and eliminate unnecessary turns.Simulation experiments show that when the number of sampling points is 1000,1500,and 2000,respectively,the EC-FMT^(*)algorithm achieves significant reductions in average planning time compared to FMT^(*),RRT^(*),and APF-Dynamic FMT^(*),ranging from 81.9%to 86.76%,86.15%to 89.78%,and 77.12%to 85.76%.Additionally,the number of inflection points is also reduced.Furthermore,EC-FMT^(*)reduces the number of iterations by 84.72%to 87.03%compared to FMT^(*)and by 80.89%to 85.55%compared to APF-Dynamic FMT^(*).These results demonstrate that the EC-FMT^(*)algorithm effectively mitigates redundant exploration,shortens path planning time,and enhances path quality.

关 键 词：FMT*算法 椭圆约束 直连策略 父节点重选 

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