Probabilistic Verification and Synthesis for Temporal Logic Robot Tasks
Consider the problem of a robot that has to operate in human environments, such as an autonomous vehicle. The stakeholders (the robot designers, operators, users, bystanders, regulators, and insurance companies) must gain confidence that the robot will remain safe and do its task despite any potential and reasonable sources of uncertainties, disturbances, malfunctions and noises. A long-lasting goal of the robotics community has been to create robots and controllers that are safe, using automatic synthesis tools. Using easy-to-reason about logical specifications, we want to create provably-correct controllers that are guaranteed to work in the set of plausible scenarios. If the robot cannot maintain safety or not able to reach its goals, for any reason, we would at least want to evaluate the risk, i.e. evaluate the probability that the robot will fail. This may be invaluable for insurance or regulatory purposes and to keep the surrounding environment safe. In this thesis, I present a technique based on sampling, that enables the model-based verification of the robot, i.e. finding the probability to fail or satisfy a specification. The specifications are written in Signal Temporal Logic (STL), which is a formalism that allows one to specify temporal and Boolean constraints on continuous-time signals. The proposed technique, which is based on Elliptical Slice Sampling (ESS), works especially well in scenarios where the controls are already mature and stable and a failure is considered a rare event. In these situations, verifying using Monte-Carlo sampling will be intractable since it would require too many simulations to find the failures. I begin with the derivation of the technique for linear systems and Gaussian noises where the derivation is exact and I can guarantee confidence bounds. I show how this method does not have to evaluate all the combinatorially-sized scenarios that may violate an STL specification, rather solving it efficiently using STL's robustness metric. I then lift the restrictions, to allow the verification of non-linear and non-Gaussian uncertainties under some mild assumptions. I then present how we can utilize this method to efficiently obtain the gradients of the probability of failure with respect to any parameter of the system. This enables us to use gradient descent to optimize the parameter and minimize the probability of failure in linear systems. Unfortunately, in non-linear systems, this is not possible. Instead, I show how one can synthesize controls for a non-linear system that would satisfy a Linear Temporal Logic (LTL) specification given bounded noises using funnels that the robot is guaranteed to stay within, created with Sums-of-Squares (SOS) programming. These funnels are used to create motion primitives, and with the use of existing automatic synthesis tools for LTL, I demonstrate how to create the provably-safe robot's controls that guarantee safety and liveness (in non-adversarial environments).