Elsevier

Aerospace Science and Technology

Volume 49, February 2016, Pages 231-238
Aerospace Science and Technology

Three-dimensional path planning for UCAV using an improved bat algorithm

https://doi.org/10.1016/j.ast.2015.11.040Get rights and content

Abstract

As a challenging high dimension optimization problem, three-dimensional path planning for Uninhabited Combat Air Vehicles (UCAV) mainly centralizes on optimizing the flight route with different types of constrains under complicated combating environments. An improved version of Bat Algorithm (BA) in combination with a Differential Evolution (DE), namely IBA, is proposed to optimize the UCAV three-dimensional path planning problem for the first time. In IBA, DE is required to select the most suitable individual in the bat population. By connecting the selected nodes using the proposed IBA, a safe path is successfully obtained. In addition, B-Spline curves are employed to smoothen the path obtained further and make it practically more feasible for UCAV. The performance of IBA is compared to that of the basic BA on a 3-D UCAV path planning problem. The experimental results demonstrate that IBA is a better technique for UCAV three-dimensional path planning problems compared to the basic BA model.

Introduction

As self-piloted or remotely piloted aircrafts, UCAVs can carry many different types of equipment such as sensors, cameras and communications devices. Because of significant advantages, such vehicles have been successfully used in a wide range of applications involving military and civil areas. UCAV is one of the developing trends of the modern aerial weapon equipment as well. Therefore, studies on UCAV have a great impacts on the battle effectiveness of the air force. UCAV path planning is one of the most technologies in cooperative UCAV combatting and can be considered as a large scale optimization problem with a large number of constraints. Therefore, solving such problems requires effective optimization techniques and consideration of several difficulties involved: constrained, local solutions, and expensive objective function.

Swarm Intelligence (SI) [1] techniques have proven to be very effective for solving challenging optimization problems. Since invention, SI-based algorithms have become very popular compared to conventional optimization techniques in several engineering fields because of their promising performances when solving different kinds of real world optimization problems: parameter estimation, feature selection, neural network training, knapsack problem, and so on. Although SI-based algorithms include a large number of methods, particle swarm optimization (PSO) [2], [3], [4], [5] and ant colony optimization (ACO) [6] are two of the most well-known and widely used ones so far. They are inspired by the social behavior of birds and marking paths via pheromone by ants when searching for food. Recently, inspired by swarm behavior of different animals, several SI-based algorithms have been developed and proposed in the literature such as artificial bee colony (ABC) [7], [8], cuckoo search (CS) [9], [10], [11], [12], [13], bat algorithm (BA) [14], firefly algorithm (FA) [15], [16], ant lion optimizer (ALO) [17], monarch butterfly optimization (MBO) [18], elephant herding optimization (EHO) [19], krill herd (KH) [20], [21], [22], [23], [24], [25], [26], multi-verse optimizer (MVO) [27], dragonfly algorithm (DA) [28], gray wolf optimizer (GWO) [29], and earthworm optimization algorithm (EWA) [30]. These algorithms have been successfully applied to a wide range of real world problems as well. Despite the popularity of these algorithms, there is little in the field of UCAV path planning. The SI-based algorithms have the potential to solve problems of any type subject to the proper formulation. This is the current work, in which BA will be analyzed in detail, improved, and employed to solve UCAV problems.

So far, different kinds of algorithms have been used to solve the UCAV path planning problem such as differential evolution [31], cuckoo search (CS) [32], [33], firefly algorithm (FA) [34], genetic algorithm [35], ant colony optimization algorithm [36] and its variants [37], [38], biogeography-based optimization (BBO) [39], chaotic artificial bee colony [40], and intelligent water drops optimization [41]. However, those methods fail to effectively deal with the contradiction between the excessive information and global optimization.

Differential evolution (DE) [42] was first proposed by Storn and Price in 1995, which is an excellent meta-heuristic for global optimization problems. Since then, this algorithm has attracted a huge number of scholars and engineers. DE requires few control parameters, which makes DE more robust, and easy to implement.

Another recent and well-known algorithm is bat algorithm (BA) [43] that was proposed with mimicking the navigation of bats in nature as a meta-heuristic optimization algorithm. In BA, each artificial bat has the property of a velocity vi, a position (solution) xi, a varying frequency (wavelength), and loudness Ai. A comprehensive review about swarm intelligence including BA is carried out by Parpinelli and Lopes [44].

In 2012 Wang et al. [45] used the basic BA and its variant to solve 2-D path planning problem. However, there is no work in the literature on the application of BA on the 3-D UCAV path planning. To solve UCAV three-dimensional path planning problem more efficiently, in this work, we first equip the BA algorithm with the evolutionary operators of DE to mutate the bats and propose a new hybrid meta-heuristic algorithm. Then, this hybrid (improved BA) algorithm is used to determine the optimal or near-optimal route with complicated multi-constraints. In other works, this work combines the DE algorithm and BA using DE's mutation operator to form the new bat updating strategy in order to reduce the number of exact evaluations of candidate solutions. Note that this proposed algorithm is named Improved BA (IBA) in this work.

Generally speaking, a real UCAV must fly through a smooth path, so different techniques have been used to generate smooth paths. B-Spline curve smoothing strategy is used to optimize the obtained path [32] to assist the BA algorithm. For investigating the effectiveness of IBA, a series of experiments on several simulated and challenging combating environment are conducted.

The structure of the rest of paper is organized as follows. The UCAV three-dimensional path planning problem is mathematically modeled in Section 2. In Section 3, preliminaries and concepts of DE and BA are introduced. Then, the improved BA for path planning problem is proposed in Section 4. Subsequently, the description of a B-Spline curve method is given in Section 5. The simulation experiments are conducted in Section 6. Finally, Section 7 concludes the paper and discusses the future research directions.

Section snippets

Mathematical model of UCAV three-dimensional path planning

Path planning for UCAV refers to the proofs of generating the optimal flight route under the given conditions, and its goal is to find the optimal flight route for UCAV within reasonable time [32]. The mathematical model of UCAV three-dimensional path planning problem is described in the following paragraphs [37].

The UCAV path planning model is shown in Fig. 1. Note that the mission space is divided into 3-D mesh.

In Fig. 1, it is assumed that the UCAV must fly from node S to node D to complete

Differential evolution

The differential evolution (DE) [42] is an evolutionary algorithm (EA) which generates new candidate solutions by combining the parent individual and a few other individuals of the same population. It only accepts the candidate solutions that are better than their parents. DE has few parameters to be adjusted, which makes the implementation and tuning of this algorithm convenient. Due to these advantages, it has many real-world applications, such as job-shop scheduling, multi-objective

Proposed Improved Bat Algorithm (IBA)

In most cases, DE is able to search globally well and locate the global optimal value with a fast speed. However, it is difficult to further improve the solutions at exploitation stage. On the other hand, standard BA is relatively poor at the exploration of the solution. Therefore, in this paper, an improved version by inducing mutation in DE into BA so-called IBA is used to solve the UCAV three-dimensional path planning. The difference between IBA and BA is that the mutation operator is used

Path smoothing strategy

In most cases, the path obtained by meta-heuristic algorithms is usually hard for exact flight. Some techniques are used to further optimize the path obtained [46]. Here, B-Spline curves smoothing strategy is used to dynamically smooth feasible trajectory [47]. B-Spline curves are highly appropriate in the evolutionary procedure because they need a small number of variables to define complicated curved paths.

B-Spline curves are parametric curves, meaning that their construction is based on

Simulation experiments

In this section, the performance of the proposed IBA to UCAV three-dimension path planning is verified by a series of experiments conducted under several challenging combating environments.

To conduct a fair comparison in terms of run times, all the experiments were implemented on a PC with a Pentium IV processor running at 2.0 GHz, 512 MB of RAM and a hard drive of 160 GB. Our implementation was compiled using MATLAB R2012a (7.14) running under Windows XP3. In all experiments, we use the same

Conclusion and future work

This paper proposed an improved version of BA called IBA and employed it to find an optimal path for UCAV three-dimensional path planning problem in difficult combating environments. In IBA, the mutation operator of DE was taken to improve the process of selecting bats during the process of position updating. Since the original BA suffers from local optima entrapment, this mutation-based mechanism promotes exploration, which results in better performance of IBA on 3D path planning for UCAV. For

Conflict of interest statement

There is no conflict of interest.

Acknowledgements

This work was supported by Jiangsu Province Science Foundation for Youths (No. BK20150239) and National Natural Science Foundation of China (No. 61503165).

References (48)

  • H. Duan et al.

    Three-dimension path planning for UCAV using hybrid meta-heuristic ACO-DE algorithm

    Simul. Model. Pract. Theory

    (2010)
  • H.-b. Duan et al.

    Max-min adaptive ant colony optimization approach to multi-uavs coordinated trajectory replanning in dynamic and uncertain environments

    J. Bionics Eng.

    (2009)
  • C. Xu et al.

    Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle (UCAV) path planning

    Aerosp. Sci. Technol.

    (2010)
  • H. Duan et al.

    Novel intelligent water drops optimization approach to single UCAV smooth trajectory planning

    Aerosp. Sci. Technol.

    (2009)
  • T.-Y. Sun et al.

    Intelligent flight task algorithm for unmanned aerial vehicle

    Expert Syst. Appl.

    (2011)
  • Z. Cui et al.

    Theory and applications of swarm intelligence

    Neural Comput. Appl.

    (2012)
  • J. Kennedy et al.

    Particle swarm optimization

  • S. Mirjalili et al.

    Binary optimization using hybrid particle swarm optimization and gravitational search algorithm

    Neural Comput. Appl.

    (2014)
  • G.-G. Wang et al.

    A hybrid method based on krill herd and quantum-behaved particle swarm optimization

    Neural Comput. Appl.

    (2015)
  • G.-G. Wang et al.

    A novel improved accelerated particle swarm optimization algorithm for global numerical optimization

    Eng. Comput.

    (2014)
  • M. Dorigo et al.

    Ant system: optimization by a colony of cooperating agents

    IEEE Trans. Syst. Man Cybern., Part B, Cybern.

    (1996)
  • D. Karaboga et al.

    A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm

    J. Glob. Optim.

    (2007)
  • X. Li et al.

    Parameter estimation for chaotic systems by hybrid differential evolution algorithm and artificial bee colony algorithm

    Nonlinear Dyn.

    (2014)
  • X.-S. Yang et al.

    Cuckoo search: recent advances and applications

    Neural Comput. Appl.

    (2013)
  • Cited by (194)

    • A systematic review on recent advances in autonomous mobile robot navigation

      2023, Engineering Science and Technology, an International Journal
    View all citing articles on Scopus
    View full text