Goal-Reaching Trajectory Design Near Danger with

Piecewise Affine Reach-avoid Computation

Long Kiu Chung*, Wonsuhk Jung*, Chuizheng Kong, Shreyas Kousik

RSS 2024

• Link
• GitHub
• YouTube

Be safe and reach a goal, even with extreme dynamics!

---

---

Guaranteed Goal-Reaching and Collision Avoidance

PARC computes guaranteed safe trajectories across a continuum of initial conditions and trajectory parameters.

---

What actually matters for safe goal reaching?

Once PARC finds a non-empty Backward Reach-Avoid Set (BRAS), the agent has a 100% success rate of goal-reaching and collision avoidance when tracking any trajectories generated from the BRAS. We find three key concepts are needed for these guarantees: (1) collaborative planner-tracker behavior, (2) low numerical approximation error, and (3) careful representation of realistic robot motion plans.

---

Preliminary Results on Hardware

This TurtleBot effort was part of a class project. We are setting up an F1tenth vehicle (driven manually for now) to perform more dynamic and exciting maneuvers.

---

Abstract

Autonomous mobile robots must maintain safety, but should not sacrifice performance, leading to the classical reach-avoid problem. This paper seeks to compute trajectory plans for which a robot is guaranteed to reach a goal and to avoid obstacles in the specific near danger case, also known as a narrow gap, where the agent starts near the goal, but must navigate through tight obstacles that block its path. The proposed method builds off of a common approach of using a simplified planning model to generate plans, which are then tracked using a high-fidelity tracking model and controller. Existing safe planning approaches use reachability analysis to overapproximate the error between these models, but this introduces additional numerical approximation error and thereby conservativeness that prevents goal reaching. The present work instead proposes a Piecewise Affine Reach-avoid Computation (PARC) method to tightly approximate the reachable set of the planning model. PARC significantly reduces conservativeness through a careful choice of the planning model and set representation, along with an effective approach to handling time-varying tracking errors. The utility of this method is demonstrated through extensive numerical experiments in which PARC outperforms state-of-the-art reach avoid methods in near-danger goal reaching. Furthermore, in a simulated demonstration, PARC enables generation of provably-safe extreme vehicle dynamics drift parking maneuvers. A preliminary hardware demo on a TurtleBot3 also validates the method.

---

BibTeX

@inproceedings{chung2024goal, 
    author    = {Chung, Long Kiu and Jung, Wonsuhk and Kong, Chuizheng and Kousik, Shreyas},
    title     = {Goal-Reaching Trajectory Design Near Danger with Piecewise Affine Reach-avoid Computation}, 
    booktitle = {Proceedings of Robotics: Science and Systems}, 
    year      = {2024}, 
    address   = {Delft, Netherlands}, 
    month     = {July}, 
    doi       = {10.15607/RSS.2024.XX.117} 
}