Abstract: To realize autonomous route planning of the UAV under different conditions, a kind of Sparse A* Search（SAS） algorithm with changeable steps is presented. When near the critical threat it switches to small step in the SAS algorithm, which can guarantee the search accuracy and the robustness of the algorithm, otherwise, keeps searching with big step for improving efficiency of the search. Based on the idea of Dynamic Sparse A* Search（DSAS）, a multi-step search method which can be applied to real time route planning is provided. Simulation results show that the algorithm can effectively realize route planning in complicated environment and achieve real-time path planning in dynamic environment.

Key words: route planning, changeable step, robustness, real-time planning

摘要： 为实现不同条件下的无人机自主航路规划，提出一种变步长稀疏A*算法。当遭遇紧迫环境时，缩小稀疏A*算法（SAS）的搜索步长，使无人机安全通过，提高了搜索精度和算法的鲁棒性，否则，保持较大的搜索步长扩展，保证搜索的高效性；并依据动态稀疏A*算法（DSAS）的思想，给出了应用于实时航路规划的多步搜索方案。仿真结果表明，算法简单有效地实现了复杂环境下的航路规划以及动态环境下的在线实时航路规划。

关键词: 航路规划, 变步长, 鲁棒性, 实时规划