Trajectory Planning For UAV Navigation In Grid-based Environments With Matrix Alignment Dijkstra

Trajectory planning problem in the dynamic environments is a challenging task because it is parameterized by time.Multitudinous restrictions should be take into consideration like dynamic terrain collision.However,some methods treat dynamic restrictions as static in order to reduce cost and obtain efficient and acceptable paths.To achieve optimal,efficient and acceptable paths,we first design the extended hierarchical graph(EHG)to model the unexplored dynamic grid environment and convert weather condition to detail passable coefficient.By this way,the generated trajectories are safest.Then we propose a new forward-exploration and backward-navigation algorithm,Matrix Alignment Dijkstra(MAD),to guide unmanned aerial vehicle in the dynamic environment.According to MAD,we use matrix operation to simulate propagation from the moment T to T+1 along time dimension to generate an optimal path.Benefit from GPU’s parallel computing power,this process is accelerated.In addition,we can accomplish UAV’s path planning from one source grid to multiple target grids within one single run.To prove the method’s effectiveness,we present results of simulation of an UAV within the dynamic weather data and analyse the performance of MAD in different scale scenarios.The comparison models include Dijkstra’s algorithm and Improved-3D A * algorithm in the graph-based path planning algorithm.The indicators include the average time cost and the safety factor of the generated path.Then based on the benchmak dataset of the grid environment and the artificially maze environment,the performance analysis experiment of MAD was carried out,and the performance of MAD and Dijkstra,Bidirectional Dijkstra and Multi-Thread Dijkstra in different scale environments was studied and compared in depth.The experimental results show that MAD’s planning efficiency and path safety factor are better than the baseline planning model in the real weather data environment.It is verified that the efficiency of MAD increases linearly with the scale of the target environment,which has a very high Accuracy and efficiency.