1、2023 年 无线电工程 第 53 卷 第 1 期11doi:103969/jissn10033106202301002引用格式:罗银辉，李荣枝，潘正宵，等多约束的无人机动态路径规划算法研究J 无线电工程，2023，53(1):1117LUOYinhui，LI ongzhi，PAN Zhengxiao，et alesearch on Dynamic Path Planning Algorithm of UAV with Multiple Constraints J adioEngineering，2023，53(1):1117多约束的无人机动态路径规划算法研究罗银辉，李荣枝，潘正宵，王星怡(中
2、国民用航空飞行学院 计算机学院，四川 广汉 618370)摘要:无人机的自主飞行是无人机相关研究的重点方向，如何在复杂环境中快速分析环境，并规划一条安全可行的路径，是该方向的研究目标。针对传统路径搜索算法存在的路径不平滑问题，采用三阶 B 样条曲线进行预规划航迹。在欧式有符号距离函数(Euclidean Signed Distance Functions，ESDF)地图提供的梯度信息的基础上，分别在平滑、碰撞和可行性上设计约束方程，实现轨迹动态重规划。针对路径动态更新中，时间间隔变化产生的控制点不再符合约束的问题，采用各向异性曲线拟合方法，实现时间再分配，保障在动态更新路径的过程中，新产生的路
3、径与原路径相似且具有同样的可行性。实验证明，该算法实现了无人机的自主路径规划与优化，能够进行动态避障，面对复杂环境具有鲁棒性。关键词:主飞行;路径规划;ESDF 地图;B 样条曲线;时间再分配中图分类号:V279文献标志码:A开放科学(资源服务)标识码(OSID):文 章 编 号:10033106(2023)01001107esearch on Dynamic Path Planning Algorithm ofUAV with Multiple ConstraintsLUO Yinhui，LI ongzhi，PAN Zhengxiao，WANG Xingyi(School of Comput
4、er Science，Civil Aviation Flight University of Chian，Guanghan 618370，China)Abstract:Autonomous flight of Unmanned Aerial Vehicle(UAV)is a key direction of UAV related research How to analyze theenvironment quickly in complex environment and plan a safe and feasible path is the research goal of this
5、direction To address theproblem of unsmooth path in traditional path search algorithm，the third-order B-spline curve is used to pre-plan the path On the basisof gradient information provided by ESDF maps，constraint equations are designed in terms of smoothing，collision and feasibilityrespectively to
6、 realize dynamic trajectory re-planning To solve the problem that the control points generated by the change of timeinterval no longer meet the constraints in the dynamic updating of the path，the anisotropic curve fitting method is adopted to realize thetime reallocation and ensure that the newly ge
7、nerated path is similar to the original one and has the same feasibility during the dynamicupdating of the path Experimental results show that the algorithm can realize the autonomous path planning and optimization as well asdynamic obstacle avoidance of UAV，and is robust to complex environmentKeywo
8、rds:autonomous flight;path planning;ESDF map;B-spline curve;time reallocation收稿日期:20220920基金项目:四川省重点研发项目(22ZDYF3574);中国民用航空飞行学院重点项目(ZJ201503)Foundation Item:Key D Project of Sichuan Province(22ZDYF3574);Key Project of China Civil Aviation Flight University(ZJ201503)0引言多旋翼无人机具有体积小、机动性高和速度快的特点，在航拍、搜救和
9、巡检工作中具有广泛应用。得益于智能移动设备的发展，斯坦福大学通过在无人机上搭载微机电系统(Micro-Electro-MechanicalSystem，MEMS)传感器加嵌入式机载电脑的方式1，首次实现了无人机的自主飞行，此后，无人机的自主飞行研究迅速发展。无人机在自主飞行过程中，最重要的功能是路径规划与避障，即实现导航。与机器人相似，导航的目的在于找到从起点到终点具有避障能力的最优或次优路径2。现实中的环境是复杂多变的，无人机在飞行的过程中除了要面对静态的障碍物如树木、灯柱等，还需要面对动态的障碍物如飞鸟和其他无人机等，如专题:面向 B5G/6G 的无人机通信122023 adio Engi
10、neering Vol.53 No.1何使无人机在动态环境中实现灵活的自主避障，是研究的重要方向。本文对基于轨迹优化的动态重规划方法进行研究，采用利于重规划的高阶 B 样条曲线，结合提出的 3 项飞行约束方程，动态重规划路径;采用基于时间的再分配策略，实现无人机动态避障，解决动态重规划路径算法的实时性问题。1算法流程无人机要实现自主飞行，需要通过感知系统估计出自身的状态信息，以及周围的环境地图3。传统的做法是将障碍物的点云图收集并转换为在三维地图中的占用栅格地图，再通过路径搜索算法计算无人机的可通行路径4。但这类地图在路径规划算法的应用过程中效率较低，为了更高效地获取环境信息，采用包含了梯度信
11、息的欧式有符号距离函数(Euclidean Signed Distance Functions，ESDF)地图。基于梯度的运动规划是当前主流的无人机局部路径规划方法，该方法将问题表述为无约束线性规划。atliff 等5 率先将 ESDF 地图引入机器人的路径规划，实现了 ESDF 地图使用上的突破。沿着这一思路，后续研究中，许多框架直接利用梯度信息进行优化配置空间中的轨迹6，有非常好的效果。在路径搜索这一问题上，A*算法是一种经典的路径搜索算法，在使用 A*算法进行路径规划时，虽然能找到最短路径，但 A*算法不考虑无人机的动力学可行性，在实际飞行过程中，无人机可能会面临危险7，且在面对动态环境
12、时，A*算法并不适用8。文献 9 采用高阶 B 样条曲线进行路径规划，该方式的优点在于预规划的路径更为平滑，且有助于动态重规划。为了实现动态重规划，文献 56 就平滑、碰撞和可行性创建惩罚项，以此设计约束方程，对轨迹进行动态规划。然而，部分动态规划算法会将时间这一维度抽离10，用离散的时间进行轨迹优化。这样的方式并不适用于无人机，因为它对动态约束更加敏感。为此，Oleynikova 等11 提出了一种用于无人机规划的连续时间多项式轨迹优化方法。本文借鉴这一思想设计时间再分配策略。文中的路径规划算法采用 B 样条曲线进行预规划路径，根据飞行约束方程，结合 ESDF 地图提供的梯度信息，实现路径搜
13、索。在飞行的过程中，结合时间再分配策略，进行无人机飞行轨迹的动态规划，实现动态避障。算法流程如图 1 所示。图 1算法流程Fig1Flow chart of algorithm2算法实现21ESDF 地图进入 21 世纪，ESDF 被用于从传感器中过滤嘈杂的数据，并构建对象12，而 atliff 等5 带来了新的思路，将 ESDF 用于机器人的运动规划。ESDF 在运用初期，不适用于增量构建，而在四旋翼无人机飞行过程中，需要不断对场进行动态更新。为此，Han等13 提出增量 ESDF 生成方式，实现并验证了ESDF 的动态更新。ESDF 源 于 TSDF(Truncated Signed Di
14、stanceFunctions)，TSDF 对距离信息进行了截断，即远离障碍物曲面一定距离后，视为无限大。这样的处理方式导致路径信息在穿过无限大的区域时，无法获取梯度信息。当控制点在障碍物里面时，无法被排斥出来。ESDF 不对距离信息进行截断，可以很方便地对当前位置到障碍物表面的距离和梯度信息进行查询。采用开源工具 FIESTA 的原理13，可以快速生成并动态更新 ESDF 地图。其流程如图 2 所示。第一步，由传感器获取周围环境的位置信息和深度信息。第二步，使用光线追踪法将点云叠加到占有的栅格地图中，然后将所有占用状态发生改变的体素分别添加到 insertQueue 和 deleteQueu
15、e 两个队列中。专题:面向 B5G/6G 的无人机通信2023 年 无线电工程 第 53 卷 第 1 期13第三步，初始化 ESDF，将前2 个队列合并到 up-dateQueue 队列中，并使用基于广度优先搜索算法的ESDF 更新算法更新所有可能更改的体素。图 2FIESTA 流程Fig2Flow chart of FIESTA22B 样条曲线传统寻路算法如 A*算法等，在生成路径时，部分路径段存在尖锐拐点。为了保障无人机飞行的安全性，采用 B 样条曲线进行路径优化可获得平滑路径14。B 样条曲线的核心在于节点的划分，在无人机的路径规划中，B 样条曲线的节点就是一个个的控制点 Q。控制点作为
16、决策变量，影响一段曲线的形状。B 样条曲线的数学表达式如下:C(x)=ni=0QiNi，k(x)，(1)式中，Ni，k(x)是 k 次 B 样条基函数，又称调和函数，是一个递归函数。其递归表达式如下:Ni，k(x)=1k!kij=0(1)yCyk+1 Dk，(2)式中，0 x1;i=0，1，k1;y=1，2，k;Cjk+1和Dk的计算如下:Cyk+1=(n+1)!y!(n+1y)!，(3)Dk=(x+kiy)k。(4)路径规划过程中，先生成初始控制点，并通过迭代的方式检测路径信息，对于迭代中检测到的每个碰撞段，生成无碰撞路径。之后，每个控制点 Qi将在障碍物表面上分配一个锚定点 Pij，并具有相应的排斥方向向量 vij，如图 3 所示。图中，i 为控制点的个数，j 为锚定点的个数，每一个锚定点和它的方向向量组合成一个(P，v)对，一个(P，v)对只对应一个控制点 Qi。一个控制点到第 j 个锚定点的距离，即控制点到障碍物表面的距离可定义为 dij，计算如下:dij=(QiPij)vij。(5)图 3控制点与锚定点Fig3Control points and anchor points2
