# Robots in Partially Known and Unknown Environments:
## 4 AdaptiveRMP Framework
### OfflineRMP  
This planning scenario searches for a feasible path for the robot navigating from the start to the target position in a known environment. A simulated annealing algorithm proposed in [35] is used to solve this problem. In this algorithm, solutions are presented as coordinates representing the sequence of positions the robot must follow from the start to the target. The simulated annealing approach works in the feasible space; hence, solutions that use obstacle positions are not considered. Algorithm 1 shows the main structure of the OfflineRMP algorithm implemented. Table 2 summarizes the main symbols used to describe the algorithm. It lists the SA-related symbols as initial and current temperature and differences in the quality of solutions. It also lists the solution points of the paths being constructed. The SA algorithm implements two main steps: the pre-processing and the search. Before the initial solution is constructed, the empty cells that the robot cannot reach are marked as obstacles using the flood-fill algorithm [36] (line 1). Figure 4 shows the grid obtained after the flood-fill algorithm. Figure 3: AdaptiveRMP components. According to the environment type identified: known, partially known, or unknown; the framework selects the algorithm to use. A greedy-based approach generates initial solutions (line 3). The approach uses a myopic function, a pile of directions, a surrounding strategy, and a pruning strategy. The myopic function detects the possible movements to perform in the next step without violating the constraints defined in Section 3.2. The next step is a selection based on the priorities defined by the pile of directions. The robot follows the direction without obstacles approaching the target cell. When an obstacle is detected, the algorithm selects to surround the obstacle by left or right. After this, the robot follows its path using the same strategy. During the surrounding step, the pile of directions defines the priorities of selecting the next position, considering that, at any point, the robot has a suitable direction. If the robot is going around an obstacle, the suitable direction is the one that guides it closer to \begin{table}
\begin{tabular}{c c} \hline \hline
**Name** & **Description** \\ \hline start & initial point of the path \\ target & final point of the path \\ \(t_{0}\) & initial temperature of simulated annealing \\ \(t\) & current temperature of simulated annealing \\ \(p_{1}\) & initial point of the path to modify \\ \(p_{2}\) & final point of the path to modify \\ \(\Delta\) & difference in quality between current and new paths \\ \hline \hline \end{tabular}
\end{table} 
Table 2: Symbols. Figure 4: Obstacle filling. The flood-fill algorithm fills inaccessible positions inside obstacles. the obstacle. Otherwise, the suitable direction is the one that brings the robot closer to the destination cell. If an obstacle is being surrounded, the positions are searched starting from the suitable direction counterclockwise. Otherwise, the positions are searched from the suitable direction clockwise. Figure 5 shows the surrounding strategy. In this case, it has been chosen to surround the left. Hence, positions are added to the pile, starting with the suitable direction until a feasible position is found. The pile is computed in each step according to the current suitable direction. A pruning strategy is included to discard unfeasible surrounding steps. Once an unfeasible step is detected, a new surrounding strategy is selected. The local search phase (lines 6-18) uses a move to repair the candidate solution (line 8). The route between two randomly selected positions from the current path is replaced by a new sub-path that joins these two positions. If there are no obstacles between these positions, a linear sub-path that joins them is generated. If there are obstacles, for each obstacle, the algorithm decides either to surround it by the left or the right, generating an alternative candidate solution.