# Fast Path Generation Algorithm for Mobile Robot Navigation Using Hybrid Map
## 3 Proposed Methods
### Path Generation  
In RC-Map, the concept of AP (Adjacent Point) is introduced for fast path generation. An AP refers to the center point of the adjacent parts when two areas are adjacent. In the actual implementation of the method, one area is expressed as a node. Assume that two nodes A and B are as in Equations (1) and (2). As in Figure 3a, the AP of the adjacent nodes can be expressed by Equation (3), and the AP of two nodes adjacent to each other vertically, as in Figure 3b, can be expressed by Equation (4).  
\[Coordinates\ of\ area\ A:A(A_{x1},A_{y1},A_{x2},A_{y2}) \tag{1}\]  
\[Coordinates\ of\ area\ B:B(B_{x1},B_{y1},B_{x2},B_{y2}) \tag{2}\]  
\[AP(x,y)=\left(B_{x1},\frac{A_{y1}+B_{y2}}{2}\right) \tag{3}\]  
\[AP(x,y)=\left(\frac{A_{x1}+B_{x2}}{2},B_{y1}\right) \tag{4}\]  
After RC-Map is generated, the mobile robot can utilize the AP to move through the area. If the AP is obtained through Equations (3) and (4), a path can be quickly generated that can pass through the AP and arrive at position G regardless of where it is in area A.  
Figure 3: Creating a path using APs. (**a**) Generate a path when A and B are adjacent to each other on the left and right. (**b**) Generate a path when A and B are adjacent up and down.  
Figure 2: Implementation of RC-MAP. (**a**) Visual representation of the RC-MAP data structure. (**b**) Internal data structure of RC-MAP.  
For example, when there is a robot in area A on the left of Figure 2(a) and the robot moves to position G of node B, the robot in node A can move directly to the AP and then to position G. Using this method, faster path generation is possible compared to grid-based path generation. Figure 3 visually shows the path created using the generated AP.  
In RC-Map, the movement of a mobile robot from the current space to the next final destination can be viewed as a movement between nodes. It can move from the current location to the AP of the immediately adjacent space, and then to the AP of the adjacent node, and repeat this process to reach the final destination. At that time, moving to the AP may not be the shortest path. However, considering the safe movement of the robot, moving from a node in a free space to the AP is an appropriate choice in the robot's situation.  
The fast path generation algorithm using RC-Map requires data in the form of the topology of G(V, A) and a start node and a destination node to find the optimal path. RC-Map is in the form of general graph data, so various graph search algorithms can be utilized. In this paper, [PERSON]'s algorithm, which is widely used to solve the shortest path problem in graphs, was modified to operate according to the RC-Map data structure [40]. Algorithm 1 demonstrates how to generate a fast shortest path by utilizing RC-Map.  
```
Data:\(G(V,A),Start\)node, Goal node
1 while each node \(v\) in \(V\)do
2\(distance[v]=cost[start][v]\);
3\(path[v]=start\);
4\(found[v]=0\);
5
6 end while
7\(found[start]=1\);
8\(distance[start]=0\);
9 while each node \(v\) in \(V\)do
10\(u=choice()\);
11\(found[u]=1\);
12 while each node \(v\) in \(V\)do
13 if\(found[w]==0\)then
14 if\(distance[u]+cost[u][w]<distance[w]\)then
15\(distance[w]=distance[u]+cost[u][w]\);
16\(path[w]=u\);
17
18
19 end if
20
21 end while
22
23 end while
24
25 end while
```  
**Algorithm 1**Shortest path generation using RC-MAP