Value Iteration Algorithm for Solving Shortest Path Problems with Homology Class Constraints

Path planning is a fundamental problem in robotics that aims to find an optimal path for a system to move on while avoiding obstacles in the environment. Often, a feasible path connecting the start and target point with the shortest length is highly desirable. Additionally, in scenarios such as drone racing or surveillance, topology constraints may arise. In this paper, we propose a novel method to address the shortest path problem with homology class constraints in both 2D and 3D environments. We first define the phase change of the path with respect to 2D obstacles and then apply the same technique to a class of super-toroid obstacles compressed by an embedding map. To synthesize the shortest path, we leverage the visibility graph and the Value Iteration Algorithm (VIA). Finally, we demonstrate the effectiveness of our approach with various simulation examples.