Chair: Ram Vasudevan
Zoom passcode: DEFENSE

Abstract:
Due to their limited sensing horizon, robots construct trajectories in a receding-horizon fashion, where a trajectory defined over a finite time horizon is computed while the robot tracks a previously planned trajectory. This trajectory is constructed by applying an optimization or sampling based method wherein collision checking is performed against obstacles at discrete time instances. Unfortunately this presents an undesirable tradeoff between real-time performance and safety. Reachability-based Trajectory Design (RTD) circumvents this tradeoff by leveraging offline pre-computation of parameterized over-approximations of the robot behavior using Forward Reachable Sets (FRS) thereby achieving safety and real-time operation. To accomplish this objective, RTD represents the full order dynamics of the robot using a reduced-order model, which enables it to apply polynomial-based reachability analysis offline to the reduced-order model while conservatively bounding the difference between the two models. The result is a parameterized over-approximation of the full order robot behavior which can then be used for real-time trajectory design without sacrificing safety. However, RTD suffers from a pair of shortcomings: first, representing the full order dynamics using a reduced order model can introduce undue conservatism that makes it challenging to construct safe, dynamic motion; and second, RTD deals with probabilistic models of the surrounding environment by requiring that any possible behavior (even one with exceedingly small probability) is safe thereby introducing more conservatism. This thesis focuses on illustrating RTD on a walking robot model and addressing the two issues of RTD.

The first contribution of the thesis generalizes the RTD framework to bipedal robots for flat ground walking using the idea of templates and anchors, where `templates' are simplified descriptions of the behavior of the full-order models as `anchors'. Reachability analysis is performed on the template model under the assumption that the difference between the template and anchor can be bounded. Offline-computed polynomial reachable sets are then incorporated into a Model Predictive Control framework to select controllers that result in safe walking on the biped in an online fashion. The second contribution of the thesis improves the RTD framework for autonomous vehicles by designing a novel robust, partial feedback linearization controller and performing zonotope-based reachability analysis on the closed-loop system. Because only the full-order model is involved in the computation of the reachable set, the outer approximation of the FRS using zonotopes is much tighter than existing polynomial-based, traditional RTD approaches. The third contribution of this thesis extends the RTD framework to deal with uncertainty. Consider the challenge of performing motion planning where one is given a Probability Density Function (PDF) description of an obstacle's state. The problem of bounding the risk of collision while performing motion planning can be cast as a chance-constrained program. To address this challenge, the thesis develops a numerical scheme that conservatively approximates the integral of a PDF over FRS and its gradient with respect to a control parameterization. Using this information, one can formulate a chance-constrained RTD approach to real-time risk-averse motion planning.