No label defined (Q4673428)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 2163041
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | No label defined |
scientific article; zbMATH DE number 2163041 |
Statements
29 April 2005
0 references
timed transition system
0 references
controller synthesis problem
0 references
probabilistic computation tree logic
0 references
linear time specifications
0 references
NP-completeness
0 references
NP-hardness
0 references
computational complexty
0 references
game
0 references
Markov decision processes
0 references
0.8644896149635315
0 references
0.8644888997077942
0 references
0.8284788727760315
0 references
0.8241291642189026
0 references
0.823545515537262
0 references
A practically important task is considered; the goal is to synthesize a controller that limits or controls the behavior of an existing system (plant) in an environment to meet the given specification. One can also understand the controller and environment as two players. The plant constitutes the game board, and controller synthesis becomes the problem of finding a strategy for the controller that satisfies the specification whatever move the environment does. The requirement specification can either be given internally or externally. Internal specifications impose restrictions, for example, on the number of visits of a state of the plant. Examples for external specifications are temporal logic formulas that are supposed to be satisfied by the controlled plant. The underlying model for the plant are Markov Decision Processes (MDPs) in which states that are under control of the plant are distinguished from those that are under the control of the environment. Quantitative winning criteria stating that the probability to win the game meets a given lower (or upper) probability bound are considered. In the first part of the paper, the synthesis problem is considered where the specification is provided by means of a formula of probabilistic computation tree logic (PCTL). As for strategies, several choices are discussed: The system or the opponent has to choose deterministically (D) or can choose randomly (R). Furthermore, he or she might choose according to the current state (M), also called Markovian, or is allowed to look at the history of the game played so far (H). From a practical point of view, it would be desirable to be able to synthesize controllers that do not require extra memory to keep track of a history and do not depend on random number generators. However, it is shown that this is not always possible. For the synthesis algorithms, it means that any of the strategy classes HD, HR, MD and MR requires its own synthesis algorithm. The authors show the NP-completeness of the synthesis problem for PCTL and MD-strategies and the NP-hardness of the synthesis problem for PCTL and the strategy classes HD, HR and MR, The second part of the paper addresses the synthesis problem for linear-time specifications formalized by LTL-formulas. A control synthesis algorithm is presented which relies on a reduction to the synthesis problem for PCTL with fairness. For the entire collection see [Zbl 1057.68001].
0 references