Asynchronous, distributed, decision-making systems with semi-autonomous entities: A mathematical framework

For many military and civilian large-scale, real-world systems of interest, data are first acquired asynchronously, i.e., at irregular intervals of ti me, at geographically-dispersed sites, processed utilizing decision-making algorithms, and the processed data then disseminated to other appropriate s ites. The term real-world refers to systems under computer control that rel ate to everyday life and are beneficial to the society in the large. The tr aditional approach to such problems consists of designing a central entity which collects all data, executes a decision-making algorithm sequentially to yield the decisions, and propagates the decisions to the respective site s. Centralized derision-making algorithms are slow and highly vulnerable to natural and artificial catastrophes. Recent literature includes successful asynchronous, distributed, decision-making algorithm designs wherein the l ocal decision making at every site replaces the centralized decision making to achieve faster response, higher reliability, and greater accuracy of th e decisions. Two key issues include 1) the lack of an approach to synthesiz e asynchronous, distributed, decision-making algorithms, for any "globally" optimal. In truth, however, as the frequency of the sensor data given prob lem, and 2) the absence of a comparative analysis of the quality of their d ecisions. This paper proposes MFAD, a Mathematical Framework for Asynchronous Distrib uted Systems, that permits the description of centralized decision-making a lgorithms and facilities the synthesis of distributed decision-making algor ithms. MFAD is based on the Kohn-Nerode distributed hybrid control paradigm . It has been a belief that since the centralized control gathers every nec essary data from all entities in the system and utilizes them to compute th e decisions, the decisions may be increases and the environment gets larger , dynamic, and more complex, the decisions are called into question. In the distributed decision-making system, the centralized decision-making is rep laced by those of the constituent entities that aim at minimizing a Lagrang ian, i.e,, a local, nonnegative cost criterion, subject to the constraints imposed by the global goal. Thus, computations are carried out locally, uti lizing locally obtained data and appropriate information that is propagated from other sites. It is hypothesized that with each entity engaged in opti mizing its individual behavior, asynchronously, concurrently, and independe nt of other entities, the distributed system will approach "global" optimal behavior While it does not claim that such algorithms may be synthesized f or all centralized real-world systems, this paper implements both the centr alized and distributed paradigms for a representative military battlefield command, control, and communication (C-3) problem. It also simulates them o n a testbed of a network of workstations for a comparative performance eval uation of the centralized and decentralized paradigms in the MFAD framework . While the performance results indicate that the decentralized approach co nsistently outperforms the centralized scheme, this paper aims at developin g a quantitative evaluation of the quality of decisions under the decentral ized paradigm. To achieve this goal, it introduces a fundamental concept, e mbodied through a hypothetical entity termed "Perfect Global Optimization D evice (PGOD)," that generates perfect or ideal decisions. PGOD possesses pe rfect knowledge, i.e., the exact state information of every entity of the e ntire system, at all times, unaffected by delay. PGOD utilizes the same dec ision-making algorithm as the centralized paradigm and generates perfect gl obally-optimal decisions which, though unattainable, provide a fundamental and absolute basis for comparing the quality of decisions. Simulation resul ts reveal that the quality of decisions in the decentralized paradigm are s uperior to those of the centralized approach and that they approach PGOD's decisions.