PARALLEL IMPLEMENTATION AND COMPARISON OF TWO UAV PATH PLANNING ALGORITHMS

Vincent Roberge, Mohammed Tarbouchi, Gilles Labonté

2011

Abstract

The development of autonomous Unmanned Aerial Vehicles (UAVs) is of high interest to many governmental and military organizations around the world. An essential aspect of UAV autonomy is the ability for automatic path planning. In this paper, we use the genetic algorithm (GA) and the particle swarm optimization algorithm (PSO) to cope with the complexity of the problem and compute feasible and quasi-optimal trajectories for fixed wing UAVs in a complex 3D environment while considering the dynamic properties of the vehicle. The characteristics of the optimal path are represented in the form of a multi-objective cost function that we developed. The paths produced are composed of line segments, circular arcs and vertical helices. We reduce the execution time of our solutions by using the “single-program, multiple-data” parallel programming paradigm and we achieve real-time performance on standard COTS multi-core CPUs. After achieving a quasi-linear speedup of 7.3 on 8 cores and an execution time of 10 s for both algorithms, we conclude that by using a parallel implementation on standard multicore CPUs, real-time path planning for UAVs is possible. Moreover, our rigorous comparison of the two algorithms shows, with statistical significance, that the GA produces superior trajectories to the PSO.

Paper Citation

in Harvard Style

Roberge V., Tarbouchi M. and Labonté G. (2011). PARALLEL IMPLEMENTATION AND COMPARISON OF TWO UAV PATH PLANNING ALGORITHMS . In Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011) ISBN 978-989-8425-83-6, pages 162-167. DOI: 10.5220/0003663501620167

in Bibtex Style

@conference{ecta11,
author={Vincent Roberge and Mohammed Tarbouchi and Gilles Labonté},
title={PARALLEL IMPLEMENTATION AND COMPARISON OF TWO UAV PATH PLANNING ALGORITHMS},
booktitle={Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011)},
year={2011},
pages={162-167},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0003663501620167},
isbn={978-989-8425-83-6},
}

in EndNote Style

TY - CONF
JO - Proceedings of the International Conference on Evolutionary Computation Theory and Applications - Volume 1: ECTA, (IJCCI 2011)
TI - PARALLEL IMPLEMENTATION AND COMPARISON OF TWO UAV PATH PLANNING ALGORITHMS
SN - 978-989-8425-83-6
AU - Roberge V.
AU - Tarbouchi M.
AU - Labonté G.
PY - 2011
SP - 162
EP - 167
DO - 10.5220/0003663501620167