陈朋 江勇奇 俞天纬 党源杰 宦若虹

(1.浙江工业大学 计算机科学与技术学院，浙江 杭州 310023；2.浙江工业大学 信息工程学院，浙江 杭州 310023)

近年来，随着无人机(UAV)广泛地应用于空中拍摄、灾后救援和城市安防等各种场景，人们对无人机自主导航能力的要求也逐渐提高，尤其是在长距离导航方面。航迹规划是实现无人机自主导航的关键技术之一，其可分为前端路径搜索和后端轨迹优化[1]。前端通过路径搜索算法获得空间上无碰撞的初始路径，但缺少在时域上对无人机速度和加速度的设定；后端则在前端基础上进行优化，生成更加平滑、安全且适合无人机动态飞行的轨迹。

前端路径搜索主要分为基于采样的和基于图搜索的两类方法。基于采样的代表算法快速探索随机树(RRT)[2]从配置空间中随机地抽取样本，并引导树向目标生长。虽然RRT算法能够有效地找到可行的路径，然而没有渐近最优性。Karaman等[3]提出了基于采样的渐进最优方法RRT*，随着样本数的增加，该算法最终会收敛到全局最优解。基于采样的方法虽能有效地解决了复杂约束的路径规划问题，但算法效率不稳定。基于图搜索的方法虽未必能找到最优路径，但效率极高且稳定，更符合无人机的实时要求。基于图搜索的代表算法A*将配置空间离散化，把路径搜索问题转化为图搜索问题，根据图中节点代价寻找最优路径[4]。近年来人们通过改进算法A*来解决相应的实际问题。Dolgov等[5]提出了基于物体实际运动约束的混合A*算法，生成符合车辆运动规律的轨迹。……