Adaptive Dynamic Path Planning Algorithm for Interception of a Moving Target

Adaptive Dynamic Path Planning Algorithm for Interception of a Moving Target

H. H. Triharminto (Department of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi, Selangor, Malaysia), A.S. Prabuwono (Department of Information Science and Technology, Universiti Kebangsaan Malaysia, Bangi, Selangor, Malaysia), T. B. Adji (Department of Electrical Engineering and Information Technology, Gadjah Mada University, Yogyakarta, Indonesia) and N. A. Setiawan (Department of Electrical Engineering and Information Technology, Gadjah Mada University, Yogyakarta, Indonesia)
DOI: 10.4018/jmcmc.2013070102
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

Most of the 3D curve path planning is used to build static path planning. For intercepting of a moving target, the path planning has to be set in a dynamic condition. L+Dumo algorithm which is based on curve is used to intercept a moving target. In the real situations, the Unmanned Aerial Vehicle (UAV) has possibility to intercept a moving target from all direction. It is assumed that environment of the UAV is in 3D Euclidean Space. It means that the UAV has to adapt for all quadrants for interception of a moving target. This research develops a path planning algorithm which enhances the previous L+Dumo algorithm to encounter the possibility quadrants. The enhancement would be simulated in C++ language to determine the accuracy of the algorithm. The simulation is conducted using one UAV and one moving target with random obstacles of cylindrical shape in between both objects. The result shows that the system accuracy is 81.0876%, a level which is able to encounter all possibility quadrants.
Article Preview

Introduction

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.

Complete Article List

Search this Journal:
Reset
Open Access Articles: Forthcoming
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2014)
Volume 5: 4 Issues (2013)
Volume 4: 4 Issues (2012)
Volume 3: 4 Issues (2011)
Volume 2: 4 Issues (2010)
Volume 1: 4 Issues (2009)
View Complete Journal Contents Listing