-One major challenge in developing multi-agent simulations is to find the appropriate agent design that is able generating the intended overall phenomenon respectively dynamics, but does not contain unnecessary details. In this paper we suggest to use agent learning for supporting the development of an agent model: The modeler defines the environmental model and the agent interfaces. Using rewards capturing the intended agent behavior, Reinforcement Learning techniques can be used for learning the rules that are optimally governing the agent behavior. However, for really being useful in a modeling and simulation context, a human modeler must be able to review and understand the outcome of the learning. We propose to use additional forms of learning as post-processing step for supporting the analysis of the learnt model. We test our ideas using a simple evacuation simulation scenario.
Methodological questions are more and more in the focus
of research on agent-based simulation as the number of
challenges in developing a good multi-agent simulation model are
numerous. The central issue hereby concerns what behaviors
the agents should exhibit so that the intended outcome is
generated. What particular detail must be included, what part
of the modeled behavior is not necessary? How to set the
parameters involved? However, if it is not fully clear from
the beginning how this local behavior should be - even if the
original agents behavior can be easily observed - the
development may result in a painful try and error procedure. The
modeler may add, respectively remove behavioral elements,
try different parameter values and test the overall outcome
again and again. Such a procedure might be feasible for an
experienced modeler who knows the critical starting points
for modifications and is capable of using complex calibration
tools for multi-agent simulation such as described in [
In this contribution we are suggesting to solve this search for
the appropriate agent-level behavior by using agent learning.
The vision is hereby the following procedure: the modeler
starts by developing an environmental model as a part of
the overall model, then, determines what the agent might be
able to perceive and to manipulate and finally describes the
intended outcome based on a reward function that evaluates the
agents performance. The agents then use a learning mechanism
for determining a behavior program that together generates the
intended overall outcome in the given environment. This
strategy might be also described as a variant of an
environmentdriven strategy for developing multiagent simulations [
A major issue in this overall procedure refers to the selection
of the particular learning agent architecture. An initial analysis
of different learning techniques applicable for this problem
has already been described in [
In the next section we will review existing approaches for learning agent architectures in simulation models. This is followed by a more detailed treatment of the learning-driven methodology and a presentation of the reinforcement learning architecture. In section IV and V we describe the used testbed, the experiments conducted with it and discuss the results. The papers ends with a conclusion and an outlook to future work.
Adaptive agents and multi-agent learning have been one
of the major focuses within distributed artificial intelligence
since its very beginning [
Reinforcement learning [
Although there is a wealth of publications dealing with
the performance of particular learning techniques, especially
reinforcement learning approaches, there are not many works
focussing on the resulting behavioral model dealing with
usability. An early example can be found in [
DESIGN
The basic idea behind a learning-driven design methodology
consists in the transfer of the agent behavior design and test
activity from the human modeler to the simulation system.
Specially in complex models, a high number of details can be
manipulated. This could make a manual modeling, debugging
and tuning process cumbersome, especially when knowledge
about the original system or experience for implicitly bridging
the micro-macro gap is missing. Using agents that learn at least
parts or initial versions of their behavior might be a good idea
for supporting the modeler in finding an appropriate low level
behavior model. Such a learning-based approach can also be
part of something as the adoption of a Living Design [
Not all agent learning architectures are equally apt for usage in the modeling support context. There are a number of properties that an appropriate learning technique may be able to exhibit for indicating a successful application. 1) Feasibility: The learning mechanism should be able to cope with the level of complexity that is required for a valid environmental models. Thus, it should not be necessary to simplify or even to reformulate the problem just for being able to apply the learning mechanism; That means the theoretical prerequisites for applying the learning technology must be known and fulfilled by the environmental model in combination with the reward function. The learning architecture must be able to find a good-enough solution; 2) Interpretability and Model Accessibility: The mechanism should produce behavior models that can be understood and interpreted by a human modeler. The architecture shall not be a black box with a behavior that the human modeler has to trust, but must be accessible for detailed analysis of the processes involved in the overall agent system; 3) Plausibility: The mechanism in the learning architecture should be well-established and well-understood. The motivation is that its usage shall not impose additional complexity to the modeler for example in setting a number of configuration parameter. How the learning architecture works, shall be explainable to and by the modeler.
There is a variety of possible learning agent architectures that might be suitable for the aim presented here and the requirements identified – as discussed in section II. We selected Q-Learning, as a Reinforcement Learning technique, as we describe it in the next paragraph.
1) Q-Learning: Q-Learning [
Q-Learning is able to compare the expected utility of the
available actions without requiring a model of the
environment. Nevertheless, the use of the Q-Learning algorithm is
constrained to a finite number of possible states and actions.
As a reinforcement learning algorithm, it also is based on
modeling the overall problem as Markov Decision Processes.
Thus, it needs sufficient information about the current state
of the agent for being able to assign discriminating reward.
Although there are a number of extensions that improve the
convergence speed of Q-Learning [
We suppose that Q-Learning meets the requirements for the application by providing both sufficient performance (if applicable) adaptability and also gives interpretability of the result. This interpretability is achieved by its rule-based structure (represented by the state action mapping) with a clear evaluation of those rules, by means of the Q-Value. The processing of this mapping, weighted by the provided utility value could be used as a bias for the interpretation of the rules, as an input for the behavior modeling.
The scenario we use for evaluating the learning architecture
approach is the same as in [
The main objective of the simulation concerned the
emergence of collision-free exiting behavior. Therefore, the reward
and interfaces to the environment were mainly shaped to
support this. In contrast to [
The basic scenario consists of a room (40x60m) surrounded by walls with one exit and a different number of columntype obstacles (with a diameter of 3.5m). In this room a number of pedestrians have to leave as fast as possible without hurting themselves during collisions. We assume that each pedestrian agent is represented by a circle with 50cm diameter and moves with a speed of 1.5m/sec. One time-step in the discrete simulation corresponds to 0.5sec. Space is continuous. We tested this scenario using 1, 5, 10 and 20 agents, and the number of obstacles was set to 10. At the beginning of a testrun, all agents were located at random positions in the upper half of the room.
All experiments alternated between explore and exploit phases. During the explore phase, the agents randomly execute an action. In exploitation trials, the best action was selected in each step. Every trial consists of 100 iteration steps. Every experiment took 1000 explore-exploit cycles.
Reward was given to the agent a immediately after executing an action at time-step t. It was computed in the following way: reward(a, t) = rewardexit(a, t)+rewarddist(a, t)+f eedbackcollision(a, t)+ f eedbackdamage(a, t) with rewardexit(a, t) = 1000, if agent a has reached the exit in time t, and 0 otherwise; rewarddist(a, t) = β × (dt(exit, a) − dt−1(exit, a)) with β = 5; f eedbackcollision(a, t) was set to 100 if a collision free actual movement had been made, to 0 if no movement happened, and to −100 if a collision occurred; f eedbackdamage(a, t) was set to −1000 if a collision with column obstacle has occurred, and 0 otherwise. Together, the different components of the feedback function stress goaldirected collision-free movements. It is goal-directed because the agents are positively rewarded every time an action results in reaching the exit or getting to a state closer to the exit. Complementary, it is collision-free oriented because the agents are positively rewarded for moving without collisions and negatively rewarded every time an action results in a collision.
As agent interfaces, the perceived situation and the set
of possible actions have to be defined. Similar to [
The action set is shaped for supporting the collisionavoidance behavior. We assume that the agents are per default oriented towards the exit. Thus, the action set consists of A = {M oveLeft, M oveSlightlyLeft, M oveStraight, M oveSlightlyRight, M oveRight, N oop, Stepback}. For any of these actions, the agent turns by the given direction (e.g. +36 degrees for M oveSlightlyRight), makes an atomic step and orients itself towards the exit again. The combination of this action set and the perceptions of the agents represents an intentional simplification of the problem, as we implicitly represent the orientation task in the actions, in order to have a MDP. This simplification allows concentrating the learning on the collision avoidance, facilitating the learning process.
The testbed was implemented in the visual modeling and simulation platform SeSAm (www.simsesam.de). The QLearning could be implemented by means of the standard highlevel behavior language in SeSAm.
It was not our objective to find the optimal configuration for the tested architecture in the given scenario, we will not give a discussion of the effects of different parameter settings on the learning outcome should not be necessary. Clearly, we tested a number of configuration for finding a reasonable configuration. This is also true for the the appropriate overall configuration including different numbers of obstacles, sizes of scenarios or the particular numbers of the reward function. In the context of this paper, we assume an initial Q-value of 0 for all untested state-action pairs. We set the learning rate to 0.5 and the discount factor to 0. It means that the agents’ actions are selected based on recent experiences and not taking into consideration the future rewards (only the best action for the current state), respectively. This is another intentional simplification for the problem, as the agents don’t need to maximize future rewards.
In this section we analyze the results of the simulations, first with respect to learning performance showing that the learning technique is actually applicable to the test scenario, but then we focus on the analysis of what the agents actually did learn.
The metric used for evaluating learning performance is the number of collisions. The time to reach the exit does not vary significantly, as a collision is not influencing the behavior directly, but indirectly via the reward the agent got. The collisions, with other pedestrians or obstacles, do not impose any effect on future movement. They only count as negative rewards. Obviously in the early stages, the agents don’t have enough experience to learn from, and therefore a higher number of collisions is expected.
Table I presents the mean number of collisions for each tested situation. The values are aggregated only after the first 50 explore-exploit cycles for avoiding the inclusion of any warm-up data. The mean and deviation over the results of the different exploit cycles are given. Despite of having the runs repeated, we did not give means and standard deviations over different runs as currently the number of repetitions is too low. Clearly the number of collisions increases with the number of agents and obstacles.
Figure 2 illustrates the adaptation speed by depicting the number of collisions over time for an exemplary run with 5 agents and 10 obstacles. We can see that the number of collisions decreases fast in the beginning, but then the behavioral knowledge converges quite fast. After 50 cycles, there is no further improvement.
To have a better illustration of the learning process, we show in figure 3 the trajectories of the agents in exploit phases after a) 10, b) 100, c) 500 and d) 1000 exploit trials. In this figure we consider the situation with 5 agents and 10 obstacles. We can see the progress of adaptation with more and more collision-free and goal-directed movement. Experience hereby does not just mean positive reinforcement. Even if the agents don’t know what is the best action, they know which one to avoid by checking the negative rewarded actions.
Alternating between explore and exploit trials plays an important role in the performance outcome. The agents must explore the possible actions set in order to maximize their experience in terms of the route to be chosen. At the end we can see the emergence of a collision-avoidance behavior.
In this section we are interested in analyzing the rules learned by the Q-Learning process in terms of the complexity of the resulting rule structure and potential use as source of inspiration in a modeling process.
In the following analysis we will examine two simulation scenarios: 1 agent and 10 obstacles; and 5 agent and 10 obstacles. In both cases we consider the outcome of one agent from an exemplary simulation.
1) Raw Q-Learning Rules: The rules generated by the learning process can be determined by taking for every situation the action with the highest q-value as it is done in the exploit phases. Depending on the situation, there might be no action with a positive q-value. The rules with a Q-Value of zero represent situation-action pairs that have not been tested during the simulation. Figure 4 depicts two out of 12 rules with the highest Q-value on the 1-agent scenarios.
Figures 5 and 6 show the distribution of the reward prediction, i.e. the Q-value, for the complete rules set for the single agent, respectively a randomly selected exemplary agent from a simulation with 5 agents. One can see that there are only a few rules with a high Q-value.
It is obvious that the Q-value alone cannot be a selection criteria for rules forming a behavior model as the ones with the highest Q-value naturally contain situations where the agent directly perceives the exit. It is also possible to see that the agent in this case has a majority of rules with Q-Value 0, which means that a lot of state-action mappings have not been tested. This is not case for the simulation with 1 agent and 10 obstacles, as seen in figure 5, where the majority of rules have been tested. The agent has explored more, resulting in a more elaborated representation of the behavior. This difference is caused by the fact that the simulation with only 1 agent presented a smaller set of possible states to be tackled due to the simplicity of the interactions just with static obstacles.
Another important aspect about the agents’ experience is that, since the agents are randomly positioned in the scenario at the beginning of each trial, the rules are not biased by a fixed position, so the rules set is more elaborated than it would be if they had to know only one best way to get to the exit.
The agent from the simulation with only one agent has a positive rules set – consisting of rules with positive, non-zero q-values – of 229 rules, while the agent from the simulation with 5 agents has a number of 1507 true positive rules. This can be seen as an effect of the interaction with other agents, generating different situation to be visited, specially when it gets closer to the exit, the situation becomes more dense and the agents must avoid the collisions, and get to the exit.
Figures 7 and 8 show the distribution of these final rules over the possible actions, for the cases with 1 and 5 agents respectively. We can see the effect of the initial random positioning in each trial. We have a balanced distribution for the rules determining going to the left or right, which makes sense, since the agent must learn to find its way out of the scenario no matter where it has started. The majority of the rules indicate the M oveStraight action. This comes from the fact that the agent is reoriented towards the exit after the execution of any action. Unless the agent needs to avoid a collision, M oveStraight is the best action to choose.
We can identify the collision-avoidance behavior focussing on an exemplary element of the perceptions of the agent (1 agent scenario in this case). Considering action M oveRight and perception ObstacleImmediatelyRight, we see that there is a larger number of rules indicating false in this perception in all rules with the M oveRight action, see figure 9.
2) Processing the rules: As the set of rules with truly positive Q-value in all scenarios is far too large to be transparently presented to a human expert, we suggest to use a post-processing step for improving the analysis of the rule set on a detailed level. As there are a number of candidates that may be suitable for generalizing the rule set in a way that all learnt rules are captured in a compact form.
For this aim, we tested three different machine learning
algorithms – mainly classification learners – using all rules
with non-zero, positive Q-Value: K Nearest Neighbors (KNN)
[
As mentioned above, the results of this post-processing step have to be evaluated with two criteria: How well they capture the given rule set and how good they are able to generalize the rule set for bringing the rules. The first can be measured in terms of classification accuracy, the second is the generalization and compactness of the resulting behavior description.
a) Classification Accuracy: Table II shows the classification accuracy for the above mentioned algorithms, both in the 1 agent and 5 agents experiments, using 10 fold cross validation in the training set. Table III shows the average classification accuracy, when model built from one agent’s experience is tested with another agent’s experience: We can see that the classification accuracy for the case with 1 agent outperformed the case with 5 agents. This is clearly an effect of the exploitexplore tradeoff. The agent from the 1 agent simulation has a lower number of states to visit during the simulation, and this reflects on the accuracy of the rules as they are tested more times and converge faster to the optimal solution (state-action mapping). The agents from the 5 agents scenario have a larger set of states that potentially may occur, reflected also in the number of rules. This requires more cycles to converge to an optimal solution.
While they are all good models – as providing a solution to the problem (as seen in section V-A) – they can not be generalized to other good solutions (other agents’ experiences). The convergence of the solution, which determines its generalization to the problem is therefore a function of the configuration of the learning, and more important, a function of the explore-exploit distribution, the number of agents and the set of perceptions and actions, that determine the size of the state-action mapping.
Figure 10 shows the confusion matrix for the decision tree learnt from the simulation with 1 agent, testing with cross-validation: Rows represent the expected class (action) from the classification model, as presented in the Q-Learning mapping and columns represent the classification determined by the decision tree. We highlight the number of correctly classified instances. The majority of misclassified instances falls on cases where different actions could result in similar, good rewards. For instance, there is a common misclassification among the actions M oveStraight, M oveSlightlyRight and M oveSlightlyLeft. This comes from the fact that when the agent is facing the exit, all these three actions will maximize the reward (represented by reaching the exit).
Representation: The second dimension is to be analyzed, with regards to the improving the representation of the behavior for a human modeler. We assumed that the best result could be produced by the decision tree learner. However, the CART decision tree learner was not able to produce an understandable, compact model in this problem. In the case of 1 agent the tree has 117 nodes and 59 leaves. For the case with 5 agents the tree has 1637 nodes and 819 leaves. For illustration, figure 11 outlines a part of the tree generated from the experience of the agent in the case of 1 agent and 10 obstacles. In this figure, the codes represented in the rule stand for different agent perceptions. For instance EIA means Exit Immediately
The post-processing result provided by the CN2 algorithm is better than the decision tree learner: For example, figure 12 shows the best 3 (from a total of 29) rules created by the CN2 algorithm, from the training set of non-zero, positive rules in the case of 1 agent. CN2 was able to reduce the rules representation from 229 to 29 rules. The rules can be evaluated by their quality, size and coverage. Here, as for the decision trees, the perceptions are represented by codes. The rules are clear and concise. Because of that, CN2 can be seen as a step further towards interpretability.
In principle, a set of rules for the agents’ producing a solution to the evacuation problem could be learnt – using a technique that results in human-readable rules. However, from these rules that were found by the Q-Learning, we could not construct a behavior representation that fully resembles the knowledge coded in the rule set, nor derive a representation of the rules that a human modeler could easily oversee. On the other side, the scenario is so simple, that it is possible to directly program a set of about 10 rules exhibiting almost optimal behavior.
In this paper we presented our investigation towards a learning-driven methodology by evaluating Reinforcement Learning as an agent learning architecture. The main motivation for this work is investigate the possibilities of creating a learning-based methodology for the design of a multiagent simulation model avoiding a time consuming trial and error process when determining the details of agent behavior.
In a small evacuation scenario, we showed that the employed learning technique can produce plausible behavior in an agent-based simulation. However, the interface between the learning technique and the agent environment is by no means trivial. The environmental model, feedback function, perception, and action sets are critical. There are also ideas on the analysis of the different architecture that may improve the usability of the learned behavior model.
Using a learning technique transfers the basic problem from
direct behavior modeling to designing the agent interface and
environment reward computation. To do so successfully, a
general understanding of scenario difficulties and the
available machine learning techniques is necessary. An example
is the fundamental requirement of the Markov property in
reinforcement-based approaches [
The standard implementation of Q-Learning, used in this paper, offers us only the estimated reward for each possible condition-action pair. For more intelligent interpretation of the rule set – that is in its raw state without any form of generalization – we decide to use three different machine learning algorithms: K-Nearest Neighbors, Decision Trees and CN2 rule inductor. The resulting, full behavior model for the Q-Learning is only partially helpful as a guidance for modeling in this case. Generalization still needs to be improved, as a part of the learning process or as a post-processing step. This could be achieved by using more flexible classification techniques, such as multi label classification, since in this process we have to deal with multiple good solutions. Another important aspect to be considered here is the tradeoff between explore and exploit, and how this scales to the complexity of the problem, in terms of the number of agents and the size of the stateaction mapping in a multiagent simulation. This is a relation yet to be analyzed in detail level.
There are admittedly many more challenging application scenarios than an evacuation scenario where all agents have the same goal, the behavior repertoire is quite restricted, and there is no direct communication between agents. In such advanced environments, the learning and environment design will certainly pose additional challenges.
Our next steps include testing other learning techniques to
investigate their performance, outcome and appropriateness
for this methodology. A short analysis of Learning Classifier
Systems and Neural Networks can be found in [
Besides that, we will pursue further self-modeling agent experiments. We are considering the application of the learning technique in other, more complex scenarios, such as an evacuation of a train with about 500 agents, complex geometry with exit signs and time pressure. We are also interested in a scenario where cooperation / collaboration is required, in order to investigate the possible emergence of the cooperation in the agent model, through the learning process. This experimentation should consider situations with and without direct communication between the agents.