## 2 Navigable Graph of an Environment
### Junction Node Extraction  
The watershed segmentation algorithm produces several grid map segments with different labels, separated by edges/boundaries one pixel in width. To construct a navigable graph using the segments, the junction nodes between adjacent segments must be defined. In the proposed path-planning method, these nodes serve as sub-goals/waypoints, allowing movement to the next path regions, defined as local regions through which the robot must pass. Algorithm 1 shows how to extract junction nodes, \(Node\), and how to construct the adjacency matrix, \(Adj\), of the grid map segments. Algorithm 1 requires two inputs, \(gridmap_{\text{dist}}\) and \(gridmap_{\text{ws}}\). \(gridmap_{\text{dist}}\) is the normalized distance transform of the grid map, and \(gridmap_{\text{ws}}\) is the watershed segmentation result where each pixel value shows the label identification of the corresponding segment. The algorithm first inspects all edges of cells, \(grid_{\text{edge}}\), in the watershed segmentation result and combines the edge cells that share neighbors into a matricized form, \(Adj^{\text{cells}}\), wherein each component is a group of cells lying between the same adjacent segments (Lines 4-10). \(Adj\) is the adjacency matrix among grid map segments. If there are \(M\) segments, the size of the symmetric matrix \(Adj\) is \(M\). If there are any edge cells between two segments \(i\) and \(j\), \(adj_{i,j}\) and \(adj_{j,i}\) are one (Line 8). Each component \(adj_{i,j}^{\text{cells}}\) of \(Adj^{\text{cells}}\) stores all edge cells between two segments \(i\) and \(j\) (Line 7). Figure 3: The navigable graph structures of the segmented grid maps: (**a**) The segmented grid maps and the junction nodes (yellow dots). (**b**) The adjacency matrix of grid map segments. (**c**) A navigable graph. For each group of edge cells, we inspect and obtain the connected edge segments using the CCL (Line 13), which can deal with the situation in which two adjacent grid map segments can be connected via several separate edge areas. The junction node should be the safest grid cell; thus, we select the cell exhibiting the maximum, normalized distance transform value with respect to one of the connected edge segments (Line 16). Finally, we obtain the junction nodes and the adjacency matrix of the grid map segments (Line 20). ```
1:\(gridmap_{\text{dist}}\), \(gridmap_{\text{ws}}\)
2:junction nodes \(Node=\left\{node_{i,j}^{n}\mid 1\leq n\leq N,\ N\text{ is the number of junction nodes. }\right\}\), adjacency matrix among grid map segments \(Adj\)
3:functionSelect-Junction-Node(\(gridmap_{\text{dist}}\), \(gridmap_{\text{ws}}\))
4: Set \(Adj^{\text{cells}}=\left\{adj^{\text{cells}}_{i,j}|\ adj^{\text{cells}}_{i,j}= \emptyset,\ 1\leq i,j\leq M,\ M\text{ is the number of segments. }\right\}\)
5: Set \(Adj=\left\{adj^{\text{cells}}_{i,j}|\text{ the identity matrix of size }M\times M,\ M\text{ is the number of segments. }\right\}\)
6:\(\triangleright\) Grouping edge cells that have the two same neighboring segments and calculating the adjacency
7:for all\(grid_{\text{edge}}\in gridmap_{\text{ws}}\)do
8: Inspect eight neighbor cells around \(grid_{\text{edge}}\). 9:if there are two different labeled neighbors, and their labels are \(i\) and \(j\)then
10:\(adj^{\text{cells}}_{i,j}\gets adj^{\text{cells}}_{i,j}\cup\left\{grid_{ \text{edge}}\right\},\ adj^{\text{cells}}_{j,j}\gets adj^{\text{cells}}_{ i,j}\)
11:\(adj_{i,j}\gets 1,\ adj_{j,i}\gets adj^{\text{cells}}_{i,j}\)
12:endif
13:endif
14:endfor
15:\(n\gets 0\) \(\triangleright\) Selecting junction node cells for each group of edge cells in \(Adj^{\text{cells}}\)
16:for all non-empty \(adj^{\text{cells}}_{i,j}\in Adj^{\text{cells}}\)do
17:\(adj^{\text{cells},1}_{i,j}\cup\cdots\cup adj^{\text{cells},K}_{i,j}=adj^{ \text{cells}}_{i,j}\), \(K\) is the number of disconnected edge segments in \(adj^{\text{cells}}_{i,j}\).