林　娜，李天啸

(沈阳航空航天大学 计算机学院，沈阳 110136)



基于双向A*算法的城市无人机航路规划

林娜，李天啸

(沈阳航空航天大学 计算机学院，沈阳 110136)

应用双向A*算法对在城市环境中的无人机进行航路规划，对比传统的A*搜索算法，双向A*搜索算法提高了搜索的效率，大大缩短了航路规划的时间。同时针对双向A*算法现有的不足，对双向A*算法进行改进，提出了同步双向A*搜索算法思想，通过编程实现双向A*算法正向搜索和反向搜索同步进行，并且采用栅格法对无人机的飞行环境进行建模，在建模时充分考虑城市环境确定栅格的大小。通过实验验证，同步双向A*算法可以快速为无人机规划出航路，且航路可飞，对比改进前的双向A*算法，同步双向A*算法的航路规划速度更快，效率更高。

无人机；双向A*；栅格法；城市环境；航路规划

A*算法是一种经典的启发式搜索算法，并广泛应用于路径搜索问题中。A*算法的思想最早由P.E Hait和N.J Nilsson提出，在以后的应用中得到了不断的改进与发展。如：J.Szczerba提出了稀疏A*算法(Sparse A*Search，SAS)[1]，其主要思想为通过一个约束函数将A*算法的搜索范围缩小，缩短了算法的时间，提高了算法的搜索效率；何雨枫、曾庆化等提出了无记忆A*算法[2]的思想，针对A*算法的OPEN表和CLOSE表进行改进，使OPEN表中的节点数每次都保持最小，从而提高算法的计算速度。

而以上方法都是基于单一方向的A*算法，即从起始节点向目标节点搜索。而本文将应用双向A*算法对无人机的航路进行搜索，并针对传统双向A*算法存在的不足，提出了同步双向启发式A*算法，将其应用于栅格建模环境中。……