4.7 Article

Incremental controller synthesis in probabilistic environments with temporal logic constraints

Journal

INTERNATIONAL JOURNAL OF ROBOTICS RESEARCH
Volume 33, Issue 8, Pages 1130-1144

Publisher

SAGE PUBLICATIONS LTD
DOI: 10.1177/0278364913519000

Keywords

Control policy synthesis; incremental synthesis; probabilistic verification; temporal logic; formal methods

Categories

Funding

  1. Office of Naval Research [MURI N00014-09-1051, MURI N00014-10-10952]
  2. National Science Foundation [CNS-0834260, CNS-1035588]

Ask authors/readers for more resources

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.

Authors

I am an author on this paper
Click your name to claim this paper and add it to your profile.

Reviews

Primary Rating

4.7
Not enough ratings

Secondary Ratings

Novelty
-
Significance
-
Scientific rigor
-
Rate this paper

Recommended

No Data Available
No Data Available