Predicting Agent’s Behavior: A Systematic Mapping Review

The term agent modeling could be defined as the ability of an agent to acquire, infer, store, and reason about the properties of other agents. These properties are: behaviors, goals and beliefs [1]. The resulting model should be able to predict with an acceptable degree of certainty the future actions of another agent [2].

The main purpose of modeling an agent is to try to infer via observation, what the observed agent does or will try to do. Since knowing the exact internal mechanism of another agent is generally impossible, observing its behavior is the best source of information for an agent trying to model another agent [3]. Observation can include: examining the history of interactions with the observed agent, examining their previous actions, analyzing their live behavior using an algorithm such as “online extreme machine learning”, and analyzing a previously established database containing behavioral data of the observed agent.

There are two types of inference: explicit and implicit. Explicitly, modeling occurs by observing the agent's actions and constructing a generative model of their behavior as a product of those observations. The description of the generation of the agent's behavior could involve the estimation of the probabilities of observing certain actions or the adjustment of the known parameters in an inferred model of variable complexity [1] for example, games with a high level of interaction, (poker, game of nines, etc.) [2, 4-6]. The observations can directly build a predictive model to infer the opponent's strategies.

On the other hand, implicit modeling does not produce explicit models of other agents, instead these models implicitly encode aspects of other agents (such as their behavior) in other structures or reasoning processes [7]. For example, scenarios where the reward function explains the behavior of agents [S10] and [S14].

In the literature there are approaches to address the problem of modeling agents, using different techniques and terms to refer to it. To unify terms, in this work “modeling” will be used with all the approaches that try to predict or infer the behavior of an agent, either implicitly or explicitly.

Agent modeling addresses the problem of reasoning about the opponent, which is of great importance in competitive situations, or reasoning about a fellow agent, which is critical for reasons of cooperation, communication, and maintenance of social connections [8].

Predicting the behavior of agents is useful in cooperative scenarios since in this way they can anticipate the actions of other agents and react accordingly. If agents can perform their tasks saving explicit communication, or anticipating certain actions, modeling agents will imply resource savings [9]. In competitive environments, predicting agent behavior is useful to create adaptive plans and overcome competing agents [10].

For example, in the scenario of a soccer team [S1] or a robot battle [11], agents model their opponents to plan and react according to their observations. In another scenario, where cars and energy are negotiated [12], the agents model their opponents to reach a satisfactory agreement. In the Predator/Prey game by Barrett and Stone [13], Denzinger and Hamdan [14], the agents model their partners to achieve a more efficient collaboration in hunting tasks.

Albretch and Stone [7] present a survey that includes agents modeling other agents. Seven methods for modeling and classifying agents using eight features are identified. They make a clear distinction between two often misunderstood concepts: policy recognition and reasoning-based types. The former assumes a specific structure model and learns the parameters of the model based on observation of the agent's actions. The second assumes that the agent possesses one of a set of known types and computes the relative probability of its behavior based on the observation.

Masvoula et al. [15] devote part of their research to the agent modeling problem, focusing their attention on negotiating agents. These agents infer certain estimates on factors that affect the behavior of their opponents, in order to decide the best course of action to follow. They classify learning methods into three categories: 1) Explorative, such as genetic algorithms or Q-learning, which belong to the category of search techniques. These algorithms "learn" to make predictions in an iterative process of trial and error, a process that is usually quite expensive. 2) Repetitive, which use statistical inference on problems based on cases that are kept in templates. The problems they analyze are compared against similar stored templates, trying to find the best match. 3) Predictive, which try directly to estimate any parameter that can explain the behavior of an opposing agent to anticipate their actions.

In these works [7, 15] decisions based on predictions are analyzed, but limited to negotiating agents that model their opponents in competitive environments, this leaves out interesting scenarios, such as those based on cooperation between agents.

According to Paulseanu and Buche [16] focus their efforts on a mental simulation to anticipate a problem before it occurs and thus prevent it. They try to simulate the cognitive mechanism that allows a human to infer certain predictions for decision making. They describe connections between a human mental simulation and a computer simulation and how this field can emerge in the form of useful applications. They analyze proposals from fields such as virtual reality and robotics, and how mental simulation capabilities could help these areas to solve problems based on prediction skills. These skills come from models that use machine learning techniques such as Reinforcement Learning. They divide the investigations according to their contribution into two main aspects: environment and behavior. The first is the problem of perceiving through noisy and fault-prone sensory input systems. The second is about the structural analysis of an agent to try to infer the laws that govern it.

Hooshyar et al. [17] present a review focused on modeling playful agents and what they call a behavioral model. This model overlaps the typical and better-known plan recognition problem. Plan recognition encompasses problems in which sequences of actions are interpreted in terms of the goals that agents are likely to try to achieve, while the behavioral model tries to infer predictions independently of possible goals. Under this presumption, they found that to address these problems, they prefer to use classification methods based on machine learning, and conclude that data mining techniques are necessary to achieve better predictions.

The works analyzed are limited to mental simulations and modeling of the opponent. The interest of this research is agent-based systems that model other agents to predict their behavior, with a broad vision that deals with smaller and more specific application areas to a minimum.

The objective of this review is to analyze the research efforts that have addressed the agent modeling problem described in the last thirteen years. As a result of this analysis, the area is categorized in four dimensions. This allows us to identify three large methods that make up the techniques that are being applied to the problem. Seventeen relevant investigations are found, which represent the main aspects of the modeling problem. Twelve features of the area are also identified, which will be discussed later. Additionally, an analysis of each of the sources consulted to carry out this systematic mapping is presented. Finally, five open problems in this area of study are identified, which could form the basis for future research.

Some items are used in these categories, which are defined as:

The articles that do not refer directly to the fields of agents and modeling have not been taken into account by other research, which can be considered incorrect for two reasons: first, modeling an agent can be -and in fact on many occasions this it is like this- the optimization of a problem. Second, it discourages the field of agent modeling from taking advantage of advances in related fields of science. For these reasons we have decided to include [S2, S8, S10, S12].

14% of the proposals are architecture. There is a difference between frameworks (43%) and tools (43%), although some tools are presented as frameworks even though they do not meet the established criteria to be categorized as such. As in the case of [S2], whose scope is restricted and would not allow extension to partially observable scenarios (according to POMPD - Partially observable Markov decision process). In [S4], they focus on the scalability of the proposal, but do not provide extensibility to it, and in [S9] some possible extensions to the model are presented, but carrying them out would mean making important modifications to the equations that support it, to the notorious detriment of its reusability.

The proportion of jobs dealing with agent and multi-agent systems is 54% and 46% respectively. It is widely accepted that the best way to evaluate such a study is through empirical evaluation. However, among the articles studied, only 29% carry out an empirical evaluation. While the majority 71% validate their findings using demonstrations.

Works that implicitly address the problem of agent modeling are included. For example, those who optimize a reward function implicitly model the behavior of the observed entity. 36% apply implicit inference, while 64% apply explicit inference. Finally, the proportion of the object of inference in the proposals studied is: 21% actions performed by the agent, 43% objectives pursued by the agent and 36% reward function that guides the behavior of the agent. Table 5 presents the details of this information.

3.2 Methods used for agent modeling (RQ2)

The solutions found in this study combine techniques synergistically. This allows you to take advantage of the strengths and weaknesses of different practices. The extracted methods are general. The following categorization is simple, but representative of the area according to the articles studied. There are three methods, presented below.

1. Machine learning. In this context, one of the most used algorithms is Inverse Reinforcement Learning. This type of optimization algorithm solves or approximates a reward function. Within the same field, classifiers are also used to predict the strategies of other agents, whether in cooperative or competitive environments.
2. Bayes. Methods based on Bayesian theories are very popular and have a strong mathematical foundation. Bayesian statistics include Bayesian networks, and in the field that concerns us, it is used to infer the behavior of an agent in all kinds of scenarios. Bayesian-based methods are used to determine the probability of future actions or states that an agent might go through.
3. Mathematical logic. Mathematical approaches include theories such as game theory and propositional logic. The first role of logic is in the representation of knowledge. In this domain, agents can use a formal language to represent their beliefs and states as knowledge. They collect this information from the environment in which they operate. Since knowledge is expressed in formal language, logical operations can be reversed and inferences can be drawn from this knowledge.

Table 6 presents the articles classified according to the three methods described, plus the year of publication and the reference number (Appendix A).

Table 6. Methods to solve agent modeling

The results in Table 6 show that 3 of 17 articles (17.6%) are categorized as Math logical, 6 (35.3%) are categorized as Machine Learning and 8 articles (47.1%) are categorized as Bayes. This data corresponds to years from 2008 to 2021.

3.3 Solutions found for agent modeling (RQ3)

Below is an analysis of each of the primary research sources considered:

S1. In the modeling phase, the authors transform each observation into an atomic sequence of behaviors. According to the relevance of the action, it is then stored in a node system (tree). Once the modeling phase is finished, the classification is carried out, comparing data sets using the chi square test. The comparison is made with the behavior patterns previously analyzed. This process is done off-line and it is assumed that there are data inputs available for training. Its application is limited since a database with candidate behavior patterns is needed to carry out supervised learning on them.

S2. This article tries to simplify an optimization problem. Simplification is about modifying it in such a way that your solution can meet Inverse Reinforcement Learning. The proof is done using PCFG (Probabilistic context free grammar). It is a syntax parser used to parse a text input into a data structure. This parsing problem is typically approached as an optimization problem by adjusting the weights of a function. However, in this work they reduce it to a Markov decision problem MDP (Markov decision problem) to solve it with an IRL reward function. Although it carries out an exhaustive analysis developing five types of Inverse Reinforcement Learning algorithms, it is not clear what types of problems, apart from PCFG, could be extrapolated from this solution. It also develops an interesting unified notation to represent algorithms that use Inverse Reinforcement Learning.

S3. It is based on a learning method that classifies and stores actions with their respective parameters (for example: action = move, parameter = left), uses decision trees to predict the actions of an agent, and regression trees to predict the parameters of an agent. Those actions it was tested in the RoboCup Soccer competition [22] with good results.

S4. It uses a mathematical model based on set theory to draw plans in the opposite direction, that is, to understand the actions of an agent, given certain observations. A practical demonstration of its mathematical propositions is carried out. An empirical evaluation is also carried out and results of three experiments are presented. Although they indicate that their proposal is easily scalable, it is not clear how the weights are assigned to the hypotheses that are proposed.

S5. It uses Bayesian probabilities to reverse an agent's plans and try to track their targets, based on observation of their actions in an MDP (Markov Decision Process) scenario. Its framework is based on TOM (Theory of Mind), which is an intuitive conception that the agent has of his own mental states and of others, and how these mental states lead to one or another behavior. It models the mental states (usually represented as: beliefs, desires and intentions) of itself and other agents. It tries to infer what it calls social goals, which means that the successful achievement of an agent's goal depends also on the successful achievement of other agents' goals. To carry it out, a kind of social reward is used between the agents. He conducts an experiment to show that he is able to make an inference after only a couple of observations. The reward function assumes that agents will always act selfishly, which restricts the solution to competitive scenarios.

S6. It presents an algorithm to perform plan recognition. Use Bayesian probabilities to infer the probability that an agent will execute a plan given certain observations. It also develops a declarative language mainly oriented to describe actions. The algorithm organizes the information in a tree structure, in which a deductive system is applied in a loop to make the inferences. The experiments are presented with an exhaustive empirical and demonstrative evaluation, and prove that the proposal is scalable.

S7. It is a practical implementation of the Appraisal Theory in agents acting in partially observable scenarios (POMPD). It models the beliefs of one agent in the mental model of another. The model allows anticipating the emotions of another agent, and therefore tries to infer their behavior, influenced by said emotions. The agents of this proposal have personality and motivations that guide them to achieve their goals. Agents keep a memory of their social relationships, they present a formula to calculate the utility of their actions, as well as their expectations, this helps the agent to make decisions. Its simplicity is remarkable and it is tested in three scenarios. Although the proposal deals with mental states and emotions, it does not provide a formal description of a model of emotions and how these emotions must necessarily affect your beliefs.

S8. It presents an original algorithm to perform Inverse Reinforcement Learning. The proposal is limited to LMPD problems (Linearly-Solvable Markov Decision Problems). It shows how to abstract a problem from an MDP (Markov Decision Process) to an LMDP. You only need the actions to infer the states and provide detailed modeling. It does not develop a practical example, and it cannot be extrapolated to problems that are usually solvable with other Inverse Reinforcement Learning algorithms.

S9. Develops a solution for plan recognition. It tries to infer the objectives of an agent in scenarios with partial (POMPD) and complete (MDP) observations. In this work, both the modeling agent (observer) and the modeled agent (observed) have partial observations of the actions of the opposing agent. The inference is done using Bayesian probabilities. For the solution to work, both agents (observer and observed) must have the same mental model, which is not always the case.

S10. It proposes to solve partially observable scenarios (POMPD) in two cases. First, when the agent's policies are explicit. Second, when the agent's policies are inferred from observations. We highlight the first case because it carries out a practical demonstration with three algorithms using some examples with interesting results. They deploy two algorithms, Q-function and Dynamic Programming (DP). Both algorithms use a reward function to optimize agent policies. Unfortunately, this also increases the number of observations exponentially with the number of agent policies. To deal with this problem they use the Witness algorithm. They report good results, although other researchers [23] suggest that the Witness algorithm is impractical even for problems of modest size.

S11. He focuses his attention on probabilistic programming and Bayesian statistics to model scenarios where agents must perform complex reasoning. Model uncertainty as a probabilistic distribution. It also establishes a second-degree inference as reasoning about the reasoning of other agents. In this model they describe knowledge according to the Theory of Mind (TOM), but they do not describe the inference process itself. It uses declarative programming to model its scenarios. In this way, these scenarios can be modeled in a few lines, in a relatively fast and clear way.

S12. It is proposed to reverse engineer TOM, it inverts planning models to make inferences about the beliefs and desires of the agent, as its behavior is observed. This is another way of expressing Recognition of plans. They essentially use Bayesian statistics in what they call the Bayes Theory of Mind to make inferences about the beliefs of other agents. They focus on the inference of beliefs, and not on intentions or plans as in most approaches. They develop formulas to represent the elements present in TOM as probabilities that affect each other, and the reasoning is developed in a Bayesian network. It is indicated that this solution would be able to be equated with basic human reasoning, however they test it in a fairly simple scenario.

S13. It is based on the Theory of Evaluation (a sub-product of TOM), which is an evaluation process carried out by the agent about himself, in relation to his environment. This evaluation process can be reversed in what is called Reverse Evaluation. Then the behavior of the agent can be inferred. It presents a tool tested in various scenarios and includes a mental model for the inference of emotions. It proposes a three-step method: first, it projects the effect that various actions could have with certain mental models. Choose the candidate states product of these actions. This information is stored in a tree structure and a reward function is used to choose the desired state from among the candidates. Second, it categorizes five emotions using the probability of the states represented in each branch of the tree structure. Third, you finally update your beliefs. This solution discretizes the emotions using only two states: high and low, which harms the realism of the proposal.

S14. The inverse equilibrium problem is addressed, but instead of optimizing the reward function with some machine learning technique, its authors use the principle of maximum entropy. Then, they use the probability distribution that provides the best prediction. To achieve this, they use game theory to reason about the behavior of the opposing agent. Compared with machine learning techniques such as classification and regression, the results of this method report that a smaller number of observations are needed to make predictions with an acceptable margin of error. It tries to infer reasoning as a second-degree intentional model (reasoning about the reasoning of others), but it does not formalize any mental model (such as Theory of Mind), so the characteristics of the observations it requires are unclear.

S15. It presents an adaptation of the well-known reinforcement learning algorithm, to choose a scenario where the utility is favorable to the modeling agent. To achieve this, the agent must model his opponent in a round of negotiations, taking into account that the opposing agent will adapt his strategy to achieve an agreement that favors him.

S16. It is a bilateral negotiation between two agents who must evaluate their mutual offers. To achieve a beneficial deal, the agent must model his opponent, mainly by trying to infer his reserve value, which is the minimum value at which an agent is willing to sell an asset.

S17. In this proposal, the agents are involved in a negotiation in the energy market. It is a competitive environment; however, the agents will try to shape their opponent to reach a Nash equilibrium. That is, both must try to model the other to balance utility with the benefit of reaching an agreement more quickly.

Next, we offer a summary of the use cases where agent modeling is applied. We include some articles, which despite not meeting our inclusion criteria, address interesting scenarios.

Use Case: Combat Agents.

Scenario: Robot Battle [11], Soccer [S1].

In Fayek and Farag [11] autonomous robots must model their opponents live, that is, online while the action is taking place, in order to react and counterattack. In [S1], the strategy of a soccer team is modeled based on a database of previous interactions, that is, it is carried out off-line.

Use Case: Deduction Problems.

Scenarios: The Blue Eye Problem [S11], Word Blocks [S4], Office Tasks [S9], Food Truck [S12], Employer/Employee [S13].

In [S11], they try to solve a puzzle by inferring the future reasoning of other agents. In [S4], they try to infer the word that the agent is trying to form. In [S9], they evaluate the daily tasks performed by an agent to infer their goals. In [S12], they try to predict which path an agent will take, based on their sensory inputs. In [S13], an employer agent models the reaction of an employee agent while having a conversation.

Use Case: Opponent Modeling.

Scenarios: Poker [2, 4], Prisoner's Dilemma [5], Game of Nines [6], Ultimatum Game [24], Soccer [S3], Shooting Squad [S7], Robot Tennis [25].

Bard and Bowling [2], and Southey et al. [4] model the opponent agent's strategy based on past interactions in a version of a poker game. Hernandez-Leal et al. [5], develop two autonomous agents in the well-known prisoner's dilemma game, the agents model each other to adapt their respective strategies. Stevens et al. [6] and Mascarenhas et al. [24], develop two negotiating agents who must decide how to distribute certain values, trying to infer their opponent's strategy. In [S3] they model the strategy of a soccer team based on live (on-line) observations. In [S7], an agent is forced to kill in a complex scenario. Then by modeling the mental states of the agents involved, they can reason about the actions that have taken place. According to Wang et al [25] a robotic arm models the behavior of an opponent agent to infer his next move in a tennis match.

Use case: Cooperative agents.

Scenarios: Soccer [26, 13], Predator/Prey Game [27, 14].

An autonomous agent engages in cooperative activities with unknown agents [13, 26]. The new agent tries to model the strategies of his companions in order to cooperate with them in achieving their goals. In the study of Barrett et al. [27], Denzinger and Hamdan [14], a set of agents called predators try to capture an agent called prey in the shortest possible time. The predatory agents do not know each other, so they must model their fellow hunters to coordinate their actions.

3.4 Open issues

The study and analysis carried out in this research has allowed the identification of five problems, which have not been satisfactorily addressed in the scientific literature found:

1. Type of learning. To model agents, algorithms must learn from data extracts to find patterns, or optimize some variables using: mathematics, statistics, machine learning techniques, or usually a combination of all of them. In any case, all modeling techniques require some type of learning technique. The analyzed articles put little or no effort into specifying what kind of learning they can handle. There are two types of learning: live learning (on-line learning) and batch learning (off line batch learning). According to Kotsiantis [28], in a batch configuration, an algorithm takes a collection of examples, and uses them to build a hypothesis, which can be used to make classification or regression predictions. In an online learning algorithm, the algorithm continually modifies its hypothesis as it receives new patterns and is constantly updated. Agent modeling is usually part of a larger system, architecture, or organism, and modeling techniques should prove effective in managing computational resources. For example, online learning can save storage resources, since it can learn instance by instance or in batches. Knowing the type of learning is also useful to determine the validity of the prediction model over time. The expiration of a model is studied in what is known as "drift concept", and it is that a model trained with off-line learning will possibly cease to be valid over time. On the other hand, online learning can ignore this problem since its model is updated with each instance it processes.
2. Lack of empirical evidence. Researched articles do not always follow accepted principles for testing findings within a scientific discipline. There is a consensus in the scientific community that one of the key precepts in research is that an experiment must have the characteristic of being able to replicate. This is important for validation and testing purposes. However, of this consensus, most of the articles found (Table 5), validate their proposals using demonstrations. It seems imperative to collect more empirical evidence to facilitate future implementations of the proposed solutions.
3. Drift problem. According to Kolter and Maloof [29], the concept "drift" is a learning task in which concepts change over time. This means that the rules or fundamentals of the object of study can change, thus changing its behavior, and invalidating a predictive model created on these bases. If this happens, any technique associated with the data set on which the model was created would be obsolete, since the rules that govern it have changed. Then the modeling techniques should take into account the expiration of their inferences, to facilitate their adaptation. None of the articles studied take into account the drift problem.
4. Biomimetics. Several proposals collected for this study indicate that their agents have some type of cognitive ability, that is, they are inspired by human reasoning. However, the articles found do not investigate mental theories. For example, they could benefit from the field known as artificial psychology [30], which deals with the study of human mental activities and their computational realization. Also, according to Wang et al. [31], all human activities are subject to emotional influences. Therefore, any mimicry attempt based on human cognitive abilities would benefit from the study of artificial emotions.
5. Conscious and unconscious agents. Whether or not the modeled agents are aware of being observed is a topic that has received little attention among researchers. According to De Bianchi [32], there is an unavoidable disturbance caused by the observer on the object of the observation. If the modeled agent is aware of being observed, he could change his behavior to cooperate or on the contrary to protect his privacy. It is also possible that no change is desirable, even if the agent is aware of being observed. This makes us reflect on the importance of encoding policies capable of simulating this behavior in an agent.

The author Gustavo Sandoval wishes to thank the National Secretariat of Higher Education, Science, Technology and Innovation (SENESCYT) of Ecuador for the scholarship that made this work possible.