ΑΙhub.org

In today’s world, more and more autonomous systems operate in safety-critical settings. These systems must accomplish their task safely without the intervention of a human operator. For example, consider the unmanned aerial vehicle (UAV) in Figure 1, whose task is to deliver a package to a designated target area. The UAV should not crash into obstacles, nor should it run out of battery. In other words, the drone must behave *safely*.

*Figure 1: The UAV’s package delivery problem.*

However, turbulence or wind gusts may cause *uncertainty* in the position and velocity of the UAV. Such factors, also referred to as *noise*, render the behavior of the UAV *uncertain*. Consequently, the ambitious aim is to compute a controller for the UAV, such that it progresses safely to its target, despite the uncertainty. The focus of our research group is such *dependable and safe decision-making under uncertainty*. AI systems, such as the UAV, need to account for the inherent uncertainty in the real world autonomously. We combine state-of-the-art techniques from machine learning, artificial intelligence, control theory, and rigorous formal verification to provide strong guarantees on the safe decision-making of AI systems.

A general problem that we face is how to capture uncertainty. For problems such as the UAV delivery, existing methods rely on critical assumptions on the type of noise. For instance, a common assumption is that we have access to well-behaved probability distributions that capture the noise precisely. In practice, however, these assumptions are unrealistic, and they may even lead to unsafe behavior of the autonomous system. For example, suppose the UAV enters a location with a specific velocity. In that case, we need to know precisely the probability that a wind gust will disturb the UAV’s trajectory to compute a safe controller.

Our recent paper *Sampling-Based Robust Control of Autonomous Systems with Non-Gaussian Noise* follows that line of research and has been selected as a distinguished paper at AAAI. We propose the first method to compute safe controllers for autonomous systems in safety-critical settings under unknown stochastic noise. In contrast to existing methods, we do not rely on any explicit representation of this noise. Instead, we predict the outcome of actions based on previous observations of the noise, that is, our approach is *sampling-based*. By combining ideas from the fields of control theory, artificial intelligence, and formal verification, we can compute controllers that are safer than those computed by state-of-the-art alternatives.

We consider autonomous systems as continuous-state linear dynamical models, with continuous control inputs that affect the state of the overall system. The general problem that we face is to compute a feedback controller that maximizes the probability to safely reach a desired goal state, while avoiding unsafe states. This problem is very hard to solve in general, because the state and control inputs are continuous, and because the outcomes of control inputs are uncertain due to disturbances in the form of noise.

The key step in our approach is to compute a discrete-state abstraction of the continuous system. Loosely speaking, we partition the infinitely many states into a set of abstract, discrete regions. We then define abstract actions that correspond to control inputs that cause transitions between these regions. Due to the noise, every action has multiple possible outcomes that all occur with a certain probability. We compute lower and upper bounds (intervals) on these probabilities based on a finite number of observations of the noise.

Our abstraction procedure ensures that we obtain a faithful, yet abstract representation of the autonomous system. In fact, this abstraction constitutes a type of Markov decision process, which is the standard type of model in sequential decision making under uncertainty. To analyze our abstract models in a rigorous manner, we use state-of-art tools from an area called formal verification.

Solving the UAV delivery problem

Now consider the specific UAV delivery problem in Figure 2, with the target area in green, and the obstacles that we must avoid in red. With our method, we can compute a controller, for which the probability to safely reach the target area is above a predefined safety threshold. The effect of turbulence causes a non-Gaussian stochastic disturbance that affects the 6-dimensional state of the UAV. The wind strength may vary from day to day, so the optimal path to take may differ as well. With our method, we can take this effect into account, because we reason over the effect of the turbulence explicitly. As shown in the figure, under weak turbulence, the UAV takes the short but narrow path, while under high noise, it is safer to take the longer path around the obstacles. Thus, accounting for noise is important to obtain controllers that are safe.

*Figure 2. Simulated trajectories for the UAV under different turbulence conditions. Above: low noise. Below: high noise.*

Developing methods to design safe controllers is a critical necessity in a world with an increasing number of autonomous systems. When these systems operate close to human beings, guaranteeing safe behavior is of utmost importance. Designing safe controllers is particularly difficult because these autonomous systems operate in continuous and uncertain environments.

We have made a first step in designing safe controllers, even if the system is perturbed by noise of an unknown probability distribution. With our approach, we bridge the gap between continuous systems in the physical world and discrete models in computer science. As part of our ongoing research, we aim to make our algorithms even faster and apply our method to systems with different types of uncertainty. Moreover, we will continuously apply our work to new applications from areas such as robotics, fintech, or predictive maintenance.

tags: AAAI2022

Thom Badings
is a PhD candidate at the Institute for Computing and Information Science, Radboud University, Nijmegen.

Nils Jansen
is a tenured assistant professor at the Institute for Computing and Information Science, Radboud University, Nijmegen.

In this blog post, we aim to understand if, when and why offline RL is a better approach for tackling a variety of sequential decision-making problems.

17 May 2022, by
BAIR blog

The recordings of the sessions from the AI UK conference are now available for all to watch.

16 May 2022, by
Lucy Smith

The standard aims to guide AI practitioners in dealing with malicious attacks on AI systems.

13 May 2022, by
Nanyang Technological University, Singapore

A computational tool developed to predict the structure of protein complexes is providing new insights into the biomolecular mechanisms of their function.

12 May 2022, by
Machine Learning Center at Georgia Tech

We talk to Nicolo' Brandizzi about his work on human-AI collaboration.

11 May 2022, by
Joe Daly

Find out how you can make a nomination for the ACM SIGAI Industry Award - deadline 31 May 2022.

10 May 2022, by
ACM SIGAI

©2021 - ROBOTS Association