Complete Coverage Path Planning in an Unknown Underwater Environment Based on D-S Data Fusion Real-Time Map Building

Abstract

A real-time map-building system is proposed for an autonomous underwater vehicle (AUV) to build a map of an unknown underwater environment. The system, using the AUV's onboard sensor information, includes a neurodynamics model proposed for complete coverage path planning and an evidence theoretic method proposed for map building. The complete coverage of the environment guarantees that the AUV can acquire adequate environment information. The evidence theory is used to handle the noise and uncertainty of the sensor data. The AUV dynamically plans its path with obstacle avoidance through the landscape of neural activity. Concurrently, real-time sensor data are “fused” into a two-dimensional (2D) occupancy grid map of the environment using evidence inference rule based on the Dempster-Shafer theory. Simulation results show a good quality of map-building capabilities and path-planning behaviors of the AUV.

1. Introduction

Autonomous underwater vehicle (AUV) is an unmanned underwater robot widely used in underwater environments to accomplish underwater missions, such as pipeline tracking, large-scale underwater exploration, and seafloor search for wrecks. It is important to build and maintain a map of an AUV's working environment for the purpose of navigation and obstacle avoidance. Path planning is usually based on a map and in turn serves dynamic map building especially in an unknown environment.

Complete coverage path planning which requires a robot to pass through every space of the workspace is an essential ability for the robot to perform missions. Complete coverage navigation of mobile robots has been extensively studied [1–5]. For instance, Liang et al. [3], and Yang and Luo [4] proposed complete coverage path planning approaches with obstacle avoidance for cleaning robots, and Zhang et al. [5] addressed on the path planning and tracking for agricultural master-slave robot system. In recent years, some studies on path planning of underwater vehicles have been reported [6–9]. An information gain approach was introduced to adaptive path planning for an AUV equipped with a sidescan sonar to achieve complete coverage of an area [8]. Neurodynamics was firstly applied to complete coverage of a completely unknown underwater environment for an AUV [9].

Autonomous robot requires map information from its onboard sensors to plan its path, especially in an unknown environment. Luo and Yang [10] used onboard sensor information for concurrent map building and complete coverage navigation of cleaning robot in unknown indoor environments. The environment information obtained by the robot's onboard sensors was assumed to be accurate. In practice, the origin measurements of sensors, such as sonar, and so forth, may be inaccurate for the noise and uncertainty in the sensor data. The inherent uncertainty in the sensory information requires a probabilistic approach to processing or fusing the information to build an accurate map. Uncertainty calculi techniques have been addressed by researchers [11–16]. Most of the techniques applied for map building are based on the Bayesian theory, the fuzzy set theory, and the Dempster-Shafer theory of evidence.

This paper focuses on building a map of an unknown underwater environment for an AUV, using the AUV's on board sensor information only. A complete coverage path planning of AUV by using a neurodynamics model is proposed for the real-time map-building system. The dynamically changing landscape of the neural activity of the neurodynamics model guarantees that the AUV can find a collision-free path to completely cover the accessible workspace. The path planning makes the AUV thoroughly detect the whole workspace to acquire adequate environment information for map building. In addition, the Dempster-Shafer theory of evidence is used to process the uncertainty of the sensor information and the misinformation from moving obstacles in the environment.

The rest of this paper is organized as follows. Section 2 presents the neurodynamics model for the complete coverage path planning. In Section 3, a sonar sensor model is built, and the Dempster-Shafer theory is used to handle the noise and uncertainty of the sensor information for map building. Section 4 presents the simulation results of map building based on complete coverage path planning in an unknown underwater environment. Finally, conclusions are outlined in Section 5.

2. The Neurodynamics Model for Complete Coverage Path Planning

2.1. The Neurodynamics Model

The proposed neurodynamics model is derived from a computational model of a biological neural system proposed by Yang and Luo [4, 10]. As Figure 1 shows, the proposed neural network is expressed topologically on a 2-demensional occupancy grid map. The location of the kth neuron of the neural network represents a location (cell) in the map. Each neuron has local lateral connections to its neighboring neurons in a small region $[\mathrm{0},r_{\mathrm{0}}]$ where $r_{\mathrm{0}}$ is the receptive field radius of the kth neuron, as shown in Figure 1(b). The excitatory input results from uncovered area and lateral neural connections, while the inhibitory input results from obstacles. The dynamics of the kth neuron in the neural network is characterized by

$$\begin{array}{l}\frac{d{x}_k}{dt}=-A{x}_k+\left(B-x_k\right)\left({\left[I_k\right]}^{+}+\sum _{l=\mathrm{1}}^m{w}_{kl}{\left[x_l\right]}^{+}\right)\\ \hspace{1em}\hspace{1em}-\left(D+x_k\right){\left[I_k\right]}^{-},\end{array}$$

(1)

where $x_k$ is the neural activity of the kth neuron in the neural network; A, B, and D are nonnegative constants describing the passive decay rate, and the upper and lower bounds of the neural activity, respectively; the terms ${[I_k]}^{+}+{\sum }_{l=\mathrm{1}}^m{w}_{kl}{[x_l]}^{+}$ and $[I_k{]}^{-}$ are the excitatory and inhibitory inputs to the kth neuron, respectively. Function $[a{]}^{+}$ is a linear-above-threshold function defined as $[a{]}^{+}=\max \hspace{0.17em}\{a,\mathrm{0}\}$ , and function $[a{]}^{-}$ is defined as $[a{]}^{-}=\max \hspace{0.17em}\{-a,\mathrm{0}\}$ . The connection weight $w_{kl}$ from the kth neuron to the lth neuron is given by $w_{kl}=f(|q_k-q_l|)$ , where $|q_k-q_l|$ represents the Euclidean distance between vectors $q_k$ and $q_l$ in the state space, and $f(d)$ is a monotonically decreasing function defined as

$$\begin{array}{cc}& f\left(d\right)=\{\begin{array}{cc}\mu /d,\hfill & \mathrm{0}\le d<r_{\mathrm{0}},\hfill \\ \mathrm{0},\hfill & d\ge r_{\mathrm{0}},\hfill \end{array}\end{array}$$

(2)

where μ and $r_{\mathrm{0}}$ are positive constants. The external input $I_k$ to the kth neuron is defined as

$$\begin{array}{cc}& I_k=\{\begin{array}{cc}E,\hfill & \text{if\hspace{0.17em}it\hspace{0.17em}is\hspace{0.17em}an\hspace{0.17em}uncovered\hspace{0.17em}area,}\hfill \\ -E,\hfill & \text{if\hspace{0.17em}it\hspace{0.17em}is\hspace{0.17em}an\hspace{0.17em}obstacle\hspace{0.17em}area,}\hfill \\ \mathrm{0},\hfill & \text{if\hspace{0.17em}it\hspace{0.17em}is\hspace{0.17em}a\hspace{0.17em}covered\hspace{0.17em}area,}\hfill \end{array}\end{array}$$

(3)

where E is a large positive constant.

Figure 1

The architecture of the neurodynamics model.

The environment is represented by a 2D occupancy grid map, as Figure 1(a) shows. Each grid element of the map corresponds to a specific square on the surface of the actual environment, respectively. A neurodynamics model (see Figure 1(b)) is topologically built on the map. A neural activity landscape of the model is shown in Figure 1(c). The neural activities of obstacles are represented by using valley in the activity landscape of the neural network because of their negative values, while the neural activities of uncovered areas stay high in the neural activity landscape because of positive excitations. The activity landscape dynamically changes due to the internal activity propagations among neurons, the varying excitatory inputs from the uncovered areas, and the inhibitory inputs from obstacles. Equation (1) guarantees that the positive neural activity can propagate to all the network through lateral connections among neurons, but the negative activity only stays locally.

2.2. The Complete Coverage Path Planning Algorithm

The AUV plans its path from the changing activity landscape of the neurodynamics model. The uncovered areas and the obstacle areas keep staying at the peak and the valley of the activity landscape of the neural network, respectively. Uncovered areas globally attract the AUV through positive neural activity, while obstacles locally push it away to avoid collision through negative neural activity. The AUV keeps moving autonomously towards an uncovered area with obstacle avoidance until the designated objective is achieved.

For power and time limitation, the AUV should travel the path with the least revisited areas and the least turns of moving directions. Therefore, for a given current AUV location, denoted by $p_c$ , the next AUV location $p_n$ is obtained by [4]

$$\begin{array}{cc}& p_n⟸x_{p_n}=\max \hspace{0.17em}\left\{x_l+c{y}_l,l=\mathrm{1,2},\dots ,m\right\},\end{array}$$

(4)

where c is a positive constant and m is the number of neighboring neurons of the $p_c$ th neuron, that is, all the possible next locations of the current location $p_c$ ; variable $x_l$ is the neural activity of the lth neuron, the same as that in (1); $y_l$ is a monotonically increasing function of the difference between the current to next AUV moving directions, which is defined as a function of the previous location $p_p$ , the current location $p_c$ , and the possible next location $p_l$ , for example, a function defined as

$$\begin{array}{cc}& y_l=\mathrm{1}-\frac{\mathrm{\Delta }{\psi }_l}{\pi },\end{array}$$

(5)

where $\mathrm{\Delta }{\psi }_l\in [\mathrm{0},\pi ]$ is the turning angle between the current moving direction and the next moving direction, for example, if the AUV goes straight, $\mathrm{\Delta }{\psi }_l=\mathrm{0}$ ; if it goes backward, $\mathrm{\Delta }{\psi }_l=\pi$ . Thus, $\mathrm{\Delta }{\psi }_l$ can be given as $\mathrm{\Delta }{\psi }_l={\psi }_l-{\psi }_c=|a\tan \hspace{0.17em}\mathrm{2}(y_{p_l}-y_{p_c},x_{p_l}-x_{p_c})-a\tan \hspace{0.17em}\mathrm{2}(y_{p_c}-y_{p_p},x_{p_c}-x_{p_p})|$ . After the current location reaches its next location, the next location becomes a new current location (if the selected next location is the same as the current location, the AUV stays there without any movement). The current AUV location adaptively changes according to the varying landscape of the neural activity.

The AUV path planned by (4) may cause overlapping problem in the vicinity of some unstructured obstacles. Therefore, three templates are defined to reduce the overlapping paths [9], as shown in Figures 2(a), 2(b), and 2(c). The central neuron C presents the current location of the AUV, and neuron P presents the previous location. In this paper, one template is supplemented to optimize the path, as shown in Figure 2(d). The templates are defined in Figure 2 and Algorithm 1.

Algorithm 1

Template 1 (as shown in Figure 2(a)).

if (obstacles are in front of the AUV) then

 if (the location of neuron 6 is uncovered) then

  {neuron 6 becomes next central neuron}

  if (the location of neuron 7 is uncovered) then

    {neuron 7 becomes next central neuron}

  end if

 end if

end if

Template 2 (as shown in Figure 2(b)).

if (obstacles are bottom left to the AUV) then

 if (the AUV moves upward) then

  if (the location of neuron 2 is uncovered) then

   {neuron 2 becomes next central neuron}

  end if

 end if

end if

Template 3 (as shown in Figure 2(c)).

if (obstacles are top left to the AUV) then

 if (the AUV moves downward) then

  if (the location of neuron 2 is uncovered) then

   {neuron 2 becomes next central neuron}

  end if

 end if

end if

Template 4 (as shown in Figure 2(d)).

if (obstacles are bottom right to the AUV) then

 if (the AUV moves left) then

  if (the location of neuron 8 is uncovered) then

   {neuron 8 becomes next central neuron}

  end if

 end if

end if

Figure 2

The four predefined templates.

The predefined templates are effective to deal with the vicinity situation of unstructured obstacles and enable the AUV to plan a more reasonable path with less overlapping areas.

2.3. Complete Coverage Path Planning in a Known Environment

The complete coverage path planning is firstly performed in a known environment. The map of the environment is shown in Figure 3(a). The AUV starts its mission from location (1, 1) in the map. The landscape of the neural activity is shown in Figure 3(b). The neural activity in the uncovered areas attains at the peak because of the external input $+E$ , the activity in the obstacle areas stays in the valley because the input $-E$ is negative. The AUV chooses its path due to (4) and the predefined templates. When an area is covered, the excitatory input is set as 0, and then the activity in the area descends. The activity in the uncovered areas remains high in the landscape attracting the AUV to cover the areas, as shown in Figure 3(d).

Figure 3

The complete coverage path planning in a known environment.

In the vicinity of unstructured obstacles, such as a U-shaped obstacle in the map shown in Figure 3(a), the path is optimized to be less overlapping coverage using the predefined templates. When the AUV moves from location (3, 1) to (3, 2) with obstacle 2 blocking its path (see Figure 3(c)), it turns right to location (4, 2) according to Template 1 (see Algorithm 1). When the AUV moves from location (9, 5) to (9, 6), it turns left due to Template 2 (see Algorithm 1). When the AUV moves from right to location (6, 6), it turns down to location (6, 5) using Template 4 (see Algorithm 1). The final result shows that there are no overlapping areas in the vicinity of obstacle 2 (see Figure 3(c)).

3. Sensor Model and Map Building

An underwater environment is represented by a two-dimensional (2D) occupancy grid map. Each cell of the map, corresponding to a specific square location in the environment, may have one of the 3 states: unknown, empty, and occupied which show the certainty that there is an obstacle there. The goal of the map-building system is to process the real-time sensor data as accurately as possible, to decide which cells are occupied by obstacles and which cells are empty, and to update the map during complete coverage navigation. In this section, a sonar model is built for the map-building system, and the Dempster-Shafer theory of evaluating the sensor confidence is used to filter out the inherent uncertainties of the sensor.

3.1. Sensor Model

Map building using sonar sensors has been addressed by some researchers [12–14]. The sensor provides relative distances and bearings between them and surrounding obstacles located within the sensor beam. The sensing process is affected by a large amount of uncertainty because the sensor is prone to several measuring errors due to various phenomena such as multiple reflections, wide radiation beam, and low angular resolution. A profile sonar model which is a function of the angle and the sonar range reading is built for map building [14], as shown in Figure 4. A single reading provides the information that one or more obstacles are located somewhere along the arc of circumference of the radius R, which is the range response from the sonar. $(r,\theta )$ is the coordinate of a point inside the sonar beam. d is the range error distributing the evidence in Region I. α is the half open beam width. There is evidence that cells located in the proximity may be occupied. On the other hand, cells inside the circular sector of radius are likely to be empty. This knowledge is modeled by the Dempster-Shafer theory discussed below.

Figure 4

The profile of the sonar model.

3.2. The Dempster-Shafer Theory of Evidence

The theory of evidence defines a frame of discernment $\mathrm{\Theta }$ which is a set of labels representing mutually exhaustive events. The labels for map building are defined as $\mathrm{\Theta }=\{E,O\}$ , where E, O, and $\{E,O\}$ correspond to the possibilities that a grid cell (a location in a map) is empty, occupied, or unknown, respectively. The set of all subsets of $\mathrm{\Theta }$ is the power set

$$\begin{array}{cc}& \mathrm{\Lambda }={\mathrm{2}}^{\mathrm{\Theta }}=\left\{\mathrm{\Phi },E,O,\left\{E,O\right\}\right\}.\end{array}$$

(6)

The state of each cell is described by assigning basic probability values to each label in $\mathrm{\Lambda }$ . For each cell $(i,j)$ in the grid,

$$\begin{array}{cc}& m_{i,j}\left(\mathrm{\Phi }\right)=\mathrm{0},\end{array}$$

(7)

$$\begin{array}{l}{m}_{i,j}\left(A\right)=\sum _{A\subset \mathrm{\Psi }}{m}_{i,j}\left(\mathrm{\Phi }\right)+m_{i,j}\left(E\right)+m_{i,j}\left(O\right)+m_{i,j}\left(\left\{E,O\right\}\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}=\mathrm{1}.\end{array}$$

(8)

Due to (7) and assuming that $m_{i,j}(\mathrm{\Phi })=\mathrm{0}$ , the number of states can be reduced to two $(m_{i,j}(E),m_{i,j}(O))$ . Each cell $(i,j)$ in the gird map is first initialized as

$$\begin{array}{cc}& m_{i,j}\left(E\right)=m_{i,j}\left(O\right)=\mathrm{0},\hspace{1em}\hspace{1em}{m}_{i,j}\left(\left\{E,O\right\}\right)=\mathrm{1},\end{array}$$

(9)

representing total ignorance about the state of each cell. If the AUV is sure about the cell occupancy, then $m_{i,j}(O)=\mathrm{1}$ . Similarly, when the AUV is sure that a cell is empty, then $m_{i,j}(E)=\mathrm{1}$ .

The evidence is obtained by projecting the raw sensor responses onto the evidence grid through the sonar profile model in Figure 4. The model converts the range information into probability values by (10), (11).

•  

In region I, where $R-d<r<R+d$ :

$$\begin{array}{cc}& m\left(O\right)=\frac{{\left(\begin{array}{c}\alpha -\left|\theta \right|\\ \alpha \end{array}\right)}^{\mathrm{2}}+{\left(\begin{array}{c}d-\left|R-r\right|\\ d\end{array}\right)}^{\mathrm{2}}}{\mathrm{2}},\\ m\left(E\right)=\mathrm{0},\\ m\left(\left\{O,E\right\}\right)=\mathrm{1}-m\left(O\right).\end{array}$$

(10)

 

In region II, where $R_{\min \hspace{0.17em}}\le r\le R-d$ :

$$\begin{array}{cc}& m\left(O\right)=\mathrm{0},\\ m\left(E\right)=\frac{{\left(\begin{array}{c}\alpha -\left|\theta \right|\\ \alpha \end{array}\right)}^{\mathrm{2}}+{\left(\begin{array}{c}R-r-d\\ R-d\end{array}\right)}^{\mathrm{2}}}{\mathrm{2}},\\ m\left(\left\{O,E\right\}\right)=\mathrm{1}-m\left(E\right).\end{array}$$

(11)

3.3. The Fusion of Sensor Data

For a certain event A, $m_{i,j}^{t-\mathrm{1}}(A)$ is the previous basic probability assignment for the cell $(i,j)$ confidence, and $s_{i,j}^t(A)$ is the current probability assignment from sensor reading. For the events O, E, and $\{O,E\}$ , the cell confidence in the map is updated using the Dempster's rule of combination, respectively.

$$\begin{array}{l}\hspace{1em}\hspace{1em}\hspace{1em}{m}_{i,j}^t\left(O\right)=m_{i,j}^{t-\mathrm{1}}\left(O\right)\oplus S_{i,j}^t\left(O\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}=\frac{m_{i,j}^{t-\mathrm{1}}\left(O\right)S_{i,j}^t\left(O\right)+m_{i,j}^{t-\mathrm{1}}\left(O\right)\left(\mathrm{1}-S_{i,j}^t\left(E\right)-S_{i,j}^t\left(O\right)\right)}{\mathrm{1}-m_{i,j}^{t-\mathrm{1}}\left(E\right)S_{i,j}^t\left(O\right)-m_{i,j}^{t-\mathrm{1}}\left(O\right)S_{i,j}^t\left(E\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+\frac{\left(\mathrm{1}-m_{i,j}^{t-\mathrm{1}}\left(E\right)-m_{i,j}^{t-\mathrm{1}}\left(O\right)\right)S_{i,j}^t\left(O\right)}{\mathrm{1}-m_{i,j}^{t-\mathrm{1}}\left(E\right)S_{i,j}^t\left(O\right)-m_{i,j}^{t-\mathrm{1}}\left(O\right)S_{i,j}^t\left(E\right)},\\ m_{i,j}^t\left(E\right)=m_{i,j}^{t-\mathrm{1}}\left(E\right)\oplus S_{i,j}^t\left(E\right)\\ \hspace{1em}\hspace{1em}\hspace{1em}=\frac{m_{i,j}^{t-\mathrm{1}}\left(E\right)S_{i,j}^t\left(E\right)+m_{i,j}^{t-\mathrm{1}}\left(E\right)\left(\mathrm{1}-S_{i,j}^t\left(E\right)-S_{i,j}^t\left(O\right)\right)}{\mathrm{1}-m_{i,j}^{t-\mathrm{1}}\left(E\right)S_{i,j}^t\left(O\right)-m_{i,j}^{t-\mathrm{1}}\left(O\right)S_{i,j}^t\left(E\right)}\\ \hspace{1em}\hspace{1em}\hspace{1em}\hspace{0.17em}+\frac{\left(\mathrm{1}-m_{i,j}^{t-\mathrm{1}}\left(E\right)-m_{i,j}^{t-\mathrm{1}}\left(O\right)\right)S_{i,j}^t\left(E\right)}{\mathrm{1}-m_{i,j}^{t-\mathrm{1}}\left(E\right)S_{i,j}^t\left(O\right)-m_{i,j}^{t-\mathrm{1}}\left(O\right)S_{i,j}^t\left(E\right)},\\ \hspace{1em}\hspace{1em}\hspace{1em}{m}_{i,j}^t\left(\left\{O,E\right\}\right)=\mathrm{1}-m_{i,j}^t\left(O\right)-m_{i,j}^t\left(E\right).\end{array}$$

(12)

The sonar responses interpreted by the Dempster-Shafer theory of evidence are collected and updated into the map using the same theory. The basic probability assignment corresponding to a range reading r is obtained directly using (10), (11). The confidence of each cell in the map is updated by (12).

3.4. Decision Rules for Building a Map

The state of the cell $(i,j)$ in the map is described by two states: O (occupied) and E (empty), representing the basic probability assignments $m_{i,j}(O)$ and $m_{i,j}(E)$ . To determine the states of the cells in the map, three rules are defined, according to the principles of target classification and practical experiences [11, 17], as follows:

$$\begin{array}{cc}& m_{i,j}\left(O\right)>T_{\mathrm{0}},\hspace{1em}\mathrm{0}<T_{\mathrm{0}}<1,\\ m_{i,j}\left(O\right)-m_{i,j}\left(A\mid A\in \left\{E,\left\{E,O\right\}\right\}\right)\ge T_{\mathrm{1}},\hspace{1em}\mathrm{0}<T_{\mathrm{1}}<1,\\ m_{i,j}\left(\left\{E,O\right\}\right)\le T_{\mathrm{2}},\hspace{1em}\mathrm{0}<T_{\mathrm{2}}<1.\end{array}$$

(13)

If $m_{i,j}(O)$ satisfies all of the rules, then the state of the cell $(i,j)$ in the map is set as occupied, otherwise the state is empty. As the AUV plans its complete coverage path, a map of the environment is increasingly constructed and updated by the decision rules.

4. Simulation Results

In this map-building system, the cell size is 4 m, and the map size is 15 × 15 cells (covering area of 60 × 60 m²), as shown in Figure 5(a). The sensor model parameters are set as follows: $R=\mathrm{8}$ , $d=\mathrm{0.6}$ , and $\alpha ={\mathrm{3}}^{°}$ for (10), (11). The AUV has no prior knowledge of any obstacle in the map initially. To perform the mapping, the AUV plans its complete coverage path using the proposed neurodynamics model. The neural network includes 15 × 15 topologically organized neurons according to the map size, as shown in Figure 5(b). The constant E in (3) is set as 100.

Figure 5

The complete coverage path planning and map building in a completely unknown environment.

4.1. Map Building in an Unknown Environment

In Figure 5(a), the AUV moves from the starting location (1, 1) to top side in the map. When the AUV has covered the location (1, 2), (1, 3), and (1, 4), the neural activity in the covered locations descend. However, the activity in uncovered locations remains relatively high, as shown in Figure 5(b). When the AUV moves to the location (1, 4), an obstacle is detected by the sensor. Table 1 shows the process of calculating the basic probability assignments in the map using the proposed evidence theory. The probability assignments are initially set as follows: $m_{i,j}(O)=\mathrm{0},\hspace{0.17em}\hspace{0.17em}{m}_{i,j}(E)=\mathrm{0}$ , and $m_{i,j}(\{O,E\})=\mathrm{1}$ . When the AUV starting from location (1, 1) reaches (1, 4), $m_{\mathrm{3,3}}^{\mathrm{4}}(O)=\mathrm{0.8940}$ , $m_{\mathrm{3,3}}^{\mathrm{4}}(E)=\mathrm{0}$ , and $m_{\mathrm{3,3}}^{\mathrm{4}}(\{O,E\})=\mathrm{0.1060}$ . According to the predefined rules, $m_{\mathrm{3,3}}^{\mathrm{4}}(O)>T_{\mathrm{0}}$ , $m_{\mathrm{3,3}}^{\mathrm{4}}(O)-m_{\mathrm{3,3}}^{\mathrm{4}}(A\mid A\in \{E,\{E,O\}\})\ge T_{\mathrm{1}}$ and $m_{\mathrm{3,3}}^{\mathrm{4}}(\{E,O\})\le T_{\mathrm{2}}$ , where $T_{\mathrm{0}}=\mathrm{0.4}$ , $T_{\mathrm{1}}=\mathrm{0.1}$ , and $T_{\mathrm{2}}=\mathrm{0.2}$ . Therefore the state of location (3, 3) in the map is set as occupied, and the locations the AUV have covered are empty, as shown in Figure 5(a). As the AUV moves, the map is increasingly built and updated, and the neural activity landscape changes accordingly. The uncovered areas continually attract the AUV until they are covered.

Table 1

The fusion of sensor data at location (3, 3) when the AUV moves from (1, 1) to (1, 4).

The AUV's location	Sensor data(r/m, θ/°)	$S_{\mathrm{3,3}}^t(O)$	$S_{\mathrm{3,3}}^t(E)$	$m_{\mathrm{3,3}}^{t-\mathrm{1}}(O)$	$m_{\mathrm{3,3}}^{t-\mathrm{1}}(E)$	$m_{\mathrm{3,3}}^t(O)$	$m_{\mathrm{3,3}}^t(E)$	$m_{\mathrm{3,3}}^t(\{O,E\})$
(1, 1)	(2.8052, 1.1742)	0	0	0	0	0	0	1
(1, 2)	(2.2176, −0.3695)	0.5490	0	0	0	0.5490	0	0.4510
(1, 3)	(1.9177, 1.4477)	0.4030	0	0.5490	0	0.7307	0	0.2693
(1, 4)	(2.3204, −0.1143)	0.6064	0	0.7307	0	0.8940	0	0.1060
$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$	$\cdots$

4.2. Escaping from a Deadlock Situation

When the AUV is trapped in a dead end, the next location is not immediately available because the neighboring neuron of the current neuron is either covered, obstacle, or with smaller neural activity. This is usually called a deadlock situation. The propagation of the neural activity guarantees that the AUV can autonomously escape from the situation through the changing landscape of the neural activity.

For example, when the AUV moves from location (3, 5) to D(3, 4) (see Figure 6(a)), it's trapped at the location D because the neural activity at D is larger than that at the neighboring locations, as shown in Figure 6(b). The AUV waits until neural activity propagates to its current deadlock location. Whenever the neural activity at the current AUV location is smaller than that at the neighboring locations (see Figure 6(d)), the AUV starts to move out from the deadlock location. When reaching location E(3, 6), the AUV successfully escapes from the deadlock situation to continue its path, as shown in Figure 6(c).

Figure 6

Escaping from a deadlock situation.

4.3. Map Building in a Dynamic Environment

In a sense, building a map of an unknown environment means finding all the static obstacle information. In a dynamic environment, when the AUV detects a moving obstacle, the map information at the location is set to be occupied. However, when the obstacle moves away afterwards, the map information is out-of-date and wrong. This is called misinformation caused by moving obstacles.

The proposed neurodynamics model is capable of planning a collision-free path when the AUV encounters moving obstacles [4, 9, 10]. In this paper, furthermore, the model combined with the evidence theory is extended for the map-building system to eliminate the interference from moving obstacles.

In Figure 7(a), when the AUV reaches location (4, 11), it detects an obstacle at location P(6, 11). The probability landscape of the obstacle is shown in Figure 7(b). According to the evidence theory and the proposed decision rules, the state of P in the map is set as occupied. It's obvious that the map information at P is not correct if the obstacle is moves away. When the AUV moves a zigzag path to (5, 10) as shown in Figure 7(d), the moving obstacle is no longer at P. Therefore the confidence at P is updated as $m_{\mathrm{6,11}}^{}(O)=\mathrm{0}$ , as shown in Figure 7(e). The state information of (6, 11) in the map is corrected to be empty. The location in the map is repeatedly detected by the sonar sensor at different times, and therefore the map information is more accurate.

Figure 7

The map building in a dynamic environment.

A complete map with static obstacle information is shown in Figure 8(a). The path is optimized with less turns of the AUV's directions and less overlapping areas. When the AUV completely covers the environment, the excitatory input to each covered neuron is zero. The inhibitory inputs from obstacles make the neural activity always negative (stay in the valley), as shown in Figure 8(b). The map is dynamically built and updated during the complete coverage navigation. The obstacles are identified by using the proposed evidence theory and the decision rules. The resulting probability landscapes of obstacles and free spaces are shown in Figures 8(c) and 8(d), respectively.

Figure 8

Final results of complete coverage path planning and map building.

5. Conclusion

The developed map-building system is capable of autonomously building a grid map of a completely unknown underwater environment. The proposed neurodynamics model for complete coverage path planning needs no prior knowledge of the environment and no learning procedure. The AUV autonomously plans its path through the dynamic landscape of neural activity with less overlapping areas and without any deadlock problem. The noise and uncertainty of sensory information is reduced by using the Dempster-Shafer theory of evidence. A complete coverage path guarantees that a location in the map will be repeatedly detected by the AUV at different times and from different locations. The path combined with the evidence theory can deal with the misinformation caused by moving obstacles in a dynamically changing environment. In the future study, experiments on a real AUV equipped with a sonar sensor will be implemented with taking the simultaneous localization issue into account.