Title of paper: Enhanced Genetic Path Planning for Autonomous Flight


Authors:

Vincent R. Ragusa, Department of Computer Science, 111 Lake Hollingsworth Drive, Lakeland, FL, 33801, USA, vincent.ragusa.94@gmail.com, +1.863.450.6034

H. David Mathias, Department of Computer Science, 111 Lake Hollingsworth Drive, Lakeland, FL, 33801, USA, hmathias@flsouthern.edu, +1.863.680.6283

Vera A. Kazakova, Department of Computer Science, 4328 Scorpius Street, Orlando, FL, 32816, USA, kazakova@cs.ucf.edu, +1.407.369.3689

Annie S. Wu, Department of Computer Science, 4328 Scorpius Street, Orlando, FL, 32816, USA, aswu@cs.ucf.edu, +1.407.823.5922


Corresponding Author: David Mathias


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-specific 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 beneficial in other domains.


Criteria List: B, D, G

Statement on Criteria:

Criterion B: Robotic path planning has been studied for decades.  Typically, the environments, or maps, are constrained to the point of being artificial.  We present a genetic algorithm that solves complex, continuous, real-world maps with high success.  Though there is not a canonical problem instance to serve as a benchmark, one can compare results based on the difficulty of the maps that can be solved.  

Though there was insufficient space to describe it in the GECCO paper cited below, our algorithm allows for intermediate destinations in addition to the final destination, creating a more complex form of the traveling salesman problem.  In this version of the problem, all destinations must be visited but simply finding an order is insufficient.  Without graph edges to follow, and with obstacles, the algorithm must find a reasonable approximation of an optimal tour.

In experiments, we have included a number of such destinations in a cityscape environment.  This might, for example, represent deliveries to be made by a courier service.  Even with a relatively small number of destinations, it is very difficult for a human user to find an efficient path.

Criterion D: In addition to the significant improvement in realism of the environments, we introduce several novel, domain-specific features.  These include crossover based on the intersection of paths, an operator that pulls a path off of obstacles, and an objective based on the degree to which a path intrudes on obstacles.

Criterion G: There is no doubt that path planning is an important and difficult problem that has been addressed using a wide variety of techniques.  The traveling salesman problem, and numerous variations, are even more widely studied and significant.


Citation:

V. Ragusa, D. Mathias, V. Kazakova, and A. Wu, 2017.  Enhanced Genetic Path Planning for Autonomous Flight.  In Proceedings of the ACM Genetic and Evolutionary Computation Conference (GECCO).  To appear.


Prize Money: Any prize money is to be divided evenly among the co-authors.


Authors’ Statement to the Judges: 

Relevance of problem: While path planning has been of interest for some time, it becomes increasingly so as autonomy becomes more realistic.  Our approach brings evolutionary path planning into the real-world by removing many of the environmental constraints.  The ability to plan effective paths for inputs that include intermediate destinations makes our solution widely applicable.  In addition to testing results in virtual environments, we take the work one step further by also testing evolved paths on a real drone.


Novel approach: It has been shown that thoughtful incorporation of domain specific knowledge is often necessary to truly optimize a genetic algorithm's performance on a given problem.  Our approach introduces several novel, domain-specific features that constitute the basis for the improvements we achieve over previous work.


General Type: Genetic Algorithm