PaperlayerView exact revision on arXiv

Source-linked AI summary

Autonomous Agents Modelling Other Agents: A Comprehensive Survey and Open Problems

Stefano V. Albrecht, Peter Stone

arXiv:1709.08071v2cs.AIcs.MA

TL;DR

Autonomous agents need models of other agents to predict actions, goals, beliefs, and other properties for interaction. This article comprehensively surveys salient modelling methods and their assumptions, then identifies open problems. Its conclusion organizes the field around seven major methodologies while noting important scope boundaries and unresolved issues.

  • Problem

    Agents must reason about other agents’ behaviours, goals, and beliefs, but modelling methods vary widely in methodology and assumptions across research communities.

  • Method

    The article synthesizes seven major methodologies for modelling other agents and surveys their assumptions, relevant literature, and related methods.

  • Results

    The survey identifies policy reconstruction, type-based reasoning, classification, plan recognition, recursive reasoning, graphical models, and group modelling as major methodologies.

  • Takeaways & Limitations

    The survey frames modelling other agents as a broad field spanning predictions about individual agents, their beliefs and plans, detailed decision dependencies, and groups.

  • Takeaways & Limitations

    The survey assumes the modelling agent has some means to identify other agents’ actions and does not cover activity recognition itself.

Abstract

from arXiv · show

Much research in artificial intelligence is concerned with the development of autonomous agents that can interact effectively with other agents. An important aspect of such agents is the ability to reason about the behaviours of other agents, by constructing models which make predictions about various properties of interest (such as actions, goals, beliefs) of the modelled agents. A variety of modelling approaches now exist which vary widely in their methodology and underlying assumptions, catering to the needs of the different sub-communities within which they were developed and reflecting the different practical uses for which they are intended. The purpose of the present article is to provide a comprehensive survey of the salient modelling methods which can be found in the literature. The article concludes with a discussion of open problems which may form the basis for fruitful future research.

1. Introduction

Autonomous agents model other agents by using observed interaction histories to predict properties such as actions, behaviour classes, goals, and plans. This article surveys diverse modelling approaches and highlights the complexity and open problems associated with their differing assumptions.

  • Purpose and scope: Agent models map portions of observed interaction histories to predictions about another agent’s actions, behaviour class, goals, or plans.Observed histories may include the modelled agent’s past actions in various situations.
  • Purpose and scope: These models can inform planning and strategy selection, or support applications such as identifying weaknesses in a human player’s behaviour.Predicted actions can be incorporated into planning, while predicted behaviour classes can select precomputed strategies.
  • Purpose and scope: Modelling often involves learning from observations collected during the current interaction or from past interactions.Examples include learning parameters of a deterministic finite automaton or classifying another agent’s strategy.
  • Challenges: Complex modelling tasks have substantial computational challenges, including NP-complete automaton learning and exponential growth in plan hypotheses.These difficulties arise across different modelling techniques, including behaviour representation and goal or plan inference.
  • Survey motivation: The survey addresses methods developed under widely varying assumptions about agents and environments, reflecting different sub-community needs and constraints.Assumptions include deterministic versus stochastic choices, fixed versus changing behaviour, and full versus partial observability.
  • Survey motivation: The article surveys seven salient modelling methods and relevant additional methods, organizing their general ideas, literature, assumptions, applicability, limitations, and open problems.The survey includes policy reconstruction, type-based reasoning, classification, plan recognition, recursive reasoning, graphical models, group modelling, and other methods.

2. Related Surveys

Existing surveys often focus on particular domains or broader multiagent learning, leaving limited coverage of general modelling approaches and recent progress. This article instead surveys major methods across the literature while excluding activity recognition.

  • Existing survey coverage: Domain-specific surveys cover settings such as bilateral negotiation and commercial video games, where modelling serves domain-specific purposes.Negotiation surveys address issues exchanged between agents, while game surveys address playing strength and player experience.
  • This survey’s scope: The article provides a general cross-domain survey, including type-based reasoning, plan recognition, recursive reasoning, and graphical models that earlier surveys sparsely address.It aims to distil common methodological ideas across communities whose domain-specific surveys have little overlap in cited works.
  • Existing survey coverage: Multiagent-learning surveys include agent modelling but also cover coordination and communication learning, so their treatment of modelling is necessarily limited.Some are also dated and omit substantial recent progress in modelling methods.
  • This survey’s scope: Activity recognition is outside the survey’s scope because the authors assume the modelling agent has some means to identify other agents’ actions.Those means may include domain heuristics, supervised action classifiers, or probabilistic reasoning about observations.

3. Assumptions in Modelling Methods

Modelling methods depend on assumptions about the modelled agents and their environment, including observability, decision factors, action stochasticity, behavioural change, inter-agent dependence, and goals. These assumptions determine applicability, reliability, and model construction choices.

  • Assumption framework: The survey categorizes assumptions into those concerning modelled agents and those concerning the interaction environment.The framework is intended to clarify methods’ applicability, limitations, and open problems.
  • Agent assumptions: Deterministic action choices simplify modelling and planning, whereas stochastic models accommodate deliberate randomization and human mistakes.Deterministic choices support structures such as decision trees and deterministic state automata with efficient learning algorithms.
  • Agent assumptions: The modelled agent may have fixed or changing decision-making, with change understood as adapting based on past observations.The precise meaning of behavioural change depends on the predicted property and the literature.
  • Agent assumptions: Methods may require known decision factors or reconstruct them from history; without either, predictions can be very unreliable.Decision factors may be recent observations or abstract features derived from the interaction history.
  • Agent assumptions: Independent action choices allow separate models for each agent, while correlated choices may require modelling teams or joint plans.Independence does not imply that agents ignore one another’s past actions.
  • Agent assumptions: Methods also distinguish common from conflicting goals, with goal assumptions especially relevant to models that infer intentions.Action-prediction methods based primarily on observed actions may be less affected by agents’ goals.
  • Environment assumptions: Environmental assumptions include move order, action and state representation, and how fully agents observe the interaction.The survey emphasizes observability as one of the most important environmental dimensions.

4. Modelling Methods

The survey organises modelling methods by salient approaches and compares their assumptions, strengths, and limitations. It treats agent goals as assumptions about agents, including subjective goals such as intrinsic rewards.

  • Survey scope: The survey covers policy reconstruction, type-based reasoning, classification, plan recognition, recursive reasoning, graphical models, group modelling, and other methods.For each method, it provides assumption tables organised by identified dimensions.
  • Assumptions: The assumption framework includes agents’ goals, allowing subjective goals such as intrinsic rewards.Goals may alternatively be viewed as environmental assumptions because payoff or reward functions are often part of task specifications.
  • Comparison: Table 1 summarises potential strengths and limitations of surveyed modelling methods, but does not apply uniformly to all papers.Variations exist, and the table does not list every potential strength or limitation.

4.1. Policy Reconstruction

Policy reconstruction models predict an agent’s actions by fitting decision-making models to observed behaviour. The section covers frequency-based, case-based, information-inference, and utility-based approaches, alongside challenges in conditioning and generalisation.

  • Core approach: Policy reconstruction explicitly predicts actions by fitting a model’s internals to observed behaviour, enabling planners to anticipate responses.Models may begin as arbitrary or idealised decision models.
  • Frequency models: Fictitious play estimates action probabilities from observed frequencies, while conditional models must balance insufficient and excessive history information.Too little conditioning can reduce reliability; too much can slow learning.
  • Generalisation: A central limitation is that some approaches lack a mechanism for generalising observations to previously unseen situations.Abstraction and similarity-based methods provide ways to extrapolate between observations or cases.
  • Case-based reasoning: Case-based reasoning predicts actions for new situations by retrieving similar prior cases and aggregating their observed actions.Similarity functions relate cases, while recency can accommodate changing behaviour.
  • Complexity: Frequency and case-based methods are general but can require exponential space as the number of history attributes and possible values grows.Conditioning on n observations with m possible values yields up to m^n distributions or cases.
  • Inference and utility: Policy reconstruction can infer unobserved actions from environmental changes and can instead model unknown preferences through utility-function reconstruction.Utility reconstruction may learn search depth and feature weights from state-action examples.

4.2. Type-Based Reasoning

Type-based reasoning assumes the modelled agent belongs to one of several known types and updates beliefs about those types from observed actions. The survey connects these methods to equilibrium reasoning, machine learning, continuous parameters, and information-seeking actions.

  • Transfer: Reusing models learned from previous interactions can reduce the observations needed when learning a new model from scratch would be slow.The agent searches for a previously learned model resembling the current agent.
  • Definition: Each type is a complete behavioural model that maps observed interaction history to probabilities over the modelled agent’s available actions.Types may be manually specified, learned from prior interactions, or generated from historical data.
  • Equilibrium results: Under stated belief conditions, repeated type-based interaction can produce Nash equilibrium, whereas differing priors may instead yield a subjective equilibrium.Some conditions also prevent players from simultaneously holding correct beliefs and acting optimally relative to them.
  • Multiagent interaction: Type-based methods support interactions with initially unknown agents by combining beliefs about types with decision-making procedures.One formulation recursively combines Bayes-Nash equilibrium and Bellman optimality.
  • Machine learning: Neural-network alternatives learn mixtures of types from observed actions and use those mixtures to inform action selection.Examples use a type-mixture network paired with a decision network or a gating network over expert Q-values.
  • Type spaces: Type spaces may be discrete, continuous, or mixed, with continuous reasoning representing parameter settings as individual types.Examples include Gaussian beliefs over continuous parameters and joint reasoning over finite types and bounded parameters.
  • Information gathering: Type-based reasoning can deliberately select actions that trade off information about an agent’s type against task reward.Proposed approaches include myopic belief updates and model-predictive-control heuristics.

4.3. Classification

Classification methods assign labels to agents from observed interaction data, while related regression tasks can be discretised into classes. The survey describes design choices and applications spanning strategy games, player preferences, robot soccer, and trust.

  • Prediction targets: Classification methods model abstract properties rather than only predicting future actions, including play style and other quantities of interest.The survey distinguishes these predictions from policy reconstruction and type-based reasoning.
  • Core approach: Classification models assign class labels such as aggressive or defensive based on information from observed interaction.Their design centres on selecting and representing observations and choosing a classification procedure.
  • Strategy games: Game-playing applications train classifiers on replay or simulated data to predict strategies, build times, preferences, or defensive play.Examples use tagged expert replays, feature vectors, and support vector machines.
  • Classification and regression: Regression problems can be transformed into classification through finite discretisation, but jointly discretising multiple variables can cause exponential class-label growth.This trade-off motivates focusing the surveyed discussion on classification methods.
  • Robot soccer: Robot-soccer methods classify players or teams using symbolic feature construction alongside statistical learning.One approach selects features from temporal high-level action sequences and applies nearest-neighbour classification.
  • Trust and reputation: Trust modelling classifies agents’ trustworthiness using personal experience, communicated experiences, roles, and social relations.Trust is defined in one account as the expectation that an agent will fulfil contract terms in context.

4.4. Plan Recognition

Plan recognition infers an agent’s goals and plans from observed actions, using representations and inference procedures that trade expressive coverage against prediction precision and specification effort.

  • Plan recognition identifies possible goals and plans from an agent’s observed actions, including the intended end-product and action sequence.
  • Hierarchical plan libraries decompose top-level goals into sub-plans and primitive observable actions, with temporal orderings and environmental preconditions.
  • Compared with policy reconstruction and type-based reasoning, plan recognition predicts goals but often gives less precise next-action predictions because plans allow partial temporal order.
  • Most current plan-recognition methods are keyhole methods, assuming the modelled agent is unaware of the modelling agent.
  • Plan hypotheses can be distinguished by plausibility, probability, graph covering, Bayesian inference, or consistency with optimal plans in a domain model.

4.5. Recursive Reasoning

Recursive reasoning models nested beliefs about other agents, while research studies how much recursion supports robust interaction and how to represent uncertainty over agents’ models.

  • Nested beliefs can produce an apparently infinite recursion in which agents reason about beliefs concerning other agents’ beliefs.
  • Bayesian-game approaches resolve infinite belief regress by modelling private game elements probabilistically and assuming agents choose actions rationally with respect to their beliefs.
  • I-POMDPs represent recursive intentional models and solve them through finite recursion, while sub-intentional models map observation histories directly to action probabilities.
  • Dynamic epistemic logic provides a qualitative alternative in which knowledge or belief operators represent nested mental states and event operators update them.
  • Humans in one fitted recursive reasoning model reasoned on average to depth 1.5, corresponding to one or two levels of recursion.

4.6. Graphical Models

Graphical models make dependencies in multiagent systems explicit, supporting compact representations and agent models, but temporal unrolling can scale poorly over longer interactions.

  • Graphical models expose dependencies among state components, decisions, and utilities that abstract multiagent formulations leave implicit.
  • For short-horizon interactions, explicit dependency structure can yield compact models and more efficient algorithms through conditional independence.
  • Influence diagrams represent single-agent decision problems with chance, decision, and utility nodes connected by dependence relations.
  • IDs and MAIDs can model another agent’s decision making: parent relations encode which environmental variables the agent incorporates into decisions.
  • Temporal graphical representations add nodes for each interaction time step but do not scale efficiently with the number of time steps.
  • NIDs represent uncertainty over multiple agent models and nested beliefs, whereas I-DIDs support subjective decision making by modelling other agents through chance and model nodes.

4.7. Group Modelling

Group modelling predicts coordinated behaviour across agents when actions are correlated or team structure is informative, while also addressing collaboration with previously unknown teams.

  • Group models are useful when independent agent models cannot capture significant randomisation and correlation in agents’ action choices.
  • Combining agents into one model captures joint action probabilities but can make the action space grow exponentially with the number of agents and actions.
  • Partitioning agents into smaller groups offers a middle path when correlation is high within groups and low or absent between groups.
  • Team context can reveal goals and plans that isolated behaviours fail to identify, motivating models of team roles, subteams, and coordinated activity.
  • Research models opponent teams through strategy classification and movement patterns, and recognises team plans using hierarchical libraries and joint policies.
  • Ad hoc teamwork requires an agent to model its own previously unknown team and collaborate without prior coordination opportunities.

4.8. Other Relevant Methods

The survey covers implicit modelling, hypothesis testing, and safe or robust best-response methods alongside explicit agent modelling. These methods address model uncertainty and the tradeoff between optimizing against a model and limiting exploitability.

  • Implicit modelling encodes aspects of other agents in structures or reasoning processes rather than producing explicit agent models.Expert algorithms that learn the best policy from a set of policies are given as an example.
  • Bayesian type-based methods compare alternative models using relative posterior likelihoods, but cannot establish that the selected model is correct.Even when one model receives all probability mass, it may still be inaccurate.
  • Safe or robust best-response methods address the risk that policies optimized against inaccurate models may be exploitable.They compute policies that balance model-specific optimization against protection from exploitation.
  • Table 9 organizes assumptions in papers covering other relevant methods and records qualifications about undefined move order, undefined environment states, and behavior changes between episodes.The table concerns methods discussed alongside the survey’s main modelling methodologies.
  • The parameter δ ∈[0, 1] regulates the tradeoff between safety and exploitability, from strict model optimization to safer, potentially suboptimal policies.The safer extreme is exemplified by minimax-style behavior.

5. Open Problems

The survey identifies open problems arising from incomplete observations, interactive exploration, changing agents, temporal actions, open systems, computational demands, and uncertainty about model adequacy. It also highlights the need to combine modelling methods and efficiently discover relevant decision factors.

  • 5.1. Synergistic Combination of Modelling Methods: Combining modelling methods remains an open question, despite examples pairing type-based reasoning with policy reconstruction.Type-based reasoning can support fast initial adaptation, while policy reconstruction can generate new types during interaction.
  • Partial observability makes modelling more difficult because agents must account for incorrect or missing information about environments and other agents’ actions.Both symbolic and probabilistic approaches have been proposed for this setting.
  • Safe model exploration is challenging because exploratory actions can reveal information while unintentionally changing the modelled agent’s behavior.The survey identifies efficient exploration as an insufficiently addressed problem.
  • 5.4. Efficient Discovery of Decision Factors: Efficiently discovering relevant decision factors is unresolved because assuming them, including all factors, or exhaustively searching can become intractable in complex applications.The difficulty increases with long interaction histories and high-dimensional state descriptions.
  • Many methods assume fixed behavior, although learning agents and humans may change during interaction, making future behavior difficult to predict.The survey describes modelling changing behavior as notoriously difficult because future actions are essentially unconstrained.
  • Most surveyed methods assume instantaneous actions, leaving unresolved whether action durations require substantive methodological changes or suitable abstractions.The issue may instead belong partly to activity recognition, and realistic applications often involve actions with durations.
  • 5.8. Modelling in Open Multiagent Systems: Nearly all surveyed work assumes closed multiagent systems, while efficient modelling for open systems with agents entering and leaving remains an open challenge.Transfer learning is suggested as a potentially useful component for such methods.
  • Sophisticated modelling methods generally do not tell agents whether their chosen models are appropriate, allowing inadequate or misleading models to go undetected.The survey identifies model adequacy assessment as a distinct unresolved issue.

6. Conclusion

The conclusion synthesizes seven major methodologies for modelling other agents, alongside additional relevant methods, and identifies open problems for future research. The surveyed literature spans algorithmic design, experimental evaluation, and theoretical guarantees.

  • The survey identifies seven major methodologies: policy reconstruction, type-based reasoning, classification, plan recognition, recursive reasoning, graphical models, and group modelling.These methods cover predictions about decision making, model classes, goals and plans, beliefs, dependencies, and groups of agents.
  • Policy reconstruction infers decision making from observed actions, whereas type-based reasoning maintains beliefs over alternative decision-making models.The two approaches differ in whether they reconstruct behavior directly or select among candidate models.
  • The survey also covers implicit modelling, hypothesis testing for agent models, and safe best-response methods.These are presented as other relevant methods beyond the seven major methodologies.
  • The literature contains substantial work addressing algorithmic design, experimental evaluation, and theoretical guarantees in agent modelling.The conclusion characterizes the body of work as very large.
  • The survey identifies open problems as fertile grounds for future research.The conclusion presents these problems as a remaining part of the research landscape.

Appendix A. Clarification for Assumption Tables

The appendix clarifies the assumptions used to organize surveyed papers, separating assumptions about modelled agents from those about their environments. It also notes that some papers leave assumptions vague, requiring inference from their descriptions.

  • The tables organize assumptions in the order discussed in Section 3 and distinguish assumptions about modelled agents from environmental assumptions.The first five assumptions concern the agents being modelled, while the last three concern the interaction environment.
  • Agent-side assumptions include stochastic or deterministic choices, changing or non-changing behavior, known decision factors, independent or correlated choices, and common or conflicting goals.These dimensions characterize the modelled agent’s decision process and objectives.
  • Environment-side assumptions include action order, state and action representation, and observability of environment states and actions.The appendix distinguishes full from partial observability and discrete, continuous, or mixed representations.
  • States and actions may be distinguished using state/action notation for assumptions concerning observability.Additional clarification is supplied in table captions.
  • Many papers leave some assumptions vague, so the survey infers them from the descriptions available.The appendix cautions that explicit reporting of assumptions is inconsistent across the literature.
Loading 1709.08071v2…