International Journal of Mobile Computing and Multimedia Communications, 5(3), 19-33, July-September 2013 19
Adaptive Dynamic Path Planning
Algorithm for Interception
of a Moving Target
H. H. Triharminto, Faculty of Information Science and Technology, Universiti Kebangsaan
Malaysia, Bangi, Selangor, Malaysia
A.S. Prabuwono, Faculty 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
N. A. Setiawan, Department of Electrical Engineering and Information Technology, Gadjah
Mada University, Yogyakarta, Indonesia
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 pos-
sibility 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.
Keywords: 3D Curve Dynamic Path Planning, L+Dumo Algorithm, Moving Target, Possibility Quadrants,
Unmanned Aerial Vehicle (UAV)
INTRODUCTION through waypoints to reach the final location.
For developing an autonomous UAV which is
One of the most important parts for establish- able to intercept a target, a path planning has
ing autonomous Unmanned Aerial Vehicle to be set dynamically. The UAV has to be able
(UAV) is the path planning system. A path to create dynamic path planning because UAV
planning system is used to guide the UAV has to change direction in discrete time due to
the movement of the target in air space.
DOI: 10.4018/jmcmc.2013070102
Copyright © 2013, IGI Global. Copying or distributing in print or electronic forms without written permission of IGI Global is prohibited.
20 International Journal of Mobile Computing and Multimedia Communications, 5(3), 19-33, July-September 2013
There are many algorithms to produce The use of evolutionary algorithm is to
UAV’s path planning. A grid based algorithms find an optimal solution from among some
that were applied on camera vision produce possibility of the path planning. In order to
path planning in limited area (Kim & Kim, find the optimal solution, the algorithm iterates
2008; Kim & Crassidis, 2010). The limitation until convergence. Nevertheless, huge num-
area occurs because of capturing capability of bers of iterations are the disadvantages of the
the camera. This algorithm is only used for algorithms for interception of a moving target
tracking or reconnaissance the target but it can- problem. This is due to the UAV has to make
not be used to intercept the target in vast area dynamic path planning to change the direction
scenario. The other grid based algorithms used of movement while seeking the target.
heuristic A* (Qi, Shao, Ping, Hiot, & Leong, Other approaches for path planning
2010; Meng & Gao, 2010; Filippi, Guglieri, & system are based on curve. It was noted that
Quagliotti, 2011) and graph voronoi diagram simple Dubins approach was used to build path
(Liu & Zhang, 2009). Optimal path planning planning (Dubins, 1961; Chitsaz & LaValle,
is obtained by computing all of the waypoint 2007; Hota & Ghose, 2009). Besides Dubins,
iteratively. Consequently, computational time Shanmugavel, Tsordos, and White (2010) de-
of the iteration would be disadvantage. veloped phytagorian hodograph (PH) to make
Beside the grid based algorithm, the path curve path. Dai and Cohran (2009) continued
planning system can also be constructed by the research using cornu spiral as algorithm,
evolutionary algorithms, e.g. Genetic Algorithm which was also based on curve. Shanmugavel
(GA), Particle Swarm Optimization (PSO), et al. extended Dubins algorithm with clothoid
Ant Colony Algorithm (ACA), and Artificial arcs to make curve path smoother than the
Immune Algorithm (AIA). Gao, Fu, Chen and basic Dubins (Shanmugavel, Tsordos, White,
Obermeyer used basic GA as 2D path planning & Zbikowski, 2010). All of these algorithms
algorithm (Gao, Fu, & Chen, 2005; Obermeyer, were very effective for static path planning
2009). In the research, Gao et al. add two op- especially in handling discontinuation problem.
erators in GA that are insertion and deletion. Nonetheless, all of these researches had not used
Zeng, Li, and Xu (2005) used evolutionary the algorithms as dynamic path planning for
algorithm, which had linked list data structure intercepting of moving target. Hence, a curve
in the chromosome. The difference between algorithm was introduced to develop dynamic
evolutionary algorithm research and the original path planning for intercepting such a moving
GA is the addition to the basic GA operators target (Triharminto, Adji, & Setiawan 2011).
(selection, crossover, and mutation). Guoshi, Although the algorithm can generate path
Sujit and Beard produced path planning using which meets kinematic and safety constrains,
PSO (Guoshi, Qiang, & Lejiang, 2010; Sujit & the algorithm cannot adapt for all possibilities
Beard, 2009). Nonetheless, only Guoshi et al. of target position in air space.
solved dynamic path planning problem. Instead In real situations, the UAV has to adapt for
of PSO, Ma et al., Brand et al., Liu and Zang all possibility position of intercepting moving
used ACA and AIA in path planning system target. This research enhances the algorithm
(Ma, Duan, & Liu, 2007; Liu & Zhang, 2010; which was introduced by Triharminto et al. to
Brand, Masuda, Wehner, & Yu 2010). Current encounter the possibility condition23. The result
approach of evolutionary algorithm was differ- of this research is the adaptive algorithm and
ential evolution (DE) algorithm that developed improvement of the accuracy. This paper will
on the framework of GA (Zhang, Chen, Xin, & be organized in several sections. The second
Fang, 2011). However, the entire path planning section gives the scenario. The third section ex-
system using evolutionary algorithm had not plains about the problem formulation. The forth
been used for the interception of a moving target. section describes the solution of the problem.
Copyright © 2013, IGI Global. Copying or distributing in print or electronic forms without written permission of IGI Global is prohibited.
13 more pages are available in the full version of this
document, which may be purchased using the "Add to Cart"
button on the product's webpage:
[Link]/article/adaptive-dynamic-path-planning-
algorithm/80425?camid=4v1
This title is available in InfoSci-Journals, InfoSci-Journal
Disciplines Communications and Social Science, InfoSci-
Select, InfoSci-Select, InfoSci-Communications, Online
Engagement, and Media eJournal Collection, InfoSci-
Networking, Mobile Applications, and Web Technologies
eJournal Collection. Recommend this product to your
librarian:
[Link]/e-resources/library-
recommendation/?id=2
Related Content
An Energy-Efficient Multilevel Clustering Algorithm for Heterogeneous
Wireless Sensor Networks
Surender Soni, Vivek Katiyar and Narottam Chand (2011). International Journal of
Mobile Computing and Multimedia Communications (pp. 62-79).
[Link]/article/energy-efficient-multilevel-clustering-
algorithm/55868?camid=4v1a
Smart Prosthetic Hand with Object Slippage Detection, Measurement, and
Control
Girish Sriram, Alex Jensen and Steve C. Chiu (2014). International Journal of
Handheld Computing Research (pp. 25-48).
[Link]/article/smart-prosthetic-hand-with-object-slippage-
detection-measurement-and-control/135997?camid=4v1a
Managing Students' Attendance using NFC-Enabled Mobile Phones
Media Anugerah Ayu, Barroon Ismaeel Ahmad and Teddy Mantoro (2016). Critical
Socio-Technical Issues Surrounding Mobile Computing (pp. 184-203).
[Link]/chapter/managing-students-attendance-using-nfc-
enabled-mobile-phones/139564?camid=4v1a
United States of America: Renewed Race for Mobile Services
Mats Samuelsson, Nikhilesh Dholakia and Sanjeev Sardana (2009). Mobile
Computing: Concepts, Methodologies, Tools, and Applications (pp. 1331-1343).
[Link]/chapter/united-states-america/26591?camid=4v1a