Efficient Path Planning Under Dynamic Environment For The Mobile Robot

Path planning is one of the key problems in the field of a mobile robot,which mainly involves the feasible path search from the current position to the target position in the workspace.The environment of path planning can be static or dynamic.When there are dynamic obstacles in the environment,the path planning algorithm should not only find the optimal path,but also keep tracking the optimal path,and update its path in realtime with a high enough frequency to maintain the response to the surrounding events.This paper presents the solution regarding the problem related to path planning in D*lite.Based on the analysis of the existing D* Lite programming methods,improvements,and optimizations are proposed in this thesis.It includes:1)The existing planning methods are analyzed and compared.In engineering,there are two different ways to solve a problem: a mathematical method or heuristic method.In the mathematical method,it is more concerned about the solution than the calculation that is feasible for the algorithm.In the heuristic method,the algorithm must use special knowledge of the problem area.Heuristics can solve problems in many different ways from beginning to the end.When one or more obstacles intersect,the calculation process will be very complex.Researchers have been looking for more effective ways to solve the problem of path planning.Many methods and algorithms are applied to solve path planning problems,such as D* Lite algorithm,road map(Voronoi diagram and visibility diagram),A* algorithm,fuzzy logic,particle swarm optimization algorithm,PBIL algorithm,ant colony algorithm,simulated annealing,potential field,etc.In different environments,each method has its benefits and backdraws.2)Analysis and improvement of D* Lite path planning.D* Lite algorithm is an adaptation of Koenig's lifetime planning a *(LPA *),which is a derivative of A* search(including incremental search).The incremental search method reuse information from previous searches to find solutions to similar problems faster rather than solving each search task from scratch.From the existing research and review,the backdraws of D *Lite algorithm are that it takes binary minimum heap as data structure,heuristic function problem based on Chebyshev distance,and four-dimensional edge cost structure,and has o(NX * NY)complexity when deleting specific items.Through the analysis of D* Lite algorithm,we propose some improvement measures:(?)reduce the complexity of priority queue;(?)improve heuristic function;and(?)create a threedimensional edge cost structure.3)The performance of the improved D* Lite algorithm is simulated and evaluated from the following aspects:(?)obstacle avoidance ability;(?)finding the shortest path from the target to the starting position in the environment;(?)remembering the path;(?)re-planning the ability path to the target position when new obstacles are blocking.(v)Move unnecessary paths to the shortest path.The simulation results show that the improved D*Lite is effective.