## 3 Marker-Assisted Region Scanning
### Update Robot State  
This process continuously updates the robot's state during navigation, determining its new pose and LiDAR measurements based on the current action and the specified target. It plays a role in maintaining the robot's alignment with its goal, dynamically adjusting its trajectory as needed and gathering essential data to support the ongoing mapping of the environment. The algorithm plays a vital role in enabling the robot to adapt its trajectory as needed, allowing for real-time decision making that enhances its ability to navigate complex spaces. ```
Input: \(\mathcal{D}\), \(\mathcal{D}\)


```
0: Grid map of the environment (\(G\))
1:\(G\leftarrow\) unknown map {Grid map with all cells as unknown (gray pixels)}
2:\(P,M,L,\Psi\leftarrow\) empty list {Pose list, marker list, LiDAR measurements and path}
3:\(\eta\leftarrow\) null {Target marker}
4:\(k\gets 0\)
5:\(P_{k}\leftarrow\) initial position
6:while full rotation not completed do
7:\(P_{k+1},L\rightarrow\) UpdateRobotState\((P_{k},\eta,rotate,G,\Psi)\) {Algorithm A1}
8:\(G\rightarrow\) UpdateGridMap\((P_{k+1},L)\) {Section 4.6}
9:\(M\rightarrow\) MarkerAddition\((G,L,M)\) {Algorithm A2}
10:\(k\gets k+1\)
11:endwhile
12:while\(M\
eq\) empty list do
13:if\(\eta\) is null then
14:\(\eta\rightarrow\) MarkerSelection\((M)\) {Algorithm A3}
15:endif
16:\(P_{k+1},L\rightarrow\) UpdateRobotState\((P_{k},\eta,towards,G,\Psi)\)
17:\(G\rightarrow\) UpdateGridMap\((P_{k+1},L)\)
18:if\(\eta\) has been reached then
19:\(\eta\leftarrow\) null;
20:endif
21:\(M\rightarrow\) MarkerRemoval\((G,M)\) {Algorithm A4}
22:\(M\rightarrow\) MarkerAddition\((G,L,M)\)
23:\(k\gets k+1\)
24:endwhile
```
**Algorithm 1** Marker-Assisted Region Scanning

### Marker Addition

Markers are created based on readings from the LiDAR, a sensor used by the robot to scan the environment. Each measurement provides the distance to the first obstacle detected along that direction. The LiDAR has a maximum range, beyond which the measurements are not considered. During the robot's movement, at each registered pose, all LiDAR measurements are analyzed to identify potential obstacle-free areas. To ensure that markers are efficiently distributed without redundancy, the algorithm imposes a restriction: a new marker can only be added if no other marker exists within a predetermined minimum distance. This criterion is enforced by calculating the Euclidean distance between the new marker and all previously placed markers, ensuring proper spacing and preventing unnecessary overlap. Figure 2 illustrates the process of identifying free areas and adding markers. Figure 2: Process of identifying free areas and adding markers during the robot’s navigation. (**a**) shows how free areas are identified based on LiDAR readings, where the red line represents the detected free area; (**b**) illustrates the addition of markers in these areas, represented by red dots, ensuring a minimum distance between them. Algorithm A2 takes the grid map (\(G\)), LiDAR measurements (\(L\)), and the existing marker list (\(M\)) as input. It checks whether a new marker can be placed by verifying if the corresponding area is still unknown (represented by a gray pixel) and if it satisfies the minimum distance requirement \(\gamma\). If both conditions are met, a new marker is added. If a marker already exists nearby, the algorithm examines neighboring cells for unexplored areas before placing a new marker. Figure 2 illustrates this process. ### Marker Selection

After the initial navigation period, the robot needs to choose a marker as a target to map an unexplored area. For this selection, the robot identifies markers that have free access, meaning it is possible to plot a direct path from the robot's current position to the marker without encountering obstacles. Once the markers with free access are identified, the robot uses two criteria to select the target marker: age and distance. Each marker is associated with a specific pose, recorded in a pose list starting from pose 0 up to the robot's current pose.