## 2 Obstacle Grid Map and True Shortest Path  
In robot path planning, constructing a grid map is a common method that helps identify the surrounding environment and make movement decisions. The grid map can be pre-built before path planning and remains unchanged during subsequent planning, known as static environment construction. Alternatively, it can be updated in real-time as the path planning progresses, known as dynamic environment construction. The grid map method is widely used due to its simplicity, intuitiveness, and ease of implementation. While the grid method can help construct environmental maps, real-life obstacles are not always regular shapes. To prevent collisions, we can directly overlay the grid map onto the obstacles and set the grids that fully or partially occupy the obstacles as obstacle grids, as shown in Figure 1. However, this rough approach may lack precision, leading to longer planned paths. To address this, we can enhance accuracy by increasing resolution [21], thus better simulating real obstacle environments, as illustrated in Figure 2. We can increase the resolution until it falls within an acceptable error range. Therefore, the obstacle grid maps mentioned in the following sections refer to regular obstacle environments. Additionally, it is important to note that in some studies, the behavior of a path passing through the common point of two obstacle grids that share only one common point is considered a valid path. However, this practice is unsafe in real life. Therefore, this paper  
Figure 1: Obstacles covered with a grid map. Figure 2: Better fitting obstacles by increasing the resolution of the grid. considers such behavior as illegal. In the subsequent sections of this paper, neither SGPs nor TSPs involve such behavior. The shortest path problem in obstacle grid maps can typically be solved using various algorithms, such as backtracking, [PERSON]'s algorithm, and dynamic programming. However, these algorithms usually explore only four or eight directions. Due to the limited search directions, the shortest paths found are not TSPs but SGPs. A TSP is the shortest (Euclidean) polyline path from the starting grid to the endpoint grid, which does not intersect with the set of obstacles except at vertices or edges and avoids crossing the common edge of two obstacle grids that share a complete edge. In contrast, an SGP is the shortest path from the starting point to the endpoint through continuous movements in eight directions within the obstacle grid map. As shown in Figure 3, path **a** represents an SGP, while path **b** represents a TSP. In the obstacle grid map, due to the obstacles, it is necessary to take a longer route to reach the destination. Most path search algorithms can only explore in eight directions, which correspond to four grids sharing a common edge and four grids sharing a common point. When the starting point and the endpoint cannot be directly connected by obstacles, the TSP requires moving along the boundaries or vertices of the obstacles. The limitation on search directions results in the difference between SGPs and TSPs. However, searching in all possible directions would require a significant amount of time. In an obstacle-free map, if the starting point and the endpoint are on the same row or column, SGPs and TSPs are identical. However, when the destination is offset so that it is not on the same row, column, or diagonal as the starting point, a difference between SGPs and TSPs emerges. This is because SGPs can only turn at 45-degree angles, whereas TSPs can turn at any angle. By placing some obstacle grids in the path of TSPs, the movement angles of TSPs are also restricted. TSPs can no longer move directly from the starting point to the endpoint, but must navigate around obstacles by using their vertices or edges. Although searching in any direction is too costly, searching for SGPs is very easy, and there is a connection between SGPs and TSPs.