My project is on simulating & optimising the dynamic task allocation through stigmergy in Robot Swarms; I am using the idea of a meta-heuristic algorithm, inspired by the pheromone production of ants. An existing paper has described this algorithm in a 2D grid on static tasks. I will be modelling it to allow visualisation, further allowing the user to interact with it and implement it in their desired manners. Further, I will deploy the algorithm in a dynamic environment, an extension of the previous paper’s static environment , where tasks appear randomly at any given time using the Multivariate Poisson Distribution to mimic more realistic conditions of different set of probabilities at all locations. I will be testing different parameters of this algorithm such as the behaviour of the pheromone’s (decay rate, diffusion) and the optimal location of the nest around the perimeter, observing the interaction of variables in terms of efficiency and convergence time. The algorithm and behaviour will be modelled in WolframLanguage, creating a dynamic interface for user interactions; this will include the searching, grabbing, homing and depositing state, as shown by the behaviour of ants to create an accurate representation. I will use the concept of a 2D-Cellular Automata as each cell in the grid will hold pheromone levels, presence of a task, and agent presence and state, and each cell’s next state will be determined by their Moore Neighbourhood.
Introduction:
Introduction:
Task allocation of agents comprises of agents communicating and working together to achieve goals more efficiently in a shorter amount of time. Famously, the agents are modelled and referred to as robots, and the operating site is considered to be a grid of cells, which is typically modeled as two-dimensional. Some challenges faced by algorithms and models of task allocation are a dynamic environment with randomly spawning non-predetermined tasks, an unknown environment, and little to no memory for storage which prevents the agents from keeping track of all the tasks completed, remembering the path and identifying tasks from a large distance.
What is the model?
What is the model?
Metaheuristic-inspired algorithms can be used to solve such complex optimization problems by breaking them down into logical, decentralized behaviors derived from natural systems, such as environmental cues and indirect communication mechanisms like pheromone trails.
The ant memory model simulates the behaviour of ants using pheromones to communicate with each other through stigmergy, which is a form of indirect coordination of agents representing emergent behaviour. The behaviour includes 4 states: the searching, grabbing, homing and depositing states represent finding a task, its collection, and its eventual deposition to a nest - an area where all the completed tasks are meant to be placed
The model implemented in this study is conceptually a Cellular Automata (CA) based system, inspired by the foraging behavior of ants. Each cell in the automaton holds information such as task state, pheromone concentration, or agent presence in a list(s).
Emergent task allocation refers to a method of assigning tasks in a dynamic environment where the distribution of work arises from the interactions and decisions of individual agents or team members, rather than being centrally planned or pre-determined.
A Moore Neighbourhood is a two-dimensional square lattice, which comprises of 8 cells surrounding a cell, and the central cell itself. It simulates a discrete, grid-like environment in which individual agents (representing robots) operate based on local information of tasks, other robots and pheromone signals in their Moore Neighbourhood, to find their optimal next step in the grid to serve the end goal of maximising efficiency of tasks completion.
The ant memory model simulates the behaviour of ants using pheromones to communicate with each other through stigmergy, which is a form of indirect coordination of agents representing emergent behaviour. The behaviour includes 4 states: the searching, grabbing, homing and depositing states represent finding a task, its collection, and its eventual deposition to a nest - an area where all the completed tasks are meant to be placed
The model implemented in this study is conceptually a Cellular Automata (CA) based system, inspired by the foraging behavior of ants. Each cell in the automaton holds information such as task state, pheromone concentration, or agent presence in a list(s).
Emergent task allocation refers to a method of assigning tasks in a dynamic environment where the distribution of work arises from the interactions and decisions of individual agents or team members, rather than being centrally planned or pre-determined.
A Moore Neighbourhood is a two-dimensional square lattice, which comprises of 8 cells surrounding a cell, and the central cell itself. It simulates a discrete, grid-like environment in which individual agents (representing robots) operate based on local information of tasks, other robots and pheromone signals in their Moore Neighbourhood, to find their optimal next step in the grid to serve the end goal of maximising efficiency of tasks completion.
What are the states used?
What are the states used?
Inspired by natural swarm intelligence, the model captures how simple agents can collaboratively solve complex problems without central coordination. Agents move across the grid, deposit and respond to pheromones, and adapt their paths based on environmental cues, mimicking the stigmergy-based behavior observed in real ant colonies. The model incorporates parameters such as pheromone decay, diffusion, vision radius, nests and task proximity, allowing for the exploration of how different conditions impact task allocation and efficiency.
By abstracting the behavior of ants into programmable rules within a CA framework, this model serves as a powerful tool for studying decentralized decision-making, emergent behavior and optimization in multi-agent systems.
By abstracting the behavior of ants into programmable rules within a CA framework, this model serves as a powerful tool for studying decentralized decision-making, emergent behavior and optimization in multi-agent systems.
Building up on previous research
Building up on previous research
This paper extends previous stigmergy-based task allocation models by developing an interactive, user-friendly simulation interface that allows users to visualize and customize algorithm behavior. Unlike prior work limited to static 2D environments, this study introduces dynamic task generation using an accurate Multivariate Poisson Distribution and expands the model into a 3D grid, marking the first application of this algorithm in such a setting.
Objectives:
Objectives:
This project aims to:
1. Effectively create a dynamic user interface for allowing users to input conditions
2. Implement Static task allocation
3. Implement the Searching and Grabbing state for the Ant Memory Model using Pheromone techniques
4. Implement the Homing and Depositing states for the Model, with a nest for depositing tasks
5. Create a multivariate Point-Poisson Distribution for accurate variance
6. Implement functional Dynamic Task Allocation
7. Parameter testing for optimisation, to identify trends and optimal parameters for the emergent behaviour
8. Develop a 3-Dimensional Model & Simulation
1. Effectively create a dynamic user interface for allowing users to input conditions
2. Implement Static task allocation
3. Implement the Searching and Grabbing state for the Ant Memory Model using Pheromone techniques
4. Implement the Homing and Depositing states for the Model, with a nest for depositing tasks
5. Create a multivariate Point-Poisson Distribution for accurate variance
6. Implement functional Dynamic Task Allocation
7. Parameter testing for optimisation, to identify trends and optimal parameters for the emergent behaviour
8. Develop a 3-Dimensional Model & Simulation
Creating a Dynamic User Interface
Creating a Dynamic User Interface
Poisson-Point Function for Dynamic Task Allocation
Poisson-Point Function for Dynamic Task Allocation
Implementing the Ant-Memory Model
Implementing the Ant-Memory Model
Searching & Grabbing State :
Searching & Grabbing State :
In the searching state, the ant actively explores the grid to locate unassigned tasks. Its movement is guided by pheromone concentrations of the neighbourhood (local cells) around it; Lower levels of pheromones attract the ant’s attention, while unexplored or high-pheromone areas discourage exploration by exemplifying a path that has previously been visited recently, or multiple times. This enables efficient coverage and helps prevent redundant paths among multiple agents for increasing efficiency. Grabbing state is referred to when, the agent is can see the task (vision radius <= 1), and thus it moves towards the task in order to go back to the homing state, to collect it
In the searching state, we determine the next neighbour that a robot will visit using the Step function by keeping a track of the Pheromone levels. Initially, valid options of cells to move too are scanned by selecting all cells which are going to be in the dimensions of the grid, and are not occupied by other robots in the searching or the homing state.
In the searching state, we determine the next neighbour that a robot will visit using the Step function by keeping a track of the Pheromone levels. Initially, valid options of cells to move too are scanned by selecting all cells which are going to be in the dimensions of the grid, and are not occupied by other robots in the searching or the homing state.
Here is an example if the coordinate was {15, 15} for a 15x15 grid:
In[]:=
Select[{{14,14},{14,15},{14,16},{15,14},{15,16},{16,14},{16,15},{16,16}},(1<=#[[1]]<=15)&&(1<=#[[2]]<=15)&&!MemberQ[{Orange,Brown},globalstate[[#[[1]],#[[2]]]]]&]
Out[]=
{{14,14},{14,15},{15,14}}
The minimum pheromone value in a valid cell is calculated:
In[]:=
minValTMP=Min[pheromone[[#[[1]],#[[2]]]]&/@{{14,14},{14,15},{15,14}}]
Out[]=
0
A list (subset) of elements with the smallest pheromone are found:
In[]:=
validOptionsTMP=Select[{{14,14},{14,15},{15,14}},pheromone[[#[[1]],#[[2]]]]==minValTMP&]
Out[]=
{{14,14},{14,15},{15,14}}
A random choice from the the elements with the smallest pheromone level’s is chosen:
In[]:=
If[Length[validOptionsTMP]>0,RandomChoice[validOptionsTMP],{15,15}]
Out[]=
{15,14}
Then, the neighbouring cells with the lowest pheromone level is chosen after comparing the values. If there are multiple such grids, it is resolved by choosing a cell randomly. However, if a task is spotted in the neighbouring 8 cells during the searching state, the robot ignores the Pheromone levels and moves to the cell with the task; But, in the case of multiple tasks, any one of the task is chosen:
In[]:=
Select[{{14,14},{14,15},{15,14}},globalstate[[#[[1]],#[[2]]]]===Blue&]
Out[]=
{}
Homing & Depositing State
Homing & Depositing State
Once a task is found, the robot picks it up and marks it as being handled to avoid duplication by others, in the grabbing state. In this state, the robot has to move back to the nest in order to deposit the task (ex: depositing food); It ignores the Pheromone values, as it is not searching for tasks for any longer. The depositing state, is known as the stage where the ant delivers the task to the nest and resets to begin the next search cycle. But, it is not depicted as a state separate from homing as the depositing of a task is conceptual and not different to reaching the location of the nest.
The step function has also been used for the Homing State, with a valid options of cells being scanned using the same function as the searching state. Though, in the scanning state the optimal cell for the agent to travel to is determined by which cell will make the agent the closest to the nest where the collected/finished task has to be deposited. If there are multiple such cells, a random cell is picked in this case too in the Nearest function of Wolfram.
The step function has also been used for the Homing State, with a valid options of cells being scanned using the same function as the searching state. Though, in the scanning state the optimal cell for the agent to travel to is determined by which cell will make the agent the closest to the nest where the collected/finished task has to be deposited. If there are multiple such cells, a random cell is picked in this case too in the Nearest function of Wolfram.
In[]:=
If[{{14,14},{14,15},{15,14}}=!={},Nearest[{{14,14},{14,15},{15,14}},{15,7}][[1]],{15,15}]
Out[]=
{15,14}
In the case of no valid cells to move to, if all neighbouring cells have been occupied, the robot stays in the same location for the turn, as also shown in the above block of code.
Colour & State Changes:
Colour & State Changes:
If a robot is in homing state, and is moving to a nest in order to deposit the task, the colour of it is changed back to orange to indicate it re-entering the searching state
Similarly, if a robot is collecting a task, it is colour is changed from orange to brown as it is entering the homing state.
Similarly, if a robot is collecting a task, it is colour is changed from orange to brown as it is entering the homing state.
The robot states of each cell (robotState) are changed from IDLE to SEARCHING to HOMING depending on the behaviour the robot is about the adopt after this move:
In[]:=
foundlist={0};found=0;nestLocation={globalrow,Floor[globalcol/2]};historyStates={globalstate};historyPheromone={pheromone};decayRate=0.01;diffusionAmount=0.25;
step[currow_Integer,curcol_Integer]:=Module[ {neighbors,cord,taskNeighbors,minVal,validOptions,chosen,nextrow,nextcol,isHoming}, isHoming=(robotState[[currow,curcol]]==="HOMING");neighbors={{currow-1,curcol-1},{currow-1,curcol},{currow-1,curcol+1},{currow,curcol-1},{currow,curcol+1},{currow+1,curcol-1},{currow+1,curcol},{currow+1,curcol+1}};cord=Select[neighbors,(1<=#[[1]]<=globalrow)&&(1<=#[[2]]<=globalcol)&&!MemberQ[{Orange,Brown},globalstate[[#[[1]],#[[2]]]]]&];If[isHoming, chosen=If[cord=!={},Nearest[cord,nestLocation][[1]],{currow,curcol}], taskNeighbors=Select[cord,globalstate[[#[[1]],#[[2]]]]===Blue&];If[Length[taskNeighbors]>0,chosen=RandomChoice[taskNeighbors],minVal=Min[pheromone[[#[[1]],#[[2]]]]&/@cord];validOptions=Select[cord,pheromone[[#[[1]],#[[2]]]]==minVal&];chosen=If[Length[validOptions]>0,RandomChoice[validOptions],{currow,curcol}]]];{nextrow,nextcol}=chosen;If[globalstate[[nextrow,nextcol]]===Blue&&robotState[[currow,curcol]]=!="HOMING",tasks--;found++;robotState[[currow,curcol]]="HOMING";];;globalstate[[currow,curcol]]=White;globalstate[[nextrow,nextcol]]=If[robotState[[currow,curcol]]==="HOMING",Brown,Orange];robotState[[nextrow,nextcol]]=robotState[[currow,curcol]];robotState[[currow,curcol]]="IDLE";pheromone[[nextrow,nextcol]]+=1;Table[With[{r=neighbor[[1]],c=neighbor[[2]]},If[1<=r<=globalrow&&1<=c<=globalcol,pheromone[[r,c]]+=diffusionAmount]],{neighbor,neighbors}]];
The function runSimulation has been used in order to run the code and simulate all the moves of robots to complete tasks. It makes use of the behaviour of the ant memory model defined in step, for individual robots, and uses this to run it over all steps (iterations) for all robots; Thus, it computes and stores all states during the simulation. Additionally, new tasks are generate randomly by calling the Poisson Point function. Each step’s state is stored in historyStates & globalPheromones
The runSimulation function runs the full simulation loop by updating robot behaviors and environment states at each step. It first identifies active robots (cells colored Orange or Brown) and stores their positions in the agents list. Each robot then performs its action through the Step function. Pheromone levels decay gradually across the grid, with a set decay rate, to maintain adaptability; This also allows them to adapt to dynamic tasks appearing on the grid at any set point of time. New tasks are generated dynamically using a Poisson Point Process and are placed only in empty, idle cells. The current state of the grid and pheromone levels are saved after each step in historyStates and historyPheromone. The loop continues until all tasks are completed or 400 steps have passed, enabling visualization and performance analysis. This limit was chosen after observing performance trends, where most simulations stabilized or completed within that range. A limit needs to be set for preventing extenuating circumstances where rate of tasks appearing overwhelms agents
The runSimulation function runs the full simulation loop by updating robot behaviors and environment states at each step. It first identifies active robots (cells colored Orange or Brown) and stores their positions in the agents list. Each robot then performs its action through the Step function. Pheromone levels decay gradually across the grid, with a set decay rate, to maintain adaptability; This also allows them to adapt to dynamic tasks appearing on the grid at any set point of time. New tasks are generated dynamically using a Poisson Point Process and are placed only in empty, idle cells. The current state of the grid and pheromone levels are saved after each step in historyStates and historyPheromone. The loop continues until all tasks are completed or 400 steps have passed, enabling visualization and performance analysis. This limit was chosen after observing performance trends, where most simulations stabilized or completed within that range. A limit needs to be set for preventing extenuating circumstances where rate of tasks appearing overwhelms agents
In[]:=
runSimulation[]:=Module[{stepcount=0,agents,newGrid},historyStates={globalstate};historyPheromone={pheromone};foundlist={0};While[stepcount<400 &&tasks>0,agents={};Table[If[MemberQ[{Orange,Brown},globalstate[[i,j]]],AppendTo[agents,{i,j}]],{i,globalrow},{j,globalcol}];Table[step[agents[[k,1]],agents[[k,2]]],{k,Length[agents]}];Table[If[pheromone[[r,c]]>=decayRate,pheromone[[r,c]]=Max[0,pheromone[[r,c]]-decayRate]],{r,globalrow},{c,globalcol}];newGrid=simulatePPPGrid[globalrow,globalcol,10,λ]["FinalGrid"];Table[If[newGrid[[i,j]]==1&&globalstate[[i,j]]===White&&robotState[[i,j]]==="IDLE",globalstate[[i,j]]=Blue;tasks++;],{i,globalrow},{j,globalcol}];AppendTo[historyStates,globalstate];AppendTo[historyPheromone,pheromone];AppendTo[foundlist,found];stepcount++;];]
In[]:=
runSimulation[]
historyStates stores the state of each cell of the grid (globalstate) at every step. Storing each step helps in creating a visualisation of the algorithm with precomputed states:
In[]:=
historyStates
Out[]=
Initial State Generator & Re-setter Function for Grid for Optimizations
Initial State Generator & Re-setter Function for Grid for Optimizations
Optimising Parameters:
Optimising Parameters:
Decay Rates + Diffusion Values
Decay Rates + Diffusion Values
To improve the efficiency of emergent task allocation, the model must first undergo systematic testing of its key parameters, in order for identifying the optimal values of different variables to choose. Some variables , such as pheromone decay rate and diffusion value, have been shown to shape how agents interact, respond to tasks, and coordinate through stigmergy, as different values produce measurable changes in task convergence speed, path formation stability, and the distribution of agents across the environment. Thus, this study explores the interplay of parameters
In order to refine emergent task allocation efficiency, there is a need to test the model conducts testing of pheromone decay rates and diffusion values, two critical parameters influencing stigmergic coordination. The decay rate regulates pheromone evaporation over time. Higher decay fosters exploration, while lower decay reinforces trail persistence by preventing pheromones in a path to get cleared up. Further, diffusion determines the extent to which pheromones spread to directly neighbouring cells in the Moore neighbourhood, enabling indirect communication across the grid. Optimal diffusion enhances local coordination between the agents by forming differentiable gradients of pheromone levels between cells, whereas excessive diffusion may dilute spatial cues by narrowing this gradient. During testing, all other parameters such as grid size, initial task distribution, agent count, Point-Poisson spawn rate are held constant to isolate the effects of decay and diffusion on the emergent behavior.
The function evaluatePheromoneParams runs multiple simulations to evaluate how different pheromone decay and diffusion values affect task completion. It loops over all combinations of decay and diffusion values, running each setting multiple times. For each run, it resets the simulation, runs it, and tracks performance metrics like steps taken, tasks completed, and tasks remaining. The function returns a list of average results, with 5 tries taken for each parameter combination, to ensure accuracy by minimizing the impact of stochastic variability. It is used for comparing the average steps taken based on the decay rate and diffusion amount for a graph plotted later.
resetSimulationGlobals resets all global variables to prevent tests effecting each other while GenerateIntitialState randomly generates a state ensuring fairness of experiment. The parameters tk and rb defined in the Module of the code block represent tasks and robots respectively, and can be changed by the user.
A starting configuration of 10 tasks and 8 agents were chosen to maintain a slight task-to-agent imbalance, ensuring sufficient interaction and competition among agents to better observe emergent coordination dynamics, with a large enough number of agents, while keeping it computationally smooth This also creates a manageable yet challenging task load, where the number of tasks slightly exceeds the number of agents to encourage dynamic task allocation and prevent trivial saturation, where the agents complete the tasks in the first few steps. while also ensuring that in most cases, agents can complete the task within the 400 defined steps.
In order to refine emergent task allocation efficiency, there is a need to test the model conducts testing of pheromone decay rates and diffusion values, two critical parameters influencing stigmergic coordination. The decay rate regulates pheromone evaporation over time. Higher decay fosters exploration, while lower decay reinforces trail persistence by preventing pheromones in a path to get cleared up. Further, diffusion determines the extent to which pheromones spread to directly neighbouring cells in the Moore neighbourhood, enabling indirect communication across the grid. Optimal diffusion enhances local coordination between the agents by forming differentiable gradients of pheromone levels between cells, whereas excessive diffusion may dilute spatial cues by narrowing this gradient. During testing, all other parameters such as grid size, initial task distribution, agent count, Point-Poisson spawn rate are held constant to isolate the effects of decay and diffusion on the emergent behavior.
The function evaluatePheromoneParams runs multiple simulations to evaluate how different pheromone decay and diffusion values affect task completion. It loops over all combinations of decay and diffusion values, running each setting multiple times. For each run, it resets the simulation, runs it, and tracks performance metrics like steps taken, tasks completed, and tasks remaining. The function returns a list of average results, with 5 tries taken for each parameter combination, to ensure accuracy by minimizing the impact of stochastic variability. It is used for comparing the average steps taken based on the decay rate and diffusion amount for a graph plotted later.
resetSimulationGlobals resets all global variables to prevent tests effecting each other while GenerateIntitialState randomly generates a state ensuring fairness of experiment. The parameters tk and rb defined in the Module of the code block represent tasks and robots respectively, and can be changed by the user.
A starting configuration of 10 tasks and 8 agents were chosen to maintain a slight task-to-agent imbalance, ensuring sufficient interaction and competition among agents to better observe emergent coordination dynamics, with a large enough number of agents, while keeping it computationally smooth This also creates a manageable yet challenging task load, where the number of tasks slightly exceeds the number of agents to encourage dynamic task allocation and prevent trivial saturation, where the agents complete the tasks in the first few steps. while also ensuring that in most cases, agents can complete the task within the 400 defined steps.
Throughout this research, the average number of steps has been taken as the parameter to measure efficiency and other metrics . A lesser number of steps signifies a stronger algorithm as it shows how tasks were completed faster and with more optimal algorithmic behaviour, which led to all tasks spawned on the grid to be completed faster:
Plotting the Graph
Plotting the Graph
The behaviour between decay rate, diffusion amount and how they impact the average steps taken in order for tasks to be completed, can be visualised using the 3-Dimensional graph below.
The following block of code replaces each association with a list containing only 3 values, ignoring other keys, finally returning a list of triplets. The rule delayed ensures the RHS is evaluated correctly, by matching the associations
A uniform grid is used in evaluatePheromoneParams to systematically test combinations of decay rate and diffusion amount across evenly spaced values. This ensures consistent coverage of the parameters across the range of 0 to 1 , helping identify trends and optimal settings for pheromone behavior.
In this data, a broader range has been utilised to build upon and identify a more specific range or clusters where the optimal decay values and diffusion may be, based on graphing these 2 dependent variables against the average number of steps.
The following block of code replaces each association with a list containing only 3 values, ignoring other keys, finally returning a list of triplets. The rule delayed ensures the RHS is evaluated correctly, by matching the associations
A uniform grid is used in evaluatePheromoneParams to systematically test combinations of decay rate and diffusion amount across evenly spaced values. This ensures consistent coverage of the parameters across the range of 0 to 1 , helping identify trends and optimal settings for pheromone behavior.
In this data, a broader range has been utilised to build upon and identify a more specific range or clusters where the optimal decay values and diffusion may be, based on graphing these 2 dependent variables against the average number of steps.
This Graphics3D visualization plots key data points in 3D space, showing how decay rate, diffusion amount, and average steps interact in the model. Each point is labeled with its coordinates to aid interpretation of optimal parameter combinations.
The decay rate and diffusion amount are compared together as they are interdependent on each other since both parameters directly influence pheromone strength and spread across the grid.
The decay rate and diffusion amount are compared together as they are interdependent on each other since both parameters directly influence pheromone strength and spread across the grid.
Below, a quadratic fit has been plotted on the data, to show a general trend of values by modelling it through a equation:
A weak correlation can be observed in the graph; A strong positive gradient was observed in the study by D.Lima and G.Oliveira et al. with a optimal decay rate of 0.01 and diffusion of 0.25 in the static task allocation paper.
Thus, it can be inferred that we should use search for optimal values of decay and diffusion from a more specific range of lower decay values and diffusion values as large values are giving less optimal answers, as shown by the quadratic best fit below and the graph’s upward sloping tend above
The selected decay and diffusion values form a uniformly spaced grid and capture subtle variations in system behavior due to the small intervals and large number of values. This allows for a more precise identification of optimal parameter combinations affecting pheromone efficiency.
Associations are used to store each simulation’s decay, diffusion, and average steps clearly as key-value pairs, making data extraction structured and efficient. These will be used later to compute efficiency of different parameter combinations:
Convergence
Convergence
To identify optimal parameters, we need to find pairs of values of diffusion amounts and decay rates with the lowest average steps,.This line selects the 3 parameter combinations from correctDataPoints that have the smallest average steps, helping identify the best parameters as a measure of convergence, which is defined as a time to reach a stable state, where all tasks have been completed; this has been identified as the most accurate measure of the success of a model.
This operation assumes structure structure his assumes structure decay, diffusion, AvgSteps. Lower average steps indicate more efficient performance, with the first pair (0.0225, 0.1) showing the best efficiency and the other 2 showing the 2nd and 3rd best efficiency of all the pairs of decay and diffusion that were run;.
Thus, the most optimal parameter pair identified during 2D Dynamic Task Allocation for the emergent behaviour is a decay value of 0.0225, and a diffusion value of 0.1. The decay value of the 3rd most efficient parameter is 0.02 which is very similar to 0.0225 too, reinforcing and validating this parameter range for decay values; A decay rate of 0.0225 is greater than the optimal decay rate of 0.01 that was found in the previous study using a model with static task allocation, reflecting the need for increased decay to enforce more exploration and acknowledge the possibility of a task appearing randomly in a visited cell
Thus, the most optimal parameter pair identified during 2D Dynamic Task Allocation for the emergent behaviour is a decay value of 0.0225, and a diffusion value of 0.1. The decay value of the 3rd most efficient parameter is 0.02 which is very similar to 0.0225 too, reinforcing and validating this parameter range for decay values; A decay rate of 0.0225 is greater than the optimal decay rate of 0.01 that was found in the previous study using a model with static task allocation, reflecting the need for increased decay to enforce more exploration and acknowledge the possibility of a task appearing randomly in a visited cell
This line generates a contour plot of AvgSteps over decay and diffusion parameters using a temperature - based color gradient and labeled axes to keep average steps and diffusion in 2 - dimensions with steps shown by the intensity of the colour:
Efficiency
Efficiency
This code quantifies efficiency as the ratio of average tasks completed to average steps taken (AvgCompleted/AvgSteps). It appends this efficiency score to each data point and identifies the top 3 most efficient parameter sets, highlighting which decay and diffusion values yield the most task completions per unit of effort. However, this metric is not as accurate as a measure of convergence, because over time, if agents fail to effectively navigate and find tasks, those tasks may begin to agglomerate. As a result, they could be completed in quick succession at later steps, inflating the efficiency score despite poor initial performance.
We can observe that the most optimal value of decay is once again in the parameter range of between 0.02 and 0.0225 observed when measuring convergence .
This code fits and visualizes a linear model of AvgSteps against Decay, overlaying the data points and a linear best-fit line:
A weak correlation has been observed currently, which makes the graph inconclusive. By changing a larger number of parameters at once and with more computations, an optimal decay rate could be identified. But, this was too computationally intensive for this project.
This graph compares the diffusion values against the number of steps taken:
The same inconclusive result was observed.
The code below calculates the ratio of decay to diffusion from correctDataPoints, fits a linear model to these ratios against steps, and then plots the data points in orange with the linear fit overlaid in blue. The plot is labeled “Decay/Diffusion Ratio vs Steps” with axes for “Decay/Diffusion” and “Steps”:
This plot shows a linear model fitted to the relationship between the Decay/Diffusion ratio and the number of steps, suggesting a slight negative trend. The correlation is weak but present, indicating that as the ratio increases, the number of steps tends to decrease slightly.
Correlations of the 2D static model can be observed in greater detail with more computations during future research.
Correlations of the 2D static model can be observed in greater detail with more computations during future research.
Testing & finding the optimal location for a nest
Testing & finding the optimal location for a nest
Nests will be assumed to be at the last row, simulating real-world like conditions of a depositing state at the perimeter, to mimic a more fair and a logical environment
To determine the optimal nest placement, the evaluateNestLocations[] function systematically tests different vertical positions while holding the column fixed; In a 2D grid, it does not matter if we are varying the columns or the rows while keeping the others fixed, since the only condition is to keep the nest on the perimeter typically to simulate real-world likeliness of such a point. For each nest location, the simulation records key performance metrics such as the number of steps taken, tasks completed, and remaining tasks. By repeating this process multiple times and averaging the results, allong with generating random states using generateInitialState, the analysis reduces randomness and reveals which nest positions yield the highest efficiency.
To determine the optimal nest placement, the evaluateNestLocations[] function systematically tests different vertical positions while holding the column fixed; In a 2D grid, it does not matter if we are varying the columns or the rows while keeping the others fixed, since the only condition is to keep the nest on the perimeter typically to simulate real-world likeliness of such a point. For each nest location, the simulation records key performance metrics such as the number of steps taken, tasks completed, and remaining tasks. By repeating this process multiple times and averaging the results, allong with generating random states using generateInitialState, the analysis reduces randomness and reveals which nest positions yield the highest efficiency.
These lines extract the “Steps” and “Completed” data from each simulation run and organize them into matrices. By transposing and averaging across runs, they compute the mean performance for each nest location correctly, reducing the effect of randomness.
The graph shows no apparent trend showing a optimal location for the placement of a nest on the perimeter. Most points on this graph are clustered over similar average total step levels; This represents the robustness of the ant memory model for emergent behaviour of robot swarms; However, there are 2 points that are anomalous to this trend, representing the ability to further tune the model’s parameters in future research with more heavy computations.
Visualisation of the Robot’s Simulation running over the 2D Grid with a dynamic animation
Visualisation of the Robot’s Simulation running over the 2D Grid with a dynamic animation
The pheromone minimum and maximum have been used in order to set hue values ; I am changing the saturation of the Hue based on the Pheromone levels
The following block of code resets and standardizes all variables at the beginning. Then, a user is provided a choice between providing user input and randomly generating a state based on the number of robots and tasks; The number of tasks and number of robots can be parsed in generateInitialState in order to generate a randomised start state based on the constraints.The format is [Number of tasks, Number of robots]
The algorithm can be modelled and visualised over a 2-Dimensional grid to observe patterns of robot behaviour and the emergent coordination based on pheromone levels. Effective visualization is crucial for assessing the emergent behaviour and dynamic task allocation, and understanding complex agent interactions in the simulation through the algorithm. Broadly, it can be used for supporting user modeling by providing intuitive, real-time insight into agent interactions and system dynamics. This enables users to better understand, interpret, and potentially adjust parameters to influence swarm performance, making the simulation a valuable tool for both analysis and decision-making.
To achieve this, the code computes global minimum and maximum pheromone values (pheromoneMin and pheromoneMax) from the simulation history to normalize pheromone intensity across the grid. A Manipulate interface then animates the robot swarm’s progression step-by-step, using distinct colors to represent agent states and a scaled hue gradient to depict pheromone concentrations at varied steps. This combined visual encoding enables simultaneous tracking of agent behavior and chemical signaling. Interactive controls allow detailed examination of spatial-temporal dynamics, providing valuable insights into how local interactions lead to global coordination. Such visualization is essential for validating model performance and interpreting emergent swarm behavior.
To achieve this, the code computes global minimum and maximum pheromone values (pheromoneMin and pheromoneMax) from the simulation history to normalize pheromone intensity across the grid. A Manipulate interface then animates the robot swarm’s progression step-by-step, using distinct colors to represent agent states and a scaled hue gradient to depict pheromone concentrations at varied steps. This combined visual encoding enables simultaneous tracking of agent behavior and chemical signaling. Interactive controls allow detailed examination of spatial-temporal dynamics, providing valuable insights into how local interactions lead to global coordination. Such visualization is essential for validating model performance and interpreting emergent swarm behavior.
Implementing the algorithm in 3-Dimensions
Implementing the algorithm in 3-Dimensions
In this section, the same idea of Emergent behaviour is applied to a 3-Dimensional Grid / Cube. Instead of observing the state of the 8 neighbours around it in it’s Moore neighbourhood, the agent and it’s behaviour is now determined by a 3-Dimensional Moore neighbourhood comprising of 26 cells and the current cell.
The meaning of all the parameters remains the same in 3D as the 2D Grid; historyStates3D & historyPheromone3D is now a 4-Dimensional list storing all the states and pheromone levels over all the steps. The 2-Dimensional arrays storing the current state at that step have also been converted to 3D lists. The global row, column and depth in 3D are each taken as 4 as large values require a very great computational power
The meaning of all the parameters remains the same in 3D as the 2D Grid; historyStates3D & historyPheromone3D is now a 4-Dimensional list storing all the states and pheromone levels over all the steps. The 2-Dimensional arrays storing the current state at that step have also been converted to 3D lists. The global row, column and depth in 3D are each taken as 4 as large values require a very great computational power
The following shows how the state of cells in the grid are represented in the list:
To enhance spatial complexity and realism, the 2D cellular automata model can be extended into three dimensions, allowing agents to operate across layered environments. This extension would support the simulation of more complex real-world scenarios such as layered terrains or structured environments. This can be applied to autonomous areal drones and autonomous underwater drones where spacial movements occurs across 3-Dimensions. This 3D grid builds on the 2D structure by introducing depth, enabling more sophisticated movement patterns and multi-level coordination, by allowing movement in the z axis too. The step3D function mirrors the logic of the 2D step function, but expands the neighborhood search and pheromone diffusion to 26 adjacent cells in 3D space. It evaluates robot states, selects movement based on local pheromone gradients, and updates task status and memory trails accordingly.
runSimulation3D had the same logic as the 2-Dimensional runSimulation function. The maximum step count has been set as 200 due to the large computational power required by the 3-D list:
The 2D visualization was extended to 3D by applying the same logic slice-by-slice across depth, preserving color-coded agent states and hue-based pheromone intensity based on the pheromone levels. This enables intuitive observation of swarm behavior in volumetric environments:
Developing a 3-Dimensional Simulation
Developing a 3-Dimensional Simulation
We can model this in 3 Dimension by forming cells as cuboids, where tasks are blue, searching robots are orange and homing tasks are red for increased visibility in the 3D structure . We can model the system in three dimensions, where tasks are marked in blue, searching robots in orange, and homing robots in red to enhance visibility within the volumetric grid., as brown for homing state is difficult to observe. The Manipulate interface renders each timestep using Graphics3D, where colored semi-transparent cuboids represent agent states, and pheromone intensity is encoded using a hue brightness gradient scaled between the global minimum and maximum values. Each cuboid is labeled with its respective pheromone value for interpretability. This layered visualization allows users to observe agent coordination and pheromone dynamics in real-time, enabling a clear understanding of how emergent behavior unfolds across 3D space.
Conclusion
Conclusion
This paper advances previous stigmergy-based task allocation research by successfully modeling an interactive, user-friendly simulation interface that allows users to input and modify system states as well as generate random states dynamically during the simulation. Moving beyond prior models confined to static 2D grids, it introduces dynamic task generation using a Multivariate Poisson Distribution and pioneers the application of this algorithm within a 3D grid environment, significantly enhancing both realism and user engagement.
Acknowledgments
Acknowledgments
I would like to express my sincere gratitude to my mentor, Adam Millar, for his invaluable guidance and support throughout the project. I also extend my thanks to the Wolfram Directors for their thoughtful and invaluable feedback and encouragement during every stage of the journey, and for such a enriching program.
Citations
Citations
• Balachandran, A., Harasha, N., & Lynch, N. (2024). Swarm algorithms for dynamic task allocation in unknown environments. Massachusetts Institute of Technology. Retrieved from https://groups.csail.mit.edu/tds/papers/Balachandran/Swarm_Dynamic_Task_Allocation.pdf
• Lima, D. A., & de Oliveira, G. M. B. (2017). A cellular automata ant memory model of foraging in a swarm of robots. Applied Mathematical Modelling, 47, 473–489. https://doi.org/10.1016/j.apm.2017.03.021
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Simulating emergent task allocation with stigmergy in cellular automata-based robot swarms
by Sanat Punj
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3503713
by Sanat Punj
Wolfram Community, STAFF PICKS, July 10, 2025
https://community.wolfram.com/groups/-/m/t/3503713