Technical report | Globally Optimal Path Planning with Anisotropic Running Costs

Abstract

There are many diverse numerical methods that can be applied to solving path planning problems, however most of these are either not valid or impractical for solving anisotropic (direction-dependent) path planning problems. Ordered Upwind Methods (OUM) are a family of numerical methods for approximating the viscosity solution of static Hamilton-Jacobi-Bellman equations, and have been tailored to solve anisotropic optimal control problems.

There is little information in the literature regarding the implementation of OUM, and a wide range of computational techniques and meticulous algorithmic considerations are required to successfully implement OUM. A comprehensive, generic implementation of OUM is documented in this report, with the intention of minimising the technical barriers to employing OUM in real-world applications.

Executive Summary

Path planning is the task of selecting a path through an environment for an entity to traverse such that a cost is minimised. Path planning has numerous applications, for example, in robotics, computer game development, and controlling unmanned vehicles.

This report emerged from a study of path planning for military aircraft conducting missions in hostile environments. In this report, an entity is considered to follow a path in Euclidean space and incur a strictly positive running cost at each instant in time. The (total) cost is the integral of the running cost over the path, and the aim is to steer the entity through its environment such that this cost is minimised.

The running cost is considered to be anisotropic, that is, it depends on the position and velocity vector of the entity. Hence for anisotropic path planning problems, the cost depends on the location of the entity in its environment and how it arrived at that location. In applications, anisotropic running costs typically stem from heterogeneous environments, and cases where the orientation of the entity has a significant impact on the cost.

There are many diverse numerical methods that can be applied to solving path planning problems, however most of these are either not valid or impractical for solving anisotropic path planning problems. Ordered Upwind Methods (OUM) are a family of numerical methods for approximating the viscosity solution of static Hamilton-Jacobi-Bellman equations, and have been tailored to solve anisotropic optimal control problems. The focus of this report is on the control-theoretic OUM.

There is little information in the literature regarding the implementation of OUM, and a wide range of computational techniques and meticulous algorithmic considerations are required to successfully implement OUM. A comprehensive, generic implementation of OUM is documented in this report, with the intention of minimising the technical barriers to employing OUM in real-world applications.

The control-theoretic OUM has been employed to solve a number of simple path planning problems in this report, to provide figures with which the reader can compare output from their implementation of the OUM.

The application of OUM to the path planning of military aircraft traversing hostile environments is the subject of a future report.