This page is under construction...

To perform optimal decision-making, autonomous agents need considerable computational resources. In multi-agent settings, when other agents are present in the environment, these demands are even more severe. We investigate ways in which the agent's knowledge and the results of optimal decision-making can be compiled to reduce the complexity of decision-making procedures and to save time in urgent situations. We use machine learning algorithms to compile the optimal decision-theoretic models into condition-action rules on how to coordinate in a multi-agent environment. Using different learning algorithms, we endow a resource-bounded agent with a tapestry of decision making tools, ranging from purely reactive to fully deliberative ones; the agent can select a method depending on the time constraints of the particular situation. We also propose combining the decision-making tools, so that, for example, more reactive methods serve as a pre-processing stage to the more accurate but slower deliberative decision-making ones. We validate our framework with experimental results in simulated coordinated defense. The experiments show that compiling optimal decision-making saves deliberation time while offering good performance in our multi-agent domain.

Each of the six defense units can launch three interceptors and are faced with an attack by 18 missiles named as A through R. In these example runs, the values of missile warhead sizes were randomly generated within the ranges of 100 to 300. Each case below is executed over 200 times, and the quality of the coordination achieved is measured as the combined expected tonnage of the missiles that penetrated the defense and damaged the protected territory (since each interceptor has an interception probability of less than one, the residual probability that the missile has not been destroyed is multiplied by its size and included in this measure).

Using fully deliberative tool: The six RMM agents, labeled "1" through "6", attempt to shoot down the 18 incoming missiles.

• Example Run: JAVA version (Please allow about 2 min. before the initial screen after loading demo.)
  
  The team of six RMM agents, when faced with a random arrangement of the attacking missiles, allows, on the average, the combined tonnage of 1141.5 (s=261.8) to penetrate the defense. The runtime of RMM agents to make their decisions was 88.69 seconds (s=1.3).

Combining decision-making tools: The six defense agents attempt to shoot down the 18 incoming missiles when Bayesian rules used to filter alternatives for deliberations using RMM.

• Example Run: JAVA version (Please allow about 2 min. before the initial screen after loading demo.)
  
  The performance of Bayes-RMM agent were 94.3% of the RMM agent's performance. That is, the total expected damage of Bayes-RMM team was 1210.9 (s=259.7). Further, the runtime of adaptive and deliberative agents was drastically reduced. We observed that the average number of recommended alternatives in the first salvo was 7 by Bayesian classifier out of 18 targets. The total runtime for Bayes-RMM agent was 9.23 seconds (s=1.04) on the average for its target selection in the simulated anti-air defense environment.

Using fully reactive tool: The six C4.5 agents attempt to shoot down the 18 incoming missiles.

• Example Run: JAVA version (Please allow about 2 min. before the initial screen after loading demo.)
  
  Since the defense batteries controlled by C4.5 alone randomly selected the targets after filtering out unprofitable targets, its performance was the worst. However, the C4.5 agent required the shortest runtime among the decision procedures. The C4.5 agent needed 0.87 seconds for its target selection.

This research has been sponsored by the Office of Naval Research Artificial Intelligence Program under contract N00014-95-1-0775. Here is the paper describing our approach in more detail:

• Sanguk Noh and Piotr J. Gmytrasiewicz, Towards Flexible Multi-Agent Decision-Making Under Time Pressure, To appear in Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence, July 1999.

For more information, please email us.

Return to Home