Skip to main content

Hardware and software acceleration for Hamilton-jacobi reachability analysis

Resource type
Thesis type
(Thesis) M.Sc.
Date created
2021-08-26
Authors/Contributors
Abstract
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.
Document
Extent
44 pages.
Identifier
etd21629
Copyright statement
Copyright is held by the author(s).
Permissions
This thesis may be printed or downloaded for non-commercial research and scholarly purposes.
Supervisor or Senior Supervisor
Thesis advisor: Shriraman, Arrvindh
Thesis advisor: Chen, Mo
Language
English
Member of collection
Download file Size
etd21629.pdf 9.07 MB

Views & downloads - as of June 2023

Views: 36
Downloads: 2