Towards Flexible Multi-Agent Decision-Making Under Time Pressure

1 Introduction

It is desirable that an autonomous agent, operating under uncertainty in complex environments, be able to make optimal decisions about which actions to ex­ ecute. Rational decision-making under such circum­ stances using, for instance, the paradigm of expected utility maximization, is costly [Horvitz, 1988; Russell and Wefald, 1991; Russell and Subramanian, 1995; Zilberstein and Russell, 1996]. In our work, we con­ sider additional complexities presented by multi-agent environments. In these settings, an agent has to make decisions as to the rational course of action consider­ ing not only the possibly complex and not fully known state of its environment, but also considering the beliefs, goals, intentions and actions of the other agents. Clearly, these demands may lead to its failure to decide an action within the time constraint.

To cope with time constraints imposed by various decision-making situations in complex and uncertain multi-agent settings, we endow an agent with a tapestry of decision-making procedures, from strictly reactive to purely deliberative. The reactive procedures are con­ structed by compiling the deliberative decision-theoretic reasoning into condition-action rules. The compilation process exploits the regularities of the decision-theoretic reasoning and avoids costly deliberations in urgent sit­ uations. The rules are obtained from machine learn­ ing algorithms, which, as inputs, use the results of full­ blown decision-theoretic computations performed off­ line. Each of the compiled methods is assigned a per­ formance measure that compares it to the full-blown decision-theoretic benchmark. The various compilations available, and their combinations with more deliberative methods, constitute a spectrum of approaches to mak­ ing decisions under the constraints of available compu­ tational (and cognitive) resources, and under time pres­ sure.

Given the various decision-making methods at its dis­ posal, an agent should consider a number of factors to choose the appropriate decision-making mechanism for the situation at hand. The key factors include the qual­ ity of the decision provided by a method, the method's running time, and the urgency of the situation at hand. Intuitively, when a situation is not urgent, the agent can afford the luxury of full-blown decision-theoretic reason­ ing since it results in highest quality of the choice made. If the situation is very urgent, the agent should save as much time as possible by using a crude but fast reac­ tive tool. If the situation is somewhat urgent , the agent should use methods that are somewhat sophisticated al­ though not necessarily optimal.

Interestingly, the spectrum between the purely reac­ tive and fully deliberative decision-making tools can be spanned by combining these two varieties of methods. For example, the agent can use fast reactive rules as a pre-processing stage to narrow down the set of viable al­ ternatives. These alternatives can then be passed on to a deliberative decision-making method that uses all of the agent 's detailed knowledge to compute the expected utility of these few courses of action.

In this paper, we develop a suite of decision-making procedures for agents operating in multi-agent environ­ ments, and we measure their performance and running time. We use a particular multi-agent domain in which automated agents have to decide how to coordinate their attempts to intercept multiple incoming threats (as in anti-air defense) , but we believe that lessons learned in this domain generalize to other multi-agent domains.

2 Background and Related Work

Our prior work on deliberative decision-theoretic method includes the Recursive Modeling Method (RMM) [Gmy­ trasiewicz, 1996; Gmytrasiewicz et al., 1998; Noh and Gmytrasiewicz, 1997; 1998] . We have implemented a full-blown version ofRMM which allows an agent to com­ pute its best action given what is known about the other agents and about their states of knowledge and capabil­ ities. In the task of coordinating agents in a simulated

anti-air defense domain (such as in Figure 1) the perfor­ mance of RMM agents was comparable to or better than the human performance. Figure 2 presents these results in terms of the average total damage suffered by each of the coordinating defense teams. We show the per­ form;mce of three different teams: RMM-RMM, RMM­ Human, and Human-Human team. We experimented with all the teams in cases when communication was , and was not , available. When the communication was available, the performance achieved by three teams was improved, with the all-RMM team performing slightly better than the others. However, since the RMM deci­ sion procedure considers all of the combinations of the agents' alternative actions, it is not surprising that its complexity is, in the worst case, exponential in the num­ ber of agents present. As the complexity of the multi­ agent situation increases, as in Figure 3, the running time of RMM grows to over one hour (our current im­ plementation is in Lisp running on a P90 machine) . It is clear that the full-blown RMM needs to be supplemented by other, more reactive, methods for more complex and time-critical scenarios.

Our present work builds on a body of related research. Fox et a!. [Fox and Krause, 1991] provides a theoretical framework for symbolic reasoning as reac­ tive decision procedure. Other rigorous efforts to make decision-theoretic systems computationally tractable in­ clude work on the use of metareasoning procedures to control inference [Horvitz, 1988; Horvitz et al., 1989], and anytime algorithms [Dean and Boddy, 1988; Rus­ sell and Subramanian, 1995; Zilberstein and Russell , 1996]. In yet another approach Bratman [Bratman et al. , 1988] describes an agent 's architecture that includes both means-end reasoning and decision-theoretic reason­ ing. For a resource-bounded agent, the agent's beliefs, desires, and intentions (BDI) involve the formation, revi­ sion, and execution of plans to constrain the deliberation process. Rao et a!. [Rao and Georgeff, 1995] explore the applicability of reactive and deliberative behavior pro­ vided by the BDI architecture, and use it for air-traffic management system (OASIS) . Ephrati and collaborators [Ephrati et al., 1995] apply a filtering strategy to the multi-agent tileworld system. The filtering is accom­ plished using rules provided by the system designer, and it only guides the agent 's role allocation. Our condition­ action rules, on the other hand, represent learning over the results of agent's rational decisions in sample scenar­ ios obtained from a deliberative method. Our filtering strategy is to accumulate agents' knowledge and effec­ tively use it to limit deliberation in urgent situations.

In the following sections of this paper we propose a compilation process that explores the regularities of a deliberative decision making, and show how an au­ tonomous agent can use the compiled information, given performance metrics and time constraints. Then, we val­ idate our framework empirically, and discuss the experi­ mental results. In conclusion, we summarize our results and further research issues.

3 Formalism of Compilation and Filtering

To reduce the complexity and time needed for decision making in time constrained situation, we compile the re­ sults of deliberative decision-making into a set of reactive condition-action rules with numerous machine learning algorithms. An autonomous agent can use the compiled knowledge [Russell, 1989; Zilberstein, 1995] and either eliminate the deliberative decision-making all together, or constrain the number of alternative actions considered by excluding the ones that are likely to be suboptimal.

We propose an adaptive and deliberative agent (ADA) architecture, as consisting of compiled and deliberative decision procedures that allow the agent's bounded ra­ tionality to emerge from their combined usage. Let N be the set of agents, Ai, i EN, be the set of actions of agent i, and Si , i E N, be the set of world states that the i- th agent can discriminate among. For each action a~ E Ai we define condition(aL Si) to be the abstraction of the world state that includes only the parameters relevant for this action. For example, if the action is to pick up a block (shoot at a given threat), then the corresponding abstraction specifies the location and other parameters of the block (threat). Finally, let Li, i E N , be the set of compilation methods (learning algorithms) that the agent i employs.

Given a learning method l E Li, a compiled decision­ making procedure of an adaptive and deliberative agent implements a function Pi[lj= condition( a~, Si) H {Yes, No}, representing that the action a~ is (or is not) recommended in the state Si. Thus, various machine learning algorithms compile decision-theoretic models into different functions Pi[!]. As we mentioned, we gener­ ated the training examples for these learning algorithms from deliberative reasoning performed by RMM.

To allow for further flexibility in the ADA agents , we allow the procedures to be combined depending on circumstances at hand. Clearly, when the agents have enough time, they should try to make a deliberatively rational decision that maximizes their expected utility. In a time-critical situation, however, agent's decision­ making is bounded by the available computation time. For an adaptive and deliberative agent, therefore, we use the set of compiled rules to remove from consideration the likely unprofitable actions, and to reduce the deliber­ ation cost. This strategy is represented by the agent i's filtering criterion Ji[!j= siX Ai H A~, where A~ ~ Ai. In­ tuitively, the value of J is the set of plausible actions the agent should consider in situation Si. The filtering cri­ terion Ji[!J results from applying the rules in the function Pi[!] to the current state to obtain the plausible alternatives. For example, if Ji[!J ( si, { ai, a~, ai}) = {a~, ai} , then a~ and ai are plausible, and ai is not, in situation s}.

Given the set of plausible actions, our agent maximizes the expected utility among them:

We now apply the above formalism to agents making coordinated decisions in the anti-air defense domain.

4 Deliberation About Action in Anti-Air Defense Domain

Our specific domain, the anti-air domain, consists of a number of attacking targets, labelled A and B in Fig­ ure 4, and a number of defending units, labelled 1 and 2. 1 The mission of the defense units is to attempt to intercept attacking targets so as to minimize damages to the defended ground area. Let us note that this situa­ tion makes coordination necessary. The defense batteries do not want to miscoordinate and attempt to intercept the same threat, both due to the wasted ammunition and due to the increase in likelihood that the remain­ ing threat will reach its destination and cause damage proportional to its warhead size.

Given these factors, the expected benefit of shooting at a threat can be quantified as a product of the size of the threat and the interception probability. The inter­ ception probability 2 , P(Hij) , is dependent on the angle a;i between the target j's direction of motion and the battery i's line of sight, the distance d;i between the battery and the target, and the speed of target Sj (see, for example, [Macfadzean, 1992]) , as follows:

1 In the figure, the left top corner of the screen is (0,0) , x is pointing right, and y is pointing down.

where J.L is an interceptor-specific constant (assumed here to be 0.001) .

For example, in Figure 4, the combined benefit of Bat­ tery1 's shooting at the threat A and Battery2's shooting at the threat B amounts to 206.8( = 100 x 0.94 + 120 x 0.94). This value is entered in the payoff matrix, such as one on top in Figure 5. In this payoff matrix the rows represent Battery1 's alternative actions of shooting at A, B , and not shooting at all (S), respectively, and the columns represent the alternative actions of Battery2.

The actual behavior of Battery2, however, depends on a number of factors that Battery1 may be uncertain about. For example, if Battery2 has been hit and inca­ pacitated, it will not be able to launch any interceptors. If it is not incapacitated then its own decision-making situation can be represented as another payoff matrix. Further, Battery2 may have run out of long-range or short-range interceptors. If Battery2 has only long-range interceptors, it would be unable to attack target B , and can only attempt to shoot down target A. If Battery2 has only short-range interceptors, it can only attempt to shoot at target B. These four models , of Battery2 being fully operational and having long- and short-range inter­ ceptors, operational with only long-range interceptors, having only short-range interceptors, and incapacitated, are depicted as the second level models in Figure 5, with their associated probabilities, in this example case 0.3, 0.3, 0.3, and 0.1, respectively.

2 In the cooperative weapon-target allocation problem, air defense units calculate probability of kill to evaluate target survivability depending upon situation-specific characteris­ t ics. Here, the interception probability is a probability of kill, and is based on our heuristic factors.

The Recursive Modeling Method uses dynamic programming [Gmytrasiewicz, 1996; Noh and Gmy­ trasiewicz, 1997J to process model structures as in Fig­ ure 5 and determine the rational choice of coordinated action. In this case, Battery1 computes that if Battery2 is fully operational then the probability distribution over Battery2's actions A, B , and Sis [0.03, 0.97, O.OJ. If Bat­ tery2 has only long-range interceptors it will choose to shoot at target A, i.e., the probability distribution over Battery2's actions becomes [1, 0, OJ. If Battery2 has only short-range interceptors it will intercept target B. These probability distributions are combined with the model of Battery2 being incapacitated:

The resulting distribution is Battery1 's overall expec­ tation of Battery2's actions, given all of the remaining uncertainties. Propagating these results to Level 1, the combined probability distribution describing Battery2's actions is used to compute the expected utilities of Bat­ tery1 's alternative actions. We have:

Thus, given the uncertainties about Battery2, Battery1's rational coordinated choice is to intercept target A.

5 Compilation of Deliberative Decisions in Air-Defense

To construct compiled rules for our agents in the coor­ dinated defense domain, we used four machine learning algorithms: Bayes Classifier, C4.5 [Quinlan, 1993], CN2 [Clark and Niblett, 1989], and FOIL [Cameron-Jones and Quinlan, 1994J. 3 The input data for the learning algorithms were obtained from the Recursive Modeling Method (RMM), as described above. For the Bayesian classifier, the results are represented as rules specify­ ing the probability of occurrence of each attribute value given a class [Clark and Niblett, 1989], in our case "Yes" (also called Select Target below) and "No" (Don't Select Target below). C4.5 represents its output as a decision­ tree, and the output of CN2 is an ordered set of if-then rules. The trained results of FOIL are the relations of at­ tributes as function-free Horn clauses. We now describe the agent's compiled knowledge by using the above learn­ ing algorithms, and compare their decision capabilities in the anti-air defense environment.

3 We implemented the anti-air defense domain with Com­ mon LISP on top of the MICE simulator [Durfee and Mont­ gomery, 1989] on a LINUX machine, and also implemented a simple Bayesian classifier described in [Clark and Niblett, 1989] .

5.1 Learned Condition-Action Rules

In our experiments we considered agents that vary in their capacities, and they have limited knowledge about other agents. They decide on which behavior to execute based upon their sensory input and the limited informa­ tion they have about the other agents.

The attributes of situations that the agents can sense in an anti-air defense environment are summarized in Table 1. They include the size, speed and angle of the attacking targets, the agent's own intercepting capabili­ ties (i.e., its possessing both long- and short-range inter­ ceptors, only long-range interceptors, only short-range interceptors, and its being incapacitated and unable to shoot), and the probabilities associated with the capa­ bilities of the other defense agent 4 (the other agent's possessing both long- and short-range interceptors, only long-range interceptors, only short-range interceptors, and its being incapacitated and unable to shoot). Dur­ ing the experiments the values of the attributes were randomly generated within the ranges of values.

Based on the attributes in Table 1, the targets the defense agent considers for interception can be classified into two classes: {Select Target, Don't Select Target}. As an example, a decision tree obtained using C4.5 for these attributes is depicted in Figure 6.

4 Table 1 describes parameters for two agents and the gen­ eralization to a set of agents requires an additional set of probability parameters.

5.2 Experiments and Performance Results

To evaluate the quality of various rule sets generated by different learning algorithms the performance obtained was expressed in terms of the total expected damage to friendly forces after launching interceptors. The to­ tal expected damage is defined as a sum of the resid­ ual warhead sizes of the attacking targets. Thus, if a target was aimed for interception, then it contributed ( (1 - interception_probability) x warhead_size) to the total damage. If a target was not intercepted, it con­ tributed all of its warhead size value to the damage.

To find a meaningful size of the training set which could guarantee the soundness of the learning hypothe­ sis, we generated several sets of training examples. As the number of the examples increased, the resulting per­ formances improved drastically up to a certain point, after which performance did not improve. In anti-air de­ fense scenarios that included two batteries and two tar­ gets the sufficient number of training instances we found was 250 examples. By using the compiled condition­ action rules obtained by different learning methods, we tested the performances of the methods on a new set of 250 cases. The results of performance (damages) and runtime (sec.) are described in Table 2.

We analyzed the performance results in Table 2 us­ ing the standard analysis of variance (ANOVA) method. Since the computed value off= 8.94 in ANOVA exceeds 3.32(= f.o1,4 , 00 ), we know that the five teams were not all equally effective at the 0.01 level of significance, i.e. , the differences in their performance were not due to chance with probability of 0.99. As we expected, the pure delib­ erative procedure RMM showed the best performance. The Bayesian classifier computes the probabilities for two classes, and enables the defense agents to select the target which has the highest probability of being in the class of targets to be intercepted. The Bayesian classifier showed reasonable performance and runtime. When the pure reactive procedures, C4.5, CN2, and FOIL, were used, they could not uniquely decide the target in some cases, if the sensory input values of attributes were sim­ ilar. If the defense agents still were ambiguous in target interception after applying condition-action rules, they randomly selected the target. The agent's performance by using C4.5 was better than those of FOIL and CN2 while it took less runtime.

As expected, RMM required the longest runtime, and C4.5 needed the shortest runtime among the five deci­ sion procedures. ANOVA revealed that the differences in running time were not due to chance with probabil­ ity 0.99 again. When making a decision, the defense agents compared the current sensory input with one of the condition-action rules to classify a new example. The learning results obtained from CN2 and FOIL were rep­ resented by the sequential comparisons while C4.5 used the decision tree. Due to this difference CN2 and FOIL took longer to run than C4.5. The advantage of decision tree was in that it reduced the number of matches by disregarding nodes in the tree unrelated to the input.

To measure the efficiency of an adaptive and deliber­ ative agent architecture which uses the reactive rules to filter the alternatives considered by a deliberative pro­ cedure, we experimented with the scaled-up setting de­ picted in Figure 3. In this setting, there were six batter­ ies and 18 targets. The RMM agents we implemented for these experiments modeled only their closest neighbors for coordinated decision-making to reduce their delibera­ tion time. Since, as shown in Table 2, the Bayes classifier and C4.5 performed best among the reactive rule sets, we used these two as filtering criteria for ADA agents. As training data for the two learning algorithms, we gen­ erated 13800 tuples, which consist of 10200 for Don't Select Target class, and 3600 for Select Target class. The results of performance (damages) and runtime (sec.) in the scaled-up setting are described in Table 3.

Table 3 presents the average total expected damage af­ ter 200 trials. We focus on the performances of three dif­ ferent agents: RMM, Bayes-RMM (Bayesian rules used to filter alternatives for deliberations using RMM), and C4.5-RMM. The performance of the RMM agent was, again, the best. The performances of Bayes-RMM and C4.5-RMM agent were 94.3% and 92.1% of the RMM agent's performance, respectively. Further, the runtimes of adaptive and deliberative agents were drastically re­ duced. The size of the set of filtered plausible alterna­ tive actions were 7, and 9 out of 18 targets for Bayesian classifier and C4.5, respectively. The total runtime for Bayes-RMM agent was 9.23 on the average, and the C4.5-RMM agent needs 9.31 seconds for its target selec­ tion in the simulated anti-air defense environment. This result indicates that the combination of reactive and de­ liberative decision-making procedures saves the agent's deliberation time while offering good performance, com­ pared with pure deliberative procedure. Also, among the reactive procedures, the performance of Bayesian classi­ fier was better than that of C4.5 since it included the additional probabilistic information. Since the defense batteries controlled by C4.5 alone randomly selected the targets after filtering out unprofitable targets, its perfor­ mance was the worst.

6 Conclusions

We investigated a set of condition-action rule sets achieved by compiling decision-theoretic reasoning im­ plemented in RMM method using various learning al­ gorithms. We found that the compiled rules reduce the complexity and running time in complex multi-agent sce­ narios. This approach enables an adaptive and deliber­ ative agent to reach a decision within a reasonable time period.

We experimented with the anti-air defense domain to assess the quality of the flexible decision-making proce­ dure. Anti-air defense is certainly a real-time task, and any overhead or loss of timely response can result in ad­ ditional damages. The combination of reactive and de­ liberative decision-making methods avoided catastrophic failure, and provided good-quality decisions in the time­ constrained anti-air defense.

In our future research, we will consider how an au­ tonomous agent can decide on its coordinated action in an any-time fashion [Horvitz, 1988; Horvitz et al., 1989; Dean and Boddy, 1988]. Our framework will provide the rational action under uncertain deadline by calcu­ lating the computational gain, representing the tradeoff between the costs and the benefits of computation.

Acknowledgments

We are grateful to Dr. Lawrence B. Holder and the anonymous referees for providing useful comments relat­ ing to this work. This research has been sponsored by the Office of Naval Research Artificial Intelligence Program under contract N00014-95-1-0775 and by the National Science Foundation CAREER award IRI-9702132.