航迹规划已经成为无人驾驶飞行器（UAVs）的一个热点问题，特别是在复杂的室内环境中，现有无人机室内航迹规划解决方案因其计算复杂度高、收敛速度慢和飞行航迹差而受到很大限制。此外，由于室内障碍物密度更高，无人机在室内航迹规划过程中经常会陷入局部死区，导致算法死锁，无法获得飞行航迹。

近期，我司首席科学家、北京大学工学院程承旗教授课题组基于地球立体剖分网格GeoSOT-3D理论，建立起一套网格优化的无人机室内航迹规划算法集。该研究成果以“Grid-optimized UAV Indoor Path Planning Algorithms in a Complex Environment”（https://doi.org/10.1016/j.jag.2022.102857）为题于2022年6月9日在中科院1区TOP期刊International Journal of Applied Earth Observation and Geoinformation在线发表。

       该研究提出了一套针对室内复杂环境、通过网格优化的无人机航迹规划算法框架（图1），主要包含三个网格优化的核心算法：

          图1. 网格优化的无人机室内路径规划算法框架图

网格优化的室内空域建模（GO-IAM）算法。基于GeoSOT-3D地球立体剖分网格模型，建立起一个增强的室内多层级三维网格空域模型，大大降低空域计算复杂性。

网格优化的A*航迹规划（GO-APP）算法。以常规室内场景为重点，GO-APP通过采用改进的A*网格算法，增加无人机的飞行约束与代价限制，可快速有效完成建筑物内的航迹规划（图2）。

图2. 多旋翼无人机路径规划结果。(a) 障碍物特殊放置下的路径规划。(b) 障碍物随机放置下的路径规划

网格优化的局部回溯航迹规划（GO-LBPP）算法。为了解决“死区问题”，GO-LBPP采用局部回溯策略，并改变无人机的视界，在多障碍物的室内场景中实现了有效精确的无人机航迹规划（图3）。

图3. 局部回溯算法成功跳出室内环境中的局部死区。

(a) 使用普通路径规划算法造成的死区。(b) 使用GO-LBPP算法的航迹规划结果

在多个无人机室内航迹规划算法的对比实验中，该研究将GO-APP算法与常用的模拟退火、Q-learning、人工势场、遗传算法、粒子群、蚁群等局部/全局规划算法的规划结果进行对比显示，GO-APP算法的航迹规划时间和规划航迹路线长度最短（表1），规划路径更优、可飞行性更高（图3）。而在多障碍物室内环境中采用GO-LBPP算法，则可以顺利解决室内局部死区问题，避免规划航迹的死锁，这是现有其他算法均无法实现的。未来这项工作将继续深入，将算法集与多机协同策略相结合，有望在无人集群协同规划中取得更多进展。

图4. 二维室内环境中不同无人机路径规划算法的规划路径图比较

表1. 二维室内环境中不同无人机路径规划算法的结果比较

北京大学前沿交叉学科研究院博士生韩炳是论文第一作者，北京大学工学院曲腾腾助理研究员是论文通讯作者，北京大学工学院程承旗教授是论文合作作者。上述研究得到了国家重点研发计划、国防基础加强重点项目及国家自然科学基金等资助。