How Agents Learn to Collaborate: Distributed Task Allocation with Cellular Learning Automata
Project
Table of Contents
- Overview
- Introduction
- Problem Definition
- Dataset Resources
- Preprocessing Steps
- Data and Environment Setup
- Model and Methodology
- Allocating spatial–temporal tasks by using proposed CLA
- Implementation of geospatial simulation environment
- Mathematical Formula
- Evaluation Metrics
- Results
- Conclusion
- References & Resources
- Project repository
Overview
This post presents a distributed, learning-based approach for spatial–temporal task allocation in multi-agent rescue environments. It introduces a model where human rescuers collaborate with intelligent assistant agents, leveraging Cellular Learning Automata (CLA) and GIS data to optimize the assignment of dynamically discovered rescue tasks. The methodology is validated in a simulated urban disaster scenario, focusing on minimizing rescue time and travel distance while ensuring efficient coordination among teams. Key contributions include:
- A fully distributed, adaptive task allocation framework using CLA
- Integration of real-time geospatial data and agent-based simulation
- Mathematical modeling of agent learning and coordination
- Empirical evaluation against auction-based and threshold-based methods
The following sections detail the problem definition, simulation environment, methodology, mathematical formulation, evaluation metrics, results, and conclusions.
Introduction
Efficient task allocation in multi-agent environments (MAE) is a key challenge in distributed artificial intelligence. In such systems, multiple autonomous agents must cooperate to complete a set of spatially and temporally distributed tasks. For example, a key problem in urban search and rescue teams, considering the severe turbulence and complexity of the environments which are hit by a crisis, is the coordination between the team members. In order to solve this problem, an effective plan would be the provision of measures where human works with intelligent assistant agents to assign the tasks in any way. Dynamic tasks are identified by the human agent of the rescue team in the crisis environment and are characterized by spatial–temporal characteristics assigned to the appropriate rescue team by the intelligent assistant agents who apply intelligent decision-making techniques. The objective of this project is to propose a new approach for allocating spatial–temporal tasks in multi-agent systems through stochastic reinforcement learning algorithm based on cellular learning automata as the decision-making technique and GIS data.
This work proposes a fully distributed and adaptive model based on Cellular Learning Automata (CLA) to enable agents to learn optimal task allocation strategies through local interactions and feedback with human, without global supervision.
Problem Definition
The problem is formulated as a Spatial–Temporal Coordination Problem (STCP) in disaster response.
Let
- Search teams: $S = {S_1, S_2, \ldots, S_N}$
- Rescue teams: $R = {R_1, R_2, \ldots, R_M}$
- Rescue tasks: $L = {l_1, l_2, \ldots, l_K}$
Each task:
- is dynamically discovered by search teams,
- has spatial constraints (geographic location),
- has temporal constraints (deadline, urgency).
Objective
Assign each task to a rescue team such that:
- rescue time is minimized,
- travel distance is minimized,
- rescue team capabilities are respected,
- assignments do not negatively impact neighboring teams.
A key challenge is avoiding vital selections, where choosing the “best” rescue team for one search team may severely degrade outcomes for others. This requires agents to anticipate and coordinate decisions, not act greedily or deterministically.
Dataset Resources
This study does not rely on a static dataset; instead, it uses a geospatial simulation environment that models realistic disaster scenarios.
Simulation Inputs:
- Geographic map data (urban environment)
- Locations of critical points (damaged buildings)
- Search team locations
- Rescue team locations and capabilities
- Estimated number of victims
- Task urgency levels
Case Study Location:
- Habibabad city, Isfahan province, Iran
- Earthquake-prone region (used for realism and validation)
Multiple scenarios are generated by varying:
- number of search teams
- number of rescue teams
- number of critical points (50–120)
- task urgency distributions
Preprocessing Steps
- Crisis Area Division: The disaster region is divided into multiple operational areas.
- Initial Damage Estimation: Loss estimation teams identify damaged buildings and estimate victims.
- Search Task Execution: Search teams move to critical locations, collect precise spatial and temporal data, and define rescue tasks.
- Data Synchronization:
- Local databases (on PDAs) store real-time updates.
- A central GIS database enables global awareness.
- Task Characterization: Each task is enriched with location, rescue urgency level, estimated rescue time, and deadline.
These steps ensure that assistant agents operate with up-to-date and spatially consistent information.
Data and Environment Setup
Software & Tools:
- C# / .NET Framework
- ArcGIS Desktop (map and shapefile creation)
- DotSpatial (GIS visualization and spatial queries)
- SQL Database (central + local data management)
Simulation Components:
- Model Layer: agent behaviors and task logic
- Scheduler: manages simultaneous agent execution
- Controller: coordinates system flow
- GIS Engine: spatial queries, distance calculations
Map Scale: 1:5000 (urban-level realism)
This setup allows realistic modeling of distributed intelligent agents operating in a spatially constrained environment.
Model and Methodology
Multi-Agent Systems (MAS) in Crisis Management
A Multi-Agent System (MAS) is a computational framework composed of multiple interacting intelligent agents operating within a shared environment, where each agent has autonomy, a local view of the environment, and decentralized decision-making capabilities. In the context of crisis and disaster response, MAS are particularly well suited because no single agent has complete information or control over the rapidly changing environment. Agents may represent humans, robots, or software assistants, and they are capable of learning, planning, coordination, and communication with other agents to achieve collective goals. The paper highlights that MAS have been widely adopted in emergency-response systems—such as DrillSim, RoboCup Rescue, FireGrid, and DEFACTO—because they can model real-world constraints like uncertainty, partial observability, and distributed control. By enabling assistant agents to support human operators in decision-making, information management, and task coordination, MAS provide a scalable and flexible solution for managing complex, dynamic rescue operations where centralized control is impractical or inefficient.
Machine Learning Model:
Learning Automata
Learning Automata (LA) are reinforcement-learning models designed to operate in stochastic and unknown environments, where an agent must gradually learn the optimal action through interaction with its environment. A learning automaton selects an action from a finite set based on a probability distribution, executes it, and then receives feedback from the environment in the form of a reward (favorable response) or penalty (unfavorable response). Based on this feedback, the automaton updates its action probabilities, increasing the likelihood of selecting actions that lead to better outcomes over time. This iterative process allows the automaton to converge toward the optimal decision without requiring prior knowledge of the environment.
The follwoing figure (Closed-loop interaction between a learning automaton and the environment) illustrates this feedback cycle: the automaton selects an action, the environment evaluates it, and a reinforcement signal is returned to adjust future behavior. This closed-loop learning mechanism is fundamental to enabling adaptive and autonomous decision-making in dynamic systems such as disaster response environments.
Cellular Learning Automata (CLA)
Cellular Learning Automata (CLA) are a class of decentralized, reinforcement-learning models designed to simulate complex systems composed of many simple, locally interacting components. CLA combine the structure of Cellular Automata (CA) with the adaptive decision-making capability of Learning Automata (LA) by assigning a learning automaton to each cell in a spatial grid. Each cell represents an autonomous decision-maker whose behavior evolves over time based on feedback from its local environment, which consists of neighboring cells rather than a global controller.
Formal Definition
A CLA can be defined as:
\[A = (Z_d, \Sigma, A, N, F)\]where:
- $Z_d$ is a $d$-dimensional lattice of cells
- $\Sigma$ is the finite set of cell states
- $A$ denotes the set of learning automata (one per cell)
- $N$ defines the neighborhood structure
- $F$ is the set of action functions governing state transitions
Learning Automaton Action Selection
Each learning automaton selects an action according to a probability vector:
\[P(t) = \{p_1(t), \ldots, p_r(t)\}\]and receives a reinforcement signal from the local environment.
1- Favorable Response ($\beta = 0$)
For a favorable response ($\beta = 0$), the probability of the selected action $i$ is updated as:
\(p_i(t+1) = p_i(t) + a(1 - p_i(t))\) \(p_j(t+1) = (1 - a)p_j(t), \quad j \neq i\)
2- Unfavorable Response ($\beta = 1$)
For an unfavorable response ($\beta = 1$):
\(p_i(t+1) = (1 - b)p_i(t)\) \(p_j(t+1) = \frac{b}{r-1} + (1 - b)p_j(t), \quad j \neq i\)
where $a$ and $b$ are reward and penalty parameters, and $r$ is the number of possible actions.
Applications
Through repeated local interactions and probability updates, CLA enable agents to learn cooperative behavior, adapt to dynamic environments, and converge toward globally efficient solutions. This makes them particularly suitable for large-scale, spatially distributed problems such as disaster response and multi-agent task allocation.
Allocating spatial–temporal tasks by using proposed CLA
Activity Diagram and Algorithm
The task allocation process in the proposed system follows a structured, multi-stage workflow that coordinates human teams and intelligent assistant agents in a disaster environment. Figure 3 (Activity diagram for the steps of task allocations) illustrates this end-to-end process, starting from the incident commander requesting damage assessment and deploying search teams to critical locations. Search teams collect detailed spatial and situational data, update both local and central GIS databases, and then invoke their intelligent assistant agents to allocate rescue tasks. Each assistant agent evaluates available rescue teams, considers spatial constraints, task urgency, and neighboring agents’ decisions, and iteratively refines its choice through learning until a deadline is reached. Once a rescue team is selected, task assignments are communicated, rescue teams move to the assigned locations, and search teams proceed to identify new critical points. This diagram highlights how task allocation is performed simultaneously, autonomously, and adaptively, without relying on a centralized controller, while still maintaining global coordination across teams.
Probability-Based Task Assignment Algorithm (Algorithm 1) defines how each intelligent assistant agent computes the selection probability for available rescue teams when assigning a newly identified rescue task. The algorithm evaluates each rescue team based on multiple factors, including the distance to the critical point, estimated travel time, rescue team capability, workload, and the severity level of the task. A cost function is computed using distance and team ability, while a reward function reflects task urgency and required rescue time. The probability of selecting each rescue team is then calculated as the normalized ratio between reward and cost, producing a probability distribution that guides the learning automaton’s stochastic decision-making. This probabilistic formulation allows assistant agents to avoid purely greedy choices and instead explore alternative allocations, which is essential in dynamic environments where multiple search teams compete for limited rescue resources. By feeding these probabilities into the learning automaton, the system enables adaptive, coordinated, and globally efficient task allocation.
Proposed CLA
The proposed structure of cellular learning automata for allocating spatial distributed tasks
The follwoing figure (The proposed structure of cellular learning automata for allocating spatially distributed tasks) shows how individual learning automata are interconnected through neighborhood relationships. Each automaton evaluates its own spatial environment (e.g., distance to rescue teams) as well as the decisions of neighboring automata to determine whether a selected rescue team is a vital selection for others. Through reward and penalty signals, the automata collaboratively learn to avoid conflicting assignments and converge toward globally efficient task distributions. This structure enables scalable, low-communication, and adaptive coordination among agents in complex disaster scenarios.
Model for integration neighborhood rules and factors of spatial environmental
Logical Variables for Neighbor-Aware Decision Making (Table 2) defines the logical variables used by each learning automaton to evaluate how its task-allocation decision affects neighboring agents. These variables capture whether a selected rescue team may create conflicts or inefficiencies for other search teams operating in the same spatial area. Specifically, T1 checks whether the same rescue team has also been selected by neighboring search teams, indicating potential contention. T2 evaluates whether the selected rescue team is the closest option for neighboring agents, which would suggest that reallocating this team could significantly increase their rescue time. T3 determines whether the selected rescue team is a vital selection for neighbors—meaning that losing this team would force them to choose a much worse alternative. Together, these logical conditions allow an automaton to reason not only about its own optimal choice, but also about the impact of that choice on surrounding agents, enabling cooperative and socially aware task allocation.
Integrating Neighborhood Rules with Spatial Environment Factors (Table 3) presents the decision model that integrates neighborhood awareness with spatial environmental factors to determine whether a learning automaton should receive a reward or penalty for its selected action. The model combines two dimensions: (1) the neighborhood law, which reflects whether neighboring agents are negatively affected by the selected rescue team, and (2) environmental factors, primarily the distance between the rescue team and the critical point. If a selected rescue team is both spatially optimal and does not conflict with neighbors, the automaton is rewarded, reinforcing this choice. Conversely, if the selection negatively impacts neighboring agents—especially when the team is a vital resource for them—the automaton receives a penalty or a probabilistic reward–penalty signal. This balanced mechanism prevents premature convergence to selfish solutions and encourages agents to learn globally efficient allocations that minimize overall rescue time and travel distance across the system.
Implementation of geospatial simulation environment
Implemented Simulation Architecture (Figure 5) illustrates the overall architecture of the geospatial simulation developed to evaluate the proposed task-allocation model. The system is composed of several interacting layers: a GIS engine responsible for managing spatial data and map layers, a model layer that defines the behavior and attributes of search and rescue teams, a scheduler that controls the timing and parallel execution of agents, and a controller that coordinates all system components. A central SQL database stores shared information such as critical points, team locations, and task status, while agents also maintain local data for real-time decision-making. This modular architecture enables realistic simulation of distributed intelligent agents operating simultaneously in a dynamic disaster environment, while supporting spatial queries, learning processes, and coordinated task allocation.
Designed Geospatial Simulation Environment (Figure 6) presents the visual interface of the implemented GIS-based simulator, showing how spatially distributed search and rescue teams operate within an urban environment. The map includes multiple GIS layers such as city blocks, roads, green spaces, and operational zones, along with the real-time positions of search teams, rescue teams, and identified critical points. Through this environment, intelligent assistant agents can calculate distances, evaluate spatial constraints, and visualize task assignments directly on the map. This geospatial representation allows the simulation to closely resemble real-world disaster scenarios, making it possible to assess how the proposed Cellular Learning Automata–based approach improves rescue time, travel distance, and coordination efficiency under realistic spatial conditions.
Mathematical Formula
Response Threshold Model
The probability that agent $i$ selects task $j$:
\[T_{ij}(s_j) = \frac{s_j^n}{s_j^n + \theta_{ij}^n}, \quad n > 1\]Where:
- $s_j$: stimulus of task $j$
- $\theta_{ij}$: internal threshold of agent $i$
Learning Automaton Update Rules
Reward (favorable response): \(P_i(t+1) = P_i(t) + a(1 - P_i(t))\) \(P_j(t+1) = (1 - a)P_j(t), \quad j \neq i\)
Penalty (unfavorable response): \(P_i(t+1) = (1 - b)P_i(t)\) \(P_j(t+1) = \frac{b}{r-1} + (1 - b)P_j(t), \quad j \neq i\)
Where:
- $P_i$: probability of selecting rescue team $i$
- $r$: number of rescue teams
Neighbor-Aware Reward/Penalty Decision: \(\beta = T_1 \wedge T_2 \wedge T_3\)
- $\beta = 0$: favorable response
- $\beta = 1$: unfavorable response
This integrates spatial optimality and neighbor impact.
Evaluation Metrics
The model is evaluated using:
- Average Rescue Time (seconds): Time taken for rescue teams to reach critical points.
- Total Travel Distance (meters): Sum of distances traveled by rescue teams.
- Rescue Team Efficiency (%): Utilization effectiveness of rescue teams.
- Total System Runtime: Time required to allocate all tasks.
Each scenario is averaged over 20 simulation runs to ensure robustness.
Results
Figures 7 and 8 together illustrate how the proposed Cellular Learning Automata (CLA) model enables intelligent assistant agents to learn and coordinate task allocation decisions over time in a decentralized manner. Figure 7 focuses on the learning behavior of four search-team agents while assigning a single rescue task, showing how each agent initially explores different rescue team selections and then gradually updates its action probabilities through reward and penalty feedback until convergence is achieved within the task deadline. Figure 8 extends this analysis to the entire operation period, during which multiple rescue tasks are assigned sequentially, highlighting the agents’ ability to continuously adapt their decisions in response to new tasks, neighbor conflicts, and time constraints. Together, these figures demonstrate that when a selected rescue team is identified as a vital resource for neighboring agents, penalties trigger probability redistribution, encouraging alternative selections that reduce conflicts. The combined results confirm that CLA effectively balances learning, coordination, and temporal constraints, leading to stable, conflict-aware, and efficient task allocation across multiple agents in dynamic disaster environments.
The results demonstrate that the proposed Cellular Learning Automata (CLA)–based task allocation model consistently outperforms both the auction-based approach and the response-threshold model (RTM) across a wide range of simulated disaster scenarios. Performance was evaluated using several key metrics, including average rescue time, total displacement of rescue teams, system runtime, and rescue team efficiency, with each scenario averaged over multiple runs to ensure robustness. The experiments show that CLA achieves the lowest average time to reach critical locations, particularly as the number of tasks and operational complexity increase. Unlike auction-based methods, which suffer from heavy communication overhead, and RTM methods, which scale poorly in dynamic environments, CLA maintains efficient coordination through local interactions and learning. Additionally, rescue teams travel significantly shorter distances under the CLA model, indicating better spatial utilization and reduced redundancy in assignments. These results confirm that integrating learning with neighborhood awareness enables agents to converge toward globally efficient task distributions while operating in a fully decentralized manner.
Key Observations:
- Auction-based methods perform well but are communication-heavy
- Threshold-based methods scale poorly with task complexity
- CLA achieves balanced global optimization through learning and local interaction
- Empirical results show significant improvement in rescue efficiency and time-space utilization.
Conclusion
This work presents a distributed, learning-based framework for spatial–temporal task allocation in multi-agent rescue environments. By combining:
- human decision-making
- intelligent assistant agents
- cellular learning automata
the proposed approach achieves faster, more efficient, and more coordinated rescue operations without relying on centralized control.
The model is particularly suitable for:
- disaster response
- large-scale dynamic environments
- systems with limited communication bandwidth
This study demonstrates that local learning with neighborhood awareness can outperform traditional centralized and market-based coordination methods in real-world crisis scenarios.
References & Resources
For more details on this project, please refer to the following resources:
Project repository
GitHub Code: Multi-Agent Rescue Task Allocation Using Cellular Learning Automata