Adaptive Visibility Graph Initialization on Edge Computing to Accelerate Hybrid Path Planning for Mobile Robots

Abstract

This paper presents a new initialization method for hybrid path planning that integrates adaptive visibility graphs (AVG), Dijkstra’s algorithm, and genetic algorithm (GA) on an edge computing platform. Several algorithmic innovations are proposed to improve its accuracy and computing efficiency. First, an adaptive approach is developed to stochastically eliminate segments/links of the full visibility graphs during each iteration, generating diverse AVGs. Then, many shortest paths corresponding to various AVGs are found using Dijkstra’s algorithm. Next, multiple different paths with low fitness values are selected to initialize the GA populations for enhanced exploration, which is distinctly different from the existing method. Its performance is evaluated on an edge computing device (Jetson AGX Xavier), and a strategy to properly utilize CPU/GPU resources is also elucidated. Parametric numerical experiments are carried out to configure desirable GA hyperparameters. Given various practical constraints of mobile robots, the present method yields different optimal paths accordingly. It is then compared with other benchmark techniques in terms of the fitness value, computing speed, and number of waypoints, and exhibits superior performance.