Safe autonomy under uncertainty : computation, control, and application

Abstract

Safety is a primary requirement for many autonomous systems, such as automated vehicles and mobile robots. An open problem is how to assure safety, in the sense of avoiding unsafe subsets of the state space, for uncertain systems under complex tasks. In this thesis, we solve this problem for certain system classes and uncertainty descriptions by developing computational tools, designing verification and control synthesis algorithms, and evaluating them on two applications.

As our first contribution, we consider how to compute probabilistic controlled invariant sets, which are sets the controller is able to keep the system state within with a certain probability. By using stochastic backward reachability, we design algorithms to compute these sets. We prove that the algorithms are computationally tractable and converge in a finite number of iterations. We further consider how to compute invariant covers, which are covers of sets that can be enforced to be invariant by a finite number of control inputs despite disturbances.A necessary and sufficient condition on the existence of an invariant cover is derived. Based on this result, an efficient computational algorithm is designed.

The second contribution is to develop algorithms for model checking and control synthesis. We consider discrete-time uncertain systems under linear temporal logic (LTL) specifications. We propose the new notion of temporal logic trees (TLT) and show how to construct TLT from LTL formulae via reachability analysis for both autonomous and controlled transition systems. We prove approximation relations between TLT and LTL formulae. Two sufficient conditions are given to verify whether a transition system satisfies an LTL formula. An online control synthesis algorithm, under which a set of feasible control inputs can be generated at each time step, is designed, and it is proven to be recursively feasible.

As our third contribution, we study two important vehicular applications on shared-autonomy systems, which are systems with a mix of human and automated decisions. For the first application, we consider a car parking problem, where a remote human operator is guided to drive a vehicle to an empty parking spot. An automated controller is designed to guarantee safety and mission completion despite unpredictable human actions. For the second application, we consider a car overtaking problem, where an automated vehicle overtakes a human-driven vehicle with uncertain motion. We design a risk-aware optimal overtaking algorithm with guaranteed levels of safety.