Shortest Path Evaluation with Enhanced Linear Graph and Dijkstra Algorithm

Path planning is one of the vital tasks in the intelligent control of autonomous robots. It is of prime importance from industrial as well as commercial point of view. Various autonomous vehicles are gaining popularity to reduce the on-field intervention of humans. The path planning problem is divided into two sub-problems: finding the feasible node pairs and then evaluate the shortest feasible path from the obtained feasible node pairs. Feasible node pair is the part of the path which do not pass through any obstacle. For the known static arena, the most popular method to solve these kinds of problems is the visibility graph (VGraph), but it is computationally intensive. This paper proposes an Enhanced Linear Graph (ELGraph), a method for finding feasible node pairs. The ELGraph has simplified linear structure which exploits the concept of line segment intersection, which may take low computational time. The simulations were carried out for VGraph and ELGraph to get the feasible node pair, and then Dijkstra algorithm evaluates the shortest feasible path. The results obtained shows that ELGraph takes lesser evaluation time and is computationally lesser intensive than VGraph, without compromising on finding the shortest possible feasible path.