# Topological Map-Based Autonomous Exploration in Large-Scale Scenes for Unmanned Vehicles
## 3 Methods
### Local Path Planning  
The global path planning module aims to assist the robot in making decisions at a global standpoint for efficient exploration. The local path planning module aims to find the best viewpoints to make the robot to follow. Many previous works refine a path by evaluating the cost and reward for efficient exploration, but they consume significant computational resources in information evaluation [1,30]. Thus, we define the potential reward of a candidate viewpoint as a volume of unknown space within its a Field of View  
Figure 5: Determination of the second category of frontier clusters. (**a**) Determine whether the second-category frontier \(f^{k}\) guides the robot towards the global target based on angle and distance conditions. (**b**) Robot moves towards other scenes following the generated exploration path. (**c**) As the robot moves, \(f^{k}\) no longer meets the initial judgment criteria. (**d**) To maintain the consistency of the previous judgment to \(f^{k}\), perform a secondary judgment of \(f^{k}\) by DTW.  
(FoV) and propose a simple and fast reward evaluation method based on incremental frontier information structure (FIS). Finally, the local path is refined by synthesizing the reward and movement cost of each viewpoint candidate.  
Cells of a frontier cluster are stored in FIS [12]. We use them to evaluate the volume of unknown space in FOV. As shown in Figure 6, each truncated pyramid is constructed based on cells that the candidate viewpoint could cover, and its volume is calculated as follows:  
\[V=\left(h_{rw}\Big{(}\frac{h_{rw}e_{cell}}{h_{cell}}\Big{)}^{2}-h_{cell}(e_{ cell})^{2}\right)/3, \tag{12}\]  
where \(e_{cell}\) is width of cell, \(h_{cell}\) is distance between cell and candidate viewpoint. \(h_{rw}\) is effective distance to calculate reward and computed by:  
\[h_{rw}=\min(h_{\max},h_{cell}+\delta), \tag{13}\]  
\(h_{max}\) is maximum range of FOV, and \(\delta\) is used to control the depth of truncated pyramid to balance movement cost and expected rewards.  
The expected reward \(rw_{i}^{k}\) of a candidate viewpoint \(vp_{i}^{k}\) is evaluated by accumulating \(V\):  
\[rw_{i}^{k}=\sum_{x=1}^{n}V_{x}^{k}+\eta\sum_{y=1}^{m}V_{y}^{l}, \tag{14}\]  
where \(V_{x}^{k}\) is taken from current frontier cluster \(f^{k}\), and \(V_{y}^{l}\) is taken from next adjacent frontier cluster \(f^{l}\) to be visited. \(m\) and \(n\), respectively, represent the number of cells that \(vp_{i}^{k}\) could cover. \(\eta\) is a weight coefficient.  
We formulate local path planning as a graph search problem and refine an optimal path from the global exploration path by balancing expected reward and movement cost, where viewpoints of each frontier cluster serve as candidate points. Suppose that the optimal exploration path \(path=\{vp_{1}^{1},vp_{k}^{2},\dots,vp_{j}^{N_{rf}},vp_{1}^{N_{rf}+1}\}\) provided by the [PERSON] algorithm will minimize the cost/reward ratio:  
\[c\Big{(}P_{R,  
where \(N_{rf}+1\) is the size of the frontier clusters to be optimized, and  
\[W_{k}^{n}=\frac{rw_{k}^{n}}{V_{FOV}}, \tag{16}\]  
\(V_{FOV}\) is the volume of FOV.  
Finally, the exploration path \(path\) is output to the trajectory generation module.