## 3 Marker-Assisted Region Scanning
### Update Robot State
## Appendix A Algorithms
```
0: Current Pose (\(P_{k}\)), Target marker (\(\eta\)), Action (\(A\)), Grid Map (\(G\)), Path (\(\Psi\))
0: Updated Pose (\(P_{k+1}\)), Updated LiDAR Measurements (\(L\))
1:if\(A\) is rotate then
2:\(P_{k+1}\leftarrow\) rotate robot [Sections 4.3-4.5]
3:\(L\leftarrow\) LiDAR measurements
4:elseif\(A\) is towards \(\eta\)then
5:if way to \(\eta\) is free then
6:\(P_{k+1}\leftarrow\) move towards \(\eta\) [Sections 4.3-4.5]
7:\(L\leftarrow\) LiDAR measurements
8:\(\Psi\leftarrow\) empty list
9:else
10:if\(\Psi\) is empty then
11:\(z\leftarrow\eta\) pose index
12:\(\Psi\leftarrow\) PathFinding\((P,k,z))\) [Algorithm A5]
13:endif
14:\(P_{k+1}\leftarrow\) move towards \(\Psi[0]\) [Sections 4.3-4.5]
15:\(L\leftarrow\) LiDAR measurements
16:if\(\Psi[0]\) has been reached then
17: remove \(\Psi[0]\) of the \(\Psi\)
18:endif
19:endif
20:endif```
0: Grid map (\(G\)), LiDAR measurements (\(L\)), Marker list (\(M\))
0: Updated Marker List (\(M\))
1:\(\gamma\leftarrow\) minimum distance between markers
2:for each \(l\) in \(L\)do
3:if\(l\) is outside LiDAR's maximum range then
4:\(x_{l},y_{l}\leftarrow\) coordinates of \(l\)
5:\(\kappa\leftarrow\) true;
6:while\(\kappa\)do
7:for each \(m\) in \(M^{\prime}\)do
8:\(x_{m},y_{m}\leftarrow\) coordinates of \(m\)
9:if\(\sqrt{(x_{l}-x_{m})^{2}+(y_{l}-y_{m})^{2}}<\gamma\)then
10:\(\kappa\leftarrow\) false;
11:endif
12:endfor
13:endwhile
14:if\(\kappa\)then
15:if\(G[x_{l},y_{l}]\) is unknown then
16: add \((x_{l},y_{l})\) to \(M\) as a new marker;
17:else
18:\(\tau\leftarrow\) true;
19:\(N\leftarrow\{(x_{l}+i,y_{l}+j)\mid i,j\in\{-1,0,1\},(i,j)\
eq(0,0)\}\)
20:for each \(n\) in \(N\)do
21:if\(G[n]\) is unknown and \(\tau\)then
22: add \((x_{l},y_{l})\) to \(M\) as a new marker
23:\(\tau\leftarrow\) false;
24:endif
25:endfor
26:endif
27:endif
28:endfor
```

**Algorithm A2** Marker Addition

```
0: Marker list (\(M\)), Robot's current pose (\(P_{k}\))
0: Target marker (\(\eta\))
1:\(M_{f}\leftarrow\) filter markers from \(M\) with free access
2:\(\mu\leftarrow\) navigation balance parameter
3:if\(M_{j}\) is empty then
4:\(M_{t}\leftarrow\) randomly select \(\rho\) markers from \(M\)
5:\(\eta\leftarrow\) marker with the shortest distance in \(M_{t}\)
6:
7:return\(\eta\)
8:endif
9:\(\eta_{c}\leftarrow\) oldest marker in \(M_{f}\)
10:\(\eta_{c}\leftarrow\) closest marker in \(M_{f}\)
11:\(x_{\eta_{c}}\),\(y_{\eta_{c}}\leftarrow\) coordinates of \(P_{k}\)
12:\(x_{\eta_{c}}\),\(y_{\eta_{c}}\leftarrow\) coordinates of \(\eta_{o}\)
13:\(x_{\eta_{c}}\),\(y_{\eta_{c}}\leftarrow\) coordinates of \(\eta_{c}\)
14:\(d_{o}\leftarrow\sqrt{(x_{\eta_{c}}-x_{\eta_{c}})^{2}+(y_{\eta_{c}}-y_{\eta_{c}}) ^{2}}\)
15:\(d_{c}\leftarrow\sqrt{(x_{\eta_{c}}-x_{\eta_{c}})^{2}+(y_{\eta_{c}}-y_{\eta_{c}}) ^{2}}\)
16:if\(d_{o}>\mu\times d_{c}\)then
17:\(\eta\leftarrow\eta_{c}\)
18:else
19:\(\eta\leftarrow\eta_{o}\)
20:endif
```

**Algorithm A3** Marker Selection

```
0:\(\eta\leftarrow\)  
```
0: Grid map (\(G\)), Marker list (\(M\))
0: Updated marker list (\(M^{\prime}\))
1:\(M^{\prime}\leftarrow\) empty list
2:for each \(m\) in \(M\)do
3:\(x_{m},y_{m}\leftarrow\) coordinates of \(m\)
4:if\([x_{m},y_{m}]\) is unknown then
5: add \(m\) to \(M^{\prime}\)
6:else
7:\(\alpha\leftarrow\) true
8:\(N\leftarrow\{(x_{m}+i,y_{m}+j)\mid i,j\in\{-1,0,1\},(i,j)\
eq(0,0)\}\)
9:for each \(n\) in \(N\)do
10:if\(G[n]\) is unknown and \(\alpha\)then
11: add \(m\) to \(M^{\prime}\)
12:\(\alpha\leftarrow\) false
13:endif
14:endfor
15:endif
16:endfor
```
**Algorithm A4** Marker Removal
```
0: Pose list (\(P\)), Robot's pose index (\(k\)), Target marker's pose index (\(z\))
0: Path (\(\mathbf{Y}\))
1:\(\Psi\leftarrow\) empty list
2:\(s\leftarrow\) search step size
3:\(\Omega=\{i\mid i=z+ns,\,n\in\mathbb{Z}^{+}\ \mathbf{e}\ i\leq k\}\)
4:while\(\Omega\) is not empty do
5:\(\tau\leftarrow\) true;
6:for each \(\omega\) in \(\Omega\)do
7:\(obstacle\leftarrow\) check for obstacles between \(P[\omega]\) and \(P[k]\);
8:if without \(obstacle\) and \(\tau\)then
9: add \(P[\omega]\) to \(\Psi\);
10:\(k\leftarrow\omega\);
11:\(\tau\leftarrow\) false;
12:endif
13:endfor
14:\(\Omega=\{i\mid i=z+ns,\,n\in\mathbb{Z}^{+}\ \mathbf{e}\ i\leq k\}\)
15:endwhile
```  
**Algorithm A5** Path finding