## 3 Our Approach
### Exploration Graph  
The observed information changes incrementally during the exploration progress, leading to the increasing dimension of state and action spaces. Compared with learning from occupancy map or sensor data, the graph offers a smaller state space, a more generalized representation of a SLAM-dependent mobile robot's environment [4]. Moreover, the graph-learning approach is more adaptable to dynamic environments, in which the input is variable-size graphs, and the size of the output data adjusts to the number of nodes of the input graph.  
For these reasons, we represent the graph topology of the exploration problem and model the exploration process as a generalized exploration graph, as shown in Figure 2. We denote the exploration graph as \(\mathcal{G}=(\mathcal{V},\mathcal{E})\), where \(\mathcal{V}\) represents the set of nodes and \(\mathcal{E}\) the set of edges.  
There are four types of nodes in \(\mathcal{V}\): historical trajectories (red), frontier waypoints (blue), landmarks (yellow), and obstacles (black), where the obstacle node is firstly introduced in this paper, and the frontier waypoint nodes are performed as the candidate points. The edges \(\mathcal{E}\) between the nodes are constructed as follows: (i) adjacent trajectory nodes are connected to each other, (ii) each trajectory is connected to the nearest landmark, (iii) each frontier waypoint is connected to the nearest landmark or the current position of the robot, (iv) the landmarks are fully connected, (v) each obstacle is connected to the nearest trajectory. After establishing the exploration graph, the robot can obtain the local target point to guide the exploration of unknown areas from candidates by network reasoning about the information on the graph.  
As a start point of node feature aggregation, we initialize the node feature as:  
\[\mathbf{x}_{i}=[d,\varphi,H_{\gamma},H_{\beta},\phi], \tag{4}\]  
where \(d\) is the distance of the node and the current position of robot, \(\varphi\) the angle between the heading of robot and direction from the robot to the node, \(H_{\gamma}\) the Shannon entropy,  
Figure 2: Extracting the exploration graph. The historical trajectories, frontier waypoints, landmarks, and obstacles are shown in red, blue, yellow, and black, respectively. The current position in trajectories is stressed with the yellow border, and the frontier waypoints are served as the candidate target points.  
the Renyi entropy, \(\phi\) the flag. The correspondence between flag \(\phi\) and nodes are shown in Table 1.  
The Shannon entropy and Renyi entropy [15] are used to measure the grid uncertainty and the pose uncertainty, respectively. The Shannon entropy is defined as:  
\[H_{\gamma}\approx-\sum_{ij}(P(m_{ij})\log(P(m_{ij}))+(1-P(m_{ij}))\log(1-P(m_{ ij}))), \tag{5}\]  
where \(m_{ij}\) is the Bernoulli random variable. \(m_{ij}=0\) indicates that the grid is free, and \(m_{ij}=1\) means grid occupied. \(P(m_{ij}=1)\) is the probability of grid being occupied, which is abbreviated as \(P(m_{ij})\). The Renyi entropy is defined as:  
\[\begin{split} H_{\beta}&=\frac{1}{1-\beta}\log_{2 }(\sum_{i=1}^{n}{P_{i}}^{\beta})\\ &=\frac{1}{1-\beta}\log_{2}(P(m_{ij})^{\beta}+(1-P(m_{ij}))^{ \beta}),\end{split} \tag{6}\]  
where \(\beta=1+\frac{1}{tr(\Sigma_{g_{ij}})}\), in which \(\Sigma_{g_{ij}}\) denotes the error covariance matrix of the grid \(g_{ij}\) and \(P_{i}\) the probability associated with the random variable \(m_{ij}\).  
Then, we use a multi-layer perceptron (MLP) [27, 28] to map the initial feature into a high dimensional vector as the input of the following network.  
\[\mathbf{F}=\text{MLP}(\mathbf{X}), \tag{7}\]  
where \(\mathbf{X}=[\mathbf{x}_{1},\cdots,\mathbf{x}_{N}]^{\mathsf{T}}\), \(\text{MLP}(\cdot)\) is a multi-layer perceptron, and \(N\) the number of the nodes.