Dieses Kapitel untersucht die Synthese universeller Sicherheitscontroller und überbrückt die Lücke zwischen reaktiver Synthese und aufsichtsrechtlicher Kontrolle. Es befasst sich mit den Beschränkungen traditioneller Methoden, die aufgrund der Notwendigkeit, alle möglichen Pflanzenverhaltungen in das Modell einzubeziehen, mit Skalierbarkeit zu kämpfen haben. Das Kapitel stellt einen bahnbrechenden Ansatz vor, der die Synthese eines universellen Controllers von seiner Anpassung an spezifische Anlagenmodelle entkoppelt, indem er Prophezeiungen verwendet, um Reglerleistungen auf Grundlage zukünftigen Anlagenverhaltens zu konditionieren. Diese Methode verbessert die Skalierbarkeit und Anpassungsfähigkeit und ermöglicht eine effiziente Synthese, selbst wenn das Pflanzenmodell nicht vollständig bekannt ist oder sich im Laufe der Zeit ändert. Das Kapitel bietet einen umfassenden Überblick über die theoretischen Grundlagen, einschließlich der formalen Einführung universeller Steuerungen und Prophezeiungen, und stellt einen Algorithmus zur Synthese universeller Steuerungen aus Sicherheitsspezifikationen vor. Es enthält auch experimentelle Ergebnisse, die die verbesserte Skalierbarkeit des Ansatzes im Vergleich zu Standardmethoden belegen. Das Kapitel schließt mit einer Diskussion der Vorteile universeller Steuerungen, einschließlich ihrer Anpassungsfähigkeit an neue Anlagen und dynamische Veränderungen, sowie ihrer Erklärbarkeit, die spezifische Anlageneigenschaften identifiziert, die bestimmte Steuerungen sicherer machen.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
The goal of logical controller synthesis is to automatically compute a control strategy that regulates the discrete, event-driven behavior of a given plant s.t. a temporal logic specification holds over all remaining traces. Standard approaches to this problem construct a two-player game by composing a given complete plant model and the logical specification and applying standard algorithmic techniques to extract a control strategy. However, due to the often enormous state space of a complete plant model, this process can become computationally infeasible. In this paper, we introduce a novel synthesis approach that constructs a universal controller derived solely from the game obtained by the standard translation of the logical specification. The universal controller’s moves are annotated with prophecies – predictions about the plant’s behavior that ensure the move is safe. By evaluating these prophecies, the universal controller can be adapted to any plant over which the synthesis problem is realizable. This approach offers several key benefits, including enhanced scalability with respect to the plant’s size, adaptability to changes in the plant, and improved explainability of the resulting control strategy. We also present encouraging experimental results obtained with our prototype tool, unicon.
Hinweise
Authors are ordered alphabetically.
1 Introduction
Reactive synthesis, in the tradition of Church’s Problem [15], and supervisory control, in the tradition of Ramadge and Wonham [37], both aim at the automatic construction of systems that are guaranteed to satisfy their formal specifications1. Reactive synthesis is based on a logical specification, typically given as a formula of a temporal logic; supervisory control is based on an open system model, known as the plant. In practical applications, we often encounter a combination of both views, where, for example, the behavioral objectives of a robot are specified as a temporal formula, while its surroundings, such as walls, humans, and other robots, as well as the physics of their interaction, are described by a plant model. This has lead to approaches which automatically abstract physical behavioral constrains into a plant automaton [8, 39, 41] or model the plant directly as an event-based automaton [33, 40], which is then composed with the finite automaton derived from the logical specification. The resulting \(\omega \)-regular game can then be solved by standard algorithmic techniques from reactive synthesis [3, 29, 30]. This approach is, however, severely limited in its scalability. The necessity to include all possible plant behaviors into the plant model to achieve a correct-by-design solution leads to a huge state space of the plant automaton, which makes solving the resulting game computationally impractical. The situation is even worse if the plant model is not fully known or changes over time, for example as the robot receives new mapping data, which currently requires a complete re-synthesis.
An encouraging observation is, however, that, in practice, it is often not necessary to analyze the interaction of the controller and the plant in great detail. In supervisory control, it has been observed that, if certain conditions are met, the plant already guarantees the desired behavior entirely on its own, independently of the controller [27]. Conversely, benchmarks in reactive synthesis, where there is no explicit plant model, often capture the relevant properties of the plant with just a small set of assumption formulas [28].
Anzeige
Based on this observation, this paper presents a novel synthesis approach that decouples the synthesis of a universal controller, which we construct purely based on the temporal formula, from the adaptation of the universal controller to the specific plant model. The two phases are connected by an annotation of the output decisions in the universal controller with a condition about the plant behavior, which we call the prophecy of the output: the controller only chooses the output if the plant satisfies the prophecy. The main advantage of the new approach is the improved scalability due to the fact that the universal controller is constructed independently of the plant. We illustrate the idea with a toy example, which will also serve as the running example of the paper.
Example 1
Our setting consists of the controller \(\texttt {c}\), the plant \(\texttt {p}\), and the external environment \(\texttt {e}\). We assume that each of these three processes has a boolean output proposition: \(o_\texttt {c}\), \(o_\texttt {p}\), and \(o_\texttt {e}\), respectively. At each time step, the processes chose the values for their respective output propositions based on the history of all previous outputs. The temporal specification is given as the LTL formula
(1)
The formula requires that the controller matches the output of the plant as long as the environment sets its output to true. As the controller cannot observe the plant output before setting its own output, it is impossible to build a correct controller independently of the plant: unless the environment sets its output to false, the controller must know the output produced by the plant one time step in advance. We express this information with the prophecies \(\langle o_\texttt {p}\rangle \), indicating that the plant will output true, and \(\langle \lnot o_\texttt {p}\rangle \), indicating that the plant will output false. The universal controller then reacts to \(\langle o_\texttt {p}\rangle \) by setting \(o_\texttt {c}\) to true and to \(\langle \lnot o_\texttt {p}\rangle \) by setting \(o_\texttt {c}\) to false.
Contribution. In the remainder of the paper, we formally introduce the concepts of universal controllers and prophecies. We provide an algorithm to synthesize universal controllers from safety specifications, with a finite representation of the prophecies as tree automata. Furthermore, we show that universal controllers are also most permissive, capturing all controller strategies that are correct for any realizable plant model. We present an exploration algorithm to obtain a controller from the universal controller for a specific plant model. We show that the algorithm is sound and complete for safety specifications. Finally, we provide experimental results based on our prototype tool, unicon [25], showing that our approach scales better than the standard method on synthesis problems with large plant models.
Related Work. One key feature of the universal controller is its permissiveness: it captures all control strategies that are correct for any realizable plant. The concept of permissiveness is well-established in the field of supervisory control, where it is the key feature of the computed supervisor [14]. However, here permissiveness is understood w.r.t. enabling all behaviors that a single plant fulfills. In the same spirit, permissive solutions have also been considered in the field of reactive synthesis [9, 12, 26], however mostly to ensure variability of resulting implementations. Recently, permissiveness for control applications of reactive synthesis has been considered [5, 32], but also w.r.t. one fixed plant model.
Anzeige
Another line of work focuses on synthesizing control strategies that are correct for a particular set of plant models. For example, dominant strategies [16, 24] are correct for all realizable plants, whereas admissible strategies [7, 10] are correct for a maximal set of realizable plants. Other works [4, 13, 21, 22] restrict plant models with reasonable assumptions and synthesize a control strategy that is correct for this restricted set of plants. Nevertheless, all these works are restricted by computing a single control strategy that must be correct for the entire set of considered plants, whereas our approach computes a universal controller that can be adapted to different control strategies depending on the plant model.
Finally, the use of prophecy variables is a common proof technique to make information about future events accessible [2]. A recent work by Beutner and Finkbeiner [11] uses such prophecies to provide a complete algorithm for hyperproperty verification. Inspired by this work, we use prophecies to guess the future behavior of the plant in order to synthesize a universal controller.
2 Preliminaries
For every set X, we write \(X^*\) and \(X^\omega \) to denote the sets of finite and respectively infinite, sequences of elements of X, and let \(X^\infty = X^* \cup X^\omega \). For \(\rho \in X^\infty \), we denote \(\left|\rho \right|\in \mathbb {N}\cup \{\infty \}\) the length of \(\rho \), and define \( dom (\rho ):=\{0,1,\ldots ,\left|\rho \right|-1\}\). For \(\rho = x_0x_1\cdots \in X^\infty \) and \(i,j\in dom (\rho )\) with \(i\le j\), we define \(\rho [i]:=x_i\) and \(\rho [i,j]:=x_i\cdots x_j\). Moreover, \( last (\rho )\) denotes the last element of \(\rho \). For \(\rho \in X^\infty \) and some set Y, we write \(\rho \downarrow _Y\) to denote the sequence \(\rho '\) with \(\rho '[i] = \rho [i]\cap Y\).
System Architectures. In this paper, we focus on systems with three processes, \(\text {Proc}= \{\texttt {c},\texttt {p},\texttt {e}\}\), i.e., a controller, a plant, and an environment. For the rest of the paper, we fix a set of atomic propositions \(\texttt{AP}= {O_{\texttt {e}}}\uplus {O_{\texttt {c}}}\uplus {O_{\texttt {p}}}\) partitioned into the output propositions of the processes. This defines an architecture \(\texttt{Arc}= ({I_{\texttt {e}}},{O_{\texttt {e}}},{I_{\texttt {c}}},{O_{\texttt {c}}},{I_{\texttt {p}}},{O_{\texttt {p}}})\) over \(\texttt{AP}\) where the input propositions of a process \(i\in \text {Proc}\) are the union of the output propositions of all other processes, i.e., \({I_{i}} = \bigcup _{j\ne i}{O_{j}}\).
Traces and Specifications. We fix alphabet \(\varSigma = 2^{\texttt{AP}}\) to the power set of the atomic propositions \(\texttt{AP}\). A trace over \(\varSigma \) is a sequence \(\gamma \in \varSigma ^\omega \). A specification\(\varphi \) specifies some restrictions on the traces. We write \(\gamma \vDash \varphi \) to denote that the trace \(\gamma \) satisfies the specification \(\varphi \). The language \(\mathcal {L}(\varphi )\) of a specification \(\varphi \) represents the set of traces that satisfy \(\varphi \).
LTL. Linear-time temporal logic (LTL) [36] is a specification language for linear-time properties. LTL specifications over atomic propositions \(\texttt{AP}\) are given by
. A trace is evaluated against an LTL specification \(\varphi \) in the ususal way. We refer to [6, Chapter 5.1.2] for the detailed semantics.
Process Strategies. We model a strategy for process i as a Moore machine \(\mathcal {M}= (S, s_0,\tau ,o)\) over inputs \({I_{i}}\) and outputs \({O_{i}}\), consisting of a finite set of states S, an initial state \(s_0 \in S\), a transition function \(\tau : S \times 2^{I_{i}} \rightarrow S\) over inputs, and an output labeling function \(o: S \rightarrow 2^{O_{i}}\). For a finite input sequence \(\gamma = \alpha _0\alpha _1\cdots \alpha _{k-1}\in (2^{{I_{i}}})^*\!\), \(\mathcal {M}\) produces a finite path \(s_0s_1\cdots s_k\) and an output sequence \(o(s_0)o(s_1)\cdots o(s_k)\in (2^{{O_{i}}})^*\) such that \(\tau (s_j, \alpha _j) = s_{j+1}\). We write \( out (\mathcal {M},\gamma )\) to denote the last output produced, i.e., \(o(s_k)\). Similarly, for an infinite input sequence \(\gamma \in (2^{{I_{i}}})^\omega \!\), \(\mathcal {M}\) produces an infinite path \(s_0s_1\cdots \) and an infinite output sequence \(o(s_0)o(s_1)\cdots \in (2^{{O_{i}}})^\omega \). We write \( Traces (\mathcal {M})\) to denote the set of all traces \(\gamma \in \varSigma ^\omega \) such that for input sequence \(\gamma \downarrow _{{I_{i}}}\), \(\mathcal {M}\) produces the output sequence \(\gamma \downarrow _{{O_{i}}}\). We say that \(\mathcal {M}\) satisfies a specification \(\varphi \), denoted \(\mathcal {M}\models \varphi \), if \(\gamma \models \varphi \) holds for all traces \(\gamma \in Traces (\mathcal {M})\).
For ease of readability, we refer to the plant strategies as plants and the controller strategies as controllers. We collect all plants in the set \(\mathbb {P}\) and all controllers in the set \(\mathbb {C}\). The parallel composition \(\mathcal {M}_{i} \parallel \mathcal {M}_j\) of two strategies \(\mathcal {M}_{i} = (S_i,s^i_0,\tau _i,o_i)\), \(\mathcal {M}_j = (S_j,s^j_0,\tau _j,o_j)\) of processes \(i, j\in \text {Proc}\) is a strategy, i.e., a Moore machine, \((S,s_0,\tau ,o)\) over inputs \(({I_{i}} \cup {I_{j}})\setminus ({O_{i}}\cup {O_{j}})\) and outputs \({O_{i}} \cup {O_{j}}\) with \(S = S_i \times S_j\), \(s_0=(s^i_0,s^j_0)\), \(\tau ((s,s'),\sigma ) = (\tau _i(s,(\sigma \cup o_j(s')) \cap {I_{i}}),\tau _j(s',(\sigma \cup o_i(s))\cap {I_{j}}))\), and \(o((s,s')) = o_i(s) \cup o_j(s')\).
We also represent a strategy \(\mathcal {M}\) over inputs I and outputs O as a \(2^{O}\)-labeled \(2^{I}\)-tree which is a function \(\mathcal {T}: (2^{I})^* \rightarrow 2^{O}\). The tree maps input sequences to their last output, i.e., for all input sequences \(\gamma \in (2^{I})^*\), \(\mathcal {T}(\gamma ) = out (\mathcal {M},\gamma )\).
\(\omega \)-Automata. A (deterministic) \(\omega \)-automaton\(\mathcal {A}\) (over alphabet \(\varSigma \)) is a tuple \((Q,q_0,\delta ,\varOmega )\) consisting of a finite set of states Q, an initial state \(q_0\in Q\), a transition function \(\delta :Q\times \varSigma \rightarrow Q\), and an acceptance condition \(\varOmega \subseteq Q^\omega \). The unique run of \(\mathcal {A}\) from state q on some trace \(\gamma \in \varSigma ^\infty \), denoted by \( run (\mathcal {A},q,\gamma )\), is a sequence of states \(\rho \in Q^\infty \) with \(\left|\rho \right| =\left|\gamma \right|+1\), \(\rho [0] = q\), and \(\delta (\rho [i],\gamma [i]) = \rho [i+1]\) for all \(i\in dom (\gamma )\). A run \(\rho \) is accepting if \(\rho \in \varOmega \). The language \(\mathcal {L}(\mathcal {A})\) is the set of all traces \(\gamma \) for which the unique run \( run (\mathcal {A},q_0,\gamma )\) is accepting.
A (deterministic) safety automaton (DSA) is an \(\omega \)-automaton with a safety acceptance condition \(\varOmega = safe (F)\), where \(F\subseteq Q\) is a set of safe states, containing the set of runs that only visits states in F. It is known that an LTL specification \(\varphi \) can be translated into an equivalent \(\omega \)-automaton \(\mathcal {A}\), i.e., with \(\mathcal {L}(\varphi ) = \mathcal {L}(\mathcal {A})\), with a double exponential blow-up [6]. A safety LTL specification \(\varphi \) is an LTL specification for which the corresponding automaton \(\mathcal {A}\) is a safety automaton. We write \(\textsf {LTLtoDSA}\) to refer to the procedure that implements this translation from a safety LTL specification to an equivalent safety automaton [34, 35].
Given an automaton \(\mathcal {A}= (Q,q_0,\delta ,\varOmega )\) and a Moore machine \(\mathcal {M}\) over inputs I and outputs O with \(2^{I\cup O}\subseteq \varSigma \), we define the composition \(\mathcal {A}\times \mathcal {M}= (Q\times S, (q_0,s_0), \delta ')\) as a product automaton with partial transition function \(\delta ': (Q\times S)\times 2^I \rightarrow (Q\times S)\) defined as \(\delta '((q,s),\sigma ) = (\delta (q,\sigma \cup o(s)),\tau (s,\sigma ))\). We write \( Runs (\mathcal {A},q,\mathcal {M})\) to denote the set of runs \(\rho \) of \(\mathcal {A}\) starting from q for which there exists a corresponding run \(\rho '\) of \(\mathcal {A}\times \mathcal {M}\) with \(\rho '[i] = (\rho [i],s_i)\) for each \(i\ge 0\). We write \(\texttt {reach}(\mathcal {A}\times \mathcal {M})\) to denote the set of states (q, s) that are reachable from the initial state \((q_0,s_0)\) in \(\mathcal {A}\times \mathcal {M}\), i.e., there exists a run \(\rho \) of \(\mathcal {A}\times \mathcal {M}\) with \(\rho [0] = (q_0,s_0)\) and \(\rho [k] = (q,s)\) for some \(k\ge 0\).
Tree Automata. A tree automaton over \(2^{O}\)-labeled \(2^{I}\)-trees is a tuple \(\mathcal {A}= (Q,q_0,T,\varOmega )\) consisting of a finite set of states Q, an initial state \(q_0\in Q\), a transition function \(T\subseteq Q\times 2^{O} \times (2^{I} \rightarrow Q)\), and an acceptance condition \(\varOmega \subseteq Q^\omega \).
A run of a tree automaton \(\mathcal {A}\) on a tree \(\mathcal {T}: (2^I)^*\rightarrow 2^O\) is a Q-labeled \(2^{I}\)-tree \(\upeta : (2^{I})^* \rightarrow Q\) with \(\upeta (\epsilon ) = q_0\) and for every input sequence \(\gamma \alpha \in (2^{I})^*\), there exists \((\upeta (\gamma ), \mathcal {T}(\gamma ), f) \in T\) such that \(f(\alpha ) = \upeta (\gamma \alpha )\). Given an input sequence \(\alpha _0\alpha _1\cdots \in (2^{I})^*\), a run (tree) \(\upeta : (2^{I})^* \rightarrow Q\) produces a path, i.e., a sequence of states, \(\upeta (\epsilon )\upeta (\alpha _0)\upeta (\alpha _0\alpha _1)\cdots \). The run (tree) is accepting if every path produced by the run is accepting by the acceptance condition \(\varOmega \). We define the language of a tree automaton \(\mathcal {L}(\mathcal {A})\) as the set of all accepting trees.
3 Universal Controllers
Logical controller synthesis is the problem of, given a plant and an environment, finding a controller that satisfies, together with the plant, some specification. More specifically, for a given architecture, an LTL specification \(\varphi \) over \(\texttt{AP}\), and a plant strategy \(\mathcal {M}_\texttt {p}\), the problem asks to find a controller strategy \(\mathcal {M}_\texttt {c}\) s.t. \(\mathcal {M}_\texttt {c}\parallel \mathcal {M}_\texttt {p}\vDash \varphi \). We formalize the example from Ex. 1 as follows:
Fig. 1.
Left: the (safety) automaton \(\mathcal {A}_\varphi =\textsf {LTLtoDSA}(\varphi )\) with safe states \(F = \{q_0,q_1\}\) representing the specification \(\varphi \) in (1). Right: a plant strategy \(\mathcal {M}_\texttt {p}\).
Example 2
Consider the architecture over \(\texttt{AP}= \{o_\texttt {c},o_\texttt {p},o_\texttt {e}\}\) with \({O_{\texttt {e}}} = \{o_\texttt {e}\}\), \({O_{\texttt {c}}} = \{o_\texttt {c}\}\), \({O_{\texttt {p}}} = \{o_\texttt {p}\}\), and LTL specification \(\varphi \) in Eq. (1). As discussed in Ex. 1, the specification requires that the controller needs to match the output of the plant as long as the environment outputs \(o_\texttt {e}\). This is also illustrated by the automaton \(\mathcal {A}_\varphi \) depicted in Fig. 1 (left) which accepts \(\mathcal {L}(\varphi )\) over the alphabet \(\varSigma = 2^{\texttt{AP}}\). We want to synthesize a controller strategy \(\mathcal {M}_\texttt {c}\) that is correct w.r.t. a given plant strategy \(\mathcal {M}_\texttt {p}\), i.e., the specification is realizable by the composition of the plant and the controller.
In general, infinitely many plants exist for which one can find a controller such that the specification over the overall architecture becomes realizable. We call such plants admissible.
Definition 1
(Admissibility). Given a specification \(\varphi \), a plant \(\mathcal {M}_\texttt {p}\) is said to be admissible for \(\varphi \) if there exists a controller \(\mathcal {M}_\texttt {c}\) s.t. \(\mathcal {M}_\texttt {c}\parallel \mathcal {M}_\texttt {p}\vDash \varphi \).
Given a plant strategy \(\mathcal {M}_\texttt {p}\) and a specification \(\varphi \), the controller synthesis problem asks to construct a controller strategy \(\mathcal {M}_\texttt {c}\) s.t. \(\mathcal {M}_\texttt {c}\parallel \mathcal {M}_\texttt {p}\vDash \varphi \), or determine that no such controller exists, i.e., to conclude that the synthesis problem is unrealizable. The latter is true iff the plant \(\mathcal {M}_\texttt {p}\) is not admissible. Given a plant strategy \(\mathcal {M}_\texttt {p}\), typical controller synthesis techniques explore the entire state space of \(\mathcal {M}_\texttt {p}\) to either construct a controller or conclude unrealizability. In practice, such plant representations can be very large, as they might represent abstractions of actual implementations or physical system dynamics with a large number of states and propositions. This quickly leads to a large and infeasible runtime of synthesis algorithms.
The major observation of this work is that this exploration can be circumvented by solving the controller synthesis problem “abstractly” without considering a particular plant strategy. We achieve this by generating future assumptions about the plant. We call such future assumptions prophecies.
Definition 2
(Prophecies). A prophecy \(\theta \subseteq \mathbb {P}\) is a set of plants.
Intuitively, we use prophecies to condition the current controller output on the future behavior of the plant strategy. To illustrate this, consider again the controller synthesis problem from Ex. 1. As future behavior of the environment is unknown, for any admissible plant, the controller needs to output \(o_\texttt {c}\) in the first time-step if the plant also outputs \(o_\texttt {p}\) in the first time-step, else it needs to output \(\lnot o_\texttt {c}\). However, the controller cannot observe the plant output before it outputs \(o_\texttt {c}\) or \(\lnot o_\texttt {c}\). Hence, the controller needs to use a prophecy about the plant to decide on its output. Note that the plant strategy can be very complex, involving a lot of other behavior and propositions. By synthesizing a controller which conditions its output on a prophecy, we extract the information about the future of the plant relevant for controller synthesis for a given specification and architecture, independently of the concrete plant realization. When given a concrete plant strategy, we then verify all prophecies to pick the correct controller output in every time step. We call such a prophecy-annotated controller a universal controller, as formalized next.
Definition 3
(Universal controller). A universal controller\(\mathcal {U}\) over alphabet \(\varSigma \) and prophecy set \(\mathbb {F}\) is a tuple \((S, s_0,\tau ,\kappa )\) consisting of a finite set of states S, an initial state \(s_0 \in S\), a transition function \(\tau : S \times \varSigma \rightarrow S\), and a prophecy annotation \(\kappa : S \times 2^{{O_{\texttt {c}}}} \rightarrow \mathbb {F}\).
Note that the transition function of a universal controller is over the whole alphabet \(\varSigma \), instead of just inputs of the controller. Furthermore, each state is annotated with an additional condition by a prophecy for each controller output. Once we obtain a plant, we can verify these prophecies to pick the correct controller output for each state and set the labelling function of the controller accordingly. Once the labelling function is set, this also refines the transition function into a function over the inputs only.
Fig. 2.
Left: a universal controller \(\mathcal {U}\) with prophecy annotation \(\kappa \) (shown by
) such that \(\kappa (q_1,*) = \langle \texttt{true}\rangle \) (i.e., the set of all plants), \(\kappa (q_2,*) = \langle \texttt{false}\rangle \) (i.e., the empty set), \(\kappa (q_0,o_\texttt {c}) = \langle o_\texttt {p}\rangle \) (i.e., the set of all plants that output \(o_\texttt {p}\) in the current time-step), and \(\kappa (q_0,\lnot o_\texttt {c}) = \langle \lnot o_\texttt {p}\rangle \) (i.e., the set of all plants that output \(\lnot o_\texttt {p}\) in the current time-step). Right: a controller strategy \(\mathcal {M}_\texttt {c}\) consistent with this universal controller w.r.t. the plant shown in Fig. 1 (right).
Example 3
Consider again the controller synthesis problem from Ex. 1 and a universal controller \(\mathcal {U}\) as shown in Fig. 2 (left). In the first time-step, as future behavior of the environment is unknown, the controller must set \(o_\texttt {c}\) to true if the plant also sets \(o_\texttt {p}\) to true. Hence, the prophecy for the output \(o_\texttt {c}\) at the initial state \(q_0\) in Fig. 2 (left), i.e., \(\kappa (q_0,o_\texttt {c}) = \langle o_\texttt {p}\rangle \), is the set of all plants that output \(o_\texttt {p}\) in the current time-step. Similarly, the prophecy for the output \(\lnot o_\texttt {c}\) at state \(q_0\), i.e., \(\kappa (q_0,\lnot o_\texttt {c}) = \langle \lnot o_\texttt {p}\rangle \), is the set of all plants that output \(\lnot o_\texttt {p}\) in the current time-step. Furthermore, once the environment outputs \(\lnot o_\texttt {e}\), we reach the state \(q_1\) where the controller can set any output as the specification is satisfied no matter what the controller does. The prophecy for both outputs \(o_\texttt {c}\) and \(\lnot o_\texttt {c}\) at state \(q_1\) is \(\langle \texttt{true}\rangle \), i.e., it can set either output for any plant. Similarly, if the environment outputs \(o_\texttt {e}\), and the output of the plant and the controller does not match, we reach the state \(q_2\) where the specification is violated no matter what the controller does. Hence, the prophecy for both output \(o_\texttt {c}\) and \(\lnot o_\texttt {c}\) at state \(q_2\) is \(\langle \texttt{false}\rangle \), i.e., there is no output that is correct for any plant.
Such a universal controller is universal in the sense that it represents a set of controllers for each plant as formalized next.
Definition 4
(Consistency). Given a universal controller \(\mathcal {U}= (S, s_0,\tau ,\kappa )\) and a plant \(\mathcal {M}_\texttt {p}\), a controller \(\mathcal {M}_\texttt {c}= (S^\texttt {c}, s_0^\texttt {c},\tau ^\texttt {c},o^\texttt {c})\) is said to be consistent with \(\mathcal {U}\) w.r.t. \(\mathcal {M}_\texttt {p}\), denoted by \(\mathcal {M}_\texttt {c}\vDash \mathcal {U}\parallel \mathcal {M}_\texttt {p}\), if for all \((s,s^\texttt {p},s^\texttt {c})\in \texttt {reach}(\mathcal {U}\times (\mathcal {M}_\texttt {p}\parallel \mathcal {M}_\texttt {c}))\), it holds that \(\mathcal {M}_\texttt {p}(s^\texttt {p})\in \kappa (s,o^\texttt {c}(s^\texttt {c}))\).
Intuitively, at each state of the universal controller, the corresponding plant state satisfies the prophecy for the controller output from that state. Given a universal controller \(\mathcal {U}\) and a plant \(\mathcal {M}_\texttt {p}\), one can find a controller \(\mathcal {M}_\texttt {c}\) such that \(\mathcal {M}_\texttt {c}\vDash \mathcal {U}\parallel \mathcal {M}_\texttt {p}\) (if one exists) by verifying the plant against each prophecy in the current state of the universal controller and picking a controller output for which the corresponding prophecy is satisfied by the plant.
Example 4
Consider the universal controller \(\mathcal {U}\) shown in Fig. 2 (left) and the plant strategy \(\mathcal {M}_\texttt {p}\) shown in Fig. 1 (right). We can construct a controller strategy \(\mathcal {M}_\texttt {c}\) that is consistent with \(\mathcal {U}\) w.r.t. \(\mathcal {M}_\texttt {p}\) by verifying the prophecies as follows. From the initial state \(q_0\), the plant \(\mathcal {M}_\texttt {p}\) sets \(o_\texttt {p}\) to true and hence, satisfies the prophecy \(\kappa (q_0, o_\texttt {c})\). Thus, a consistent controller has to set \(o_\texttt {c}\) to true in the first time-step. Later on from state \(q_0\), the plant \(\mathcal {M}_\texttt {p}\) continues setting \(o_\texttt {p}\) to true as long as the environment outputs \(o_\texttt {e}\). Hence, a consistent controller also has to set \(o_\texttt {c}\) to true as long as the environment outputs \(o_\texttt {e}\). As soon as the environment outputs \(\lnot o_\texttt {e}\), we reach state \(q_1\) in the universal controller \(\mathcal {U}\) from which the prophecy for \(o_\texttt {c}\) and \(\lnot o_\texttt {c}\) are \(\langle \texttt{true}\rangle \), and hence, the controller can set any output. By picking the prophecy \(\kappa (q_1,\lnot o_\texttt {c})\), the controller \(\mathcal {M}_\texttt {c}\) sets \(o_\texttt {c}\) to false for all future time-steps. With this, we obtain the controller strategy \(\mathcal {M}_\texttt {c}\) shown in Fig. 2 (right) which is consistent with \(\mathcal {U}\) w.r.t. \(\mathcal {M}_\texttt {p}\). Note that as we set controller outputs by verifying the prophecies for the plant \(\mathcal {M}_\texttt {p}\), we never had to verify prophecies at the state \(q_2\) in the universal controller \(\mathcal {U}\) where the specification is violated.
Given the above representation of controllers by universal controllers, our main goal is to find a universal controller such that given any admissible plant, the controller strategy consistent with them solves the logical controller synthesis problem. We call such a universal controller correct as formalized below.
Definition 5
(Correctness). Given a specification \(\varphi \), a universal controller \(\mathcal {U}\) is correct for \(\varphi \) if for all admissible plant strategies \(\mathcal {M}_\texttt {p}\), it holds that \(\mathcal {M}_\texttt {c}\vDash \mathcal {U}\parallel \mathcal {M}_\texttt {p}\) implies \(\mathcal {M}_\texttt {p}\parallel \mathcal {M}_\texttt {c}\vDash \varphi \).
Conversely, if all correct controllers for an admissible plant are consistent with the universal controller, we call such a universal controller most permissive.
Definition 6
(Permissiveness). Given a specification \(\varphi \), a universal controller \(\mathcal {U}\) is most permissive for \(\varphi \) if for all admissible plant strategies \(\mathcal {M}_\texttt {p}\), it holds that \(\mathcal {M}_\texttt {p}\parallel \mathcal {M}_\texttt {c}\vDash \varphi \) implies \(\mathcal {M}_\texttt {c}\vDash \mathcal {U}\parallel \mathcal {M}_\texttt {p}\).
Example 5
Consider the universal controller \(\mathcal {U}\) shown in Fig. 2 (left), the plant strategy \(\mathcal {M}_\texttt {p}\) shown in Fig. 1 (right), and the controller strategy \(\mathcal {M}_\texttt {c}\) shown in Fig. 2 (right) that is consistent with \(\mathcal {U}\) w.r.t. \(\mathcal {M}_\texttt {p}\). The universal controller \(\mathcal {U}\) is correct and most permissive for the specification \(\varphi \) in (1) and hence, the controller strategy \(\mathcal {M}_\texttt {c}\) solves the logical controller synthesis problem for \(\varphi \) with given plant strategy \(\mathcal {M}_\texttt {p}\).
We define the formal problem statement as follows:
Definition 7
(Universal controller synthesis). Given a specification \(\varphi \), the problem of universal controller synthesis is to find a universal controller that is correct and most permissive for \(\varphi \).
Computing a universal controller reduces to the problem of computing suitable prophecies. The following section presents an automata-based algorithm to compute prophecies for safety specifications. These prophecies build the foundation of our algorithm for synthesizing universal controllers.
4 Prophecies for Controller Synthesis
In this section, we introduce a class of prophecies, namely safe prophecies, which are sufficient to construct a universal controller for safety specifications that is both correct and most permissive.
4.1 Prophecies
The class of safe prophecies only considers the current and next state of execution to capture the safety part of the given specification. Intuitively, for the current choice of the controller output, a safe prophecy collects a set of plants for which this choice is safe, i.e., it can lead to an accepting run in the automaton. We define these prophecies for a given automaton:
Definition 8
Let \(\mathcal {A}= (Q,q_0,\delta ,\varOmega )\) be an automaton, \(q\in Q\) be a state in \(\mathcal {A}\), and \(\alpha \in 2^{{O_{\texttt {c}}}}\) be an output of the controller. The safe prophecy\(\mathbb {S}_\mathcal {A}^{q,\alpha }\) is the set
Given a state \(q\in Q\) and a controller output \(\alpha \in 2^{{O_{\texttt {c}}}}\), the set \(\mathbb {S}_\mathcal {A}^{q,\alpha }\) collects all plant strategies for which there exists a controller strategy \(\mathcal {M}_\texttt {c}\) from q that is consistent with the current output \(\alpha \) and produces only accepting runs with \(\mathcal {M}_\texttt {p}\) in the automaton, i.e., \( Runs (\mathcal {A},q,\mathcal {M}_\texttt {p}\parallel \mathcal {M}_\texttt {c})\subseteq \varOmega \). Intuitively, the safe prophecy of a controller’s choice collects all the plant strategies for which this choice is safe. Hence, for any safety LTL formula, safe prophecies provide necessary restrictions on the controller’s choices.
Theorem 1
Let \(\varphi \) be a safety LTL specification and \(\mathcal {A}= (Q,q_0,\delta ,\varOmega = safe (F))\) its equivalent safety automaton. The universal controller \(\mathcal {U}= (Q,q_0,\delta ,\kappa )\) with \(\kappa (q,\alpha ) = \mathbb {S}_{\mathcal {A}}^{q,\alpha }\) is most permissive for \(\varphi \).
The proofs of Thm. 1 and Thm. 2 can be found in the full version of this paper [23]. The theorem shows that every controller strategy that is correct for a plant is preserved in the prophecy set. Ensuring that the controller does not make any unsafe choices is sufficient to realize a safety specification, and we can show that the safe prophecies are sufficient to synthesize a correct universal controller realizing any safety specification once a plant strategy is given.
Theorem 2
Let \(\varphi \) be a safety LTL specification and \(\mathcal {A}= (Q,q_0,\delta ,\varOmega = safe (F))\) its equivalent safety automaton. The universal controller \(\mathcal {U}= (Q,q_0,\delta ,\kappa )\) with \(\kappa (q,\alpha ) = \mathbb {S}_{\mathcal {A}}^{q,\alpha }\) is correct for \(\varphi \).
The universal controller for our running example shown in Fig. 2 (left) is annotated with safe prophecies and hence, is correct and most permissive for the safety specification \(\varphi \) in (1).
4.2 Automata for Prophecies
Prophecies, as defined in Def. 2 and Def. 8, define sets of plants that are correct for an explicit controller choice. A suitable automaton model for prophecies are tree automata whose languages are sets of trees (in contrast to sets of traces for word automata). Every tree in the language of such an automaton corresponds to a strategy of a plant, which is also an infinite tree. We show that we can construct a tree automaton that correctly accepts the safe prophecy for a given controller choice. The basic idea of the construction is similar to the automaton to two-player game conversion for LTL synthesis [20]. A plant satisfies the prophecy if it has a correct reaction to any choice of the controller inputs. Additionally, we restrict the output of the controller in the first step of the automaton, i.e., the output we compute the prophecy for. This yields the following result.
Theorem 3
Let \(\mathcal {A}= (Q, q_0, \delta , \varOmega )\) be a safety automaton for the safety LTL formula \(\varphi \) and \(q_s \in Q, \alpha _s \in 2^{O_\texttt {c}}\) be an output of the controller. There exists a linear tree automaton \(\mathcal {A}'\) s.t. \(\mathcal {L}(\mathcal {A}') = \mathbb {S}_{\mathcal {A}}^{q_s,\alpha _s}\).
Proof
We construct a tree automaton \(\mathcal {A}'\) over \((2^{O_\texttt {p}})\)-labelled \(2^{I_\texttt {p}}\) trees that accepts all plants for which a controller strategy exists with the current choice \(\alpha _s\) that ensures the specification. The idea is to simulate the plant and controller behavior on the word automaton \(\mathcal {A}\), where the automaton is implicitly labelled with both plant and controller outputs, and only branches over environment outputs. To make the tree automaton labelled with plant outputs, we remove each controller output \(\beta _\texttt {c}\) from the labels and make the corresponding node branch over all possible plant inputs, i.e., outputs of both controller and environment, by taking all branches with inconsistent controller outputs (i.e., \(\ne \beta _\texttt {c}\)) to an accepting sink state. In addition, we simulate \(\mathcal {A}\) from \(q_s\) and restrict the initial choice of the controller to \(\alpha _s\) by introducing a new initial state \(q_0'\). Formally, the automaton \(\mathcal {A}' =(Q', q_0', T', \varOmega ')\) is defined as follows:
\(Q' = Q \uplus \{q_0',q_{sink}\}\),
\(T'\subseteq Q\times 2^{O_\texttt {p}} \times (2^{I_\texttt {p}} \rightarrow Q)\) is the minimal set such that
for all \(\beta _\texttt {p}\in 2^{O_\texttt {p}}\), there is a transition \((q_0', \beta _\texttt {p}, f)\) such that for all \(\beta \in 2^{I_\texttt {p}}\), \(f(\beta ) = {\left\{ \begin{array}{ll} \delta (q_s, \beta _\texttt {p}\cup \beta ) & \text {if } \beta \cap {O_{\texttt {c}}} = \alpha _s,\\ q_{sink} & \text {otherwise}, \end{array}\right. }\)
for all \(q \in Q\), \(\beta _\texttt {p}\in 2^{O_\texttt {p}}\), and \(\beta _\texttt {c}\in 2^{O_\texttt {c}}\), there is a transition \((q, \beta _\texttt {p},f)\) such that for all \(\beta \in 2^{I_\texttt {p}}\), \(f(\beta ) = {\left\{ \begin{array}{ll} \delta (q, \beta _\texttt {p}\cup \beta ) & \text {if } \beta \cap {O_{\texttt {c}}} = \beta _\texttt {c},\\ q_{sink} & \text {otherwise}, \end{array}\right. }\)
for all \(\beta _\texttt {p}\in 2^{O_\texttt {p}}\), there is a transition \((q_{sink}, \beta _\texttt {p}, f)\) such that \(f(\beta ) = q_{sink}\) for all \(\beta \in 2^{I_\texttt {p}}\).
\(\varOmega ' = safe (F')\) with \(F' = F \cup \{q_0',q_{sink}\}\).
Compared to \(\mathcal {A}\), the automaton \(\mathcal {A}'\) has two new states \(q_0'\) and \(q_{sink}\). For all transitions from \(q_0'\), we fix the controller output to be \(\alpha _s\) and quantify over all possible plant outputs. Afterwards, we branch over all possible plant inputs but only simulate the automaton \(\mathcal {A}\) when the controller output is \(\alpha _s\), otherwise, we go to the sink state \(q_{sink}\). Similarly, in the general case, we quantify over all possible controller outputs \(\beta _\texttt {c}\) and plant outputs \(\beta _\texttt {p}\), but only use the plant output to explicitly label the tree. Then, we branch over all possible plant inputs but only simulate the automaton \(\mathcal {A}\) when the controller output is \(\beta _\texttt {c}\), otherwise, we go to the sink state \(q_{sink}\). The runs of this automaton are all trees that branch over environment and controller outputs and are labeled with plant outputs that satisfy the prophecy \(\mathbb {S}_{\mathcal {A}}^{q_s,\alpha _s}\). Since the transition function follows a similar construction for reactive synthesis (without a plant) in [20], the correctness of the construction follows immediately. As \(\left|Q'\right| = \left|Q\right|+2\), the size of \(\mathcal {A}'\) is linear in the size of \(\mathcal {A}\).
Fig. 3.
A part of the tree automaton (without transitions of \(q_0\) and \(q_{sink}\)) with safe states \(F' = \{q_0',q_0,q_1\}\) for prophecy \(\mathbb {S}_{\mathcal {A}_\varphi }^{q_0,o_\texttt {c}} = \langle o_\texttt {p}\rangle \) of Fig. 2, where each function \(f_i\) shown as dashed edges.
Note that it is not possible to represent safe prophecies with a word automaton as we are looking for an automaton that accepts all plant strategies of any size, therefore infinite trees. One key insight is that we do not only have to verify the choices of the controller against the behavior of the plant, but, there must also exist a strategy of the controller such that all future behavior of the plant satisfies the specification. Both of these criteria are captured in the constructed tree automaton.
Example 6
Consider the universal controller in Fig. 2 (left) for the running example. A tree automaton \(\mathcal {A}'\) for prophecy \(\kappa (q_0,o_\texttt {c}) = \mathbb {S}_{\mathcal {A}_\varphi }^{q_0,o_\texttt {c}}\) is shown in Fig. 3. As we are considering a prophecy from the initial state \(q_0\), we have a new initial state \(q_0'\) that is a copy of \(q_0\). From \(q_0'\), we fix the controller output to be \(o_\texttt {c}\) for simulation, and branch over all possible plant outputs. Given plant output \(o_\texttt {p}\) from \(q_0'\), we simulate the automaton \(\mathcal {A}_\varphi \) by function \(f_1\) when the controller output is \(o_\texttt {c}\) (else we go to the sink state \(q_{sink}\)). Hence, it branches to state \(q_0\) and \(q_1\) depending on the environment outputs. Similarly, given plant output \(\lnot o_\texttt {p}\) from \(q_0'\), we simulate the automaton \(\mathcal {A}_\varphi \) by function \(f_2\) when the controller output is \(o_\texttt {c}\). From every other state, we branch over all possible plant and controller outputs. For example, from state \(q_1\), we fix the controller output to be \(o_\texttt {c}\) (resp. \(\lnot o_\texttt {c}\)) and simulate the automaton \(\mathcal {A}_\varphi \) by function \(f_3\) (resp. \(f_4\)) with consistent controller output. As every transition in \(\mathcal {A}_\varphi \) from \(q_1\) leads to \(q_1\), the function \(f_3\) maps every input with consistent controller output to \(q_1\) (and inconsistent controller output to \(q_{sink}\)).
Once we have the tree automaton for the prophecy, we can use it to construct an explicit controller consistent with a universal controller by verifying the plant strategies against the tree automaton. For verifying a plant against such a tree automaton, we check if the infinite tree produced by the plant (strategy) is an element of the language of the tree automaton. We refer to the procedure that constructs the automaton for the prophecy as
.
5 Universal Controller Synthesis
In this section, we present an automata-theoretic approach to synthesizing correct universal controllers from safety LTL formulas. We also present an algorithm that, given a plant and a universal controller, constructs a controller that is consistent with the plant and satisfies the specification.
5.1 Universal Controllers
Algo. 1 shows the main procedure for the construction of a universal controller. The first step is to construct an equivalent safety automaton \(\mathcal {A}_\varphi \) for the specification \(\varphi \). The state space of the automaton yields the initial state space for the universal controller. The algorithm continues with iterating over every pair of state and controller output, and builds the respective prophecy with the construction introduced in Section 4.2. Once the map \(\kappa \) contains all pairs of states and outputs, we build the universal controller \(\mathcal {U}\). The universal controller can be interpreted as follows: For a given environment output and state q, some output \(\alpha \) is taken for which the plant behaves as specified in the tree automaton \(\kappa (q, \alpha )\). Since the alphabet of the automaton \(\mathcal {A}_\varphi \) ranges over all propositions, the transition function \(\delta \) is also defined over the plant outputs. During composition, we ensure that the prophecy also agrees with the current output of the plant to ensure consistency.
Subautomata Sharing. Instead of constructing a new tree automaton for every state-output pair in \(\mathcal {A}_\varphi \), we build a global tree automaton that contains all possible plants for the specification and only set new initial states and transitions. The global tree automaton construction is similar to
but q is the initial state \(q_0\) of \(\mathcal {A}_\varphi \) and \(\alpha \) is not considered in the construction. One obtains the tree automaton \(\varOmega _\mathcal {T}= (Q, q_0, T, \varSigma )\) that accepts all plant and controller pairs that are accepting for the specification. In the loop of Algo. 1, the only construction step is changing the initial state in \(\mathcal {A}_\mathcal {T}\) to a duplicate of q and adding an initial step from q with \(\alpha \) to the transition relation T. For the implementation of this algorithm, as presented in Section 6, it suffices to store the new initial state and the controller outputs. The modified copy of the global tree automaton is only computed during the verification in Algo. 2.
5.2 Composition
Once the universal controller is computed, we can compose it with a plant to obtain a plant-specific controller that is consistent with the plant’s behavior. The algorithm operates on an on-the-fly exploration of the product state-space of the universal controller and the plant and is shown in Algo. 2. The new initial state of the controller is a tuple \((q_0, q_0')\), i.e., the initial states of the universal controller and the plant. Note that we omit double parentheses for function calls over tuple of universal controller and plant states whenever it is clear from the context. We use a
loop over the states to be explored in the composition as a termination condition. The body of the loop that ranges from line 5 to line 12 starts by computing a one-step composition from the current state \((q_c, q_p)\) in
which takes the states, the universal controller, and the plant as input. The result of this function is a list of edges, i.e., pairs over an assignment of the alphabet and future state, in the composition that are possible to reach. However, since not every computed edge is correct for the given plant, the prophecy of this explicit edge has to be checked first before adding it to the controller’s edges. To verify the plant, we first obtain the tree automaton \(\mathcal {A}_\mathcal {T}\) representing the prophecy with \(\kappa (q_c, \sigma )\) and change the input plant to a modified version \(\mathcal {M}_\texttt {p}'\) that starts in \(q_p\) with \(\sigma \). The membership check is then performed in line 9 with a call to
returning true if the tree produced by \(\mathcal {M}_\texttt {p}\) is an accepting run of \(\mathcal {A}_\mathcal {T}\). In case of the membership check being successful, the edge is a correct edge in the controller and is added to the set of edges and, if not already explored, the target of the edge is added to the queue. The result of the algorithm is then all explored states and edges with the starting state \((q_0, q_0')\).
Tree Automata Checking. The most involved computation is verifying the modified plant against the prophecy tree automaton. In Algo. 2, this check is performed in the function
. Following the literature [31], we encode this function into a 2-player game where the environment player chooses the inputs of the plant and the system player has to provide a correct output for every choice of the environment. If the system player wins, then the infinite tree produced by the plant’s Moore machine is contained in the language of the tree automaton. The winning condition of the game is safety, implied by the acceptance condition of the tree automaton, and the state space is linear in the size of the tree automaton and the plant.
Hashing. The number of automaton checks of Algo. 2 is \(\left|\varSigma \right| \times |\mathcal {U}| \times |\mathcal {M}_\texttt {p}|\), i.e., the product of the alphabet size, the universal controller size, and the plant size. We reduce the number of automata checks drastically by hashing intermediate results: For a solved game we obtain a set of winning and a set of losing states in the game. These states can be directly mapped back to the composition such that we maintain a function
that stores for already computed edge-state pairs if the game is winning or losing. Then, before calling
, we check if the current edge was hashed before and, if so, return the hashed result. In our experiments in Section 6, we observe that the number of real containment checks that are computed without hashing is one for almost all benchmarks. This is the case if every state is reachable for every initial transition from (\(q_0, q_0')\) since this is the first state that we compute the safety game for.
Early Termination. The local exploration of the state space allows the use of heuristics for termination during both, composition of universal controller with plant and construction of the game. One such heuristics is defined over the transition function of currently discovered edges: Once the explored set of edges has a transition for every possible output of the environment, then we can stop exploring the current edges and move on to the next state in the queue. We do this check before jumping from line 11 to line 6. Furthermore, we order the edgelist according to already explored states so that we look for such edges before verifying edges to new states. The semantics of the specification is used to reduce the size of the game to be solved during verification. Since the acceptance condition is solely based on the specification automaton, we can stop exploring the state space of the plant once we are in a clearly accepting/rejecting loop, e.g., a terminal state. The early termination heuristics all benefit from one key observation: the specifics of the plant implementation can often be ignored while solving the controller synthesis problem.
Note that for simplicity, we construct the controller as a Mealy machine, i.e., as usual for automata, we use edge labels instead of state labels. However, this can easily be transformed into Moore machines by ignoring the first environment output and moving the controller output to the source state of every edge.
5.3 Correctness and Complexity
Algo. 1 and Algo. 2 together compute a controller for a given specification and plant with the automata constructions presented in Section 4.2. The correctness of the algorithm immediately follows from (Thm. 2). As the tree automata for the prophecies are linear in the size of the deterministic specification automaton, solving the game in polynomial time results in the same complexity as the standard controller synthesis problem [20]. Moreover, as the number of prophecies is linear in the size of the specification automaton, the overall time complexity of universal controller synthesis remains doubly exponential in the size of the specification. In summary, we observe the following result:
Corollary 1
Let \(\varphi \) be a safety LTL formula. Algo. 1 returns a universal controller \(\mathcal {U}\) that is correct and most permissive for \(\varphi \). Furthermore, given an admissible plant \(\mathcal {M}_\texttt {p}\), Algo. 2 returns a controller \(\mathcal {M}_\texttt {c}\) such that \(\mathcal {M}_\texttt {c}\parallel \mathcal {M}_\texttt {p}\vDash \varphi \). The overall time complexity of computing \(\mathcal {M}_\texttt {c}\) using Algo. 1 and Algo. 2 is doubly-exponential in the size of the specification \(\varphi \) and linear in the size of the plant \(\mathcal {M}_\texttt {p}\).
Fig. 4.
We compare the execution times of unicon and the standard synthesis approach. Fig. 4a to Fig. 4c show the results of three different specification types on increasing robot benchmarks. Fig. 4d shows a cactus plot for the number of SYNTCOMP benchmarks solved in a certain time budget.
6 Experiments
We have implemented our approach in a prototype tool called unicon [25]. For benchmarking purposes, unicon additionally implements the standard controller synthesis algorithm that reduces the synthesis problem to game solving [20]. The tool is implemented in F# and uses FsOmegaLib [1] and spot [18] for automata operations and oink [17] for game solving. The experiments are performed on a computer with an Apple M1 Pro 8-core CPU and 16GB of RAM.
We evaluate our approach on a set of benchmarks where the controller guides a robot through a maze-like workspace, avoiding collisions with the walls and with a second (uncontrollable) robot. Given the size of the grid as a parameter, the workspace is encoded in the plant model as a grid of cells with some walls between the cells and walls around the boundary of the grid. Initially, the controller robot is placed in the center of the grid and the plant robot in the bottom left corner. At each step, the robots can either stay or move in four directions: up, down, left, and right. The controller robot has sensors to detect the obstacles (i.e., walls or the plant robot) if they are adjacent to it or when there is a collision. The behavioral objective of the controlled robot is specified as an LTL formula. We consider three different types of specifications: Specification type 1 is an invariant
, which simply states that the controller must always avoid collisions. In specification type 2, we add some more information about the setting into the temporal formula: \( \lnot col \ W\ \lnot \texttt {assump}_\texttt {p}\), where the assumption \(\texttt {assump}_\texttt {p}\) expresses that a collision can occur only if in the previous step there was an obstacle in some direction and the controller moved in that direction or stayed in the same position (which might lead to a collision if the obstacle was the other robot). Specification type 3 is a condition that only restricts the first three steps in the execution, requiring that during those three steps, the robot does not see an obstacle in the up direction:
.
Evaluation on robot benchmarks. The results of the experiments are shown in Fig. 4, which shows the comparison of the execution times of unicon (i.e., the total time for synthesizing the universal controller and extracting a correct controller using Algos. 1 and 2) with the standard controller synthesis approach to compute a correct controller. In all three types of specifications, our approach scales well with growing grid size, while the running time of the standard approach quickly becomes prohibitively large. The reason is that standard controller synthesis constructs the complete composition of the plant and the specification automaton to solve the synthesis problem, while the universal controller synthesis composes the plant and the prophecies on-the-fly. Since the prophecy size is independent of the plant size, the universal controller synthesis scales better with the increasing grid size. Specification type 2 performs better than specification type 1, as the added information of the assumption allows for simpler prophecies. Simple specifications like type 3 are most beneficial as the prophecies only need to consider three steps into the future.
Baseline evaluation on SYNTCOMP benchmarks. The benchmarks of the annual SYNTCOMP reactive synthesis competition [28] are often used to evaluate synthesis algorithms. Since the benchmarks do not contain plant models, we cannot use them to evaluate the scalability of our approach, but we still include them here as a baseline to evaluate the overhead caused by the computation of the universal controller. We selected the 68 benchmarks that have safety requirements and explicit environment assumptions, and translated the assumption formulas into plant models. As shown in Fig. 4d, unicon shows similar performance to standard synthesis. Because of the small size of the plant models resulting from the assumption formulas, the overhead for the universal controller is not compensated by the improved performance in the size of the plant model. Still, computation times remain close, showing that unicon is able to scale to practical problem instances.
7 Conclusions
Universal controllers have three major advantages over standard control strategies: The first advantage is the improved scalability due to the fact that the universal controller is constructed independently of the plant. There is no free lunch – adapting the universal controller to a specific plant does require an analysis of the plant model. However, we only need to verify the prophecy, not the original specification. Simple prophecies can be checked without a full exploration of the state space. There is no loss of completeness: the adaptation of the universal controller to a particular plant succeeds whenever the synthesis problem is realizable for the plant. A second advantage is that the universal controller is adaptable to new plants; if the plant model changes, it is not necessary to re-synthesize the universal controller, only the prophecies need to be re-evaluated. In principle, the controller can even be adapted to dynamic changes in the plant by evaluating the prophecies on-the-fly. A third major advantage of the universal controller is its explainability: the prophecy identifies the specific property of the plant that makes it safe to choose the move. If the adaptation fails, the violated prophecies identify properties of the plant that make it unrealizable. In future work, we plan to exploit these advantages by constructing controllers that adapt to new situations dynamically and explain their behavior to the user in terms of these changes.
Acknowledgements
This work is funded by the DFG grant 389792660 as part of TRR 248 - CPEC, by the European Union with ERC Grant HYPER (No. 101055412), and by the Emmy Noether Grant SCHM 3541/1-1. Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them.
Open Access This chapter is licensed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license and indicate if changes were made.
The images or other third party material in this chapter are included in the chapter's Creative Commons license, unless indicated otherwise in a credit line to the material. If material is not included in the chapter's Creative Commons license and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder.
The formula requires that the controller matches the output of the plant as long as the environment sets its output to true. As the controller cannot observe the plant output before setting its own output, it is impossible to build a correct controller independently of the plant: unless the environment sets its output to false, the controller must know the output produced by the plant one time step in advance. We express this information with the prophecies \(\langle o_\texttt {p}\rangle \), indicating that the plant will output true, and \(\langle \lnot o_\texttt {p}\rangle \), indicating that the plant will output false. The universal controller then reacts to \(\langle o_\texttt {p}\rangle \) by setting \(o_\texttt {c}\) to true and to \(\langle \lnot o_\texttt {p}\rangle \) by setting \(o_\texttt {c}\) to false.
. A trace is evaluated against an LTL specification \(\varphi \) in the ususal way. We refer to [6, Chapter 5.1.2] for the detailed semantics.
) such that \(\kappa (q_1,*) = \langle \texttt{true}\rangle \) (i.e., the set of all plants), \(\kappa (q_2,*) = \langle \texttt{false}\rangle \) (i.e., the empty set), \(\kappa (q_0,o_\texttt {c}) = \langle o_\texttt {p}\rangle \) (i.e., the set of all plants that output \(o_\texttt {p}\) in the current time-step), and \(\kappa (q_0,\lnot o_\texttt {c}) = \langle \lnot o_\texttt {p}\rangle \) (i.e., the set of all plants that output \(\lnot o_\texttt {p}\) in the current time-step). Right: a controller strategy \(\mathcal {M}_\texttt {c}\) consistent with this universal controller w.r.t. the plant shown in Fig. 1 (right).
.
but q is the initial state \(q_0\) of \(\mathcal {A}_\varphi \) and \(\alpha \) is not considered in the construction. One obtains the tree automaton \(\varOmega _\mathcal {T}= (Q, q_0, T, \varSigma )\) that accepts all plant and controller pairs that are accepting for the specification. In the loop of Algo. 1, the only construction step is changing the initial state in \(\mathcal {A}_\mathcal {T}\) to a duplicate of q and adding an initial step from q with \(\alpha \) to the transition relation T. For the implementation of this algorithm, as presented in Section 6, it suffices to store the new initial state and the controller outputs. The modified copy of the global tree automaton is only computed during the verification in Algo. 2.
loop over the states to be explored in the composition as a termination condition. The body of the loop that ranges from line 5 to line 12 starts by computing a one-step composition from the current state \((q_c, q_p)\) in
which takes the states, the universal controller, and the plant as input. The result of this function is a list of edges, i.e., pairs over an assignment of the alphabet and future state, in the composition that are possible to reach. However, since not every computed edge is correct for the given plant, the prophecy of this explicit edge has to be checked first before adding it to the controller’s edges. To verify the plant, we first obtain the tree automaton \(\mathcal {A}_\mathcal {T}\) representing the prophecy with \(\kappa (q_c, \sigma )\) and change the input plant to a modified version \(\mathcal {M}_\texttt {p}'\) that starts in \(q_p\) with \(\sigma \). The membership check is then performed in line 9 with a call to
returning true if the tree produced by \(\mathcal {M}_\texttt {p}\) is an accepting run of \(\mathcal {A}_\mathcal {T}\). In case of the membership check being successful, the edge is a correct edge in the controller and is added to the set of edges and, if not already explored, the target of the edge is added to the queue. The result of the algorithm is then all explored states and edges with the starting state \((q_0, q_0')\).
. Following the literature [31], we encode this function into a 2-player game where the environment player chooses the inputs of the plant and the system player has to provide a correct output for every choice of the environment. If the system player wins, then the infinite tree produced by the plant’s Moore machine is contained in the language of the tree automaton. The winning condition of the game is safety, implied by the acceptance condition of the tree automaton, and the state space is linear in the size of the tree automaton and the plant.
that stores for already computed edge-state pairs if the game is winning or losing. Then, before calling
, we check if the current edge was hashed before and, if so, return the hashed result. In our experiments in Section 6, we observe that the number of real containment checks that are computed without hashing is one for almost all benchmarks. This is the case if every state is reachable for every initial transition from (\(q_0, q_0')\) since this is the first state that we compute the safety game for.
, which simply states that the controller must always avoid collisions. In specification type 2, we add some more information about the setting into the temporal formula: \( \lnot col \ W\ \lnot \texttt {assump}_\texttt {p}\), where the assumption \(\texttt {assump}_\texttt {p}\) expresses that a collision can occur only if in the previous step there was an obstacle in some direction and the controller moved in that direction or stayed in the same position (which might lead to a collision if the obstacle was the other robot). Specification type 3 is a condition that only restricts the first three steps in the execution, requiring that during those three steps, the robot does not see an obstacle in the up direction:
.
