Sage Journals: Discover world-class research

Abstract

The quantitative evaluation of unmanned ground vehicles is difficult. For this problem, we propose a quantitative evaluation method based on chaos theory. First, the ideal trajectory of an unmanned ground vehicle was designed applying the quintic polynomial method, and the deviation time series were obtained by calculating the deviation of the actual trajectory from the ideal trajectory. Then, the phase space of the deviation time series was reconstructed based on the improved algorithm using correlation integral method. Finally, the Lyapunov exponent of the deviation time series was calculated, which was the quantitative presentation of the unmanned ground vehicle’s trajectory. The quantitative presentation of the unmanned ground vehicle’s trajectory for lane keeping, obstacle avoidance, and overtaking lane changing was achieved. The Lyapunov exponent of lane keeping was the least, so the maximum predicted time was the longest. Lane keeping was done the best of all. Experimental results show that the quantitative evaluation method based on chaos theory for unmanned ground vehicle trajectory is feasible and effective.

Keywords

Unmanned ground vehicles chaos quantitative analysis Lyapunov exponent

Foreword

It is difficult to objectively evaluate unmanned ground vehicles. Researchers from Carnegie Mellon University proposed a quantitative evaluation method based on a cost function for the unmanned ground vehicle Boss in low-speed, low-density traffic environments in 2007 Defense Advanced Research Projects Agency (DARPA) Urban Challenge.¹ Our research group also made some attempts to quantitatively evaluate unmanned ground vehicles. We proposed a qualitative and quantitative evaluation method based on a cost function² and a quantitative evaluation method based on fuzzy analytic hierarchy process (AHP).³ Although the quantitative evaluation was completed using these methods, the quantification of the evaluation index was influenced by subjective factors. In order to achieve the objective and quantitative evaluation of unmanned ground vehicles, we need to study and explore more objective quantitative analysis methods.

In the field of robotics, many scholars have carried out a quantitative analysis of the behavior of mobile robots. Nehmzow et al.^4–6 proposed a quantitative description of the behavior of mobile robots based on chaos theory. Schöner et al.^7,8 applied dynamical systems theory to the analysis of robot behavior. Nehmzow proposed a quantitative analysis of the trajectories of mobile robots or their computer simulations, based on the error growth factor (EGF), an approximation of the Lyapunov exponent. Using the EGF, it can be shown that deterministic chaos can be present in the behavior of a mobile robot interacting with its environment.⁹ Duckett and Nehmzow¹⁰ presented statistical methods to assess the performance of robot localization systems. Zhang et al. proposed a fitness-scaling chaotic artificial bee colony (FSCABC) method for the task of path planning of uninhabited combat air vehicle (UCAV). The FSCABC employed the fitness-scaling method and the chaotic theory.¹¹ And then a fitness-scaling adaptive chaotic particle swarm optimization (FAC-PSO) approach was proposed as a fast and robust approach for the task of path planning of UCAVs. The FAC-PSO employed the fitness-scaling method, the adaptive parameter mechanism, and the chaotic theory. The FAC-PSO is more robust and costs less time than elite genetic algorithm with migration, simulated annealing, and chaotic artificial bee colony.¹²

Borrowing the idea of the quantitative analysis of the behavior of mobile robots, a quantitative analysis method for the trajectories of unmanned ground vehicles applying chaos theory is proposed. The results can directly reflect the intelligence level of unmanned ground vehicles.

Article structure

The trajectory of unmanned ground vehicles is one of the parameters most closely associated with their behavior, such as X-axis and Y-axis positions change with time. A flowchart for the quantitative analysis of the trajectory of an unmanned ground vehicle is shown in Figure 1:

The ideal trajectory was designed applying the quintic polynomial method combined with trajectory parameters of an excellent driver.

The deviation time series were obtained by calculating the deviation of the actual trajectory from the ideal trajectory of unmanned ground vehicles.

The time delay and the embedding dimension were calculated by the correlation integral (C-C) method, and then the phase space of the deviation time series was reconstructed.

The quantitative description of the trajectory of unmanned ground vehicles was achieved by calculating the Lyapunov exponent.

The third and the fourth steps are the focus of this article. The quantitative analysis of the trajectory of an unmanned ground vehicle was achieved by applying the phase space reconstruction and the Lyapunov exponent method based on chaos theory.

Figure 1.

Flowchart of the quantitative analysis of the trajectory.

Quantitative analysis method

This section presents the quantitative analysis of the trajectory of an unmanned ground vehicle, including the phase space reconstruction of the deviation time series and calculating the Lyapunov exponent.

First, the deviation time series $D (t)$ were obtained by calculating the deviation of the actual trajectory $f (x, y)$ from the ideal trajectory of the unmanned ground vehicle. Second, the phase space of the deviation time series $D (t)$ was reconstructed. Finally, the Lyapunov exponent of the deviation time series of the unmanned ground vehicle was calculated.

Phase space reconstruction based on the C-C method

“Phase space” means the space of all possible states of a system; each possible state of the system has a corresponding point in phase space. In order to fully reveal the hidden information about the deviation time series of the unmanned ground vehicle trajectory and restore the characteristics of the attractor, the phase space was reconstructed based on the C-C method.¹³

The appropriate time delay $τ$ and embedding dimension $m$ were selected for the time series $x (t_{1}), x (t_{2}), \dots, x (t_{i}), \dots, x (t_{n})$ . Then, the m-dimensional phase space was constructed

X (t_{i}) = [x (t_{i}), x (t_{i} + τ), x (t_{i} + 2 τ), \dots, x (t_{i} + (m - 1) τ)]

(1)

where $i = 1, 2, \dots, n - (m - 1) τ$

Calculate the standard deviation $σ$ of the deviation time series of the unmanned ground vehicle trajectory and select $N$ .

Calculate the amount of the following three formulas

\bar{S} (t) = \frac{1}{16} \sum_{m = 2}^{5} \sum_{j = 1}^{4} S (m, r_{j}, t)

(2)

Δ \bar{S} (t) = \frac{1}{4} \sum_{m = 2}^{5} Δ S (m, t)

(3)

S_{cor} (t) = Δ \bar{S} (t) + | Δ \bar{S} (t) |

(4)

where $S (m, r_{j}, t)$ and $Δ S (m, t)$ are as follows

S (m, r_{j}, t) = \frac{1}{t} \sum_{s = 1}^{t} [C_{s} (m, r_{j}, t) - C_{s}^{m} (1, r_{j}, t)], (m = 2, 3, 4, 5)

(5)

Δ S (m, t) = max {S (m, r_{j}, t)} - min {S (m, r_{j}, t)}

(6)

Find from the calculation results in equation (2):

The first minimum value of $Δ S (m, t)$ corresponding to the best time delay $t$ ;

The first zero of $\bar{S} (t)$ is the best time delay $t$ ;

The minimum $t$ of $S_{cor} (t)$ corresponding to the time window $τ_{ϖ}$ .

If the deviation $D (t)$ of the actual trajectory from the ideal trajectory of unmanned ground vehicles is greater, then the phase space is more fuzzy distortion and the dimension is greater.

Calculate Lyapunov exponent

According to chaos theory, the largest Lyapunov exponent being negative indicates that the motion of the system will eventually converge to a stable equilibrium point, zero indicates that the motion of the system will eventually converge to a stable movement pattern, and positive indicates that the motion of the system is in a chaotic state.¹³

To calculate the Lyapunov exponent of the deviation time series of an unmanned ground vehicle trajectory

Calculate the mean period $P$ of the deviation time series ${x (t_{i}), i = 1, 2, \dots, N}$ of the unmanned ground vehicle trajectory using the fast Fourier transform (FFT).

The time delay $τ$ and the embedding dimension $m$ were calculated by the C-C method.

The phase space ${Y_{j}, j = 1, 2, \dots, M}$ of the deviation time series was reconstructed according to the time delay and embedding dimension.

Find the nearest neighbor points $Y_{\hat{j}}$ of each point $Y_{j}$ in phase space and restrict the temporary separation

d_{j} (0) = min_{\hat{j}} | | Y_{j} - Y_{\hat{j}} | |, | j - \hat{j} | > P

(7)

Calculate the distance $d_{j} (i)$ of the ith discrete time of the adjacent points for each point $Y_{j}$ in the phase space

d_{j} (i) = | Y_{j + i} - Y_{\hat{j} + i} |, i = 1, 2, \dots, \min (M - j, M - \hat{j})

(8)

Calculate the average of all $j$ for each $i$

y (i) = \frac{1}{q Δ t} \sum_{j = 1}^{q} \ln d_{j} (i)

(9)

where $q$ is the number of non-zero $d_{j} (i)$ . The regression line was drawn using the method of least squares. The slope of the straight line is the largest Lyapunov exponent of the deviation time series of the unmanned ground vehicle trajectory.

The ideal trajectory design

The trajectory of unmanned ground vehicles was quantitatively analyzed using chaos theory to evaluate the intelligence level of unmanned ground vehicles. The actual trajectory and the ideal trajectory of unmanned ground vehicles are needed for the quantitative analysis calculation.

The actual trajectory of unmanned ground vehicles can be gained through the integrated positioning test technology, but the ideal trajectory of unmanned ground vehicles is different for different scenarios and tasks. For straight and curved lane following, the ideal trajectory of unmanned ground vehicles is the center line of the lane. For complex scenarios and tasks, such as obstacle avoidance and lane change, the ideal trajectory was designed specifically. Static obstacle avoidance is essentially a lane change process which is a good example for introducing the method of determining the ideal trajectory of an unmanned ground vehicle. The test scenario is shown in Figure 2.

Figure 2.

Lane changing scene of the static obstacle avoidance.

First, the trajectory of the outstanding driver driving the vehicle is collected to obtain the driving parameters: displacement, velocity, time, heading angle, front wheel angle, and so on, and then the initial state and the target state are obtained.

The ideal trajectory for static obstacle avoidance by an unmanned ground vehicle is planned according to the initial state and the target state which were obtained from the outstanding driver and ensuring that the vehicle arrives in the adjacent lane at the appointed time. We used the function $f (x, y, t)$ to describe the lane changing trajectory, which was limited to the geometric structure of the road. The dynamic characteristics of the vehicle from the initial position to a target position in the whole transition process can be described. A quintic polynomial was selected for the constructor of the lane changing trajectory

{\begin{matrix} x (t) = \sum_{0}^{5} a_{i} * t^{i} \\ y (t) = \sum_{0}^{5} b_{i} * t^{i} \end{matrix}

(10)

The derivative with respect to time is

{\begin{matrix} \overset{\cdot}{x} (t) = \frac{d (\sum_{0}^{5} a_{i} * t^{i})}{dt} \\ \overset{\cdot}{y} (t) = \frac{d (\sum_{0}^{5} b_{i} * t^{i})}{dt} \end{matrix}

(11)

The second derivative is

{\begin{matrix} \overset{\cdot\cdot}{x} (t) = \frac{d (\sum_{0}^{5} a_{i} * t^{i})}{d^{2} t} \\ \overset{\cdot\cdot}{y} (t) = \frac{d (\sum_{0}^{5} b_{i} * t^{i})}{d^{2} t} \end{matrix}

(12)

The initial state and the target state of the lane changing of unmanned ground vehicles are

{\vec{S}}_{s} = (x_{s}, {\overset{\cdot}{x}}_{s}, {\overset{\cdot\cdot}{x}}_{s}, y_{s}, {\overset{\cdot}{y}}_{s}, {\overset{\cdot\cdot}{y}}_{s})

{\vec{S}}_{f} = (x_{f}, {\overset{\cdot}{x}}_{f}, {\overset{\cdot\cdot}{x}}_{f}, y_{f}, {\overset{\cdot}{y}}_{f}, {\overset{\cdot\cdot}{y}}_{f})

where $x$ is the longitudinal displacement of the vehicle, $\overset{\cdot}{x}$ is the longitudinal velocity, $\overset{\cdot\cdot}{x}$ is the longitudinal acceleration, $y$ is the lateral displacement, $\overset{\cdot}{y}$ is the lateral velocity, and $\overset{\cdot\cdot}{y}$ is the lateral acceleration. Longitudinal displacement and the lateral displacement of the initial state are 0; lateral displacement of the target state is the lane width, while the longitudinal displacement of the target state has to be considered the safe spacing between vehicles and static obstacles. At present, domestic and foreign researchers proposed three kinds of safe spacing model: (1) the safe spacing calculation model based on the typical braking process, (2) the driver’s preview safe spacing model, and (3) the safe spacing model based on the time distance of vehicles.¹⁴ The safe spacing calculation model based on the typical braking process only considers the traffic safety requirements but not the efficiency of road transport. The result is that the determination of safe spacing using this model is relatively large. The driver’s preview safe spacing model has several problems: low accuracy, cannot adapt to the complex traffic environment, low practicality, and insufficient consideration of the subjective feelings of the driver. The safe spacing model based on the time distance of vehicles not only considers the speed but also considers the distance between vehicles. It is currently accepted by most researchers. Therefore, this article applied the safe spacing model based on the vehicle headway.

According to China’s “highway traffic management approach,” the time distance between vehicles is about 3–4 s. The safe distance between vehicles is

SS = 3 v_{0} + MSS

(13)

where SS is the safe spacing, $v_{0}$ is the vehicle speed, and $MSS$ is the minimum safe spacing. According to the literature,¹⁵ the minimum safe spacing is the speed difference between the front and rear two vehicles multiplied by the time of the lane changing

MSS = v_{0} t_{c}

(14)

The safe spacing of the static obstacle avoidance is therefore

SS = 3 v_{0} + v_{0} t_{c}

(15)

Substituting into the initial and target states and rearranging

[\begin{matrix} x (t_{i}) \\ \overset{\cdot}{x} (t_{i}) \\ \overset{\cdot\cdot}{x} (t_{i}) \\ x (t_{f}) \\ \overset{\cdot}{x} (t_{f}) \\ \overset{\cdot\cdot}{x} (t_{f}) \end{matrix}] = T A^{T}

(16)

[\begin{matrix} y (t_{i}) \\ \overset{\cdot}{y} (t_{i}) \\ \overset{\cdot\cdot}{y} (t_{i}) \\ y (t_{f}) \\ \overset{\cdot}{y} (t_{f}) \\ \overset{\cdot\cdot}{y} (t_{f}) \end{matrix}] = T B^{T}

(17)

where

\begin{matrix} A^{T} = (a_{5}, a_{4}, a_{3}, a_{2}, a_{1}, a_{0}) \\ B^{T} = (b_{5}, b_{4}, b_{3}, b_{2}, b_{1}, b_{0}) \\ T = [\begin{matrix} t_{i}^{5} & t_{i}^{4} & t_{i}^{3} & t_{i}^{2} & t_{i} & 1 \\ 5 t_{i}^{4} & 4 t_{i}^{3} & 3 t_{i}^{2} & 2 t_{i} & 1 & 0 \\ 20 t_{i}^{3} & 12 t_{i}^{2} & 6 t_{i} & 2 & 0 & 0 \\ t_{f}^{5} & t_{f}^{4} & t_{f}^{3} & t_{f}^{2} & t_{f} & 1 \\ 5 t_{f}^{4} & 4 t_{f}^{3} & 3 t_{f}^{2} & 2 t_{f} & 1 & 0 \\ 20 t_{f}^{3} & 12 t_{f}^{2} & 6 t_{f} & 2 & 0 & 0 \end{matrix}] \end{matrix}

(18)

Therefore, the design of the trajectory becomes a problem of satisfying the boundary conditions. $A$ and $B$ were calculated according to the boundary conditions. Finally, the quintic polynomial of $x$ and $y$ was obtained.

Experimental demonstrations

Test data acquisition

The Ray unmanned ground vehicle test platform uses Global Positioning System (GPS) and an inertial navigation system to provide the position and the attitude information of the vehicle (as shown in Figure 3). The driving parameters of Ray’s trajectory $f (x, y)$ were collected by high-precision integrated positioning test technology.

Figure 3.

Ray unmanned ground vehicle test platform.

Quantitative analysis

The lane changing of the static obstacle avoidance is used as an example to illustrate the quantitative analysis process of an unmanned ground vehicle trajectory. We first collect the trajectory of lane changing of Ray when driven by an outstanding driver, as shown in Figure 4.

Figure 4.

Trajectory for obstacle avoidance and lane changing.

The initial state ${\vec{S}}_{i}$ (the initial displacement, initial velocity, and initial acceleration of $x$ and $y$ ) and the target state ${\vec{S}}_{f}$ (the final displacement, initial velocity, and initial acceleration of $x$ and $y$ ) of the static obstacle avoidance are obtained from the outstanding driver. The ideal trajectory of the static obstacle avoidance was planned using equations (16) and (17) based on the quintic polynomial method (the dotted line in Figure 4)

{\vec{S}}_{i} = (x_{i}, {\overset{\cdot}{x}}_{i}, {\overset{\cdot\cdot}{x}}_{i}, y_{i}, {\overset{\cdot}{y}}_{i}, {\overset{\cdot\cdot}{y}}_{i}) = (0, 9, 0, 0, 0, 0)

{\vec{S}}_{f} = (x_{f}, {\overset{\cdot}{x}}_{f}, {\overset{\cdot\cdot}{x}}_{f}, y_{f}, {\overset{\cdot}{y}}_{f}, {\overset{\cdot\cdot}{y}}_{f}) = (72, 9, 0, 3, 0, 0)

This figure shows that the curvature of the ideal trajectory changes continuously; there is no mutation, and the curvature of the start and the end of the lane changing is zero. By comparison with the manned trajectory, we can visually see the curvature of the ideal is smoother.

The actual trajectory of Ray was collected as shown in Figure 5. The deviation time series were obtained by calculating the deviation of the actual trajectory from the ideal trajectory of Ray.

Figure 5.

Actual trajectory of Ray.

The time delay and the embedding dimension were selected for the deviation time series based on the C-C method (Figure 6). Then, the m-dimensional phase space was constructed (Figure 7).

Figure 6.

Time delay of the deviation time series.

Figure 7.

Phase space of the deviation time series.

Finally, the Lyapunov exponent of obstacle avoidance lane changing is calculated. It is 3.3572.

The lane keeping and the overtaking of Ray were quantitatively analyzed using the same method. In Figure 8, the top left shows the ideal trajectory of the lane keeping of Ray, the top right shows the actual trajectory of the lane keeping of Ray, the bottom left shows the time delay of the lane keeping of Ray, and the bottom right shows the phase space reconstruction of the lane keeping of Ray.

Figure 8.

Quantitative analysis of the lane keeping of Ray.

In Figure 9, the top left shows the ideal trajectory of the overtaking of Ray, the top right shows the actual trajectory of the overtaking of Ray, the bottom left shows the time delay of the overtaking of Ray, and the bottom right shows the phase space reconstruction of the overtaking of Ray.

Figure 9.

Quantitative analysis of the overtaking of Ray.

The Lyapunov exponents of the deviation time series of Ray were calculated. The results are shown in Table 1.

Table 1.

Lyapunov exponent of Ray’s trajectories.

Experiment	X deviation	Y deviation	Mean square deviation
Lane keeping	0.8518	1.1275	0.8191
Obstacle avoidance	3.457	3.5772	3.3572
Overtaking	3.5352	3.5849	3.8269

The Lyapunov exponents of the lane keeping, obstacle avoidance, and overtaking of unmanned ground vehicles are positive. This indicates that the processes of lane keeping, obstacle avoidance, and overtaking of unmanned ground vehicles are chaotic. The size of the Lyapunov exponent represents the speed degree of the unmanned ground vehicle’s convergence to the steady-state response. The reciprocal of the Lyapunov exponent represents the maximum predictable time of unmanned ground vehicles. The Lyapunov exponent, the greater the chaos of the system, and the shorter the maximum predictable time, and vice versa. As can be seen from Table 1, the maximum predictable time of the lane keeping of Ray is the longest, and the maximum predictable time of the overtaking is the shortest. It can be seen that the unmanned ground vehicle performed better for the simple environment and the simple task, and it can be quantified by the Lyapunov exponent intuitively.

Conclusion

The trajectory of unmanned ground vehicles was studied using chaos theory. The phase space of the deviation time series, which is the deviation of the actual trajectory from the ideal trajectory, was reconstructed, and then the maximum Lyapunov exponent was calculated to achieve the quantitative analysis of the trajectory of unmanned ground vehicles. If the maximum Lyapunov exponent is greater than 0, it can be judged that the trajectory of the unmanned ground vehicle is chaotic. The chaotic time series analysis method can effectively determine whether the trajectory of the unmanned ground vehicle is chaotic.

Theoretical analysis and experimental results show that the Lyapunov exponent can not only represent the chaos of unmanned ground vehicles but also represent the speed degree of an unmanned ground vehicle’s convergence to the steady-state response. The Lyapunov exponent gives objective and quantitative results.

The quantitative analysis of the trajectory of unmanned ground vehicles can achieve a quantitative evaluation method for unmanned ground vehicles. It can lay a good foundation for improving the test and evaluation system of unmanned ground vehicles and establishing evaluation standards.

Footnotes

Academic Editor: Duc T Pham

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article: This research was supported by the National Natural Science Foundation of China (grant nos 90920304 and 91120010) and the Science and Technology Research Youth Foundation of Hebei Province (grant no. QN2015129).

References

Junqing

Dolan

Litkouhi

. A prediction- and cost function-based algorithm for robust autonomous freeway driving. In: Intelligent Vehicles Symposium (IV), 2010 IEEE, San Diego, CA, 21–24 June 2010. New York: IEEE.

Sun

Xiong

Chen

. A cost function-oriented quantitative evaluation method for unmanned ground vehicles. In: Esa

(eds) Advanced measurement and test. Dürnten: Trans Tech Publication, 2011, pp. 701–706.

Sun

Tao

Xiong

. The fuzzy-AHP evaluation method for unmanned ground vehicles. Appl Math Inf Sci 2013; 7(2): 653–658.

Nehmzow

Walkery

. The behaviour of a mobile robot is chaotic. AISBJ 2003; 1(4): 373–388.

Nehmzow

Walkery

. Quantitative description of robot-environment interaction using chaos theory. Robot Autons Syst 2005; 53; 177–193.

Nehmzow

. Scientific methods in mobile robotics: quantitative analysis of agent behaviour. Beijing, China: China Machine Press, 2010.

Schöner

Dose

. A dynamical systems approach to task-level system integration used to plan and control autonomous vehicle motion. Robot Auton Syst 1992; 10: 253–267.

Schöner

Dose

Engels

. Dynamics of behavior: theory and applications for autonomous robot architectures. Robot Auton Syst 1995; 16: 213–245.

Nehmzow

. Quantitative analysis of robot–environment interaction—towards “scientific mobile robotics.”Robot Auton Syst 2003; 44: 55–68.

10.

Duckett

Nehmzow

Quantitative analysis of mobile robot localisation systems. In: British conference on autonomous mobile robotics and “scientific methods in mobile robotics,” Manchester, 1997, pp.1361–6153.

11.

Zhang

Wang

. UCAV path planning based on FSCABC. Information 2011; 14(3): 687–692.

12.

Zhang

Wang

. UCAV path planning by fitness-scaling adaptive chaotic particle swarm optimization. Math Probl Eng 2013; 2013(1): 147–170.

13.

Chen

. Analysis and application of chaotic time series. Wuhan, China: Wuhan University Press, 2002.

14.

Wang

. Driving assistant system based on ITS. J Jiang Univ 2005; 26(4): 294–297.

15.

You

. Study on autonomous lane changing and autonomous overtaking control method of intelligent vehicle. Changchun, China: Jilin University, 2005.

Quantitative evaluation of unmanned ground vehicle trajectory based on chaos theory

Abstract

Keywords

Foreword

Article structure

Quantitative analysis method

Phase space reconstruction based on the C-C method

Calculate Lyapunov exponent

The ideal trajectory design

Experimental demonstrations

Test data acquisition

Quantitative analysis

Conclusion

Footnotes

Declaration of conflicting interests

Funding

References