hybrid task assignment

Hybrid User Based Task Assignment for Mobile Crowdsensing: Problem and Algorithm

Ieee account.

• Change Username/Password
• Update Address

Purchase Details

• Payment Options
• Order History
• View Purchased Documents

Profile Information

• Communications Preferences
• Profession and Education
• Technical Interests
• US & Canada: +1 800 678 4333
• Worldwide: +1 732 981 0060
• Contact & Support
• About IEEE Xplore
• Accessibility
• Terms of Use
• Nondiscrimination Policy
• Privacy & Opting Out of Cookies

A not-for-profit organization, IEEE is the world's largest technical professional organization dedicated to advancing technology for the benefit of humanity. © Copyright 2024 IEEE - All rights reserved. Use of this web site signifies your agreement to the terms and conditions.

Advertisement

HATMOG: an enhanced hybrid task assignment algorithm based on AHP-TOPSIS and multi-objective genetic in cloud computing

• Regular Paper
• Published: 09 January 2022
• Volume 104 , pages 1123–1154, ( 2022 )

Cite this article

• Sahar Samsam Shariat 1 &
• Behrang Barekatain   ORCID: orcid.org/0000-0001-5344-6282 1 , 2  

363 Accesses

7 Citations

Explore all metrics

In recent years, despite the rapid growth of cloud computing platforms, the technology confronts significant challenges including virtualization, load balancing, fault tolerance and most important of all, task scheduling. Considering the last challenge, because of high number of users and significant growth of number of tasks, there are some limitations such as MakeSpan, high resource utilization rate and executive costs in task scheduling algorithms. In this study, an effective method called HATMOG based on the smart hybrid of multiple criteria decision making algorithms of AHP-TOPSIS and Non-Dominated Sorting Genetic Algorithm (NSGAII) has been used to improve task scheduling in the cloud. The proposed method was done in two phases. In the first phase, the tasks which entered the cloud environment were placed in separate queues and then, according to task length, number of required processor elements and task expire time were sorted by AHP-TOPSIS algorithm in their priority queues. This phase helped on time assignment of more important tasks to the most appropriate virtual machines significantly that resulted in response time decrease and optimized resource utilization. In the second phase, the sorted tasks with prioritized queues were assigned to the appropriate virtual machines using NSGAII. Task assignment to virtual machine is an NP-Hard issue and NSGAII helped the efficiency improvement of cloud computing environment significantly because of the high convergence speed in finding close to optimal solution. The results of numerous simulations in Cloudism showed that the proposed method improved MakeSpan comparing TOPSIS-PSO, AHP-TOPSIS-PSO, NSGAII and PSO by 17.76, 155.73, 5.05 and 171.35 percent respectively and the average resource utilization by 15.94, 176.59, 4.83 and 176.65 percent respectively.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Price includes VAT (Russian Federation)

Instant access to the full article PDF.

Rent this article via DeepDyve

Institutional subscriptions

Similar content being viewed by others

A novel strategy for deterministic workflow scheduling with load balancing using modified min-min heuristic in cloud computing environment

Anjali Choudhary & Ranjit Rajak

Boosting white shark optimizer for global optimization and cloud scheduling problem

Reham R. Mostafa, Amit Chhabra, … Fatma A. Hashim

Optimizing Placement and Scheduling for VNF by a Multi-objective Optimization Genetic Algorithm

Phan Duc Thien, Fan Wu, … Ahmad Salah

Soltani B, Soleimani NN, Barekatain B (2017) Heuristic algorithms for task scheduling in cloud computing: a survey. J Comput Netw Inf Secur Int. https://doi.org/10.5815/ijcnis.2017.08.03

Article   Google Scholar  

Soltani B, Barekatain N, Neysiani BS (2016) Job scheduling based on single and multi objective meta- heuristic algorithms in cloud computing: a survey. Adv Comput

Senyo PK, Addae E, Boateng R (2018) Cloud computing research: a review of research themes, frameworks, methods and future research directions. Int J Inf Manage 38(1):128–139. https://doi.org/10.1016/j.ijinfomgt.2017.07.007

Abualigah L, Diabat A (2020) A novel hybrid antlion optimization algorithm for multi-objective task scheduling problems in cloud computing environments. Cluster Comput. https://doi.org/10.1007/s10586-020-03075-5

Shaw SB, Singh AK (2014) A survey on cloud computing, Proceeding IEEE Int. Conf. Green Comput. Commun. Electr. Eng. ICGCCEE 2014, no. (2014), https://doi.org/10.1109/ICGCCEE.2014.6921423

Singh S, Jeong YS, Park JH (2016) A survey on cloud computing security: issues, threats, and solutions. J Netw Comput Appl 75:200–222. https://doi.org/10.1016/j.jnca.2016.09.002

Arunarani AR, Manjula D, Sugumaran V (2019) Task scheduling techniques in cloud computing: a literature survey. Futur Gener Comput Syst 91:407–415. https://doi.org/10.1016/j.future.2018.09.014

Tom L, Bindu VR (2020) Task scheduling algorithms in cloud computing: a survey, in lecture notes in networks and systems, vol 98, S. Smys \(\bullet \) Robert Bestak, Ed. Springer, Switzerland, pp 342–350

Kumar M, Sharma SC, Goel A, Singh SP (2019) A comprehensive survey for scheduling techniques in cloud computing. J Netw Comput Appl 143(April):1–33. https://doi.org/10.1016/j.jnca.2019.06.006

Houssein EH, Gad AG, Wazery YM, Suganthan PN (2021) Task scheduling in cloud computing based on meta-heuristics: review, taxonomy, open challenges, and future trends. Swarm Evol Comput 62(2020):100841. https://doi.org/10.1016/j.swevo.2021.100841

Mapetu JPB, Chen Z, Kong L (2019) Low-time complexity and low-cost binary particle swarm optimization algorithm for task scheduling and load balancing in cloud computing. Appl Intell 49(9):3308–3330. https://doi.org/10.1007/s10489-019-01448-x

Li Y, Meili JT, Jin WS (2017) Improved FIFO scheduling algorithm based on fuzzy clustering in cloud computing. Information 8:25. https://doi.org/10.3390/info8010025

Ebadifard F, Babamir SM (2018) A PSO-based task scheduling algorithm improved using a load-balancing technique for the cloud computing environment. Concurr Comput 30(12):1–16. https://doi.org/10.1002/cpe.4368

Zhou Z, Chang J, Hu Z, Yu J, Li F (2018) A modified PSO algorithm for task scheduling optimization in cloud computing. Concurr. Comput. 30(24):1–11. https://doi.org/10.1002/cpe.4970

GNR Kumar SP (2019) Modified ant colony optimization algorithm for task scheduling in cloud computing systems (2019)

Liu CY, Zou CM, Wu P (2014) A task scheduling algorithm based on genetic algorithm and ant colony optimization in cloud computing, Proceedings of - 13th Int. Symp. Distrib. Comput. Appl. to Business, Eng. Sci. DCABES 2014, pp. 68–72 https://doi.org/10.1109/DCABES.2014.18

Senthil Kumar AM, Venkatesan M (2019) Multi-objective task scheduling using hybrid genetic-ant colony optimization algorithm in cloud environment. Wirel Pers Commun 107(4):1835–1848. https://doi.org/10.1007/s11277-019-06360-8

Khanmohammadi AE, Barekatain B, Quintana (2021) An enhanced AHP-TOPSIS-based clustering algorithm for high-quality live video streaming in flying ad hoc networks. J Supercomput 77:10664–10698. https://doi.org/10.1007/s11227-021-03645-3

Ider M, Barekatain B (2021) An enhanced AHP-TOPSIS-based load balancing algorithm for switch migration in software-defined networks. J Supercomput 77(1):563–596. https://doi.org/10.1007/s11227-020-03285-z

Agarwal M, Srivastava GMS (2017) A genetic algorithm inspired task scheduling in cloud computing, Proceeding - IEEE Int Conf Comput Commun Autom ICCCA 2016:364–367. https://doi.org/10.1109/CCAA.2016.7813746

Shukla DK, Kumar D, Kushwaha DS (2021) Task scheduling to reduce energy consumption and makespan of cloud computing using NSGA-II. Today Proc Mater. https://doi.org/10.1016/j.matpr.2020.11.556

Tawfeek M, El-Sisi A, Keshk A, Torkey F (2015) Cloud task scheduling based on ant colony optimization. Int Arab J Inf Technol 12(2):129–137

Google Scholar  

Sreelatha KSM (2017) W-Scheduler: whale optimization for task scheduling in cloud computing. Cluster Comput. https://doi.org/10.1007/s10586-017-1055-5

Mohammad Taisir Masadeh R, Abdel-Aziz Sharieh A, Mahafzah BA, Masadeh R, Sharieh A (2019) Humpback Whale Optimization Algorithm Based on Vocal Behavior for Task Scheduling in Cloud Computing, Int J Adv Sci Technol, no. May, [Online] . Available: www.ijast.org

Hemasian-Etefagh F, Safi-Esfahani F (2019) Dynamic scheduling applying new population grouping of whales meta-heuristic in cloud computing, 75(10). Springer, Berlin

Milan ST, Rajabion L, Darwesh A, Hosseinzadeh M, Navimipour NJ (2020) Priority-based task scheduling method over cloudlet using a swarm intelligence algorithm. Cluster Comput 23(2):663–671. https://doi.org/10.1007/s10586-019-02951-z

Prasanna Kumar KR, Kousalya K (2019) Amelioration of task scheduling in cloud computing using crow search algorithm. Neural Comput Appl. https://doi.org/10.1007/s00521-019-04067-2

Rajagopalan A, Modale DR, Senthilkumar R (2020) Optimal scheduling of tasks in cloud computing using hybrid firefly-genetic algorithm, pp 678–687 https://doi.org/10.1007/978-3-030-24318-0_77

Velliangiri S, Karthikeyan P, Arul Xavier VM, Baswaraj D (2021) Hybrid electro search with genetic algorithm for task scheduling in cloud computing. J., no. xxxx, Ain Shams Eng https://doi.org/10.1016/j.asej.2020.07.003

Senthil Kumar AM, Venkatesan M (2019) Task scheduling in a cloud computing environment using HGPSO algorithm. Cluster Comput 22:2179–2185. https://doi.org/10.1007/s10586-018-2515-2

Fu HL, Xueliang Sun Yang, Haifang Wang (2021) Task scheduling of cloud computing based on hybrid particle swarm algorithm and genetic algorithm. Cluster Comput. https://doi.org/10.1007/s10586-020-03221-z

Kodli S, Shilpa T (2021) Hybrid max-min genetic algorithm for load balancing and task scheduling in cloud environment, 14(1): 63–71, https://doi.org/10.22266/ijies2021.0228.07

Natesan G, Chokkalingam A (2020) Multi-objective task scheduling using hybrid whale genetic optimization algorithm in heterogeneous computing environment. Wirel Pers Commun 110(4):1887–1913. https://doi.org/10.1007/s11277-019-06817-w

Maheswari PU, Edwin EB, Thanka MR (2019) A hybrid algorithm for efficient task scheduling in cloud computing environment. Int J Reason Intell Syst 11(2):134. https://doi.org/10.1504/ijris.2019.10021325

Pradeep K, Jacob TP (2018) A hybrid approach for task scheduling using the cuckoo and harmony search in cloud computing. Wirel Pers Commun. https://doi.org/10.1007/s11277-018-5816-0

Prem Jacob T, Pradeep K (2019) A multi-objective optimal task scheduling in cloud environment using cuckoo particle swarm optimization. Wirel Pers Commun 109(1):315–331. https://doi.org/10.1007/s11277-019-06566-w

Chhabra A, Singh G, Kahlon KS (2020) Multi-criteria HPC task scheduling on IaaS cloud infrastructures using, vol 1. Springer, Berlin

Elaziz MA, Xiong S, Jayasena KPN, Li L (2019) Task scheduling in cloud computing based on hybrid moth search algorithm and differential evolution. Knowledge-Based Syst 169:39–52. https://doi.org/10.1016/j.knosys.2019.01.023

Panwar N, Negi S, Rauthan MMS, Vaisla KS (2019) TOPSIS-PSO inspired non-preemptive tasks scheduling algorithm in cloud environment. Cluster Comput 22(4):1379–1396. https://doi.org/10.1007/s10586-019-02915-3

Ben Alla H, Ben Alla S, Ezzati A (2016) An efficient dynamic priority-queue algorithm based on AHP and PSO for task scheduling in cloud computing, vol 1, no His, https://doi.org/10.1007/978-3-319-52941-7

Kumar Samriya J, Kumar N (2020) An optimal SLA based task scheduling aid of hybrid fuzzy TOPSIS-PSO algorithm in cloud environment. Today Proc., no. xxxx, Mater. https://doi.org/10.1016/j.matpr.2020.10.082

Samriya JK (2020) A QoS aware FTOPSIS-WOA based task scheduling algorithm with load balancing technique for the cloud computing environment. Indian J Sci Technol 13(35):3675–3684. https://doi.org/10.17485/ijst/v13i35.1314

Lu F, Jie Z, Guangquan R, Wu da (2007) Preface to multi-objective group decision-making: methods, software and applications with fuzzy set techniques, vol 6

Behzadian M, Khanmohammadi Otaghsara S, Yazdani M, Ignatius J (2012) A state-of the-art survey of TOPSIS applications. Expert Syst Appl 39(17):13051–13069. https://doi.org/10.1016/j.eswa.2012.05.056

Deb K, Pratap A, Agarwal S, Meyarivan T (2002) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans Evol Comput 6(2):182–197. https://doi.org/10.1109/4235.996017

Singh H, Tyagi S, Kumar P (2020) Scheduling in cloud computing environment using metaheuristic techniques: a survey, vol 937. Springer, Singapore

Awad AI, El-Hefnawy NA, Abdel-Kader HM (2015) Enhanced particle swarm optimization for task scheduling in cloud computing environments, Procedia Comput. Sci. 65(Iccmit):920–929. https://doi.org/10.1016/j.procs.2015.09.064

Ashouraei Mehran NJ, Khezr SN, Benlamri R, Navimipour (2018) A new SLA-aware load balancing method in the cloud using an improved parallel task scheduling algorithm, pp 71–76, https://doi.org/10.1109/FiCloud.2018.00018

Mansouri N, Mohammad Hasani Zade B, Javidi MM (2019) Hybrid task scheduling strategy for cloud computing by modified particle swarm optimization and fuzzy theory. Comput Ind Eng 130:597–633. https://doi.org/10.1016/j.cie.2019.03.006

Alworafi MA, Al-Hashmi A, Dhari A, Suresha Darem AB (2018) Task-scheduling in cloud computing environment: cost priority approach. Lect Notes Netw Syst 14:99–108. https://doi.org/10.1007/978-981-10-5146-3_10

Kumar P, Kumar R (2019) Issues and challenges of load balancing techniques in cloud computing: a survey. ACM Comput Surv. https://doi.org/10.1145/3281010

Lipowski A, Lipowska D (2012) Roulette-wheel selection via stochastic acceptance. Physica A 391(6):2193–2196. https://doi.org/10.1016/j.physa.2011.12.004

Goyal T, Singh A, Agrawa A (2012) Cloudsim: Simulator for cloud computing infrastructure and modeling. Procedia Eng 38:3566–3572. https://doi.org/10.1016/j.proeng.2012.06.412

Download references

Author information

Authors and affiliations.

Faculty of Computer Engineering, Najafabad Branch, Islamic Azad University, Najafabad, Iran

Sahar Samsam Shariat & Behrang Barekatain

Big Data Research Center, Najafabad Branch, Islamic Azad University, Najafabad, Iran

Behrang Barekatain

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Behrang Barekatain .

Additional information

Publisher's note.

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Samsam Shariat, S., Barekatain, B. HATMOG: an enhanced hybrid task assignment algorithm based on AHP-TOPSIS and multi-objective genetic in cloud computing. Computing 104 , 1123–1154 (2022). https://doi.org/10.1007/s00607-021-01049-y

Download citation

Received : 05 October 2021

Accepted : 17 December 2021

Published : 09 January 2022

Issue Date : May 2022

DOI : https://doi.org/10.1007/s00607-021-01049-y

Share this article

Anyone you share the following link with will be able to read this content:

Sorry, a shareable link is not currently available for this article.

Provided by the Springer Nature SharedIt content-sharing initiative

• Cloud computing
• Task scheduling
• Optimized utilization of cloud resources
• Load balancing

Mathematics Subject Classification

• Find a journal
• Publish with us
• Track your research

• Reference Manager
• Simple TEXT file

People also looked at

Original research article, research on a hybrid neural network task assignment algorithm for solving multi-constraint heterogeneous autonomous underwater robot swarms.

• Faculty of Robot Science and Engineering, Northeastern University, Shenyang, China

Studying the task assignment problem of multiple underwater robots has a broad effect on the field of underwater exploration and can be helpful in military, fishery, and energy. However, to the best of our knowledge, few studies have focused on multi-constrained underwater detection task assignment for heterogeneous autonomous underwater vehicle (AUV) clusters with autonomous decision-making capabilities, and the current popular heuristic methods have difficulty obtaining optimal cluster unit task assignment results. In this paper, a fast graph pointer network (FGPN) method, which is a hybrid of graph pointer network (GPN) and genetic algorithm, is proposed to solve the task assignment problem of detection/communication AUV clusters, and to improve the assignment efficiency on the basis of ensuring the accuracy of task assignment. A two-stage detection algorithm is used. First, the task nodes are clustered and pre-grouped according to the communication distance. Then, according to the clustering results, a neural network model based on graph pointer network is used to solve the local task assignment results. A large-scale cluster cooperative task assignment problem and a detection/communication cooperative work mode are proposed, which transform the cooperative cooperation problem of heterogeneous AUV clusters into a Multiple Traveling salesman problem (MTSP) for solving. We also conducted a large number of experiments to verify the effectiveness of the algorithm. The experimental results show that the solution efficiency of the method proposed in this paper is better than the traditional heuristic method on the scale of 300/500/750/1,000/1,500/2,000 task nodes, and the solution quality is similar to the result of the heuristic method. We hope that our ideas and methods for solving the large-scale cooperative task assignment problem can be used as a reference for large-scale task assignment problems and other related problems in other fields.

1. Introduction

With the development of underwater vehicle technology and information technology, new underwater detection needs are constantly emerging. Under the constraints of multi-agents, more challenges are emerging, and different scholars have focused on related research directions. The assignment of detection tasks is a relatively classic research direction when using AUV clusters to perform traversal detection of multiple points to be detected in underwater detection scenarios.

The task assignment of underwater detection robots can be divided into two types: dynamic task assignment and static task assignment, which correspond to different usage scenarios. When performing detection tasks on dynamic targets ( Page et al., 2010 ; Xie et al., 2018 ), the task allocation method of dynamic allocation is often used because the situation of the area to be detected is unknown at this time, detection tasks always appear, and tasks can only be allocated while exploring. Many scholars have focused in this topic. For example, MahmoudZadeh et al. (2018) proposed a hierarchical dynamic task planning framework for the problem of dynamic task assignment of AUVs within a limited time interval in a spatiotemporally changing marine environment. Bertuccelli et al. (2009) proposed a dynamic mission planning algorithm based on enhanced Consensus-Based Bundle Algorithm for multi-agent combat scenarios with noisy sensors. Capitan et al. (2016) proposed a dynamic task planning algorithm based on MDP (Markov Decision Process) for planning problems under multi-stage uncertainty. The above problems have no global information, and the task allocation will focus on factors, such as the robot's detection ability, communication delay, and energy allocation. When assigning static tasks ( Ferreira et al., 2007 ; Edison and Shima, 2011 ), the related problem is usually modeled as a traveling salesman problem. For example, Abbasi et al. (2022) proposed a heuristic fleet cooperation algorithm to solve the problem of sea star cluster processing. Hooshangi and Alesheikh (2017) explored a multi-agent task planning method combining interval number VIKOR and auction mechanism based on Contract Net Protocol is used to solve rescue problems in disaster environments. In addition, many scholars have used deep learning ( Vinyals et al., 2015 ; Bello et al., 2016 ; François-Lavet et al., 2016 ; Deudon et al., 2018 ; Kool et al., 2018 ; Holler et al., 2019 ; Solozabal et al., 2019 ) methods to solve the traveling salesman problem. The above work uses more capable surface and underwater ships to pre-scan the area to be detected, a more capable experimental platform to improve some of the above shortcomings in detection and energy consumption, and a multi-robot cluster to perform the detection task, but requires a large number of AUVs that can perform communication and detection tasks. The cost is high and the number is small. The number of task points allocated to each AUV is large, and the computational efficiency and detection efficiency of the task allocation algorithm are relatively low. Thus far, the underwater task detection task still faces many problems, and limited research has focused on task assignments for large-scale detection points in the pre-detection area using the heterogeneous AUV cluster combination of communication/detection.

Studying the task assignment problem of heterogeneous AUV cluster combinations for large-scale probe points can bring many benefits ( Zhu et al., 2020 ; Ru et al., 2021 ). In terms of energy consumption, the heterogeneous AUV combination performs its duties, which can provide smaller energy consumption and prolong the working time of the AUV cluster ( Zhu et al., 2017 ; Khan et al., 2022 ). In terms of task allocation efficiency, the AUV responsible for communication has strong computing power and can be equipped with deep learning modules. It can greatly improve the efficiency of task allocation ( Zhu et al., 2019 ; Khan and Li, 2022 ). In terms of economy, the types and performance of sensors configured by small robots that perform short-range detection tasks are weak, and the cost is low. It can be used in combination with large AUVs with strong detection capabilities to save costs ( Huang et al., 2014 ; Khan et al., 2021 ). In terms of detection efficiency, heterogeneous clusters can detect more detection points per unit time and increase the detection area per unit time ( Li et al., 2017 ).

Heterogeneous AUV cluster detection with detection/communication hybrid functions has many benefits but still faces the following challenges. First, the balance of robot task allocation is an issue considering that the number of points obtained by pre-detection increases with the increase of sensor capabilities and detection requirements. How to reasonably allocate detection points to each robot group is another challenge. The second is the cooperation between heterogeneous robots. Because the functions of heterogeneous robots are different, robots with functions such as detection and communication need to cooperate in the time and space domains, so the cooperation between heterogeneous robots is a challenge. Finally, the multi-robot task assignment problem is a typical NP-hard problem, and the efficient assignment of tasks is a challenge.

To overcome the above challenges, we propose a novel task assignment method suitable for solving heterogeneous AUV cluster combinations-Cluster-based hybrid solution method: This algorithm (i) proposes a detection point assignment method, (ii) designs a set of task assignment algorithm based on the fusion of GPN ( Ma et al., 2019 ) network and heuristic method, and (iii) proposes a heterogeneous AUV matching algorithm. The contributions of this paper are as follows:

(1) To our knowledge, this paper is the first to use the area detection algorithm in a large-scale underwater environment to be detected by using a heterogeneous segmentation method.

(2) A DBSCAN clustering equivalence algorithm based on communication distance constraints that can perform grouping equivalent processing on large-scale tasks is proposed.

(3) An improved task assignment method based on GPN network is also proposed, which can effectively replace the traditional heuristic algorithm to solve the TSP problem with fixed start and end points.

(4) A task coordination method for heterogeneous AUVs that can work under the common constraints of detection and communication for heterogeneous AUV systems is explored.

(5) We also carried out a large number of simulation experiments on virtual underwater pre-detection points, compared the effects of classical heuristic algorithms, and analyzed the combination of different numbers of robots to further verify the effectiveness and efficiency of the algorithm practicality.

2. Problem description

There are N target points tp i to be processed in a certain sea area, forming a set of tasks to be processed TP :

where tp i = { x, y }, x, y represents the location information of the target task point.

Existing M 1 communication units cu , and M 2 execution units eu constitute cluster unit U :

When the execution unit and the communication unit cooperate to access all task nodes, they should meet the communication constraint requirements, as shown in Equation (3), that is, the execution unit should be within the scope of the communication unit. In addition, the execution unit should also meet the requirements of its own capability constraints, as shown in Equation (4), that is, at the same time, the execution unit can only access at most one target task node. The specific constraints are as follows:

where C i,j indicates whether communication can be established between communication unit cu i and execution unit eu j , C i,j = 1 indicates that the communication unit can establish communication with the execution unit, and vice versa, d i,j represents the distance between the communication unit cu i and the execution unit eu j , and r represents the communication radius of the communication unit cu i .

where h ( eu j , tp i , t ) indicates whether the execution unit eu j accesses the target task point tp i at time t , the value of h ( eu j , tp i , t ) is 1 if the execution unit eu j visits the target task point tp i , and 0 otherwise.

In order to ensure the optimal result of the overall task assignment, this study takes the minimum moving distance as the optimization goal to optimize the entire task assignment process. The optimization goals are as follows:

where L c u i represents the total distance moved by the communication unit cu i , and L e u j represents the total distance moved by the execution unit eu j .

3. Cluster collaborative task assignment solution framework

The execution and the communication units need to cooperate to complete the processing of all task points, and a communication distance constraint between the execution and the communication units exists, limited by the current computing power level. Hence, it is difficult to directly solve the task assignment and solve it in a limited time. For optimal task assignment results, the process of solving the cluster cooperative task assignment problem in this paper is shown in the following Figure 1 .

Figure 1 . Flowchart for solving cluster collaborative task assignment. (A) Perform equivalent clustering on all task nodes, and generate several task cluster units after clustering. (B) Perform global task assignment of execution units and communication units according to the equivalent clustering results. (C) According to The result of the global task assignment is to assign tasks to the communication unit and the execution unit within the task cluster.

Module A means to perform equivalent clustering on all task points, module B means to plan the order in which the execution unit and communication unit access each task cluster according to the clustering result, module C means to allocate within each task cluster according to the global task allocation result local tasks.

3.1. Target task point clustering grouping

Considering the influence of communication constraints, the execution unit must select executable task points near the communication unit. At the same time, when the task scale becomes larger, the overall optimization will become more complicated. Therefore, consider grouping tasks first through communication distance constraints, and then, large-scale tasks and resource allocation planning problems become local small-scale problems, thereby reducing the amount of computation. The grouping method adopts the DBSCAN method to group the task points:

where g i = { tp 1 , tp 2 , …, tp l } indicates that the task cluster g i has l target task points, and k represents the number of task clusters after clustering.

First, according to the distribution of target task points tp i in the task cluster group g i , it is equivalently converted into a node, and then the equivalent approximation is made to the moving distance and time consuming of the execution unit eu j to complete the task cluster.

Task cluster g i equivalent node E x,y ( g i ) location coordinates is as follow:

where f r ( g i ) represents the center coordinates of the smallest covering circle containing all target task points tp i in the task cluster g i .

The equivalent approximate moving distance E d of the execution unit after visiting all target task point tp i in the task cluster g i is as follow:

The equivalent approximate time E t for the execution unit to complete the task cluster g i is as follows:

where v ̄ represents the average expected speed of execution unit.

3.2. Global task assignment

3.2.1. execution unit task assignment.

According to the clustering and grouping results g i , the global task assignment problem of execution units can be transformed into a multi-travel salesman problem with fixed start and end nodes. Genetic algorithm is used to solve the optimal task cluster access sequence of each execution unit eu j , and the minimum moving data distance is used as the The optimization objective of the problem optimizes the task assignment results. The specific form of the optimization goal is as follows:

3.2.2. Communication unit task assignment

The communication unit needs to cooperate with the execution unit to complete the processing of task points and assign tasks to the communication unit according to the global planning result of the execution unit. The time required by the execution unit to process each task cluster also varies because of the different number of tasks in each task cluster. Therefore, the following time constraints exist for the communication unit to reach each task cluster node:

where w j = max(0, e i − a j ), a j is the time when the communication unit arrives at the task cluster node, w j is the waiting time of the communication unit, e i,j is the time when the ith execution unit starts to execute the jth node, and Δ i,j is the time when the communication unit arrives from node i to node j.

The global task assignment problem of communication units can be equivalently transformed into a multi-travel salesman problem with time windows. In order to ensure that the optimal task assignment results of communication units are obtained, this paper takes the minimum moving distance of communication units as the optimization objective, and adopts genetic The algorithm solves the problem. The optimization goal is defined as:

3.3. Local task assignment

During the execution of the task, the communication unit does not participate directly in the processing of the task point and is only responsible for completing the communication with the execution unit, that is, it does not need to reach the task point. In group task planning, a genetic algorithm is used to plan tasks for execution units, and then tasks are planned for communication units according to the results of task planning for execution units.

3.3.1. Execution unit local task planning

The local task assignment problem of the execution unit belongs to the traveling salesman problem with fixed start and end points. In this paper, the deep learning method based on the GPN model ( Ma et al., 2019 ) is used to solve the local task assignment problem. The model structure is shown in the Figure 2 .

Figure 2 . GPN network structure model diagram.

The encoding part of the model is divided into node feature information encoding and neighbor node information encoding. The node location feature information is encoded through the LSTM network, thereby mapping the node feature information from the low-dimensional space to the high-dimensional space. According to the encoding vector of the location features of each node by LSTM, the node neighbor information encoding part aggregates and encodes the neighbor information of each node through the GraphSAGE network, so as to obtain the feature information between the node and other nodes. The network form of each layer of the neighbor node information encoding network is as follows:

In the formula, T i l represents the l − th task node of the layer, γ is a trainable weight matrix, Θ ∈ ℝ d l - 1 * d l is a trainable weight matrix, R θ represents the aggregation function, and N ( i ) represents the k adjacent task nodes T i .

The decoder part encodes the node feature information and the neighbor node feature information to obtain the high-dimensional feature vector of the node and the high-dimensional feature vector of the neighbor node and send it to the attention network model to obtain the pointer vector u i , which is then passed to the softmax layer, using to generate the probability distribution P i of the next node to visit.

3.3.2. Local task planning of communication unit

Because the communication unit does not need to reach the task location point, virtual nodes v x, y are added according to the task location point processed by the execution unit to plan the access node location of the communication unit. The types of virtual node additions are as follows Figure 3 .

Figure 3 . Schematic diagram of virtual node types.

Single virtual nodemodel. When all target task points tp i in the task cluster g i are within the communication range of the communication unit cu i that executes the task cluster, the virtual node v x, y is defined as:

The above formula indicates that the coordinates of the virtual node v x,y at this time are the center coordinates of the smallest covering circle containing all target task points in the task cluster g i .

Multiple virtual nodes model. When some target task points tp j in the task cluster g i are all within the communication range of the communication unit cu i executing the task cluster, the task points of the current task group are grouped twice according to the order of the execution unit eu j executing the task nodes.

where g i ′ = { t p j | d i , j ≤ r } , g i ′ represents a new small task cluster formed by re-clustering the task points tp i in the task cluster unit g i according to the communication range of the communication unit cu i , a represents the number of new task clusters generated by secondary clustering of the task cluster. At this point the virtual node looks like this:

To sum up, for the task assignment problem of underwater autonomous vehicles in multi-heterogeneous clusters, firstly, clustering is performed according to the location information of all task nodes, and the clustering results are equivalently approximated, and then the global tasks of the execution units are assigned. The problem is transformed into a multi-travel salesman problem to solve, and the communication unit task cooperative assignment problem is transformed into a multi-travel salesman problem with a time window to solve. Task allocation, the specific method is: the task allocation problem of the execution unit is transformed into the traveling salesman problem, which is solved by the deep learning method based on GPN, and the communication unit performs local task allocation by adding virtual nodes. The notation used in the design is summarized in Table 5 .

4. Experiment

This paper uses an NVIDIA RTX2080 GPU to train the FGPN model, limited by memory size constraints. The training batch size is B = 50, the tsp scale size is size = 60, and 1,000 rounds of training are performed. The training time for each round is about 3 min. The rest of the algorithms are implemented based on MATLAB2019, and the device CPU model is Intel (R) Core (TM) i7-6500U@2.50GHz.

Experiment 1: Comparison of task allocation algorithms for individual execution unit eu in target task nodes tp of different scales in the 1*1 km area. The results are shown in Table 1 .

Table 1 . Compare the task assignments of target nodes with fixed start and end points of different sizes in the 1*1 km area.

It can be seen from Figure 4 that the number of TP is less than 20, the solution results based on the deep learning method are similar in quality to the results obtained by GA, and the solution time is roughly the same; when the number of task nodes is greater than 20, the solution time is roughly the same. The quality of the solution based on the deep learning method is better than that of the GA solution. When the number of task nodes is greater than 40, the quality of the solution is improved by more than 30%. Moreover, when the number of task nodes is greater than 20, the quality of the solution is roughly under the same conditions, and the solution efficiency based on deep learning is better than that of GA. When the scale of task nodes is greater than 40, the solution efficiency is improved by about 70%.

Figure 4 . Comparison of solution times for the number of target task nodes at different scales. (A) Comparison of solution speed between GA algorithm and FGPN method when the solution results are similar. (B) Comparison of the solution results of the GA algorithm and the FGPN method when the solution speed is similar.

Experiment 2: Comparison of results of task assignment methods based on the DBSCAN clustering method. Let the area size be 10*10km, the number of execution unit eu is 3, the number of communication unit cu is 2, the communication distance is 300 m, the movement speed of the execution unit is 2 m / s , and the movement speed of the communication unit is 3 to 5 m/s. The results are shown in Tables 2 – 4 .

Table 2 . The relationship between the solution time and the total moving distance and the scale of the task nodes when the number of target task nodes in the task cluster is about 40. The unit of total Len. in the table is 10 6 m , and the unit of Time is seconds.

Table 3 . The relationship between the solution time and the total moving distance and the scale of the task nodes when the number of target task nodes in the task cluster is about 50. The unit of total Len. in the table is 10 6 m , and the unit of Time is seconds.

Table 4 . The relationship between the solution time and the total moving distance and the scale of the task nodes when the number of target task nodes in the task cluster is about 60. The unit of total Len. in the table is 10 6 m , and the unit of Time is seconds.

Table 5 . Variable explanation table.

Taking 1,000 task nodes in a 10*10 km area as an example, the overall task planning results are shown in the following figures.

The experimental results indicate that in the 10*10 km area when the number of TP is between 300 and 500, as shown in Figures 5 , 6 , the solution time based on the deep learning method is similar to the total moving distance based on the solution result of the genetic algorithm, and the solution speed is increased by about 50%. When the task scale is greater than 500, the solution efficiency based on the deep learning method is better than that based on the genetic algorithm. When the total moving distance obtained by the solution remains similar, the solution speed is increased by more than 70%. Meanwhile, when the number of task nodes in the task cluster increases, the time spent to solve the relative optimal solution of the current scale task is relatively reduced, and when the scale of task nodes is greater than 1,500, it increases by about 20%. In addition, the solution efficiency of the BAS (Beetle Antennae Search Algorithm) is roughly similar to that of our proposed method, but the solution result is far worse than the genetic-based method and the method proposed in this paper. Experiments show that the method proposed in this paper can greatly improve the efficiency of solving large-scale cluster coordination problems.

Figure 5 . Comparison between the solution time of the three methods and the scale of task nodes when the number of target task nodes in the task cluster is 40/50/60.

Figure 6 . Comparison between the total length of the three methods and the scale of task nodes when the number of target task nodes in the task cluster is 40/50/60.

Figures 7 , 8 , respectively, show the situation of three execution units traversing 1,000 task nodes and two communication units traversing virtual nodes cooperatively. Figure 9 shows the sequence of cooperative access to all target task nodes by the execution unit and the communication unit. Each execution unit traverses all the task nodes in the graph in turn, and the communication unit synchronously plans to traverse the virtual nodes of the graph according to the order in which the execution units access the task nodes to jointly complete the entire task. It can be seen from the figure that the algorithm proposed in this paper can effectively solve the problem of communication constraints and cooperative task assignment of multiple heterogeneous clusters.

Figure 7 . Schematic diagram of the execution unit accessing node sequence when the number of target task nodes is 1,000.

Figure 8 . Schematic diagram of the communication unit cooperative access node sequence when the number of target task nodes is 1,000.

Figure 9 . Schematic diagram of the communication unit and the execution unit cooperating to access the target task points.

5. Conclusion

This paper proposes a deep learning method and a heuristic algorithm by adopting the idea of divide and conquer and the combination of global and local, aiming at the large task scale and complex coordination difficulties in the large-scale cooperative task assignment problem of multi-heterogeneous cluster units with communication distance constraints. The FGPN method proposed in this paper, which combines the clustering-based GPN and the genetic algorithm, can greatly improve the solution efficiency while ensuring that the solution results are similar to the genetic algorithm when the number of target task nodes is between 1,000 and 1,500. The experimental results show that the algorithm proposed in this paper can solve the problem of cooperative assignment of large-scale cluster tasks and can obtain relatively optimal task assignment results faster while ensuring that the quality of the solution is roughly the same as that of the traditional method. We will further explore the use of deep learning methods to solve the multi-traveling salesman problem with fixed start and end positions and the multi-traveling salesman problem with time windows in the future.

Data availability statement

The raw data supporting the conclusions of this article will be made available by the authors, without undue reservation.

Author contributions

JR contributed to the conception of the study and contributed significantly to analysis and manuscript preparation. DH performed the experiment and performed the data analyses and wrote the manuscript. XZ, HX, and ZJ helped perform the analysis with constructive discussions. All authors contributed to the article and approved the submitted version.

This research was funded by the National Natural Science Foundation of China (61872073 and 62203099), the Fundamental Research Funds for the Central Universities (N2126005, N2126002, and N2126006), the National Defense Preliminary Research Project (Grant No. 50911020604), and the Science Foundation of Liaoning under Grant No. 2021-MS-101.

Conflict of interest

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

Publisher's note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

Abbasi, A., MahmoudZadeh, S., and Yazdani, A. (2022). A cooperative dynamic task assignment framework for COTSbot AUVs. IEEE Trans. Automat. Sci. Eng . 19, 1163–1179. doi: 10.1109/TASE.2020.3044155

CrossRef Full Text | Google Scholar

Bello, I., Pham, H., Le, Q. V., Norouzi, M., and Bengio, S. (2016). Neural combinatorial optimization with reinforcement learning. arXiv preprint arXiv:1611.09940 . doi: 10.48550/arXiv.1611.09940

Bertuccelli, L., Choi, H.-L., Cho, P., and How, J. (2009). “Real-time multi-UAV task assignment in dynamic and uncertain environments,” in AIAA Guidance, Navigation, and Control Conference (Chicago, IL), 5776. doi: 10.2514/6.2009-5776

Capitan, J., Merino, L., and Ollero, A. (2016). Cooperative decision-making under uncertainties for multi-target surveillance with multiples UAVs. J. Intell. Robot. Syst . 84, 371–386. doi: 10.1007/s10846-015-0269-0

Deudon, M., Cournut, P., Lacoste, A., Adulyasak, Y., and Rousseau, L.-M. (2018). “Learning heuristics for the TSP by policy gradient,” in International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Delft: Springer), 170–181. doi: 10.1007/978-3-319-93031-2_12

Edison, E., and Shima, T. (2011). Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms. Comput. Operat. Res . 38, 340–356. doi: 10.1016/j.cor.2010.06.001

Ferreira, P. R. Jr., Boffo, F. S., and Bazzan, A. L. (2007). “A swarm based approximated algorithm to the extended generalized assignment problem (e-GAP),” in Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (Honolulu, HI), 1–3. doi: 10.1145/1329125.1329373

François-Lavet, V., Taralla, D., Ernst, D., and Fonteneau, R. (2016). “Deep reinforcement learning solutions for energy microgrids management,” in European Workshop on Reinforcement Learning (EWRL 2016) (Barcelona).

Google Scholar

Holler, J., Vuorio, R., Qin, Z., Tang, X., Jiao, Y., Jin, T., et al. (2019). “Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem,” in 2019 IEEE International Conference on Data Mining (ICDM) (Seoul: IEEE), 1090–1095. doi: 10.1109/ICDM.2019.00129

Hooshangi, N., and Alesheikh, A. A. (2017). Agent-based task allocation under uncertainties in disaster environments: an approach to interval uncertainty. Int. J. Disaster Risk Reduct . 24, 160–171. doi: 10.1016/j.ijdrr.2017.06.010

Huang, H., Zhu, D., and Ding, F. (2014). Dynamic task assignment and path planning for multi-AUV system in variable ocean current environment. J. Intell. Robot. Syst . 74, 999–1012. doi: 10.1007/s10846-013-9870-2

PubMed Abstract | CrossRef Full Text | Google Scholar

Khan, A. T., and Li, S. (2022). Smart surgical control under RCM constraint using bio-inspired network. Neurocomputing 470, 121–129. doi: 10.1016/j.neucom.2021.10.116

Khan, A. T., Li, S., and Cao, X. (2021). Control framework for cooperative robots in smart home using bio-inspired neural network. Measurement 167, 108253. doi: 10.1016/j.measurement.2020.108253

Khan, A. T., Li, S., and Li, Z. (2022). Obstacle avoidance and model-free tracking control for home automation using bio-inspired approach. Adv. Cont. Appl. Eng. Indust. Syst. 4, 1–14. doi: 10.1002/adc2.63

Kool, W., Van Hoof, H., and Welling, M. (2018). Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 . doi: 10.48550/arXiv.1803.08475

Li, J., Zhang, K., and Xia, G. (2017). “Multi-AUV cooperative task allocation based on improved contract network,” in 2017 IEEE International Conference on Mechatronics and Automation (ICMA) (Takamatsu: IEEE), 608–613. doi: 10.1109/ICMA.2017.8015886

Ma, Q., Ge, S., He, D., Thaker, D., and Drori, I. (2019). Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning. arXiv preprint arXiv:1911.04936 . doi: 10.48550/arXiv.1911.04936

MahmoudZadeh, S., Powers, D. M., Sammut, K., Atyabi, A., and Yazdani, A. (2018). A hierarchal planning framework for AUV mission management in a spatiotemporal varying ocean. Comput. Electric. Eng . 67, 741–760. doi: 10.1016/j.compeleceng.2017.12.035

Page, A. J., Keane, T. M., and Naughton, T. J. (2010). Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system. J. Parallel Distribut. Comput . 70, 758–766. doi: 10.1016/j.jpdc.2010.03.011

Ru, J., Yu, S., Wu, H., Li, Y., Wu, C., Jia, Z., et al. (2021). A multi-AUV path planning system based on the omni-directional sensing ability. J. Mar. Sci. Eng . 9, 806–827. doi: 10.3390/jmse9080806

Solozabal, R., Ceberio, J., Sanchoyerto, A., Zabala, L., Blanco, B., and Liberal, F. (2019). Virtual network function placement optimization with deep reinforcement learning. IEEE J. Select. Areas Commun . 38, 292–303. doi: 10.1109/JSAC.2019.2959183

Vinyals, O., Fortunato, M., and Jaitly, N. (2015). “Pointer networks,” in Proceedings of NIPS 2015 (Montreal, QC), 2692–2700.

Xie, B., Chen, J., and Shen, L. (2018). “Cooperation algorithms in multi-agent systems for dynamic task allocation: a brief overview,” in 2018 37th Chinese Control Conference (CCC) (Wuhan: IEEE), 6776–6781. doi: 10.23919/ChiCC.2018.8483939

Zhu, D., Cao, X., Sun, B., and Luo, C. (2017). Biologically inspired self-organizing map applied to task assignment and path planning of an AUV system. IEEE Trans. Cogn. Dev. Syst . 10, 304–313. doi: 10.1109/TCDS.2017.2727678

Zhu, D., Zhou, B., and Yang, S. X. (2020). A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network map. IEEE Trans. Intell. Vehicles 6, 333–342. doi: 10.1109/TIV.2020.3029369

Zhu, D.-Q., Qu, Y., and Yang, S. X. (2019). Multi-AUV som task allocation algorithm considering initial orientation and ocean current environment. Front. Inform. Technol. Electron. Eng . 20, 330–341. doi: 10.1631/FITEE.1800562

Keywords: task assignment problem, multiple autonomous underwater robots, cluster collaboration, genetic algorithm, graph pointer network

Citation: Ru J, Hao D, Zhang X, Xu H and Jia Z (2023) Research on a hybrid neural network task assignment algorithm for solving multi-constraint heterogeneous autonomous underwater robot swarms. Front. Neurorobot. 16:1055056. doi: 10.3389/fnbot.2022.1055056

Received: 27 September 2022; Accepted: 05 December 2022; Published: 10 January 2023.

Reviewed by:

Copyright © 2023 Ru, Hao, Zhang, Xu and Jia. This is an open-access article distributed under the terms of the Creative Commons Attribution License (CC BY) . The use, distribution or reproduction in other forums is permitted, provided the original author(s) and the copyright owner(s) are credited and that the original publication in this journal is cited, in accordance with accepted academic practice. No use, distribution or reproduction is permitted which does not comply with these terms.

This article is part of the Research Topic

Granular Computing-Based Artificial Neural Networks: Toward Building Robust and Transparent Intelligent Systems

• Help & FAQ

TA-GAE: Crowdsourcing Diverse Task Assignment Based On Graph Autoencoder in AIoT

• Center for Big Data
• Data Science
• Computer Science

Research output : Contribution to journal › Article › peer-review

With the recent development of AIoT (AI+IoT), crowdsourcing has emerged as a promising paradigm for distributed problem solving and business practice. Crowdsourcing entails posting tasks on a dedicated web platform, enabling networked workers to choose preferred tasks on a first-come, first-served basis, typically of the same type to ensure high assignment accuracy. However, existing crowdsourcing task assignment methods do not take into account the potential fatigue of workers for similar tasks. In this paper, we propose a task assignment architecture using a gravity-based graph autoencoder(TA-GAE), which comprehensively considers the relationship between the occupation and skills of workers and potential tasks, facilitating an accurate assignment of a wide variety of tasks to workers. The proposed architecture consists of three modules, The Graph Creation module analyzes the potential connections between tasks based on worker evaluations and constructs an initial task graph that represents these connections. The Gravity-Based Graph Autoencoder module is inspired by Newton’s law of universal gravitation. We analogize the tasks on the crowd-sourcing platform to masses in the universe and calculate the mutual attractive force between two tasks to quantify their correlation. The Hybrid Task Assignment module recommends task lists to workers by combining traditional collaborative filtering and content-based task assignment strategies. The experimental results demonstrate that the proposed architecture outperforms several state-of-the-art methods and achieves a diversity rate of over 40% across four datasets: Fliggy Trip, MovieLens 1M, Library and Survey.

All Science Journal Classification (ASJC) codes

• Signal Processing
• Information Systems
• Hardware and Architecture
• Computer Science Applications
• Computer Networks and Communications
• Artificial intelligence
• Computer architecture
• Correlation
• Crowdsourcing
• Internet of Things
• Task analysis
• Task assignment
• crowdsourcing
• potential tasks
• worker occupation
• worker skills

Access to Document

• 10.1109/JIOT.2023.3344573

Other files and links

• Link to publication in Scopus
• Link to the citations in Scopus

Fingerprint

• Crowdsourcing Engineering & Materials Science 100%
• Gravitation Engineering & Materials Science 75%
• Internet of things Engineering & Materials Science 71%
• Collaborative filtering Engineering & Materials Science 32%
• Fatigue of materials Engineering & Materials Science 19%
• Industry Engineering & Materials Science 12%

T1 - TA-GAE

T2 - Crowdsourcing Diverse Task Assignment Based On Graph Autoencoder in AIoT

AU - Liu, Xiuya

AU - Xing, Tianzhang

AU - Meng, Xianjia

AU - Wu, Chase Q.

N1 - Publisher Copyright: IEEE

N2 - With the recent development of AIoT (AI+IoT), crowdsourcing has emerged as a promising paradigm for distributed problem solving and business practice. Crowdsourcing entails posting tasks on a dedicated web platform, enabling networked workers to choose preferred tasks on a first-come, first-served basis, typically of the same type to ensure high assignment accuracy. However, existing crowdsourcing task assignment methods do not take into account the potential fatigue of workers for similar tasks. In this paper, we propose a task assignment architecture using a gravity-based graph autoencoder(TA-GAE), which comprehensively considers the relationship between the occupation and skills of workers and potential tasks, facilitating an accurate assignment of a wide variety of tasks to workers. The proposed architecture consists of three modules, The Graph Creation module analyzes the potential connections between tasks based on worker evaluations and constructs an initial task graph that represents these connections. The Gravity-Based Graph Autoencoder module is inspired by Newton’s law of universal gravitation. We analogize the tasks on the crowd-sourcing platform to masses in the universe and calculate the mutual attractive force between two tasks to quantify their correlation. The Hybrid Task Assignment module recommends task lists to workers by combining traditional collaborative filtering and content-based task assignment strategies. The experimental results demonstrate that the proposed architecture outperforms several state-of-the-art methods and achieves a diversity rate of over 40% across four datasets: Fliggy Trip, MovieLens 1M, Library and Survey.

AB - With the recent development of AIoT (AI+IoT), crowdsourcing has emerged as a promising paradigm for distributed problem solving and business practice. Crowdsourcing entails posting tasks on a dedicated web platform, enabling networked workers to choose preferred tasks on a first-come, first-served basis, typically of the same type to ensure high assignment accuracy. However, existing crowdsourcing task assignment methods do not take into account the potential fatigue of workers for similar tasks. In this paper, we propose a task assignment architecture using a gravity-based graph autoencoder(TA-GAE), which comprehensively considers the relationship between the occupation and skills of workers and potential tasks, facilitating an accurate assignment of a wide variety of tasks to workers. The proposed architecture consists of three modules, The Graph Creation module analyzes the potential connections between tasks based on worker evaluations and constructs an initial task graph that represents these connections. The Gravity-Based Graph Autoencoder module is inspired by Newton’s law of universal gravitation. We analogize the tasks on the crowd-sourcing platform to masses in the universe and calculate the mutual attractive force between two tasks to quantify their correlation. The Hybrid Task Assignment module recommends task lists to workers by combining traditional collaborative filtering and content-based task assignment strategies. The experimental results demonstrate that the proposed architecture outperforms several state-of-the-art methods and achieves a diversity rate of over 40% across four datasets: Fliggy Trip, MovieLens 1M, Library and Survey.

KW - Artificial intelligence

KW - Computer architecture

KW - Correlation

KW - Crowdsourcing

KW - Internet of Things

KW - Surveys

KW - Task analysis

KW - Task assignment

KW - crowdsourcing

KW - potential tasks

KW - worker occupation

KW - worker skills

UR - http://www.scopus.com/inward/record.url?scp=85181574918&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85181574918&partnerID=8YFLogxK

U2 - 10.1109/JIOT.2023.3344573

DO - 10.1109/JIOT.2023.3344573

M3 - Article

AN - SCOPUS:85181574918

SN - 2327-4662

JO - IEEE Internet of Things Journal

JF - IEEE Internet of Things Journal

Help | Advanced Search

Computer Science > Distributed, Parallel, and Cluster Computing

Title: matching-based hybrid service trading for task assignment over dynamic mobile crowdsensing networks.

Abstract: By opportunistically engaging mobile users (workers), mobile crowdsensing (MCS) networks have emerged as important approach to facilitate sharing of sensed/gathered data of heterogeneous mobile devices. To assign tasks among workers and ensure low overheads, a series of stable matching mechanisms is introduced in this paper, which are integrated into a novel hybrid service trading paradigm consisting of futures trading mode and spot trading mode to ensure seamless MCS service provisioning. In the futures trading mode, we determine a set of long-term workers for each task through an overbooking-enabled in-advance many-to-many matching (OIA3M) mechanism, while characterizing the associated risks under statistical analysis. In the spot trading mode, we investigate the impact of fluctuations in long-term workers' resources on the violation of service quality requirements of tasks, and formalize a spot trading mode for tasks with violated service quality requirements under practical budget constraints, where the task-worker mapping is carried out via onsite many-to-many matching (O3M) and onsite many-to-one matching (OMOM). We theoretically show that our proposed matching mechanisms satisfy stability, individual rationality, fairness and computational efficiency. Comprehensive evaluations also verify the satisfaction of these properties under practical network settings, while revealing commendable performance on running time, participators' interactions, and service quality.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .

An official website of the United States government

The .gov means it’s official. Federal government websites often end in .gov or .mil. Before sharing sensitive information, make sure you’re on a federal government site.

The site is secure. The https:// ensures that you are connecting to the official website and that any information you provide is encrypted and transmitted securely.

• Publications
• Account settings

Preview improvements coming to the PMC website in October 2024. Learn More or Try it out now .

• Advanced Search
• Journal List
• Front Neurorobot

Research on a hybrid neural network task assignment algorithm for solving multi-constraint heterogeneous autonomous underwater robot swarms

Associated data.

The raw data supporting the conclusions of this article will be made available by the authors, without undue reservation.

Studying the task assignment problem of multiple underwater robots has a broad effect on the field of underwater exploration and can be helpful in military, fishery, and energy. However, to the best of our knowledge, few studies have focused on multi-constrained underwater detection task assignment for heterogeneous autonomous underwater vehicle (AUV) clusters with autonomous decision-making capabilities, and the current popular heuristic methods have difficulty obtaining optimal cluster unit task assignment results. In this paper, a fast graph pointer network (FGPN) method, which is a hybrid of graph pointer network (GPN) and genetic algorithm, is proposed to solve the task assignment problem of detection/communication AUV clusters, and to improve the assignment efficiency on the basis of ensuring the accuracy of task assignment. A two-stage detection algorithm is used. First, the task nodes are clustered and pre-grouped according to the communication distance. Then, according to the clustering results, a neural network model based on graph pointer network is used to solve the local task assignment results. A large-scale cluster cooperative task assignment problem and a detection/communication cooperative work mode are proposed, which transform the cooperative cooperation problem of heterogeneous AUV clusters into a Multiple Traveling salesman problem (MTSP) for solving. We also conducted a large number of experiments to verify the effectiveness of the algorithm. The experimental results show that the solution efficiency of the method proposed in this paper is better than the traditional heuristic method on the scale of 300/500/750/1,000/1,500/2,000 task nodes, and the solution quality is similar to the result of the heuristic method. We hope that our ideas and methods for solving the large-scale cooperative task assignment problem can be used as a reference for large-scale task assignment problems and other related problems in other fields.

1. Introduction

With the development of underwater vehicle technology and information technology, new underwater detection needs are constantly emerging. Under the constraints of multi-agents, more challenges are emerging, and different scholars have focused on related research directions. The assignment of detection tasks is a relatively classic research direction when using AUV clusters to perform traversal detection of multiple points to be detected in underwater detection scenarios.

The task assignment of underwater detection robots can be divided into two types: dynamic task assignment and static task assignment, which correspond to different usage scenarios. When performing detection tasks on dynamic targets (Page et al., 2010 ; Xie et al., 2018 ), the task allocation method of dynamic allocation is often used because the situation of the area to be detected is unknown at this time, detection tasks always appear, and tasks can only be allocated while exploring. Many scholars have focused in this topic. For example, MahmoudZadeh et al. ( 2018 ) proposed a hierarchical dynamic task planning framework for the problem of dynamic task assignment of AUVs within a limited time interval in a spatiotemporally changing marine environment. Bertuccelli et al. ( 2009 ) proposed a dynamic mission planning algorithm based on enhanced Consensus-Based Bundle Algorithm for multi-agent combat scenarios with noisy sensors. Capitan et al. ( 2016 ) proposed a dynamic task planning algorithm based on MDP (Markov Decision Process) for planning problems under multi-stage uncertainty. The above problems have no global information, and the task allocation will focus on factors, such as the robot's detection ability, communication delay, and energy allocation. When assigning static tasks (Ferreira et al., 2007 ; Edison and Shima, 2011 ), the related problem is usually modeled as a traveling salesman problem. For example, Abbasi et al. ( 2022 ) proposed a heuristic fleet cooperation algorithm to solve the problem of sea star cluster processing. Hooshangi and Alesheikh ( 2017 ) explored a multi-agent task planning method combining interval number VIKOR and auction mechanism based on Contract Net Protocol is used to solve rescue problems in disaster environments. In addition, many scholars have used deep learning (Vinyals et al., 2015 ; Bello et al., 2016 ; François-Lavet et al., 2016 ; Deudon et al., 2018 ; Kool et al., 2018 ; Holler et al., 2019 ; Solozabal et al., 2019 ) methods to solve the traveling salesman problem. The above work uses more capable surface and underwater ships to pre-scan the area to be detected, a more capable experimental platform to improve some of the above shortcomings in detection and energy consumption, and a multi-robot cluster to perform the detection task, but requires a large number of AUVs that can perform communication and detection tasks. The cost is high and the number is small. The number of task points allocated to each AUV is large, and the computational efficiency and detection efficiency of the task allocation algorithm are relatively low. Thus far, the underwater task detection task still faces many problems, and limited research has focused on task assignments for large-scale detection points in the pre-detection area using the heterogeneous AUV cluster combination of communication/detection.

Studying the task assignment problem of heterogeneous AUV cluster combinations for large-scale probe points can bring many benefits (Zhu et al., 2020 ; Ru et al., 2021 ). In terms of energy consumption, the heterogeneous AUV combination performs its duties, which can provide smaller energy consumption and prolong the working time of the AUV cluster (Zhu et al., 2017 ; Khan et al., 2022 ). In terms of task allocation efficiency, the AUV responsible for communication has strong computing power and can be equipped with deep learning modules. It can greatly improve the efficiency of task allocation (Zhu et al., 2019 ; Khan and Li, 2022 ). In terms of economy, the types and performance of sensors configured by small robots that perform short-range detection tasks are weak, and the cost is low. It can be used in combination with large AUVs with strong detection capabilities to save costs (Huang et al., 2014 ; Khan et al., 2021 ). In terms of detection efficiency, heterogeneous clusters can detect more detection points per unit time and increase the detection area per unit time (Li et al., 2017 ).

Heterogeneous AUV cluster detection with detection/communication hybrid functions has many benefits but still faces the following challenges. First, the balance of robot task allocation is an issue considering that the number of points obtained by pre-detection increases with the increase of sensor capabilities and detection requirements. How to reasonably allocate detection points to each robot group is another challenge. The second is the cooperation between heterogeneous robots. Because the functions of heterogeneous robots are different, robots with functions such as detection and communication need to cooperate in the time and space domains, so the cooperation between heterogeneous robots is a challenge. Finally, the multi-robot task assignment problem is a typical NP-hard problem, and the efficient assignment of tasks is a challenge.

To overcome the above challenges, we propose a novel task assignment method suitable for solving heterogeneous AUV cluster combinations-Cluster-based hybrid solution method: This algorithm (i) proposes a detection point assignment method, (ii) designs a set of task assignment algorithm based on the fusion of GPN (Ma et al., 2019 ) network and heuristic method, and (iii) proposes a heterogeneous AUV matching algorithm. The contributions of this paper are as follows:

(1) To our knowledge, this paper is the first to use the area detection algorithm in a large-scale underwater environment to be detected by using a heterogeneous segmentation method.

(2) A DBSCAN clustering equivalence algorithm based on communication distance constraints that can perform grouping equivalent processing on large-scale tasks is proposed.

(3) An improved task assignment method based on GPN network is also proposed, which can effectively replace the traditional heuristic algorithm to solve the TSP problem with fixed start and end points.

(4) A task coordination method for heterogeneous AUVs that can work under the common constraints of detection and communication for heterogeneous AUV systems is explored.

(5) We also carried out a large number of simulation experiments on virtual underwater pre-detection points, compared the effects of classical heuristic algorithms, and analyzed the combination of different numbers of robots to further verify the effectiveness and efficiency of the algorithm practicality.

2. Problem description

There are N target points tp i to be processed in a certain sea area, forming a set of tasks to be processed TP :

where tp i = { x, y }, x, y represents the location information of the target task point.

Existing M 1 communication units cu , and M 2 execution units eu constitute cluster unit U :

When the execution unit and the communication unit cooperate to access all task nodes, they should meet the communication constraint requirements, as shown in Equation (3), that is, the execution unit should be within the scope of the communication unit. In addition, the execution unit should also meet the requirements of its own capability constraints, as shown in Equation (4), that is, at the same time, the execution unit can only access at most one target task node. The specific constraints are as follows:

where C i,j indicates whether communication can be established between communication unit cu i and execution unit eu j , C i,j = 1 indicates that the communication unit can establish communication with the execution unit, and vice versa, d i,j represents the distance between the communication unit cu i and the execution unit eu j , and r represents the communication radius of the communication unit cu i .

where h ( eu j , tp i , t ) indicates whether the execution unit eu j accesses the target task point tp i at time t , the value of h ( eu j , tp i , t ) is 1 if the execution unit eu j visits the target task point tp i , and 0 otherwise.

In order to ensure the optimal result of the overall task assignment, this study takes the minimum moving distance as the optimization goal to optimize the entire task assignment process. The optimization goals are as follows:

where L c u i represents the total distance moved by the communication unit cu i , and L e u j represents the total distance moved by the execution unit eu j .

3. Cluster collaborative task assignment solution framework

The execution and the communication units need to cooperate to complete the processing of all task points, and a communication distance constraint between the execution and the communication units exists, limited by the current computing power level. Hence, it is difficult to directly solve the task assignment and solve it in a limited time. For optimal task assignment results, the process of solving the cluster cooperative task assignment problem in this paper is shown in the following Figure 1 .

Flowchart for solving cluster collaborative task assignment. (A) Perform equivalent clustering on all task nodes, and generate several task cluster units after clustering. (B) Perform global task assignment of execution units and communication units according to the equivalent clustering results. (C) According to The result of the global task assignment is to assign tasks to the communication unit and the execution unit within the task cluster.

Module A means to perform equivalent clustering on all task points, module B means to plan the order in which the execution unit and communication unit access each task cluster according to the clustering result, module C means to allocate within each task cluster according to the global task allocation result local tasks.

3.1. Target task point clustering grouping

Considering the influence of communication constraints, the execution unit must select executable task points near the communication unit. At the same time, when the task scale becomes larger, the overall optimization will become more complicated. Therefore, consider grouping tasks first through communication distance constraints, and then, large-scale tasks and resource allocation planning problems become local small-scale problems, thereby reducing the amount of computation. The grouping method adopts the DBSCAN method to group the task points:

where g i = { tp 1 , tp 2 , …, tp l } indicates that the task cluster g i has l target task points, and k represents the number of task clusters after clustering.

First, according to the distribution of target task points tp i in the task cluster group g i , it is equivalently converted into a node, and then the equivalent approximation is made to the moving distance and time consuming of the execution unit eu j to complete the task cluster.

Task cluster g i equivalent node E x,y ( g i ) location coordinates is as follow:

where f r ( g i ) represents the center coordinates of the smallest covering circle containing all target task points tp i in the task cluster g i .

The equivalent approximate moving distance E d of the execution unit after visiting all target task point tp i in the task cluster g i is as follow:

The equivalent approximate time E t for the execution unit to complete the task cluster g i is as follows:

where v ¯ represents the average expected speed of execution unit.

3.2. Global task assignment

3.2.1. execution unit task assignment.

According to the clustering and grouping results g i , the global task assignment problem of execution units can be transformed into a multi-travel salesman problem with fixed start and end nodes. Genetic algorithm is used to solve the optimal task cluster access sequence of each execution unit eu j , and the minimum moving data distance is used as the The optimization objective of the problem optimizes the task assignment results. The specific form of the optimization goal is as follows:

3.2.2. Communication unit task assignment

The communication unit needs to cooperate with the execution unit to complete the processing of task points and assign tasks to the communication unit according to the global planning result of the execution unit. The time required by the execution unit to process each task cluster also varies because of the different number of tasks in each task cluster. Therefore, the following time constraints exist for the communication unit to reach each task cluster node:

where w j = max(0, e i − a j ), a j is the time when the communication unit arrives at the task cluster node, w j is the waiting time of the communication unit, e i,j is the time when the ith execution unit starts to execute the jth node, and Δ i,j is the time when the communication unit arrives from node i to node j.

The global task assignment problem of communication units can be equivalently transformed into a multi-travel salesman problem with time windows. In order to ensure that the optimal task assignment results of communication units are obtained, this paper takes the minimum moving distance of communication units as the optimization objective, and adopts genetic The algorithm solves the problem. The optimization goal is defined as:

3.3. Local task assignment

During the execution of the task, the communication unit does not participate directly in the processing of the task point and is only responsible for completing the communication with the execution unit, that is, it does not need to reach the task point. In group task planning, a genetic algorithm is used to plan tasks for execution units, and then tasks are planned for communication units according to the results of task planning for execution units.

3.3.1. Execution unit local task planning

The local task assignment problem of the execution unit belongs to the traveling salesman problem with fixed start and end points. In this paper, the deep learning method based on the GPN model (Ma et al., 2019 ) is used to solve the local task assignment problem. The model structure is shown in the Figure 2 .

GPN network structure model diagram.

The encoding part of the model is divided into node feature information encoding and neighbor node information encoding. The node location feature information is encoded through the LSTM network, thereby mapping the node feature information from the low-dimensional space to the high-dimensional space. According to the encoding vector of the location features of each node by LSTM, the node neighbor information encoding part aggregates and encodes the neighbor information of each node through the GraphSAGE network, so as to obtain the feature information between the node and other nodes. The network form of each layer of the neighbor node information encoding network is as follows:

In the formula, T i l represents the l − th task node of the layer, γ is a trainable weight matrix, Θ ∈ ℝ d l - 1 * d l is a trainable weight matrix, R θ represents the aggregation function, and N ( i ) represents the k adjacent task nodes T i .

The decoder part encodes the node feature information and the neighbor node feature information to obtain the high-dimensional feature vector of the node and the high-dimensional feature vector of the neighbor node and send it to the attention network model to obtain the pointer vector u i , which is then passed to the softmax layer, using to generate the probability distribution P i of the next node to visit.

3.3.2. Local task planning of communication unit

Because the communication unit does not need to reach the task location point, virtual nodes v x, y are added according to the task location point processed by the execution unit to plan the access node location of the communication unit. The types of virtual node additions are as follows Figure 3 .

Schematic diagram of virtual node types.

Single virtual nodemodel. When all target task points tp i in the task cluster g i are within the communication range of the communication unit cu i that executes the task cluster, the virtual node v x, y is defined as:

The above formula indicates that the coordinates of the virtual node v x,y at this time are the center coordinates of the smallest covering circle containing all target task points in the task cluster g i .

Multiple virtual nodes model. When some target task points tp j in the task cluster g i are all within the communication range of the communication unit cu i executing the task cluster, the task points of the current task group are grouped twice according to the order of the execution unit eu j executing the task nodes.

where g i ′ = { t p j | d i , j ≤ r } , g i ′ represents a new small task cluster formed by re-clustering the task points tp i in the task cluster unit g i according to the communication range of the communication unit cu i , a represents the number of new task clusters generated by secondary clustering of the task cluster. At this point the virtual node looks like this:

To sum up, for the task assignment problem of underwater autonomous vehicles in multi-heterogeneous clusters, firstly, clustering is performed according to the location information of all task nodes, and the clustering results are equivalently approximated, and then the global tasks of the execution units are assigned. The problem is transformed into a multi-travel salesman problem to solve, and the communication unit task cooperative assignment problem is transformed into a multi-travel salesman problem with a time window to solve. Task allocation, the specific method is: the task allocation problem of the execution unit is transformed into the traveling salesman problem, which is solved by the deep learning method based on GPN, and the communication unit performs local task allocation by adding virtual nodes. The notation used in the design is summarized in Table 5 .

Variable explanation table.

4. Experiment

This paper uses an NVIDIA RTX2080 GPU to train the FGPN model, limited by memory size constraints. The training batch size is B = 50, the tsp scale size is size = 60, and 1,000 rounds of training are performed. The training time for each round is about 3 min. The rest of the algorithms are implemented based on MATLAB2019, and the device CPU model is Intel (R) Core (TM) [email protected].

Experiment 1: Comparison of task allocation algorithms for individual execution unit eu in target task nodes tp of different scales in the 1*1 km area. The results are shown in Table 1 .

Compare the task assignments of target nodes with fixed start and end points of different sizes in the 1*1 km area.

The total Len. in the table is 10 3 m and the time unit is seconds. Total Len., total length; TP, target task points.

It can be seen from Figure 4 that the number of TP is less than 20, the solution results based on the deep learning method are similar in quality to the results obtained by GA, and the solution time is roughly the same; when the number of task nodes is greater than 20, the solution time is roughly the same. The quality of the solution based on the deep learning method is better than that of the GA solution. When the number of task nodes is greater than 40, the quality of the solution is improved by more than 30%. Moreover, when the number of task nodes is greater than 20, the quality of the solution is roughly under the same conditions, and the solution efficiency based on deep learning is better than that of GA. When the scale of task nodes is greater than 40, the solution efficiency is improved by about 70%.

Comparison of solution times for the number of target task nodes at different scales. (A) Comparison of solution speed between GA algorithm and FGPN method when the solution results are similar. (B) Comparison of the solution results of the GA algorithm and the FGPN method when the solution speed is similar.

Experiment 2: Comparison of results of task assignment methods based on the DBSCAN clustering method. Let the area size be 10*10km, the number of execution unit eu is 3, the number of communication unit cu is 2, the communication distance is 300 m, the movement speed of the execution unit is 2 m / s , and the movement speed of the communication unit is 3 to 5 m/s. The results are shown in Tables 2 – 4 .

The relationship between the solution time and the total moving distance and the scale of the task nodes when the number of target task nodes in the task cluster is about 40. The unit of total Len. in the table is 10 6 m , and the unit of Time is seconds.

The relationship between the solution time and the total moving distance and the scale of the task nodes when the number of target task nodes in the task cluster is about 60. The unit of total Len. in the table is 10 6 m , and the unit of Time is seconds.

The relationship between the solution time and the total moving distance and the scale of the task nodes when the number of target task nodes in the task cluster is about 50. The unit of total Len. in the table is 10 6 m , and the unit of Time is seconds.

Taking 1,000 task nodes in a 10*10 km area as an example, the overall task planning results are shown in the following figures.

The experimental results indicate that in the 10*10 km area when the number of TP is between 300 and 500, as shown in Figures 5 , ​ ,6, 6 , the solution time based on the deep learning method is similar to the total moving distance based on the solution result of the genetic algorithm, and the solution speed is increased by about 50%. When the task scale is greater than 500, the solution efficiency based on the deep learning method is better than that based on the genetic algorithm. When the total moving distance obtained by the solution remains similar, the solution speed is increased by more than 70%. Meanwhile, when the number of task nodes in the task cluster increases, the time spent to solve the relative optimal solution of the current scale task is relatively reduced, and when the scale of task nodes is greater than 1,500, it increases by about 20%. In addition, the solution efficiency of the BAS (Beetle Antennae Search Algorithm) is roughly similar to that of our proposed method, but the solution result is far worse than the genetic-based method and the method proposed in this paper. Experiments show that the method proposed in this paper can greatly improve the efficiency of solving large-scale cluster coordination problems.

Comparison between the solution time of the three methods and the scale of task nodes when the number of target task nodes in the task cluster is 40/50/60.

Comparison between the total length of the three methods and the scale of task nodes when the number of target task nodes in the task cluster is 40/50/60.

Figures 7 , ​ ,8, 8 , respectively, show the situation of three execution units traversing 1,000 task nodes and two communication units traversing virtual nodes cooperatively. Figure 9 shows the sequence of cooperative access to all target task nodes by the execution unit and the communication unit. Each execution unit traverses all the task nodes in the graph in turn, and the communication unit synchronously plans to traverse the virtual nodes of the graph according to the order in which the execution units access the task nodes to jointly complete the entire task. It can be seen from the figure that the algorithm proposed in this paper can effectively solve the problem of communication constraints and cooperative task assignment of multiple heterogeneous clusters.

Schematic diagram of the execution unit accessing node sequence when the number of target task nodes is 1,000.

Schematic diagram of the communication unit cooperative access node sequence when the number of target task nodes is 1,000.

Schematic diagram of the communication unit and the execution unit cooperating to access the target task points.

5. Conclusion

This paper proposes a deep learning method and a heuristic algorithm by adopting the idea of divide and conquer and the combination of global and local, aiming at the large task scale and complex coordination difficulties in the large-scale cooperative task assignment problem of multi-heterogeneous cluster units with communication distance constraints. The FGPN method proposed in this paper, which combines the clustering-based GPN and the genetic algorithm, can greatly improve the solution efficiency while ensuring that the solution results are similar to the genetic algorithm when the number of target task nodes is between 1,000 and 1,500. The experimental results show that the algorithm proposed in this paper can solve the problem of cooperative assignment of large-scale cluster tasks and can obtain relatively optimal task assignment results faster while ensuring that the quality of the solution is roughly the same as that of the traditional method. We will further explore the use of deep learning methods to solve the multi-traveling salesman problem with fixed start and end positions and the multi-traveling salesman problem with time windows in the future.

Data availability statement

Author contributions.

JR contributed to the conception of the study and contributed significantly to analysis and manuscript preparation. DH performed the experiment and performed the data analyses and wrote the manuscript. XZ, HX, and ZJ helped perform the analysis with constructive discussions. All authors contributed to the article and approved the submitted version.

Funding Statement

This research was funded by the National Natural Science Foundation of China (61872073 and 62203099), the Fundamental Research Funds for the Central Universities (N2126005, N2126002, and N2126006), the National Defense Preliminary Research Project (Grant No. 50911020604), and the Science Foundation of Liaoning under Grant No. 2021-MS-101.

Conflict of interest

The authors declare that the research was conducted in the absence of any commercial or financial relationships that could be construed as a potential conflict of interest.

Publisher's note

All claims expressed in this article are solely those of the authors and do not necessarily represent those of their affiliated organizations, or those of the publisher, the editors and the reviewers. Any product that may be evaluated in this article, or claim that may be made by its manufacturer, is not guaranteed or endorsed by the publisher.

• Abbasi A., MahmoudZadeh S., Yazdani A. (2022). A cooperative dynamic task assignment framework for COTSbot AUVs . IEEE Trans. Automat. Sci. Eng . 19 , 1163–1179. 10.1109/TASE.2020.3044155 [ CrossRef ] [ Google Scholar ]
• Bello I., Pham H., Le Q. V., Norouzi M., Bengio S. (2016). Neural combinatorial optimization with reinforcement learning . arXiv preprint arXiv:1611.09940 . 10.48550/arXiv.1611.09940 [ CrossRef ] [ Google Scholar ]
• Bertuccelli L., Choi H.-L., Cho P., How J. (2009). “Real-time multi-UAV task assignment in dynamic and uncertain environments,” in AIAA Guidance, Navigation, and Control Conference (Chicago, IL: ), 5776. 10.2514/6.2009-5776 [ CrossRef ] [ Google Scholar ]
• Capitan J., Merino L., Ollero A. (2016). Cooperative decision-making under uncertainties for multi-target surveillance with multiples UAVs . J. Intell. Robot. Syst . 84 , 371–386. 10.1007/s10846-015-0269-0 [ CrossRef ] [ Google Scholar ]
• Deudon M., Cournut P., Lacoste A., Adulyasak Y., Rousseau L.-M. (2018). “Learning heuristics for the TSP by policy gradient,” in International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (Delft: Springer; ), 170–181. 10.1007/978-3-319-93031-2_12 [ CrossRef ] [ Google Scholar ]
• Edison E., Shima T. (2011). Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms . Comput. Operat. Res . 38 , 340–356. 10.1016/j.cor.2010.06.001 [ CrossRef ] [ Google Scholar ]
• Ferreira P. R., Jr., Boffo F. S., Bazzan A. L. (2007). “A swarm based approximated algorithm to the extended generalized assignment problem (e-GAP),” in Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems (Honolulu, HI: ), 1–3. 10.1145/1329125.1329373 [ CrossRef ] [ Google Scholar ]
• François-Lavet V., Taralla D., Ernst D., Fonteneau R. (2016). “Deep reinforcement learning solutions for energy microgrids management,” in European Workshop on Reinforcement Learning (EWRL 2016) (Barcelona: ). [ Google Scholar ]
• Holler J., Vuorio R., Qin Z., Tang X., Jiao Y., Jin T., et al.. (2019). “Deep reinforcement learning for multi-driver vehicle dispatching and repositioning problem,” in 2019 IEEE International Conference on Data Mining (ICDM) (Seoul: IEEE; ), 1090–1095. 10.1109/ICDM.2019.00129 [ CrossRef ] [ Google Scholar ]
• Hooshangi N., Alesheikh A. A. (2017). Agent-based task allocation under uncertainties in disaster environments: an approach to interval uncertainty . Int. J. Disaster Risk Reduct . 24 , 160–171. 10.1016/j.ijdrr.2017.06.010 [ CrossRef ] [ Google Scholar ]
• Huang H., Zhu D., Ding F. (2014). Dynamic task assignment and path planning for multi-AUV system in variable ocean current environment . J. Intell. Robot. Syst . 74 , 999–1012. 10.1007/s10846-013-9870-2 [ CrossRef ] [ Google Scholar ]
• Khan A. T., Li S. (2022). Smart surgical control under RCM constraint using bio-inspired network . Neurocomputing 470 , 121–129. 10.1016/j.neucom.2021.10.116 [ CrossRef ] [ Google Scholar ]
• Khan A. T., Li S., Cao X. (2021). Control framework for cooperative robots in smart home using bio-inspired neural network . Measurement 167 , 108253. 10.1016/j.measurement.2020.108253 [ CrossRef ] [ Google Scholar ]
• Khan A. T., Li S., Li Z. (2022). Obstacle avoidance and model-free tracking control for home automation using bio-inspired approach . Adv. Cont. Appl. Eng. Indust. Syst. 4 , 1–14. 10.1002/adc2.63 [ CrossRef ] [ Google Scholar ]
• Kool W., Van Hoof H., Welling M. (2018). Attention, learn to solve routing problems! arXiv preprint arXiv:1803.08475 . 10.48550/arXiv.1803.08475 [ CrossRef ] [ Google Scholar ]
• Li J., Zhang K., Xia G. (2017). “Multi-AUV cooperative task allocation based on improved contract network,” in 2017 IEEE International Conference on Mechatronics and Automation (ICMA) (Takamatsu: IEEE; ), 608–613. 10.1109/ICMA.2017.8015886 [ CrossRef ] [ Google Scholar ]
• Ma Q., Ge S., He D., Thaker D., Drori I. (2019). Combinatorial optimization by graph pointer networks and hierarchical reinforcement learning . arXiv preprint arXiv:1911.04936 . 10.48550/arXiv.1911.04936 [ CrossRef ] [ Google Scholar ]
• MahmoudZadeh S., Powers D. M., Sammut K., Atyabi A., Yazdani A. (2018). A hierarchal planning framework for AUV mission management in a spatiotemporal varying ocean . Comput. Electric. Eng . 67 , 741–760. 10.1016/j.compeleceng.2017.12.035 [ CrossRef ] [ Google Scholar ]
• Page A. J., Keane T. M., Naughton T. J. (2010). Multi-heuristic dynamic task allocation using genetic algorithms in a heterogeneous distributed system . J. Parallel Distribut. Comput . 70 , 758–766. 10.1016/j.jpdc.2010.03.011 [ PMC free article ] [ PubMed ] [ CrossRef ] [ Google Scholar ]
• Ru J., Yu S., Wu H., Li Y., Wu C., Jia Z., et al.. (2021). A multi-AUV path planning system based on the omni-directional sensing ability . J. Mar. Sci. Eng . 9 , 806–827. 10.3390/jmse9080806 [ CrossRef ] [ Google Scholar ]
• Solozabal R., Ceberio J., Sanchoyerto A., Zabala L., Blanco B., Liberal F. (2019). Virtual network function placement optimization with deep reinforcement learning . IEEE J. Select. Areas Commun . 38 , 292–303. 10.1109/JSAC.2019.2959183 [ CrossRef ] [ Google Scholar ]
• Vinyals O., Fortunato M., Jaitly N. (2015). “Pointer networks,” in Proceedings of NIPS 2015 (Montreal, QC: ), 2692–2700. [ Google Scholar ]
• Xie B., Chen J., Shen L. (2018). “Cooperation algorithms in multi-agent systems for dynamic task allocation: a brief overview,” in 2018 37th Chinese Control Conference (CCC) (Wuhan: IEEE; ), 6776–6781. 10.23919/ChiCC.2018.8483939 [ CrossRef ] [ Google Scholar ]
• Zhu D., Cao X., Sun B., Luo C. (2017). Biologically inspired self-organizing map applied to task assignment and path planning of an AUV system . IEEE Trans. Cogn. Dev. Syst . 10 , 304–313. 10.1109/TCDS.2017.2727678 [ CrossRef ] [ Google Scholar ]
• Zhu D., Zhou B., Yang S. X. (2020). A novel algorithm of multi-AUVs task assignment and path planning based on biologically inspired neural network map . IEEE Trans. Intell. Vehicles 6 , 333–342. 10.1109/TIV.2020.3029369 [ CrossRef ] [ Google Scholar ]
• Zhu D.-Q., Qu Y., Yang S. X. (2019). Multi-AUV som task allocation algorithm considering initial orientation and ocean current environment . Front. Inform. Technol. Electron. Eng . 20 , 330–341. 10.1631/FITEE.1800562 [ CrossRef ] [ Google Scholar ]