Page 122 - Innovations in Intelligent Machines

Evolution-based Dynamic Path Planning
for Autonomous Vehicles

Anawat Pongpunwattana and Rolf Rysdyk

Autonomous Flight Systems Laboratory
University of Washington, Seattle, WA 98195

Planning is an essential element of autonomous systems. This work presents
a dynamic path planning algorithm for an unmanned autonomous vehicle
to execute a set of assigned tasks in a changing environment. This problem
comprises path planning and task sequencing. The approach adopted here
is to solve these subproblems simultaneously using an evolutionary planning
algorithm and a stochastic model of the environment. During the mission,
the planner replans and adapts the path in response to changes in the envi-
ronment. Simulation results demonstrate that the path planning algorithm
can compute feasible effective solutions to path planning problems. These
include planning with timing constraints and dynamic planning with moving
targets and obstacles. The vehicle is able to autonomously travel from the
initial location to the goal location while avoiding obstacles and performing
the assigned tasks.

1 Introduction

The path planning algorithm presented here was developed as a part of the
Evolution-based Cooperative Planning System (ECoPS) [19]. The ECoPS
is a distributed system for real-time task and path planning for a team of
autonomous vehicles. The planning algorithms are based on the combina-
tion of a market-based planning architecture and optimization techniques
called Evolutionary Computation (EC). The planning system was success-
fully demonstrated for the Defense Advanced Research Projects Agency
under the Mixed Initiative Control of Automa-teams program. In related
work, it is scheduled for flight testing on Seascan Unmanned Aerial Vehicles
(UAVs) manufactured by The Insitu Group in combination with autonomous
Unmanned Surfaces Vehicles (USVs), see Figure 1.
The overall goal of this work is to increase autonomy of unmanned vechi-
cles. A vehicle is called autonomous if it has the ability to plan its own actions
using the acquired information about its environment to accomplish its tasks.

A. Pongpunwattana and R. Rysdyk: Evolution-based Dynamic Path Planning for Autonomous
Vehicles, Studies in Computational Intelligence (SCI) 70, 113–145 (2007)
www.springerlink.com c Springer-Verlag Berlin Heidelberg 2007