The role concept provides a useful tool to design and understand complex multi-agent systems, which allows agents with a similar role to share similar behaviors. However, existing role-based methods use prior domain knowledge and predefine role structures and behaviors. In contrast, multi-agent reinforcement learning (MARL) provides flexibility and adaptability, but less efficiency in complex tasks. In this paper, we synergize these two paradigms and propose a role-oriented MARL framework (ROMA). In this framework, roles are emergent, and agents with similar roles tend to share their learning and to be specialized on certain sub-tasks. To this end, we construct a stochastic role embedding space by introducing two novel regularizers and conditioning individual policies on roles. Experiments show that our method can learn specialized, dynamic, and identifiable roles, which help our method push forward the state of the art on the StarCraft II micromanagement benchmark. Demonstrative videos are available at https://sites.google.com/view/romarl/.

As artificial intelligence (AI) systems become increasingly ubiquitous, the topic of AI governance for ethical decision-making by AI has captured public imagination. Within the AI research community, this topic remains less familiar to many researchers. In this paper, we complement existing surveys, which largely focused on the psychological, social and legal discussions of the topic, with an analysis of recent advances in technical solutions for AI governance. By reviewing publications in leading AI conferences including AAAI, AAMAS, ECAI and IJCAI, we propose a taxonomy which divides the field into four areas: 1) exploring ethical dilemmas; 2) individual ethical decision frameworks; 3) collective ethical decision frameworks; and 4) ethics in human-AI interactions. We highlight the intuitions and key techniques used in each approach, and discuss promising future research directions towards successful integration of ethical AI systems into human societies.

In today's world, intelligent embedded devices and sensors are interconnected into a dynamic and global network infrastructure is referred to as the Internet of Things (IoT). It has been widely recognized that the performance of an IoT is highly affected by how it is organized. A large-scale system may have billions of possible ways of being organized, which makes it impractical to find a high quality choice of organization by manual means. In this paper, we propose a genetic algorithm (GA) aided framework for generating hierarchical IoT organizational structures. We propose a novel unique mapping between organizational structures and genome representations. Since hierarchical (i.e., tree-structured) organizations are one of the most common forms of organizations, we propose a novel method to map the phenotypic hierarchical structure space into a genome-like array representation space. This new representation opens up opportunities for evolutionary computing techniques to help IoT applications automatically generate organizational structures according to desired objective functions. Based on this mapping, we introduce the hierarchical GA which enriches standard genetic programming approaches with the hierarchical crossover operator with a repair strategy and the mutation of small perturbation operator. The proposed approach is evaluated in an IoT-based information retrieval system. The results have shown that competitive baseline structures which lead to IoT organizations with good performance in terms of utility can be found by the proposed approach during the evolutionary search.

In this paper we propose a novel DCOP algorithm, called DJAO, that is able toefficiently find a solution with low communication overhead; this algorithm can be used for optimal and bounded approximate solutions by appropriately setting the error bounds. Our approach builds on distributed junction trees used in Action-GDL to represent independence relationsamong variables. We construct an AND/OR search space based on these junction trees.This new type of search space results in higher degrees for each OR node, consequently yielding a more efficient search graph in the distributed settings. DJAO uses a branch-and-bound search algorithm to distributedly find solutions within this search graph. We introduce heuristics to compute the upper and lower boundestimates that the search starts with, which is integral to our approach for reducing communication overhead. We empirically evaluate our approach in various settings.

Networks are seen everywhere in our modern life, including the Internet, the Grid, P2P file sharing, and sensor networks. Consequently, researchers in Artificial Intelligence (and Multi-Agent Systems in particular) have been actively seeking methods for optimizing the performance of these networks. A promising yet challenging optimization direction is multi-agent learning: allowing agents to adapt their behavior through interaction with one another. However, understanding the dynamics of an adaptive agent network is complicated due to the large number of system parameters, the concurrency by which the system parameters change, and the delay in the effect/consequence of parameter changes. All these factors make it hard to understand why an adaptive network of agents performed well at some time and poorly at another. In this paper we present a software tool that enables researchers in the multi-agent systems field to visualize and analyze the evolution of adaptive networks. The proposed software customizes and implements techniques from data mining and social network analysis research and augment these techniques in order to analyze local agent behaviors. We use our tool to analyze two domains. In both domains we are able to report and explain interesting observations using our tool.

It is crucial for embedded systems to adapt to the dynamics of open environments. This adaptation process becomes especially challenging in the context of multiagent systems. In this paper, we argue that multiagent meta-level control is an effective

We present a novel ensemble architecture for learning problem-solving techniques from a very small number of expert solutions and demonstrate its effectiveness in a complex real-world domain. The key feature of our “Generalized Integrated Learning Architecture” (GILA) is a set of heterogeneous independent learning and reasoning (ILR) components, coordinated by a central meta-reasoning executive (MRE). The ILRs are weakly coupled in the sense that all coordination during learning and performance happens through the MRE. Each ILR learns independently from a small number of expert demonstrations of a complex task. During performance, each ILR proposes partial solutions to subproblems posed by the MRE, which are then selected from and pieced together by the MRE to produce a complete solution. The heterogeneity of the learner-reasoners allows both learning and problem solving to be more effective because their abilities and biases are complementary and synergistic. We describe the application of this novel learning and problem solving architecture to the domain of airspace management, where multiple requests for the use of airspaces need to be deconflicted, reconciled, and managed automatically. Formal evaluations show that our system performs as well as or better than humans after learning from the same training data. Furthermore, GILA outperforms any individual ILR run in isolation, thus demonstrating the power of the ensemble architecture for learning and problem solving.

In many multi-agent applications such as distributed sensor nets, a network of agents act collaboratively under uncertainty and local interactions. Networked Distributed POMDP (ND-POMDP) provides a framework to model such cooperative multi-agent decision making. Existing work on ND-POMDPs has focused on offline techniques that require accurate models, which are usually costly to obtain in practice. This paper presents a model-free, scalable learning approach that synthesizes multi-agent reinforcement learning (MARL) and distributed constraint optimization (DCOP). By exploiting structured interaction in ND-POMDPs, our approach distributes the learning of the joint policy and employs DCOP techniques to coordinate distributed learning to ensure the global learning performance. Our approach can learn a globally optimal policy for ND-POMDPs with a property called groupwise observability. Experimental results show that, with communication during learning and execution, our approach significantly outperforms the nearly-optimal non-communication policies computed offline.

Embedded systems consisting of collaborating agents capable of interacting with their environment are becoming ubiquitous. It is crucial for these systems to be able to adapt to the dynamic and uncertain characteristics of an open environment. In this paper, we argue that multiagent meta-level control (MMLC) is an effective way to determine when this adaptation process should be done and how much effort should be invested in adaptation as opposed to continuing with the current action plan. We describe a reinforcement learning based approach to learn decentralized meta-control policies offline. We then propose to use the learned reward model as input to a global optimization algorithm to avoid conflicting meta-level decisions between coordinating agents. Our initial experiments in the context of NetRads, a multiagent tornado tracking application show that MMLC significantly improves performance in a 3-agent network.

Due to the non-stationary environment, learning in multi-agent systems is a challenging problem. This paper first introduces a new gradient-based learning algorithm, augmenting the basic gradient ascent approach with policy prediction. We prove that this augmentation results in a stronger notion of convergence than the basic gradient ascent, that is, strategies converge to a Nash equilibrium within a restricted class of iterated games. Motivated by this augmentation, we then propose a new practical multi-agent reinforcement learning (MARL) algorithm exploiting approximate policy prediction. Empirical results show that it converges faster and in a wider variety of situations than state-of-the-art MARL algorithms.

We consider a multiagent resource allocation problem where individual users intend to route traffic by requesting the help of entities across a network, and a cost is incurred at each network node that depends on the amount of traffic to be routed. We propose to study contract-based network resource allocation. In our model, users and nodes in the network make contracts before nodes route traffic for the users. The problem is an interesting self-interested negotiation problem because it requires the complete assembly of a set of distinct resources, and there are multiple combinations of distinct resources that could satisfy the goal of negotiation. First, we characterize the network allocation problem and show that finding optimal allocations is NP-complete and is inapproximable. We take both Nash equilibrium and pairwise Nash equilibrium as the solution concepts to characterize the equilibrium allocations. We find that, for any resource allocation game, Nash equilibrium and pairwise Nash equilibrium always exist. In addition, socially optimal allocations are always supported by Nash equilibrium and pairwise Nash equilibrium. We introduce best-response dynamics in which each agent takes a myopic best-response strategy and interacts with each other to dynamically form contracts. We analyze the convergence of the dynamics in some special cases. We also experimentally study the convergence rate of the dynamics and how efficient the evolved allocation is as compared with the optimal allocation in a variety of environments.

Choosing when to communicate is a fundamental problem in multi‐agent systems. This problem becomes particularly challenging when communication is constrained and each agent has different partial information about the overall situation. We take a decision‐theoretic approach to this problem that balances the benefits of communication against the costs. Although computing the exact value of communication is intractable, it can be estimated using a standard myopic assumption—that communication is only possible at the present time. We examine specific situations in which this assumption leads to poor performance and demonstrate an alternative approach that relaxes the assumption and improves performance. The results provide an effective method for value‐driven communication policies in multi‐agent systems.

Several multiagent reinforcement learning (MARL) algorithms have been proposed to optimize agents' decisions. Due to the complexity of the problem, the majority of the previously developed MARL algorithms assumed agents either had some knowledge of the underlying game (such as Nash equilibria) and/or observed other agents actions and the rewards they received. We introduce a new MARL algorithm called the Weighted Policy Learner (WPL), which allows agents to reach a Nash Equilibrium (NE) in benchmark 2-player-2-action games with minimum knowledge. Using WPL, the only feedback an agent needs is its own local reward (the agent does not observe other agents actions or rewards). Furthermore, WPL does not assume that agents know the underlying game or the corresponding Nash Equilibrium a priori. We experimentally show that our algorithm converges in benchmark two-player-two-action games. We also show that our algorithm converges in the challenging Shapley's game where previous MARL algorithms failed to converge without knowing the underlying game or the NE. Furthermore, we show that WPL outperforms the state-of-the-art algorithms in a more realistic setting of 100 agents interacting and learning concurrently. An important aspect of understanding the behavior of a MARL algorithm is analyzing the dynamics of the algorithm: how the policies of multiple learning agents evolve over time as agents interact with one another. Such an analysis not only verifies whether agents using a given MARL algorithm will eventually converge, but also reveals the behavior of the MARL algorithm prior to convergence. We analyze our algorithm in two-player-two-action games and show that symbolically proving WPL's convergence is difficult, because of the non-linear nature of WPL's dynamics, unlike previous MARL algorithms that had either linear or piece-wise-linear dynamics. Instead, we numerically solve WPL's dynamics differential equations and compare the solution to the dynamics of previous MARL algorithms.

This paper designed and developed negotiation agents with the distinguishing features of 1) conducting continuous time negotiation rather than discrete time negotiation, 2) learning the response times of trading parties using Bayesian learning and, 3) deciding when to make a proposal using a multi-objective genetic algorithm (MOGA) to evolve their best-response proposing time strategies for different negotiation environments and constraints. Results from a series of experiments suggest that 1) learning trading parties’ response times helps agents achieve more favorable trading results, and 2) on average, when compared with SSAs (Static Strategy Agents), BRSAs (Best-Response proposing time Strategy Agents) achieved higher average utilities, higher success rates in reaching deals, and smaller average negotiation time.

Distributed Constraint Satisfaction (DCSP) has long been considered an important problem in multi-agent systems research. This is because many real-world problems can be represented as constraint satisfaction and these problems often present themselves in a distributed form. In this article, we present a new complete, distributed algorithm called Asynchronous Partial Overlay (APO) for solving DCSPs that is based on a cooperative mediation process. The primary ideas behind this algorithm are that agents, when acting as a mediator, centralize small, relevant portions of the DCSP, that these centralized subproblems overlap, and that agents increase the size of their subproblems along critical paths within the DCSP as the problem solving unfolds. We present empirical evidence that shows that APO outperforms other known, complete DCSP techniques.

In this paper, we present a cooperative mediation-based protocol that solves a distributed resource allocation problem while conforming to soft real-time constraints in a dynamic environment. Two central principles are used in this protocol that allow it to operate in constantly changing conditions. First, we frame the allocation problem as an optimization problem, similar to a partial constraint satisfaction problem (PCSP), and use relaxation techniques to derive conflict (constraint violation) free solutions. Second, by using overlapping mediation sessions to conduct the search, we are able to prune large parts of the search space by using a form of arc-consistency. This allows the protocol to both quickly identify situations when the problem is over-constrained, and to determine the appropriate repair. From the global perspective, the protocol has a hill climbing behavior and because it was designed to work in dynamic environments, is approximate. We describe the domain which inspired the creation of this protocol, as well as discuss experimental results

This paper addresses the problem of negotiation in a complex organizational context. An integrative negotiation mechanism is introduced, which enables agents to dynamically select a negotiation attitude based on the degree of external directedness. Experimental work explores the question of whether it always improves the organization's social welfare to have an agent be completely externally directed when negotiating and making choices. Results show that there are situations in which it is better for the organization if agents are partially externally directed in their negotiations with other agents rather than completely externally directed. The paper discusses the driving factors behind this unexpected result

This paper discusses a solution to the problems posed by sensor resource allocation in an adaptive, distributed radar array. We have formulated a variant of the classic resource allocation problem, called the setting-based resource allocation problem, which reflects the challenges posed in domains in which sensors have multiple settings, each of which could be useful to multiple tasks. Further, we have implemented a solution to this problem that takes advantage of the locality of resources and tasks that is common to such domains. This solution involves translating tasks and possible resource configurations into bids that can be solved by a modified combinatorial auction, thus allowing us to make use of recent developments in the solution of such auctions. We have also developed an information-theoretic procedure for accomplishing this translation, which models the effect various sensor settings would have on the network's output.

185-196

Formal treatment of collaborative multi-agent systems has been lagging behind the rapid progress in sequential decision making by individual agents. Recent work in the area of decentralized Markov Decision Processes (MDPs) has contributed to closing this gap, but the computational complexity of these models remains a serious obstacle. To overcome this complexity barrier, we identify a specific class of decentralized MDPs in which the agents' transitions are independent. The class consists of independent collaborating agents that are tied together through a structured global reward function that depends on all of their histories of states and actions. We present a novel algorithm for solving this class of problems and examine its properties, both as an optimal algorithm and as an anytime algorithm. To our best knowledge, this is the first algorithm to optimally solve a non-trivial subclass of decentralized MDPs. It lays the foundation for further work in this area on both exact and approximate algorithms.

Graphical models have been widely applied to uncertain reasoning in knowledge‐based systems. For many of the problems tackled, a single graphical model is constructed before individual cases are presented and the model is used to reason about each new case. In this work, we consider a class of problems whose solution requires inference over a very large number of models that are impractical to construct a priori. We conduct a case study in the domain of vehicle monitoring and then generalize the approach taken. We show that the previously held negative belief on the applicability of graphical models to such problems is unjustified. We propose a set of techniques based on domain decomposition, model separation, model approximation, model compilation, and re‐analysis to meet the computational challenges imposed by the combinatorial explosion. Experimental results on vehicle monitoring demonstrated good performance at near‐real‐time.

We consider a common task in multiagent systems where agents need to estimate the state of an uncertain domain so that they can act accordingly. If each agent only has partial knowledge about the domain and local observations, how can the agents accomplish the task with a limited amount of communication? Multiply sectioned Bayesian networks (MSBNs) provide an effective and exact framework for such a task but also impose a set of constraints. Are there simpler frameworks with the same performance but with less constraints? We identify a small set of high level choices which logically imply the key representational choices leading to MSBNs. The result addresses the necessity of constraints of the framework. It facilitates comparisons with related frameworks and provides guidance to potential extensions of the framework.

Scientific research and practice in multiagent systems focuses on constructing computational frameworks, principles, and models for how both small and large societies of intelligent, semiautonomous agents can interact effectively to achieve their goals. This article provides a personal view of the key application areas for cooperative multiagent systems, the major intellectual problems in building such systems, the underlying principles governing their design, and the major directions and challenges for future developments in this field.

A reusable agent is a self-contained computational system that implements some specific expertise and that can be embedded into diverse applications requiring that expertise. Systems composed of heterogeneous reusable agents are potentially highly adaptable, maintainable, and affordable, assuming that integration issues such as information sharing, coordination, and conflict management can be effectively addressed. The authors investigate sharing metalevel search information to improve system performance, specifically with respect to how sharing affects the quality of solutions and the runtime efficiency of a reusable-agent system. They first give a formal description of shareable metainformation in systems where agents have private knowledge and databases and where agents are specifically intended to be reusable. They then present and analyze experimental results from a mechanical design system for steam condensers that demonstrate performance improvements related to information sharing and assimilation. Finally, they discuss the practical benefits and limitations of information sharing in application systems comprising heterogeneous reusable agents. Issues of pragmatic interest include determining what types of information can realistically be shared and determining when the costs of sharing outweigh the benefits.

The Integrated Processing and Understanding of Signals (IPUS) architecture is presented as a framework that exploits formal signal processing models to structure the bidirectional interaction between front-end signal processing and signal understanding processes. This architecture is appropriate for complex environments, which are characterized by variable signal-to-noise ratios, unpredictable source behaviors, and the simultaneous occurrence of objects whose signal signatures can distort each other. A key aspect of this architecture is that front-end signal processing is dynamically modifiable in response to scenario changes and to the need to reanalyze ambiguous or distorted data. The architecture tightly integrates the search for the appropriate front-end signal processing configuration with the search for plausible interpretations. In our opinion, this dual search, informed by formal signal processing theory, is a necessary component of perceptual systems that must interact with complex environments. To explain this architecture in detail, we discuss examples of its use in an implemented system for acoustic signal interpretation.

This paper investigates the effects of parallelism on blackboard system scheduling heuristics. A parallel blackboard system is described that allows multiple knowledge source instantiations (KSIs) to execute in parallel using a shared-memory blackboard approach. New classes of control knowledge are defined that order the agenda by using information about the relationships between the goals of the KSIs. This control knowledge is implemented and tested in the DVMT application on a Sequent multiprocessor using BB1-style control heuristics. The usefulness of the heuristics is examined by comparing the effectiveness of problem-solving with and without the heuristics (as a group and individually). Problem solving with the new control knowledge results in improved system performance.

Approximate processing is an approach to real-time AI problem solving in domains in which compromise is possible between the resources required to generate a solution and the quality of that solution. It is a satisficing approach in which the goal is to produce acceptable solutions within the available time and computational resource constraints. Previous work has shown how to integrate approximate processing knowledge sources within the blackboard architecture. However, in order to solve real-time problems with hard deadlines using a blackboard system, we need to have: (1) a predictable blackboard execution loop, (2) a representation of the set of current and future tasks and their estimated durations, and (3) a model of how to modify those tasks when their deadlines are projected to be missed, and how the modifications will affect the task durations and results. This paper describes four components for achieving this goal in an approximate processing blackboard system. A parameterized low-level control loop allows predictable knowledge source execution, multiple execution channels allow dynamic control over the computation involved in each task, a meta-controller allows a representation of the set of current and future tasks and their estimated durations and results, and a real-time blackboard scheduler monitors and modifies tasks during execution so that deadlines are met. An example is given that illustrates how these components work together to construct a satisficing solution to a time-constrained problem in the Distributed Vehicle Monitoring Testbed (DVMT).

As part of research on sophisticated control for sensor interpretation, a planning-based control scheme for blackboard systems is developed. A planner's goal/plan/subgoal structure provides explicit context information that can be used to index and apply large amounts of context-specific control knowledge. The key obstacle to using planning for the control of problem solvers is the need to deal with uncertain and dynamically changing situations without incurring unacceptable overhead. These problems are addressed in several ways: the authors' planner is script-based, planning and execution are interleaved; plans can invoke information gathering actions; plan refinement is controlled by plan-specific focusing heuristics; and the system's focus of attention can be dynamically shifted by the refocusing mechanism. Refocusing makes it possible to postpone focusing decisions and maintain the opportunistic control capabilities of conventional blackboard systems. Planning with refocusing results in a view of the control process as both a search for problem solutions and a search for the best methods to determine these solutions.>

Design-to-time is an approach to problem solving in resource-constrained domains where multiple solution methods are available for tasks. Those solution methods make tradeoffs in solution quality within the available time. The design-to-time approach is defined in detail, and contrasted to the anytime algorithm approach. A heuristic algorithm for design-to-time real-time scheduling is presented. The authors' blackboard architecture that implements the design-to-time approach is discussed, and an example problem and solution from the Distributed Vehicle Monitoring Testbed (DVMT) is described in detail. Experimental results, generated using simulation, show the effects of various parameters on scheduler performance. Future research goals and plans are discussed.>

The authors extend their previous work (Nawab and Lesser, 1991; Weiss et al., 1991) on model variety analysis of a signal processing algorithm with respect to the class of all input signals that may potentially arise in a given signal understanding application. This analysis has two related objectives. The first objective is to partition the set of all possible signals in the application domain into two sets according to whether each signal is correctly or incorrectly processed by the signal processing algorithm under consideration. The second objective of model variety analysis is to characterize the nature of the distortions in the signal processing output for the cases where the input signal is incorrectly processed. The results of model variety analysis are useful for designing signal understanding systems for applications where it is necessary for the signal processing to be carried out in a situation-dependent manner. Model variety analysis and its usefulness for the design of signal understanding systems are illustrated through examples involving the use of short-time Fourier transform (STFT) processing for a sound understanding application.>

The distributed coordination problem can be described as "how should the local scheduling of activities at each agent be affected by non-local concerns and constraints?" Partial global planning (PGP) is a flexible approach to distributed coordination that allows agents to respond dynamically to their current situation. It is based on detecting relationships in the computational goal structures of the distributed agents. However, the detailed PGP mechanisms depend on the existence and availability of certain characteristics and structures that are idiosyncratic to the Distributed Vehicle Monitoring Testbed (DVMT). Generalized Partial Global Planning tries to extend the PGP approach by communicating more abstract and hierarchically organized information, detecting in a general way the coordination relationships that are needed by the partial global planning mechanisms, and separating the process of coordination from local scheduling. This new characterization of partial global planning has less communication overhead and can be more easily adapted and extended to new styles of problem solving and new multi-agent environments that have different characteristics from the original DVMT. This paper first describes the coordination problem as it was viewed by the PGP algorithm, and then extensions to that problem. It then briefly describes our model of task structures and coordination relationships. Finally, we show how the PGP algorithm, as an example, can be described using our method.

Research in Cooperative Distributed Problem Solving (CDPS) considers how problem-solving tasks should be allocated among a group of agents and how the agents should coordinate their actions to achieve effective problem solving. For some CDPS systems, negotiation plays an important role in how agents cooperate. We define negotiation as the process of information exchange by which the agents act to resolve inconsistent views and to reach agreement on how they should work together in order to cooperate effectively. We describe a generic model, the Recursive Negotiation Model (RNM), that can serve as a basis for classifying and specifying where conflict resolution among multiple experts, viewpoints, or types of reasoning is needed in building a sophisticated CDPS system. This model defines where and how negotiation can be applied during problem solving based on structuring problem solving into four stages: problem formulation, focus-of-attention, allocation of goals or tasks to agents, and achievement of goals or tasks. We further discuss how the degree of agent participation in control decisions, including decisions about assigning responsibility to agents, influences the nature of negotiation within a particular system. Through this model, we emphasize that negotiation may be a recursive, complex, and pervasive process that is used to resolve conflicts in both domain-level and control-level problem solving. Finally, we survey existing negotiation frameworks and how they relate to our generic model.

A cooperation paradigm and coordination protocol for a distributed planning system consisting of a network of semi-autonomous agents with limited internode communication and no centralized control is presented. A multistage negotiation paradigm for solving distributed constraint satisfaction problems in this kind of system has been developed. The strategies presented enable an agent in a distributed planning system to become aware of the extent to which its own local decisions may have adverse nonlocal impact in planning. An example problem is presented in the context of transmission path restoration for dedicated circuits in a communications network. Multistage negotiation provides an agent with sufficient information about the impact of local decisions on a nonlocal state so that the agent may make local decisions that are correct from a global perspective, without attempting to provide a complete global state to all agents. Through multistage negotiation, an agent is able to recognize when a set of global goals cannot be satisfied, and is able to solve a related problem by finding a way of satisfying a reduced set of goals.>

Partial global planning is used to provide a framework for coordinating multiple AI systems that are cooperating in a distributed sensor network. By combining a variety of coordination techniques into a single, unifying framework, partial global planning enables separate AI systems to reason about their roles and responsibilities as part of group problem solving, and to modify their planned processing and communication actions to act as a more coherent team. Partial global planning is uniquely suited for coordinating systems that are working in continuous, dynamic, and unpredictable domains because it interleaves coordination with action and allows systems to make effective decisions despite incomplete and possibly obsolete information about network activity. The authors implement and evaluate partial global planning in a simulated vehicle monitoring application and identifying promising extensions to the framework.>

The functionally accurate, cooperative (FA/C) paradigm provides a model for task decomposition and agent interaction in a distributed problemsolving system. In this model, agents need not have all the necessary information locally to solve their subproblems, and agents interact through the asynchronous, co-routine exchange of partial results. This model leads to the possibility that agents may behave in an uncoordinated manner. The author traces the development of a series of increasingly sophisticated cooperative control mechanisms for coordinating agents. They include integrating data- and goal-directed control, using static metalevel information specified by an organizational structure, and using dynamic metalevel information developed in partial global planning. The framework of distributed search motivates these developments. Major themes are the importance of sophisticated local control, the interplay between local control and cooperative control, and the use of satisficing cooperative control. Ongoing and new directions for research in FA/C systems are presented.>

The authors present an overview of cooperative distributed problem solving (CDPS), an emerging research area that combines aspects of AI (artificial intelligence) and distributed processing. CDPS can be used to study how a loosely coupled network of sophisticated problem-solving nodes can solve a complex problem which consists of a set of interdependent subproblems. Subproblems arise because of spatial, temporal, and functional distribution of data, knowledge, and processing capabilities. Application areas include distributed interpretation, distributed planning and control, cooperating expert systems, and computer-supported human cooperation. The authors survey the important approaches and empirical investigations that have been developed. The approaches covered include negotiation, functionally accurate cooperation, organizational structuring, multiagent planning, sophisticated local control, and theoretical frameworks.>

When two or more computing agents work on interacting tasks, their activities should be coordinated so that they cooperate coherently. Coherence is particularly problematic in domains where each agent has only a limited view of the overall task, where communication between agents is limited, and where there is no ``controller'' to coordinate the agents. Our approach to coherent cooperation in such domains is developed in the context of a distributed problem-solving network where agents cooperate to solve a single problem. The approach stresses the importance of sophisticated local control by which each problem-solving node integrates knowledge of the problem domain with (meta-level) knowledge about network coordination. This allows nodes to make rapid, intelligent local decisions based on changing problem characteristics with only a limited amount of intercommunication to coordinate these decisions. We describe three mechanisms that improve network coherence: 1) an organizational structure that provides a long-term framework for network coordination to guide each node's local control decisions; 2) a planner at each node that develops sequences of problem-solving activities based on the current situation; and 3) meta-level communication about the current state of local problem solving that enables nodes to dynamically refine the organization. We present a variety of problem-solving situations to show the benefits and limitations of these mechanisms, and we provide simulation results showing the mechanisms to be particularly cost effective in more complex problem-solving situations. We also discuss how these mechanisms might be of more general use in other distributed computing applications.

A new component of a problem-solving system, called the diagnosis module (DM), that enables the system to reason about its own behavior is described. The aim of the diagnosis is to identify inappropriate control parameter settings or faulty hardware components as the causes of observed misbehavior. The problem-solving system being diagnosed is a distributed interpretation system, the distributed vehicle monitoring testbed (DVMT), which is based on a blackboard problem-solving architecture. The diagnosis module uses a causal model of the expected behavior of the DVMT to guide the diagnosis. Causal-model-based diagnosis is not new in AI. What is different is the application of this technique to the diagnosis of problem-solving system behavior. Problem-solving systems are characterized by the availability of the intermediate problem-solving state, the large amounts of data to process, and in some cases, the lack of absolute standards for behavior. New diagnostic techniques that exploit the availability of the intermediate problem-solving state and address the combinatorial problem arising from the large amount of data to analyze are described. A technique has also been developed, called comparative reasoning, for dealing with cases where no absolute standard for correct behavior is available. In such cases the diagnosis system selects its own "correct behavior criteria" from objects within the problem-solving system which did achieve some desired situation. The diagnosis module for the DVMT has been implemented and successfully identifies faults.

Many signal-processing systems can be viewed as transforming their input signals into a representation of the real-world scenario from which the signals originated. Such systems usually have parameters whose settings are selected on the basis of the class of expected input scenarios. Finding the appropriate parameter settings for a class of input scenarios usually involves testing the system against typical and/or important input scenarios from that class. Whenever the system output does not match the input scenario, the parameter settings responsible for the fault are identified. The system user can then adjust the system parameters to ensure correct system behavior for such scenarios. The diagnostic process of identifying the parameters responsible for system faults is generally difficult because the signal-processing system carries out a complicated mathematical transformation involving a multistage algorithm that generates an enormous amount of intermediate data. A new approach to the diagnosis of such systems is developed. The approach is based on the availability of an abstract and possibly qualitative description of the input scenario and the use of an alternative system model derived from the underlying mathematical theory that explicitly represents the phenomena responsible for any incorrect processing. This approach to diagnosis models a system as a combination of processes that transform the user-specified abstract description of the input scenario into the system output. Whenever the correct answer is obtained at the system output, each process reduces to an identity transformation at the level of abstraction of the system output.

Signal processing systems usually have parameters whose settings are selected on the basis of the class of expected input signals. Finding the appropriate parameter settings for a class of inputs usually involves testing the system against typical and/or important inputs from that class. Whenever the system produces an incorrect output, the parameter settings responsible for the fault are identified. The system user can then adjust the system parameters in order to ensure correct system behavior. The diagnostic process of identifying the parameters responsible for system faults is generally difficult because the signal processing system carries out a complicated mathematical transformation involving a multi-stage algorithm that generates an enormous amount of intermediate data. We develop a new approach to the diagnosis of such systems. The approach is based on the availability of an abstract and possibly qualitative description of the input scenario and the use of an alternative system model derived from the underlying mathematical theory that explicitly represents the phenomena responsible for any incorrect processing.

A new approach for structuring distributed processing systems, called functionally accurate, cooperative (FA/C), is proposed. The approach differs from conventional ones in its emphasis on handling distribution-caused uncertainty and errors as an integral part of the network problem-solving process. In this approach nodes cooperatively problem-solve by exchanging partial tentative results (at various levels of abstraction) within the context of common goals. The approach is especially suited to applications in which the data necessary to achieve a solution cannot be partitioned in such a way that a node can complete a task without seeing the intermediate state of task processing at other nodes. Much of the inspiration for the FA/C approach comes from the mechanisms used in knowledge-based artificial intelligence (Al) systems for resolving uncertainty caused by noisy input data and the use of approximate knowledge. The appropriateness of the FA/C approach is explored in three application domains: distributed interpretation, distributed network traffic-light control, and distributed planning. Additionally, the relationship between the approach and the structure of management organizations is developed. Finally, a number of current research directions necessary to more fully develop the FA/C approach are outlined. These research directions include distributed search, the integration of implicit and explicit forms of control, and distributed planning and organizational self-design.

The range of application areas to which distributed processing has been applied effectively is limited. In order to extend this range, new models for organizing distributed systems must be developed.

The Hearsay II speech-understanding system (HSII) (Lesser et al [11], Fennell [9], and Erman and Lesser [6]) is an implementation of a knowledge-based multiprocessing artificial intelligence (AI) problem-solving organization. HSII is intended to represent a problem-solving organization which is applicable for implementation in a parallel hardware environment such as C.mmp (Bell et al [2]). The primary characteristics of this organization include: 1) multiple, diverse, independent and asynchronously executing knowledge sources (KS's), 2) cooperating (in terms of control) via a generalized form of the hypothesize-and-test paradigm involving the data-directed invocation of KS processes, and 3) communicating (in terms of data) via a shared blackboard-like data base in which the current data state is held in a homogeneous, multidimensional, directed-graph structure. The object of this paper is to explore several of the ramifications of such a problem-solving organization by examining the mechanisms and policies underlying HSII which are necessary for supporting its organization as a multiprocessing system. In addition, a multiprocessor simulation study is presented which details the effects of actually implementing such a parallel organization for use in a particular application area, that of speech understanding.

The Hearsay II speech understanding system under development at Carnegie-Mellon University is a complex, distributed-logic processing system: Processing in the system is affected by independent, data-directed knowledge sources processes which examine and alter values in a global data base representing hypothesized phones, phonemes, syllables, words, and phrases, as well as the hypothetical temporal and logical relationships among them. The question of how to schedule the numerous potential activities of the knowledge sources so as to understand the utterance in minimal time is called the "focus of attention problem". Near optimal focusing is especially important in a speech understanding system because of the very large solution space that potentially needs to be searched. Using the concepts of stimulus and response frames of scheduled knowledge source instantiations, competition among alternative responses, goals, and the desirability of a knowledge source instantiation, a general attentional control mechanism is developed. This general focusing mechanism facilitates the experimental evaluation of a variety of specific attentional control policies (such as best-first, bottom-up, and top-down search heuristics) and allows the modular addition of specialized heuristics for the speech understanding task.

This paper considers various factors affecting system em organization for speech understanding research. The structure of the Hearsay system based on a set of cooperating, independent processes using the hypothesize-and-test paradigm is presented. Design considerations for the effective use of multiprocessor and network achitectures in speech understanding systems ems are presented: control of processes, interprocess communication and data sharing, resource allocation, and debugging are discussed.1

The structure of microprogrammed processors is largely determined by the state of (semiconductor) technology and the requirements of the task of emulation. We discuss the impact of LSI components on microprogrammable processors and in particular, the effect of large memory arrays, LSI microprocessors (bit-slices), programmable logic arrays, and high-speed shifters.

This paper is an investigation of the organization of a parallel microcomputer designed to emulate a wide variety of sequential and parallel computers. This microcomputer allows tailoring of its control structure so that it is appropriate for the particular computer to be emulated. The control structure of this microcomputer is dynamically modified by changing the organization of its data structure for control. The microcomputer contains six primitive operators that dynamically manipulate and generate a tree-type data structure for control. This data structure for control is used as a syntactic framework within which particular implementations of control concepts, such as iteration, recursion, co-routines, parallelism, interrupts, etc., can be easily expressed. The major features of the control data structure and the primitive operators are: 1) once the fixed control and data linkages among microprocesses have been defined, they need not be rebuilt on subsequent executions of the control structure; 2) microprograms may be written so that they execute independently of the number of physical processors present and still take advantage of available processors; 3) control structures for I/O processes, data-accessing processes, and computational processes are expressed in a single uniform framework. An emulator programmed on this microcomputer works as an iterative two-step process similar to the process of dynamic compilation or run time macroexpansion. This data structure approach to emulation differs considerably from the conventional approach to emulation and provides a unifying approach to the emulation of a wide variety of sequential and parallel computers.