上海交通大学学报 ›› 2024, Vol. 58 ›› Issue (4): 511-524.doi: 10.16183/j.cnki.jsjtu.2022.442

• 电子信息与电气工程 • 上一篇    下一篇

复杂环境下基于改进Informed RRT*的无人机路径规划算法

刘文倩1, 单梁1(), 张伟龙1, 刘成林2, 马强1   

  1. 1.南京理工大学 自动化学院,南京 210094
    2.江南大学 轻工过程先进控制教育部重点实验室,江苏 无锡 214122
  • 收稿日期:2022-11-04 修回日期:2022-12-12 接受日期:2022-12-21 出版日期:2024-04-28 发布日期:2024-04-30
  • 通讯作者: 单 梁,副教授;E-mail:shanliang@njust.edu.cn. E-mail:shanliang@njust.edu.cn
  • 作者简介:刘文倩(2000-),硕士生,从事无人机路径规划与控制算法研究.
  • 基金资助:
    国家自然科学基金资助项目(61973139);江苏省自然科学基金面上项目(BK20191286);中央高校基本科研业务费专项资金资助项目(30920021139)

Unmanned Aerial Vehicle Path Planning Algorithm Based on Improved Informed RRT* in Complex Environment

LIU Wenqian1, SHAN Liang1(), ZHANG Weilong1, LIU Chenglin2, MA Qiang1   

  1. 1. School of Automation, Nanjing University of Science and Technology, Nanjing 210094, China
    2. Key Laboratory of Advanced Process Control of Light Industry of the Ministry of Education, Jiangnan University, Wuxi 214122, Jiangsu, China
  • Received:2022-11-04 Revised:2022-12-12 Accepted:2022-12-21 Online:2024-04-28 Published:2024-04-30

摘要:

针对无人机在复杂环境中进行路径规划时,快速搜索随机树(RRT)算法易出现规划时间长、路径冗余、狭窄空间中易陷入局部约束导致规划失败的问题,提出一种改进的Informed RRT*算法.首先,引入人工势场法使采样点按照势场下降的方式向目标点移动,以提高RRT树扩展的目的性和方向性.然后,考虑随机树在扩展过程中全局环境的复杂度,引入自适应步长调整策略以增加随机树在无障碍环境下的扩展速度,并在随机树扩展的过程中加入相关约束条件以确保生成路径的可行性.在找到第一条可达路径后,采用变化的椭圆或椭球采样域限制采样点选取和自适应步长的扩展范围,加快算法收敛到渐进最优的速度.最后,在复杂二维和三维环境下进行传统算法和改进算法的对比实验,仿真分析表明:改进算法可以在很少的迭代次数下找到更优的初始路径,更快地锁定椭圆或椭球采样域,从而给路径优化留出更多时间,算法规划效果更好.

关键词: 路径规划, Informed RRT*, 人工势场法, 自适应步长, 椭圆采样域

Abstract:

To address the problems of long planning time, redundant planning path, and even planning failure caused by local constraints in narrow spaces in the rapid exploring random trees (RRT) algorithm when unmanned aerial vehicle is planning a path in a complex environment, an improved Informed RRT* algorithm is proposed. First, the artificial potential field (APF) method is used to make the sampling points move to the target point in the way of potential field descending, which improves the purpose and directionality of RRT tree expansion. Considering the complexity of the global environment during tree expansion, an adaptive step size is introduced to accelerate the expansion speed of the RRT tree in an unobstructed environment. Then, relevant constraints are added in the process of random tree expansion to ensure the feasibility of the generated paths. After the first reachable path is found, variable elliptic or ellipsoidal sampling domain is used to limit the selection of sampling points and the expansion range of adaptive step size, so as to accelerate the convergence of the algorithm to the asymptotic optimization. Finally, the original algorithm and the improved algorithm are compared in two-dimensional and three-dimensional complex environment. The simulation results show that the improved algorithm can find a better reachable path with a small number of iterations, lock the elliptic or ellipsoidal sampling domain faster and leave more time for path optimization. The improved algorithm performs better in path planning.

Key words: path planning, Informed RRT* (IRRT*), artificial potential field (APF) method, adaptive step size, elliptic sampling domain

中图分类号: