Back to search

Georgia Institute of Technology

Verification and synthesis for stochastic systems with temporal logic specifications

Abstract

dc:description.abstract

The objective of this thesis is to first provide a formal framework for the verification of discrete-time, continuous-space stochastic systems with complex temporal specifications. Secondly, the approach developed for verification is extended to the synthesis of controllers that aim to maximize or minimize the probability of occurrence of temporal behaviors in stochastic systems. As these problems are generally undecidable or intractable to solve, approximation methods are employed in the form of finite-state abstractions arising from a partition of the original system’s domain for which analysis is greatly simplified. The abstractions of choice in this work are Interval-valued Markov Chains (IMC) which, unlike conventional discrete-time Markov Chains, allow for a non-deterministic range of probabilities of transition between states instead of a fixed probability. Techniques for constructing IMC abstractions for two classes of systems are presented. Due to their inherent structure that facilitates estimations of reachable sets, mixed monotone systems with additive disturbances are shown to be efficiently amenable to IMC abstractions. Then, an abstraction procedure for polynomial systems that uses stochastic barrier functions computed via Sum-of-Squares programming is derived. Next, an algorithm for computing satisfaction bounds in IMCs with respect to so-called omega-regular properties is detailed. As probabilistic specifications require finding the set of initial states whose probability of fulfilling some behavior is below or above a certain threshold, this method may yield a set of states whose satisfaction status is undecided. An iterative specification-guided partition refinement method is proposed to reduce conservatism in the abstraction until a precision threshold is met. Finally, similar interval-based finite abstractions are utilized to synthesize control policies for omega-regular objectives in systems with both a finite number of modes and a continuous set of available inputs. A notion of optimality for these policies is introduced and a partition refinement scheme is presented to reach a desired level of optimality.

Degree

thesis:*
Level thesis:degree_level
Doctoral
Department dc:contributor.department
Electrical and Computer Engineering
Grantor dc:publisher
Georgia Institute of Technology
Year dc:date.issued
2020

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Dutreix, Maxence Dominique Henri
Advisor dc:contributor.advisor
  • Coogan, Samuel
Committee members dc:contributor.committeemember
  • Zhang, Fumin
  • Zhao, Ye
  • Wardi, Yorai
  • Vamvoudakis, Kyriakos

Subjects

dc:subject × 5

Rights

Language dc:language.iso
en_US

Identifiers

dc:identifier.*
Handle dc:identifier.uri
http://hdl.handle.net/1853/62820

Chain of custody

source
Harvested from
Georgia Tech
Base URL
repository.gatech.edu/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Dutreix, Maxence Dominique Henri. Verification and synthesis for stochastic systems with temporal logic specifications. Doctoral thesis, Georgia Institute of Technology, 2020. http://hdl.handle.net/1853/62820