RAIDER asked how an autonomous agent can keep acting sensibly when neither its environment nor the other agents in it can be fully trusted: sensing is noisy, disturbances accumulate along a trajectory, on-board computation is finite, and some of the agents in the scene may be adversarial. Our part of the program ran along two lines. The first developed uncertainty quantification and mitigation methods that keep an agent operational in the presence of intermittent interactions and potential adversaries. The second developed hierarchical representations that let an agent with limited resources decide how much of the environment it can afford to reason about, and at what resolution.
Path planners have traditionally treated uncertainty as something to be mopped up afterwards by a low-level feedback controller. Because the planner cannot then anticipate how much the tracking error will actually grow, it has to assume the worst, and the resulting nominal paths are unnecessarily conservative. We instead made the closed-loop evolution of the uncertainty part of the planning problem itself, through optimal covariance steering, which designs the feedback gain so as to control the state covariance directly. The planner computes a collision-free path under non-convex state chance constraints, steers the state to a prescribed terminal Gaussian distribution, and minimizes the expected quadratic cost, so the choice of nominal path now depends on how much the uncertainty can be squeezed along it: a longer route through open space may be preferable to a short one through a gap the covariance cannot be made to fit. Around this core we built input-hard-constrained and iterative (linearization-based) versions for nonlinear systems, an iterative risk allocation formalism that distributes the allowed failure probability across the constraints instead of splitting it uniformly, a covariance steering stochastic model predictive controller with guarantees of stability and recursive feasibility, and a covariance steering belief roadmap that extends the probabilistic roadmap to belief space, using a covariance steering controller as the edge controller so that terminal belief constraints are met in finite time. In parallel we extended the underlying theory to martingale noise combining white Gaussian and abrupt jump components, to chance constraints under general (non-Gaussian) distributions, to distributionally robust settings where the distribution is known only to lie in some ambiguity set, to systems with unknown parameters entering multiplicatively, to a two-player game-theoretic version, and to a lossless convex relaxation that recovers the exact solution by semidefinite programming.
The same machinery was then used to make sampling-based predictive control robust. Model predictive path integral (MPPI) control degrades badly when the rollouts are dispersed by disturbances the sampler did not anticipate; the covariance-controlled variant fixes this by steering the dispersion of the rollout trajectories at the end of the prediction horizon, which also gives an adjustable sampling distribution that can be adapted to the environment. A risk-aware variant replaces the expectation in the MPPI objective with Conditional Value-at-Risk, and, unlike most stochastic MPC and CVaR methods, does so without linearizing the dynamics or restricting the form of the cost. Driving a vehicle aggressively through cluttered environments, it matched the lap times of the baseline controller while incurring far fewer collisions. A third variant adds a control-barrier-function safety filter to the sampled rollouts, achieving real-time planning from a much smaller number of parallel simulations, so that it runs on ordinary CPUs rather than a GPU. These controllers were validated experimentally on the AutoRally platform and on a full-size autonomous vehicle.
The second line of work started from the observation that a highly descriptive map is of little use to an agent that cannot afford to process it. We posed environment abstraction as an information-theoretic compression problem, in which the degree of compression is set by a single parameter tied to the agent’s available resources, and showed that it connects naturally to rate-distortion theory and the information bottleneck. Taking the environment as an occupancy grid and the abstraction as a quadtree, the state-aggregation problem becomes a search over the space of feasible quadtrees; an invariance in the cost between two consecutive trees made that search cheap enough to be practical. The resulting abstractions are multi-resolution and adapt to the agent: agents with less processing capability select coarser representations, while resolution is retained where the probability of occupancy is highest, near the agent, or along a candidate trajectory. We later recast the same problem as an integer linear program, which enforces the degree of compression as a hard constraint rather than a soft penalty and, in its linear relaxation, shows that multi-resolution information-theoretic tree abstractions can be obtained by convex programming; a second algorithm handles environments with multiple sources of relevant, irrelevant, or confidential information. In collaboration with the group of Nikolay Atanasov at UC San Diego, the approach was carried over to three-dimensional semantic octrees built from point-cloud data, where it compresses a large outdoor scene while preserving the semantic classes the robot cares about and discarding the rest. Finally, we applied the same hierarchical representation to stochastic pursuit-evasion games on large grid worlds. Partitioning the grid into superstates yields a two-resolution decision process, consisting of a set of local games at the state level and an aggregated game at the superstate level, each with a state space small enough to be solved for Nash equilibria; numerically, this cuts the computational overhead substantially while maintaining satisfactory performance.
This project is in collaboration with Jorge Cortés, Nikolay Atanasov, and Luca Carlone.
Sponsors
This project was funded by ONR.