Reachability-based Trajectory Design

Abstract

Autonomous mobile robots have the potential to increase the availability and accessibility of goods and services throughout society. However, to enable public trust in such systems, it is critical to certify that they are safe. This requires formally specifying safety, and designing motion planning methods that can guarantee safe operation (note, this work is only concerned with planning, not perception).

The typical paradigm to attempt to ensure safety is receding-horizon planning, wherein a robot creates a short plan, then executes it while creating its next short plan in an iterative fashion, allowing a robot to incorporate new sensor information over time. However, this requires a robot to plan in real time. Therefore, the key challenge in making safety guarantees lies in balancing performance (how quickly a robot can plan) and conservatism (how cautiously a robot behaves). Existing methods suffer from a tradeoff between performance and conservatism, which is rooted in the choice of model used describe a robot; accuracy typically comes at the price of computation speed.

To address this challenge, this dissertation proposes Reachability-based Trajectory Design (RTD), which performs real-time, receding-horizon planning with a simplified planning model, and ensures safety by describing the model error using a reachable set of the robot.

RTD begins with the offline design of a continuum of parameterized trajectories for the plan- ning model; each trajectory ends with a fail-safe maneuver such as braking to a stop. RTD then computes the robot’s Forward Reachable Set (FRS), which contains all points in workspace reach- able by the robot for each parameterized trajectory. Importantly, the FRS also contains the error model, since a robot can typically never track planned trajectories perfectly. Online (at runtime), the robot intersects the FRS with sensed obstacles to provably determine which trajectory plans could cause collisions. Then, the robot performs trajectory optimization over the remaining safe trajectories. If no new safe plan can be found, the robot can execute its previously-found fail-safe maneuver, enabling perpetual safety.

This dissertation begins by presenting RTD as a theoretical framework, then presents three representations of a robot’s FRS, using (1) sums-of-squares (SOS) polynomial programming, (2) zonotopes (a special type of convex polytope), and (3) rotatotopes (a generalization of zonotopes that enable representing a robot’s swept volume). To enable real-time planning, this work also de- velops an obstacle representation that enables provable safety while treating obstacles as discrete, finite sets of points. The practicality of RTD is demonstrated on four different wheeled robots (using the SOS FRS), two quadrotor aerial robots (using the zonotope FRS), and one manipulator robot (using the rotatotope FRS). Over thousands of simulations and dozens of hardware trials, RTD performs safe, real-time planning in arbitrary and challenging environments.

In summary, this dissertation proposes RTD as a general purpose, practical framework for provably safe, real-time robot motion planning.