UC Merced

In this dissertation I present new GPU-based approaches for addressing path planning and multi-agent navigation problems. The proposed methods rely on GPU rasterization techniques to construct navigation structures which allow us to address these problems in novel ways.

There are three main contributions described in this document.

The first is a new method for computing Shortest Path Maps (SPMs) for generic 2D polygonal environments. By making use of GPU shaders an approach is presented to implement the continuous Dijkstra’s wavefront propagation method, resulting in an SPM representation in a GPU’s buffer which can efficiently give a globally optimal shortest path between any point in the environment and the considered source point. The proposed shader-based approach also allows several extensions to be incorporated: multiple source points, multiple source segments, and the incorporation of weights that can alter the wavefront propagation in order to model velocity changes at vertices. These extensions allow SPMs to address a large range of real-world situations.

The second contribution addresses the global coordination of multiple agents flowing from source to sink edges in a polygonal environment. The same GPU-based SPM methods are extended to compute a Continuous Max Flow in the input environment, which can be used to guide agents through the environment from source edges to sink edges, leading to a flow representation stored in the frame buffer of the GPU. A method for extracting flow lanes respecting clearance constraints is also presented, achieving the maximum possible number of lanes to route agents across an environment without ever creating bottlenecks.

In order to address decentralized autonomous agents, the third contribution presents a new method for dynamically detecting and representing in SPMs regions where agents are bottlenecked. The incorporation of weighted barriers are proposed to model the corresponding time delays in corridors of the SPMs, in order to provide agents with alternative paths avoiding bottlenecks. In this way, a novel type of SPM is defined, providing optimal solutions from weights which reflect dynamic delays in the corridors of the environments.

The methods proposed in this dissertation present novel approaches for addressing optimal paths and agent distribution in planar environments. Given the continuous development of high-performance GPUs, the proposed methods have the potential to open new avenues for the development of efficient navigation algorithms and representations.