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 $[0, r_{0}]$ where $r_{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}}{d t} = - A x_{k} + (B - x_{k}) ({[I_{k}]}^{+} + \sum_{l = 1}^{m} w_{k l} {[x_{l}]}^{+}) \\ - (D + x_{k}) {[I_{k}]}^{-}, \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 = 1}^{m} w_{k l} {[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 {a, 0}

, and function

[a]^{-}

is defined as

[a]^{-} = \max {- a, 0}

. The connection weight

w_{k l}

from the kth neuron to the lth neuron is given by

w_{k l} = 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{matrix} f (d) = {\begin{cases} μ / d, & 0 \leq d < r_{0}, \\ 0, & d \geq r_{0}, \end{cases} \end{matrix}

(2)

where μ and

r_{0}

are positive constants. The external input

I_{k}

to the kth neuron is defined as

\begin{matrix} I_{k} = {\begin{cases} E, & if it is an uncovered area, \\ - E, & if it is an obstacle area, \\ 0, & if it is a covered area, \end{cases} \end{matrix}

(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{matrix} p_{n} ⟸ x_{p_{n}} = \max {x_{l} + c y_{l}, l = 1,2, \dots, m}, \end{matrix}

(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{matrix} y_{l} = 1 - \frac{Δ ψ_{l}}{π}, \end{matrix}

(5)

where

Δ ψ_{l} \in [0, π]

is the turning angle between the current moving direction and the next moving direction, for example, if the AUV goes straight,

Δ ψ_{l} = 0

; if it goes backward,

Δ ψ_{l} = π

. Thus,

Δ ψ_{l}

can be given as

Δ ψ_{l} = ψ_{l} - ψ_{c} = | a \tan 2 (y_{p_{l}} - y_{p_{c}}, x_{p_{l}} - x_{p_{c}}) - a \tan 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

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

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

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

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, θ)$ 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 $Θ$ which is a set of labels representing mutually exhaustive events. The labels for map building are defined as $Θ = {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 $Θ$ is the power set

\begin{matrix} Λ = 2^{Θ} = {Φ, E, O, {E, O}} . \end{matrix}

(6)

The state of each cell is described by assigning basic probability values to each label in

Λ

. For each cell

(i, j)

in the grid,

\begin{matrix} m_{i, j} (Φ) = 0, \end{matrix}

(7)

\begin{array}{l} m_{i, j} (A) = \sum_{A \subset Ψ} m_{i, j} (Φ) + m_{i, j} (E) + m_{i, j} (O) + m_{i, j} ({E, O}) \\ = 1 . \end{array}

(8)

Due to (7) and assuming that

m_{i, j} (Φ) = 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{matrix} m_{i, j} (E) = m_{i, j} (O) = 0, m_{i, j} ({E, O}) = 1, \end{matrix}

(9)

representing total ignorance about the state of each cell. If the AUV is sure about the cell occupancy, then

m_{i, j} (O) = 1

. Similarly, when the AUV is sure that a cell is empty, then

m_{i, j} (E) = 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{matrix} m (O) = \frac{{(\begin{smallmatrix} α - | θ | \\ α \end{smallmatrix})}^{2} + {(\begin{smallmatrix} d - | R - r | \\ d \end{smallmatrix})}^{2}}{2}, \\ m (E) = 0, \\ m ({O, E}) = 1 - m (O) . \end{matrix}

(10)

In region II, where $R_{\min} \leq r \leq R - d$ :

\begin{matrix} m (O) = 0, \\ m (E) = \frac{{(\begin{smallmatrix} α - | θ | \\ α \end{smallmatrix})}^{2} + {(\begin{smallmatrix} R - r - d \\ R - d \end{smallmatrix})}^{2}}{2}, \\ m ({O, E}) = 1 - m (E) . \end{matrix}

(11)

3.3. The Fusion of Sensor Data

For a certain event A, $m_{i, j}^{t - 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} m_{i, j}^{t} (O) = m_{i, j}^{t - 1} (O) \oplus S_{i, j}^{t} (O) \\ = \frac{m_{i, j}^{t - 1} (O) S_{i, j}^{t} (O) + m_{i, j}^{t - 1} (O) (1 - S_{i, j}^{t} (E) - S_{i, j}^{t} (O))}{1 - m_{i, j}^{t - 1} (E) S_{i, j}^{t} (O) - m_{i, j}^{t - 1} (O) S_{i, j}^{t} (E)} \\ + \frac{(1 - m_{i, j}^{t - 1} (E) - m_{i, j}^{t - 1} (O)) S_{i, j}^{t} (O)}{1 - m_{i, j}^{t - 1} (E) S_{i, j}^{t} (O) - m_{i, j}^{t - 1} (O) S_{i, j}^{t} (E)}, \\ m_{i, j}^{t} (E) = m_{i, j}^{t - 1} (E) \oplus S_{i, j}^{t} (E) \\ = \frac{m_{i, j}^{t - 1} (E) S_{i, j}^{t} (E) + m_{i, j}^{t - 1} (E) (1 - S_{i, j}^{t} (E) - S_{i, j}^{t} (O))}{1 - m_{i, j}^{t - 1} (E) S_{i, j}^{t} (O) - m_{i, j}^{t - 1} (O) S_{i, j}^{t} (E)} \\ + \frac{(1 - m_{i, j}^{t - 1} (E) - m_{i, j}^{t - 1} (O)) S_{i, j}^{t} (E)}{1 - m_{i, j}^{t - 1} (E) S_{i, j}^{t} (O) - m_{i, j}^{t - 1} (O) S_{i, j}^{t} (E)}, \\ m_{i, j}^{t} ({O, E}) = 1 - m_{i, j}^{t} (O) - m_{i, j}^{t} (E) . \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{matrix} m_{i, j} (O) > T_{0}, 0 < T_{0} < 1, \\ m_{i, j} (O) - m_{i, j} (A ∣ A \in {E, {E, O}}) \geq T_{1}, 0 < T_{1} < 1, \\ m_{i, j} ({E, O}) \leq T_{2}, 0 < T_{2} < 1 . \end{matrix}

(13)

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 = 8$ , $d = 0.6$ , and $α = 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) = 0, m_{i, j} (E) = 0$ , and $m_{i, j} ({O, E}) = 1$ . When the AUV starting from location (1, 1) reaches (1, 4), $m_{3,3}^{4} (O) = 0.8940$ , $m_{3,3}^{4} (E) = 0$ , and $m_{3,3}^{4} ({O, E}) = 0.1060$ . According to the predefined rules, $m_{3,3}^{4} (O) > T_{0}$ , $m_{3,3}^{4} (O) - m_{3,3}^{4} (A ∣ A \in {E, {E, O}}) \geq T_{1}$ and $m_{3,3}^{4} ({E, O}) \leq T_{2}$ , where $T_{0} = 0.4$ , $T_{1} = 0.1$ , and $T_{2} = 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_{3,3}^{t} (O)$	$S_{3,3}^{t} (E)$	$m_{3,3}^{t - 1} (O)$	$m_{3,3}^{t - 1} (E)$	$m_{3,3}^{t} (O)$	$m_{3,3}^{t} (E)$	$m_{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
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

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_{6,11}^{} (O) = 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.

Footnotes

Acknowledgments

This project is supported by the Innovation Program of Shanghai Municipal Education Commission (12YZ114), the National Natural Science Foundation of China (51075257), and Science & Technology Program of Shanghai Maritime University (20100097).

References

Cai

C. H.

Ferrari

Information-driven sensor path planning by approximate cell decomposition

IEEE Transactions on Systems, Man, and Cybernetics B 2009 39 3 672 689

2-s2.0-60349119747

10.1109/TSMCB.2008.2008561

Atkar

P. N.

Conner

D. C.

Greenfield

Choset

Rizzi

A. A.

Hierarchical segmentation of piecewise pseudoextruded surfaces for uniform coverage

IEEE Transactions on Automation Science and Engineering 2009 6 1 107 120

2-s2.0-58149511925

10.1109/TASE.2008.916768

Liang

Y. M.

Wen

R. C.

Zhang

Z. L.

Zhu

J. L.

Dynamic coverage path planning and obstacle avoidance for cleaning robot based on behavior

Proceedings of the International Conference on Electric Information and Control Engineering (ICEICE '11)

April 2011

Wuhan, China

4952 4956

2-s2.0-79959916361

10.1109/ICEICE.2011.5777555

Yang

S. X.

Luo

C. M.

A neural network approach to complete coverage path planning

IEEE Transactions on Systems, Man, and Cybernetics B 2004 34 1 718 724

2-s2.0-0742324891

10.1109/TSMCB.2003.811769

Zhang

Qiao

J. F.

Zhang

H. Y.

Path planning and tracking for agricultural master-slave robot system

Proceedings of the International Conference on Computer and Communication Technologies in Agriculture Engineering (CCTAE '10)

June 2010

Suzhou, China

55 58

2-s2.0-77956476427

10.1109/CCTAE.2010.5543710

Stutters

Liu

Tiltman

Brown

D. J.

Navigation technologies for autonomous underwater vehicles

IEEE Transactions on Systems, Man and Cybernetics C 2008 38 4 581 589

2-s2.0-46849086341

10.1109/TSMCC.2008.919147

Molnar

Omerdic

Toal

Guidance, navigation and control system for the Tethra unmanned underwater vehicle

International Journal of Control 2007 80 7 1050 1076

2-s2.0-34547953778

10.1080/00207170701245039

Paull

Saeedi

Myers

An information gain based adaptive path planning method for an autonomous underwater vehicle using sidescan sonar

Proceedings of the IEEE International Conference on Automation Science and Engineering (CASE '10)

August 2010

Toronto, Canada

835 840

2-s2.0-78149443369

10.1109/COASE.2010.5584478

Yana

M. Z.

Zhub

D. Q.

An algorithm of complete coverage path planning for Autonomous Underwater Vehicles

Key Engineering Materials 2011 467–469 1377 1385

2-s2.0-79952539979

10.4028/www.scientific.net/KEM.467-469.1377

10.

Luo

C. M.

Yang

S. X.

A bioinspired neural network for real-time concurrent map building and complete coverage robot navigation in unknown environments

IEEE Transactions on Neural Networks 2008 19 7 1279 1298

2-s2.0-48949116229

10.1109/TNN.2008.2000394

11.

Song

Jiang

Structure selection for DAG-SVM based on misclassification cost minimization

International Journal of Innovative Computing, Information & Control 2011 7 9 5133 5143

12.

Ribo

Pinz

A comparison of three uncertainty calculi for building sonar-based occupancy grids

Robotics and Autonomous Systems 2001 35 3-4 201 209

2-s2.0-0035973311

10.1016/S0921-8890(01)00116-6

13.

Oriolo

Ulivi

Vendittelli

Fuzzy maps: a new tool for mobile robot perception and planning

Journal of Robotic Systems 1997 14 3 179 197

2-s2.0-0031104534

14.

Velagic

Lacevic

Perunicic

A 3-level autonomous mobile robot navigation system designed by using reasoning/search approaches

Robotics and Autonomous Systems 2006 54 12 989 1004

2-s2.0-33845995084

10.1016/j.robot.2006.05.006

15.

Zhu

Sensor fusion in integrated circuit fault diagnosis using a belief function model

International Journal of Distributed Sensor Networks 2008 4 3 247 261

2-s2.0-48849083240

10.1080/15501320701260626

16.

Dauwe

van Renterghem

Botteldooren

Dhoedt

Multiagent-based data fusion in environmental monitoring networks

International Journal of Distributed Sensor Networks 2012 2012 15

324935

2-s2.0-84863672004

10.1155/2012/324935

17.

Liang

W. G.

Wang

Zhu

G. M.

Zhou

J. L.

Anomaly state monitoring for spacecraft based on evidence theory

Journal of Astronautics 2011 32 12 2537 2544