Concurrent dynamic programming for grid-based optimisation problems

Abstract

A particular class of optimisation problems can be solved using a technique known as dynamic programming. This technique applies to problems that have many possible solutions, each consisting of a number of individual decision points. In theory, a globally optimal solution relative to a given metric can be obtained by recursively choosing the most optimal option at each decision point. In practice, however, applications of dynamic programming are computationally expensive for the scale of real-world domains.

This thesis examines the existing array of robot motion planning algorithms and applications, a core application of dynamic programming for ground and aerial vehicles. In particular, the thesis highlights that the sequential nature of traditional algorithms does not scale in practice as modern central processing units begin to reach physical limits in terms of computational throughput. This thesis then outlines current parallel processing unit architectures that have emerged in the last decade with particular focus on graphical processing units.

The main contribution of this thesis is a new class of concurrent dynamic programming algorithms that are applicable to multi-core processor architectures. The core mechanic of the algorithms is proven to generate an equally optimal global solution to existing sequential algorithms, with a computational complexity of O(n), assuming enough cores are available relative to the problem size. Various implementation flavours are developed and benchmarked over a variety of two-dimensional configuration spaces, with the most efficient being able to plan on the scale of the main campus of the University of New South Wales (a 1000m x 500m area) with 1m x 1m resolution in sub-second time.

Higher dimensional configuration spaces are also investigated with a proof-of-concept experiment presented to assess the feasibility and performance as the dimensionality increases --- a factor notorious in traditional approaches that increases the computational complexity exponentially. The work presented here gains an increased concurrent benefit as the dimensionality of the problem increases and hence is able to perform an order of magnitude more efficiently in the presented three-dimensional experiments.

Designing concurrent algorithms can be more difficult, but the implementation benefits will continue to increase as the level of parallelism found in modern hardware approaches that found in nature.