A mathematical framework for asynchronous, distributed, decision-making systems with semi-autonomous entities: Algorithm synthesis, simulation, and evaluation

For many military and civilian large-scale, real-world systems of interest, data are first acquired asynchronously, i.e. at irregular intervals of tim e, at geographically-dispersed sites, processed utilizing decision-making a lgorithms, and the processed data then disseminated to other appropriate si tes. The term real-world refers to systems under computer control that rela te to everyday life and are beneficial to the society in the large. The tra ditional approach to snell 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 sit es. Centralized decision making algorithms are slow and highly vulnerable t o natural and artificial catastrophes. Recent literature includes successfu l asynchronous, distributed, decision making algorithm designs wherein the local decision making at every site replaces the centralized decision makin g to achieve faster response, higher reliability, and greater accuracy of t he decisions. Two key issues include the lack of an approach to synthesize asynchronous, distributed, decision malting algorithms, for any given probl em, and the absence of a comparative analysis of the quality of their decis ions. This paper proposes MFAD, a Mathematical Framework for Asynchronous, Distributed Systems, that permits the description of centralized decision-m alting algorithms and facilities the synthesis of distributed decision-maki ng algorithms. MFAD is based on thc Kohn-Nerode distributed hybrid control paradigm. It has been a belief that since the centralized control gathers e very necessary data fi om all entities in the system and utilizes them to c ompute the decisions, the decisions mag be "globally" optimal. In truth, ho wever, as the frequency of the sensor data increases and the environment ge ts larger, dynamic, and more complex, the decisions are called into questio n. In the distributed decision-making system, the centralized decision-maki ng is replaced by those of the constituent entities that aim at minimizing a Lagrangian, i.e. a local, non-negative cost criterion, subject to the con straints imposed by the global goal. Thus, computations are carried out loc ally, utilizing locally obtained dataand appropriate information that is pr opagated from other Bites. It is hypothesized that with each entity engaged in optimizing its individual behavior, asynchronously, concurrently, and i ndependent of other entities, the distributed system will approach "global" optimal behavior. While it does not claim that such algorithms mag be synt hesized for all centralized real-world systems, this paper implements both the centralized and distributed paradigms for a representative military bat tlefield command, control, and communication (C-3) problem It also simulate s them on a testbed of a network of workstations for a comparative performa nce evaluation of the centralized and decentralized paradigms in the MFAD f ramework. While the performance results indicate that the decentralized app roach consistently outperforms the centralized scheme, this paper aims at d eveloping a quantitative evaluation of the quality of decisions under the d ecentralized paradigm. To achieve this goal, it introduces a fundamental co ncept, embodied through a hypothetical entity termed "Perfect Global Optimi zation Device (PGOD)," that generates perfect or ideal decisions. PGOD poss esses perfect knowledge, i.e. the exact state information of every entity o f the entire system, at all times: unaffected by delay. PGOD utilizes the same decision-making algorithm as the centralized paradig m and generates perfect globally-optimal decisions which, though unattainab le, provide a fundamental and absolute basis for comparing the quality of d ecisions. Simulation results reveal that the quality of decisions in the de centralized paradigm are superior to those of the centralized approach and that they approach PGODs decisions.