Common topologies in agent-based simulation
January 29, 2022
Whenever it is necessary to assess the impact of individual components on the state of a system, agent-based simulation can be a potent tool. With that said, agent-based models can be challenging to plan and develop – there are virtually endless ways to arrange agents in a system.
Agent topologies alleviate this issue by offering a structured way of building simulations. There are many topologies in agent-based simulation – each suited for a particular task. In this blog post, we will cover some common agent topologies and their advantages and disadvantages.
What are topologies in agent-based simulation and why are they important?
At a high level, a topology in agent-based simulation is essentially a system map. This map shows the position of the agents in the system and outlines how the agents are connected (Figure 1).
On a more technical level, a topology is a set of rules that define how agents interact. Among other things, topologies define (Zhu, 2006; Heinze, et al., 2002):
- What type of communication agents support.
- Who they can communicate within the system.
- Whether they can communicate with other agents directly or if they need to send requests through intermediary agents.
Why are topologies necessary in agent-based simulation?
Topologies serve as templates that businesses can use to define their simulation environments more efficiently. But how exactly is this helpful?
Agent-based models can have very different sizes and levels of complexity. Agent-based simulations can be small at one end of the spectrum, having just a dozen or two agents. There are large simulations with hundreds and even thousands of agents at the other end.
Small systems can be reasonably easy to build even without rigid rulesets. However, as system size increases, teams need a better way to handle complexity and quickly scale their simulations.
With agent topologies, defining the behavior of each agent from scratch is unnecessary. Simulation teams only need to create specific rulesets for each of the agent types in the model. And when simulation engineers add new agents to the system, only the type needs to be selected – the rules defined earlier will automatically determine how the agent should behave and interact with its environment.
Common topologies in agent-based simulation
- Web-like topology,
- Star-like topology,
- Grid-like topology, and
- HCAN (hierarchical collective agent network) topology.
These topologies have varying degrees of flexibility, reliability, robustness, and adaptability – more below.
The web-like topology is relatively easy to understand, but it can be challenging to implement (Figure 2).
In this topology, all agents are directly connected to each other. Every agent can exchange information and send and receive requests to any other agent in the system.
Agents in the web-like topology typically have identical capabilities and decision-making rules. Privileges and rights are distributed equally across all agents, and there are no intermediary entities that carry out communication.
Despite their shared internal structure and functionality, agents in the web-like topology can have distinct goals. These goals can be defined by the agents’ internal variables and their interactions with their environment.
Web-like networks are very robust and have a reasonable degree of parallelism. However, they can perform very poorly if the agents don’t have specific responsibilities that would allow them to coordinate with each other.
Because agents are not organized into groups in the web-like topology, assigning specific tasks can be very difficult. With groups, task assignments can be done at a group level. In contrast, one would need to assign tasks to each agent in web-like systems individually. Not only would this be tedious, but simulation engineers would require a meticulous understanding of agent interactions to build a good model.
All in all, the advantages and disadvantages of the web-like topology are as follows.
|Redundancy and robustness. Web-like systems, if designed correctly, can be exceptionally fault-tolerant and robust. Because agents are identical as far as their capabilities are concemed, failures of one or more agents don’t dramatically affect the entire system’s state.||Complexity. Web-like systems can be challenging to handle because agents can freely interact with each other. Properly designing a free-flow system with complex agent interactions can be highly challenging.|
|Parallelism. When agents are assigned different tasks, the web-like topology has high levels of parallelism. Global tasks are perfomed more efficiently by web-like systems.||Potentially poor coordination and adaptation. Although agents are densely connected, coordination and collaboration in a web-like topology can be challenging to achieve. Each agent needs to have its own internal protocols nad control functions that define cooperation rules to cooperate with others effectively. Otherwise, agents may interfere with each other, and they may not handle inconsistencies in input data.|
|Challenging distribution of tasks. Assigning specific tasks to different groups of agents is difficult in the web-like topology. Again, this is because all agents in the system have equal capabilities and are not distributed into groups.|
IIn the star-like topology, agents cannot communicate with each other directly. Instead, they communicate and collaborate through a particular type of agent called a facilitator (Figure 3).
Facilitators are aware of the state and responsibilities of the agent groups they oversee. Upon receiving a request from an agent, facilitators look up agents that can handle the request and decide how the request should be distributed among suitable agents.
Because agents need to address facilitators to exchange information with other agents, star-like systems are tightly coordinated and controlled. While this can negatively affect performance, star-like networks can be extremely reliable.
All in all, the star-like topology has the following advantages and disadvantages.
|Modularity. Star-like systems are modular and can expand quickly when necessary. Agent groups with different functionalities constitute building blocks that can be added to existing models. Not only are star-like systems expandable, but they can be quickly improved with groups of agents that perform new tasks.||Relatively low performance. To communicate, agents in different groups need to interact with at least one intermediary agent. In very complex systems with large chains of facilitator agents, this can significantly slow down performance.|
|Simplicity. Because of their more modular structure, star-like systems are easier to conceptualize and design. Handling complex interactions between an arbitrary number of agents are unnecessary. The more “grouped” structure makes understanding and designing star-like systems more manageable.||Potential bottlenecks. Facilitator agents can be potential bottlenecks in a star-like system. If the number of requests is too high for facilitators to handle, the entire system may not perform its tasks effectively.|
|Effective coordination. Thanks to facilitator agents, global goals can be performed more quickly because of the adaptability of the star-like systems. Facilitators can decide who to assign incoming requests to on their own, making the system more efficient. Inconsistencies in data are easy to handle in star-like systems as well.||Lack of robustness. Because agents rely on facilitators to send and handle requests, facilitators are a significant point of failure in star-like networks. Unless the system has many backup facilitators, the failure of even one facilitator can impede the entire system’s function.|
The grid-like topology combines some of the web and star-like topologies' traits (Figure 4).
On the one hand, like in the star-like topology, grid-like systems have facilitators that link agents to each other. On the other hand, agents in a grid-like system are directly connected to other agents in their neighborhood – somewhat like in the web-like topology.
Due to this mix of features, the grid-like topology combines some of the advantages and disadvantages of the web- and star-like topologies. At a high level, grid-like networks are robust and can perform well in clearly defined systems. However, they can be difficult to upscale.
The pros and cons of the grid-like system are given below.
|Effectiveness in well-defined systems. If the target system is clearly defined and understood, the grid-like topology can allow teams to build agent networks that coordinate very well.||Weak adjustability and modularity. The connections between adjacent agents make grid-like systems hard to adjust. Again, grid-like systems are best suited for more static and better-understood processes.|
|High level of flexibility and robustness. When necessary, adjacent agents in the grid-like topology can freely interchange their responsibilities. This capability adds a good deal of robustness to grid-like systems.|
Unlike the previous topologies, the HCAN (hierarchical collective agent network) topology has a hierarchical structure (Figure 5).
In HCAN networks, agents are organized into layers. The three key characteristics of HCAN layers are as follows:
- Agents in the same layer are typically not connected.
- Agents in adjacent layers are fully connected.
- Agents at higher layers control agents at lower layers.
In HCAN systems, agents at lower levels serve as information collectors. Lower-level agents pass the collected information to agents at higher levels. Based on this information, high-level agents can make decisions that can impact and coordinate lower-level activities.
The HCAN topology is highly adaptive and can very well handle data gaps and inconsistencies. HCAN networks also do well at extracting information from diverse data sources, which is thanks to their layered structure.
We give the advantages and disadvantages of the HCAN topology below.
|Excellent scalability. Additional agent layers can easily be added to existing systems without affecting the state of existing layers.||Challenging planning and implementation. HCAN systems are effective only if the interaction mechanisms and patterns between different layers are well understood. Efficient distribution of responsibilities between layers can be difficult as well.|
|Simplified communication between agents. Because agents can only interact with agents at adjacent layers, communication and data exchange are easy to manage in the HCAN topology.||Relative inflexibility. HCAN systems are less flexible than web-like, star-like, and grid-like topologies. Agents cannot freely interchange roles with each other because of the hierarchical structure of HCAN networks.|
|Diversity. HCAN systems can handle a diverse set of inputs and agent functionalities thanks to their layered structure. Each layer can be dedicated to a very specialized function, allowing HCAN systems to perform complex tasks.|
All in all, agent-based simulation benefits immensely from careful planning. With an in-depth understanding of the agents' tasks, teams can develop more robust, scalable, and coordinated systems.
At the same time, all-inclusive knowledge about a process is not always realistic or possible. In these cases, topologies like HCAN can work great thanks to their solid self-adapting properties.
No matter what, simulation teams should try to gain as much information about the target system as they can. Based on that, they can decide whether to go with a more densely connected but less coordinated model or vice versa. Team members may wish to experiment with inexpensive/free introductory courses:
Heinze, C., Goss, S., Josefsson, T., Bennett, K., Waugh, S., Lloyd, I., et al., (2002). Interchanging agents and humans in military simulation. AI Magazine, 23(2), 37-37.
Macal, C., & North, M. (2014, December). Introductory tutorial: Agent-based modeling and simulation. In Proceedings of the Winter Simulation Conference 2014 (pp. 6-20). IEEE.
Robertson, D. A. (2005). Agent-based models to manage the complex. In Managing Organizational Complexity: Philosophy, Theory, and Application, (Chapter 24), 417-430.
Zhu, Q. (2006). Topologies of agents interactions in knowledge intensive multi-agent systems for networked information services. Advanced Engineering Informatics, 20(1), 31-45.