复杂环境下无人机全覆盖三维路径规划算法

Full coverage 3D path planning algorithm for UAV in complex environment

针对复杂实际环境下无人机进行快速三维全覆盖路径规划的问题,提出了无人机全覆盖三维路径规划算法。首先,二维全覆盖路径规划由全局运动策略、局部运动策略和摆脱死区策略组成,在全局运动策略中改进标记函数和提出次层起点动态搜寻策略,摆脱死区策略由A^(*)算法和改进环形搜索算法构成;三维全覆盖路径规划由分层规划策略、地图重构策略和层间连接策略组成,分层规划策略将三维分为不同间隔高度的二维环境,地图重构策略对二维进行动态地图构建,层间连接策略由头一层的遍历终点确定下一层的遍历起点。仿真结果表明:所提算法在二维全覆盖路径规划时,相较于传统的单环搜索方式摆脱死区策略,路径长度缩短2.7%,路径重复率减小3%;相较于无局部运动策略,路径长度缩短14.2%,总死点数目和路径重复率降低32.9%和4.4%,且运行时间减少6.7 s;在三维全覆盖路径规划时,相较于无地图重构策略,路径长度缩短27.33%,死点数目减少16.82%,运行时间减少70.8 s,路径重复率减小7%;最后进行参数分析,得出本算法性能最优时参数取值。综上,该算法能够适应复杂环境,且能有效降低死点数目和路径重复率,快速规划全覆盖路径,具有较好的鲁棒性。

To solve the problem of rapid three-dimensional full coverage path planning of Unmanned Aerial Vehicle(UAV)in complex practical environment,a three-dimensional full coverage path planning algorithm of UAV was proposed.The two-dimensional full coverage path planning was composed of global motion strategy,local motion strategy and getting rid of dead zone strategy.In the global motion strategy,the marking function was improved and the sub layer starting point dynamic search strategy was proposed.The getting rid of dead zone strategy was composed of A^(*)algorithm and improved ring search algorithm.The three-dimensional full coverage path planning consisted of hierarchical planning strategy,map reconstruction strategy and inter layer connection strategy,and the hierarchical planning strategy divided the three-dimensional into two-dimensional environments with different interval heights.The map reconstruction strategy constructed the two-dimensional dynamic map,and the inter layer connection strategy determined the traversal starting point of the next layer from the traversal end point of the first layer.The simulation results showed that compared with the traditional single loop search method to get rid of the dead zone strategy,the path length was shortened by 2.7%and the path repetition rate was reduced by 3%.Compared with no local motion strategy,the path length was shortened by 14.2%,the total number of dead points and path repetition rate were reduced by 32.9%and 4.4%,and the running time was reduced by 6.7s.In three-dimensional full coverage path planning,compared with no map reconstruction strategy,the path length was shortened by 27.33%,the number of dead points was reduced by 16.82%,the running time was reduced by 70.8s,and the path repetition rate was reduced by 7%.The parameter analysis was carried out to obtain the parameter value when the algorithm had the best performance.The proposed algorithm could adapt to complex environment,effectively reduced the number of dead points,quickly planed the full coverage path,reduced the path repetition rate,and had good robustness.