Showing 1–18 of 18 results for author: Kousik, S

Socially Acceptable Bipedal Robot Navigation via Social Zonotope Network Model Predictive Control

Authors: Abdulaziz Shamsah, Krishanu Agarwal, Nigam Katta, Abirath Raju, Shreyas Kousik, Ye Zhao

Abstract: This study addresses the challenge of social bipedal navigation in a dynamic, human-crowded environment, a research area largely underexplored in legged robot navigation. We present a zonotope-based framework that couples prediction and motion planning for a bipedal ego-agent to account for bidirectional influence with the surrounding pedestrians. This framework incorporates a Social Zonotope Netw… ▽ More This study addresses the challenge of social bipedal navigation in a dynamic, human-crowded environment, a research area largely underexplored in legged robot navigation. We present a zonotope-based framework that couples prediction and motion planning for a bipedal ego-agent to account for bidirectional influence with the surrounding pedestrians. This framework incorporates a Social Zonotope Network (SZN), a neural network that predicts future pedestrian reachable sets and plans future socially acceptable reachable set for the ego-agent. SZN generates the reachable sets as zonotopes for efficient reachability-based planning, collision checking, and online uncertainty parameterization. Locomotion-specific losses are added to the SZN training process to adhere to the dynamic limits of the bipedal robot that are not explicitly present in the human crowds data set. These loss functions enable the SZN to generate locomotion paths that are more dynamically feasible for improved tracking. SZN is integrated with a Model Predictive Controller (SZN-MPC) for footstep planning for our bipedal robot Digit. SZN-MPC solves for collision-free trajectory by optimizing through SZN's gradients. and Our results demonstrate the framework's effectiveness in producing a socially acceptable path, with consistent locomotion velocity, and optimality. The SZN-MPC framework is validated with extensive simulations and hardware experiments. △ Less

Submitted 24 June, 2024; originally announced June 2024.

Comments: 19 pages, 19 figures. arXiv admin note: text overlap with arXiv:2403.16485, arXiv:2310.09969

ZAPP! Zonotope Agreement of Prediction and Planning for Continuous-Time Collision Avoidance with Discrete-Time Dynamics

Authors: Luca Paparusso, Shreyas Kousik, Edward Schmerling, Francesco Braghin, Marco Pavone

Abstract: The past few years have seen immense progress on two fronts that are critical to safe, widespread mobile robot deployment: predicting uncertain motion of multiple agents, and planning robot motion under uncertainty. However, the numerical methods required on each front have resulted in a mismatch of representation for prediction and planning. In prediction, numerical tractability is usually achiev… ▽ More The past few years have seen immense progress on two fronts that are critical to safe, widespread mobile robot deployment: predicting uncertain motion of multiple agents, and planning robot motion under uncertainty. However, the numerical methods required on each front have resulted in a mismatch of representation for prediction and planning. In prediction, numerical tractability is usually achieved by coarsely discretizing time, and by representing multimodal multi-agent interactions as distributions with infinite support. On the other hand, safe planning typically requires very fine time discretization, paired with distributions with compact support, to reduce conservativeness and ensure numerical tractability. The result is, when existing predictors are coupled with planning and control, one may often find unsafe motion plans. This paper proposes ZAPP (Zonotope Agreement of Prediction and Planning) to resolve the representation mismatch. ZAPP unites a prediction-friendly coarse time discretization and a planning-friendly zonotope uncertainty representation; the method also enables differentiating through a zonotope collision check, allowing one to integrate prediction and planning within a gradient-based optimization framework. Numerical examples show how ZAPP can produce safer trajectories compared to baselines in interactive scenes. △ Less

Submitted 3 June, 2024; originally announced June 2024.

Comments: 8 pages, 3 figures, 1 table, submitted to 2024 IEEE International Conference on Robotics and Automation (ICRA)

Real-time Model Predictive Control with Zonotope-Based Neural Networks for Bipedal Social Navigation

Authors: Abdulaziz Shamsah, Krishanu Agarwal, Shreyas Kousik, Ye Zhao

Abstract: This study addresses the challenge of bipedal navigation in a dynamic human-crowded environment, a research area that remains largely underexplored in the field of legged navigation. We propose two cascaded zonotope-based neural networks: a Pedestrian Prediction Network (PPN) for pedestrians' future trajectory prediction and an Ego-agent Social Network (ESN) for ego-agent social path planning. Rep… ▽ More This study addresses the challenge of bipedal navigation in a dynamic human-crowded environment, a research area that remains largely underexplored in the field of legged navigation. We propose two cascaded zonotope-based neural networks: a Pedestrian Prediction Network (PPN) for pedestrians' future trajectory prediction and an Ego-agent Social Network (ESN) for ego-agent social path planning. Representing future paths as zonotopes allows for efficient reachability-based planning and collision checking. The ESN is then integrated with a Model Predictive Controller (ESN-MPC) for footstep planning for our bipedal robot Digit designed by Agility Robotics. ESN-MPC solves for a collision-free optimal trajectory by optimizing through the gradients of ESN. ESN-MPC optimal trajectory is sent to the low-level controller for full-order simulation of Digit. The overall proposed framework is validated with extensive simulations on randomly generated initial settings with varying human crowd densities. △ Less

Submitted 25 March, 2024; originally announced March 2024.

Comments: 8 pages, 9 figures

Mapping High-level Semantic Regions in Indoor Environments without Object Recognition

Authors: Roberto Bigazzi, Lorenzo Baraldi, Shreyas Kousik, Rita Cucchiara, Marco Pavone

Abstract: Robots require a semantic understanding of their surroundings to operate in an efficient and explainable way in human environments. In the literature, there has been an extensive focus on object labeling and exhaustive scene graph generation; less effort has been focused on the task of purely identifying and mapping large semantic regions. The present work proposes a method for semantic region map… ▽ More Robots require a semantic understanding of their surroundings to operate in an efficient and explainable way in human environments. In the literature, there has been an extensive focus on object labeling and exhaustive scene graph generation; less effort has been focused on the task of purely identifying and mapping large semantic regions. The present work proposes a method for semantic region mapping via embodied navigation in indoor environments, generating a high-level representation of the knowledge of the agent. To enable region identification, the method uses a vision-to-language model to provide scene information for mapping. By projecting egocentric scene understanding into the global frame, the proposed method generates a semantic map as a distribution over possible region labels at each location. This mapping procedure is paired with a trained navigation policy to enable autonomous map generation. The proposed method significantly outperforms a variety of baselines, including an object-based system and a pretrained scene classifier, in experiments in a photorealistic simulator. △ Less

Submitted 11 March, 2024; originally announced March 2024.

Comments: Accepted by IEEE International Conference on Robotics and Automation (ICRA 2024)

Goal-Reaching Trajectory Design Near Danger with Piecewise Affine Reach-avoid Computation

Authors: Long Kiu Chung, Wonsuhk Jung, Chuizheng Kong, Shreyas Kousik

Abstract: Autonomous mobile robots must maintain safety, but should not sacrifice performance, leading to the classical reach-avoid problem: find a trajectory that is guaranteed to reach a goal and avoid obstacles. This paper addresses the 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 bui… ▽ More Autonomous mobile robots must maintain safety, but should not sacrifice performance, leading to the classical reach-avoid problem: find a trajectory that is guaranteed to reach a goal and avoid obstacles. This paper addresses the 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 the common approach of using a simplified planning model to generate plans, which are then tracked using a high-fidelity tracking model and controller. Existing approaches use reachability analysis to overapproximate the error between these models and ensure safety, but doing so introduces numerical approximation error 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 the generation of provably-safe extreme vehicle dynamics drift parking maneuvers. A preliminary hardware demo on a TurtleBot3 also validates the method. △ Less

Submitted 28 May, 2024; v1 submitted 23 February, 2024; originally announced February 2024.

Comments: The first two authors contributed equally to the work. This work has been submitted for possible publication. Copyright may be transferred without notice, after which this version may no longer be accessible

Connected Autonomous Vehicle Motion Planning with Video Predictions from Smart, Self-Supervised Infrastructure

Authors: Jiankai Sun, Shreyas Kousik, David Fridovich-Keil, Mac Schwager

Abstract: Connected autonomous vehicles (CAVs) promise to enhance safety, efficiency, and sustainability in urban transportation. However, this is contingent upon a CAV correctly predicting the motion of surrounding agents and planning its own motion safely. Doing so is challenging in complex urban environments due to frequent occlusions and interactions among many agents. One solution is to leverage smart… ▽ More Connected autonomous vehicles (CAVs) promise to enhance safety, efficiency, and sustainability in urban transportation. However, this is contingent upon a CAV correctly predicting the motion of surrounding agents and planning its own motion safely. Doing so is challenging in complex urban environments due to frequent occlusions and interactions among many agents. One solution is to leverage smart infrastructure to augment a CAV's situational awareness; the present work leverages a recently proposed "Self-Supervised Traffic Advisor" (SSTA) framework of smart sensors that teach themselves to generate and broadcast useful video predictions of road users. In this work, SSTA predictions are modified to predict future occupancy instead of raw video, which reduces the data footprint of broadcast predictions. The resulting predictions are used within a planning framework, demonstrating that this design can effectively aid CAV motion planning. A variety of numerical experiments study the key factors that make SSTA outputs useful for practical CAV planning in crowded urban environments. △ Less

Submitted 14 September, 2023; originally announced September 2023.

Comments: 2023 IEEE 26th International Conference on Intelligent Transportation Systems (ITSC)

Can't Touch This: Real-Time, Safe Motion Planning and Control for Manipulators Under Uncertainty

Authors: Jonathan Michaux, Patrick Holmes, Bohao Zhang, Che Chen, Baiyue Wang, Shrey Sahgal, Tiancheng Zhang, Sidhartha Dey, Shreyas Kousik, Ram Vasudevan

Abstract: Ensuring safe, real-time motion planning in arbitrary environments requires a robotic manipulator to avoid collisions, obey joint limits, and account for uncertainties in the mass and inertia of objects and the robot itself. This paper proposes Autonomous Robust Manipulation via Optimization with Uncertainty-aware Reachability (ARMOUR), a provably-safe, receding-horizon trajectory planner and trac… ▽ More Ensuring safe, real-time motion planning in arbitrary environments requires a robotic manipulator to avoid collisions, obey joint limits, and account for uncertainties in the mass and inertia of objects and the robot itself. This paper proposes Autonomous Robust Manipulation via Optimization with Uncertainty-aware Reachability (ARMOUR), a provably-safe, receding-horizon trajectory planner and tracking controller framework for robotic manipulators to address these challenges. ARMOUR first constructs a robust controller that tracks desired trajectories with bounded error despite uncertain dynamics. ARMOUR then uses a novel recursive Newton-Euler method to compute all inputs required to track any trajectory within a continuum of desired trajectories. Finally, ARMOUR over-approximates the swept volume of the manipulator; this enables one to formulate an optimization problem that can be solved in real-time to synthesize provably-safe motions. This paper compares ARMOUR to state of the art methods on a set of challenging manipulation examples in simulation and demonstrates its ability to ensure safety on real hardware in the presence of model uncertainty without sacrificing performance. Project page: https://roahmlab.github.io/armour/. △ Less

Submitted 1 November, 2023; v1 submitted 30 January, 2023; originally announced January 2023.

Comments: 20 pages, 6 figures

Set-Valued Shadow Matching Using Zonotopes for 3-D Map-Aided GNSS Localization

Authors: Sriramya Bhamidipati, Shreyas Kousik, Grace Gao

Abstract: Unlike many urban localization methods that return point-valued estimates, a set-valued representation enables robustness by ensuring that a continuum of possible positions obeys safety constraints. One strategy with the potential for set-valued estimation is GNSS-based shadow matching~(SM), where one uses a three-dimensional (3-D) map to compute GNSS shadows (where line-of-sight is blocked). Howe… ▽ More Unlike many urban localization methods that return point-valued estimates, a set-valued representation enables robustness by ensuring that a continuum of possible positions obeys safety constraints. One strategy with the potential for set-valued estimation is GNSS-based shadow matching~(SM), where one uses a three-dimensional (3-D) map to compute GNSS shadows (where line-of-sight is blocked). However, SM requires a point-valued grid for computational tractability, with accuracy limited by grid resolution. We propose zonotope shadow matching (ZSM) for set-valued 3-D map-aided GNSS localization. ZSM represents buildings and GNSS shadows using constrained zonotopes, a convex polytope representation that enables propagating set-valued estimates using fast vector concatenation operations. Starting from a coarse set-valued position, ZSM refines the estimate depending on the receiver being inside or outside each shadow as judged by received carrier-to-noise density. We demonstrated our algorithm's performance using simulated experiments on a simple 3-D example map and on a dense 3-D map of San Francisco. △ Less

Submitted 28 September, 2022; originally announced September 2022.

Comments: Accepted for publication in Journal of Navigation, Winter 2022 issue

Safe Reinforcement Learning Using Black-Box Reachability Analysis

Authors: Mahmoud Selim, Amr Alanwar, Shreyas Kousik, Grace Gao, Marco Pavone, Karl H. Johansson

Abstract: Reinforcement learning (RL) is capable of sophisticated motion planning and control for robots in uncertain environments. However, state-of-the-art deep RL approaches typically lack safety guarantees, especially when the robot and environment models are unknown. To justify widespread deployment, robots must respect safety constraints without sacrificing performance. Thus, we propose a Black-box Re… ▽ More Reinforcement learning (RL) is capable of sophisticated motion planning and control for robots in uncertain environments. However, state-of-the-art deep RL approaches typically lack safety guarantees, especially when the robot and environment models are unknown. To justify widespread deployment, robots must respect safety constraints without sacrificing performance. Thus, we propose a Black-box Reachability-based Safety Layer (BRSL) with three main components: (1) data-driven reachability analysis for a black-box robot model, (2) a trajectory rollout planner that predicts future actions and observations using an ensemble of neural networks trained online, and (3) a differentiable polytope collision check between the reachable set and obstacles that enables correcting unsafe actions. In simulation, BRSL outperforms other state-of-the-art safe RL methods on a Turtlebot 3, a quadrotor, a trajectory-tracking point mass, and a hexarotor in wind with an unsafe set adjacent to the area of highest reward. △ Less

Submitted 21 November, 2022; v1 submitted 15 April, 2022; originally announced April 2022.

Comments: This paper is accepted at IEEE Robotics and Automation Letters and International Conference on Robotics and Automation (ICRA)

Self-Supervised Traffic Advisors: Distributed, Multi-view Traffic Prediction for Smart Cities

Authors: Jiankai Sun, Shreyas Kousik, David Fridovich-Keil, Mac Schwager

Abstract: Connected and Autonomous Vehicles (CAVs) are becoming more widely deployed, but it is unclear how to best deploy smart infrastructure to maximize their capabilities. One key challenge is to ensure CAVs can reliably perceive other agents, especially occluded ones. A further challenge is the desire for smart infrastructure to be autonomous and readily scalable to wide-area deployments, similar to mo… ▽ More Connected and Autonomous Vehicles (CAVs) are becoming more widely deployed, but it is unclear how to best deploy smart infrastructure to maximize their capabilities. One key challenge is to ensure CAVs can reliably perceive other agents, especially occluded ones. A further challenge is the desire for smart infrastructure to be autonomous and readily scalable to wide-area deployments, similar to modern traffic lights. The present work proposes the Self-Supervised Traffic Advisor (SSTA), an infrastructure edge device concept that leverages self-supervised video prediction in concert with a communication and co-training framework to enable autonomously predicting traffic throughout a smart city. An SSTA is a statically-mounted camera that overlooks an intersection or area of complex traffic flow that predicts traffic flow as future video frames and learns to communicate with neighboring SSTAs to enable predicting traffic before it appears in the Field of View (FOV). The proposed framework aims at three goals: (1) inter-device communication to enable high-quality predictions, (2) scalability to an arbitrary number of devices, and (3) lifelong online learning to ensure adaptability to changing circumstances. Finally, an SSTA can broadcast its future predicted video frames directly as information for CAVs to run their own post-processing for the purpose of control. △ Less

Submitted 30 July, 2022; v1 submitted 13 April, 2022; originally announced April 2022.

Comments: 2022 IEEE 25th International Conference on Intelligent Transportation Systems (ITSC)

Constrained Feedforward Neural Network Training via Reachability Analysis

Authors: Long Kiu Chung, Adam Dai, Derek Knowles, Shreyas Kousik, Grace X. Gao

Abstract: Neural networks have recently become popular for a wide variety of uses, but have seen limited application in safety-critical domains such as robotics near and around humans. This is because it remains an open challenge to train a neural network to obey safety constraints. Most existing safety-related methods only seek to verify that already-trained networks obey constraints, requiring alternating… ▽ More Neural networks have recently become popular for a wide variety of uses, but have seen limited application in safety-critical domains such as robotics near and around humans. This is because it remains an open challenge to train a neural network to obey safety constraints. Most existing safety-related methods only seek to verify that already-trained networks obey constraints, requiring alternating training and verification. Instead, this work proposes a constrained method to simultaneously train and verify a feedforward neural network with rectified linear unit (ReLU) nonlinearities. Constraints are enforced by computing the network's output-space reachable set and ensuring that it does not intersect with unsafe sets; training is achieved by formulating a novel collision-check loss function between the reachable set and unsafe portions of the output space. The reachable and unsafe sets are represented by constrained zonotopes, a convex polytope representation that enables differentiable collision checking. The proposed method is demonstrated successfully on a network with one nonlinearity layer and approximately 50 parameters. △ Less

Submitted 16 July, 2021; originally announced July 2021.

Comments: 5 pages, 4 figures

Reachability-based Trajectory Safeguard (RTS): A Safe and Fast Reinforcement Learning Safety Layer for Continuous Control

Authors: Yifei Simon Shao, Chao Chen, Shreyas Kousik, Ram Vasudevan

Abstract: Reinforcement Learning (RL) algorithms have achieved remarkable performance in decision making and control tasks due to their ability to reason about long-term, cumulative reward using trial and error. However, during RL training, applying this trial-and-error approach to real-world robots operating in safety critical environment may lead to collisions. To address this challenge, this paper propos… ▽ More Reinforcement Learning (RL) algorithms have achieved remarkable performance in decision making and control tasks due to their ability to reason about long-term, cumulative reward using trial and error. However, during RL training, applying this trial-and-error approach to real-world robots operating in safety critical environment may lead to collisions. To address this challenge, this paper proposes a Reachability-based Trajectory Safeguard (RTS), which leverages reachability analysis to ensure safety during training and operation. Given a known (but uncertain) model of a robot, RTS precomputes a Forward Reachable Set of the robot tracking a continuum of parameterized trajectories. At runtime, the RL agent selects from this continuum in a receding-horizon way to control the robot; the FRS is used to identify if the agent's choice is safe or not, and to adjust unsafe choices. The efficacy of this method is illustrated on three nonlinear robot models, including a 12-D quadrotor drone, in simulation and in comparison with state-of-the-art safe motion planning methods. △ Less

Submitted 2 March, 2021; v1 submitted 16 November, 2020; originally announced November 2020.

Safe, Optimal, Real-time Trajectory Planning with a Parallel Constrained Bernstein Algorithm

Authors: Shreyas Kousik, Bohao Zhang, Pengcheng Zhao, Ram Vasudevan

Abstract: To move through the world, mobile robots typically use a receding-horizon strategy, wherein they execute an old plan while computing a new plan to incorporate new sensor information. A plan should be dynamically feasible, meaning it obeys constraints like the robot's dynamics and obstacle avoidance; it should have liveness, meaning the robot does not stop to plan so frequently that it cannot accom… ▽ More To move through the world, mobile robots typically use a receding-horizon strategy, wherein they execute an old plan while computing a new plan to incorporate new sensor information. A plan should be dynamically feasible, meaning it obeys constraints like the robot's dynamics and obstacle avoidance; it should have liveness, meaning the robot does not stop to plan so frequently that it cannot accomplish tasks; and it should be optimal, meaning that the robot tries to satisfy a user-specified cost function such as reaching a goal location as quickly as possible. Reachability-based Trajectory Design (RTD) is a planning method that can generate provably dynamically-feasible plans. However, RTD solves a nonlinear polynmial optimization program at each planning iteration, preventing optimality guarantees; furthermore, RTD can struggle with liveness because the robot must brake to a stop when the solver finds local minima or cannot find a feasible solution. This paper proposes RTD*, which certifiably finds the globally optimal plan (if such a plan exists) at each planning iteration. This method is enabled by a novel Parallelized Constrained Bernstein Algorithm (PCBA), which is a branch-and-bound method for polynomial optimization. The contributions of this paper are: the implementation of PCBA; proofs of bounds on the time and memory usage of PCBA; a comparison of PCBA to state of the art solvers; and the demonstration of PCBA/RTD* on a mobile robot. RTD* outperforms RTD in terms of optimality and liveness for real-time planning in a variety of environments with randomly-placed obstacles. △ Less

Submitted 3 March, 2020; originally announced March 2020.

Comments: 20 pages, 8 figures

Reachable Sets for Safe, Real-Time Manipulator Trajectory Design

Authors: Patrick Holmes, Shreyas Kousik, Bohao Zhang, Daphna Raz, Corina Barbalata, Matthew Johnson-Roberson, Ram Vasudevan

Abstract: For robotic arms to operate in arbitrary environments, especially near people, it is critical to certify the safety of their motion planning algorithms. However, there is often a trade-off between safety and real-time performance; one can either carefully design safe plans, or rapidly generate potentially-unsafe plans. This work presents a receding-horizon, real-time trajectory planner with safety… ▽ More For robotic arms to operate in arbitrary environments, especially near people, it is critical to certify the safety of their motion planning algorithms. However, there is often a trade-off between safety and real-time performance; one can either carefully design safe plans, or rapidly generate potentially-unsafe plans. This work presents a receding-horizon, real-time trajectory planner with safety guarantees, called ARMTD (Autonomous Reachability-based Manipulator Trajectory Design). The method first computes (offline) a reachable set of parameterized trajectories for each joint of an arm. Each trajectory includes a fail-safe maneuver (braking to a stop). At runtime, in each receding-horizon planning iteration, ARMTD constructs a parameterized reachable set of the full arm in workspace and intersects it with obstacles to generate sub-differentiable, provably-conservative collision-avoidance constraints on the trajectory parameters. ARMTD then performs trajectory optimization over the parameters, subject to these constraints. On a 6 degree-of-freedom arm, ARMTD outperforms CHOMP in simulation, never crashes, and completes a variety of real-time planning tasks on hardware. △ Less

Submitted 29 September, 2020; v1 submitted 4 February, 2020; originally announced February 2020.

Comments: 14 pages, 4 figures

Technical Report: Safe, Aggressive Quadrotor Flight via Reachability-based Trajectory Design

Authors: Shreyas Kousik, Patrick Holmes, Ramanarayan Vasudevan

Abstract: Quadrotors can provide services such as infrastructure inspection and search-and-rescue, which require operating autonomously in cluttered environments. Autonomy is typically achieved with receding-horizon planning, where a short plan is executed while a new one is computed, because sensors receive limited information at any time. To ensure safety and prevent robot loss, plans must be verified as… ▽ More Quadrotors can provide services such as infrastructure inspection and search-and-rescue, which require operating autonomously in cluttered environments. Autonomy is typically achieved with receding-horizon planning, where a short plan is executed while a new one is computed, because sensors receive limited information at any time. To ensure safety and prevent robot loss, plans must be verified as collision free despite uncertainty (e.g, tracking error). Existing spline-based planners dilate obstacles uniformly to compensate for uncertainty, which can be conservative. On the other hand, reachability-based planners can include trajectory-dependent uncertainty as a function of the planned trajectory. This work applies Reachability-based Trajectory Design (RTD) to plan quadrotor trajectories that are safe despite trajectory-dependent tracking error. This is achieved by using zonotopes in a novel way for online planning. Simulations show aggressive flight up to 5 m/s with zero crashes in 500 cluttered, randomized environments. △ Less

Submitted 18 June, 2019; v1 submitted 11 April, 2019; originally announced April 2019.

Comments: 12 Pages, 3 Figures, 1 Table

Towards Provably Not-at-Fault Control of Autonomous Robots in Arbitrary Dynamic Environments

Authors: Sean Vaskov, Shreyas Kousik, Hannah Larson, Fan Bu, James Ward, Stewart Worrall, Matthew Johnson-Roberson, Ram Vasudevan

Abstract: As autonomous robots increasingly become part of daily life, they will often encounter dynamic environments while only having limited information about their surroundings. Unfortunately, due to the possible presence of malicious dynamic actors, it is infeasible to develop an algorithm that can guarantee collision-free operation. Instead, one can attempt to design a control technique that guarantee… ▽ More As autonomous robots increasingly become part of daily life, they will often encounter dynamic environments while only having limited information about their surroundings. Unfortunately, due to the possible presence of malicious dynamic actors, it is infeasible to develop an algorithm that can guarantee collision-free operation. Instead, one can attempt to design a control technique that guarantees the robot is not-at-fault in any collision. In the literature, making such guarantees in real time has been restricted to static environments or specific dynamic models. To ensure not-at-fault behavior, a robot must first correctly sense and predict the world around it within some sufficiently large sensor horizon (the prediction problem), then correctly control relative to the predictions (the control problem). This paper addresses the control problem by proposing Reachability-based Trajectory Design for Dynamic environments (RTD-D), which guarantees that a robot with an arbitrary nonlinear dynamic model correctly responds to predictions in arbitrary dynamic environments. RTD-D first computes a Forward Reachable Set (FRS) offline of the robot tracking parameterized desired trajectories that include fail-safe maneuvers. Then, for online receding-horizon planning, the method provides a way to discretize predictions of an arbitrary dynamic environment to enable real-time collision checking. The FRS is used to map these discretized predictions to trajectories that the robot can track while provably not-at-fault. One such trajectory is chosen at each iteration, or the robot executes the fail-safe maneuver from its previous trajectory which is guaranteed to be not at fault. RTD-D is shown to produce not-at-fault behavior over thousands of simulations and several real-world hardware demonstrations on two robots: a Segway, and a small electric vehicle. △ Less

Submitted 7 February, 2019; originally announced February 2019.

Comments: 10 pages, 3 figures

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

Authors: Shreyas Kousik, Sean Vaskov, Fan Bu, Matthew Johnson-Roberson, Ram Vasudevan

Abstract: To operate with limited sensor horizons in unpredictable environments, autonomous robots use a receding-horizon strategy to plan trajectories, wherein they execute a short plan while creating the next plan. However, creating safe, dynamically-feasible trajectories in real time is challenging; and, planners must ensure persistent feasibility, meaning a new trajectory is always available before the… ▽ More To operate with limited sensor horizons in unpredictable environments, autonomous robots use a receding-horizon strategy to plan trajectories, wherein they execute a short plan while creating the next plan. However, creating safe, dynamically-feasible trajectories in real time is challenging; and, planners must ensure persistent feasibility, meaning a new trajectory is always available before the previous one has finished executing. Existing approaches make a tradeoff between model complexity and planning speed, which can require sacrificing guarantees of safety and dynamic feasibility. This work presents the Reachability-based Trajectory Design (RTD) method for trajectory planning. RTD begins with an offline Forward Reachable Set (FRS) computation of a robot's motion when tracking parameterized trajectories; the FRS provably bounds tracking error. At runtime, the FRS is used to map obstacles to parameterized trajectories, allowing RTD to select a safe trajectory at every planning iteration. RTD prescribes an obstacle representation to ensure that obstacle constraints can be created and evaluated in real time while maintaining safety. Persistent feasibility is achieved by prescribing a minimum sensor horizon and a minimum duration for the planned trajectories. A system decomposition approach is used to improve the tractability of computing the FRS, allowing RTD to create more complex plans at runtime. RTD is compared in simulation with Rapidly-Exploring Random Trees and Nonlinear Model-Predictive Control. RTD is also demonstrated in randomly-crafted environments on two hardware platforms: a differential-drive Segway, and a car-like Rover. The proposed method is safe and persistently feasible across thousands of simulations and dozens of real-world hardware demos. △ Less

Submitted 22 April, 2020; v1 submitted 18 September, 2018; originally announced September 2018.

Comments: The first two authors contributed equally to this work

Safe Trajectory Synthesis for Autonomous Driving in Unforeseen Environments

Authors: Shreyas Kousik, Sean Vaskov, Matthew Johnson-Roberson, Ramanarayan Vasudevan

Abstract: Path planning for autonomous vehicles in arbitrary environments requires a guarantee of safety, but this can be impractical to ensure in real-time when the vehicle is described with a high-fidelity model. To address this problem, this paper develops a method to perform trajectory design by considering a low-fidelity model that accounts for model mismatch. The presented method begins by computing a… ▽ More Path planning for autonomous vehicles in arbitrary environments requires a guarantee of safety, but this can be impractical to ensure in real-time when the vehicle is described with a high-fidelity model. To address this problem, this paper develops a method to perform trajectory design by considering a low-fidelity model that accounts for model mismatch. The presented method begins by computing a conservative Forward Reachable Set (FRS) of a high-fidelity model's trajectories produced when tracking trajectories of a low-fidelity model over a finite time horizon. At runtime, the vehicle intersects this FRS with obstacles in the environment to eliminate trajectories that can lead to a collision, then selects an optimal plan from the remaining safe set. By bounding the time for this set intersection and subsequent path selection, this paper proves a lower bound for the FRS time horizon and sensing horizon to guarantee safety. This method is demonstrated in simulation using a kinematic Dubin's car as the low-fidelity model and a dynamic unicycle as the high-fidelity model. △ Less

Submitted 28 April, 2017; originally announced May 2017.

Comments: Submitted to DSCC 2017