In cooperative game theory, the two foremost problems are determining what coalitions will form and how a coalition's payoff should be divided. The Shapley value, a proven fair and unique payoff distribution, has become a central solution concept in the field. Computing the Shapley value is exponential in the number of agents, however, and has motivated many practical approximation methods, only two of which apply to arbitrary cooperative games. We propose a Shapley value approximation method using hierarchical clustering that partitions coalitions based on agent feature similarity and then interpolates the subcoalitions' Shapley values. Additionally, the approximation is guaranteed to satisfy the Shapley value's desirable fairness properties of symmetry, efficiency, and often null player. With a low runtime, experimental error, and a tuning parameter for error-runtime trade-off, this algorithm is the most practical for cooperative games requiring fast, near-optimally fair payoff distributions.

One of the biggest obstacles of Reinforcement Learning (RL) is its slow convergence rate in large state spaces or with sparse rewards. It has been shown that single-agent RL can be accelerated within a cooperative multi-agent scenario with information sharing, however the speedup depends on how well the agents' information can be used together. We demonstrate in this paper that state-space partitioning among agents can be realized by reward design without hard coded rules. The partitioning-associated reward directs agents to focus on different partitions and thus share information more efficiently. This approach has two advantages: (1) agents' actions are not diminished and remain relatively independent from one another; (2) it can be used to accelerate learning in both structured state domains (where partitions can be pre-determined) and arbitrarily-structured state domains (where partitions may be developed dynamically by agent teams as they explore the environment). Finally, we validate the method's efficacy by comparing it to previous related work in a simplified soccer domain.

SUMMARY: We have developed a web tool to predict Gene Ontology (GO) terms. The tool accepts an input DNA or protein sequence, and uses BLAST to identify homologous sequences in GO annotated databases. A graph is returned to the user via email. AVAILABILITY: The tool is freely available at: http://udgenome.ags.udel.edu/frm_go.html/

The explosive growth in genomic (and soon, expression and proteomic) data, exemplified by the Human Genome Project, is a fertile domain for the application of multi-agent information gathering technologies. Furthermore, hundreds of smaller-profile, yet still economically important organisms are being studied that require the efficient and inexpensive automated analysis tools that multi-agent approaches can provide. In this paper, we discuss the use of DECAF, a multi-agent system toolkit based on RETSINA and TAEMS, to build reusable information gathering systems for bioinformatics. We will cover why bioinformatics is a classic application for information gathering, how DECAF supports it, and several extensions that support new analysis paths for genomic information.

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).

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.