北京大学程承旗课题组在室内三维复杂环境下的无人机航迹规划中取得新进展
北京大学程承旗课题组在室内三维复杂环境下的无人机航迹规划中取得新进展
【航迹规划已经成为无人驾驶飞行器（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在线发表。
北京大学程承旗教授团队在研究地球剖分网格框架理论的基础上，提出了2n一维整型数组的全球经纬度剖分网格（GeoSOT）。GeoSOT-3D将二维剖分的概念扩展到三维空间，其起始位置位于地球参考椭球体、本初子午线平面和赤道平面的交点（O点），如图1（b）所示。基于由经度、纬度和高程组成的0级网格，通过在经度、纬度和地球高度三个方向上的实体八叉树剖分，形成了一个多层级的地球三维空间网格系统，如图1（c）和（d）所示。因此，GeoSOT-3D为以后的无人机室内环境建模提供一个通用的空间框架。
图1.GeoSOT和GeoSOT-3D剖分结构示意图。（a） 具有四叉树结构的GeoSOT剖分网格金字塔。（b） GeoSOT-3D全局剖分图。（c） GeoSOT-3D八叉树数据结构图。（d） 不同级别的GeoSOT-3D分割块的实际形状。
该研究提出了一套针对室内复杂环境、通过网格优化的无人机航迹规划算法框架（图2），主要包含三个网格优化的核心算法：
图2. 网格优化的无人机室内路径规划算法框架图
网格优化的室内空域建模（GO-IAM）算法。基于GeoSOT-3D地球立体剖分网格模型，建立起一个增强的室内多层级三维网格空域模型，大大降低空域计算复杂性。
网格优化的A*航迹规划（GO-APP）算法。以常规室内场景为重点，GO-APP通过采用改进的A*网格算法，增加无人机的飞行约束与代价限制，可快速完成建筑物内的航迹规划（图3，图4），并能够有效完成楼层的穿越（图5）。
图3. 多旋翼无人机路径规划结果。(a)障碍物特殊放置下的路径规划。(b) 障碍物随机放置下的路径规划
图4. 固定翼无人机路径规划结果。(a)障碍物特殊放置下的路径规划。(b) 障碍物随机放置下的路径规划
图5. 无人机在楼层间穿越的模拟路径。（a） 固定翼无人机路径规划结果。（b） 多旋翼无人机路径规划结果。
网格优化的局部回溯航迹规划（GO-LBPP）算法。为了解决“死区问题”，GO-LBPP采用局部回溯策略，并改变无人机的搜寻视界（图6），在多障碍物的室内场景中实现了有效精确的无人机航迹规划（图7）。
图6. GO-LBPP算法中无人机视界的范围，以红色网格标注。无人机视界包括上下层的相邻邻域网格和长方体的侧网格，长方体是无人机侧邻域的n倍的空间扩展
图7. 局部回溯算法成功跳出室内环境中的局部死区。(a) 使用普通路径规划算法造成的死区。(b) 使用GO-LBPP算法的航迹规划结果
在多个无人机室内航迹规划算法的对比实验中，该研究将GO-APP算法与常用的模拟退火、Q-learning、人工势场、遗传算法、粒子群、蚁群等局部/全局规划算法的规划结果进行对比显示，GO-APP算法的航迹规划时间和规划航迹路线长度最短（表1），规划路径更优、可飞行性更高（图8）。而在多障碍物室内环境中采用GO-LBPP算法，则可以顺利解决室内局部死区问题，避免规划航迹的死锁，这是现有其他算法均无法实现的。未来这项工作将继续深入，将算法集与多机协同策略相结合，有望在无人集群协同规划中取得更多进展。
图8. 二维室内环境中不同无人机路径规划算法的规划路径图比较
表1. 二维室内环境中不同无人机路径规划算法的结果比较
北京大学前沿交叉学科研究院博士生韩炳是论文第一作者，北京大学工学院曲腾腾助理研究员是论文通讯作者，北京大学工学院程承旗教授是论文合作作者。上述研究得到了国家重点研发计划、国防基础加强重点项目及国家自然科学基金等资助。
荐读
《慧天地》敬告
《慧天地》公众号聚焦国内外时空信息科技前沿、行业发展动态、跨界融合趋势，发现企业核心竞争力，传播测绘地理信息文化，为时空信息类相关专业学子提供日常学习、考研就业一站式服务，打造政产学研金服用精准对接的平台。
《慧天地》借鉴《读者》办刊理念，把时空信息领域的精华内容汇聚到平台上。我们高度重视版权，对于精选的每一篇推文，都会在文章开头显著注明出处，以表达对作者和推文引用平台版权的充分尊重和感谢；对于来源于网络作者不明的优质作品，转载时如出现侵权，请后台留言，我们会及时删除。感谢大家一直以来对《慧天地》的关注和支持！
——《慧天地》运营团队
投稿、转载、商务等合作请联系
微信号：huitiandi321
邮箱：geomaticshtd@163.com