Sage Journals: Discover world-class research

Abstract

According to the requirements of the mobile robot complete coverage path planning for some special missions, this paper introduces a bounded strategy based on the integration of the Lorenz dynamic system and the robot kinematics equation. Chaotic variables of the Lorenz system are confined in a limited range, while when they are used to produce the robot's coordinate position, the trajectory range is determined by the starting point, iterative times, and iterative step. The proposed bounded strategy can constrain all the robot positions in the workplace by a mirror mapping method that can reflect the overflow waypoints returning to it. Moreover, the statistical characteristics of the Lorenz chaotic variables and the robot trajectory are discussed in order to choose the best mapping variable. The simulation results show that the bounded strategy that uses the chosen variable can achieve a higher coverage rate contrary to other similar works.

Keywords

Coverage Path Planning Lorenz Chaotic System Bounded Strategy Mobile Robot Statistical Characteristics

1. Introduction

The coverage path planning addresses the problem of requiring a traverse for every feasible area in a given workplace while avoiding obstacles [1]. It is needed for a variety of applications such as vacuum cleaning robots [2], lawn mowers [3], exploring underwater sources [4], demining robots [5], etc. Different coverage path planning algorithms are proposed for the above applications, such as the backtracking spiral algorithm (BSA) [6], back-and-forth method [7, 8], as well as some artificial intelligence algorithms, for instance, the neural network [9, 10], genetic algorithm [11, 12], etc. Each method can be suitable for different applications. As yet, there is no universal algorithm or method that can solve all above cases is found. For achieving some special missions, such as the surveillance of terrains [13], the terrain exploration for searching [14], or patrolling [15], the mobile robot tries to find the way to generate a trajectory, which will guarantee the surveillance of the entire terrain or the finding of the explosives. Furthermore, in the case of patrolling for intrusion, the path of the robot must be as much difficult to be predicted by the intruder as possible. Chaotic systems, due to their sensitivity to initial conditions, feature, and topological transitivity [16], provide the much-needed framework for achieving the previously mentioned tasks. Sensitivity on initial conditions will produce a totally different chaotic trajectory and make the long-term prediction impossible. Due to the topological transitivity, the chaotic mobile robot is guaranteed to scan the whole connected workplace. Now this goal is achieved by designing controllers, which ensure chaotic motion of the mobile robot. Though the random signal can also yield unpredictable trajectory, chaotic motion has a very important advantage because it is based on determinism. This means that the behavior of a robot can be predicted in advance by the system's designer.

In order to generate chaotic motions of the mobile robot, well-known chaotic systems, such as Arnold dynamical system [14, 17, 18], Lorenz system [19, 20], standard or Taylor-Chirikov map [13, 21], and Chua circuit [14], have been used. A chaotic path planning generator is produced by combing the robot kinematic motion with a chaotic dynamical system. Then, the robot can behave in a chaotic manner. Chaotic systems of different dimensions require diverse integration methods. One-dimensional systems have only one variable that is usually imparted to be as the robot's running orientation [22, 23], such as the Logistic map. And the two-dimensional systems, for example the standard or Taylor-Chirikov map [13, 21, 24], have two variables, and they can easily be used to control the robot's coordinate position. The three-dimensional systems have a very flexible selection because they have three variables [25, 26, 27]. Theoretically, any one of them can be chosen as the chaotic variable to control the robot's orientation. In fact, most of the current literature did so. They only discussed the application of the chaotic systems in the mobile robot and satisfied the mission requirements. While which variable can show better statistical results with regard to the coverage rate and how does the robot behave with an integration motion in the workplace have not been described in most literature. In this paper, we discuss a famous three-dimensional chaotic system, i.e., the Lorenz system. Compared with other nonlinear systems, the Lorenz system has a relatively simple structure, as well as a good chaotic characteristic that can obtain a higher coverage rate for a specific terrain. So, in this paper we use it to generate a chaotic path planner to fulfill the coverage path planning for some special missions, and discuss the above -mentioned problems in detail.

This paper is organized as follows. The basic features of the Lorenz dynamic system are presented in Section 2. Section 3 introduces the integration strategy of the Lorenz chaotic system and the robot kinematic equation, and the transformation methods for the integration differential formula to the difference one. The χ² values are used to evaluate the statistical characteristics of the Lorenz chaotic variables and the robot trajectory, which are discussed in Section 4, and the robot coverage rate produced by the integration path planner is also discussed in this section. Section 5 presents the comparative result of the improved coverage strategy with the similar work with regard to the coverage rate. The last section outlines the conclusions and final remarks.

2. Lorenz Dynamic System

The Lorenz system is a well-known nonlinear dynamical system introduced by the meteorologist E. N. Lorenz. It is a three-dimensional dynamical system that exhibits chaotic flow [25]. The term “butterfly effect,” which in chaos theory means sensitive dependence on initial conditions, was first demonstrated by the oscillator.

In this system, the control parameters are the Rayleigh number r, the Prandtl number σ, and the geometric factor β. The Lorenz system is described by the following differential equation:

\begin{array}{l} \frac{d x (t)}{d t} = - β x (t) + y (t) z (t), \\ \frac{d y (t)}{d t} = - σ (y (t) - z (t)), \\ \frac{d z (t)}{d t} = - x (t) y (t) + r y (t) - z (t) . \end{array}

(1)

All $σ, r, β > 0$ , but usually $σ = 10$ , $β = 8 / 3$ , and r is varied. The system exhibits chaotic behavior for $r = 28$ and displays orbits for other values. Figure 1 depicts the simulation results of the Lorenz system (1) for the following parameters: $σ = 10$ , $β = 8 / 3$ , and $r = 28$ , and simulation time 50 s for time step h = 0.01. The results are obtained by the ODE45 procedure of the MATLAB inherent software. In this paper, the parameters σ, β, and r assume constant values that are the same as before. $x (t)$ , $y (t)$ , and $z (t)$ of the Lorenz system are state variables that demonstrate a chaotic behavior in a bounded range. Even if the initial point $(x (0), y (0), z (0))$ does not locate in the attraction domain, $(x (t), y (t), z (t))$ will return to the attraction region after limited iterations. One of the variables can be used to be embedded in a mobile robot to produce a chaotic trajectory for some special missions that need coverage path and unpredictability characteristics.

Figure 1.

Simulation results of the Lorenz system for parameters $σ = 10$ , $β = 8 / 3$ , $r = 28$ , and initial point $(x_{0}, y_{0}, z_{0}) = (0, 1, 0)$

3. Integration Strategy of the Lorenz Chaotic System and the Mobile Robot

In order to generate chaotic motions of the mobile robot, we should integrate the Lorenz equation into the controller of the mobile robot to construct a chaotic path planner. First, we have to select a robot kinematic modeling that can produce the robot coordinate position (X(t), Y(t)) for the path planning by the robot linear velocity v and running orientation θ(t). Here, v is usually supposed as a constant value. And we only use orientation θ(t) to control the robot position. Second, the chaotic variable x(t) of the Lorenz system is mapped into the robot kinematic modeling to replace the robot orientation θ(t). So, the robot position changes according to the chaotic value x(t) and can demonstrate the chaotic characteristics to obtain a coverage path planning. Finally, a chaotic path planner is achieved. Because the followed bounded strategy each time required robot position (X_n, Y_n) for boundary detection or mirror mapping computation, the planner has to be discretized for realization. The following equation (Eq. (2)) provides a robot kinematic modeling, formula (3) is the constructed chaotic path planner in a differential form, Eq. (4) solves the discretized parameters of formula (3), and Eq. (5) is the discretized chaotic path planner for formulae (3) and (4). The discretized form is used in our paper for the coverage path planning and the followed bounded strategy. The detailed construction procedure is described as follows.

The assumed kinematic modeling of the robot is [28]

\begin{array}{l} \frac{d X (t)}{d t} = v \cos (θ (t)), \\ \frac{d Y (t)}{d t} = v \sin (θ (t)), \end{array}

(2)

where $X (t)$ and $Y (t)$ identify the robot coordinate position, $θ (t)$ is the orientation, and v is the velocity which is supposed as a constant value. Using variable $x (t)$ of the Lorenz system as the mapping value, we exemplify how to produce a chaotic robot path planner by integrating Eq. (1) with Eq. (2). Variable $x (t)$ replaces $θ (t)$ in formula (2). So, the fusion result is

\begin{array}{l} \frac{d x (t)}{d t} = - β x (t) + y (t) z (t), \\ \frac{d y (t)}{d t} = - σ (y (t) - z (t)), \\ \frac{d z (t)}{d t} = - x (t) y (t) + r y (t) - z (t), \\ \frac{d X (t)}{d t} = v \cos (x (t)), \\ \frac{d Y (t)}{d t} = v \sin (x (t)) . \end{array}

(3)

The whole states evolve in a 5D space according to Eq. (3), which includes a 3D subspace of the Lorenz flow. So, the robot path planner possesses the chaotic characteristics.

Because the followed mirror mapping means and the bounded strategy for achieving the coverage path planning need each time robot position (X_n, Y_n), Eqs. (1), (2) and (3) have to be discretized (X(t), Y(t)) to (X_n, Y_n) for realization. By the four -order Runge-Kutta method, the discretization parameters of Eq. (1) are

\begin{array}{l} K_{1}^{x} = - β x_{n} + y_{n} z_{n}, \\ K_{1}^{y} = - σ (y_{n} - z_{n}), \\ K_{1}^{z} = - x_{n} y_{n} + r y_{n} - z_{n}, \\ K_{2}^{x} = - β (x_{n} + \frac{Δ t}{2} K_{1}^{x}) + (y_{n} + \frac{Δ t}{2} K_{1}^{y}) (z_{n} + \frac{Δ t}{2} K_{1}^{z}), \\ K_{2}^{y} = - σ ((y_{n} + \frac{Δ t}{2} K_{1}^{y}) - (z_{n} + \frac{Δ t}{2} K_{1}^{z})), \\ K_{2}^{z} = - (x_{n} + \frac{Δ t}{2} K_{1}^{x}) (y_{n} + \frac{Δ t}{2} K_{1}^{y}) + r (y_{n} + \frac{Δ t}{2} K_{1}^{y}) - (z_{n} + \frac{Δ t}{2} K_{1}^{z}), \\ K_{3}^{x} = - β (x_{n} + \frac{Δ t}{2} K_{2}^{x}) + (y_{n} + \frac{Δ t}{2} K_{2}^{y}) (z_{n} + \frac{Δ t}{2} K_{2}^{z}), \\ K_{3}^{y} = - σ ((y_{n} + \frac{Δ t}{2} K_{2}^{y}) - (z_{n} + \frac{Δ t}{2} K_{2}^{z})), \\ K_{3}^{z} = - (x_{n} + \frac{Δ t}{2} K_{2}^{x}) (y_{n} + \frac{Δ t}{2} K_{2}^{y}) + r (y_{n} + \frac{Δ t}{2} K_{2}^{y}) - (z_{n} + \frac{Δ t}{2} K_{2}^{z}), \\ K_{4}^{x} = - β (x_{n} + Δ t K_{3}^{x}) + (y_{n} + Δ t K_{3}^{y}) (z_{n} + Δ t K_{3}^{z}), \\ K_{4}^{y} = - σ ((y_{n} + Δ t K_{3}^{y}) - (z_{n} + Δ t K_{3}^{z})), \\ K_{4}^{z} = - (x_{n} + Δ t K_{3}^{x}) (y_{n} + Δ t K_{3}^{y}) + r (y_{n} + Δ t K_{3}^{y}) - (z_{n} + Δ t K_{3}^{z}), \end{array}

(4)

where $Δ t$ is a sufficiently small iterative time step. The robot kinematic equation (2) is also transformed into a one-order difference formula. So the difference formula of Eq. (3) is

\begin{array}{l} x_{n} = x_{n - 1} + \frac{Δ t}{6} (K_{1}^{x} + 2 K_{2}^{x} + 2 K_{3}^{x} + K_{4}^{x}), \\ y_{n} = y_{n - 1} + \frac{Δ t}{6} (K_{1}^{y} + 2 K_{2}^{y} + 2 K_{3}^{y} + K_{4}^{y}), \\ z_{n} = z_{n - 1} + \frac{Δ t}{6} (K_{1}^{z} + 2 K_{2}^{z} + 2 K_{3}^{z} + K_{4}^{z}), \\ X_{n} = X_{n - 1} + h v \cos (x_{n}), \\ Y_{n} = Y_{n - 1} + h v \sin (x_{n}), \end{array}

(5)

where h is a small iterative step. Given the initial values $(x_{0}, y_{0}, z_{0}, X_{0}, Y_{0})$ , the robot position $(X_{n}, Y_{n})$ of each time in the path planning can be figured out step by step according to formula (5). If the variable $y (t)$ or $z (t)$ of the Lorenz equation is selected as the mapping value, the solving means is similar as the method mentioned above.

4. Statistical Characteristics of the Lorenz System and the Robot Trajectory

The target of the coverage path planning is to cover the whole workplace as quickly, randomly, and uniformly as possible for a special mission. Any of the three variables can be chosen as the mapping value, but which one can show better statistical characteristics or has a higher coverage rate after mapping into the robot? Here, we use the χ² test to evaluate statistical characteristics of each variable [29].

The main thought of the χ² test is to divide a time sequences into k same length subintervals between a defined range [a, b], and examine the diversity between the real frequency and theoretical one of the random sequence distribution in the subinterval. Define the real frequency of the ith subinterval random data as n_i. And the corresponding theoretical frequency of this subinterval is defined as m_i, here $m_{i} = N / k$ , where N is the total random sequences number. The statistical value χ² is expressed as follows:

χ^{2} = \sum_{i = 1}^{k} \frac{{(n_{i} - m_{i})}^{2}}{m_{i}} = \frac{k}{N} {\sum_{i = 1}^{k} (n_{i} - \frac{N}{k})}^{2} .

(6)

Here, the χ² value is not used to pass the random test. We utilize the value to evaluate the chaotic variables’ statistical characteristics. The smaller the χ² value is, the better properties the chaotic variable exhibits. Two experiments are designed. One is to compute the χ² values of the three chaotic variables of the Lorenz system, and the other is to calculate them for the robot position, or trajectory, in the workplace.

4.1. Statistical characteristics of the chaotic variables

At first we analyze the statistical characteristic values that assume the χ² data of the three chaotic variables x_n, y_n, and z_n, respectively. Figure 2 shows N iterative values of the three chaotic variables, respectively. Here, the iterative time N = 20,000. Figure 2(a) and (b) assumes different starting points. Though the initial data are not very stable due to the random selection of the beginning iterative point, as long as the iterative time N is big enough, the computation error can be ignored.

Figure 2.

Time sequences of the three chaotic variables of the Lorenz system with different iterative starting points

We analyze the computation procedure of the χ² value for variable x_n.

Divide all the data between $\max (x_{n})$ and $\min (x_{n})$ into k cells that have the uniform size, here $k = 100 \times 100$ ;

Total out the occupied numbers of each cell where the x_n values are located in;

Compute the corresponding theoretical frequency of each subinterval, here $m_{i} = N / k = 20, 000 / 10, 000 = 2$ ;

Calculate the χ² value according to formula (6).

The computing procedure of the χ² value for variable y_n and z_n is the same as mentioned above. Table 1 lists the χ² values of x_n, y_n, and z_n with different starting iterative points, respectively.

Though different initial points may produce diverse χ² values, the relative relationship between variables is constant. Data from Table 1 show variable y_n has the minimum χ² value for both the groups, z_n has the maximum value, while the value of x_n lies between them. So, in the Lorenz chaotic system y_n has the best statistical characteristics with regard to the uniformity. But when it produces the robot position by cosine transform, does it still have the best characteristics?

Table 1.

Statistical characteristics of chaotic variables

Chaotic variable	χ² value
Chaotic variable	(x₀,y₀,z₀)=(0 1 0)	(x₀,y₀,z₀)=(1 1 1)
x_n	1.1803e+004	1.0366e+004
y_n	6.2885e+003	6.3476e+003
z_n	1.4172e+004	1.5213e+004

4.2. Statistical characteristics of the robot's position

All variables are mapped into the robot kinematic equation respectively to further test which chaotic variables show better statistical characteristics. The χ² values of the robot position $(X_{n}, Y_{n})$ and the robot coverage rate in the workplace are obtained to be used as the test data.

All the $(X_{n}, Y_{n})$ data are changed into $100 \times 100$ space by coordinate transformation, so the three chaotic variables can provide the comparable results:

\begin{array}{l} X_{n} = (X_{n} - \min (X_{n})) \times (100 / \max (X_{n})), \\ Y_{n} = (Y_{n} - \min (Y_{n})) \times (100 / \max (Y_{n})) . \end{array}

(7)

Figure 3.

Robot iterative position $(X_{n}, Y_{n})$ , or moving trajectory, after chaotic mapping by the three variables, respectively, in the workplace, with the initial value $(x_{0}, y_{0}, z_{0}) = (0, 1, 0)$ , the robot starting point $(X_{0}, Y_{0}) = (3, 3)$ , and the iterative time is 20,000

Figure 3 show the transformed trajectory after chaotic mapping. The χ² values of each of the three variables are calculated using the method mentioned in Section 4.1. The coverage rate C, or the terrain coverage, which represents the effectiveness, as the amount of the total surface covered the known coverage rate (C), by the robot running the algorithm, is usually expressed by the following equation:

C = \frac{1}{M} \cdot \sum_{i = 1}^{M} I (i),

(8)

where $I (i)$ is the coverage situation for each cell in which the terrain has been divided. This is defined by the following equation:

I (i) = {\begin{cases} 1 when the cell i is covered, \\ 0 when the cell i is not covered . \end{cases}

(9)

Here $i = 1, 2, …, M$ . The robot's workplace is supposed to be a square terrain with dimensions $M = 100 \times 100$ in normalized unit cells. All the results are listed in Table 2.

Table 2.

Statistical characteristics of the robot position

Figure	Chaotic mapping variable	χ² value	C
Figure 3(a)	x_n	1.4553e+005	23.63
Figure 3(b)	y_n	1.7533e+005	18.99
Figure 3(c)	z_n	1.9220e+005	17.41

Data in Table 2 show that the robot position produced by x_n has the minimum χ² value for the three variables after chaotic mapping, and it possesses the maximum coverage rate C. It appears that the statistical characteristics after transition are not consistent with the previous one. Then, chaotic variable x_n is chosen to be as the mapping value. So, the iterative kinematics equation of the robot is

\begin{array}{l} X_{n} = X_{n - 1} + h v \cos (x_{n}), \\ Y_{n} = Y_{n - 1} + h v \sin (x_{n}) . \end{array}

(10)

Later we use formula (10), or formulae (4) and (5), as the chaotic path planner to produce the robot trajectory in the workplace.

5. Statistical Characteristics of the Robot Coverage Trajectory

5.1. Characteristics of the traditional coverage trajectory

Given a random initial point in the workplace, the robot trajectory, or the position $(X_{n}, Y_{n})$ , is figured out by Eq. (10) step by step. Though the chaotic variables x_n, y_n, and z_n of the Lorenz equation are confined in a limited range, as shown in Figure 1, the robot position $(X_{n}, Y_{n})$ transformed by the variables mapping are not always bounded. The moving range of $(X_{n}, Y_{n})$ can be deduced as the following formula according to Eq. (10):

\begin{array}{l} X_{0} - N h v \leq X_{n} \leq X_{0} + N h v, \\ Y_{0} - N h v \leq Y_{n} \leq Y_{0} + N h v . \end{array}

(11)

Here $(X_{0}, Y_{0})$ is the iterative initial point of the mobile robot, and N is the total iterative times. The range of the trajectory $(X_{n}, Y_{n})$ of the robot is confined by $(X_{0}, Y_{0})$ , iterative times N, and iterative step h. When the initial point and iterative step are constant, some points of the robot trajectory can run out of the workplace boundary with the increasing values of N.

Here assume a 5×5 workplace. Figure 4 shows the robot trajectory with different iterative times.

Figure 4.

Snapshots of the robot trajectory with the initial point $(x_{0}, y_{0}, z_{0}, X_{0}, Y_{0}) = (0, 1, 0, 4, 4)$

In order to increase the simulation speed, the iterative step adopts a relatively large value, here h = 0.1. When the iterative time N=10,000, there are some robot positions that are located out of the boundary. If the initial point is selected improperly, such as $(X_{0}, Y_{0}) = (2.5, 2.5)$ , in a very short iterative time the robot can run out of the boundary. Though the robot can also run back some times, we cannot guarantee it is always in the workplace. Figure 5 shows this circumstance. If we do not assume some measures to control the robot running range, the workplace can not be covered completely in a limited time, and the coverage rate will be low.

Figure 5.

Snapshots of the robot trajectory with the initial point $(x_{0}, y_{0}, z_{0}, X_{0}, Y_{0}) = (0, 1, 0, 2.5, 2.5)$

5.2. Characteristics of the bounded coverage trajectory

Here we use mirror mapping method to reflect the overflow points into the robot workplace or a defined range. Figure 6 displays all overflow circumstances and their reflection principle. The resolving means of other special circumstances that are not mentioned here belong to them. Suppose coordinate $(X_{n - 1}, Y_{n - 1})$ is the (n – 1)th time position, and $(X_{n}, Y_{n})$ is the next time coordinate. Assume it is exactly the overflow waypoint. Our task is to figure out the refection point $(X'_{n}, Y'_{n})$ in the workplace. Here, the workplace is a rectangular area, the left line of it is defined as

\begin{array}{l} x_{l} = M_{l}, \\ y_{l} = 0. \end{array}

(12)

The right line is defined as

\begin{array}{l} x_{r} = M_{r}, \\ y_{r} = 0. \end{array}

(13)

The up line is defined as

\begin{array}{l} x_{u} = 0, \\ y_{u} = N_{u} . \end{array}

(14)

And the below line is defined as

\begin{array}{l} x_{d} = 0, \\ y_{d} = N_{d} . \end{array}

(15)

Figure 6.

Mirror mapping

For the circumstances of Figure 6 (a)–(d),the reflection point $(X'_{n}, Y'_{n})$ can be figured out by using the mirror mapping method once. In Figure 6(a), it is defined as

\begin{array}{l} X'_{n} = - X_{n} + 2 M_{l}, \\ Y'_{n} = Y_{n} . \end{array}

(16)

In Figure 6(b), it is defined as

\begin{array}{l} X'_{n} = - X_{n} + 2 M_{r}, \\ Y'_{n} = Y_{n} . \end{array}

(17)

In Figure 6(c), it is defined as

\begin{array}{l} X'_{n} = X_{n}, \\ Y'_{n} = - Y_{n} + 2 N_{d} . \end{array}

(18)

In Figure 6(d), it is defined as

\begin{array}{l} X'_{n} = X_{n}, \\ Y'_{n} = - Y_{n} + 2 N_{u} . \end{array}

(19)

While for the circumstances of Figure 6 (e)–(h),the reflection point $(X'_{n}, Y'_{n})$ has to be figured out by using the mirror mapping means twice. In Figure 6(e), it is defined as

\begin{array}{l} X'_{n} = - X_{n} + 2 M_{l}, \\ Y'_{n} = - Y_{n} + 2 N_{d} . \end{array}

(20)

In Figure 6(f), it is defined as

\begin{array}{l} X'_{n} = - X_{n} + 2 M_{r}, \\ Y'_{n} = - Y_{n} + 2 N_{d} . \end{array}

(21)

In Figure 6(g), it is defined as

\begin{array}{l} X'_{n} = - X_{n} + 2 M_{l}, \\ Y'_{n} = - Y_{n} + 2 N_{u} . \end{array}

(22)

In Figure 6(h), it is defined as

\begin{array}{l} X'_{n} = - X_{n} + 2 M_{r}, \\ Y'_{n} = - Y_{n} + 2 N_{u} . \end{array}

(23)

Then, the obtained reflection point $(X'_{n}, Y'_{n})$ is used as the new iterative point $(X_{n}, Y_{n})$ in formula (10) to iterate computation sequentially until the coverage rate satisfies the task need.

The procedure of the novel coverage path planning of the robot is as follows:

Initialize the parameters. The total iterative time N = 30,000, chaotic variables $(x_{0}, y_{0}, z_{0}) = (0, 1, 0)$ , the robot starting point $(X_{0}, Y_{0}) = (3, 3)$ , the iterative step h=0.1, and a workplace G_w ∈[0 5 0 5];

According to formulae (4) and (5), compute each $(X_{n}, Y_{n})$ based on $(x_{0}, y_{0}, z_{0}, X_{0}, Y_{0})$ ;

Judge whether $(X_{n}, Y_{n})$ overflows the workplace G_w or not; if not, switch to (6); otherwise continue;

According to the corresponding formula (16)– (23), compute the reflection point $(X'_{n}, Y'_{n})$ based on the attribution $(X_{n}, Y_{n})$ of the overflowing circumstances in Figure 6;

Update $(X_{n}, Y_{n})$ with $(X'_{n}, Y'_{n})$ ;

Minus N by 1. Judge whether N = 0 or not. if no, switch to (2); otherwise stop the procedure.

The flowchart of the algorithm is shown in Figure 7.

Figure 7.

Flowchart of the algorithm

Figure 8(a) shows the simulation result of the robot trajectory by the bounded method. The blue dots are the robot position $(X_{n}, Y_{n})$ , and the red “*” are used to show the overflow mark with the boundaries when the robot runs out of the workplace. In order to evaluate the effect of the improved method, Figure 8(b) illustrates the similar work result without boundary constrained and with the same parameters set as Figure 8(a). It is obvious to see that the novel coverage methods have a higher coverage rate, which is 52% here. While Figure 8(b) shows only 23% coverage rate. Then, the bounded method can show better performance. With the increase in the iterative times, the coverage rate of the whole workplace is increasing. When the iterative time N = 160,000, the coverage rate can exceed 95%, as shown in Figure 9. If the iterative time N is large enough, the complete coverage path planning can be achieved successfully.

Figure 8.

Coverage trajectory of the robot in the workplace

Figure 9.

Bounded strategy for coverage trajectory of the robot in the workplace

6. Conclusion

In this paper, we have discussed about the chaotic Lorenz equation and its application in the robot coverage path planning. A novel strategy that has been added to boundary constrained is used to enhance the coverage rate for the robot and can show better performance in contrary with the unconstrained method. This strategy can be extended to other three-dimensional equations, such as Arnold, Chua, etc. And, there are other factors that should be considered:

The mirror mapping is used to constrain the overflow robot positions in the workplace. It is simple and can also be used for obstacle avoidance of the robot in the further work;

The χ² value provides a tool to evaluate the statistical characteristics of the chaotic variables. The smaller it is, the better behavior the variable shows. From the values and the simulation results, we can also see that though the constructed chaotic path planner can satisfy the special task requirements of the coverage path planning, the uniformity of the chaotic variables is not good. So, the characteristics should be improved in the future;

In the simulation, more sampled data should be obtained in order to guarantee that the statistical results are more meaningful.

Footnotes

7. Acknowledgements

This work is supported by the National Natural Science Foundation of China (Nos. 61473179, 61573213, and 61233014) and Natural Science Foundation of Shandong Province (Nos. ZR2014FM007 and ZR2015CM016).

References

Galceran

Carreras

, A survey on coverage path planning for robotics. Robotics and Autonomous Systems, 2013, 61(12):1258–1276.

Park

Kim

K. J.

Del

Angel

, Energy efficient complete coverage path planning for vacuum cleaning robots. Lecture Notes in Electrical Engineering, Future Information Technology, Application, and Service, 2012, 164(1):23–31.

Ousingsawat

Earl

M. G.

, Modified lawn-mower search pattern for areas comprised of weighted regions. Proceedings of the 2007 American Control Conference, 2007, 918–923.

Galceran

Carreras

, Planning coverage paths on bathymetric maps for in-detail inspection of the ocean floor. International Conference on Robotics and Automation, 2013, 4159–4164.

Prado

Marques

, Energy efficient area coverage for an autonomous demining robot. Advances in Intelligent Systems and Computing, 2014, 253:459–471.

Gonzalez

Alvarez

Diaz

Parra

Bustacara

, BSA: A complete coverage algorithm. Proceedings of the 2005 IEEE International Conference on Robotics and Automation, 2005, 2040–2044.

Park

Kim

K. J.

Del Pobil

A. P.

, Energy efficient complete coverage path planning for vacuum cleaning robots. Lecture Notes in Electrical Engineering, Future Information Technology, Application, and Service, 2012, 164(1):23–31.

Oksanen

Visala

, Coverage path planning algorithms for agricultural field machines. Journal of Field Robotics, 2009, 26(8):651–668.

Kassim

A. A.

Vijaya Kumar

B. V. K.

, Path planners based on the wave expansion neural network. Robotics and Autonomous Systems, 1999, 26(1):1–22.

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.

11.

Kapanoglu

Ozkan

YazIcI

Pattern-based genetic algorithm approach to coverage path planning for mobile robots. Computational Science — ICCS 2009— 9th International Conference, 2009, 5544 LNCS(PART 1):33–42.

12.

Chong

W. M.

Goh

C. L.

Bau

Y. T.

, A practical framework for cleaning robots. 2011 6th International Conference on Bio-Inspired Computing: Theories and Applications, 2011, 97–102.

13.

Martins-Filho

L. S.

Macau

E. E. N.

, Patrol mobile robots and chaotic trajectories. Mathematical Problems in Engineering, 2007, 2007:1–13.

14.

Sooraksa

Klomkarn

, No-CPU chaotic robots: From classroom to commerce. IEEE Circuits and Systems Magazine, 2010, 10(1):46–53.

15.

Corbett

D. R.

Gage

D. W.

Hackett

D. D.

, Robotic communications and surveillance—the DARPA LANdroids Program. Lecture Notes in Computer Science 7, 2011, 106:749–758.

16.

Devaney

R. L.

, An Introduction to Chaotic Dynamical Systems. Studies in Nonlinearity, Westview Press, Boulder, Colo., USA, 2nd edition, 2003.

17.

Hara

Kokame

Konishi

, Circular periodic motion generation for mobile robots using limit cycle systems. Proceedings of the American Control Conference, 2010, 4271–4276.

18.

Daniel-Ioan

Constantin

, Path planning algorithm based on Arnold Cat Map for surveillance UAVs. Defence Science Journal, 2015, 65(6): 483–488.

19.

Daniel-Ioan

Constantin

, Chaotic trajectory design for monitoring an arbitrary number of specified locations using points of interest. Mathematical Problems in Engineering, 2012, 2012:1–18.

20.

Kia

Henry

, A cooperative mobile robot task assignment and coverage planning based on chaos synchronization. International Journal of Bifurcation and Chaos, 2010, 20(1):161–176.

21.

Caihong

Yong

Song

Fengying

Wang

Chaotic path planner of autonomous mobile robots based on the standard map for surveillance missions. Mathematical Problems in Engineering, 2015, 2015:1–11.

22.

Caihong

Fengying

Wang

Lei

Zhao

An improved chaotic motion path planner for autonomous mobile robots based on logistic map. International Journal of Advanced Robotic Systems, 2013, 10:1–9.

23.

Volos

Ch. K.

Kyprianidis

I. M.

Stouboulos

I. N.

, Experimental investigation on coverage performance of a chaotic autonomous mobile robot. Robotics and Autonomous Systems, 2013, 61(12):1314–1322.

24.

Daniel-Ioan

Constantin

, A 2D chaotic path planning for mobile robots accomplishing boundary surveillance in adversarial conditions. Communications in Nonlinear Science and Numerical Simulation, 2014, 19(10):3617–3627.

25.

Volos

C. K.

Bardis

N. G.

Kyprianidis

I. M.

Implementation of mobile robot by using double-scroll chaotic attractors. Recent Researches in Applications of Electrical and Computer Engineering, 2012, 119–124.

26.

Nakamura

Sekiguchi

, The chaotic mobile robot. IEEE Transaction on Robotics and Automation, 2001, 17(6):898–904.

27.

Volos

Ch. K.

Kyprianidis

I. M.

Stouboulos

I. N.

, A chaotic path planning generator for autonomous mobile robots. Robotics and Autonomous Systems, 2012, 60(4):651–656.

28.

Siegwart

Nourbakhsh

I. R.

, Introduction to Autonomous Mobile Robots, MIT Press, Cambridge, Mass., USA, 2004.

29.

Gao

Xiuhua

. Statistical Computing, Peking University Press, China, 1995.

A Bounded Strategy of the Mobile Robot Coverage Path Planning Based on Lorenz Chaotic System

Abstract

Keywords

1. Introduction

2. Lorenz Dynamic System

3. Integration Strategy of the Lorenz Chaotic System and the Mobile Robot

4. Statistical Characteristics of the Lorenz System and the Robot Trajectory

4.1. Statistical characteristics of the chaotic variables

4.2. Statistical characteristics of the robot's position

5. Statistical Characteristics of the Robot Coverage Trajectory

5.1. Characteristics of the traditional coverage trajectory

5.2. Characteristics of the bounded coverage trajectory

6. Conclusion

Footnotes

7. Acknowledgements

References