An evolution based path planning algorithm for autonomous motion of a UAV through uncertain environments
Authors:
- D. RathbunDRD. Rathbun
- S. KragelundSKS. Kragelund
- A. PongpunwattanaAPA. Pongpunwattana
- B. CapozziBCB. Capozzi
- 26 June 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- Vol. 2, 8D2-1
Abstract
Adaptive and intelligent on-board path planning is a required part of a fully autonomous UAV. In controlled airspace, such a UAV would have to interact with other vehicles moving though its environment. The locations of obstacles (other vehicles) that form obstructions in the environment may only be known with limited accuracy. Evolutionary algorithms (EA) have been successfully used to compute near-optimal paths through obstructed, dynamically changing environments. Explicitly accounting for the uncertainty of the obstacles can result in the survival of "best" paths which differ from those that would be favored in a purely deterministic environment. In this paper, we consider the application of evolution-based path planning to the motion of an unmanned air vehicle (UAV) through a field of obstacles at uncertain locations. We begin with the static form of the EA algorithm for generating a path at a single point in time. We describe the algorithm and show its behavior, specifically how it responds differently based on the known accuracy of the predictions of the environment. We then show how the static structure can be extended to consider the uncertainties which change with time. We demonstrate by application to path planning through a field of moving obstacles whose future motion is uncertain.Keywords
This publication has 8 references indexed in Scilit:
- Optimal and efficient path planning for partially-known environments2002
- Optimal routing of multiple autonomous underwater vehicles through evolutionary programming2002
- Evolutionary Approaches to Path Planning Through Uncertain Environments2002
- Evolving (semi)-autonomous vehicles2001
- Markov Localization for Mobile Robots in Dynamic EnvironmentsJournal of Artificial Intelligence Research, 1999
- Genetic algorithm to solve constrained routing problem with applications for cruise missile routing1998
- Adaptive evolutionary planner/navigator for mobile robotsIEEE Transactions on Evolutionary Computation, 1997
- Real-Time Obstacle Avoidance for Manipulators and Mobile RobotsThe International Journal of Robotics Research, 1986