Bridging the Gap Between Safety and Real-Time Performance in\n Receding-Horizon Trajectory Design for Mobile Robots

Abstract

To operate with limited sensor horizons in unpredictable environments,\nautonomous robots use a receding-horizon strategy to plan trajectories, wherein\nthey execute a short plan while creating the next plan. However, creating safe,\ndynamically-feasible trajectories in real time is challenging; and, planners\nmust ensure persistent feasibility, meaning a new trajectory is always\navailable before the previous one has finished executing. Existing approaches\nmake a tradeoff between model complexity and planning speed, which can require\nsacrificing guarantees of safety and dynamic feasibility. This work presents\nthe Reachability-based Trajectory Design (RTD) method for trajectory planning.\nRTD begins with an offline Forward Reachable Set (FRS) computation of a robot's\nmotion when tracking parameterized trajectories; the FRS provably bounds\ntracking error. At runtime, the FRS is used to map obstacles to parameterized\ntrajectories, allowing RTD to select a safe trajectory at every planning\niteration. RTD prescribes an obstacle representation to ensure that obstacle\nconstraints can be created and evaluated in real time while maintaining safety.\nPersistent feasibility is achieved by prescribing a minimum sensor horizon and\na minimum duration for the planned trajectories. A system decomposition\napproach is used to improve the tractability of computing the FRS, allowing RTD\nto create more complex plans at runtime. RTD is compared in simulation with\nRapidly-Exploring Random Trees and Nonlinear Model-Predictive Control. RTD is\nalso demonstrated in randomly-crafted environments on two hardware platforms: a\ndifferential-drive Segway, and a car-like Rover. The proposed method is safe\nand persistently feasible across thousands of simulations and dozens of\nreal-world hardware demos.\n