A Two-stage Reinforcement Learning-based Approach for Multi-entity Task Allocation (2025)

1 Introduction

Task allocation is a critical combinatorial optimization problem (Yan etal. (2012)). It plays a vital role in modern applications such as multi-robot collaboration, resource scheduling, and more. In warehouse logistics, mobile robot teams allocate tasks and transport goods to different locations (Tang etal. (2021)). In industrial and manufacturing fields, robotic arms are assigned to various processing tasks (Johannsmeier and Haddadin (2016)). On-demand carpooling and delivery services require the dispatch of agents to meet customer needs (Hyland and Mahmassani (2018)). As decision-makers, we must allocate tasks to entities based on their location, current attributes, and task requirements to ensure timely task completion.

Various approaches have been proposed to solve the task allocation problem (Wang etal. (2023); Quinton etal. (2023); Burkard etal. (2012); Parasuraman etal. (1996); Alighanbari and How (2005); Merlo etal. (2023)). The common approach treats it as a discrete optimization problem, assigning entities to tasks. Accurate solution algorithms like the Hungarian algorithm (Msala etal. (2023); Samiei and Sun (2023, 2020); Munkres (1957)), branch and bound (Martin etal. (2021); Singh (2021); Lawler and Wood (1966)), network flow algorithms (Javanmardi etal. (2023); Jamil etal. (2023); DeWeerdt etal. (2007)), fuzzy logic algorithm (Ali and Sridevi (2024); Sharma etal. (2023); Ali etal. (2021); Jamil etal. (2022)) and dynamic programming (Choudhury etal. (2022); Alkaabneh etal. (2021); Bellman (2010)) are used, as well as heuristic algorithms such as the genetic algorithm (DENG etal. (2023); Patel etal. (2020); Ye etal. (2020); Page etal. (2010); Forrest (1996); Fu etal. (2023a)), particle swarm optimization (Kalimuthu and Thomas (2024); Geng etal. (2021); Qingtian (2021)), symbiotic organisms search(Truong etal. (2020); Gharehchopogh etal. (2020); Abdullahi etal. (2023)). simulated annealing (Barbosa etal. (2023); Wang etal. (2022); Barboza and Kniess (2024); Bertsimas and Tsitsiklis (1993)) are used to solve this problem. There are also methods using game theory to allocate robots to finish tasks Martin etal. (2023); Sun etal. (2023).However, while these methods have proven effective in addressing the task allocation problem under static conditions, they often assume static task and entity attributes. In reality, task assignments frequently encounter dynamic states and fluctuations in task estimation or entity numbers over time. As a result, the applicability of the aforementioned methods may diminish, necessitating the exploration of new approaches for dynamic task allocation. This dynamic nature underscores the importance of developing methodologies capable of adapting to evolving conditions and uncertainties in real-time task assignment scenarios.

To address the dynamic allocation problem in real-world scenarios, our aim is to develop more efficient and practical algorithms compared to prior methods. After each step, a series of tasks can emerge, requiring us to allocate entities effectively to achieve task goals. However, these resources come with associated costs, such as power consumption in transmission and additional expenses incurred by companies when assigning employees to extra tasks. Therefore, we must carefully select the appropriate resources from a large pool to minimize costs and successfully complete tasks.Treating this problem as a Markov Decision Process (MDP), we leverage Reinforcement Learning (RL) algorithms to dynamically adjust allocation actions based on the current state, without incurring additional computational costs. Several RL-based methods have been developed for task allocation in various domains. For instance, Afrin etal. (2023) integrates edge and cloud computing with robotics to address computation tasks impacted by uncertain failures, utilizing a multiple deep Q-network mechanism for dynamic task allocation and ensuring quicker resiliency management. Similarly, Fu etal. (2023b) applies deep reinforcement learning to mobile crowd sensing, using a double deep Q network based on the dueling architecture to manage dynamic task allocation under multiple constraints, surpassing traditional heuristic methods in platform profit and task completion rate. These approaches show promising results in Smart Farm and mobile crowd sensing scenarios. Additionally, methods such as Park etal. (2021) and Agrawal etal. (2023) use attention modules to extract task and robot properties, facilitating efficient allocation decisions in environments like warehouses. Other notable works include task allocation for workers in spatio-temporal crowdsourcing (Zhao etal. (2023)) and mobile crowdsensing (Xu and Song (2023)).

2 Related Work

Multi-robot task allocation: The overview of task allocation for multiple robots is how to allocate subtasks to each robot in a way that balances the entire load. Due to the Non-deterministic Polynomial (NP) difficulty of the problem, researchers decompose it into sub-problems or apply meta-heuristic techniques. Some studies have addressed the challenges in multi-robot task allocation, which have various objectives such as energy consumption, time, cost, fairness, and task completion. Genetic algorithm (Patel etal. (2020); Ye etal. (2020); Page etal. (2010)), k-means clustering algorithm (Muthusamy and Chandran (2021); Sheikh etal. (2023); Elango etal. (2011)), and imitative learning (Wang etal. (2020); Yuvaraj etal. (2021); Jebara (2001)) are used to solve this problem. Most research has focused on specific applications, such as manufacturing (Wang etal. (2021); Morariu etal. (2020); Giordani etal. (2010)), inspection (Karami etal. (2020); Zhou etal. (2023); Liu etal. (2017)), warehouses (Tsang etal. (2018); Albert etal. (2023)), disaster rescue (Ghassemi and Chowdhury (2022); Xu etal. (2023)), multiple unmanned aerial vehicle (UAV) formations (Wu etal. (2023); Zhang etal. (2020b)), computation allocation (Sun and He (2023)), and workshop scheduling (Wang and Wu (2023); Zhang etal. (2022); Han etal. (2022); Dahl etal. (2009)). Currently, (Zhang etal. (2023)) uses graph-based method to batch tasks with time and precedence constraints, aiming to optimize coordination, reduce downtime, and minimize energy consumption to addresses multi-robot task allocation. (Wen and Ma (2024)) introduces a unified model for the multi-robot task allocation problem, presenting an efficient indicator-based multi-objective evolutionary algorithm with a hybrid encoding scheme and adaptive archive update mechanism. (Zhang etal. (2024)) proposes a novel graph deep-reinforcement-learning-based approach that leverages graph sampling and cross-attention decoding to efficiently allocate tasks to robots, demonstrating high scalability and robustness through extensive experiments in various multi-robot task allocation scenarios. (Yan and Di (2023)) introducing a hyper-heuristic algorithm that minimizes the time cost for compulsory tasks while selectively completing functional tasks to address multi-robot task allocation. (Guo etal. (2024)) introducing a collaborative discrete bee colony algorithm. (Agrawal etal. (2023)) presents a novel reinforcement learning-based algorithm (RTAW) for multi-robot task allocation in warehouse environments, utilizing a deep multi-agent reinforcement learning method with an attention-inspired policy architecture to minimize total travel delay and improve makespan. This article focuses more on algorithmic innovation and provides a new allocation model based on RL algorithms for tasks, including multi-robot allocation.

Dynamic task allocation: There are several typical methods in the study of dynamic task allocation. The first method is to use a multi-robot task allocation strategy (Quinton etal. (2023); Schneider etal. (2017)), which mimics the process of market trading. When a new task is born, all robots will quote, and ultimately the task is assigned to the robot with the lowest quote. Robots will regularly update their quotes to reassign tasks, but this auction is very time-consuming, so the action distance of robots assigned using this strategy will be set very short (Ullah and Nawi (2023); DeRyck etal. (2022); Talebpour and Martinoli (2018)). The second method is to still use the static task allocation method to search for solutions. When the task state changes, fine-tuning methods are used to find new solutions. For example, the genetic algorithm in meta heuristic algorithms can partially cross mutate on the basis of the original solution to obtain a new solution (Patel etal. (2020); Zhang etal. (2021); Chen etal. (2018); Zhou etal. (2019)). Some methods need to rerun the algorithm to calculate new optimal solutions, such as Integer programming algorithm (Chen etal. (2023); Li etal. (2017); Su etal. (2018)) and search algorithm (Sanaj and Prathap (2020); Zhang etal. (2020a); Mitiche etal. (2019)). Whether it is fine-tuning or searching for the optimal solution again, it is a very time-consuming process, and when the task changes frequently, it is completely impossible to find a suitable solution. The third method is to use clustering algorithms to cluster similar entities into a formation, and entities with similar functions or attributes will be assigned to a formation, greatly reducing the allocation time (Sun etal. (2021); Sarkar etal. (2018)). This approach can meet the requirements of real-time performance, but once the attributes of the entity are misvalued or malfunctions occur, the completion rate of the task will be greatly reduced (Mitiche etal. (2019)). Currently, Dynamic Multi-Robot Task Allocation for capacitated robots using Satisfiability Modulo Theories solves the problem of handling dynamic streams of tasks with deadlines, ensuring soundness, completeness, and generality for various task specifications Tuck etal. (2024). Merlo etal. (2023) introduces an ergonomic role allocation framework for human-robot collaboration, integrating task features and human state measurements to optimize task assignment and reduce the risk of work-related musculoskeletal disorders. Afrin etal. (2023) incorporates edge and cloud computing with robotics to support computation tasks affected by uncertain failures, proposing a multiple deep Q-network dynamic task allocation mechanism to ensure faster resiliency management. Fu etal. (2023b) leverages deep reinforcement learning methods for mobile crowd sensing task allocation, using a double deep Q network based on the dueling architecture to address dynamic task allocation under multiple constraints. These two approaches have shown promising results utilizing deep reinforcement learning in Smart Farm and mobile crowd sensing scenarios. Existing RL methods (Park etal. (2021); Agrawal etal. (2023)) aim to solve the allocation problem by using attention modules to extract task and robot properties for decision-making, similar to our approach. They apply an attention-based approach to derive robot and task embeddings and utilize algorithms to allocate robots, often in warehouse environments. However, these methods model the problem as an MDP and apply reinforcement learning but don’t handle scenarios with a variable number of robots. Additionally, they assume fixed robot attributes and do not allow robots to autonomously propose bids. Also, all robots must be allocated, making it a fixed-number allocation problem. In contrast, our approach addresses more complex scenarios. Our entities can include robots, vehicles, suppliers who propose bids based on their attributes, or employees requesting salaries. Our problem definition allows for entity-specific attributes and bids, enabling managers to exclude entities with high bids and low attributes. Our method accommodates variable numbers of entities, dynamic bids, and can handle entity selection and task allocation even when the number of entities far exceeds the number of tasks.

3 Problem Setup

In the environment, there are many tasks in an episode, and we need to act as managers to assign entities to solve these tasks in order to receive rewards. These entities can be workers who have their own minds and are self-interested or cars that contain a lot of resources. Choosing these entities to complete tasks requires a cost, such as overtime wages for employees and fuel consumption considerations for allocating vehicles. What we need to do is choosing these entities in a reasonable manner and allocating them to complete various tasks. Suppose there are $m$ tasks and $n$ entities in an environment. The number of entities $n$ is much larger than $m$ and these entities will follow the instructions if the manager pays a cost to them. For different states, the cost of entities is dynamic since the consumption of vehicles is different and the demands of the workers are changing.

MDP. Our setting builds on the standard formulation of the Markov Decision Process (MDP) Sutton etal. (1998) where the agent observes a state $s\in\mathcal{S}$ and takes an action $a\in\mathcal{A}$. The transition probability function $P(s^{\prime}|s,a)$ transits current state $s$ to next state $s^{\prime}$ after taking action $a$, and the agent receives a reward $r$ according to the reward function $r:\mathcal{A}\times\mathcal{S}\to\mathbb{R}$. The goal of the agent is to learn a policy $\pi(a|s)$ that maximizes the expected cumulative discounted returns $\mathbb{E}_{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r\left(s_{t},a_{t}\right)\right]\text{ where }\gamma\in[0,1)\text{ is the discount factor}$. In this paper, the state of the manager comprises the positional information of all entities, attributes of carried resources, the positions of tasks, and the total resources required for tasks. Actions are defined as the task allocation scenario. The state transition matrix is based on the current task allocation scenario, where the environment returns the positions and resources of all entities and tasks after each entity’s movement. The state of an entity includes its own resources and position, as well as the resource requirements and positions of all tasks. Actions involve moving in any direction, and for worker entities, there is an additional action for bidding. The state transition matrix is determined by the current state and action, returning the entity’s resource position and the resource requirements and positions of all tasks for the next time step.

Task. Let $T=<T_{1},T_{2},...T_{m}>$ be the sequence of tasks arriving in an episode, and task $T_{i}$ is defined as a tuple $<r_{i},tr_{i,1},tr_{i,2},...tr_{i,k}>$ where $r_{i}$ denotes the reward of completing task $T_{i}$ and $tr_{i,j}$ is the quantity of resource $j$ needed to complete task $T_{i}$. Ability, experience, or the number of items can all be interpreted as resources. We define $C_{i}$ as the flag of completion of task $T_{i}$, i.e., $C_{i}=1$ if task $T_{i}$ is completed, otherwise $C_{i}=0$.

Entities.In this paper, we extend the concept of reinforcement learning agents to entities, which can be considered roughly equivalent. Entities can be item entities (e.g., vehicles) or worker entities. The difference between the two lies in whether the entity can provide bids based on its own attributes. The former can be regarded as fixed-price untrained agents, while the latter employs reinforcement learning algorithms to dynamically adjust bidding strategies. In the subsequent descriptions, we will use the term "entity" instead of "agent." Item entities have a cost (e.g., fuel consumption and time penalty), while worker entities have wage demands for task assignments. Each entity $w_{i}$ is defined as $<d_{i},wr_{i,1},wr_{i,2},...,wr_{i,k}>$, with $d_{i}$ representing the cost demand and $wr_{i,j}$ denoting the resource $j$ possessed by entity $w_{i}$. For item entities, $d_{i}$ is a manually given cost function based on distance, time, purchase cost, etc. For Worker entities, they aim to maximize their individual rewards. Workers propose demands $d=<d_{1},d_{2},...d_{n}>$ based on their resources $wr=<wr_{1},wr_{2},...wr_{k}>$. A high demand reduces the chances of selection, while low demands result in lower task rewards. Worker entities take a policy $\pi_{i}(d_{i}|T)$ to determine appropriate reward demands.

Manager. Our algorithm acts as a manager, assigning entities to tasks based on task and entity attributes. The manager observes the task $T$, entity resources $wr$, entity costs $d$, and chooses entities ($a=<a_{1},a_{2},...a_{m}>$) to perform tasks. The manager’s goal is to maximize its own reward, $\sum_{i=1}^{m}R_{i}C_{i}$, where $R_{i}=r_{i}-\sum_{j\in a_{i}}d_{j}$ represents the reward for task $T_{i}$ with action $a_{i}$. If $R_{i}<0$, the manager abandons task $T_{i}$ ($C_{i}=0$) due to negative profit. To maximize returns, the manager ensures selected entities have sufficient resources for task completion and minimizes entity selection costs. A policy $\pi(a|T,w)$ is learned to allocate entities to suitable tasks.

4 Methodology

The manager faces challenges in allocating entities to tasks. One challenge is the uncertainty in the number of tasks, making it difficult to allocate entities simultaneously. To address this, we propose setting the action dimension as $n\times M$, where $M$ denotes the maximum number of tasks. However, obtaining the precise value of $M$ in advance is challenging, and in most cases, the total number of tasks is smaller than the maximum number of tasks, which can result in wasted space. Another challenge is determining the task allocation order. Fixed order may result in suboptimal solutions, while simultaneous allocation makes it difficult to decide which task each entity should be assigned to. Additionally, the manager needs to consider the generalization problem, where entity costs and resources can vary. Most RL algorithms are unable to handle the issue of variable numbers of agents. The majority of RL algorithms typically assume a fixed environment, meaning a fixed number of agents. This assumption makes these algorithms ill-suited for handling problems with variable numbers of agents. For instance, when the number of agents dynamically changes, traditional reinforcement learning algorithms may struggle to adapt effectively because they often require a predefined number of agents and state spaces. Therefore, when the number of agents fluctuates, these algorithms may encounter difficulties, leading to degraded performance or failure to converge.

To address these challenges, we propose a two-stage approach for entity selection. We first propose a pre-allocation method where each entity is pre-assigned as a candidate for each task based on its attributes and the attributes of the tasks. This method avoids the drawbacks of sequential and random selection by enabling sequential allocation based on the fitness between tasks and entities. We have also demonstrated that this pre-allocation method outperforms sequential allocation methods in finding optimal solutions. Secondly, our proposed attention-based hyper network structure allows for the allocation of different network parameters to different numbers of entities, enabling the neural network to accommodate dynamic entity counts and addressing the generalization issue when the number of entities changes. It overcomes local convergence and entity overlap issues and handles generalization problems. We introduce worker entities as selfish agents to verify the allocation of entities with varying attributes. The overview of our method is depicted in Figure 1, while the architecture is illustrated in Figure 2.

4.1 Pre-assign Module

The pre-assign module initially allocates entities to suitable tasks. In discrete action space environments, each discrete number typically corresponds to an entity action. However, traditional RL algorithms focus on learning the likelihood of number occurrences in the current state, which limits their ability to effectively utilize information in task assignment problems. To leverage the individual attributes of each entity, we propose a Two-head Attention Module (TAM) based on attention mechanisms (Vaswani etal. (2017)). This module guides the manager in making pre-assigned allocations based on the compatibility between tasks and entities. It provides policy and assignment value outputs, and its network structure accommodates a variable number of input entities. We adopt Soft Actor-Critic method (SAC, Haarnoja etal. (2018)) as the base RL algorithm for modeling the manager. Since the action space for task allocation is discrete, we adopted the discrete version of the SAC algorithm (Christodoulou (2019)).

TAM consists of two heads: the actor head and the critic head. The actor head is responsible for generating the policy for the pre-assign actions, while the critic head calculates the value of these actions. The actor head consists of an entity embedding function $f^{h}:\mathbb{R}^{S}\rightarrow\mathbb{R}^{d}$, a task embedding function $f^{g}:\mathbb{R}^{S}\rightarrow\mathbb{R}^{d}$. Here, $S$ represents the dimension of the task and entity attributes. The entity embedding can be expressed as $\boldsymbol{h}_{i}=f^{h}(w_{i})$ and the task embedding can also be denoted as $\boldsymbol{g}_{i}=f^{g}(T_{i})$. The probability of each entity pre-assigning to each task is computed by an attention module, i.e., $\pi(T_{j}|w_{i})=\text{SoftMax}(\boldsymbol{h}_{i}^{T}\boldsymbol{g}_{j}/\sqrt{d})$. This method can solve the problem of a variable number of tasks with zero-shot training because when an unseen task $T_{u}$ occurs, we can compute the embedding $\boldsymbol{g}_{u}=f^{g}(T_{u})$ and then the probability of entity $w_{i}$ assigning task $T_{u}$ is $\pi(T_{u}|w_{i})=(\boldsymbol{h}_{i}^{T}\boldsymbol{g}_{u}/\sqrt{d})$. The pre-assign allocation of entity $w_{i}$ is $c_{i}$, which is sampled from the $\pi(T_{j}|w_{i})$. The total pre-assign allocation is $c=(c_{1},c_{2},...c_{n})$ where $c_{i}=k$ denotes that $w_{i}$ is pre-assigned to task $T_{k}$.

Due to the discrete nature of pre-assigned actions, a table can be created to record each action’s value. However, the table size ($2^{n}$) becomes impractical when $n$ is large, making it challenging to accurately approximate values with limited datasets. To address this, we adopt an approach inspired by the Q MIXing network (QMIX) Rashid etal. (2020), which employs a mixing network to compute the total Q value for multi-agent systems. In our approach, we calculate the value selected for each entity and consider the overall assigned value as a nonlinear aggregation of the individual entity values.In QMIX, each agent has a Q network that calculates the value of taking a particular action based on the current observations, resulting in a total of as many Q values as there are agents. Additionally, QMIX employs a hyper network that generates non-negative parameters for the neural network, combining each Q value to compute the overall Q value. For algorithm fine-tuning, we modify the attention mechanism by incorporating a critic head, similar in architecture to the actor head, to output action values. The critic component includes entity value embedding ($f^{o}$) and task value embedding ($f^{q}$) functions denoted as $\boldsymbol{o}_{i}=f^{o}(w_{i})$ and $\boldsymbol{q}_{i}=f^{q}(T_{i})$, respectively. The pre-assign value of $w_{j}$ to $T_{i}$ is computed using the dot product, $Q(w_{i},.)=\boldsymbol{o}_{i}^{T}\boldsymbol{q}$. The architecture of TAM is depicted in Figure 3.

When a pre-assigned action of an entity is sampled, we obtain a value from the critic’s component. In the case of having $n$ entities, we obtain $n$ values corresponding to the pre-assigned actions. However, since we interact with the environment throughout the entire pre-assign action, we only receive a single total reward from the environment, which does not align with the output of our critic. To address this disparity, we introduce the Attention MIXing (AMIX) module. The AMIX module utilizes a self-attention-based hypernetwork to generate parameters for its layers. Unlike QMIX, which provides network parameters for a fixed number of agents, AMIX’s hyperparameter network, called the Self-attention-based Hyper Network (SHN), utilizes an attention model. This allows it to dynamically adjust the number of parameters based on the input values, effectively accommodating the variable number of entities in the problem. For a visual representation of this concept, please refer to Figure 4.Using the aforementioned critic structure, we can calculate the value estimates for task allocation. According to the SAC algorithm, the actor loss can be expressed as:

$\displaystyle\mathcal{L}_{\text{actor}}(\theta)=\alpha\log\pi_{\theta}(\mathbf{c}|\mathbf{w})-Q_{\varphi}(\mathbf{w},\mathbf{c})$

After the allocation is complete, the critic is updated based on the reward values obtained from the interaction between the agent and the environment. The loss can be expressed as:

$\displaystyle\mathcal{L}_{\text{critic}}(\varphi)=\frac{1}{2}\left\|r(\mathbf{w},\mathbf{c})+\gamma\arg\max_{\mathbf{a}}Q_{\varphi}\left(\mathbf{w}^{\prime},\mathbf{a}\right)-Q_{\varphi}(\mathbf{w},\mathbf{a})\right\|^{2}$

Through the aforementioned loss, we can continuously update the critic network to estimate the reward values for the current allocation executed by all entities. This allows the actor network to output optimal task allocations.

5 Experiment

In this section, we try to answer these questions: (1) Is the pre-assign method more effective than the sequential task allocation method in avoiding finding local optimal solutions? (2) Can the algorithm solve the allocation problem when the cost of entities is dynamically changed based on the current task? (3) Can the algorithm provide a reasonable allocation for such a variable number of entities as their number increases and decreases? (4) Does our proposed method outperform heuristic algorithms?For all experimental environments, our two-stage method uses the same hyperparameters, with no parameters specifically set for each environment. For all network architectures, we use the ReLU function as the activation function and set the number of hidden units to 64, with each network consisting of a 3-layer MLP structure. More details on the parameter configurations of our method can be found in Table 3.

5.1 Retain the Almighty

This small experiment will answer the question (1) and demonstrate why using sequential selection methods can fall into local optimization and prove that using the pre-assign method is more effective.

In the Retain the Almighty environment, there are $N$ tasks and $n$ entities in this environment, and each task $T_{i}$ in this environment corresponds to a subset of the best entities $b_{i}$, and the task is completed if and only if a best entity $w\in b_{i}$ participates in this task. The last task $T_{N}$ is a difficult but rewarding task. The best entity of $b_{N}$ is $w_{o}$, which is an almighty agent that is able to finish every task, and the cost for it is the same as others. The best allocation is to arrange $w\in b_{i}$ to do $T_{i}$ and the task cannot choose the entities if the previous task has chosen them, which means the algorithm must retain the almighty to the last task to find a good solution. The result is shown in Figure 6.

It can be seen that the entity learned using the sequential method is getting trapped in the local optimum. The perfect entity $w_{o}$ is selected by the previous task and fails to complete the last task, resulting in a low total reward. When the order of the most difficult tasks is randomly assigned to the top, we can assign the Almighty to this task and obtain high profits; when the most difficult task is randomly assigned later, the rewards will sharply decrease. According to the training curve, the entity has not learned how to assign entities to appropriate tasks, and the final return of this entity is related to the random order of tasks instead of how well it learns to allocate entities to tasks. However, by using the pre-assign method, the manager is able to find the best solution because the task can be completed once the best entity is pre-assigned to the last task. The manager is able to allocate $w_{o}$ to $T_{N}$ to get a large reward and then find the optimal solution.

In fact, in this environment, we can suppose that without prior knowledge, all entities have the same probability of being selected when the algorithm does not start training. The probability upper bound of $w_{o}\in T_{N}$ by using the sequential method is $(\frac{n-1}{n+N-2})^{N-1}$. The probability upper bound decreases exponentially with the number of tasks. However, the probability of $w_{o}\in T_{N}$ by using the pre-assign method is $\frac{1}{N}$. The rate of probability decline is far less than that of the sequential method. See Appendix A for complete proof.

6 Conclusion

In our work, we propose a two-stage approach to solve the task allocation problem. Our approach starts by pre-assigning entities to tasks that they are good at, based on the similarity of each entity and task. We then select from the candidate entities in each task using a sequence model similar to point-net. The proposed TAM and AMIX network architectures can accommodate the changing number of tasks and entities and have the potential to achieve zero-shot and few-shot generalization to new tasks and unseen entities scenarios. Through a variety of experiments, we verify the effectiveness of our proposed two-stage task allocation approach and the validity of our proposed structure. We compared our algorithm with heuristic algorithms in multiple environments and found that our algorithm achieves better results, demonstrating the effectiveness of our approach. Additionally, we conducted generalization experiments by modifying the number of entities and tasks, as well as the associated resources and attributes. This validation confirms that our method can successfully address these challenges and achieve good generalization performance.

7 Limitation

A limitation of our method pertains to the prerequisite knowledge of task and entity attributes for efficient task allocation, which is highly justified in resource scheduling and delivery scenarios. However, in certain contexts, it becomes imperative to make reasonably estimated attributions for tasks and entities. For instance, within an enterprise, quantifying project complexity and required competencies, while conducting quantitative evaluations of employees, becomes indispensable to leverage our algorithm for task allocation. Encouragingly, this limitation can be overcome as certain task characteristics and entity observations are readily obtainable. By employing appropriate methods to extract task and entity features and employing them as attributes, these challenges can be effectively addressed.

\printcredits

References

• Abdullahi etal. (2023)Abdullahi, M., Ngadi, M.A., Dishing, S.I., Abdulhamid, S.M., 2023.An adaptive symbiotic organisms search for constrained task scheduling in cloud computing.Journal of ambient intelligence and humanized computing 14, 8839–8850.
• Afrin etal. (2023)Afrin, M., Jin, J., Rahman, A., Li, S., Tian, Y.C., Li, Y., 2023.Dynamic task allocation for robotic edge system resilience using deep reinforcement learning.IEEE Transactions on Systems, Man, and Cybernetics: Systems .
• Agrawal etal. (2023)Agrawal, A., Bedi, A.S., Manocha, D., 2023.Rtaw: An attention inspired reinforcement learning method for multi-robot task allocation in warehouse environments, in: 2023 IEEE International Conference on Robotics and Automation (ICRA), IEEE. pp. 1393–1399.
• Albert etal. (2023)Albert, P.W., Rönnqvist, M., Lehoux, N., 2023.Trends and new practical applications for warehouse allocation and layout design: a literature review.SN Applied Sciences 5, 378.
• Ali etal. (2021)Ali, H.S., Rout, R.R., Parimi, P., Das, S.K., 2021.Real-time task scheduling in fog-cloud computing framework for iot applications: A fuzzy logic based approach, in: 2021 International Conference on COMmunication Systems & NETworkS (COMSNETS), IEEE. pp. 556–564.
• Ali and Sridevi (2024)Ali, H.S., Sridevi, R., 2024.Mobility and security aware real-time task scheduling in fog-cloud computing for iot devices: a fuzzy-logic approach.The Computer Journal 67, 782–805.
• Alighanbari and How (2005)Alighanbari, M., How, J.P., 2005.Decentralized task assignment for unmanned aerial vehicles, in: Proceedings of the 44th IEEE Conference on Decision and Control, IEEE. pp. 5668–5673.
• Alkaabneh etal. (2021)Alkaabneh, F., Diabat, A., Gao, H.O., 2021.A unified framework for efficient, effective, and fair resource allocation by food banks using an approximate dynamic programming approach.Omega 100, 102300.
• Barbosa etal. (2023)Barbosa, V.L., Kniess, J., Parpinelli, R.S., 2023.Optimization of task allocation in edge computing to industrial internet with simulated annealing, in: Anais do XX Encontro Nacional de Inteligência Artificial e Computacional, SBC. pp. 1171–1185.
• Barboza and Kniess (2024)Barboza, V.G.R.L., Kniess, J., 2024.Task allocation based on simulated annealing for edge industrial internet, in: International Conference on Advanced Information Networking and Applications, Springer. pp. 210–221.
• Bellman (2010)Bellman, R.E., 2010.Dynamic programming.Princeton university press.
• Bertsimas and Tsitsiklis (1993)Bertsimas, D., Tsitsiklis, J., 1993.Simulated annealing.Statistical science 8, 10–15.
• Burkard etal. (2012)Burkard, R., Dell’Amico, M., Martello, S., 2012.Assignment problems: revised reprint.SIAM.
• Chen etal. (2023)Chen, J., Han, P., Liu, Y., Du, X., 2023.Scheduling independent tasks in cloud environment based on modified differential evolution.Concurrency and Computation: Practice and Experience 35, e6256.
• Chen etal. (2018)Chen, X., Zhang, P., Li, F., Du, G., 2018.A cluster first strategy for distributed multi-robot task allocation problem with time constraints, in: 2018 WRC Symposium on Advanced Robotics and Automation (WRC SARA), IEEE. pp. 102–107.
• Cheng and Prayogo (2014)Cheng, M.Y., Prayogo, D., 2014.Symbiotic organisms search: a new metaheuristic optimization algorithm.Computers & Structures 139, 98–112.
• Choudhury etal. (2022)Choudhury, S., Gupta, J.K., Kochenderfer, M.J., Sadigh, D., Bohg, J., 2022.Dynamic multi-robot task allocation under uncertainty and temporal constraints.Autonomous Robots 46, 231–247.
• Christodoulou (2019)Christodoulou, P., 2019.Soft actor-critic for discrete action settings.arXiv preprint arXiv:1910.07207 .
• Dahl etal. (2009)Dahl, T.S., Matarić, M., Sukhatme, G.S., 2009.Multi-robot task allocation through vacancy chain scheduling.Robotics and Autonomous Systems 57, 674–687.
• DeRyck etal. (2022)DeRyck, M., Pissoort, D., Holvoet, T., Demeester, E., 2022.Decentral task allocation for industrial agv-systems with routing constraints.Journal of Manufacturing Systems 62, 135–144.
• DeWeerdt etal. (2007)DeWeerdt, M., Zhang, Y., Klos, T., 2007.Distributed task allocation in social networks, in: Proceedings of the 6th international joint conference on autonomous agents and multiagent systems, pp. 1–8.
• DENG etal. (2023)DENG, F., HUANG, H., TAN, C., FU, L., ZHANG, J., LAM, T., 2023.Multi-robot task allocation algorithm combining genetic algorithm and rolling scheduling.Journal of Computer Applications 43, 3833.
• Elango etal. (2011)Elango, M., Nachiappan, S., Tiwari, M.K., 2011.Balancing task allocation in multi-robot systems using k-means clustering and auction based mechanisms.Expert Systems with Applications 38, 6486–6491.
• Forrest (1996)Forrest, S., 1996.Genetic algorithms.ACM computing surveys (CSUR) 28, 77–80.
• Fu etal. (2023a)Fu, X., Sun, Y., Wang, H., Li, H., 2023a.Task scheduling of cloud computing based on hybrid particle swarm algorithm and genetic algorithm.Cluster Computing 26, 2479–2488.
• Fu etal. (2023b)Fu, Y., Shen, Y., Tang, L., 2023b.A dynamic task allocation framework in mobile crowd sensing with d3qn.Sensors 23, 6088.
• Geng etal. (2021)Geng, N., Chen, Z., Nguyen, Q.A., Gong, D., 2021.Particle swarm optimization algorithm for the optimization of rescue task allocation with uncertain time constraints.Complex & Intelligent Systems 7, 873–890.
• Gharehchopogh etal. (2020)Gharehchopogh, F.S., Shayanfar, H., Gholizadeh, H., 2020.A comprehensive survey on symbiotic organisms search algorithms.Artificial Intelligence Review 53, 2265–2312.
• Ghassemi and Chowdhury (2022)Ghassemi, P., Chowdhury, S., 2022.Multi-robot task allocation in disaster response: Addressing dynamic tasks with deadlines and robots with range and payload constraints.Robotics and Autonomous Systems 147, 103905.
• Giordani etal. (2010)Giordani, S., Lujak, M., Martinelli, F., 2010.A distributed algorithm for the multi-robot task allocation problem, in: Trends in Applied Intelligent Systems: 23rd International Conference on Industrial Engineering and Other Applications of Applied Intelligent Systems, IEA/AIE 2010, Cordoba, Spain, June 1-4, 2010, Proceedings, Part I 23, Springer. pp. 721–730.
• Guo etal. (2024)Guo, H., Miao, Z., Ji, J., Pan, Q., 2024.An effective collaboration evolutionary algorithm for multi-robot task allocation and scheduling in a smart farm.Knowledge-Based Systems , 111474.
• Haarnoja etal. (2018)Haarnoja, T., Zhou, A., Abbeel, P., Levine, S., 2018.Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor, in: International conference on machine learning, PMLR. pp. 1861–1870.
• Han etal. (2022)Han, W., Xu, J., Sun, Z., Liu, B., Zhang, K., Zhang, Z., Mei, X., 2022.Digital twin-based automated guided vehicle scheduling: a solution for its charging problems.Applied Sciences 12, 3354.
• Holland (1992)Holland, J.H., 1992.Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence.MIT press.
• Hyland and Mahmassani (2018)Hyland, M., Mahmassani, H.S., 2018.Dynamic autonomous vehicle fleet operations: Optimization-based strategies to assign avs to immediate traveler demand requests.Transportation Research Part C: Emerging Technologies 92, 278–297.
• Jamil etal. (2023)Jamil, B., Ijaz, H., Shojafar, M., Munir, K., 2023.Irats: A drl-based intelligent priority and deadline-aware online resource allocation and task scheduling algorithm in a vehicular fog network.Ad hoc networks 141, 103090.
• Jamil etal. (2022)Jamil, B., Ijaz, H., Shojafar, M., Munir, K., Buyya, R., 2022.Resource allocation and task scheduling in fog computing and internet of everything environments: A taxonomy, review, and future directions.ACM Computing Surveys (CSUR) 54, 1–38.
• Javanmardi etal. (2023)Javanmardi, S., Shojafar, M., Mohammadi, R., Persico, V., Pescapè, A., 2023.S-fos: A secure workflow scheduling approach for performance optimization in sdn-based iot-fog networks.Journal of Information Security and Applications 72, 103404.
• Jebara (2001)Jebara, T., 2001.Discriminative, generative and imitative learning.Ph.D. thesis. PhD thesis, Media laboratory, MIT.
• Johannsmeier and Haddadin (2016)Johannsmeier, L., Haddadin, S., 2016.A hierarchical human-robot interaction-planning framework for task allocation in collaborative industrial assembly processes.IEEE Robotics and Automation Letters 2, 41–48.
• Kalimuthu and Thomas (2024)Kalimuthu, R., Thomas, B., 2024.Design of a multi-constraint pso for resource allocation and task scheduling.International Journal of Intelligent Systems and Applications in Engineering 12, 426–440.
• Karami etal. (2020)Karami, H., Darvish, K., Mastrogiovanni, F., 2020.A task allocation approach for human-robot collaboration in product defects inspection scenarios, in: 2020 29th IEEE International Conference on Robot and Human Interactive Communication (RO-MAN), IEEE. pp. 1127–1134.
• Kennedy and Eberhart (1995)Kennedy, J., Eberhart, R., 1995.Particle swarm optimization, in: Proceedings of ICNN’95-international conference on neural networks, ieee. pp. 1942–1948.
• Lawler and Wood (1966)Lawler, E.L., Wood, D.E., 1966.Branch-and-bound methods: A survey.Operations research 14, 699–719.
• Li etal. (2017)Li, Z., Li, X., etal., 2017.Research on model and algorithm of task allocation and path planning for multi-robot.Open Journal of Applied Sciences 7, 511.
• Lillicrap etal. (2015)Lillicrap, T.P., Hunt, J.J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., Wierstra, D., 2015.Continuous control with deep reinforcement learning.arXiv preprint arXiv:1509.02971 .
• Liu etal. (2017)Liu, S., Kurniawan, E., Tan, P.H., Zhang, P., Sun, S., Ye, S., 2017.Dynamic scheduling for heterogeneous resources with time windows and precedence relation, in: TENCON 2017-2017 IEEE Region 10 Conference, IEEE. pp. 3045–3050.
• Martin etal. (2021)Martin, J.G., Frejo, J.R.D., García, R.A., Camacho, E.F., 2021.Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms.Intelligent Service Robotics 14, 707–727.
• Martin etal. (2023)Martin, J.G., Muros, F.J., Maestre, J.M., Camacho, E.F., 2023.Multi-robot task allocation clustering based on game theory.Robotics and Autonomous Systems 161, 104314.
• Merlo etal. (2023)Merlo, E., Lamon, E., Fusaro, F., Lorenzini, M., Carfì, A., Mastrogiovanni, F., Ajoudani, A., 2023.An ergonomic role allocation framework for dynamic human–robot collaborative tasks.Journal of Manufacturing Systems 67, 111–121.
• Mitiche etal. (2019)Mitiche, H., Boughaci, D., Gini, M., 2019.Iterated local search for time-extended multi-robot task allocation with spatio-temporal and capacity constraints.Journal of Intelligent Systems 28, 347–360.
• Morariu etal. (2020)Morariu, C., Morariu, O., Răileanu, S., Borangiu, T., 2020.Machine learning for predictive scheduling and resource allocation in large scale manufacturing systems.Computers in Industry 120, 103244.
• Msala etal. (2023)Msala, Y., Hamed, O., Talea, M., Aboulfatah, M., 2023.A new method for improving the fairness of multi-robot task allocation by balancing the distribution of tasks.Journal of Robotics and Control (JRC) 4, 743–753.
• Munkres (1957)Munkres, J., 1957.Algorithms for the assignment and transportation problems.Journal of the society for industrial and applied mathematics 5, 32–38.
• Muthusamy and Chandran (2021)Muthusamy, G., Chandran, S.R., 2021.Cluster-based task scheduling using k-means clustering for load balancing in cloud datacenters.Journal of Internet Technology 22, 121–130.
• Page etal. (2010)Page, A.J., Keane, T.M., Naughton, T.J., 2010.Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system.Journal of parallel and distributed computing 70, 758–766.
• Papoudakis etal. (2020)Papoudakis, G., Christianos, F., Schäfer, L., Albrecht, S.V., 2020.Benchmarking multi-agent deep reinforcement learning algorithms in cooperative tasks.arXiv preprint arXiv:2006.07869 .
• Parasuraman etal. (1996)Parasuraman, R., Mouloua, M., Molloy, R., 1996.Effects of adaptive task allocation on monitoring of automated systems.Human factors 38, 665–679.
• Park etal. (2021)Park, B., Kang, C., Choi, J., 2021.Cooperative multi-robot task allocation with reinforcement learning.Applied Sciences 12, 272.
• Patel etal. (2020)Patel, R., Rudnick-Cohen, E., Azarm, S., Otte, M., Xu, H., Herrmann, J.W., 2020.Decentralized task allocation in multi-agent systems using a decentralized genetic algorithm, in: 2020 IEEE International Conference on Robotics and Automation (ICRA), IEEE. pp. 3770–3776.
• Qingtian (2021)Qingtian, H., 2021.An application of improved pso algorithm in cooperative search task allocation, in: 2021 IEEE International Conference on Power Electronics, Computer Applications (ICPECA), IEEE. pp. 580–583.
• Quinton etal. (2023)Quinton, F., Grand, C., Lesire, C., 2023.Market approaches to the multi-robot task allocation problem: a survey.Journal of Intelligent & Robotic Systems 107, 29.
• Rashid etal. (2020)Rashid, T., Samvelyan, M., DeWitt, C.S., Farquhar, G., Foerster, J., Whiteson, S., 2020.Monotonic value function factorisation for deep multi-agent reinforcement learning.The Journal of Machine Learning Research 21, 7234–7284.
• Samiei and Sun (2020)Samiei, A., Sun, L., 2020.Distributed recursive hungarian-based approaches to fast task allocation for unmanned aircraft systems, in: AIAA Scitech 2020 Forum, p. 0658.
• Samiei and Sun (2023)Samiei, A., Sun, L., 2023.Distributed matching-by-clone hungarian-based algorithm for task allocation of multi-agent systems.IEEE Transactions on Robotics .
• Sanaj and Prathap (2020)Sanaj, M., Prathap, P.J., 2020.Nature inspired chaotic squirrel search algorithm (cssa) for multi objective task scheduling in an iaas cloud computing atmosphere.Engineering Science and Technology, an International Journal 23, 891–902.
• Sarkar etal. (2018)Sarkar, C., Paul, H.S., Pal, A., 2018.A scalable multi-robot task allocation algorithm, in: 2018 IEEE International Conference on Robotics and Automation (ICRA), IEEE. pp. 5022–5027.
• Schneider etal. (2017)Schneider, E., Sklar, E.I., Parsons, S., 2017.Mechanism selection for multi-robot task allocation, in: Towards Autonomous Robotic Systems: 18th Annual Conference, TAROS 2017, Guildford, UK, July 19–21, 2017, Proceedings 18, Springer. pp. 421–435.
• Sharma etal. (2023)Sharma, D.K., Mishra, J., Singh, A., Govil, R., Singh, K.K., Singh, A., 2023.Optimized resource allocation in iot using fuzzy logic and bio-inspired algorithms.Wireless Personal Communications 131, 1393–1413.
• Sheikh etal. (2023)Sheikh, M.S., Enam, R.N., Qureshi, R.I., 2023.Machine learning-driven task scheduling with dynamic k-means based clustering algorithm using fuzzy logic in fog environment.Frontiers in Computer Science 5, 1293209.
• Singh (2021)Singh, P., 2021.Scheduling tasks based on branch and bound algorithm in cloud computing environment, in: 2021 8th International Conference on Signal Processing and Integrated Networks (SPIN), IEEE. pp. 41–46.
• Su etal. (2018)Su, X., Wang, Y., Jia, X., Guo, L., Ding, Z., 2018.Two innovative coalition formation models for dynamic task allocation in disaster rescues.Journal of Systems Science and Systems Engineering 27, 215–230.
• Sun etal. (2021)Sun, G., Cong, Y., Dong, J., Liu, Y., Ding, Z., Yu, H., 2021.What and how: generalized lifelong spectral clustering via dual memory.IEEE transactions on pattern analysis and machine intelligence 44, 3895–3908.
• Sun and He (2023)Sun, Y., He, Q., 2023.Joint task offloading and resource allocation for multi-user and multi-server mec networks: A deep reinforcement learning approach with multi-branch architecture.Engineering Applications of Artificial Intelligence 126, 106790.
• Sun etal. (2023)Sun, Z., Sun, G., Liu, Y., Wang, J., Cao, D., 2023.Bargain-match: A game theoretical approach for resource allocation and task offloading in vehicular edge computing networks.IEEE Transactions on Mobile Computing .
• Sutton etal. (1998)Sutton, R.S., Barto, A.G., etal., 1998.Introduction to reinforcement learning. volume 135.MIT press Cambridge.
• Talebpour and Martinoli (2018)Talebpour, Z., Martinoli, A., 2018.Multi-robot coordination in dynamic environments shared with humans, in: 2018 IEEE International Conference on Robotics and Automation (ICRA), IEEE. pp. 4593–4600.
• Tang etal. (2021)Tang, H., Wang, A., Xue, F., Yang, J.X., Cao, Y., 2021.A novel hierarchical soft actor-critic algorithm for multi-logistics robots task allocation.IEEE Access PP, 1–1.
• Truong etal. (2020)Truong, K.H., Nallagownden, P., Elamvazuthi, I., Vo, D.N., 2020.A quasi-oppositional-chaotic symbiotic organisms search algorithm for optimal allocation of dg in radial distribution networks.Applied Soft Computing 88, 106067.
• Tsang etal. (2018)Tsang, K.F.E., Ni, Y., Wong, C.F.R., Shi, L., 2018.A novel warehouse multi-robot automation system with semi-complete and computationally efficient path planning and adaptive genetic task allocation algorithms, in: 2018 15th International Conference on Control, Automation, Robotics and Vision (ICARCV), IEEE. pp. 1671–1676.
• Tuck etal. (2024)Tuck, V.M., Chen, P.W., Fainekos, G., Hoxha, B., Okamoto, H., Sastry, S.S., Seshia, S.A., 2024.Smt-based dynamic multi-robot task allocation.arXiv preprint arXiv:2403.11737 .
• Ullah and Nawi (2023)Ullah, A., Nawi, N.M., 2023.An improved in tasks allocation system for virtual machines in cloud computing using hbac algorithm.Journal of Ambient Intelligence and Humanized Computing 14, 3713–3726.
• Vaswani etal. (2017)Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A.N., Kaiser, Ł., Polosukhin, I., 2017.Attention is all you need.Advances in neural information processing systems 30.
• Vinyals etal. (2015)Vinyals, O., Fortunato, M., Jaitly, N., 2015.Pointer networks.Advances in neural information processing systems 28.
• Wang etal. (2021)Wang, G., Zhang, G., Guo, X., Zhang, Y., 2021.Digital twin-driven service model and optimal allocation of manufacturing resources in shared manufacturing.Journal of Manufacturing Systems 59, 165–179.
• Wang etal. (2023)Wang, L., Zhu, D., Pang, W., Zhang, Y., 2023.A survey of underwater search for multi-target using multi-auv: Task allocation, path planning, and formation control.Ocean Engineering 278, 114393.
• Wang etal. (2020)Wang, X., Ning, Z., Guo, S., Wang, L., 2020.Imitation learning enabled task scheduling for online vehicular edge computing.IEEE Transactions on Mobile Computing 21, 598–611.
• Wang etal. (2022)Wang, Y., Shi, Y., Liu, Y., 2022.Research on improved genetic simulated annealing algorithm for multi-uav cooperative task allocation, in: Journal of Physics: Conference Series, IOP Publishing. p. 012081.
• Wang and Wu (2023)Wang, Z., Wu, Y., 2023.An ant colony optimization-simulated annealing algorithm for solving a multiload agvs workshop scheduling problem with limited buffer capacity.Processes 11, 861.
• Wen and Ma (2024)Wen, C., Ma, H., 2024.An indicator-based evolutionary algorithm with adaptive archive update cycle for multi-objective multi-robot task allocation.Neurocomputing , 127836.
• Wu etal. (2023)Wu, Y., Xu, S., Dai, W., Lin, L., 2023.Heuristic position allocation methods for forming multiple uav formations.Engineering Applications of Artificial Intelligence 118, 105654.
• Xu and Song (2023)Xu, C., Song, W., 2023.Intelligent task allocation for mobile crowdsensing with graph attention network and deep reinforcement learning.IEEE Transactions on Network Science and Engineering 10, 1032–1048.
• Xu etal. (2023)Xu, Y., Li, X., Li, Q., 2023.A discrete teaching–learning based optimization algorithm with local search for rescue task allocation and scheduling.Applied Soft Computing 134, 109980.
• Yan and Di (2023)Yan, F., Di, K., 2023.Solving the multi-robot task allocation with functional tasks based on a hyper-heuristic algorithm.Applied Soft Computing 146, 110628.
• Yan etal. (2012)Yan, Z., Jouandeau, N., Ali-Chérif, A., 2012.Multi-robot heuristic goods transportation, in: 2012 6th IEEE International Conference Intelligent Systems, IEEE. pp. 409–414.
• Ye etal. (2020)Ye, F., Chen, J., Tian, Y., Jiang, T., 2020.Cooperative task assignment of a heterogeneous multi-uav system using an adaptive genetic algorithm.Electronics 9, 687.
• Yuvaraj etal. (2021)Yuvaraj, N., Karthikeyan, T., Praghash, K., 2021.An improved task allocation scheme in serverless computing using gray wolf optimization (gwo) based reinforcement learning (ril) approach.Wireless Personal Communications 117, 2403–2421.
• Zhang etal. (2021)Zhang, F., Mei, Y., Nguyen, S., Tan, K.C., Zhang, M., 2021.Multitask genetic programming-based generative hyperheuristics: A case study in dynamic scheduling.IEEE Transactions on Cybernetics 52, 10515–10528.
• Zhang etal. (2023)Zhang, L., Zhao, J., Lamon, E., Wang, Y., Hong, X., 2023.Energy efficient multi-robot task allocation constrained by time window and precedence.IEEE Transactions on Automation Science and Engineering .
• Zhang etal. (2020a)Zhang, Q., Gui, L., Hou, F., Chen, J., Zhu, S., Tian, F., 2020a.Dynamic task offloading and resource allocation for mobile-edge computing in dense cloud ran.IEEE Internet of Things Journal 7, 3282–3299.
• Zhang etal. (2020b)Zhang, T., Wang, Y., Liu, Y., Xu, W., Nallanathan, A., 2020b.Cache-enabling uav communications: Network deployment and resource allocation.IEEE Transactions on Wireless Communications 19, 7470–7483.
• Zhang etal. (2022)Zhang, Y., Zhu, H., Tang, D., Zhou, T., Gui, Y., 2022.Dynamic job shop scheduling based on deep reinforcement learning for multi-agent manufacturing systems.Robotics and Computer-Integrated Manufacturing 78, 102412.
• Zhang etal. (2024)Zhang, Z., Jiang, X., Yang, Z., Ma, S., Chen, J., Sun, W., 2024.Scalable multi-robot task allocation using graph deep reinforcement learning with graph normalization.Electronics 13, 1561.
• Zhao etal. (2023)Zhao, B., Dong, H., Wang, Y., Pan, T., 2023.A task allocation algorithm based on reinforcement learning in spatio-temporal crowdsourcing.Applied Intelligence 53, 13452–13469.
• Zhou etal. (2023)Zhou, Q., Qu, S., Wang, Q., She, Y., Yu, Y., Bi, J., 2023.Sliding window-based machine learning for environmental inspection resource allocation.Environmental Science & Technology 57, 16743–16754.
• Zhou etal. (2019)Zhou, X., Wang, H., Ding, B., Hu, T., Shang, S., 2019.Balanced connected task allocations for multi-robot systems: An exact flow-based integer program and an approximate tree-based genetic algorithm.Expert Systems with Applications 116, 10–20.

Appendix A Proof

The following is a proof of the probability upper bound of the sequential selection method. We define $w\in b_{a_{i}}$ as the set of entities which only belong to $b_{i}$, i.e., $w\in b_{a_{i}}\Leftrightarrow\forall i,j\neq i,w\in b_{i},w\notin b_{j}$. We denote $r_{i}=b_{i}\setminus b_{a_{i}}$. The number of entities in $b_{a_{i}}$ and $r_{i}$ is defined as $n_{a_{i}}$ and $n_{r_{i}}$. The summary of $n_{a_{i}}$ is less than $n-1$ and $n_{r_{i}}$ is bigger than 1 since $\forall i,w_{o}\in r_{i}$. We record the number of entities in $b_{a_{j}}$ who were mistakenly selected by $T_{i}$ as $m^{i}_{j}$. The probability of $w_{o}\in T_{N}$ is

The probability of $w_{o}\in T_{N}$ using pre-assign method is $\frac{1}{N}$ because we only need to make sure the pre-assign is correct.

Appendix B Algorithms

In this section, we give the pseudocode of the algorithms. Algorithm 1 is the main algorithm of our approach. It shows how we assign tasks based on given tasks and entities. Algorithm 2 corresponds to the pre-assign module mentioned in the main text, which is used to pre-assign entities as the candidates for all tasks. Algorithm 3 is the select module used to select and allocate entities for each task. We used Python and PyTorch framework to implement pseudo code.

Appendix C Experiment details

The hyperparameters of our approach are shown in Table 3.