This paper describes an architecture for ad hoc teamwork, i.e., to enable an agent to collaborate with other agents “on the lfy". State of the art frameworks for ad hoc teamwork often pursue a data-driven approach, using a large labeled dataset of prior observations to model the behavior of other agents and to determine the ad hoc agent's behavior. These models are computationally expensive to learn, lack transparency, and make it dificult to recognize and adapt to previously unseen changes. In a departure from existing work, we introduce an architecture for ad hoc teamwork that performs non-monotonic logical reasoning with prior commonsense domain knowledge and models that are learned and revised rapidly from limited examples to predict the behavior of other agents. In addition, the architecture enables the agent to provide relational descriptions as on-demand explanations of its decisions and beliefs in response to diferent types of questions. We evaluate the architecture's capabilities in two benchmark multiagent collaboration domains: Fort Attack and Half field Ofense, in comparison with data-driven and knowledge-driven baselines.
abling an agent to collaborate with previously unknown
teammates [
They may also have to operate under partial observability (Figure 1b) and restricted communication. These conditions are representative of practical applications such as disaster rescue and surveillance that require the agents to reason with prior knowledge and noisy observations.
The state of the art in AHT has moved from using
predetermined policies for selecting actions in specific
states to methods based on a key “data-driven" compo- (a) Limited version (b) Full version
nent [
However, in practical domains, it is dificult to gather large training datasets of diferent situations. Also, these methods lack transparency, and make it dificult to adapt to unforeseen changes (e.g., in team composition) and to leverage commonsense domain knowledge. Unlike existing work, we follow a cognitive systems approach that formulates AHT as a joint reasoning and learning problem. Our knowledge-guided architecture for AHT (KAT) builds on the principles of refinement and ecological rationality such that the ad hoc agent:
iors to determine its actions; 2. Uses reasoning to guide the selection of relevant behavior models and the learning of new models under partial observability; and 3. Provides on-demand relational descriptions of its decisions and beliefs as explanations in response to diferent types of questions.
described in recent papers [
Example Domain 1. [Fort Attack (FA) Domain]
AHT has been researched under diferent names, as de- Three guards are defending a fort from three attackers
scribed in a recent survey [
Many recent studies include a data-driven component rotate clockwise or anticlockwise, do nothing, or shoot
that uses probabilistic, deep-network, and reinforcement an opponent in its shooting range. The environment has
learning (RL)-based methods to learn action choice poli- four kinds of built-in policies for guards and attackers (see
cies for diferent types of teammates from a lengthy Section 4.1). The original FA domain is fully observable,
history or prior observations of similar agents or situa- i.e., each agent can observe the state of other agents at
tions [
Various studies have investigated communication un- the 2013 Robocup 2D simulation league competitions;
der diferent AHT settings. This includes a multi-armed ofense agents are from: helios, gliders, cyrus, axiom, aut
bandits formulation to broadcast messages to teammates and defense agents are from agent2D. The strategies of
while incurring a cost [
Methods based on a data-driven learning component are two state space abstractions in HFO: low and high; require considerable computation, memory, and train- we use the high-level features. There are three action ing examples, build opaque models, and make it dificult abstractions: primitive, mid-level, and high-level; we use to adapt to unexpected changes. Our architecture ad- a combination of mid-level and high-level actions.
Prior commonsense knowledge in above domains in- the ofense team members, and whether the ad hoc agent
cludes relational descriptions of some domain attributes is too far from the goal. Actions of the domain include:
(e.g., location information), agent attributes (e.g.,
shooting range), default statements, and axioms governing (_ℎ_, _, _)
change, e.g., an agent can only move to a location nearby, (_ℎ_, _, _)
only shoot others within its shooting range (FA), and only (_ℎ_, _)
score a goal from a certain angle (HFO). This knowledge
may need to be revised over time.
which encodes the ad hoc agent’s ability to move to a
location, dribble the ball, and pass the ball to a
team3.1. Representation and Reasoning mate. The domain dynamics are described in using
three types of axioms: causal law, state constraint and
Any domain’s transition diagram in KAT is described us- executablility condition. Examples in HFO include:
ing an extension of the action language ℒ [
automatically translated to a program Π( , ℋ) in
CR(_ℎ_, _, _) Prolog [
Once the program Π is constructed, all reasoning tasks (e.g., planning, diagnostics, and inference) are reduced to computing answer sets of Π . The ad hoc agent can prioritize diferent goals at diferent times, e.g., score a goal when it has control of the ball, or position itself eficiently to receive the ball. It automatically selects the goal based on current state and considers the cost of diferent actions to compute a plan that minimizes the cost for achieving the goal.
We use the SPARC system [
Previous Yes actions <= 1
No
Action = 1 Dist. from guard3 to fort <= 0.0004
Yes No
Action = 1 Y pos. of attacker2 <= -0.8
Yes No
Action = 1 Dist. from guard1 to fort <= 0.0002 (a) FF tree in the ensemble for a guard in the FA domain. State of the art AHT methods try to optimize performance by training models ofline with large amounts of (e.g., few hundred-thousand or million) training data from diferent situations. However, it is not feasible to collect such labeled data for various situations in complex domains. KAT focuses on choosing relevant attributes and learning models of the behavior of other agents from limited training data (e.g., 5-10K) while supporting rapid, incremental updates and accurate predictions.
To learn the predictive models, we use the
Ecological Rationality (ER) approach, which is based on Herb
Simon’s definition of Bounded Rationality [
Individual FF trees learned for an attacker and a guard in the FA domain are shown in Figures 4b- 4a.
Unlike state of the art AHT methods, predictive models in KAT can be learned and revised rapidly. Specifically, KAT enables the ad hoc agent to automatically revise existing models, switch between existing models, or learn new models. The ad hoc agent uses Algorithm 1 to select the appropriate models for the other agents by periodically comparing the existing models’ predictions with the observed action choices of each agent over a sliding window of steps; in Algorithm 1, we limit this window to size of 1 (Lines 4-5). It then uses a graded strategy to penalize the error in orientation less than the error in location (Lines 6-7), selecting the models whose predictions best matches the observations for subsequent use (Line 10). If none of the models provide a good match over multiple steps, the learning of a new model is triggered.
rithm 2. The initial setup takes as input the ad hoc agent’s prior knowledge and the current set of learned behavior models of agent types (ℳ), and the policies that govInput: : other agents; ℳ: subset of behavior models; {}, {}: actual and predicted actions of each agent in current step of game; : initial values (100) for each agent-model combination.
Output: model: selected model for each agent. 1 for = 0 to do 2 for = 0 to ℳ do 3 if [, ] ̸= [] then 4 , ← actual_pose() 5 , ← predicted_pose() 6 ← ( − ) +
( − )/10 7 [, ] =
[, ] − end end model[i] = select_model(ℳ, scores[i, *]) 8 9 10 11 end Input: N: number of games; Π( , ℋ): core ASP program, ℳ: behavior models of other agents; : other agents’ policies; : other agents
Output: game_stats: statistics of games 1 Create environment, load , initialize
environment 2 for = 0 to − 1 do 3 s ← state of environment 4 while ¬ _(s) do 5 other_agents_action(s, ) 6 a ← ℎ, ← adhoc_agent_action(s, Π , ℳ) a = a ∪ ℎ s′ = execute(s, a) model_selection(,ℳ, a , ) if _(s′) then update(game_stats) initialize environment else end s = s′ ern the other agents’ action choices (Line 1, unknown to the ad hoc agent). In each episode of a game, other agents’ 16 end actions are based on (Line 5), and the ad hoc agent com- 17 end putes an action by reasoning with domain knowledge 18 return game_stats and ℳ (Line 6). These actions are executed in the simulated environment to compute the updated state (Line 8). Then the actual and predicted actions of the other agents are used by the model selection Algorithm 1 to incrementally revise ℳ (Line 9). Finally, the updated state is used for the next step (Lines 13-15). This process continues until the game ends; the related statistics are stored before moving to next game (Lines 10-12).
Algorithm 3 describes how the ad hoc agent determines its action choice in Line 6 of Algorithm 2. It uses ℳ to predict and simulate the efects of the next action (or few actions) of other agents in the current state (Lines 1-2). These efects are used to automatically identify the relevant domain regions (i.e., zones), axioms, level of abstraction, and goal(s) that need to be considered in the ASP program (Lines 3-4) whose answer set determines the ad hoc agent’s next action (Line 6) that is returned with the predicted actions of other agents to Algorithm 2.
Algorithm 3: adhoc_agent_action Input: s, Π( , ℋ), ℳ
Output: 1 ← action_predictions(ℳ) 2 s′ ← simulate_efects( ) 3 zones ← compute_relevance(s, s′) 4 ASP_program ← construct_program(s, Π , zones) 5 answer_set ← SPARC(ASP_program) 6 ← next_action(answer_set) 7 return , nicate using statements such as:
with restricted communication. To simulate such par- Statement 2a encodes that communication is to be only tial observability to the FA domain, we implemented used when a hidden attacker is within the shooting range a “forest" region where attackers can hide from guards of a teammate; Statement 2b defines when an attacker other than ad hoc agent and secretly approach the fort— is hidden; and Statement 2c describes the ad hoc agent’s Figure 1b. The ad hoc agent determines when to commu- belief that a teammate receiving information about a (, ,) causes ℎ(, ) (2c)
impossible (, , ) if _ () if _(, , ), _(, ) (, ), ℎ() (2a) (2b) hidden attacker will shoot it, although the teammate may ignore this information. Communication actions are thus triggered only if (a) one or more attackers are hidden; and (b) one or more teammates are closer to the hidden attacker(s) than the ad hoc agent.
HFO domain provides built-in functionality to enable partial observability by limiting each agent’s perception of objects (e.g., other agents, ball) to a specific viewing cone. We used this built-in ability, together with helper axioms, to simulate partial observability in the HFO domain without any communication actions. 3.5. Transparency prevented consideration of A. ∙ if no preconditions of A are identified, compute cost of adding A to the computed plan. This will identify reasons for not selecting A. 3. (Justify beliefs) Why did you believe L at step I? To justify a belief at a specific step, ad hoc agent will: ∙ find the axioms which has the given belief in its
head(state constraints).
∙ extract related literals and check whether they are
satisfied by the answer set. These will be the
supporting statements for the belief.
∙ if there are multiple supporting statements
explaining a target belief, select one to provide the
explanation. We leave the ranking of explanations and
multi-step tracing of beliefs to future work [
make an entire learned model interpretable, or to explain
(or justify) all the choices made by a reasoning system, The selected literals are processed with existing software
KAT focuses on quickly identifying the relevant infor- tools and templates to generate textual descriptions
promation to construct relational descriptions as explana- vided as responses (i.e., explanations). We provide an
tions in response to causal, contrastive, or counterfactual execution trace in Section 4.3. This approach can also
questions about its decisions and beliefs. An automated provide on-demand explanations of decisions and beliefs
decision-making system’s ability to reliably answer such during planning and execution.
questions about its decisions and beliefs promotes
acceptability; this ability has been shown to play an important
role in human reasoning and learning as well [
subsequent action from happening. ∙ any such literal that exists in answer set at step I
but not in I+1 triggered A. 2. (Contrastive questions) Why did you not do action
A at step I? When asked to justify why an action was not included in the plan, the ad hoc agent will: ∙ find axioms with A as head to obtain preconditions. ∙ extract corresponding literals and check if they are satisfied by the answer set; each such literals
observability. For H2, we considered partial observability in both domains, and explored limited communication in the FA domain; H3 was evaluated in the FA domain. As performance measures, we used the team of guards’ win percentage and shooting accuracy (i.e., fraction of times shooting eliminates an attacker) in the FA domain, and the fraction of the goals scored by ofense team in the HFO domain. In both domains, we also measured the accuracy of the predictive models. Further details of experiments and baselines are provided below.
hoc agent’s teammates and attackers: hand-crafted and built-in. Hand-crafted policies were simple strategies that mimic an agent’s basic expected behavior. We used two sets of hand-crafted policies: (Policy1) guards stay close to the fort and try to shoot attackers, while attackers spread and approach fort; (Policy2) guards and attackers spread and shoot opponents. Four built-in policies were provided with the FA domain: • Policy220: guards place themselves in front of the fort and shoot continuously; attackers try to approach the fort. • Policy650: guards try to block the fort; attackers try to sneak in from all sides. • Policy1240: guards spread and shoot the attackers; attackers sneak from all sides. • Policy1600: guards are willing to move from the fort; some attackers approach the fort and shoot to distract guards while others try to sneak in.
several hundred-thousand training examples. to learn the models used by the ad hoc agent to predict
We evaluated KAT in two sets of experiments; Exp1, behavior of other agents. in which other agents followed the hand-crafted policies; We used two sets of experiments to measure KAT’s and Exp2, in which other agents followed the built-in performance under full observability: (i) Exp4: limited policies. To simulate training from limited examples, we version with two ofense players (including ad hoc agent) collected state observations and action choices of other against two defense agents (including goalkeeper); and agents by running the hand-crafted policies, using only (ii) Exp5: full version with four ofense players (includ10000 examples to train the ensemble of FF trees for ing ad hoc agent) against five defense agents (including diferent agent types. The learned behavior prediction goalkeeper). In Exp6 and Exp7, we evaluated KAT’s models were used by the ad hoc agent to predict the performance under partial observability in the limited actions of other agents, including when the other agents and full versions (respectively). In each of these experiused the previously unseen built-in policies. ments our ad hoc agent replaced one of the ofense team
For experiments under full observability, each agent agents and all other ofense agents were based on one
other than our ad hoc agent was assigned a policy se- external team at a time. As baselines for Exp4-Exp5 we
lected randomly from the available policies (described used Base5, an ad hoc agent architecture that only uses
above). The baselines for this experiment were: (i) Base1 non-monotonic logical reasoning with prior knowledge
in Exp1 with other agents following a random mix of without any behavior prediction models, and recent state
hand-crafted policies; (ii) Base2 in Exp2 with other of the art AHT methods PPAS [
In the HFO domain, we used six external agent built-in policies. When the team of guards included our teams from 2013 RoboCup simulation competition; ad ad hoc agent, they won a higher fraction of the episodes hoc agent’s teammates were selected from helios, gliders, compared with Base2. These results demonstrated our cyrus, axiom and aut, and the opponents were based on ad hoc agent’s ability to adapt to unforeseen other agents agent2d team. We deployed these agent teams in the using the built-in policies, based on online revision of the HFO domain and collected state observations from only behavior models learned from the hand-crafted policies. 300 game episodes. Since the actions of the other agents These results support hypotheses H1 and H2. were not directly observable, we computed them from Table 3 shows the prediction accuracy of the (ensemthe observed state transitions. We used this limited data ble of FF trees) models learned from hand-crafted poliAgent Model Guard type 1 Guard type 2 Attacker type 1 Attacker type 2
Accuracy
domain are described in Table 7. In the limited version of Ad hoc agent Base2 GPL the game, the fraction of goals scored by the ofense team 34% 10% 30% was higher when the ad hoc agent used KAT than when the ad hoc agent used the logical reasoning baseline (i.e., Table 5 without any learned behavior prediction models), and Wins (%) for team of guards with hand-crafted policies ( Exp1). comparable with ofense team’s performance using state Communication addresses partial observability. of the art data-driven baselines that required orders of magnitude more training examples and did not support Policy (W%)ith Comm. (W%,itBhaosuet3) Comm. reasoning with prior domain knowledge. In the full version of the game, the team of ofense agents was able Policy1 73 58 to score a much higher fraction of goals when the team Policy2 19 8 included an hoc agent (using KAT) than when the agents used the baselines. This indicates that by leveraging the cies. The prediction accuracy ranges from 60 − 87%, interplay between representation, reasoning, and learni.e., these models were not perfect. However, when the ing, KAT was able to improve performance substantially, ad hoc agent reasons with prior knowledge and these strongly supporting hypotheses H1 and H2. models, the performance of the team of guards was com- The prediction accuracy of the learned behavior modparable or better than baselines without an ad hoc agent. els in the HFO domain for the limited and full versions These results demonstrate the benefits of reasoning and of the game are summarized in Tables 8 and 9 respeclearning guiding each other and further support H2. tively. Recall that the models were learned using data
Table 4 shows that our ad hoc agent’s shooting accu- from only 300 episodes for each external agent type, i.e., racy was higher than that of a Base2 guard agent and the orders of magnitude fewer examples than the several GPL agent, both of whom used policies based on orders hundred-thousand used by the data-driven baselines. The of magnitude larger number of training samples. prediction accuracy varied for diferent agent types but
Next, the results of Exp1 under partial observability these models could be learned and revised rapidly and
(in FA domain) are summarized in Table 5. We grouped resulted in good performance when the ad hoc agent also
the results according to the policy used. When the ad reasoned with prior knowledge.
hoc agent used the communication actions, the fraction Table 10 summarizes the results of evaluating KAT
of games won by the guards was substantially higher under partial observability in Exp6-Exp7 in the HFO
than when the ad hoc agent did not use communication domain. The goals scored by the ofense team with our ad
actions (Base3). Policy2 is a particularly challenging hoc agent is slightly lower than that of the external agent
scenario (e.g., guards and attackers shoot), which justifies teams. However this diference was not significant and
the lower number of games won by the guards. Table 6 mainly due to noise, e.g., in the perceived angle to the
summarizes the results from Exp2 where other agents goal. The ability to provide performance comparable with
used built-in policies. We observed that for policies 650, teams whose training datasets were orders of magnitude
1240 or 1600, the fraction of games won by the guards larger strongly supports H2.
was comparable or higher than that of Base4 that did not Additional results and videos, particularly those
inuse any communication actions. For policy 220, the ob- volving unexpected changes in the number and type of
served performance was slightly lower than the baseline. agents, are in our open-source repository [
− ℎ(_(, ), ).
Next, the ad hoc agent explored its answer set to check whether the grounded literal in_range(learner , attacker1 ) was present in step 2 and 3. Since it existed at step 2 but not in step 3, this literal was selected as an explanation for justifying the action execution. • Human: “Why did you not move to grid (3,14)
in time step 3? " • Ad hoc Agent: “Because it increases the cost of the plan; new plan cost = 6, old plan cost = 4." In this scenario, the ad hoc agent tried to create a plan with the suggested action. Such a plan to achieve the goal was found but the new plan’s cost was higher than the original plan. This information was included in the explanation to the contrastive question. • Human: “Why did you believe the attacker was
in shooting range at time step 4?" • Ad hoc Agent: “Because I observed attacker1 in (8,7) and I was in (5,14) facing south and the values satisfied the conditions 2 − 1 <= 8, 2 − 3 <= 1, 1 <= 2 + 3.".
When posed with a question about its beliefs, the ad hoc agent first identified the valid axioms (e.g., state constraints) that could influence the belief: ℎ(_(, ), ) ← ℎ(_(, 1, 1), ), ℎ( (, ℎ), ), 2 − 3 <= 1,
This paper described KAT, a knowledge-driven AHT architecture that supports non-monotonic logical reasoning with prior commonsense domain knowledge and predictive models of other agents’ behaviors that are learned and revised rapidly using heuristic methods. KAT automatically selects and uses the relevant behavior prediction models, and learns new ones when appropriate, enabling an ad hoc agent to adapt to previously unseen teammates and opponents on the fly. Moreover, KAT provides transparency by generating on-demand relational descriptions of its decisions and beliefs in response to diferent types of questions. In the future, we will explore scenarios with multiple ad hoc agents, investigate scalability of our architecture to more complex domains, and use our architecture on physical robots in AHT settings.