Hardware and software acceleration for Hamilton-jacobi reachability analysis

Hamilton-Jacobi (HJ) reachability analysis is a powerful technique with applications in robotic safety, game theory. etc. HJ reachability analysis is advantageous in analyzing nonlinear systems with disturbances and flexible set representations. A drawback to this approach is that the associated Partial Differential Equation (PDE) is solved numerically on a multidimensional grid, hence scales poorly as the number of dimensions increases. There has been an extensive body of work that addresses the computational complexity reduction of the problem with or without introducing overapproximation. In this thesis, without changing the numerical solution approach, we address the speedup of solving HJ PDE using software and hardware acceleration. Our first contribution is OptimizedDP, a python-based software toolbox optimized for dynamic programming algorithms arising in optimal control and reinforcement learning. The software toolbox reduces computational time ranging from 7x-75x compared to common toolboxes written in MATLAB and implementation in Python. Our second contribution is a customized hardware design that accelerates HJ PDE solving procedure on a Field Programmable Gate Array (FPGA). The design can accelerate 4D grid-based HJ reachability analysis up to 14 times compared to OptimizedDP and 103 times compared to the existing MATLAB toolbox on a 16-thread machine. The methodology presented here is without loss of generality: it can potentially be applied to different systems dynamics, and moreover, leveraged for higher dimensional systems. In addition, we experiment online HJ PDE solving algorithm, using on-cloud FPGA, on a robot car that can safely avoid obstacles.