Enhanced Genetic Path Planning For Autonomous Flight

Keywords

Domain-specific genetic operators; Genetic algorithm; Multiobjective optimization; Speedup technique; Transportation

Abstract

Path planning, the task of finding an obstacle-avoiding, shortest-length route from source to destination is an interesting theoretical problem with numerous applications. We present an improved genetic algorithm for path planning in a continuous, largely unconstrained real-world environment. We introduce a new domain-speciic crossover operator based on path intersections. We also implement a new path correction operator that eliminates obstacle collisions from a path, leading to a dramatic search improvement despite the conceptual simplicity of the correction. Finally, in place of a standard binary measure of obstacle collisions, we present a new optimization objective measuring the degree to which a path intersects obstacles. Due to these improvements, individually and in combination, our algorithm is able to solve scenarios that are considerably more complex and exist in a more general environment than those that appear in the literature. We demonstrate the utility of our system through testing onboard an autonomous micro aerial vehicle. Further, our approach demonstrates the utility of domain-specific genetic operators for path planning. We hypothesize that such operators may be beneicial in other domains.

Publication Date

7-1-2017

Publication Title

GECCO 2017 - Proceedings of the 2017 Genetic and Evolutionary Computation Conference

Number of Pages

1208-1215

Document Type

Article; Proceedings Paper

Personal Identifier

scopus

DOI Link

https://doi.org/10.1145/3071178.3071293

Socpus ID

85026403490 (Scopus)

Source API URL

https://api.elsevier.com/content/abstract/scopus_id/85026403490

This document is currently not available here.

Share

COinS