printacmref=false ifaamas [AAMAS ’23]To appear at the 22nd International
Conference on Autonomous Agents and Multiagent Systems (AAMAS 2023)May 29 –
June 2, 2023 London, United KingdomA. Ricci, W. Yeoh, N. Agmon, B. An (eds.)
2023 2023 1056 MIT Cambridge US MIT Cambridge US MIT Cambridge US

# A Comparison of New Swarm Task Allocation Algorithms in Unknown Environments
with Varying Task Density

Grace Cai<EMAIL_ADDRESS>,  Noble Harasha<EMAIL_ADDRESS>and  Nancy
Lynch<EMAIL_ADDRESS>
###### Abstract.

Task allocation is an important problem for robot swarms to solve, allowing
agents to reduce task completion time by performing tasks in a distributed
fashion. Existing task allocation algorithms often assume prior knowledge of
task location and demand or fail to consider the effects of the geometric
distribution of tasks on the completion time and communication cost of the
algorithms. In this paper, we examine an environment where agents must explore
and discover tasks with positive demand and successfully assign themselves to
complete all such tasks. We first provide a new discrete general model for
modeling swarms. Operating within this theoretical framework, we propose two
new task allocation algorithms for initially unknown environments – one based
on N-site selection and the other on virtual pheromones. We analyze each
algorithm separately and also evaluate the effectiveness of the two algorithms
in dense vs. sparse task distributions. Compared to the Levy walk, which has
been theorized to be optimal for foraging, our virtual pheromone inspired
algorithm is much faster in sparse to medium task densities but is
communication and agent intensive. Our site selection inspired algorithm also
outperforms Levy walk in sparse task densities and is a less resource-
intensive option than our virtual pheromone algorithm for this case. Because
the performance of both algorithms relative to random walk is dependent on
task density, our results shed light on how task density is important in
choosing a task allocation algorithm in initially unknown environments.

###### Key words and phrases:

Task Allocation, Robot Swarms, Geometric Swarm Algorithms

##  1\. Introduction

Robot swarms are simple, distributed units that are able to work together to
achieve emergent collective behaviours Fan et al. (2020). We contribute a
general, theoretical framework to model these swarms, which can be leveraged,
as will be done in this work, to implement various swarm algorithms. Swarm
algorithms often draw inspiration from swarms in nature such as birds, ants,
and bees Pratt (2005b); Reynolds (1987); Karaboga and Akay (2009). Swarm
algorithms provide a scalable and fault-tolerant solution to problems such as
search-and-rescue Couceiro (2017) and environmental monitoring Duarte et al.
(2016). One of the most well-studied swarm problems is task allocation Gerkey
and Matarić (2004), which aims to assign agents to tasks in an optimal manner.
Here, a task refers to an abstract notion; a task is simply a location of
interest in the environment which requires some action(s) by agents. This
could be a food item in foraging, survivors in search-and-rescue, mines for
robots to defuse, and more.

Many classes of task allocation algorithms assume that task locations and
demand for agents are known, and try to optimize an assignment of agents to
tasks Bettinelli et al. (2020); Xu et al. (2015); Berman et al. (2009).
However, in many applications, such as finding and defusing mines Sahin et al.
(2002), task information is not initially known. Algorithms which do consider
task allocation in unknown environments Harwell and Gini (2018); Brutschy et
al. (2014) run limited testing on the effects of task density. However, the
density of tasks in the environment affects relative algorithm performance.

In this paper, we consider the problem of assigning agents to tasks with
positive demand in an initially unknown environment. We assume each agent can
only be assigned to one task. Within this setup, we contribute two new
algorithms and compare them to the Levy Walk (RW), which is used in nature for
foraging Reynolds and Rhodes (2009). We also show how task density makes our
different algorithms better suited towards different task environments.

The first algorithm, our house hunting task allocation algorithm (HHTA), is
inspired by swarm house-hunting models Reina et al. (2015). While the house
hunting problem aims for agents to agree on one of many locations in the
environment, the task allocation problem aims for agents to split themselves
proportionally to task demand amongst all tasks in the environment. In our
HHTA algorithm, agents use their starting location as a home base that they
can return to after discovering tasks in the environment. The home base
functions as a central point of communication and allows for agents to recruit
each other to do tasks, serving the same function as the home nest in many
swarm house hunting algorithms.

The second algorithm is our propagation-based algorithm (PROP), which uses a
regular grid of cheap, simple agents to propagate task demand information
outwards to neighboring propagator agents. We assign a separate type of agent
with more advanced computing powers to read the information and use it to
probabilistically decide which task to head towards. The propagation of task
demand information via cheap agents is inspired by virtual pheromones
Attygalle and Morgan (1985); Barth (2003), a commonly used nature-inspired
technique in swarm algorithms.

By comparing both algorithms to the Levy flight, we show that it is harder for
PROP to do well with very dense tasks, as a large influx of propagated
information can confuse agents. Our other algorithm, HHTA, does worse when
tasks are mid to high density because inter-agent communication about tasks is
not worth it compared to a random walk, which is highly likely to encounter
tasks quickly. However, it does better than RW when tasks are sparse as the
cost of communication about task location is justified when tasks are harder
to find. It is also less resource intensive compared to PROP. We also evaluate
the effects of varying individual parameters within several task densities in
order to better understand our new algorithms.

Our results demonstrate how different task allocation algorithms do well in
environments with different task density and invite further examination on the
performance of other task allocation algorithms in different types of task
environments.

Section 2 provides the inspiration for our two proposed algorithms, explaining
house hunting and virtual pheromones in further depth. Section 3 describes our
general formal model and then dives into the models for our two specific
algorithms. Our simulation results and comparison between the two new
algorithms in sparse and dense task environments can be found in Section 4.
Section 5 discusses our results, and Section 6 concludes the paper and
provides ideas for future work. The full simulation code can be found at
Harasha and Cai (2023).

##  2\. Background

Task allocation is a well studied problem and has been classified into many
subproblems. Per the taxonomy defined in Gerkey and Matarić (2004) our task
allocation problem is of the single-task agents, multi-robot tasks variety,
which means that agents can only do one task at a time, but tasks may require
multiple agents.

When task demands and locations are known, this problem becomes a coalition
formation problem, where we wish to form agents into groups that are best
suited to do each task. This problem can be thought of as a set partitioning
problem Gerkey and Matarić (2004), and adaptations to distributed swarms have
been proposed Bettinelli et al. (2020); Xu et al. (2015).

Other strategies for when tasks are fixed at known locations model tasks as a
graph where agents can travel between edges Berman et al. (2009); Hsieh et al.
(2008); Halász et al. (2007). These algorithms optimize for a flow rate
between edges in the graph so that agents can satisfy all task demands
quickly. Another strategy in this case, based on Optimal Mass Transport
Solomon (2018), is to treat the tasks with demands as sinks and the tasks with
agents as sources in a min cost flow problem. However, both strategies require
prior knowledge of task locations.

Our problem differs from coalition formation and the graph-based task
allocation problems because we are assuming that agents have no initial
knowledge of task location or demands. In this case, we want to discover tasks
and communicate information about them as quick as possible so that agents can
satisfy all task demands.

One solution to task allocation in an environment with unknown tasks is to
have agents form local clusters and run Optimal Mass Transport locally Zhang
et al. (2007). Other task allocation algorithms, such as auction-based
algorithms, perform a similar type of agent clustering to assign tasks Hoeing
et al. (2007). Our two algorithms by contrast are fully distributed and
computationally simple, without the need for grouping to locally run a complex
centralized algorithm. This allows us to save the time needed to form agent
clusters and allows agents to be cheaper to implement due to low computation
cost.

###  2.1. Levy Flight

The Levy flight is a random walk that has been observed in foraging animals
and adapted to swarm algorithms Reynolds and Rhodes (2009); Fujisawa and
Dobata (2013) as well. The Levy Flight has shown to be an optimal forgaing
algorithm, which is very relevant to the situation in which task locations and
demands are unknown. As such, we will be using this random walk as a baseline
to compare against for our two new algorithms.

###  2.2. House Hunting

Several ant species engage in a house-hunting behaviour when their home nest
is destroyed Pratt (2005b, a). First, ants explore nearby for nest sites. If a
site is found, the ant waits a period of time inversely proportional to the
site quality before returning to the home nest to lead others to the new nest.
This process of recruitment is known as forward tandem running (FTR). Once the
encounter rate of other ants in the candidate nest reaches a critical
threshold known as the quorum threshold, ants switch to carrying members of
the colony to the new nest. This carrying behaviour is 3 times faster than FTR
and accelerates the move to the new site Pratt (2005b).

Ant house hunting has inspired the corresponding swarm problem of N-site
selection Valentini et al. (2017), where agents must choose the highest
quality site from N initially unknown candidates. One common N-site selection
model has agents transition between four main states: Uncommitted Interactive,
Uncommitted Latent, Favoring Interactive, and Favoring Latent Reina et al.
(2015). Some works also include a fifth Committed state Khurana and Sofge
(2020); Cody and Adams (2017); Cai and Sofge (2019). In this type of model,
Uncommitted Interactive agents explore the arena for new sites, while
Uncommitted Latent agents stay in the home nest. Once an Uncommitted
Interactive agent discovers a site, it can decide to favor the site. Favoring
agents can be interactive, meaning they return to the home nest to recruit
other favoring agents, or latent, meaning they stay in their favored site to
build up quorum. Lastly, if agents detect a sufficient number of others in a
new candidate site, they can transition into the committed state to finalize
their decision.

Task allocation can be thought of as an extension to the house hunting
problem, where instead of trying to send all agents to one location, we want
to send agents to multiple locations according to the demand at each one. This
idea has been used in Berman Berman et al. (2009) and Halasz’s Halász et al.
(2007) work to develop task allocation algorithms for a known graph of tasks
where agents can traverse along the edges. We extend this idea further by
using inspiration from site selection algorithms to develop our novel HHTA
algorithm, in which, unlike Berman et al. (2009); Halász et al. (2007), task
locations are initially unknown. In HHTA, agents use a home nest which
functions as a location for recruiting other agents to tasks and communicating
with other agents. The four main states of the HHTA algorithm share parallels
to the Uncommitted Interactive, Uncommitted Latent, Favoring Active, and
Committed states described above which are further explained in Section 3.3.

###  2.3. Virtual Pheromones and Potential Fields

Ants leave pheromones in their environment when foraging to guide other ants
to any discovered food sources Attygalle and Morgan (1985). This strategy of
leaving information in the environment has inspired swarms to implement
virtual pheromones (pheromones represented by computational data instead of
chemical signals). For example, Barth (2003) used physically deployable
beacons that robots could leave in the environment to store information in, Lu
et al. (2018) simulated pheromone trails by leveraging depots to store target-
rich locations (pheromone waypoints) found by other robots, and O’hara et al.
(2005) set up a virtual pheromone approach with a pre-deployed network of
beacons that acted as a grid of locations to leave information in. One cheap
way to implement virtual pheromones is using wireless sensor motes to store
and propagate information Russell et al. (2015).

Pheromones are frequently used in conjunction with potential fields or
particle swarm optimization techniques. Potential field algorithms model
objects in the environment as either positive charges or negative charges,
with agents experiencing attraction or repulsion from the objects based on the
electric force between them. Particle swarm optimization Poli et al. (2007)
follows a similar physics approach, except the attractive and repulsive forces
were based on springs as opposed to charges. These techniques are employed in
navigation tasks, where potential fields and pheromones can work together to
guide robots around obstacles and towards a target in space Parunak et al.
(2002). Pheromones are also employed in foraging tasks to help robots
efficiently find what they are foraging for Hoff et al. (2010).

We apply the ideas of virtual pheromones in our novel PROP algorithm, which
uses simple mote-like agents to leave task information in the environment.
Task-performing robots use this information when searching for tasks in the
task allocation process. The use of virtual pheromones allows us to easily
notify task-performing robots of nearby tasks. We also use potential fields as
inspiration for how a robot’s motion should be influenced when it learns of
multiple potential tasks through pheromones in the environment. Robots are
more attracted to tasks with higher demand and tasks that are closer to their
current location, so tasks can be thought of like charges which robots can
feel the force of.

##  3\. Model

We first describe our new discrete general model for modeling swarms. Then we
discuss the individual restrictions, parameters, and agent algorithms needed
for task allocation. Figure 1 is provided as a lookup table for the parameter
notation used in defining this theoretical framework (and our two task
allocation algorithms).

Notation |  Parameter Description
---|---
$M$, $N$ |  Grid dimensions, $M\times N$
$I$ |  Agent influence radius
$\alpha$ |  Agent transition function
$T$ |  Number of tasks
$t_{i}$ |  Task $i$
${t_{i}}^{rd}$ |  Residual demand of $t_{i}$
HHTA |  House hunting task allocation algorithm
PROP |  Task propagation algorithm
RW |  Levy random walk
$P_{c}$ |  Base probability of committing to a task upon arrival (for HHTA)
$P_{e}$ |  Expected fraction of exploring agents (for HHTA)
$r_{m}$ |  Recruiting agents’ message rate (for HHTA)
$\mathcal{M_{T}}$ |  Propagator agent’s known task demand information (for PROP)
$d_{p}$ |  Maximum propagation radius (for PROP)
$r_{p}$ |  Propagation timeout in integer rounds (for PROP)
$L$ |  $1/(M+N)$
Figure 1. Summary table of notation for relevant parameters.

###  3.1. General Model

We assume a finite set $R$ of agents, with a state set $SR$ of potential
states. Agents move on a discrete rectangular grid of size $M\times N$,
formally modelled as directed graph $G=(V,E)$ with $|V|=MN$. Edges are
bidirectional, and we also include a self-loop at each vertex. Vertices are
indexed as $(x,y)$, where $0\leq x\leq M-1$, $0\leq y\leq N-1$. Each vertex
also has a state set $SV$ of potential states.

Local Configurations: A local configuration $C^{\prime}(v)$ captures the
contents of vertex $v$. It is a triple $(sv,myagents,srmap)$, where $sv\in SV$
is the vertex state of $v$, $myagents\subseteq R$ is the set of agents at $v$,
and $srmap:myagents\rightarrow SR$ assigns an agent state to each agent at
$v$.

Local Transitions: The transition of a vertex $v$ may be influenced by the
local configurations of nearby vertices. We define an influence radius $I$,
which is the same for all vertices, to mean that vertex indexed at $(x,y)$ is
influenced by all valid vertices $\\{(a,b)|a\in[x-I,x+I],b\in[y-I,y+I]\\}$,
where $a$ and $b$ are integers. We can use this influence radius to create a
local mapping $M_{v}$ from local coordinates to the neighboring local
configurations. For a vertex $v$ at location $(x,y)$, we produce $M_{v}$ such
that $M_{v}(a,b)\rightarrow C^{\prime}(w)$ where $w$ is the vertex located at
$(x+a,y+b)$ and $-I<a,b<I$. This influence radius is representative of a
sensing and communication radius. Agents can use all information from vertices
within the influence radius to make decisions.

We have a local transition function $\delta$, which maps all the information
associated with a vertex and its influence radius at one time to new
information that can be associated with the vertex and the agents at that
vertex for the following time.

Formally, for a vertex $v$, $\delta$ probabilistically maps $M_{v}$ to a
quadruple of the form $(sv_{1},myagents,srmap_{1},dirmap_{1})$, where
$sv_{1}\in SV$ is the new state of the vertex, $srmap_{1}:myagents\rightarrow
SR$ is the new agent state mapping for agents at the vertex, and
$dirmap_{1}:myagents\rightarrow\\{R,L,U,D,S\\}$ gives directions of motion for
agents currently at the vertex. Note that $R$, $L$, $U$, and $D$ mean right,
left, up, and down respectively, and $S$ means to stay at the vertex. The
local transition function $\delta$ is further broken down into two phases as
follows.

Phase One: Each agent in vertex $v$ uses the same transition function
$\alpha$, which probabilistically maps the agent’s state $sr\in SR$, location
$(x,y)$, and the mapping $M_{v}$ to a new suggested vertex state
$sv^{\prime}$, agent state $sr^{\prime}$, and direction of motion
$d\in\\{R,L,U,D,S\\}$. We can think of $\alpha$ as an agent state machine
model.

Phase Two: Since agents may suggest conflicting new vertex states, a rule $Q$
is used to select one final vertex state. The rule also determines for each
agent whether they may transition to state $sr^{\prime}$ and direction of
motion $d$ or whether they must stay at the same location with original state
$sr$.

Probabilistic Execution:  The system operates by probablistically
transitioning all vertices $v$ for an infinite number of rounds. During each
round, for each vertex $v$, we obtain the mapping $M_{v}$ which contains the
local configurations of all vertices in its influence radius. We then apply
$\delta$ to $M_{v}$ to transition vertex $v$ and all agents at vertex $v$. For
each vertex $v$ we now have $(sv_{v},myagents_{v},srmap_{v},dirmap_{v})$
returned from $\delta$.

For each $v$, we take $dirmap_{v}$, which specifies the direction of motion
for each agent and use it to map all agents to their new vertices. For each
vertex $v$, its new local configuration is just the new vertex state $sv_{v}$,
the new set of agents at the vertex, and the $srmap$ mapping from agents to
their new agent states.

###  3.2. Task Allocation Problem Definition

Consider $T$ tasks $[t_{0}\dots t_{T-1}]$ arranged at a subset of vertices in
our general model, with at most one task at each vertex. Specifically, the
task locations can be described as
$l=[(x_{0},y_{0}),\dots,(x_{T-1},y_{T-1})]$, where $l_{i}=(x_{i},y_{i})$ is
the vertex location of task $t_{i}$ and $i\neq j\rightarrow l_{i}\neq l_{j}$
(each task has a distinct location). We wish to distribute agents among the
tasks to achieve a certain distribution $a=[a_{0},...,a_{T-1}]$ where $a_{i}$
represents the number of agents doing task $i$ and $\sum a_{i}=kR\leq R$
(meaning $k$% of all agents is enough to complete all the tasks).

We assume that when an agent senses a task within its influence radius, it is
able to detect the demand of that task. Since agents can also detect how many
agents are at the task, they can use this information to compute the residual
demand, defined as the difference between the task demand and the number of
agents already at the task. We denote the residual demand at task $i$ by
$t_{i}^{rd}$. We assume that the desired task distribution does not change
over time, and that the task is complex enough that each agent can only do one
task over the course of the algorithm.

In order to properly represent tasks in both of our algorithms, the vertex
state set $SV$ contains the following variables: is_task, whether the vertex
is a task; demand, the task demand if the vertex is a task; residual_demand,
the residual demand if the vertex is a task; task_location, the $x,y$
coordinates of the vertex if it is a task.

We go into more detail on the agent states and transitions for our two
algorithms in Sections 3.3 and 3.4. One other detail to note about task
allocation is that in phase two of $\delta$, we reconcile conflicting proposed
vertex states. This shows up in task allocation when multiple agents attempt
to claim the same task. When this happens, if there are $s$ agents trying to
claim the task but only $rd<s$ residual demand, then only $rd$ agents are
allowed to transition their state to having claimed the task (these $rd$
agents are chosen arbitrarily). Otherwise, if $rd>s$, all agents will be
allowed to claim the task.

###  3.3. House Hunting Task Allocation Algorithm

In our house-hunting inspired algorithm (HHTA), agents start out at a square
home location with lower left corner $(x^{1}_{h},y^{1}_{h})$ and upper right
corner $(x^{2}_{h},y^{2}_{h})$. Call the set of home vertices $\mathcal{H}$.
We assume that $\forall i,l_{i}\notin\mathcal{H}$, meaning no tasks are
located at the home location. In HHTA, the vertex state set $SV$ needs the
additional variable is_home, indicating whether the vertex is a home vertex or
not.

Agents can be in one of four core states: Home (H), Exploring (E), Recruiting
(R), or Committed (C). Home agents wait in home nest for news of tasks.
Exploring agents explore the arena for tasks. Home agents have a
$P_{E}=\frac{L*P_{e}}{1-P_{e}}$ chance of converting to exploring agents, and
exploring agents have a $P_{H}=L$ chance of converting to home agents, where
$L$ is defined as $1/(M+N)$ and $P_{e}$ is the expected fraction of exploring
agents. The transitions between H and E agents indicate that agents are
expected to explore for $M+N$ time steps (enough to reach the corners of the
grid) before returning home. It also ensures that the expected fraction of E
agents out of the total number of E and H agents is $P_{e}$. The factor of $L$
is inspired by house hunting algorithms, where $L$ is defined as the inverse
of the average site round trip so that exploring agents will have enough time
to reach candidate sites before returning home.

An exploring agent has a $P_{t_{i}}$ chance of finding task $i$. Once it finds
task $i$, it has a $c=\max(P_{c},1/t_{i}^{rd})$ chance of becoming a Committed
agent, and a $1-c$ chance of becoming a Recruiting agent. Here $P_{c}$ is the
base probability of committing, and $1/t_{i}^{rd}$ makes it so that at low
residual demands, agents have a higher chance of committing to the task right
away. If a task has residual demand $1$, for instance, any agent which
discovers it will commit to the task right away, completing the task instead
of trying to recruit others for it.

Committed agents have fully committed to a task and stay at that task. The
Committed state is similar to the Committed state in house hunting, where
agents have decided on a new nest site and have moved to it. Recruiting agents
head back to the home nest to tell Home agents about the task they have found.
Agents recruiting for site $i$ have a $1/t_{i}^{rd}$ chance to stop recruiting
and become committed to task $i$. Recruiting agents have a $r_{m}$ chance of
sending a message to each agent within their influence radius at each time
step, where $r_{m}$ is the message rate. Therefore, a Home agent has an
$P_{r_{i}}=I_{1-r_{m}}(R_{t_{i}}-1,2)$ chance of receiving at least one
recruiting message for task $i$. Here, $R_{t_{i}}$ is the number of agents
recruiting for task $i$ that are within sensing radius, and $I$ is the
regularized incomplete beta function. If a Home agent receives a message from
a recruiting agent, it has a $P_{c}$ chance of committing to the task and
heading towards it, and a $1-P_{c}$ chance of recruiting for the task. Note
that the residual demand information for C and R agents may become stale as
more agents commit to tasks. A diagram of the transitions between these core
states can be found in Figure 2.

$H$ $E$ $C_{i}$ $R_{i}$
$P_{E}$$P_{H}$$P_{t_{i}}c$$P_{t_{i}}(1-c)$$P_{r_{i}}$$P_{r_{i}}(1-c)$$1/t_{i}^{rd}$
Figure 2. State model of the four core states. The subscript $i$ denotes that
an agent is recruiting for or committed to task $i$.

In order to execute the core state transitions, the agent state set $SR$
comprises of the following variables: core_state, which can be H, E, R or C;
id, the agent id, taking on values from $0\dots|R|-1$; L, defined as
$L=1/(M+N)$; P_commit, the probability $P_{c}$; P_explore, the probability
$P_{e}$; message_rate, the message rate $r_{m}$; angle, the agent’s current
angle of travel; starting_point, a random walk parameter tracking where the
agent started from; travel_distance, the length of the current leg of the
random walk; destination_task, the agent’s destination if they have just found
a task or are headed towards their committed task; home_destination, the
agent’s destination if they are headed to a home vertex; recruitment_task, the
task an agent is recruiting for; and committed_task, the task an agent has
committed to.

The agent transition function $\alpha$ uses these state variables to implement
the transitions between the four core states.

A pseudocode example of how $\alpha$ looks like for Recruiting agents can be
seen in Algorithm 1. In this example, we first check if the recruiting agent
has reached the home nest to recruit yet. If they have not, they keep heading
towards the home nest by stepping one step in that direction. If they have
reached the home nest, they have a $1/t_{i}^{rd}$ chance of transitioning to
the Committed core state. Otherwise, they remain in the Recruiting state.

Algorithm 1 Agent transition function $\alpha$ for a Recruiting agent with
state $s$ at vertex $v$ with coordinates $(x,y)$

1:procedure generate_transition(local_vertex_mapping)

2: $new\\_agent\\_state\leftarrow s$

3: if $s.\texttt{home\\_destination is not None}$ then

4: $new\\_direction\leftarrow$

5: $\texttt{dir\\_from\\_dest(}s.\texttt{home\\_destination, x, y)}$

6: $new\\_location\leftarrow$

7: $\texttt{coords\\_from\\_dir(x,y,}new\\_direction\texttt{)}$

8: if $\texttt{within\\_home(}new\\_location\texttt{)}$ then

9: $new\\_agent\\_state.\texttt{home\\_destination}\leftarrow\texttt{None}$

10: return $v.\texttt{state}$, $new\\_agent\\_state,new\\_direction$

11: $committed\\_chance\leftarrow$

12: $1/s.\texttt{recruitment\\_task.residual\\_demand}$

13: if $\texttt{random\\_float\\_from(0,1) < }committed\\_chance$ then

14: $new\\_agent\\_state.\texttt{core\\_state}\leftarrow\texttt{Committed}$

15: $new\\_agent\\_state.\texttt{destination\\_task}\leftarrow$

16: $new\\_agent\\_state.\texttt{recruitment\\_task}$

17: $new\\_agent\\_state.\texttt{recruitment\\_task}\leftarrow\texttt{None}$

18: return $v.\texttt{state},new\\_agent\\_state,\texttt{S}$

19: return $self.\texttt{location.state},new\\_agent\\_state,\texttt{S}$

###  3.4. Task Propagation Algorithm

In our task propagation algorithm (PROP), we distinguish between two types of
agents – $MN$ propagators and $F$ followers. Propagators are simple, mote-like
agents. One of them is assigned to each vertex to allow vertices to propagate
task information to each other. Followers are more advanced agents which are
able to perform the tasks in the task allocation problem. Followers follow the
signals left by propogators in order to find tasks.

Similarly to HHTA, all agents are initially deployed at a rectangular home
location with lower left corner $(x^{1}_{h},y^{1}_{h})$ and upper right corner
$(x^{2}_{h},y^{2}_{h})$. However, agents in PROP do not utilize this home
location after starting the algorithm. First, all $MN$ propagators travel to
the vertex which they are assigned to, taking $\frac{M+N}{2}$ time for all
agents to reach their assigned vertex.

Each propagator has an influence radius of 1 and also stores in their state a
mapping $\mathcal{M}_{T}$ from task locations $l_{i}$ to residual demands
$t_{i}^{rd^{\prime}}$, representing that they have heard that task $i$ at
location $l_{i}$ has residual demand $t_{i}^{rd^{\prime}}$. After all
propagators are in place, propagators that are at a task $t_{i}$ spread the
tuple $(t_{i}^{rd^{\prime}},l_{i})$ to all other propagators in their
influence radius. Every $r_{p}$ time steps, a propagator takes all new task
information (if it has new information it did not already propagate) it has
received and spreads that information to all other propagators in its
influence radius with the following conditions: information about task $i$ can
only be spread to agents whose assigned vertex $v$ is located within the
bounds $[x_{i}-I,x_{i}+I]$ for the x coordinate and $[y_{i}-I,y_{i}+I]$ for
the y coordinate, and the Euclidian distance between $t_{i}$ and $v$ must be
less than or equal to $d_{p}$. Here, $r_{p}$ is the integer propagation
timeout and $d_{p}$ is the maximum propagation radius. Figure 3 shows an
example of this propagation process, with propagator agents spreading the
demand information of a single task throughout the graph.

(a) Initial state

(b) Propagator agent at task propagates demand info to its influence radius of
1

(c) $r_{p}$ rounds later

(d) Propagation bounded by $d_{p}$, radius of circle here

(e) No new task demand info to propagate

Figure 3. A simulated example—(a) to (e) chronologically—of how task demand
information is propagated by propagator agents. Each square in the grid is a
vertex, with edges between adjacent squares. Red denotes home vertices, green
vertices have follower agents, the numbered vertex is a task with that value
as its current residual demand, and blue vertices have propagator agents
containing task demand information, with darker blues denoting newer
information.

Because the residual demand of a task changes over time, the propagator at
task $i$ will have to send new information whenever the residual demand
decreases. When a propagator which already has task information
$\mathcal{M_{T}}(l_{i})\rightarrow t_{i}^{rd^{\prime}}$ receives new
information about a task $(t_{i}^{rd^{\prime\prime}},l_{i})$, it updates the
task information for task $i$ to be $\mathcal{M_{T}}(l_{i})\rightarrow
min(t_{i}^{rd^{\prime}},t_{i}^{rd^{\prime\prime}})$ in order to have the most
up-to-date information. Since the residual demand of a task is always
decreasing as more and more agents join the task, we know the smaller residual
demand is the more accurate one.

After all propagators have reached their assigned vertex, followers try to use
the information of propagators in order to find tasks to head towards. At
every time step, a follower first checks the vertices within its influence
radius for a task with non-zero residual demand, and starts moving towards
that task if it exists. If no task is found in its influence radius, a
follower located at $(x,y)$ looks at the propagator assigned to location
$(x,y)$ in order to get information about potential task locations it could
head towards. It compiles all non-zero residual demands into the resulting
mapping $M_{F}$, which maps from task locations $l_{i}$ to residual demands
$t_{i}^{rd^{\prime}}$. If $M_{F}$ is non-empty (there is at least one task
location with non-zero residual demand) then the probability that a follower
located at $(x,y)$ heads towards task location $l_{i}\in M_{F}$ is:

$\frac{\frac{M_{F}(l_{i})}{L_{2}(l_{i},(x,y))^{2}}}{\sum\limits_{l_{j}\in
D(M_{F})}\frac{M_{F}(l_{j})}{L_{2}(l_{j},(x,y))^{2}}}$ (1)

This means that the probability of a follower heading towards a task has an
inverse square relationship with $L_{2}$ distance between the task location
and the agent’s location, and is also weighted by the residual demand of the
task itself. This equation is determined so that agents are less likely to
travel to tasks that are further away from them, but more likely to travel to
a task if it has higher residual demand. If the mapping $M_{F}$ is empty (the
agent has no task information), it takes a random step in one direction
$\\{L,D,R,U\\}$ (following a Levy flight random walk) in order to explore.

Once a follower agent reaches a task with non-zero residual demand, it stays
there indefinitely, ”completing the task” and decrementing the task’s residual
demand by one.

In order to execute the algorithm, the agent state set contains the following
variables: type, the type of agent, which can be ‘propagator’ or ‘follower’
and id, the agent id, which takes on values from $0\dots|MN+F|-1$. The
following additional variables are in SR and are only used by propagator
agents: task_info, the mapping $\mathcal{M_{T}}$; propagation_rate, the
propagation timeout $r_{p}$; and propagation_ctr, the number of rounds since
an agent last propagated task information. Lastly, the variables in SR used
only by follower agents are: destination_task, the agent’s destination if they
have just found a task or are headed towards their committed task;
committed_task, the task an agent has committed to; angle, a random walk
parameter denoting angle of travel; starting_point, a random walk parameter
tracking where the agent started from; and travel_distance, the length of the
current leg of the random walk.

The agent transition functions $\alpha$ for propagator and follower agents,
respectively, use these state variables to implement the desired transitions
at each time step. The pseudocode for $\alpha$ for propogator and follower
agents can be found in Algorithms 2 and 3, respectively. The following
functions (already described in the steps of PROP) are referenced in the
pseudocode: propagate(), the propagator spreads its newest task information
$\mathcal{M_{T}}$ to the other propagators in its influence radius;
find_nearby_task(), the follower looks at the vertices in its influence radius
for a task with nonzero residual demand; dir_from_propagator(), the follower
looks at the task information $\mathcal{M_{T}}$ of the propagator at its
current vertex, chooses a task according to the probabilities defined earlier,
and returns the direction towards that task, or, if $\mathcal{M_{T}}$ is empty
or zero, returns a random direction.

Algorithm 2 Agent transition function $\alpha$ for a propagator agent with
state $s$ at vertex $v$ with coordinates $(x,y)$

1:procedure generate_transition(local_vertex_mapping)

2: $new\\_agent\\_state\leftarrow s$

3: if $v.\texttt{state.is\\_task}$ then

4: $new\\_agent\\_state.\texttt{task\\_info}[(x,y)]\leftarrow$

5: $v.\texttt{state.residual\\_demand}$

6: if $s.\texttt{propagation\\_ctr}\geq s.\texttt{propagation\\_rate}$ then

7: $self.\texttt{propagate()}$

8: $new\\_agent\\_state.\texttt{propagation\\_ctr}\leftarrow 0$

9: else

10: $new\\_agent\\_state.\texttt{propagation\\_ctr}\leftarrow$

11: $new\\_agent\\_state.\texttt{propagation\\_ctr}+1$

12: return $v.\texttt{state},new\\_agent\\_state,\texttt{S}$

Algorithm 3 Agent transition function $\alpha$ for a follower agent with state
$s$ at vertex $v$ with coordinates $(x,y)$

1:procedure generate_transition(local_vertex_mapping)

2: $new\\_agent\\_state\leftarrow s$

3: if $s.\texttt{committed\\_task is None}$ then

4: if $s.\texttt{destination\\_task is None}$ then

5: if $self.\texttt{find\\_nearby\\_task() is not None}$ then

6: $new\\_agent\\_state.\texttt{destination\\_task}\leftarrow$

7: $self.\texttt{find\\_nearby\\_task()}$

8: return $v.\texttt{state},new\\_agent\\_state,\texttt{S}$

9: else

10: return $v.\texttt{state},new\\_agent\\_state,$

11: $self.\texttt{dir\\_from\\_propagator()}$

12: else

13: $\textbf{if }s.\texttt{destination\\_task.state.residual\\_demand }$

14: $\texttt{is }0\textbf{ then}$

15: $new\\_agent\\_state.\texttt{destination\\_task}\leftarrow\texttt{None}$

16: return $v.\texttt{state},new\\_agent\\_state,\texttt{S}$

17: if $s.\texttt{destination\\_task}\texttt{ is }v$ then

18: $new\\_agent\\_state.\texttt{committed\\_task}\leftarrow$

19: $s.\texttt{destination\\_task}$

20: $new\\_agent\\_state.\texttt{destination\\_task}\leftarrow\texttt{None}$

21: $new\\_vertex\\_state\leftarrow v.\texttt{state}$

22: $new\\_vertex\\_state.\texttt{residual\\_demand}\leftarrow$

23: $new\\_vertex\\_state.\texttt{residual\\_demand}-1$

24: return $new\\_vertex\\_state,new\\_agent\\_state,\texttt{S}$

25: else

26: return $v.\texttt{state},new\\_agent\\_state,$

27: $self.\texttt{dir\\_from\\_dest(}s.\texttt{destination\\_task,}$

28: x, y)

29: else

30: return $v.\texttt{state},new\\_agent\\_state,\texttt{S}$

##  4\. Results

Our algorithms were tested in simulation Harasha and Cai (2023) using Pygame
(see Figure 3) on a grid of size $M=N=50$, with a $3\times 3$ home area in the
center of the grid. Each vertex had an area of $1\text{cm}^{2}$, meaning that
agents moved at $1\text{cm/s}$ (letting time be discretized by $1$s), a speed
which simple, low-cost robots are able to move at Rubenstein et al. (2012).
All simulations were run using $100$ task-performing agents—this resulting
swarm density was chosen to allow for feasible task discovery time,
particularly in the case of RW—and the total task demand summed to $80$. In
the trials for the HHTA algorithm, agents had an influence radius of 2. In the
trials for the PROP algorithm, propagators had an influence radius of 1 and
followers had an influence radius of 2. These smaller influence radii were
chosen to keep the algorithms more local.

For each set of trials, we evaluated task completion time, defined as the time
necessary for the total residual demand to become $0$. In subsections 4.1 and
4.2, we also measure the average number of messages sent per run per agent.
For the HHTA algorithm, whenever a Home agent is notified of a task by a
Recruiting agent, the Recruiting agent’s message count is incremented. For the
PROP algorithm, the message count is incremented when a propagator shares new
task information with one of its neighbors. We do not track the message count
for follower agents since it is a negligible portion of total messages.

###  4.1. Effects of Task Density on HHTA Performance

Figure 4. The effect of number of tasks on completion time for HHTA and RW
Figure 5. The effect of number of tasks on average messages sent per agent for
HHTA

To examine the effects of task density on the HHTA algorithm’s performance, we
measured task completion time and average number of messages sent per agent
for $T\in\\{2,3,4,5,6,7,8,9,10,20,30\\}$. For each value of $T$ (the number of
tasks), we ran 100 trials with $r_{m}=\frac{1}{6}$,
$P_{e}=\frac{2}{3},P_{c}=\frac{3}{10}$. Figure 4 shows the resulting average
task completion time for varying task densities. The HHTA algorithm
outperforms the random walk by about 100 rounds in very sparse task setups
when $T\leq 6$ and performs comparably when $7\leq T\leq 10$, but for denser
task setups, the cost of returning to the home nest to recruit others is too
high compared to the random walk (Welch’s T-test, p=0.05). We can approximate
the area covered by detectable tasks as $\frac{T(2I+1)^{2}}{NM}$, where
$(2I+1)^{2}$ is the size of the influence radius (in reality, the ratio would
be a bit smaller as the detectable range for tasks can intersect). This means
that for our choice of parameters, the HHTA algorithm outperforms the random
walk when about $6\%$ or less of the total task area has an immediately
detectable task.

Figure 5 shows the average number of messages sent per agent for the HHTA
algorithm. (Note that the random walk algorithm uses no communication). Note
that on average, each agent sends less than $1.2$ messages per round using
HHTA. Note also that agents send less messages on average as density
increases. Since the total task demand is fixed at 80, a larger number of
tasks indicates less demand per task on average, making agents in the HHTA
algorithm less likely to enter the task state (where messages are sent) and
remain in it.

###  4.2. Effects of Task Density on PROP Performance

To examine the effects of task density on the PROP algorithm’s performance, we
once again measured task completion time and average number of messages sent
per propagator agent for
$T\in\\{1,2,4,6,8,10,12,14,16,18,20,25,30,35,40,50,60,70,80\\}$. For each
value of $T$ (the number of tasks), we ran 20 trials with $r_{p}=3$ and
$d_{p}=25$. Figure 6 shows the resulting average task completion time for
varying task densities. The PROP algorithm outperforms the random walk
significantly (Welch’s T-test, p=0.05) in sparser task setups ($T\in[1,25]$),
with fewer tasks exaggerating this performance gap nonlinearly. In moderately
dense task setups ($T\in[30,60]$), the two algorithms’ runtimes are
comparable, and in our most dense task setups ($T\in[70,80]$), the random walk
begins to increasingly outperform the PROP algorithm to a significant extent
(Welch’s T-test, p=0.05). Intuitively, as the density of tasks in the
environment increases, follower agents are more likely to find tasks in their
influence radius (benefiting RW). Conversely, more tasks means more task
information within each propagator agent, overloading and misguiding the
follower agents during their decision process (harming PROP). After a certain
point, too much propagated information results in that information declining
in its specificity and thus usefulness.

Figure 7 shows the average number of messages sent per propagator agent per
round (for the PROP algorithm). Note that on average, each propagator agent
sends less than 1.3 messages to other agents per round; however, given the
grid space’s size, a large communication cost is still incurred as there are
$2,500$ propagator agents. Regarding the effect of task density on these
communication costs, agents generally send more messages as the number of
tasks increases. When there are more tasks and thus more vertices close to
tasks, it takes less time for most of the propagator agents to receive some
information initially that they can begin propagating. Additionally, having
more tasks means that some task’s demand gets updated more often, resulting in
there being new information (as messages) that needs to be propagated more
often. This increasing trend becomes less dramatic at higher task densities,
likely due to the fact that with enough tasks, the overlapping propagation
radii all cover roughly the same area. As shown in Figure 6, recall that
higher task densities result in higher completion times for the PROP
algorithm. Therefore, higher task densities do not only result in agents
sending more messages per round, but the total number of messages sent over an
entire run increases even more dramatically along with the number of tasks.

Figure 6. The effect of number of tasks on completion time for PROP and RW
Figure 7. The effect of number of tasks on average messages sent per
propagator agent per round (for PROP)

###  4.3. Effects of $P_{c}$ on HHTA Completion Time for Varying Task Density

We explored the effects of varying $P_{c}$ on completion time for varying $T$.
We ran 100 trials for each value of $P_{c}\in\\{\frac{i}{10},0\leq i\leq 9\\}$
using $r_{m}=\frac{1}{6}$ and $P_{e}=\frac{2}{3}$. The results can be seen in
Figure 8.

For $P_{c}\leq 0.7$, there was no significant difference between the HHTA
completion time at different task densities (Welch’s T-test, p=0.05). However,
for $P_{c}\in\\{0.8,0.9\\}$, the completion time for $T=4$ is higher than the
completion time for $T=16$ (Welch’s T-test, p=0.05). Our results show that
only for large $P_{c}$ do we see a significant difference in performance at
different task densities. This makes sense, as a larger proportion of
committing agents means agents mostly find tasks by discovering them
independently, which is harder in the sparse case. We also note that from
$P_{c}=0.4$ to $P_{c}=0.8$, task completion time follows an increasing trend,
indicating that higher recruitment (lower $P_{c}$) allows agents to complete
tasks faster.

Figure 8. The effect of $P_{c}$ on HHTA completion time for $\\{4,10,16\\}$
tasks

###  4.4. Effects of $P_{e}$ on HHTA Completion Time for Varying Task Density

We also explored varying $P_{e}$, running 100 trials each for
$P_{e}\in\\{\frac{i}{10},1\leq i\leq 10\\}$, with $T\in{4,10,16}$ and using
$r_{m}=\frac{1}{6}$ and $P_{c}=\frac{3}{10}$. The results can be seen in
Figure 9.

For $P_{e}\leq 0.8$, there was no significant difference between the HHTA
completion time at different task densities (Welch’s T-test, p=0.05) with the
exception of $T=10$ vs. $T=4$ at $P_{e}=0.2$, with $p=0.03$. However, there
was a significant difference in completion time between $T=4$ and $T=16$ when
$P_{e}=1.0$ and $P_{e}=0.9$. Our results show that HHTA has a consistent
completion time regardless of task density other than for large
$P_{e}\in\\{0.9,1.0\\}$, meaning a large majority of agents are exploring
(making the algorithm more similar to random walk). When $P_{e}$ is high, it
is harder to complete the sparse problem because exploring is harder in a
sparse environment.

Our results also show that a more even balance of $P_{e}$ (the proportion of
Exploring agents) vs. $1-P_{e}$ (the proportion of Home agents) leads to a
faster completion time. When $P_{e}$ is too low, not enough agents are
exploring, making it harder to find tasks. When $P_{e}$ is too high, not
enough agents are available in the home nest to be recruited when tasks are
found.

Figure 9. The effect of $P_{e}$ on HHTA completion time for $\\{4,10,16\\}$
tasks

###  4.5. Effects of $d_{p}$ on PROP Completion Time for Varying Task Density

We explored the effects of varying $d_{p}$, the maximum propagation radius, on
completion time for varying $T$. We ran 20 trials for each unique pair of
$d_{p}\in\\{0,5,10,15,20,25,30,40,50,60,50\sqrt{2}\\}$ (note that $d_{p}=0$ is
equivalent to RW, and $d_{p}=50\sqrt{2}$ means all tasks’ information can be
propagated over the entire grid space) and $T\in\\{4,10,16,50\\}$, using
$r_{p}=3$. The results can be seen in Figure 10.

For reasonably sparse task setups ($T\in\\{4,10,16\\}$), larger maximum
propagation radii correlate with faster runtimes (Welch’s T-test, p=0.05) but
after a certain point, completion time is mostly unchanged. In contrast, for
very dense task setups ($T=50$), besides a slight improvement in completion
time moving from around $d_{p}=0$ to $d_{p}=10$, larger maximum propagation
radii result in slower completion times (Welch’s T-test, p=0.05). Increasing
$d_{p}$ results in more propagator agents having more task information, which
allows (1) for follower agents to find tasks even if they are far way and (2)
for follower agents to leverage this extra task information to prioritize
tasks with higher demand. This causes the initial decline in completion time
for increasing $d_{p}$ values. However, if $d_{p}$ is too large, there is too
much information being propagated, diluting the agents’ strategy. This adverse
effect is likely not seen with sparser environments because even with every
single propagator having information about every single task, each mapping of
task info is still bounded in size by this smaller number of tasks. It is also
reasonable to infer that the turning point in each plot’s trend (when
completion time either becomes constant or starts increasing) is related to
the $d_{p}$ value at which every propagator agent receives some task
information.

###  4.6. Effects of $r_{p}$ on PROP Completion Time for Varying Task Density

We explored the effects of varying $r_{p}$, the number of rounds a propagator
must wait before sharing new task information with its neighbors, on
completion time for varying T. We ran 20 trials for each unique pair of
$r_{p}\in\\{1,2,3,5,10,15,20\\}$ and $T\in\\{4,10,16\\}$, using $d_{p}=25$.
The results can be seen in Figure 11.

There is a clear, mostly linear trend between $r_{p}$ and completion time,
where increasing the propagation timeout results in increasing completion
times. The trend is fairly consistent across all distinct task densities that
were tested. This relationship between $r_{p}$ and completion time is to be
expected, as smaller $r_{p}$ means that task information is moved about the
environment more quickly, causing the information that is used by follower
agents to decide which task to move towards to be more up-to-date. Besides at
the very beginning, $r_{p}$ has no effect on the locations of task
information, so none of the adverse phenomena we have seen in which there is
“too much” propagated information occur when varying $r_{p}$. It is the same
task information, simply better when when the timeout is smaller. It is worth
noting, though, that smaller values of $r_{p}$ involve more message passing.

Figure 10. The effect of maximum propagation radius ($d_{p}$) on PROP
completion time for $\\{4,10,16,50\\}$ tasks Figure 11. The effect of integer
propagation timeout ($r_{p}$) on PROP completion time for $\\{4,10,16\\}$
tasks

##  5\. Discussion

Our results demonstrate for both HHTA and PROP that when the total demand for
agents is held fixed, task density significantly affects algorithm
performance. HHTA performs better than RW when tasks are very sparse, and
worse when the number of tasks is high because communicating about individual
tasks matters less when there are many of them. RW performs very poorly with
sparse tasks because it becomes harder over time for the remaining agents to
find tasks. PROP also performs better than RW until the number of tasks is
very high, as agents struggle to arrive at tasks when too much task
information is being propagated. Though it outperforms RW for sparse tasks,
PROP’s completion time increases for very sparse tasks ($T\leq 6$). PROP also
has a faster completion time and is more distributed than HHTA, but is much
more resource and communication intensive, as it requires a propagator agent
at every grid cell in order to spread information.

In relevant task allocation problems such as search-and-rescue or mine
detection, the number of tasks in the environment is expected to be sparse, so
both algorithms provide a speed-up in completion time compared to the Levy
walk. HHTA provides a less agent intensive and less communication intensive
approach but requires a central communication location. Contrarily, PROP
provides a quicker and more distributed approach for sparse and mid-density
environments but is more resource-intensive. Since the Levy flight has been
shown to optimize search efficiency and can be observed in many species in
nature, it makes sense that for very dense task environments with a low demand
per task, the Levy flight outperforms both algorithms. Such environments are a
very similar problem to foraging itself. On the other hand, environments with
fewer tasks that require more agents benefit more from the coordination and
communication of more advanced algorithms.

We also analyzed both algorithms’ mechanics individually, showing the
importance of recruitment in HHTA as well as the importance of an even balance
of Exploring vs. Home agents. For PROP, we showed as expected that generally,
higher $d_{p}$ leads to better performance, though it is more communication-
intensive. We also showed that as propagation timeout increases, time to
completion increases, since task demands are stale for longer periods of time.

We also note that in extreme parameter settings, HHTA completion time was
similar regardless of task density while varying algorithm parameters like
$P_{c}$ and $P_{e}$. However, this is untrue for PROP, which had a higher
completion time for sparser environments at low $d_{p}$, and a higher
completion time for denser environments at high $d_{p}$. This behavior makes
sense because as $d_{p}$ approaches $0$, PROP reduces to RW, which is
similarly affected with a higher completion time for sparse tasks.

##  6\. Future Work

Future work could explore experiments in a dynamic setting, where new tasks
can appear over time and agents can search for a new task after their existing
task is finished. It could also evaluate other environment parameters, such as
the ratio of total task demand to total number of agents. A larger such ratio
would make the task allocation problem harder to solve, as there are less and
less extra agents available to communicate. Another parameter left to be
analyzed is swarm density; that is, the ratio of total number of agents to
grid size ($M\times N$).

Future work could also combine the strengths of the PROP and HHTA algorithms,
where one agent for each task is assigned to propagate by leaving information
in the vertex state of nearby vertices or communicating task information
directly to any nearby agents like HHTA does. This algorithm would have a much
smaller agent cost than the PROP algorithm while still being able to propagate
task information. It would also not require a central home nest like the HHTA
algorithm does, instead opting to induce agent communication all around the
arena.

Future work could also aim for analytical bounds on the expected task
completion time of our two algorithms. Because the algorithms are relatively
simple compared to many swarm algorithms, high probability bounds may be
possible to obtain.

Lastly, future work could extend our algorithms to the continuous 2D as well
as 3D (discrete and continuous) settings, adaptations which our presented
theoretical framework is amenable to.

Special thanks to Andrea Richa for her insights on the task allocation
problem.

## References

  * (1)
  * Attygalle and Morgan (1985) Athula B Attygalle and E David Morgan. 1985.  Ant trail pheromones.  In _Advances in insect physiology_. Vol. 18. Elsevier, 1–30.
  * Barth (2003) Eric J Barth. 2003\.  A dynamic programming approach to robotic swarm navigation using relay markers. In _Proceedings of the 2003 American Control Conference, 2003._ , Vol. 6. IEEE, 5264–5269.
  * Berman et al. (2009) Spring Berman, Adám Halász, M Ani Hsieh, and Vijay Kumar. 2009.  Optimized stochastic policies for task allocation in swarms of robots.  _IEEE transactions on robotics_ 25, 4 (2009), 927–937.
  * Bettinelli et al. (2020) Mickaël Bettinelli, Michel Occello, and Damien Genthial. 2020\.  Coalition formation problem: a group dynamics inspired swarming method. In _International Conference on Swarm Intelligence_. Springer, 282–289.
  * Brutschy et al. (2014) Arne Brutschy, Giovanni Pini, Carlo Pinciroli, Mauro Birattari, and Marco Dorigo. 2014.  Self-organized task allocation to sequentially interdependent tasks in swarm robotics.  _Autonomous Agents and Multi-Agent Systems_ 28 (2014), 101–125.
  * Cai and Sofge (2019) Grace Cai and Don Sofge. 2019.  An Urgency-Dependent Quorum Sensing Algorithm for N-Site Selection in Autonomous Swarms.. In _AAMAS_. 1853–1855.
  * Cody and Adams (2017) Jason R Cody and Julie A Adams. 2017.  An evaluation of quorum sensing mechanisms in collective value-sensitive site selection. In _2017 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)_. IEEE, 40–47.
  * Couceiro (2017) Micael Santos Couceiro. 2017\.  An overview of swarm robotics for search and rescue applications.  _Artificial Intelligence: Concepts, Methodologies, Tools, and Applications_ (2017), 1522–1561.
  * Duarte et al. (2016) Miguel Duarte, Jorge Gomes, Vasco Costa, Tiago Rodrigues, Fernando Silva, Víctor Lobo, Mario Monteiro Marques, Sancho Moura Oliveira, and Anders Lyhne Christensen. 2016\.  Application of swarm robotics systems to marine environmental monitoring. In _OCEANS 2016-Shanghai_. IEEE, 1–8.
  * Fan et al. (2020) Xumei Fan, William Sayers, Shujun Zhang, Zhiwu Han, Luquan Ren, and Hassan Chizari. 2020\.  Review and classification of bio-inspired algorithms and their applications.  _Journal of Bionic Engineering_ 17, 3 (2020), 611–631.
  * Fujisawa and Dobata (2013) Ryusuke Fujisawa and Shigeto Dobata. 2013.  Lévy walk enhances efficiency of group foraging in pheromone-communicating swarm robots. In _Proceedings of the 2013 IEEE/SICE International Symposium on System Integration_. 808–813.  https://doi.org/10.1109/SII.2013.6776760
  * Gerkey and Matarić (2004) Brian P Gerkey and Maja J Matarić. 2004.  A formal analysis and taxonomy of task allocation in multi-robot systems.  _The International journal of robotics research_ 23, 9 (2004), 939–954.
  * Halász et al. (2007) Adám Halász, M Ani Hsieh, Spring Berman, and Vijay Kumar. 2007.  Dynamic redistribution of a swarm of robots among multiple sites. In _2007 IEEE/RSJ international conference on intelligent robots and systems_. IEEE, 2320–2325.
  * Harasha and Cai (2023) Noble Harasha and Grace Cai. 2023.  _Geometric Swarm Model_.  https://doi.org/10.5281/zenodo.7570294
  * Harwell and Gini (2018) John Harwell and Maria Gini. 2018.  Broadening applicability of swarm-robotic foraging through constraint relaxation. In _2018 IEEE International Conference on Simulation, Modeling, and Programming for Autonomous Robots (SIMPAR)_. IEEE, 116–122.
  * Hoeing et al. (2007) Matthew Hoeing, Prithviraj Dasgupta, Plamen Petrov, and Stephen O’Hara. 2007.  Auction-based multi-robot task allocation in comstar. In _Proceedings of the 6th international joint conference on autonomous agents and multiagent systems_. 1–8.
  * Hoff et al. (2010) Nicholas R Hoff, Amelia Sagoff, Robert J Wood, and Radhika Nagpal. 2010.  Two foraging algorithms for robot swarms using only local communication. In _2010 IEEE International Conference on Robotics and Biomimetics_. IEEE, 123–130.
  * Hsieh et al. (2008) M Ani Hsieh, Ádám Halász, Spring Berman, and Vijay Kumar. 2008.  Biologically inspired redistribution of a swarm of robots among multiple sites.  _Swarm Intelligence_ 2, 2 (2008), 121–141.
  * Karaboga and Akay (2009) Dervis Karaboga and Bahriye Akay. 2009.  A survey: algorithms simulating bee swarm intelligence.  _Artificial intelligence review_ 31, 1 (2009), 61–85.
  * Khurana and Sofge (2020) Shreeya Khurana and Donald Sofge. 2020.  Quorum Sensing Re-evaluation Algorithm for N-Site Selection in Autonomous Swarms.. In _ICAART (1)_. 193–198.
  * Lu et al. (2018) Qi Lu, Joshua P Hecker, and Melanie E Moses. 2018.  Multiple-place swarm foraging with dynamic depots.  _Autonomous Robots_ 42 (2018), 909–926.
  * O’hara et al. (2005) Keith J O’hara, Daniel B Walker, and Tucker R Balch. 2005\.  The GNATS—low-cost embedded networks for supporting mobile robots.  In _Multi-Robot Systems. From Swarms to Intelligent Automata Volume III_. Springer, 277–282.
  * Parunak et al. (2002) H Van Parunak, Michael Purcell, and Robert O’Connell. 2002\.  Digital pheromones for autonomous coordination of swarming UAV’s. In _1st UAV Conference_. 3446\.
  * Poli et al. (2007) Riccardo Poli, James Kennedy, and Tim Blackwell. 2007\.  Particle swarm optimization.  _Swarm intelligence_ 1, 1 (2007), 33–57.
  * Pratt (2005a) Stephen C Pratt. 2005a.  Behavioral mechanisms of collective nest-site choice by the ant Temnothorax curvispinosus.  _Insectes Sociaux_ 52, 4 (2005), 383–392.
  * Pratt (2005b) Stephen C Pratt. 2005b.  Quorum sensing by encounter rates in the ant Temnothorax albipennis.  _Behavioral Ecology_ 16, 2 (2005), 488–496.
  * Reina et al. (2015) Andreagiovanni Reina, Gabriele Valentini, Cristian Fernández-Oto, Marco Dorigo, and Vito Trianni. 2015.  A design pattern for decentralised decision making.  _PloS one_ 10, 10 (2015), e0140950.
  * Reynolds and Rhodes (2009) A. M. Reynolds and C. J. Rhodes. 2009.  The Lévy Flight Paradigm: Random Search Patterns and Mechanisms.  _Ecology_ 90, 4 (2009), 877–887.  http://www.jstor.org/stable/25592573
  * Reynolds (1987) Craig W Reynolds. 1987\.  Flocks, herds and schools: A distributed behavioral model. In _Proceedings of the 14th annual conference on Computer graphics and interactive techniques_. 25–34.
  * Rubenstein et al. (2012) Michael Rubenstein, Christian Ahler, and Radhika Nagpal. 2012\.  Kilobot: A low cost scalable robot system for collective behaviors. In _2012 IEEE international conference on robotics and automation_. IEEE, 3293–3298.
  * Russell et al. (2015) Katherine Russell, Michael Schader, Kevin Andrea, and Sean Luke. 2015\.  Swarm robot foraging with wireless sensor motes. In _Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems_. Citeseer, 287–295.
  * Sahin et al. (2002) F Sahin et al. 2002\.  A swarm intelligence based approach to the mine detection problem. In _IEEE International Conference on Systems, Man and Cybernetics_ , Vol. 3. IEEE, 6–pp.
  * Solomon (2018) Justin Solomon. 2018\.  Optimal transport on discrete domains.  _AMS Short Course on Discrete Differential Geometry_ (2018).
  * Valentini et al. (2017) Gabriele Valentini, Eliseo Ferrante, and Marco Dorigo. 2017\.  The best-of-n problem in robot swarms: Formalization, state of the art, and novel perspectives.  _Frontiers in Robotics and AI_ 4 (2017), 9.
  * Xu et al. (2015) Bo Xu, Zhaofeng Yang, Yu Ge, and Zhiping Peng. 2015\.  Coalition formation in multi-agent systems based on improved particle swarm optimization algorithm.  _International Journal of Hybrid Information Technology_ 8, 3 (2015), 1–8.
  * Zhang et al. (2007) Dandan Zhang, Guangming Xie, Junzhi Yu, and Long Wang. 2007\.  Adaptive task assignment for multiple mobile robots via swarm intelligence approach.  _Robotics and Autonomous Systems_ 55, 7 (2007), 572–588.


# Large-scale Generative AI Models
Lack Visual Number Sense

Alberto Testolin
Department of General Psychology and
Department of Mathematics
University of Padova , Padova (IT)
<EMAIL_ADDRESS>
Kuinan Hou
Department of General Psychology
University of Padova, Padova (IT)
<EMAIL_ADDRESS>
Marco Zorzi
Department of General Psychology and Padova Neuroscience Center
University of Padova, Padova (IT) and
IRCSS San Camillo Hospital, Venice-Lido (IT)
<EMAIL_ADDRESS>

###### Abstract

Humans can readily judge the number of objects in a visual scene, even without
counting, and such a skill has been documented in a variety of animal species
and in babies prior to language development and formal schooling. Numerical
judgments are error-free for small sets, while for larger collections
responses become approximate, with variability increasing proportionally to
the target number. This response pattern is observed for items of all kinds,
despite variation in object features (such as color or shape), suggesting that
our visual number sense relies on abstract representations of numerosity.
Here, we investigated whether generative Artificial Intelligence (AI) models
based on large-scale transformer architectures can reliably name the number of
objects in simple visual stimuli or generate images containing a target number
of items in the 1-10 range. Surprisingly, none of the foundation models
considered performed in a human-like way: They all made striking errors even
with small numbers, the response variability often did not increase in a
systematic way, and the pattern of errors varied with object category. Our
findings demonstrate that advanced AI systems still lack a basic ability that
supports an intuitive understanding of numbers, which in humans is
foundational for numeracy and mathematical development.

_K_ eywords Foundation Models $\cdot$ Machine Vision $\cdot$ Deep Learning
$\cdot$ Numerical Cognition $\cdot$ Numerosity

## Introduction

Artificial Intelligence (AI) is progressing rapidly, with deep learning models
approaching or even surpassing human performance in a variety of domains,
including perceptual judgements [1] and natural language processing [2]. In
this article, we investigate whether advanced AI systems can judge the
numerosity of visual sets, a core capability that we share with many animal
species [3]. Even infants are sensitive to numerosity [4] and toddlers can
generate sets containing a target number of items [5], suggesting that a
preverbal understanding of numerical quantities develops well before formal
education. Although it is a high-level feature derived from global image
properties, numerosity is spontaneously extracted by our visual system [6].
Small numerosities in the “subitizing” range (up to 4) are perceived in an
exact manner, while the numerosity of larger sets is approximately estimated
when counting is precluded [7]. In the latter case, responses follow Weber’s
law, so that variability increases proportionally to the mean estimate [3].
Another key signature of number sense is its abstract nature: numerosity is
encoded independently from object category, location or presentation modality
[4].

Here we systematically probed the visual number sense of several state-of-the-
art “foundation models”, which are large-scale generative architectures
trained on huge data sets that can be readily used to solve a wide range of
downstream tasks [8]. In the image-to-text domain, modern Visual Question
Answering (VQA) systems can provide written answers to non-trivial questions
about the content of an image or accurate descriptions of complex visual
scenes; here we tested the capability of judging visual numerosity of the
Vision-and-Language Transformer (ViLT) [9] and the Bootstrapping Language-
Image Pre-training (BLIP-2) model [10]. In the text-to-image domain,
generative models can produce high-quality visual content following detailed
user prompts provided in natural language; here we tested the numerosity
production skills of two of the most popular generative models for images:
DALL-E (version 2) [11] and Stable Diffusion (version 2.1) [12].

In line with recent proposals [13], we exploited two behavioral tasks used in
cognitive psychology to evaluate number sense: numerosity naming [7], which
requires establishing how many items are present in a given image, and
numerosity production [14, 5], which requires generating a target number of
items. We characterized the distribution of responses produced by the
different AI models in the range 1-10 using a variety of object categories.
Perfect accuracy across the entire numerical range would suggest the emergence
of counting skills, while error-free responses with only small numbers would
either indicate subitizing capabilities, or that counting is only partially
developed as in children who do not fully master the counting principles [15,
16]. Error-prone responses centered on the target number would instead suggest
that the AI model relies on approximate estimation mechanisms, which may or
may not follow Weber’s law.

## Results

### Numerosity naming

We probed the numerosity naming skills of two state-of-the-art VQA
architectures: the Vision-and-Language Transformer (ViLT) [9] and the
Bootstrapping Language-Image Pre-training (BLIP-2) model [10]. These systems
have remarkable visual reasoning abilities and can answer nontrivial questions
related to image content (e.g., What does the image represent? What are the
feelings of the people in the scene and why?). We asked the models how many
objects were present in a set of images containing up to 10 objects (see
Section Materials and Methods for methodological details). Each stimulus
included only items of the same kind, sampled from 5 possible classes:
realistic pictures of common categories (apples, people, butterflies), colored
dots, and “fast cards” depicting regularly placed clip-arts similar to those
used to test children [15]. Examples are shown in Fig. 1 (top row).

Figure 1: Examples of images provided as input or produced by the models,
ordered according to target number (reported at the bottom). The first row
shows examples of stimuli used in the numerosity naming task: the first four
images are taken from the “apples”, “people”, “butterflies” and “dots”
categories, while the remaining images are sampled from the “fast cards”
category. Subsequent rows show examples of images generated by DALL-E and
Stable Diffusion in the numerosity production task, showcasing both correct
and wrong generations. We sampled two images for each target category (apples,
people, butterflies, dots). In specific cases, DALL-E never makes mistakes
when there are a few objects to be produced (up to 3 objects for the “apples”
category, exactly 3 objects for the “people” category, and exactly 1 object
for the “butterflies” category). Another interesting phenomenon is the
generation of images containing a wrong number of dots, which are nevertheless
arranged according to the target digit shape (e.g., 8 in the figure).

In general, response accuracy was extremely low for both models (ViLT: 28.0%,
BLIP-2: 29.6%), thereby showing that they cannot count. In sharp contrast with
humans, both models returned wrong answers within the subitizing range (1-4)
and even for images with one or two objects. According to standard criteria
used in developmental studies (see Methods), these models could be considered
at most “One”-knowers [15]. Confusion matrices (CMs) reported in Fig. 2
clearly show the presence of anchoring effects, leading the models to choose
prototypical responses (e.g., 4, 6) probably corresponding to common spatial
layouts that might be over-represented in the training corpora. The pattern of
responses also drastically varied between categories (minimum correlation
between CMs for ViLT: 0.04, BLIP-2: 0.27), suggesting that the emergent
numerical representations are not abstract.

### Numerosity production

We also probed the numerosity production skills of two of the most popular
generative models for images: DALL-E (version 2) [11] and Stable Diffusion
(version 2.1) [12]. These foundation models have proven capable of generating
high-quality images following a textual description, also taking into account
stylistic instructions, fine-grained details, and relational features (e.g., A
photo of an astronaut riding a horse in photorealistic style). We asked the
models to generate images with a target number of objects, in analogy with
numerosity production tasks used in animal and human studies [14, 5]. The
target objects belonged to the same classes used for the naming task, except
for the “fast cards” category, which could be underrepresented in the corpora
used to train these models. Examples of generated images are shown in the
middle and bottom rows of Fig. 1.

Overall, DALL-E tended to generate images with white background and more
definite objects, while Stable Diffusion adopted more artistic generation
styles, producing either paintings, clip-arts, or realistic content. Similarly
to the naming task, mean accuracy was low (DALL-E: 38.7%, Stable Diff: 33.3%),
though DALL-E in some cases exhibited accurate response in the small number
range (for the apples category, responses were error-free up to $n$ = 3).
According to standard criteria, DALL-E would be considered a “Three”-knower,
while Stable Diffusion would be considered a “Two”-knower [15]. Compared to
the naming task, the response patterns were more homogeneous across categories
(minimum correlation between CMs for DALL-E: 0.76, Stable Diff: 0.81).

Figure 2: Confusion matrices showing the distribution of models’ responses for
different object categories. The x-axis represents the target number, while
the y-axis represents the corresponding model responses. Response frequency is
encoded using a grey scale (white = 0%, black = 100%). The first two rows
refer to the numerosity naming task, which contains the additional “fast
cards” category. The remaining rows refer to the numerosity production task,
and contain two additional panels depicting the response distributions
observed in behavioral studies with human adults [7] and children [16] across
similar numerical ranges (note that for the adult data the maximum number of
items to be estimated was eight). For the children data, the graph shows the
response frequency of “Three”-knower children (larger circles indicate higher
frequency), along with the estimated response likelihood (gray shading).

### Adherence to Weber’s law

In humans and other animal species, numerosity estimation data collected
through naming and production tasks approximately follow the law of scalar
variability, as indicated by a constant coefficient of variation (standard
error of the responses/mean response) [17, 18] (but see [19] for discussion of
possible exceptions). To investigate whether models’ responses followed a
scalar variability pattern, we used a well-established methodology
implementing a log–log regression analysis [20]. If scalar variability holds,
as the number $n$ increases the logs of the standard error $SE(n)$ and of the
mean estimates $\mu(n)$ should form a straight line, with a slope $\beta=1$
[$log(SE(n))=\alpha+\beta log(\mu(n))$]. A slope that is significantly
different from 1 would indicate that the relation between the standard errors
and the means is a more complex power function, while a poor fit would more
generally indicate that the response variability cannot be explained by linear
or power trends.

We carried out a separate analysis for each model and for each object
category. If a model exhibited error-free responses for small numbers, we
excluded those numbers from the analysis. In almost half of the cases (8 out
of 18), the regression analysis resulted in a poor fit ($p>0.05$), indicating
that the distribution of responses did not systematically change as a function
of numerosity, in sharp contrast with human and animal data. In the remaining
cases the regression analysis was significant (all $p<0.05$;
$r^{2}=0.64-0.96$), therefore we further tested whether the regression slopes
were significantly different from 1. Results were mixed, and depended both on
the model type and the object category.

In the numerosity naming task, the distribution of models’ responses did not
follow the pattern observed in human estimation [7]. For ViLT, we observed
scalar variability for the people (slope = 1.11, p > 0.05) and butterflies
(slope = 1.14, p > 0.05) categories, while we observed power variability for
the fast card category (slope = 1.37, p = 0.003). For BLIP2, the regression
analysis never produced a good fit. In the numerosity production task the
errors were more regularly distributed around the target number (also see Fig.
2). For DALL-E, we observed scalar variability for the dots category (slope =
0.82, p > 0.05), while we observed power variability for the apples (slope =
1.53, p = 0.024) and butterflies (slope = 1.49, p = 0.036) categories. For
Stable Diffusion, we observed scalar variability for the apples (slope = 1.07,
p > 0.05) and butterflies (slope = 1.15, p > 0.05) categories, while we
observed power variability for the people (slope = 0.70, p = 0.030) and dots
(slope = 0.60, p = 0.016) categories.

Overall, scalar variability was thus observed only in five specific
conditions. In other five conditions the variability increased according to a
power law, while in the remaining eight cases the response variability did not
have a systematic trend.

## Discussion

This work demonstrates that foundational AI models cannot reliably judge the
number of objects in a visual scene, both in image-to-text and text-to-image
tasks. Such a striking deficit is observed even for small sets, supporting a
knower-level comparable to that of 3-year-old children [15, 16]. This might
explain anecdotal evidence showing the failure of generative AI to synthesize
realistic images featuring multiple instances of a body part, such as the
correct number of fingers in a hand. Surprisingly, and in contrast with
smaller-scale deep learning models [21, 22, 23], even approximate estimation
was not robust and often failed to match the psychophysics of human numerosity
perception. We believe that substantial progress in architecture design and
training procedures is warranted to create AI systems that understand visual
numerosity [24]. Grounding numeracy development in the visual number sense, as
in the case of humans [3], might also be the key to enabling AI systems to
acquire and fully master numerical and mathematical knowledge [25].

## Materials and Methods

In the naming task, for each object class and target number we probed the
models using 50 high-resolution ($1024\times 1024$ pixels) images created by
randomly placing items of variable size on a uniform white background, with no
overlap. Fast card stimuli were created using clip-arts of common objects
(apples, bells, butterflies, candies, cars, fish, flowers, planes, stars)
drawn in different colors (black, blue, green, orange, red). Responses without
numerical content or with vague quantification (e.g., “a few”) were
automatically discarded, but we ensured that at least 20 acceptable answers
were produced for each class/number combination. In the production task, for
each condition we probed the models to generate 50 high-resolution images,
which were then manually labeled by one of the authors (K.H.) and individually
double checked by another author. Images with an ambiguous number of objects
or with ill-formed content were discarded (see Section Analysis of model
responses for details). We ensured that at least 20 acceptable images were
produced for each test condition.

### Models

We considered two different Visual Question Answering (VQA) models. We used
the vilt-b32-mlm version of the Vision-and-Language Transformer (ViLT) model
[9] available through Hugging Face. This architecture incorporates text
embeddings into a Vision Transformer (ViT), allowing it to have a minimal
design for Vision-and-Language Pre-training and thus speeding-up model
training and inference phases. It has a total of 87.4 million parameters. We
also used the blip2-flan-t5-xl version of the Bootstrapping Language-Image
Pre-training with Frozen Image Encoders and Large Language Models (BLIP-2)
model [10], developed by Salesforce and available through Hugging Face. This
architecture is considered an improved version of BLIP [26] and it is
available in different versions, depending on the type and size of the
backbone models. We explored all versions except for the t5-xxl model (due to
GPU memory constraints) and found that the version using Flan-T5 as a language
model yielded the best accuracy. The chosen model version has a total of 4.1
billion parameters.

We considered two different image generation models. We probed the DALL-E
(version 2) model [11] using the API interface provided by OpenAI. DALL-E 2 is
an improved version of the original text-to-image DALL-E model, featuring a
total of 3.5 billion parameters. We also used the Stable Diffusion (version
2.1) model [12], developed by Stability AI and available through Hugging Face.
Stable Diffusion v2.1 is a text-to-image latent diffusion model that combines
an autoencoder with a diffusion model that is trained in the latent space of
the autoencoder. It has approximately 500 million parameters.

### Prompting methods

For each model, we explored different prompting methods and selected the one
leading to the best performance, measured as mean absolute distance from the
target number.

For the numerosity naming task, we implemented three different prompting
methods. The first required to explicitly estimate the number of objects
belonging to a specific category (i.e., How many apples / butterflies / people
/ dots / shapes are there in the picture?). The other two used the more
general “objects” or “things” words to identify the items to count. For ViLT,
the best performance was achieved with the generic “things” prompt, while for
BLIP-2 the best performance was achieved with the category-specific prompts.
To make sure that the models were prompted correctly, we carried out a control
simulation related to a non-numerical task using the entire set of “apples”
stimuli. We probed the VQA models with the following prompt: What does the
image represent? and we considered as correct the following answers: apple(s)
and fruit. All models almost always provided the correct answer across the
entire set of stimuli (accuracy for ViLT : 96.8%, BLIP-2 : 100%), thus
demonstrating a proper understanding of the image content and the prompt
structure.

For the numerosity production task, both DALL-E and Stable Diffusion were
initially prompted with the following text: An image with n apples /
butterflies / people / dots (where n varied between 2 and 10). When n = 1 the
prompt was adjusted to the singular form. However, for the dots category this
prompting method resulted in poor generations: we obtained better results when
the models were prompted with a more specific description of the image: An
image with white background with n filled dots.

### Analysis of model responses

For each model, we assessed the knower-level by applying standard criteria
used in the literature on the development of counting skills [15] to the
average responses across categories. To be considered an “$n$”-knower (i.e.,
“One”-knower, “Two”-knower, “Three”-knower, “Four”-knower) the model had to:
1) Give $n$ objects at least 67% of the time when asked for that number; and
2) Give $n$ objects no more than half as often when asked for a different
number.

Responses given by VQA models were automatically parsed. If present, number
words were converted to numerical values using the word2number Python library.
The response was discarded if it contained multiple numbers or if it contained
vague quantification terms (e.g., “a few”, “a bunch of”). We checked that at
least 20 correct trials were recorded for each number/category. All models
achieved the minimum number of tests required without the need to further
prompt them (total number of responses discarded for ViLT: 0; BLIP-2: 6).

Images produced by the image generation models were discarded when more than
50% of at least one target object fell outside the margin, or the model
generated only objects of non-target categories, or the image contained more
than 20 objects. Target objects were not counted when they appeared at the
border of the picture and only a very small portion (no more than 20%) of the
object was visible, or they were not well-formed (e.g., the shape was clearly
distorted) preventing unambiguous identification, or they were occluded by
other objects, preventing unambiguous identification. Target objects were
considered valid and thus counted when they appeared behind other objects but
could still be reliably identified, or they were not entirely visible (e.g.,
more than 50% of the object mass fell outside the margin or behind other
objects) but a salient feature of the object was clearly visible (e.g., the
face of a person or the stalk of an apple), or they were represented in an
unconventional way (e.g., an apple cut in half).

For DALL-E, the minimum number of trials was not achieved for the dots
category with n = 10 (15), since the model in these cases most frequently
generated more than 30 items. For Stable Diffusion, the minimum number was not
achieved for the dots category with n = 1 (15), n = 8 (14), n = 9 (14) and n =
10 (13). Also in this case, for these prompts the model most frequently
generated more than 30 items.

### Software and computing hardware

All simulations and analyses were implemented using Python v3 and Google
Colab. To test larger-scale models (BLIP-2 family) we used a virtual machine
with an NVIDIA L4 GPU and 64 GB of RAM memory, which was allocated using the
Google cloud computing platform. Data and code used in the current study are
available on GitHub.

## Acknowledgements

We are grateful to OpenAI for granting research access to the DALL-E APIs.
This work was partially supported by the Italian Ministry of University and
Research (PRIN grant n. C53D23004110006 to M.Z.).

## References

  * [1] Scott Mayer McKinney, Marcin Sieniek, Varun Godbole, Jonathan Godwin, Natasha Antropova, Hutan Ashrafian, Trevor Back, Mary Chesus, Greg S Corrado, Ara Darzi, et al.  International evaluation of an AI system for breast cancer screening.  Nature, 577(7788):89–94, 2020.
  * [2] Fabrizio Gilardi, Meysam Alizadeh, and Maël Kubli.  ChatGPT outperforms crowd-workers for text-annotation tasks.  Proceedings of the National Academy of Sciences, 120(30), 2023.
  * [3] Stanislas Dehaene.  The number sense: How the mind creates mathematics.  OUP USA, 2011.
  * [4] Véronique Izard, Coralie Sann, Elizabeth S Spelke, and Arlette Streri.  Newborn infants perceive abstract numbers.  Proceedings of the National Academy of Sciences, 106(25):10382–10385, 2009.
  * [5] Francesco Sella, Ilaria Berteletti, Daniela Lucangeli, and Marco Zorzi.  Spontaneous non-verbal counting in toddlers.  Developmental science, 19(2):329–337, 2016.
  * [6] Guido Marco Cicchini, Giovanni Anobile, and David C Burr.  Spontaneous perception of numerosity in humans.  Nature communications, 7(1):12536, 2016.
  * [7] Susannah K Revkin, Manuela Piazza, Véronique Izard, Laurent Cohen, and Stanislas Dehaene.  Does subitizing reflect numerical estimation?  Psychological science, 19(6):607–614, 2008.
  * [8] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al.  On the opportunities and risks of foundation models.  arXiv preprint arXiv:2108.07258, 2021.
  * [9] Wonjae Kim, Bokyung Son, and Ildoo Kim.  ViLT: Vision-and-language transformer without convolution or region supervision.  In International Conference on Machine Learning, pages 5583–5594, 2021.
  * [10] Junnan Li, Dongxu Li, Silvio Savarese, and Steven Hoi.  BLIP-2: Bootstrapping language-image pre-training with frozen image encoders and large language models.  In International Conference on Machine Learning, 2023.
  * [11] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with CLIP latents.  arXiv preprint arXiv:2204.06125, 1(2):3, 2022.
  * [12] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models.  In IEEE/CVF conference on computer vision and pattern recognition, 2022.
  * [13] Marcel Binz and Eric Schulz.  Using cognitive psychology to understand GPT-3.  Proceedings of the National Academy of Sciences, 120(6):e2218523120, 2023.
  * [14] John Whalen, Charles R Gallistel, and Rochel Gelman.  Nonverbal counting in humans: The psychophysics of number representation.  Psychological science, 10(2):130–137, 1999.
  * [15] Mathieu Le Corre and Susan Carey.  One, two, three, four, nothing more: An investigation of the conceptual sources of the verbal counting principles.  Cognition, 105(2):395–438, 2007.
  * [16] Michael D Lee and Barbara W Sarnecka.  Number-knower levels in young children: Insights from bayesian modeling.  Cognition, 120(3):391–402, 2011.
  * [17] Stanislas Dehaene.  The neural basis of the weber–fechner law: a logarithmic mental number line.  Trends in cognitive sciences, 7(4):145–147, 2003.
  * [18] Charles R Gallistel and Rochel Gelman.  Non-verbal numerical cognition: From reals to integers.  Trends in cognitive sciences, 4(2):59–65, 2000.
  * [19] Alberto Testolin and James L McClelland.  Do estimates of numerosity really adhere to weber’s law? a reexamination of two case studies.  Psychonomic Bulletin & Review, 28:158–168, 2021.
  * [20] Véronique Izard and Stanislas Dehaene.  Calibrating the mental number line.  Cognition, 106(3):1221–1247, 2008.
  * [21] Ivilin Stoianov and Marco Zorzi.  Emergence of a’visual number sense’in hierarchical generative models.  Nature neuroscience, 15(2):194–196, 2012.
  * [22] Alberto Testolin, Serena Dolfi, Mathijs Rochus, and Marco Zorzi.  Visual sense of number vs. sense of magnitude in humans and machines.  Scientific reports, 10(1):10045, 2020.
  * [23] Tommaso Boccato, Alberto Testolin, and Marco Zorzi.  Learning numerosity representations with transformers: Number generation tasks and out-of-distribution generalization.  Entropy, 23(7):857, 2021.
  * [24] Alberto Testolin.  The challenge of modeling the acquisition of mathematical concepts.  Frontiers in human neuroscience, 14:100, 2020.
  * [25] Alberto Testolin.  Can neural networks do arithmetic? a survey on the elementary numerical skills of state-of-the-art deep learning models.  arXiv preprint arXiv:2303.07735, 2023.
  * [26] Junnan Li, Dongxu Li, Caiming Xiong, and Steven Hoi.  Blip: Bootstrapping language-image pre-training for unified vision-language understanding and generation.  In International Conference on Machine Learning, pages 12888–12900. PMLR, 2022.