Graphics processing unit-enabled path planning based on global evolutionary dynamic programming and local genetic algorithm optimization

Abstract

This paper presents a novel path planning method for real-time robotic path planning in a dynamic environment involving moving obstacles. It combines on a holistic platform a global approach to rapidly generate initial paths of prominent diversity and a heuristic approach to enable local path refinement for enhanced computational efficiency, exploration, and robustness. The global approach innovates a formulation that treats a path planning problem with a visibility graph as a Markov decision process and decomposes the process into many subproblems. A new evolutionary dynamic programming approach (EDP) is proposed to solve these subproblems in an iterative manner using graphics processing unit (GPU) computing to allow backpropagation of state values from goal to start points. The EDP generates multiple feasible initial paths with salient state values, each initializing an independent genetic algorithm (GA) optimization on waypoints only near the mobile robot, and all GAs are run in parallel on GPU, further improving exploration and convergence speed. The strategy to fully utilize CPU/GPU resources for various components in the pipeline is also established. The proposed algorithms are then implemented on an edge computing device (Jetson AGX Xavier) onboard a mobile robot (TurtleBot 3 Waffle Pi). Optimal paths can be continuously generated at the rate of 0.1 seconds/path, enabling successful obstacle avoidance and robot navigation through dynamic environments and, hence, verifying the real-time capabilities and accuracy of the present method. Compared to other benchmarks, the present method greatly enhances path planning robustness, computing speed, and path quality. • Path planning problem is treated as a Markov decision process. • A new evolutionary dynamic programming approach (EDP) is proposed. • All genetic algorithms (GAs) are run in parallel on GPU. • It is implemented on an edge computing device onboard a mobile robot.