Abstract:
This paper examines the impact of the spatial resolution of a discretized (lattice) representation of the environment on the efficiency and correctness of optimal pathfinding in complex environments. Scenarios are considered that may include bottlenecks, non-uniform obstacle distributions, and areas of increased safety requirements in the immediate vicinity of obstacles. Despite the widespread use of lattice representations of the environment in robotics due to their compatibility with sensor data and support for classical trajectory planning algorithms, the resolution of these lattices has a significant impact on both goal reachability and optimal path performance. An algorithm is proposed that combines environmental connectivity analysis, trajectory optimization, and geometric safety refinement. In the first stage, the Leath algorithm is used to estimate the reachability of the target point by identifying a connected component containing the starting position. Upon confirmation of the target point’s reachability, the A* algorithm is applied to the nodes of this component in the second stage to construct a path that simultaneously minimizes both the path length and the risk of collision. In the third stage, a refined obstacle distance estimate is performed for nodes located in safety zones using a combination of the Gilbert – Johnson –Keerthi (GJK) and expanding polyhedron (EPA) algorithms. Experimental analysis revealed a nonlinear relationship between the probability of the existence and effectiveness of an optimal path and the lattice parameters. Specifically, reducing the spatial resolution of the lattice increases the likelihood of connectivity loss and target unreachability, while increasing its spatial resolution increases computational complexity without a proportional improvement in the optimal path’s performance.
Fulltext:
PDF file (711 kB)