Systems Engineering and Electronics ›› 2018, Vol. 40 ›› Issue (12): 2714-2721.doi: 10.3969/j.issn.1001-506X.2018.12.14

Previous Articles     Next Articles

Dynamic path planning using anytime repairing sparse A* algorithm

WANG Shengyin1,2, LONG Teng1,2, WANG Zhu1,2, CAI Qisheng1,2#br#   

  1. 1. School of Aerospace Engineering, Beijing Institute of Technology, Beijing 100081, China;
    2. Key Laboratory of Dynamics and Control of Flight Vehicle, Ministry of Education, Beijing 100081, China
  • Online:2018-11-30 Published:2018-11-30

Abstract:

To satisfy the requirements of efficiency, feasibility, and optimality of unmanned aerial vehicle path planning in dynamic environment, an anytime repairing sparse A* search (AR-SAS) algorithm is proposed, by incorporating the sparse A* search (SAS) into anytime repairing framework and introducing double criteria ordering, memory bounded and adaptivestep expanding strategies into the process of path optimization. Monte-Carlo simulations in static environment demonstrate that AR-SAS takes less time to generate the feasible path and optimal path compared with standard SAS and hierarchical SAS. Simulation results in dynamic environment show that AR-SAS can satisfy the requirements of dynamic planning to rapidly produce a feasible path and gradually improve the path quality in given time.

[an error occurred while processing this directive]