Kevin Nasman

Intelligent Multi-Agent Systems: Investigation into Distributed Implementation

Thesis Topic Summary

First Quarter Thesis Progress Report
PowerPoint Summary

 Purpose:

             To develop the framework for a system of multiple, autonomous, decision-theoretic agents working together to perform complex tasks.

 Details:

             The idea behind a multi-agent system is to leverage off design simplicity while still maintaining the ability to perform otherwise complex tasks. In other words, each agent in the system is not able to complete the task alone due to both its simplistic skill set and the demanding nature of the given task. Thus the agent must learn to work in a group of similar agents in order to act as one in performing the feat.

            There are both positive and negative aspects to this type of structure. One downside is that it requires more than one entity to perform a job, which in effect adds complexity to the system despite the simpler design of the agents themselves. One of the benefits for a distributed multi-agent system is that the computational demand for each agent is reduced. Another benefit is the implicit redundancy built into such a system, meaning that one agent can fail and the task will still be performed with little or no noticeable difference in efficiency (though it depends on the task and the number of agents that were assigned to it to begin with).

 System Components:

             There are a couple key components to a multi-agent system. The first is the knowledge representation mechanism used by each agent. This is done using an extended form of the Bayesian Network (BN) called an Influence Diagram (ID). The ID consists of a knowledge base and a set of one or more utility functions. The knowledge base is just a  BN which contains the agent’s beliefs about its status and the state of its surrounding environment. The leave nodes of the BN are the actions which the agent will perform based on what action it thinks will maximize its utility.

            The second component to this system is the agent’s capabilities in terms of its sensory inputs and actuator outputs. These have a great impact on the design of the ID used for each agent since the agent is inherently limited by what it can realistically perceive, reason, and do. This applies to agents of any kind, from physical (ex: robots trying to climb a set of stairs) to virtual (ex: software agents collecting relevant data from the internet).

Ideas and Challenges:

            There are several aspects of this system which are presently being considered.

1)      Agent self-querying

The idea would be to allow an agent to “complete its thought” by filling in the necessary information to make a solid decision. This requires the use of an arbitrary inference engine (for the agent BN) which can determine what else it needs to know in order to make a better choice for an action. 

2)      Sharing experience amongst agents

For more complex agents, there may be situations where each agent working together to perform a difficult task might experience slightly different events, and thus each agent will become mini-experts in the area it has learned the most. It would be optimal to share this experience among the agents at regular intervals so that an agent does not always have to learn by trial and error. This is exactly how humans learn.

3)      Multi-agent task allocation

If each agent has several tasks that it can perform towards the main task, each of which has its own combination of relative utility functions, how does it know what to do and when? There are a few ways to deal with this situation. The first would be to make the agent more complex such that it knows how to choose which sub-task it should be doing. This is OK but adds to the cost of the agent. Another way to deal with this would be to have a supervisory agent (or group of agents) which dish out the tasks based on what they see needs to be done. This would reduce the complexity of the individual agents which would allow them to spend most of their time doing the tasks.

4)      Using continuous valued functions with online clustering

Most real-world applications have need to less quantized values than can normally be tolerated by a BN. Thus going to a continuous valued function such as a mixture of Gaussians would allow smoother operation with minimal parameters. The data could be clustered online to allow adaptation of the Gaussians as needed. This would require quite a bit of work in the area of getting the BN to adjust its existing knowledge correlations when a new “quantization” is introduced (i.e. a new Gaussian is added based on a new cluster of data).