用弗洛伊德算法为无人机规划最优无障飞行路径
Obstacle-Free Path Planning for Autonomous Drones Using Floyd Algorithm
- 基于弗洛伊德算法构建全局最短路径，支持大范围带障碍区域导航
- 路径规划时间随场景规模呈立方增长，与障碍物和无人机数量无关
- 适合大规模单机或集群无人机路径规划任务，尤其看重效率的场景
本研究探讨弗洛伊德算法在自主无人机（UAV）无障飞行路径规划中的应用效率。该算法可生成无人机从任意起点到目的地的最短无障碍路径，适用于存在不可穿越障碍的大规模飞行区域。仿真结果表明，弗洛伊德算法能有效规划最短路径，其时间复杂度为O(n³)。研究发现，计算耗时与场地规模呈三次多项式关系，但与障碍物数量及无人机数量无显著相关性。论文还讨论了研究成果的实际应用场景。
原文摘要 · Abstract (English)
This research investigates the efficiency of Floyd algorithm for obstacle-free path planning for autonomous aerial vehicles (UAVs) or drones. Floyd algorithm is used to generate the shortest paths for UAVs to fly from any place to the destination in a large-scale field with obstacles which UAVs cannot fly over. The simulation results demonstrated that Floyd algorithm effectively plans the shortest obstacle-free paths for UAVs to fly to a destination. It is verified that Floyd algorithm holds a time complexity of O(n3). This research revealed a correlation of a cubic polynomial relationship between the time cost and the size of the field, no correlation between the time cost and the number of obstacles, and no correlation between the time cost and the number of UAVs in the tested field. The applications of the research results are discussed in the paper as well.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。