Development of a multi-resolution parallel genetic algorithm for autonomous robotic path planning

摘要

Deterministic algorithms such as A∗ and D∗ have been applied with great success to autonomous robotic path planning. However, as search space size increases numerous problem domains will likely become intractable when reactive behavior is desired. This is extremely relevant when considering the exponential increase in search space sizes due to any linear addition of degrees of freedom. Over the last few decades, Evolutionary Algorithms (EA) have been shown to be particularly applicable to extremely large search spaces. However, it is often assumed that generational convergence is the only measure of quality for an EA. A novel combination of the Anytime Planning (AP) criteria with multi-resolution search spaces is explored for application to high-level semi-reactive path planning. Separate populations are evolved in parallel within different abstractions of the search space while low cost solutions from each population are exchanged among the populations. Generational evaluations in low-resolution search spaces can be evaluated quickly generating seed candidate solutions that are likely to speed convergence in the high-resolution search spaces. Convergence rates up to 4× were achieved along with modest decreases in path cost. Parallel GPU computation was then applied to allow reactive searching up to 40Hz in search grids up to 8192×8192 cells.