# Topological Map-Based Autonomous Exploration in Large-Scale Scenes for Unmanned Vehicles
## 3 Methods
### PCATSP-Based Global Path Planning  
PCATSP is a variation of the classic Traveling Salesman Problem (TSP), which aims to find a minimum-cost Hamiltonian circuit, with the constraint that some nodes must be visited before others. If splitting the start and end points of PCATSP into two nodes, PCATSP is equivalent to finding a path between the start and end points that satisfy priority constraints, which is also considered a Sequential Ordering Problem (SOP) [25]. To address Objective 3, our basic idea of global path planning is to solve PCATSP with frontiers and priority-constrained global targets. It is equivalent to inserting frontiers into a sequential queue of global targets, utilizing the global targets to influence the covered sequence of some frontier clusters. However, the construction of PCATSP faces the following challenges: First, constrained by the perception range of sensor and obstacle obstruction, the robot cannot accurately calculate the movement distance between global targets in unknown space and viewpoints inside the free space. Second, for TSP, the farther the metric distance between frontier cluster and global target, the less influence the global target can exert. So, we need to enable global targets to influence specific frontier clusters. To address the above challenges, we define the following: if a global target \(s_{i}\) is inside the free space, and the other global target \(s_{j}\) connected to \(s_{i}\) is in unknown space, then  
Figure 1: The overview of the proposed exploration method. the shortest path \(P_{p_{k},s_{j}}\) between any node \(p_{k}\) in free space and global target \(s_{j}\) in unknown space is given by  
\[P_{p_{k},s_{j}}=P_{p_{k},a}+P_{a,s_{j}}, \tag{1}\]  
where \(a\) is an intersection point of frontier and undirected edge \(e_{k}\) that connects \(s_{i}\) and \(s_{j}\), as shown in Figure 2a. \(P_{a,s_{j}}\) is a portion of \(e_{k}\) in unknown space, and \(P_{p_{k},a}\) is a search path from \(p_{k}\) to \(a\). Based on the above definition and by incorporating the solving property of TSP, if all elements in a certain row or column of cost matrix \(D\) of TSP are subtracted by the same value, a new cost matrix \(D^{*}\) for the TSP will be obtained. However, \(D\) and \(D^{*}\) correspond to the same TSP solution [26]. Thus, we can subtract \(P_{a,s_{j}}\) from all \(P_{p,s_{j}}\), and leave the TSP solution unchanged. It is equivalent to setting an agent point for the global target on the frontier. For constructing PCATSP, the intersection point \(a^{j}\) could be extracted on a frontier cluster as an agent for global target \(s_{j}\) and the priority can be set to \(a^{j}\) based on global exploration strategy \(O\). Hence, based on the above theory, we define agent \(a^{j}\) as the intersection point of a frontier cluster \(f^{k}\) and an undirected edge \(e_{k}=(s_{i},s_{j})\), which is associated with a global target \(s_{j}\) in unknown space and possesses access priority. Then, the path between any point inside free space and an agent on frontier could be found by a path-searching algorithm, and then path length could also be accurately calculated. The method of agent extraction and priority assignment will be elaborated in Section 3.2. Finally, we can naturally combine the prior topological map with real-time updated scene information in path planning based on PCATSP. We can then solve the PCATSP with the extracted agent set \(A=\{a^{i},a^{j},\dots,a^{l}\}\) and frontier cluster set \(F\), where agents with priority will influence the visited order of nearby frontier clusters. In this section, we suppose that the movement cost \(c\left(p_{i},p_{j}\right)\) between any two nodes \(p_{i}\) and \(p_{j}\) is calculated as follows:  
\[c\left(p_{i},p_{j}\right)=\frac{L\left(P_{p_{i},p_{j}}\right)}{v_{\max}}, \tag{2}\]  
where \(P_{p_{i},p_{j}}\) is the shortest search path between nodes \(p_{i}\) and \(p_{j}\); \(L()\) denotes the length of search path; and \(v_{max}\) is the maximum velocity of the robot.