Impact of spatial resolution on mobile robot path optimality in two-dimensional lattice models

Moskalev P.V., Stebulyanin M.M., Myagkov A.S.
 pdf (712K)

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.

Keywords: mobile robot, optimal pathfinding, lattice percolation, percolation cluster, Leath algorithm, A* algorithm, Gilbert – Johnson –Keerthi algorithm, expanding polytope algorithm
Citation in English: Moskalev P.V., Stebulyanin M.M., Myagkov A.S. Impact of spatial resolution on mobile robot path optimality in two-dimensional lattice models // Computer Research and Modeling, 2025, vol. 17, no. 6, pp. 1131-1148
Citation in English: Moskalev P.V., Stebulyanin M.M., Myagkov A.S. Impact of spatial resolution on mobile robot path optimality in two-dimensional lattice models // Computer Research and Modeling, 2025, vol. 17, no. 6, pp. 1131-1148
DOI: 10.20537/2076-7633-2025-17-6-1131-1148
URL: http://crm-en.ics.org.ru/journal/article/3671/
Creative Commons License This work is licensed under a Creative Commons Attribution-NoDerivs 3.0 Unported License.

Copyright © 2025 Moskalev P.V., Stebulyanin M.M., Myagkov A.S.

Indexed in Scopus

Full-text version of the journal is also available on the web site of the scientific electronic library eLIBRARY.RU

The journal is included in the Russian Science Citation Index

The journal is included in the RSCI

International Interdisciplinary Conference "Mathematics. Computing. Education"

Website Copyright © 2009–2025 Institute of Computer Science