More projects to be posted soon!
Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games
Many problems in robotics involve multiple decision making agents. To operate efficiently in such settings, robots must reason about the impact of their decisions on the behavior of other agents. Differential games offer an expressive theoretical framework for formulating these types of multi-agent problems. Unfortunately, most numerical solution techniques scale poorly with state dimension and are rarely used in real-time applications. For this reason, it is common to predict the future decisions of other agents and solve the resulting decoupled, i.e., single-agent, optimal control problem. This decoupling neglects the underlying interactive nature of the problem; however, efficient solution techniques do exist for broad classes of optimal control problems. We take inspiration from one such technique, the iterative linear-quadratic regulator (ILQR), which solves repeated approxima-tions with linear dynamics and quadratic costs. Similarly, our proposed algorithm solves repeated linear-quadratic games. We experimentally benchmark our algorithm in several examples with a variety of initial conditions and show that the resulting strategies exhibit complex interactive behavior. Our results indicate that our algorithm converges reliably and runs in real-time. In a three-player, 14-state simulated intersection problem, our algorithm initially converges in < 0.75 s. Receding horizon invocations converge in < 50 ms in a hardware collision-avoidance test.
Read more here.
Risk-Sensitive Safety Analysis
An important problem is to quantify how safe a dynamic system can be despite real-world uncertainties and to synthesize control policies that ensure safe operation. Existing approaches typically assume either a worst-case perspective (which can yield conservative solutions) or a risk-neutral perspective (which neglects rare events). An improved approach would seek a middle ground that allows practitioners to modify the assumed level of conservativeness as needed. To this end, we have developed a new risk-sensitive approach to safety analysis that facilitates a tunable balance between the worst-case and risk-neutral perspectives by leveraging the Conditional Value-at-Risk (CVaR) measure. This work proposes risk-sensitive safety specifications for stochastic systems that penalize one-sided tail risk of the cost incurred by the system’s state trajectory. The theoretical contributions have been to prove that the safety specifications can be under-approximated by the solution to a CVaR-Markov decision process, and to prove that a value iteration algorithm solves the reduced problem and enables tractable risk-sensitive policy synthesis for a class of linear systems. A key empirical contribution has been to show that the approach can be applied to non-linear systems by developing a realistic numerical example of an urban water system. The water system and a thermostatically controlled load system have been used to compare the CVaR criterion to the standard risk-sensitive criterion that penalizes mean-variance (exponential disutility). Numerical experiments demonstrate that reducing the mean and variance is not guaranteed to minimize the mean of the more harmful cost realizations. Fortunately, however, the CVaR criterion ensures that this safety-critical tail risk will be minimized, if the cost distribution is continuous.
Read more here.
FaSTrack: a Modular Framework for Fast and Guaranteed Safe Motion Planning
Fast and safe navigation of dynamical systems through a priori unknown cluttered environments is vital to many applications of autonomous systems. However, trajectory planning for autonomous systems is computationally intensive, often requiring simplified dynamics that sacrifice safety and dynamic feasibility in order to plan efficiently. Conversely, safe trajectories can be computed using more sophisticated dynamic models, but this is typically too slow to be used for real-time planning. We propose a new algorithm FaSTrack: Fast and Safe Tracking for High Dimensional systems. A path or trajectory planner using simplified dynamics to plan quickly can be incorporated into the FaSTrack framework, which provides a safety controller for the vehicle along with a guaranteed tracking error bound. This bound captures all possible deviations due to high dimensional dynamics and external disturbances. Note that FaSTrack is modular and can be used with most current path or trajectory planners. We demonstrate this framework using a 10D nonlinear quadrotor model tracking a 3D path obtained from an RRT planner.
Read more here.
Probabilistically Safe Robot Planning with Confidence Based Human Predictions
In order to safely operate around humans, robots can employ predictive models of human motion. Unfortunately, these models cannot capture the full complexity of human behavior and necessarily introduce simplifying assumptions. As a result, predictions may degrade whenever the observed human behavior departs from the assumed structure, which can have negative implications for safety. In this paper, we observe that how "rational" human actions appear under a particular model can be viewed as an indicator of that model's ability to describe the human's current motion. By reasoning about this model confidence in a real-time Bayesian framework, we show that the robot can very quickly modulate its predictions to become more uncertain when the model performs poorly. Building on recent work in provably-safe trajectory planning, we leverage these confidence-aware human motion predictions to generate assured autonomous robot motion. Our new analysis combines worst-case tracking error guarantees for the physical robot with probabilistic time-varying human predictions, yielding a quantitative, probabilistic safety certificate. We demonstrate our approach with a quadcopter navigating around a human.
Read more here.