Discrete approximations to continuous shortest-path: application to minimum-risk path planning for groups of UAVs

Abstract

This paper addresses the weighted anisotropic shortest-path problem on a continuous domain, i.e., the computation of a path between two points that minimizes the line integral of a cost-weighting function along the path. The cost-weighting depends both on the instantaneous position and direction of motion. We propose an algorithm for the computation of shortest-path that reduces the problem to an optimization over a finite graph. This algorithm restricts the search to paths formed by the concatenation of straight-line segments between points, from a suitably chosen discretization of the continuous region. To maximize efficiency, the discretization of the continuous region should not be uniform. We propose a novel "honeycomb" sampling algorithm that minimizes the cost penalty introduced by discretization. The resulting path is not optimal but the cost penalty can be made arbitrarily small at the expense of increased computation. This methodology is applied to the computation of paths for groups of unmanned air vehicles (UAVs) that minimize the risk of being destroyed by ground defenses. We show that this problem can be formulated as a weighted anisotropic shortest-path optimization and show that the algorithm proposed can efficiently produce low-risk paths.