On an almost closed-form fast generation of Euclidean shortest path trajectories in cluttered environments

Abstract

This paper addresses the challenge of determining the shortest path in a domain with static obstacles by leveraging the concepts of visibility graphs and visibility polygons. The core idea is that, since the obstacles are considered static, the only parts of the overall graph that are subject to change are the edges that connect the initial and final nodes to the rest of the graph. This allows the overall graph to be divided into two sub-graphs: (i) a static sub-graph that captures the visibility among subsets of the obstacle vertices and that can be computed offline, and (ii) a dynamic sub-graph that connects the initial and final points to the static sub-graph. This division entails fewer online computations when computing the shortest path, as building the entire visibility graph can be time-consuming. Additionally, we propose a purely geometrical approach based on visibility polygons to determine the connections between the initial and ending nodes. We then divide the environment into sub-regions to reduce the search space, making the dynamic linking of the starting and ending nodes faster.