Article Preview
TopIntroduction
One of the most important parts for establishing autonomous Unmanned Aerial Vehicle (UAV) is the path planning system. A path planning system is used to guide the UAV through waypoints to reach the final location. For developing an autonomous UAV which is able to intercept a target, a path planning has to be set dynamically. The UAV has to be able to create dynamic path planning because UAV has to change direction in discrete time due to the movement of the target in air space.
There are many algorithms to produce UAV’s path planning. A grid based algorithms that were applied on camera vision produce path planning in limited area (Kim & Kim, 2008; Kim & Crassidis, 2010). The limitation area occurs because of capturing capability of the camera. This algorithm is only used for tracking or reconnaissance the target but it cannot be used to intercept the target in vast area scenario. The other grid based algorithms used heuristic A* (Qi, Shao, Ping, Hiot, & Leong, 2010; Meng & Gao, 2010; Filippi, Guglieri, & Quagliotti, 2011) and graph voronoi diagram (Liu & Zhang, 2009). Optimal path planning is obtained by computing all of the waypoint iteratively. Consequently, computational time of the iteration would be disadvantage.
Beside the grid based algorithm, the path planning system can also be constructed by evolutionary algorithms, e.g. Genetic Algorithm (GA), Particle Swarm Optimization (PSO), Ant Colony Algorithm (ACA), and Artificial Immune Algorithm (AIA). Gao, Fu, Chen and Obermeyer used basic GA as 2D path planning algorithm (Gao, Fu, & Chen, 2005; Obermeyer, 2009). In the research, Gao et al. add two operators in GA that are insertion and deletion. Zeng, Li, and Xu (2005) used evolutionary algorithm, which had linked list data structure in the chromosome. The difference between evolutionary algorithm research and the original GA is the addition to the basic GA operators (selection, crossover, and mutation). Guoshi, Sujit and Beard produced path planning using PSO (Guoshi, Qiang, & Lejiang, 2010; Sujit & Beard, 2009). Nonetheless, only Guoshi et al. solved dynamic path planning problem. Instead of PSO, Ma et al., Brand et al., Liu and Zang used ACA and AIA in path planning system (Ma, Duan, & Liu, 2007; Liu & Zhang, 2010; Brand, Masuda, Wehner, & Yu 2010). Current approach of evolutionary algorithm was differential evolution (DE) algorithm that developed on the framework of GA (Zhang, Chen, Xin, & Fang, 2011). However, the entire path planning system using evolutionary algorithm had not been used for the interception of a moving target.
The use of evolutionary algorithm is to find an optimal solution from among some possibility of the path planning. In order to find the optimal solution, the algorithm iterates until convergence. Nevertheless, huge numbers of iterations are the disadvantages of the algorithms for interception of a moving target problem. This is due to the UAV has to make dynamic path planning to change the direction of movement while seeking the target.