Do What You Know: Coupling Knowledge with Action in Discrete-Event Systems

arXiv:2108.02000 · cs.AI, cs.SY, eess.SY · Submitted 2021-07-25 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: We're looking at the paper: "Do What You Know".

Jane: Here's the gist of the paper. The gist: An epistemic model for decentralized discrete-event systems with nonbinary control is presented.

Tom: Decentralized Control and System Modeling This work focuses on systems modeled as discrete-event systems (DES) in the context of decentralized supervisory control, which is relevant to modern Internet of things applications like smart vehicles and home automation.

Jane: The paper defines a discrete-event system plant G as a finite state automaton (FSA) G = (Σ, Q, δ, q0) and defines its language L(G) as the set of physically possible behaviours of G Decentralized Supervisory Control Architecture Decentralized control involves allowing an arbitrary number of supervisors to jointly perform the control, where each supervisor observes and controls a subset of events.

Tom: The architecture is formally defined using sets like Σi,c for controllable events and Σi,o for observable events for each supervisor i.

Paper summary: Tom: So wrapping up on "Do What You Know: Coupling Knowledge with Action in Discrete-Event Systems", Richard Ean and Karen Rudie present this epistemic model that links what supervisors know to what they actually do, which helps define the necessary and sufficient conditions for solving the problem >

Jane: It seems like the paper is really pushing for a more intuitive way to talk about these complex control problems by using a formalism that mimics natural language, making it easier to determine how requirements should be revised when things don't go as planned >

Lu: They use epistemic logic and define inference-observability as the necessary and sufficient condition to solve the decentralized supervisory control problem when supervisors can infer some knowledge of others >

Meng: From a deployment standpoint, this framework seems strong because it gives you a clear structure for checking if your entire supervisor setup is feasible before you even start coding complex policies >

Lalam: The paper shows that there exists a set N of n supervisors that solves the problem if I is controllable and inference-observable, which is their main result connecting these ideas >

Tom: And they extend this to include the complete set of control decisions from Yoo and Lafortune two thousand four resulting in CD = five which relaxes that condition of inference-observability >

Jane: Ultimately, it suggests that epistemic logic can be a universal tool for studying decentralized supervisory control problems beyond just those specific classes they mentioned >

Conclusion: Tom: So we’re wrapping up on "Do What You Know: Coupling Knowledge with Action in Discrete-Event Systems" by Ean and Rudie, which is basically about making sure supervisors know what to do based on what they already know.

Jane: They take these complex decentralized systems, you know, those things like smart grids or autonomous vehicles where lots of little controllers are working together, and they put an epistemic logic layer on top of it.

Lu: The core idea is that the necessary and sufficient conditions for solving the problem—finding a working set of supervisors—actually encode the actions those supervisors have to take. It’s this direct coupling between knowledge and action that’s the big mechanism here.

Meng: So, if you look at their main result, it says there's a set of n supervisors that solves the whole thing if I is controllable and inference-observable. That sounds like a solid way to check feasibility before you start building anything complex.

Lalam: From what I’m seeing, they use this logic structure to mimic how people actually reason in control problems, which makes it much clearer than just writing down a huge list of rules. It gives you an anthropomorphic view of the control problem itself.

Tom: That direct mapping between the knowledge supervisors need and the actions they take is what’s really neat for engineers; it lets you trace exactly why a supervisor needs to have that specific piece of information to make its required move.

Jane: It means if your system isn't solving the problem, you can look at this model and see exactly which piece of knowledge is missing or which action is wrong, instead of just debugging a mess.

Lu: They also extended this to include the complete set of control decisions from Yoo and Lafortune, which gives them a slightly relaxed condition called inference-observability. That’s an interesting tweak for practical implementation.

Tom: It sounds like they’ve given us a really useful tool here to move straight from having a working supervisor solution to actually knowing if that solution is truly the right one under all the conditions.

Jane: Exactly, and this framework suggests that epistemic logic isn't just for niche theoretical problems anymore; it can be used more universally across different kinds of decentralized control setups.

Lu: It really opens up the door to using this kind of reasoning not just for those specific classes of control problems they mentioned, but for studying a much broader range of decentralized systems.

Meng: The implication for me is that when I’m shipping something, I can use this idea to rigorously test my supervisor architecture against these necessary and sufficient conditions instead of just guessing if it will scale up correctly.

Tom: It sounds like the authors have given us a way to talk about these control problems in a language that feels closer to how we actually think about decision-making under uncertainty.

Jane: And this approach could help people build systems that are more robust because they’ve explicitly modeled the knowledge dependencies between all the controllers involved.

Lu: It’s really about making the reasoning process explicit, which is a huge step forward for AI-driven control where we want to trust what the system knows.

Tom: So basically, we move from just saying "this works" to being able to mathematically prove why it works and what else it needs to function properly.

Richard Ean, Karen Rudie

Queen's University · Natural Sciences and Engineering Research Council of Canada · General Dynamics Land Systems–Canada · Defence Research and Development Canada

cs.AI, cs.SY, eess.SY

Submitted: 2021-07-25

Updated: 2022-05-30

DOI: 10.1007/s10626-023-00381-z

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 91/100

The gist: The gist: An epistemic model for decentralized discrete-event systems with nonbinary control is presented.

Key concepts

Discrete-Event Systems (DES)
These are systems where state changes happen due to discrete events. The paper models them using Finite State Automata (FSA) to define physically possible behaviors and languages generated by the system.
Epistemic Logic
This is a formal logic used to reason about knowledge, allowing supervisors to be modeled anthropomorphically. It uses modal operators like 'K' (know), enabling discussions on what supervisors must know for a problem to be solvable.
Inference-Observability
This condition defines when a decentralized control problem is solvable. It requires that at every state, either at least one supervisor can make an unambiguous decision, or the event in question must be enabled, ensuring consistent control outcomes.

Summary

The gist: An epistemic model for decentralized discrete-event systems with nonbinary control is presented.

Decentralized Control and System Modeling

This work focuses on systems modeled as discrete-event systems (DES) in the context of decentralized supervisory control, which is relevant to modern Internet of things applications like smart vehicles and home automation. The paper defines a discrete-event system plant G as a finite state automaton (FSA) G = (Σ, Q, δ, q0) and defines its language L(G) as the set of physically possible behaviours of G

Decentralized Supervisory Control Architecture

Decentralized control involves allowing an arbitrary number of supervisors to jointly perform the control, where each supervisor observes and controls a subset of events. The architecture is formally defined using sets like Σi,c for controllable events and Σi,o for observable events for each supervisor i. The closed-loop behaviour of the plant under joint supervision is denoted by L(fN /G)

Epistemic Logic for Control Reasoning

Epistemic logic provides a natural modelling paradigm that parallels natural languages, giving better intuition into the reasoning behind the decisions that supervisors make. The semantics of epistemic formulae are given through the use of a structure called a Kripke structure. Inference-observability is defined as the necessary and sufficient condition to solve DSCOP when supervisors are allowed to infer the knowledge of other supervisors to some extent.

Coupling Knowledge with Action

The novelty of this model is that the necessary and sufficient conditions for problem solvability encapsulate the actions that supervisors must take, resulting in a direct coupling between knowledge and action. This coupling is demonstrated through a line-by-line correspondence between the expressions of knowledge supervisors must possess and their required actions. The main result states that there exists a set N of n supervisors that solves DSCOP iff I is controllable and inference-observable

Extended Decision Set and Universal Formalism

The framework is extended to include the complete set of control decisions from Yoo and Lafortune (2004), resulting in CD = 5, which yields a relaxed condition of inference-observability The paper demonstrates that epistemic logic can be used as a universal tool in the study of decentralized supervisory control.

Conclusion and Implications

The framework aids in going directly from a working supervisor solution to the necessary and sufficient conditions that would match such a solution. This approach allows for an anthropomorphic perspective and language to understand and discuss the control problem. The framework can aid in going directly from a working supervisor solution to the necessary and sufficient conditions that would match such a solution. The paper suggests that epistemic logic can be used to discuss not only some specific classes of DSCOP (Ricker and Rudie, 2007, 2000), but also more universally

References

R. Cieslak, C. Desclaux, A. S. Fawaz, and P. Varaiya, “Supervisory control of discreteevent processes with partial observations,” IEEE Transactions on Automatic Control, vol. 33, no. 3, pp. 249–260, 1988

K. Rudie and W. M. Wonham, “Think globally, act locally: decentralized supervisory control,” IEEE Transactions on Automatic Control, vol. 37, no. 11, pp. 1692–1708, 1992

T.-S. Yoo and S. Lafortune, “A general architecture for decentralized supervisory control of discrete-event systems,” Discrete Event Dynamic Systems, vol. 12, no. 3, pp. 335–377, 2002

S. L. Ricker and K. Rudie, “Knowledge is a terrible thing to waste: Using inference in discrete-event control problems,” IEEE Transactions on Automatic Control, vol. 52, no. 3, pp. 428–441, 2007

R. Ean and K. Rudie, “Epistemic interpretations of decentralized discrete-event system problems,” 2022, to appear in Discrete Event Dynamic Systems

W. M. Wonham and K. Cai, Supervisory Control of Discrete-Event Systems

C. G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems, 2nd ed., Springer-Verlag GmbH, 2007

J. H. Prosser, M. Kam, and H. G.

Improvements for AI systems

  1. Decentralized control agents can make conditional decisions based on knowledge of other agents by employing a fusion rule that mimics natural language, as described in This direct coupling between knowledge and action—in a formalism that mimics natural language—makes it easier, when the problem conditions fail, to determine how the problem requirements should be revised.

  2. AI systems can be designed to possess an epistemic model where supervisors can infer the knowledge of other supervisors, enabling them to issue control decisions based on what they know, such as supervisor i issuing on if the supervisor knows that the plant is in a state at which the event sigma can be enabled.

  3. A robust verification algorithm for supervisor existence and synthesis can be developed by using a single proof that demonstrates the correctness of these processes, which runs as a coroutine with partitioning controllable events.

  4. The system's solvability condition for decentralized control problems can be characterized by inference-observability, which is the necessary and sufficient condition to solve DSCOP when supervisors are allowed to infer the knowledge of other supervisors to some extent.

  5. AI systems can utilize a generalized inference-observability condition, which allows for a default decision of an event to either enable or disable when all supervisors abstain, leading to a set of control decisions CD = on, off, weak on, weak off, abstain.

  6. The system can be engineered to achieve strong C&P co-observability or strong D&A co-observability by restricting the control decisions to subsets like only off, abstain or only on, abstain, which are derived from the generalized inference-observability condition.

Related papers