Back to search

Cornell University

Probabilistic Verification and Synthesis for Temporal Logic Robot Tasks

Abstract

dc:description.abstract

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).

Degree

thesis:*
Name thesis:degree_name
Ph. D., Mechanical Engineering
Level thesis:degree_level
Doctor of Philosophy
Discipline thesis:degree_discipline
Mechanical Engineering
Grantor
Cornell University
Year dc:date.issued
2023

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Scher, Guy
Chair dc:contributor.chair
  • Kress Gazit, Hadas
Committee members dc:contributor.committeemember
  • Campbell, Mark
  • Napp, Nils

Subjects

dc:subject × 3

Rights

dc:rights
Statement dc:rights
  • Attribution 4.0 International
Language dc:language.iso
en

Identifiers

dc:identifier.*
Dc Identifier Bibid
16176497
Dc Identifier Other
ProQuest Submission ID: 13623
ProQuest Publication ID: 30485124

Chain of custody

source
Harvested from
Cornell University
Base URL
ecommons.cornell.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Scher, Guy. Probabilistic Verification and Synthesis for Temporal Logic Robot Tasks. Doctor of Philosophy thesis, Cornell University, 2023. https://hdl.handle.net/1813/114137