Decentralized Problems of Discrete-Event Systems: Epistemic Reasoning and Graph Representation

Abstract

This thesis provides modelling formalisms for decentralized problems of discrete-event systems for better derivation of problem solvability and solution constructions and for comparison of one decentralized architecture with another. The thesis establishes equivalence between three classes of problems---observation problems, diagnosis problems, and control problems---in terms of Turing reduction. Through the reduction, the thesis demonstrates that the solvability of the control problems is undecidable, alongside the similar result known for the other two classes of problems. Moreover, since the observation problems are formally simpler, the thesis advocates focusing research effort on these problems whenever suitable, i.e., when the results can transfer to the other two classes of problems via the reduction. The thesis then puts into uniform frameworks solutions to decentralized problems, characterized by their architectures. Two such frameworks have been proposed, one formalized using epistemic logic, while the other in terms of graph theory. Both frameworks capture the essential indistinguishability relations. The epistemic logic formalism is primarily suited for methodologically deriving problem solvability conditions and solution constructions under a given architecture. The methodology promotes coupling knowledge and action, so that a problem solvability condition directly expresses what knowledge an agent needs to perform its actions. This contrasts with the traditional case-by-case, ad hoc approach. The resulting epistemic expressions are closer to human reasoning than the traditionally-used predicate logic. We provide epistemic expressions for well-known problem solvability conditions. Being able to circumscribe a collection of such conditions in a uniform and concise modelling paradigm, we are able to refine the known hierarchy of such conditions in a more concise manner. The graph theoretical formalism provides a direct approach to compare architectures. This contrasts with the traditional approach in which one first derives problem solvability conditions for the architectures to be compared, and then shows that one condition (strictly) implies another. The approach also gives a visually intuitive model for understanding why a given architecture is superior to another.