A Uniform Approach to Compare Architectures in Decentralized Discrete-Event Systems

arXiv:2210.16511 · eess.SY, cs.SY · Submitted 2022-10-29 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: Hi, I'm Rosa.

Dev: And I'm Dev, here with Taro.

Rosa: We're looking at the paper: "A Uniform Approach to Compare Architectures in Decentralized Discrete-Event Systems".

Dev: Here's the gist of the paper. The gist: A method based on morphisms between graphs has been extracted to yield a uniform approach to compare the permissiveness of the architectures.

Rosa: Decentralized Problems Decentralized control problems are formally defined, which can be simplified by reducing them to observation problems using facts from Ritsuka and Rudie

RR23: .

Dev: Problem 2.1 defines the Control Problem as constructing local decision functions and fusion rules such that specific conditions regarding the language languages K and L are met

RR23: .

Rosa: This problem is denoted by C(L, K, Pi, Σc,i).

Paper summary: Rosa: So, this paper, "A Uniform Approach to Compare Architectures in Decentralized Discrete-Event Systems," it’s basically saying that comparing how local decisions get fused into a global decision—that fusion rule, or architecture—isn't as hard as we thought.

Dev: Right. The authors are tackling the problem where you have these decentralized systems, and you want to know if one way of fusing those local decisions is better than another one. They say current ways of comparing them are a mess because they usually rely on making up examples or individual inspiration that shows if one architecture is more permissive than another >

Taro: So the core idea here is to get rid of that case-by-case ingenuity and find a uniform way to compare them, which they call an architecture, and they achieve this by using something based on morphisms between graphs >

Rosa: Exactly. They start by formalizing these decentralized control problems, which they reduce down to these observation problems using some facts from Ritsuka and Rudie RR23 >

Dev: And then Theorem two point three sets up an equivalence: you solve a control problem if you can solve a set of observation problems for each condition in Sigma c > <ref:2210.16511#pg3>

Taro: So the comparison then boils down to checking the relationship between the sets Of and Og of solvable observation problems, where if all problems solvable by one architecture are also solvable by another, that means it’s at least as permissive >

Rosa: And this paper provides a direct way to check that relationship without needing to go through all those complex characterizations and counterexamples they mentioned earlier >

Dev: They describe the problem as an observation graph and a solution based on a fusion rule as a decision graph, and the solvability is then thought of as determining if the decision graph has the capacity to embed the observation graph >

Taro: So they introduce these two concepts: an Observation Graph defined by a symmetric relation N on L where s and t are related if their local observations differ in exactly those components N >

Rosa: And a Decision Graph for a fusion rule f, which is defined over a set D of combinations of local decisions, using the symmetric relation approximate to define when two decision tuples are related >

Dev: The link between them is formalized through this mapping g = <fiPi>, which they call a type of graph morphism and it has to satisfy two conditions >

Taro: One is Node-Colour Preserving, meaning the mapping preserves node colouring, so it achieves the desired fused decision >

Rosa: And the other one is Edge-Colour Intensive, meaning N includes N prime, so only agents observing s and t differently can issue different decisions for those two strings >

Dev: Theorem three point five states that an Observation Problem has a solution if and only if there exists a morphism from the observation graph to the decision graph that satisfies these conditions >

Taro: And Theorem four point one is the main result for comparing architectures, which says fusion rule f prime is more permissive than f if and only if there is a graph morphism from D to D prime satisfying those same graph morphism conditions > <ref:2210.16511#pg2>

Conclusion: Rosa: So what does this all mean for us? The paper "A Uniform Approach to Compare Architectures in Decentralized Discrete-Event Systems" provides a concrete, mathematical tool—the observation and decision graphs combined with these specific graph morphisms—to directly compare decentralized architectures >

Dev: It cuts through the need for those indirect paths through characterizations and counterexamples that the authors said are hard to do because they rely on case-by-case ingenuity >

Taro: For someone who just listens to this show, it means we don't have to build a whole new set of rules every time we want to check if a new fusion rule is better than an old one; you just look at the morphism between the graphs >

Rosa: It's about taking something that used to be an ad hoc process and turning it into a systematic procedure, which is really what this work claims they extracted from those earlier research efforts >

Dev: The authors are showing that this approach works for fusion rules with finite, bounded numbers of decisions, giving us a direct and easy way to compare the corresponding architectures >

K. Ritsuka, K. Rudie

eess.SY, cs.SY

Submitted: 2022-10-29

Updated: 2023-12-26

DOI: 10.1016/j.automatica.2024.111683

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

Importance score: 81/100

The gist: The gist: A method based on morphisms between graphs has been extracted to yield a uniform approach to compare the permissiveness of the architectures.

Key concepts

Observation Graph: This graph represents the decentralized problem where nodes are possible system states (strings in L). Edges connect states that differ only by a specific subset of local observations (N). It captures how agents' local data relates to each other across different scenarios.
Decision Graph: This graph models the fusion rule, where nodes represent combinations of local decisions. Edges connect decision combinations that are considered equivalent under the fusion rule (≈N). It shows how the chosen architecture groups or merges different local choices.
Graph Morphism: A mapping between the observation graph and decision graph that must satisfy two conditions: preserving node coloring (achieving the fused decision) and being edge-color intensive. This morphism directly links a specific fusion rule architecture to its solvability conditions for decentralized problems.

Summary

The gist: A method based on morphisms between graphs has been extracted to yield a uniform approach to compare the permissiveness of the architectures.

Decentralized Problems

Decentralized control problems are formally defined, which can be simplified by reducing them to observation problems using facts from Ritsuka and Rudie [RR23]. Problem 2.1 defines the Control Problem as constructing local decision functions and fusion rules such that specific conditions regarding the language languages K and L are met [RR23]. This problem is denoted by C(L, K, Pi, Σc,i).

Problem 2.2 introduces the Decentralized Observation Problem, which requires constructing local decision functions fi for agents i ∈ N and a fusion rule f such that for all s ∈ L, the condition s ∈ K ⇒ f(f1P1(s),..., fnPn(s)) = 1 and s ∈ L − K ⇒ f(f1P1(s),..., fnPn(s)) = 0 is satisfied [RR23]. This problem is denoted by O(L, K, Pi).

Theorem 2.3 establishes an equivalence between the control problem and a set of observation problems: solving a control problem C(f, L, K, Pi, Σc,i) is equivalent to solving the observation problems O(f, Lσ, Kσ, Pi) for each σ∈Σc [RR23]. The comparison of architectures is then stated as determining the relationship between the sets Of and Og of solvable observation problems: if all problems solvable by f are solvable by g, i.e., if Of ⊆ Og, then g is at least as permissive as f [RR23].

Uniform Approach to Compare Fusion Rules

The paper aims to derive a uniform approach for easy and direct comparison of decentralized architectures without needing to pass indirectly through characterizations and counterexamples [RR22]. The approach describes a decentralized problem as an observation graph and a solution based on a fusion rule f as a decision graph, expressing the problem as finding a way of folding the observation graph into the decision graph formally in terms of graph morphism [RR22]. The solvability condition is then thought of as determining if the decision graph has the capacity to embed the observation graph [RR22].

The core concepts introduced are:

Observation Graph: Defined by a symmetric relation ∼N on L, where s ∼N t if and only if the two tuples ⟨Pi⟩s = (P1(s),..., Pn(s)) and ⟨Pi⟩t = (P1(t),..., Pn(t)) differ by exactly the components indexed by N [RR22]. This forms an undirected graph (L, ∼) called the observation graph, where nodes are strings in L and edges are colored by subsets of N [RR22].
Decision Graph: Defined for a fusion rule f over a set D of combinations of local decisions (d1,..., dn), using symmetric relations ≈N on D, where (d1,..., dn) ≈N (d′1,...) when the two tuples differ by exactly the components indexed by N [RR22]. This forms an undirected graph (D, ≈) called the decision graph [RR22].

Graph Morphisms and Solvability Characterization

The relationship between these two graphs is formalized through a mapping g = ⟨fiPi⟩, which is a type of graph morphism [RR22]. This mapping must satisfy two conditions:

GM-1: Node-Colour Preserving, meaning the mapping preserves node colouring, that is, g achieves the desired fused decision [RR22].

GM-2: Edge-Colour Intensive, meaning N ⊇ N′, i.e., only agents observing s and t differently can issue different decisions for the two strings [RR22]. This property captures feasibility [RR23].

Theorem 3.5 states that an Observation Problem O(f, L, K, Pi) has a solution if and only if there exists a morphism from the observation graph to the decision graph (representing the architecture’s fusion rule) satisfying the morphism conditions GM [RR22]. This theorem provides a direct way to check for problem solvability.

Comparing Architectures

Theorem 4.1 provides the main result for comparing architectures directly: "Given fusion rules f, f′ and their respective decision graphs D, D′, the fusion rule f′ is more permissive than f (i.e., if O(f, L, K, Pi) ∈ Of, then O(f′, L, K, Pi) ∈ O′f) if and only if there is a graph morphism from D to D′ satisfying the graph morphism conditions GM" [RR22].

This result relies on Lemma 4.2, which states that for every decision graph (D, ≈N), there is an isomorphic observation graph where the isomorphism preserves node- and edge-colouring [RR23]. The proof shows that if a morphism g: D → D′ satisfies GM, it implies that all problems solvable with f are also solvable with f' [RR22]. Conversely, if all observation problems solvable with f are solvable with f', then there must exist a morphism from D to D' satisfying GM [RR23].

Illustrative Examples of Comparison

The paper illustrates the comparison process through several examples:

Example 4.3 shows how the C&P∧D&A architecture is weaker than the C&P architecture by giving a decision graph morphism that sends all nodes in the dashed box to (1, 1) [RR22].
Example 4.5 demonstrates incomparability between the conjunctive architecture (f = ∧) and the disjunctive architecture (f = ∨) by showing that no morphism exists in either direction between their respective decision graphs [RR23].

In summary, the work proposes two tools—observation graphs and decision graphs—to study decentralized observation problems, providing a systematic approach to directly compare decentralized architectures through graph morphisms [RR22]. This method bypasses the need for deriving explicit problem solvability characterizations first. The paper concludes that for fusion rules with finite, bounded numbers of decisions, this provides a direct and easy approach to compare the corresponding architectures [RR22].

Improvements for AI systems

Uniform Architecture Comparison: The system can directly compare two decentralized architectures by checking if there is a graph morphism from one decision graph to another satisfying conditions GM, determining if one architecture is strictly more permissive than the other.
Solvability Characterization Derivation: The system can derive a uniform approach to compare architectures without needing to pass indirectly through characterizations and counterexamples by describing a decentralized problem as an observation graph and a solution based on a fusion rule as a decision graph, which can then be folded into each other via graph morphisms.
Equivalence Detection: The system can determine if two architectures are equivalent by checking for the existence of graph morphisms in both directions between their respective decision graphs, which accounts for cases where different formulations describe the same underlying control behavior.

Sources

Equivalence of Decentralized Observation, Diagnosis, and Control Problems in Discrete-event Systems