# Autonomous Navigation Framework for Intelligent Robots Based on a Semantic Environment Modeling
## 4 Experiments
### Experimental Results
#### 4.3.1 Behavior Planner  
One of the key hyper-parameters of the PRM algorithm is the number of nodes \(n\). We conducted experiments aiming to show the influence of this value on the algorithm performance. Initially, four differently sized places were selected, as shown in Table 6. Using each of the places' grid map, we calculated the map total area by multiplying the map's height by the map's width in meters. To calculate the _free space ratio_ value, we divided the amount of pixels representing a free space on the map image by the total amount of pixels. Finally, we multiplied the free space ratio by the total map area to generate the _free space area_.  
We chose a set of the number of samples \(\{50,100,200,300,400,500\}\) heuristically, and ran our PRM algorithm 50 times for each \(n\) value on each map. The most important performance information for our application was the time taken to build the PRM graph, the time taken to find the optimal path, the length of the final path, and whether or not the algorithm was able to find a path between \(\mathcal{N}_{p}\) and \(\mathcal{N}_{g}\). The average values for each of those measurements are shown in Figure 13. While the time taken to build the PRM graph grew quadratically with the number of samples, the time taken to  
\begin{table}
\begin{tabular}{c c c c} \hline \hline
**Place Name** & **Place Total Mapped Area (m2)** & **Free Space Ratio** & **Free Space Area (m2)** \\ \hline floor1 & 39,759.4 & 0.123 & 4890.41 \\ corridor1 & 13,632.0 & 0.258 & 3517.06 \\ corridor2 & 4672.0 & 0.391 & 1826.75 \\ corridor3 & 3124.0 & 0.271 & 846.60 \\ \hline \hline \end{tabular}
\end{table}
Table 6: Map information.  
find the optimal path only grew linearly. As our approach generated the graph only when receiving a new map, the effect of building the PRM graph can be mitigated. Smaller places showed higher times for both, graph building and path finding, when using the same amount of samples as larger places, because it became progressively harder for the algorithm to find free spaces when the map was nearly filled with samples. In addition, graphs with a high density of nodes per square meter tended to have a higher variety of possible paths, which could slow down the path search.  
Additionally, we were able to show that the number of samples barely influenced the final path length. However, it had a considerable influence on the ability to find a valid path. When the amount of nodes was too small while comparing to the map size, some nodes could not find valid neighbors, which led to disconnected graphs. This situation is not desirable when performing a mission, as it would require the robot to re-generate the PRM graph whenever encountering such an issue. This can lead to unexpected delays and even dead-locks.  
Aiming to select an optimal number of nodes based on the free space information, we performed a linear regression while trying to minimize \(n\) with two constraints: the path search time should take no more than 15 ms; the success rate should be above 90%. We obtained the following coefficients:  
\[NumberOfSamples=ceil(0.057*FreeSpaceArea+30), \tag{1}\]  
where _ceil_ represents the rounding up operation. By using Equation (1), the number of samples needed by each one of the aforementioned maps is displayed in Table 7. We ran the algorithm 50 more times, this time using the optimal \(n\) values. It has been shown that by using the proposed formula, both constraints were satisfied.  
Figure 13: Influence of the number of samples (x-axis) on the PRM algorithm.