Incremental controller synthesis in probabilistic environments with temporal logic constraints
Authors:
- 19 May 2014
- journal article
- research article
- Published by SAGE Publications in The International Journal of Robotics Research
- Vol. 33 (8) , 1130-1144
Abstract
In this paper, we consider automatic computation of optimal control strategies for a robot interacting with a set of independent uncontrollable agents in a graph-like environment. The mission specification is given as a syntactically co-safe Linear Temporal Logic formula over some properties that hold at the vertices of the environment. The robot is assumed to be a deterministic transition system, while the agents are probabilistic Markov models. The goal is to control the robot such that the probability of satisfying the mission specification is maximized. We propose a computationally efficient incremental algorithm based on the fact that temporal logic verification is computationally cheaper than synthesis. We present several case studies where we compare our approach to the classical non-incremental approach in terms of computation time and memory usage.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- Incremental synthesis of control policies for heterogeneous multi-agent systems with linear temporal logic specifications2013
- Probabilistic guarantees for high-level robot behavior in the presence of sensor errorAutonomous Robots, 2012
- MDP optimal control under temporal logic constraints2011
- Strategy construction for parity games with imperfect informationInformation and Computation, 2010
- Dealing with Nondeterminism in Symbolic ControlLecture Notes in Computer Science, 2008
- Efficient Model Checking of Safety Properties2003
- Infinite Games and Verification2002
- Probabilistic Symbolic Model Checking with PRISM: A Hybrid ApproachLecture Notes in Computer Science, 2002
- Model checking of probabilistic and nondeterministic systems1995
- Temporal and Modal Logic1990