3.1.1. Method

The algorithm is based on the idea of using neighbor information to estimate swarm information. By comprehensively considering the prior knowledge and neighbor information, the constraint is satisfied in several iterations. The architecture of the algorithm is shown in Figure 2.

Figure 2.

Architecture of the CPPCA.

Inspired by the use of social and environmental information to regulate the selection probabilities, we propose CPPCA in this section. When this article refers to an agent’s neighbors, it includes the agent itself. The satisfaction constraint described in Section 2.1 governs the adjustment of the number of agents. Specifically, if the current number of agents assigned to a task is insufficient to meet the task requirements, more existing agents are reallocated (switched) to that task; if it is sufficient, the allocation is maintained without reduction. This logic of ”additive but non-subtractive” adjustment is functionally analogous to the behavior of a rectified linear unit (ReLU), as formulated in Eq. (8).

(8) \begin{equation} \operatorname {ReLU} \left ( x \right ) = \max\!(x,0) \end{equation}

Information entropy is a measure used to quantify the uncertainty of information in information theory. The higher the entropy, the greater the system’s uncertainty, and vice versa. The definition of information entropy is based on probability theory. If a random variable $X$ takes the possible values ${X_1},{X_2},{} \ldots ,{X_N}$ , and the corresponding probability distributions are $P({X_1}),{}P({X_2}),{} \ldots ,{}P({X_N})$ , the entropy $H(X)$ of this random variable is defined as follows:

(9) \begin{equation} H(X) = - \sum \limits _{n = 1}^{N} {P({X_n}){\text{log}}P({X_n})} \end{equation}

For distributed task allocation, the random variable $X$ should represent the set of task choices of all agents in the swarm. Where the choices of the neighbors of agent $n$ are known, the choices of the non-neighbors need to be estimated. $P({X_n})$ stands for the probability of $X_n$ , where the probability is estimated in frequency. In this way, the neighbor information entropy of agent $n$ represents the uncertainty of the information about its neighbors.

In this paper, we assume that the total number of tasks is $M$ , and the number of neighbors of agent $n$ is $d_n$ . In general, the number of elements in $X$ should be of magnitude close to $M^{N - \sum _{m = 1}^M{N_l}_{_{n,m}}}$ . Counting the frequencies of each $X_i$ is computationally expensive. Let’s assume that none of the $X_i$ are repeated, that is, they all have frequency 1; we also assume that the agent has no capacity constraints, so the probability of each choice is $1/{M^{N - {d_n}}}$ , and the number of elements in $X$ is $M^{N - {d_n}}$ . In Eq. (9), the logarithm is generally base 2, and the unit is bit. But you could take other log bases. For the sake of conciseness, let $M$ be the base, then the confidence proxy $H_n^i(X)$ of agent $n$ at the $i$ th iteration of the algorithm is approximately as follows:

(10) \begin{equation} \begin{aligned} H_n^i(X) &\approx - \sum _{i = 1}^{M^{N - d_n}} \frac {1}{M^{N - d_n}} \log _{M}\!\Bigl (\frac {1}{M^{N - d_n}}\Bigr ) = \log _{M}\!\bigl (M^{N - d_n}\bigr ) = N - d_n \end{aligned} \end{equation}

That is, $H_n^i(X)$ can be approximated by the number of non-neighbors of agent $n$ at iteration $i$ . This is a monotone heuristic proxy for neighborhood completeness. It makes intuitive sense because the more non-neighbors an agent has, the less reliable information it has and the less confidence it has. It is worth noting that this approximation does not influence the optimal solution of Eq. (7). The confidence proxy essentially determines the update magnitude of the algorithm. Although approximated, its relative scale preserves the correct reflection of the reliability of neighborhood information, thereby ensuring convergence to the theoretical optimum while significantly reducing computational complexity.

In literature [Reference Pérez-Escudero and de Polavieja15], the environmental information item ${a_{m\mu }} = P({Y_m}|c)/P({Y_\mu }|c)$ . Referring to this definition, the prior knowledge item for task allocation of redundant multi-agents is set as follows:

(11) \begin{equation} a_{n,\mu }^i = \left \{ \begin{array}{l} {N_{{d_\mu }}},i = 1 \\[4pt] P_n^{i - 1}({Y_\mu }|A,B),i \ne 1 \end{array} \right . \end{equation}

At the first iteration, $a_{n,\mu }^1$ is set to the number of agents required for task $\mu$ (environmental knowledge). $A$ and $B$ are prior and posterior knowledge, respectively. In order to avoid that animals making decisions first have more influence on the group than other animals when making sequential decisions in literature [Reference Pérez-Escudero and de Polavieja15], CPPCA uses parallel decision-making and sets $a_{n,\mu }^i$ in subsequent iterations as the selection probability of task $\mu$ in the previous iteration. This is to inherit the corrected probabilities from the previous iteration.

Then the probability that agent $n$ chooses a task at iteration $i$ can be written as follows:

(12) \begin{equation} \begin{aligned} \tilde {P}_n^i({Y_\mu }|A,B) &= \ln \left \{ {{{\left [ {{{\left ( {\frac {{H_n^i(X)}}{N} + \delta } \right )}^{\alpha \operatorname {ReLU} \left ( {\frac {{{N_{{d_\mu }}}}}{{N - R}} - \frac {{{N_{{l_{n,\mu }}}}}}{{{d_n}}}} \right )}}} \right ]}^{ - 1}} \times a_{n,\mu }^i} \right \} \\ &= - \alpha \operatorname {ReLU} \left ( {\frac {{{N_{{d_\mu }}}}}{{N - R}} - \frac {{{N_{{l_{n,\mu }}}}}}{{{d_n}}}} \right )\ln \left ( {\frac {{H_n^i(X)}}{N} + \delta } \right ) \\ &\quad + \ln \left ( {a_{n,\mu }^i} \right ) \end{aligned} \end{equation}

(13) \begin{equation} P_n^i({Y_\mu }|A,B) = \frac {{\exp \left [ {\tilde {P}_n^i({Y_\mu }|A,B)} \right ]}}{{\sum \limits _{m = 1}^M {\exp \left [ {\tilde {P}_n^i({Y_m}|A,B)} \right ]} }} \end{equation}

Here, $\tilde {P}$ represents the selection scores, and $P$ represents the selection probability. $B$ stands for posterior knowledge. And $A$ represents the environment knowledge required by the number of task agents in the first iteration. In the subsequent iterations, $A$ in addition contains the knowledge learned in the previous iterations, collectively referred to as prior knowledge. $\delta$ is a bias added to prevent undefined logs at zero if the agent’s neighbors are the entire swarm. It can be set to a small positive real number. $\alpha$ is the learning rate, which is a positive real number greater than 1. $R$ denotes the redundant number of the swarm, which can be computed by $N - \mathop \sum \nolimits _{m = 1}^M {N_{{d_m}}}$ . $d_n$ denotes the number of neighbors of agent $n$ . It is calculated as follows: $\sum _{m = 1}^M{N_l}_{_{n,m}}$ . Meanwhile, the term ${N_{{d_\mu }}}/\left ( {N - R} \right ) - {N_l}_{_{n,\mu }}/{d_n}$ computes the difference between the proportion of the selected task $\mu$ among the neighbors of agent $n$ and the proportion required by environmental knowledge. The agent will use this difference to correct its own choice probabilities for the corresponding task with $\alpha$ learning rate. However, when the number of agents in the neighborhood that select task $\mu$ has satisfied the environmental knowledge constraint, the scores of selecting it will not be increased. In Eq. (13), the softmax operation is performed on the score of selecting each task.

The information entropy of the selection probability of agent $n$ at iteration $i$ is defined as follows:

(14) \begin{equation} Decision\_Entropy_n^i = - \sum \limits _{m = 1}^{M} {P_n^i({Y_m}|A,B){\text{log}}P_n^i({Y_m}|A,B)} \end{equation}

The CPPCA algorithm uses $Decision\_Entropy$ as the stopping criterion, halting the agent’s iteration when the entropy falls below a threshold $\epsilon$ , with a maximum iteration count set as a safeguard.

According to the formula, the larger $\alpha$ is, the stronger the agent will revise according to the posterior knowledge. And the probabilities of all non-optimal choices for each agent will approach 0 faster, and the agent’s decision will be more firm. So a large learning rate will not only increase the speed of convergence but also reduce the amplitude after convergence. The pseudocode of CPPCA is shown in Algorithm 1. The computational complexity per iteration per agent of CPPCA is $O\left [ {\max \left ( {{d_n},M} \right )} \right ]$ , and the message complexity is $O\left ( {{d_n}} \right )$ .

Algorithm 1:

CPPCA for the ith iteration of agent n

3.1.2. Proof of convergence

This section will focus on the convergence proof that CPPCA can make the task allocation satisfy the constraints.

Definition 1 [Redundancy $R_\mu$ of for task $\mu$ ]. The redundancy $R_\mu$ assigned to task $\mu$ is the redundant number of agents dedicated to that task. Let $T_u$ denote the set of task numbers of all current unsatisfied quantity constraints. The sum of redundancies across $T_u$ equals the total redundant number $R$ , i.e.,

(15) \begin{equation} \sum \nolimits _{\mu \in {T_u}} {{R_\mu }} = R \end{equation}

This allocation of redundancies $R_\mu$ is a key parameter for the subsequent analysis. $R_\mu$ does not possess a strict physical meaning, nor does it require any manual intervention or uniform real-world distribution. Instead, $R_\mu$ is purely an auxiliary theoretical construct (or virtual variable) designed exclusively to facilitate the mathematical proof of convergence.

Proof. For constant ${N_l}_{_{n,\mu }}$ and $N_{{t_\mu }}$ , $N \cdot {N_l}_{_{n,\mu }}/\left ( {{N_{{t_\mu }}} + {R_\mu }} \right )$ is smaller for larger $R_\mu$ . It is not hard to find that there should exist an allocation of $R$ such that for $\forall \mu \in {T_u}$ , all $N \cdot {N_l}_{_{n,\mu }}/\left ( {{N_{{t_\mu }}} + {R_\mu }} \right )$ are equal. And this equal value is a lower bound on $d_n$ .

Suppose the value we want to find that is equal is $Const$ , that is:

(16) \begin{equation} \frac {{{N_l}_{_{n,\mu }}}}{{{N_{{t_\mu }}} + {R_\mu }}} = Const,{\text{ }}\forall \mu \in {T_u} \end{equation}

Since $\sum \nolimits _{\mu \in {T_u}} {{R_\mu }} = R$ and ${R_\mu } = {N_l}_{_{n,\mu }}/Const - {N_{{t_\mu }}},{}\forall \mu \in {T_u}$ are deduced from the above equation, we can obtain:

(17) \begin{equation} \frac {{\sum \nolimits _{\mu \in {T_u}} {{N_l}_{_{n,\mu }}} }}{{Const}} - \sum \nolimits _{\mu \in {T_u}} {{N_{{t_\mu }}}} = R \end{equation}

So:

(18) \begin{equation} Const = \frac {{\sum \nolimits _{\mu \in {T_u}} {{N_l}_{_{n,\mu }}} }}{{\sum \nolimits _{\mu \in {T_u}} {{N_{{t_\mu }}} + R} }} \end{equation}

Under this reasonable allocation of $R$ , $d_n$ satisfies at least ${d_n} \geqslant N \cdot \sum \nolimits _{\mu \in {T_u}} {{N_l}_{_{n,\mu }}} /\left ( {\sum \nolimits _{\mu \in {T_u}} {{N_{{t_\mu }}}} + R} \right )$ .

Proof. Due to the existence of redundancy $R$ , the neighbor information can reflect the whole with a certain error, which can be described as follows:

(19) \begin{equation} {N_{{t_\mu }}} - {R_\mu } \leqslant N \cdot \frac {{{N_l}_{_{n,\mu }}}}{{{d_n}}} \leqslant {N_{{t_\mu }}} + {R_\mu },{\text{ }}\forall \mu \in {T_u} \end{equation}

The middle part of Eq. (19) represents the number of task $\mu$ selected by the agent in the whole, estimated by the neighbor information, and the left and right sides are the upper and lower bounds given after considering the redundancy. Our concern is that the number of estimates is so high that the agent does not properly adjust its selection score. So only focus on the right two parts of the inequality here. Collation can be obtained:

(20) \begin{equation} {d_n} \geqslant \frac {{N \cdot {N_l}_{_{n,\mu }}}}{{{N_{{t_\mu }}} + {R_\mu }}},{\text{ }}\forall \mu \in {T_u} \end{equation}

By Lemma 3.1 and Eq. (20), $d_n$ satisfies at least the following:

(21) \begin{equation} {d_n} \geqslant \frac {{N \cdot \sum \nolimits _{\mu \in {T_u}} {{N_l}_{_{n,\mu }}} }}{{\sum \nolimits _{\mu \in {T_u}} {{N_{{t_\mu }}}} + R}} \end{equation}

In the extreme case, all agents that choose unsatisfied tasks are neighbors of agent $n$ , and conversely, all neighbors of agent $n$ are those selecting unsatisfied tasks, in which case the right-hand side of Eq. (21) scales as follows:

(22) \begin{equation} \frac {{N \cdot \sum \nolimits _{\mu \in {T_u}} {{N_{{l_{n,\mu }}}}} }}{{\sum \nolimits _{\mu \in {T_u}} {{N_{{t_\mu }}}} + R}} \leqslant \frac {{N \cdot \sum \nolimits _{\mu \in {T_u}} {{N_{{l_{n,\mu }}}}} }}{{\sum \nolimits _{\mu \in {T_u}} {{N_{{l_{n,\mu }}}}} + R}} = \frac {N}{{1 + R/\sum \nolimits _{\mu \in {T_u}} {{N_{{l_{n,\mu }}}}} }} \leqslant \frac {N}{{1 + R/{d_n}}} \end{equation}

In this case, the right-hand side of Eq. (21) is the largest, which is $N/\left ( {1 + R/{d_n}} \right )$ . Then the inequality relation of $d_n$ is as follows:

(23) \begin{equation} {d_n} \geqslant \frac {{N \cdot {d_n}}}{{{d_n} + R}} \end{equation}

Rearranging gives:

(24) \begin{equation} {d_n} \geqslant N - R \end{equation}

When ${d_n} \geqslant N - R$ , the error of the neighbor information is within the range that the redundancy can be filled.

Proof. When $i \gt 1$ , the formula can also be written as follows:

(25) \begin{equation} \begin{aligned} \tilde {P}_n^i({Y_\mu }|A,B) &= - \alpha \operatorname {ReLU} \left ( {\frac {{{N_{{d_\mu }}}}}{{N - R}} - \frac {{{N_{{l_{n,\mu }}}}}}{{{d_n}}}} \right )\ln \left ( {\frac {{H_n^i(X)}}{N} + \delta } \right ) + \ln \left ( P_n^{i - 1}({Y_\mu }|A,B) \right ) \end{aligned} \end{equation}

$\mu$ is the task that the agent can choose within the capability constraint. When the ${N_l}_{_{n,\mu }}/{d_n} \lt {N_{{d_\mu }}}/\left ( {N - R} \right )$ , that is, when the proportion of agents that select task $\mu$ in the overall information reflected by neighbor information does not satisfy the constraint, Eq. (25) is transformed into:

(26) \begin{equation} \tilde {P}_n^i({Y_\mu }|A,B) = - \alpha \left ( {\frac {{{N_{{d_\mu }}}}}{{N - R}} - \frac {{{N_{{l_{n,\mu }}}}}}{{{d_n}}}} \right )\ln \left ( {\frac {{N-d_n}}{N} + \delta } \right ) + \ln \left ( P_n^{i - 1}({Y_\mu }|A,B) \right ) \end{equation}

Since $\delta$ is small and can be ignored, $\left [ {\left ( {N - {d_n}} \right )/N + \delta } \right ] \in (0,1)$ and $\left [ {{N_{{d_\mu }}}/\left ( {N - R} \right ) - {N_l}_{_{n,\mu }}/{d_n}} \right ] \in ( 0,1]$ , $\alpha \cdot \left [ {{N_{{d_\mu }}}/\left ( {N - R} \right ) - {N_l}_{_{n,\mu }}/{d_n}} \right ] \in (0 ,\alpha ]$ . When $\alpha \gt 1$ , the first term of Eq. (26) is greater than 0.

It follows from Theorem3.2 that the neighbor information can correctly reflect the overall information. The above derivation shows that the algorithm can always increase the selection score corresponding to a task when the number of agents choosing a task does not satisfy the constraint. Similarly, if the number of agents choosing a task satisfies the constraint, the algorithm can always keep the selection score corresponding to this task unchanged (due to the existence of the ReLU function).

Intuitively, the condition that the number of neighbors must exceed a certain threshold for CPPCA to converge is deeply tied to its estimation mechanism. The core philosophy of CPPCA relies on agents estimating the global task distribution of the population through the local task selections of their neighbors, followed by iterative strategy adjustments. This process fundamentally depends on estimation accuracy. When the number of neighbors is too small, the local observation acts as an unrepresentative sample, leading to poor estimation accuracy of the global state. Such unreliable estimations can easily mislead an agent’s decision-making process, causing its choice to deviate from the correct convergence direction. Therefore, a sufficiently large number of neighbors is required to guarantee the statistical reliability of the estimation, thereby ensuring the stable convergence of the algorithm.

However, due to the subsequent softmax operation on the selection probabilities, the increase in the selection score described in Theorem3.3 does not guarantee that the normalized selection probability will also increase. When another task has a larger demand for the number of agents than task $\mu$ , the selection probability of task $\mu$ may become smaller after normalization. But this is a better outcome for the swarm, as the agent will tend to choose tasks that require it more.

With the development of communication and iteration, the algorithm will continuously increase the selection probabilities of tasks whose constraints are not satisfied until the constraints are satisfied and the algorithm converges.

Theorem3.2 gives a lower bound on $d_n$ in a very extreme case, where it is practically impossible to encounter an iteration in which only the task with the smallest demand is satisfied. So in practice, the lower bound of $d_n$ is affected by the capacity constraint matrix $E$ and the initialization way, but it must be lower than $N-R$ .

3.2.1. Method

After the above decision process is completed, only one of the solutions satisfying the constraints is obtained. However, it is not the solution that minimizes the objective function. In this section, we will use GSA to solve this problem. For each agent, evaluate whether swapping tasks with all of its neighbors results in a decrease in the objective function. Note that this step requires both agents to complete the swapped task. If a swap is found that reduces the overall cost, the swap is implemented. This is repeated for all agents until no swap can further reduce the overall cost. The algorithm architecture is shown in Figure 3, and the detailed steps are summarized as Algorithm 2. The computational complexity per iteration per agent of GSA is $O\left ( {{d_n}} \right )$ , and the message complexity is $O\left ( {{d_n}} \right )$ .

Because the algorithm only performs swapping task operations, the satisfied quantity constraints are not changed. The GSA selects the current best decision at each step, but this can lead to a globally suboptimal solution, especially in complex multi-agent environments.

Figure 3.

Architecture of the GSA.

Algorithm 2:

GSA for the jth iteration of agent n

3.2.2. Proof of convergence

The convergence of the GSA can be analyzed under an asynchronous execution model. We model the process as one where each agent activates according to its own clock, attempting to negotiate task swaps with its neighbors. Convergence is guaranteed provided two key conditions hold: (1) the communication channels are eventually reliable (messages are not lost or delayed indefinitely), and (2) each agent is activated infinitely often. This ensures that the system can explore all possible swap pairs over time.

To handle transient conflicts that may arise from concurrency (e.g., two agents simultaneously attempting to swap with a common third agent), we assume a simple priority-based conflict resolution mechanism. In this scheme, each agent or task is assigned a unique priority. When conflicting swap proposals are detected, the proposal involving the higher-priority entity is executed. This deterministic resolution strategy ensures progress and does not affect the core argument for convergence, which relies on the monotonic improvement of the global objective function with each successful, non-conflicting swap.

The correctness and convergence of GSA will be illustrated from the following aspects.

In the worst case, the ratio bound of GSA is related to the number of agents and the communication topology, but the specific ratio bound can be determined empirically and experimentally.

4.1.1. Parameter settings

To ensure a fair and reproducible comparison, the following protocol was adhered to for all experiments reported in this section. All algorithms were evaluated using the same number of tasks ( $M$ ), the same number of agents ( $N$ ), identical agent-task capability matrices, and the same random seeds for generating communication graph topologies. The hardware configuration and solver setup are shown in Table I. For calculating the ratio bound, the centralized optimal solution was obtained by solving the ILP problem defined in Eq. (7) using the COIN-OR branch and cut (CBC) solver. No time limit was imposed to ensure the global optimum was found.

Table I.

Hardware configuration and solver setup.

Table I. Long description

A table with two columns and five rows. The columns are labeled ‘Name’ and ‘Configuration/value’. The rows are as follows: Row 1: Name, CPU; Configuration/value, Intel(R) Core(TM) i9-14900KF. Row 2: Name, RAM; Configuration/value, 256 GB. Row 3: Name, Operating System; Configuration/value, Windows. Row 4: Name, Solver; Configuration/value, COIN-OR branch and cut (CBC). Row 5: Name, Tolerance; Configuration/value, 10^-7.

The Consensus-Based Auction Algorithm (CBAA) can solve the distributed single task allocation and can obtain the approximate optimal solution in finite time under the premise that the communication topology is not a complete graph [Reference Choi, Brunet and How9]. In the allocation process, the agent does not need to know the total payoff of the group, but it requires the communication topology graph to be connected at any time; otherwise, there will be conflicts.

The consensus link of CBAA can resolve the conflict of swarm task selection. Therefore, even if the number of agents is equal to the required number of tasks, the tasks can still be assigned accurately to meet the required number of tasks and minimize the cost function. The task allocation in this paper can be viewed as an $M\lt N$ allocation. That is, the number of tasks is smaller than the number of agents, and each task can be repeatedly selected by the agent. Based on this, we can multiply the tasks by the number of agents required, such that $M=N$ after augmentation. The payoff is defined as the inverse of Euclidean distance if the agent can complete a task and zero if the agent cannot. This single allocation problem is then solved using CBAA. This method inherits the desirable convergence properties of CBAA. Its performance is optimal when the cloned tasks are truly independent and interchangeable, which is a valid assumption in our target application.

A genetic algorithm (GA) is an optimization algorithm that simulates natural selection and genetic mechanisms (such as crossover and mutation). It searches for the global optimal solution through iterative evolution of the population, which is widely used in combinatorial optimization, machine learning, and other fields. In this paper, GA, a representative centralized optimization method, is selected to compare with CPPC-GA.

Decentralized genetic algorithm (DGA) parallelizes genetic algorithms across a team of agents [Reference Patel, Rudnick-Cohen, Azarm, Otte, Xu and Herrmann36]. Each agent periodically shares its current best solution with the other agents and incorporates any solutions it receives into its population.

The simulation parameters selected for a swarm size of 60 are listed in Table II. The range of the $\alpha$ is related to the scale of the update amount. The recommended range for the $\alpha$ is 10 to $10^4$ , based on the scale of the parameters for common task allocation problems.

Table II.

Simulation parameters.

Table II. Long description

The table compares simulation parameters for four algorithms: CPPC-GS, CBAA, GA, and DGA. It has four columns: Algorithm, Parameter, and Value. The table lists the values for each parameter across the different algorithms. Row 1: Algorithm, CPPC-GS. Row 2: Parameter, Number of tasks (M). Row 3: Value, 3. Row 4: Parameter, Number of agents (N). Row 5: Value, 60. Row 6: Parameter, Maximum iterations (max_iter). Row 7: Value, 30. Row 8: Parameter, Learning rate (alpha). Row 9: Value, 200. Row 10: Parameter, Bias (delta). Row 11: Value, 1 times 10 to the power of -8. Row 12: Parameter, Threshold (epsilon). Row 13: Value, 0.01. Row 14: Algorithm, CBAA. Row 15: Parameter, Number of tasks (M). Row 16: Value, 3. Row 17: Parameter, Number of agents (N). Row 18: Value, 60. Row 19: Algorithm, GA. Row 20: Parameter, Number of tasks (M). Row 21: Value, 3. Row 22: Parameter, Number of agents (N). Row 23: Value, 60. Row 24: Parameter, Crossover probability (CR). Row 25: Value, 0.5. Row 26: Parameter, Mutation probability (MU). Row 27: Value, 0.2. Row 28: Parameter, Population size (POPSIZE). Row 29: Value, 200. Row 30: Parameter, Generations (NGEN). Row 31: Value, 100. Row 32: Algorithm, DGA. Row 33: Parameter, Number of tasks (M). Row 34: Value, 3. Row 35: Parameter, Number of agents (N). Row 36: Value, 60. Row 37: Parameter, Crossover probability (CR). Row 38: Value, 0.5. Row 39: Parameter, Mutation probability (MU). Row 40: Value, 0.2. Row 41: Parameter, Population size (POPSIZE). Row 42: Value, 200. Row 43: Parameter, Generations (NGEN). Row 44: Value, 20. Row 45: Parameter, Communication interval (tau). Row 46: Value, 2.

The average degree is the average of the degrees of all nodes, which can be calculated by the following formula:

(27) \begin{equation} \overline D = \frac {{2Edges}}{N} \end{equation}

where $Edges$ is the total number of edges in the graph and $N$ is the total number of nodes in the graph. This parameter can reflect the connectivity of a connected graph. Since the convergence time of CPPC-GS, CBAA, and DGA is affected by the number of neighbors of each node, it should be consistent in the subsequent comparison, which is taken as 20 here. The graphs in this section are randomly generated at this average degree.

4.1.2. Feasibility and advantages of CPPC-GS

Using the simulation parameters defined above, when the communication topology is a connected graph, CPPC-GS is used for redundant agent task allocation. The simulation results of CPPCA are shown in Figure 5.

Figure 5.

The curve of quantity change.

The ordinate represents the number of agents that selected task $\mu$ . The abscissa represents the number of iterations. The broken lines with different colors indicate that the number of agents selecting task $\mu$ varies with the number of iterations. The dashed line is the constraint of the environment information. Under the premise of agent redundancy, CPPCA can satisfy the constraint of environment information within the maximum number of iterations, which is also the criterion to judge the convergence of CPPCA.

Figure 6 shows the change curve of the information entropies of the selection probabilities of the agents during the iterations.

Figure 6.

Change in the information entropies of the selection probabilities.

Figure 6. Long description

The image contains a grid of 50 line graphs, each representing changes in information entropies of selection probabilities. Each graph has a horizontal axis labeled from 0 to 30 and a vertical axis labeled from 0 to 1. The legend indicates that the blue line represents the entropy of p. The graphs show various patterns of entropy changes, including sharp drops, gradual declines, fluctuations, and steady states. Each graph illustrates different behaviors of the selection probabilities under varying conditions, highlighting the diversity in entropy changes across different scenarios.

The reduction in information entropies reflects the reduction in selection uncertainty. After multiple iterations, the information entropies of selection probabilities of most agents converged to 0 or some other value, indicating that these agents had understood the task they should choose or the probability they should assign. The information entropies of a small number of agents do not converge, which is because they have relatively few neighbors, but this does not affect the convergence of the swarm.

CPPCA can regulate the selection probability by the prior term and the posterior term in the formula. When the agent’s ability to complete a task is weak, its own selection probability is strongly corrected by the decisions of its neighbors so that the swarm’s decisions will converge after a finite number of iterations.

Next, we reduce the total cost by swapping tasks with GSA. The resulting curve of the total cost as a function of swap is shown in Figure 7.

Figure 7.

The curve of the cost change.

Ratio bound is a common index to measure the goodness of an approximate solution, which is defined by the following formula:

(28) \begin{equation} ratio\_bound = \max \!\left\{ \frac {{APP}}{{OPT}},\frac {{OPT}}{{APP}}\right\} \end{equation}

where $APP$ is an approximate solution to an optimization problem and $OPT$ is the optimal solution to this problem. So the bigger $ratio\_bound$ is, the worse the solution is. After repeated experiments, ILP is used as the exact benchmark method to generate the optimal solution. The simulation under different problem sizes is carried out, and the ratio bound obtained is shown in Figure 8.

Figure 8.

Box plot of ratio bound as a function of problem size.

The figure shows that the approximate solution produced by GSA in CPPC-GS is within about 2% of the optimal solution and is independent of the problem size. The convergence time comparison of the four algorithms is shown in Figure 9.

Figure 9.

Comparison of convergence time.

The different algorithms in Figure 9 have their own independent Y-axis. After a finite number of iterations, four methods can meet the constraints, and the stabilities of the algorithms are all good after repeated running. Without sacrificing optimality, CPPC-GS is more efficient than other algorithms, which take a long time to reach consensus, while GA and DGA randomly approach the optimal solution. With the increase of the number of agents, the dimension explosion of CBAA, GA, and DGA occurs, and their convergence time rises rapidly. However, the convergence time of CPPC-GS increases almost linearly. When the number of agents reaches 240, the average runtime of CBAA, GA, and DGA no longer meets the real-time requirement. It is foreseeable that when solving large-scale problems, the advantages of applying CPPC-GS to solve such problems will further increase. In the simulation, we also found that when using CBAA to solve the task allocation in this paper, there will be a situation where the corresponding capacity constraint is 0 but the task is still assigned. Due to the algorithmic logic of CBAA, there will be cases where the bids on the tasks with a capacity constraint of 1 are smaller than those of other agents, and they will have to choose the task with a capacity constraint of 0. Limited by CPU cores in PC-based multi-process simulation, multiple agents share one process. Intra-process serial overhead combined with decentralized coordination costs (e.g., inter-process communication) restricts efficiency, making DGA’s runtime no better than the centralized GA in this study.

A summary table of the performance comparison is shown in Table III.

To validate the statistical significance of these performance improvements, we conducted the Wilcoxon signed-rank test between CPPC-GS and each comparative method. The results show that all p-values from the tests are less than 0.05, demonstrating that the performance advantages of CPPC-GS over CBAA, GA, and DGA are statistically significant at the 95% confidence level.

Table III.

Performance comparison.

Table III. Long description

The table compares the performance of four methods: CPPC-GS, CBAA, GA, and DGA across different sample sizes (N) and metrics including mean (s), interquartile range (IQR), and 95% confidence interval (CI). The table has 5 rows and 8 columns. Column headers are Method, CPPC-GS, CBAA, GA, and DGA. Row labels include N, mean (s), IQR(s), and 95%CI (s) for each sample size (60, 120, 180, 240). Row 1: Method, CPPC-GS, CBAA, GA, DGA. Row 2: N, , , 60, . Row 3: mean (s), 0.019, 1.285, 0.760, 2.412. Row 4: IQR(s), 0.001, 0.096, 0.037, 0.041. Row 5: 95%CI (s), 0.018-0.019, 1.248-1.321, 0.742-0.778, 2.391-2.434. Row 6: N, , , 120, . Row 7: mean (s), 0.049, 16.990, 6.996, 11.716. Row 8: IQR(s), 0.002, 1.605, 0.108, 0.432. Row 9: 95%CI (s), 0.046-0.050, 16.349-17.632, 6.812-7.181, 11.536-11.896. Row 10: N, , , 180, . Row 11: mean (s), 0.089, 78.674, 22.429, 33.181. Row 12: IQR(s), 0.005, 7.430, 1.281, 1.403. Row 13: 95%CI (s), 0.087-0.091, 75.689-81.660, 21.531-23.327, 32.588-33.775. Row 14: N, , , 240, . Row 15: mean (s), 0.188, 249.375, 39.635, 205.026. Row 16: IQR(s), 0.076, 16.328, 7.591, 15.797. Row 17: 95%CI (s), 0.162-0.214, 241.211-257.539, 36.778-42.492, 186.153-223.900.

$^{1}$ $\overline {t}$ : average convergence time (seconds) $^{2}$ IQR: interquartile range of average convergence time (seconds) $^{3}$ 95%CI: confidence interval of average convergence time (seconds).

4.1.3. Scalability evaluation

To investigate the impact of neighbor degree on the convergence of CPPC-GS, we conducted tests on the algorithm with different neighbor degree values under the premise that $N$ is set to 60, and the results are illustrated in the Figure 10.

Figure 10.

Convergence vs. neighbor degree.

As can be observed from the figure, when the neighbor degree is set to 5 or 10, each agent obtains limited posterior knowledge and faces high uncertainty in group decision estimation. Consequently, the resulting estimation error cannot be compensated for by the corresponding redundancy, leading to the failure of CPPC-GS to converge.

To investigate the impact of redundancy on the convergence of CPPC-GS, we conducted tests on the algorithm with different redundancy levels, and the results are illustrated in the Figure 11.

Figure 11.

Convergence vs. redundancy.

As can be observed from the figure, when the redundancy is set to 0, 5, or 10, the estimation error of each agent cannot be compensated for by the corresponding redundancy. Consequently, CPPC-GS fails to converge.

4.3.1. Parameter settings

In the simulation of this section, according to the capability constraint matrix, the agents in the swarm can be divided into three categories, which are represented by squares, circles, and triangles, respectively. The capability constraints and number of agents are defined in Table IV.

Since each task can only be selected by a subset of agents, the shapes of agents that should appear in different task points in the simulation results are shown in Table V. According to Table IV, the square agent can complete tasks 1 and 3, so the square agent can appear within task points 1 and 3. On the contrary, if an agent inconsistent with Table V appears in the task point, it means that the result of task allocation does not comply with the capability constraint. The motion of the swarm uses the Reynolds-Boid model, and the parameters used are defined in Table VI.

The low-level flocking behavior of the agent swarm is governed by a motion control model based on the boids framework. Separation (governed by weight $w_s$ ) compels an agent to steer away from its local flock mates to avoid crowding. Alignment (governed by weight $w_a$ ) steers an agent towards the average heading of its local neighbors. Cohesion (governed by weight $w_c$ ), in contrast, directs an agent to move towards the average position of its local flock mates. The weights $w_s$ , $w_a$ , and $w_c$ tune the relative influence of these three competing forces.

The positions of tasks 2 and 3 are constant and are (0,8) and (5,8), respectively. The location of task 1 is time-varying. Its trajectory is defined as a circle with center (0,0) and radius 5 m. The motion speed is $1\pi$ m/s. Task 2 will become inaccessible for 6s–14s and appear for the rest of the time.

Table IV.

Different types of agents.

Table IV. Long description

Table with three rows and three columns. The first column lists capability constraint vectors as [1,"0", 1], [1,"1", 0], and [1,"1", 1]. The second column lists shapes as Square, Triangle, and Circle. The third column lists quantities as 40, 10, and 10 respectively.", "EDH": "Table categorizing agents by shape and quantity.

Table V.

The shapes of the agents that should appear in the task point.

Table V. Long description

A table with three rows and three columns. The columns are labeled Task, The shape of the agent, and N subscript a. The rows are as follows: Row 1: Task 1, Square, circle, triangle, N subscript a 10. Row 2: Task 2, Circle, triangle, N subscript a 15. Row 3: Task 3, Square, circle, N subscript a 20.

Table VI.

Dynamic task allocation corresponding parameters.

Table VI. Long description

A table with two columns labeled Parameter and Size. The table contains six rows with the following data: Row 1: Parameter, N; Size, 60. Row 2: Parameter, Time step; Size, 0.05 s. Row 3: Parameter, Simulation time; Size, 20 s. Row 4: Parameter, Radius of agent; Size, 0.1 m. Row 5: Parameter, Communication radius; Size, 2 m. Row 6: Parameter, Obstacle avoidance distance; Size, 1 m. Row 7: Parameter, Agent ideal speed; Size, 5 m/s. Row 8: Parameter, Separation weight coefficient (w s); Size, 3. Row 9: Parameter, Alignment weight coefficient (w a); Size, 1. Row 10: Parameter, Cohesion weight coefficient (w c); Size, 1.

4.3.2. The real-time performance and emergence

The CPPC-GS and CBAA are designed to solve a static instance of the task allocation problem. To evaluate their performance in dynamic environments, we adopt a receding-horizon approach. Specifically, at each discrete time step, the current state of the system (agent positions and the set of available tasks) is treated as a static snapshot. The CPPC-GS and CBAA are then invoked to compute an allocation for this snapshot. This process repeats at every time step, allowing the system to adapt to new tasks and agent state changes.

The dynamic task allocation simulations of CPPC-GS and CBAA are shown in Figures 13 and 14, respectively. In the figures, the top right legend shows how many more agents are needed for each task.

Figure 13.

Simulation of dynamic task allocation for CPPC-GS.

Figure 13. Long description

Panel A: At time 0.00 seconds, three circles are shown with no data points inside them. The circles are labeled as Unsatisfied. Panel B: At time 1.85 seconds, data points start appearing within the circles, with some points overlapping between circles. The circles are labeled as Unsatisfied. Panel C: At time 5.95 seconds, more data points are within the circles, with increased overlap. The circles are labeled as Unsatisfied. Panel D: At time 6.05 seconds, data points continue to cluster within and overlap the circles. The circles are labeled as Unsatisfied. Panel E: At time 6.95 seconds, data points are densely packed within the circles, with significant overlap. The circles are labeled as Unsatisfied. Panel F: At time 13.95 seconds, data points are densely packed within the circles, with significant overlap. The circles are labeled as Unsatisfied. Panel G: At time 14.05 seconds, data points are densely packed within the circles, with significant overlap. The circles are labeled as Unsatisfied. Panel H: At time 15.20 seconds, data points are densely packed within the circles, with significant overlap. The circles are labeled as Unsatisfied.

Figure 14.

Simulation of dynamic task allocation for CBAA.

After the simulation starts, the swarm continuously makes decisions based on the distance from the task point and its own capabilities constraints, as shown in Figures 13a and 14a, and then moves towards the assigned task point. Note that CPPC-GS and CBAA are called repeatedly throughout the simulation to update the agents’ decisions. Task 1 is motion, and the agent can achieve tracking according to simple motion logic, as shown in Figures 13b and 14b. When $6s \lt t \lt 14s$ , task 3 becomes temporarily inaccessible, and a swarm of CPPC-GS can dynamically adjust the allocation according to the algorithm, as shown in Figure 13(c)–e). However, the CBAA-based swarm requires approximately 1.3s to complete task allocation. When tasks change, the agents that retain their original selections remain unresponsive—represented as gray markers staying stationary in Figure 14d. It is not until around 7.30s that the CBAA finishes recalculation, and the gray agents are reallocated, as illustrated in Figure 14(c)–(f). At $t \geqslant 14s$ , task 3 becomes accessible, and a swarm of CPPC-GS dynamically adjusts the allocation according to the algorithm, as shown in Figure 13(f)–(h). Due to the lag in task allocation of the CBAA-based swarm, agents specifically assigned to task 3 are not promptly reallocated following task changes. It is not until around 15.30s that the CBAA completes its recalculation, and the agents are reallocated as illustrated in the Figure 14(g)–(l). Since CPPC-GS and CBAA solve a static snapshot of the allocation problem at each decision point, the temporary inaccessibility of a task leads to its removal from the current snapshot. The remaining tasks are then re-allocated. When the task becomes accessible again, it is reintroduced as a new task in a subsequent snapshot.

Simulation results show that CPPC-GS can take advantage of its fast convergence speed to deal with dynamic task allocation compared to CBAA in time and space in real time. When the task points are scattered, a small number of agents will spontaneously become communication relay nodes. This is because the distance between these agents and each task point is close, and the decisions are uncertain. Since GSA requires communication topology connectivity to optimize swarm distance cost, the emergence of such relay nodes is desirable and is allowed to happen with the object of redundant agents.

4.4.1. Hardware system design

Figure 15 illustrates the hardware architecture of the virtual-real fusion system for redundant agent task allocation. First, the FreeZe motion (FZMotion) optical motion capture camera array acquires the position data of the markers on the rigid bodies and transmits it to a power over ethernet (PoE) switch, which routes the data to the corresponding mocap computer. By matching the marker coordinates to pre-defined rigid body models, the mocap computer resolves the real-time pose of the UAVs and sends it to a Wi-Fi router. This router distributes the pose data along two parallel paths: to the UAV’s onboard Wi-Fi module and to the virtual node computer. On the UAV side, the pose is relayed to the mission computer and flight controller for precise state awareness. On the virtual node side, the system uses the pose data to calculate the subsequent control inputs for all agents, which are then transmitted back to the UAVs. Throughout this process, the UAVs continuously downlink their flight status to the ground station via Wi-Fi. Autonomous UAV flight relies on Prometheus [37].

4.4.2. Parameter settings

The task scenario defined in this section remains identical to Section 4.3.1. For the current experiments, the baseline parameters of CPPC-GS follow the previous setup. Furthermore, the swarm movement is simulated using the Reynolds-Boid model, with its parameters specified in Table VII.

Tasks 2 and 3 are stationary, located at (0, 8) and (5, 8), respectively. Task 1 is time-varying, following a circular trajectory centered at (0, 0) with a radius of 5 m and a speed of 0.5 $\pi$ m/s. Furthermore, Task 3 is inaccessible between 6s and 14s but remains active otherwise.

Table VII.

Dynamic task allocation corresponding parameters in the virtual-real fusion system.

Table VII. Long description

A table listing parameters for swarm movement simulation using the Reynolds-Boid model. The table has two columns: Parameter and Size. It contains the following data: Row 1: Parameter, N; Size, 60. Row 2: Parameter, h; Size, 1. Row 3: Parameter, Time step; Size, 0.05 s. Row 4: Parameter, Simulation time; Size, 40 s. Row 5: Parameter, Communication radius; Size, 2 m. Row 6: Parameter, Obstacle avoidance distance; Size, 2 m. Row 7: Parameter, Agent ideal speed; Size, 1 m/s. Row 8: Parameter, Maximum acceleration; Size, 2 m/s^2. Row 9: Parameter, Separation weight coefficient (w_s); Size, 20. Row 10: Parameter, Alignment weight coefficient (w_a); Size, 10. Row 11: Parameter, Cohesion weight coefficient (w_c); Size, 10.

Figure 15.

Hardware system design.

4.4.3. Virtual-real fusion experiment of multiple UAVs in a motion capture environment

Figure 16 illustrates the virtual-real fusion experiment of multiple UAVs in a motion capture environment for the CPPC-GS algorithm. In each subfigure, the upper panel displays the physical UAVs flying in the motion capture environment, while the lower panel maps their real-time positions within the virtual environment alongside the locations of all other purely virtual UAVs.

Figure 16.

Virtual-real fusion experiment of multiple UAVs in a motion capture environment.

Figure 16. Long description

The image consists of eight panels arranged in two rows and four columns. Each panel includes a photo of a motion capture environment and a corresponding 3D scatter plot. Panel A shows the initial positions of the UAVs at t=0.00s. The scatter plot has three axes labeled with numerical values and includes colored markers and ellipses representing different states of the UAVs. Panel B shows the positions at t=5.90s, with similar scatter plot details. Panel C shows the positions at t=6.05s. Panel D shows the positions at t=10.25s. Panel E shows the positions at t=14.05s. Panel F shows the positions at t=18.15s. Panel G shows the positions at t=29.10s. Panel H shows the positions at t=40.00s. Each scatter plot includes markers labeled as Satisfied or Unsatisfied, with different colors and sizes indicating various states of the UAVs. The photos show the physical positions of the UAVs in the environment, with red circles and lines indicating specific points of interest or movement paths.

At the onset of the experiment, the swarm iteratively makes decisions based on the distances to the task points and their own capability constraints, as shown in Figure 16a, and subsequently moves toward the assigned targets. Task 1 is dynamic; the agents can achieve tracking through simple motion logic, as illustrated in Figure 16b. During the interval $6\,\text{s} \lt t \lt 14\,\text{s}$ , Task 3 becomes temporarily inaccessible. The CPPC-GS swarm dynamically adjusts the task allocation according to the algorithm, as depicted in Figure 16(c) and (d). When $t \ge 14\,\text{s}$ , Task 3 becomes available again, and the swarm reconfigures the allocation accordingly, as shown in Figure 16(e) and (f).

The quantitative test results throughout the experiment indicate that (1) the average single-step computational latency of the onboard CPPC-GS algorithm across the three physical UAVs fully satisfies the timing requirements for real-time onboard control; (2) the algorithm exhibits short convergence times for re-allocation during dynamic task mutation scenarios; (3) the task constraint satisfaction rate remains nearly $100\%$ throughout the entire experiment, with no instances of capability constraint mismatch; (4) during the virtual-real collective flight, the state synchronization error between the physical UAVs and virtual agents is minimal, and the cooperative control precision meets the design specifications.

This multi-UAV virtual-real fusion experiment in a motion capture environment effectively bridges the “modeling gap” by validating the deployment of the CPPC-GS on physical hardware under complex engineering constraints. Beyond basic performance metrics, the experiment focuses on replicating non-ideal communication links—characterized by packet loss and co-channel interference—to confirm the algorithm’s distributed convergence and its capacity to prevent allocation conflicts in a decentralized setup. Furthermore, by incorporating hardware heterogeneity and real-world physical disturbances, such as airflow turbulence and sensor noise, the experiment demonstrates the system’s resilience against environmental uncertainties. This comprehensive validation underscores the algorithm’s adaptability to the inherent non-idealities of physical systems, marking a successful transition from theoretical simulation to robust practical deployment.