task assignment network

• 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

• Trending Now
• Foundational Courses
• Data Science
• Practice Problem
• Machine Learning
• System Design
• DevOps Tutorial
• Distributed Systems Tutorial

Introduction to Distributed System

• What is a Distributed System?
• Features of Distributed Operating System
• Evolution of Distributed Computing Systems
• Types of Transparency in Distributed System
• What is Scalable System in Distributed System?
• Role of Middleware in Distributed System
• Difference between Hardware and Middleware
• What is Groupware in Distributed System?
• Difference between Parallel Computing and Distributed Computing
• Difference between Loosely Coupled and Tightly Coupled Multiprocessor System
• Design Issues of Distributed System
• Introduction to Distributed Computing Environment (DCE)
• Limitation of Distributed System
• Various Failures in Distributed System
• Types of Operating Systems
• Types of Distributed System
• Comparison - Centralized, Decentralized and Distributed Systems
• Three-Tier Client Server Architecture in Distributed System

Communication in Distributed Systems

• Features of Good Message Passing in Distributed System
• Issues in IPC By Message Passing in Distributed System
• What is Message Buffering?
• Multidatagram Messages in Distributed System
• Group Communication in distributed Systems

Remote Procedure Calls in Distributed System

• What is RPC Mechanism in Distributed System?
• Distributed System - Transparency of RPC
• Stub Generation in Distributed System
• Marshalling in Distributed System
• Server Management in Distributed System
• Distributed System - Parameter Passing Semantics in RPC
• Distributed System - Call Semantics in RPC
• Communication Protocols For RPCs
• Client-Server Model
• Lightweight Remote Procedure Call in Distributed System
• Difference Between RMI and DCOM
• Difference between RPC and RMI

Synchronization in Distributed System

• Synchronization in Distributed Systems
• Logical Clock in Distributed System
• Lamport's Algorithm for Mutual Exclusion in Distributed System
• Vector Clocks in Distributed Systems
• Event Ordering in Distributed System
• Mutual exclusion in distributed system
• Performance Metrics For Mutual Exclusion Algorithm
• Cristian's Algorithm
• Berkeley's Algorithm
• Difference between Token based and Non-Token based Algorithms in Distributed System
• Ricart–Agrawala Algorithm in Mutual Exclusion in Distributed System
• Suzuki–Kasami Algorithm for Mutual Exclusion in Distributed System

Source Management and Process Management

• Features of Global Scheduling Algorithm in Distributed System

What is Task Assignment Approach in Distributed System?

• Load Balancing Approach in Distributed System
• Load-Sharing Approach in Distributed System
• Difference Between Load Balancing and Load Sharing in Distributed System
• Process Migration in Distributed System

Distributed File System and Distributed shared memory

• What is DFS (Distributed File System)?
• Andrew File System
• File Service Architecture in Distributed System
• File Models in Distributed System
• File Accessing Models in Distributed System
• File Caching in Distributed File Systems
• What is Replication in Distributed System?
• Atomic Commit Protocol in Distributed System
• Design Principles of Distributed File System
• What is Distributed shared memory and its advantages
• Architecture of Distributed Shared Memory(DSM)
• Difference between Uniform Memory Access (UMA) and Non-uniform Memory Access (NUMA)
• Algorithm for implementing Distributed Shared Memory
• Consistency Model in Distributed System
• Distributed System - Thrashing in Distributed Shared Memory

Distributed Scheduling and Deadlock

• Scheduling and Load Balancing in Distributed System
• Issues Related to Load Balancing in Distributed System
• Components of Load Distributing Algorithm | Distributed Systems
• Distributed System - Types of Distributed Deadlock
• Deadlock Detection in Distributed Systems
• Conditions for Deadlock in Distributed System
• Deadlock Handling Strategies in Distributed System
• Deadlock Prevention Policies in Distributed System
• Chandy-Misra-Haas's Distributed Deadlock Detection Algorithm
• Security in Distributed System
• Types of Cyber Attacks
• Cryptography and its Types
• Implementation of Access Matrix in Distributed OS
• Digital Signatures and Certificates
• Design Principles of Security in Distributed System

Distributed Multimedia and Database System

• Distributed Database System
• Functions of Distributed Database System
• Multimedia Database

Distributed Algorithm

• Deadlock-Free Packet Switching
• Wave and Traversal Algorithm in Distributed System
• Election algorithm and distributed processing
• Introduction to Common Object Request Broker Architecture (CORBA) - Client-Server Software Development
• Difference between CORBA and DCOM
• Difference between COM and DCOM
• Life cycle of Component Object Model (COM) Object
• Distributed Component Object Model (DCOM)

Distributed Transactions

• Flat & Nested Distributed Transactions
• Transaction Recovery in Distributed System
• Mechanism for building Distributed file system
• Two Phase Commit Protocol (Distributed Transaction Management)

A Distributed System is a Network of Machines that can exchange information with each other through Message-passing. It can be very useful as it helps in resource sharing. In this article, we will see the concept of the Task Assignment Approach in Distributed systems.

Resource Management:

One of the functions of system management in distributed systems is Resource Management. When a user requests the execution of the process, the resource manager performs the allocation of resources to the process submitted by the user for execution. In addition, the resource manager routes process to appropriate nodes (processors) based on assignments. 

Multiple resources are available in the distributed system so there is a need for system transparency for the user. There can be a logical or a physical resource in the system. For example, data files in sharing mode, Central Processing Unit (CPU), etc.

As the name implies, the task assignment approach is based on the division of the process into multiple tasks. These tasks are assigned to appropriate processors to improve performance and efficiency. This approach has a major setback in that it needs prior knowledge about the features of all the participating processes. Furthermore, it does not take into account the dynamically changing state of the system. This approach’s major objective is to allocate tasks of a single process in the best possible manner as it is based on the division of tasks in a system. For that, there is a need to identify the optimal policy for its implementation.

Working of Task Assignment Approach:

In the working of the Task Assignment Approach, the following are the assumptions:

• The division of an individual process into tasks.
• Each task’s computing requirements and the performance in terms of the speed of each processor are known.
• The cost incurred in the processing of each task performed on every node of the system is known.
• The IPC (Inter-Process Communication) cost is known for every pair of tasks performed between nodes.
• Other limitations are also familiar, such as job resource requirements and available resources at each node, task priority connections, and so on.

Goals of Task Assignment Algorithms:

• Reducing Inter-Process Communication (IPC) Cost
• Quick Turnaround Time or Response Time for the whole process
• A high degree of Parallelism
• Utilization of System Resources in an effective manner

The above-mentioned goals time and again conflict. To exemplify, let us consider the goal-1 using which all the tasks of a process need to be allocated to a single node for reducing the Inter-Process Communication (IPC) Cost. If we consider goal-4 which is based on the efficient utilization of system resources that implies all the tasks of a process to be divided and processed by appropriate nodes in a system.

Note: The possible number of assignments of tasks to nodes:

But in practice, the possible number of assignments of tasks to nodes < m x n because of the constraint for allocation of tasks to the appropriate nodes in a system due to their particular requirements like memory space, etc.

Need for Task Assignment in a Distributed System:

The need for task management in distributed systems was raised for achieving the set performance goals. For that optimal assignments should be carried out concerning cost and time functions such as task assignment to minimize the total execution and communication costs, completion task time, total cost of 3 (execution, communication, and interference), total execution and communication costs with the limit imposed on the number of tasks assigned to each processor, and a weighted product of cost functions of total execution and communication costs and completion task time. All these factors are countable in task allocation and turn, resulting in the best outcome of the system.

Example of Task Assignment Approach:

Let us suppose, there are two nodes namely n1 and n2, and six tasks namely t1, t2, t3, t4, t5, and t6. The two task assignment parameters are:

• execution cost: x ab refers to the cost of executing a task an on node b.
• inter-task communication cost: c ij refers to inter-task communication cost between tasks i and j.

Note: The execution of the task (t2) on the node (n2) and the execution of the task (t6) on the node (n1) is not possible as it can be seen from the above table of Execution costs that resources are not available.

Case1: Serial Assignment

Cost of Execution in Serial Assignment:

Cost of Communication in Serial Assignment:

Case2: Optimal Assignment

Cost of Execution in Optimal Assignment:

Cost of Communication in Optimal Assignment:

Optimal Assignment using Minimal Cutset:

Cutset: The cutset of a graph refers to the set of edges that when removed makes the graph disconnected.

Minimal Cutset: The minimal cutset of a graph refers to the cut which is minimum among all the cuts of the graph.

Please Login to comment...

Similar reads.

• Distributed System

Improve your Coding Skills with Practice

What kind of Experience do you want to share?

• Selected Reading
• UPSC IAS Exams Notes
• Developer's Best Practices
• Questions and Answers
• Effective Resume Writing
• HR Interview Questions
• Computer Glossary

Task Assignment Approach in Distributed System

Introduction.

Distributed systems are a fundamental aspect of modern computing that has revolutionized the way we interact with technology. In essence, a distributed system is a collection of independent computers that work together as a single entity to achieve a common goal. These computers are connected through a communication network and interact with each other by exchanging messages.

A distributed system is an infrastructure consisting of multiple computers that are interconnected and communicate with each other using various communication protocols. The main feature of these systems is the fact that the resources and responsibilities are spread across different nodes in the network, rather than being centralized in one location.

Types of Task Assignment Approaches

Centralized task assignment approach.

The centralized task assignment approach is a method where there is a single point of control for the entire distributed system. In this approach, all the tasks are assigned from a central server, which allocates tasks to different nodes in the network.

The central server monitors the performance of each node and re−assigns tasks as needed. This approach requires that each node in the network communicates with the central server frequently to request task assignments or report on their current status.

One advantage of this approach is that it provides better control over task assignments and resource allocation, as all assignments are managed centrally. However, it also has some disadvantages such as high communication overhead since all systems communicate with a centralized entity which can increase latency and reduce response time especially if there is a large number of nodes in the system.

Decentralized Task Assignment Approach

The decentralized task assignment approach is a method where there is no central point of control in the distributed system. In this approach, every node in the network has equal responsibility for assigning and executing tasks. Each node decides what tasks to execute based on its current status and available resources without any interaction with other nodes or central servers.

The advantage of this approach is that it reduces communication overhead by eliminating frequent communications between nodes and central servers. It also provides better fault tolerance since if one node fails, other nodes in the system can continue working without disruption.

Factors Affecting Task Assignment Approach in Distributed Systems

Distributed systems are complex systems that operate in a network of interconnected computers. These systems are designed to handle a large amount of data and computation by distributing the tasks across multiple machines.

The task assignment approach plays a crucial role in the efficient operation of these distributed systems. Here, we discuss the factors that affect the task assignment approach in distributed systems.

Network Latency: The Barrier to Efficient Task Assignment

Network latency refers to how long it takes for data to travel from one point on a network to another. It is one of the primary factors affecting task assignment approaches in distributed systems.

High network latency can significantly slow down the process of task execution. For instance, if data has to be shuffled between different nodes frequently, it can cause significant delays and affect overall system performance.

A practical solution to address network latency is to employ techniques like caching or replication so that critical data is available locally for faster access. Another option is using algorithms that consider network latency as a factor while assigning tasks so that tasks are assigned closer together geographically where possible.

Load Balancing: The Challenge of Distributing Workload Equitably

In distributed computing, load balancing refers to distributing workloads evenly among different nodes for better utilization of resources and efficient task execution. In other words, load balancing ensures that no single node is overloaded with more tasks than it can handle while others remain underutilized.

The challenge with load balancing lies in identifying how much workload each node can handle, especially when dealing with heterogeneous infrastructure with varying capabilities such as CPU power or memory capacity. To address this challenge, several algorithms have been developed such as round−robin or least−loaded which distribute workload evenly among available nodes based on their capacity for handling tasks.

Resource Availability: Ensuring Adequate Resources for Task Execution

The availability of resources like CPU, memory, or storage is another factor affecting the task assignment approach in distributed systems. Inadequate resources can cause delays or system crashes if a task requires more resources than available on a node. For example, if a node running a task runs out of memory, the task cannot be completed.

To prevent such issues, task assignment algorithms must consider resource availability and allocate tasks only to machines with adequate resources to complete them. Additionally, monitoring tools can be used to track resource utilization and identify overutilized nodes that may need additional support or maintenance.

Network latency, load balancing and resource availability are critical factors affecting the performance of distributed systems. To ensure efficient execution of tasks in these systems, it is necessary to employ algorithms that consider these factors while assigning tasks among multiple available nodes.

Algorithms for Task Assignment in Distributed Systems

Round robin algorithm.

The Round Robin Algorithm is a popular task assignment approach used in distributed systems. It involves assigning tasks to nodes in a circular manner, with each node receiving an equal share of tasks.

The algorithm is simple and easy to implement, making it a preferred choice for many applications. In this approach, the system assigns tasks to the first available node, and then moves on to the next node in the list.

Least Loaded Algorithm

Another popular task assignment approach for distributed systems is Least Loaded Algorithm. This approach assigns new tasks to the least loaded node in the network at any given time. In other words, it selects a node that currently has fewer assigned tasks than others.

The Least Loaded Algorithm also helps maintain balanced workload distribution across all available resources and reduces processing delays caused by overburdened resources. One advantage of using this algorithm is that it automatically adjusts to changes in resource availability and processing capabilities by dynamically reassigning tasks as needed.

Practical Applications of Task Assignment Approach in Distributed Systems

Cloud computing: a game−changer for distributed systems.

Cloud computing has revolutionized the way distributed systems operate by providing access to a vast pool of resources on−demand. Cloud service providers deploy task assignment approaches to balance the workload and maximize resource utilization across their data centers. They use centralized or decentralized algorithms based on the specific needs of their cloud service offerings.

Distributed Database Management System: Efficiency through Task Assignment

Distributed database management systems (DDBMS) rely heavily on effective task assignment approaches to optimize query processing and improve transaction execution times. A DDBMS replicates data across multiple nodes, and each node independently processes queries or transactions to reduce response time for users.

Centralized or decentralized algorithms are used depending on the requirements of the DDBMS application. Load balancing is one of the main goals of task assignment in DDBMS since it ensures that each node gets a fair share of queries without being overwhelmed with requests.

As technology continues to evolve, researchers must continue exploring new and innovative algorithms for task assignment in distributed systems. The recent advancements in machine learning and artificial intelligence open up new avenues for developing intelligent algorithms that can predict performance, optimize resource allocation, and ensure fault tolerance. Researchers can further explore approaches such as genetic algorithms, particle swarm optimization, and other sophisticated techniques that may enhance the quality of task assignment.

Related Articles

• Distributed Consensus in Distributed System
• Distributed operating System
• Logical Clock in Distributed System
• Event Ordering in Distributed System
• Exception Handling in Distributed System
• Distributed Database Management System
• Atomic Commit Protocol in Distributed System
• File Model in Distributed Operating System
• Load Balancing Issues in Distributed System
• Mutual exclusion in a distributed system
• File Accessing Models in Distributed System
• File Service Architecture in Distributed System
• Priority Assignment to Tasks in Operating System
• Difference Between Network Operating System and Distributed Operating System
• What is a distributed Operating System?

Kickstart Your Career

Get certified by completing the course

To Continue Learning Please Login

Boosting MapReduce with Network-Aware Task Assignment

• Conference paper
• First Online: 01 January 2014
• Cite this conference paper

• Fei Xu 17 ,
• Fangming Liu 17 ,
• Dekang Zhu 17 &
• Hai Jin 17  

Part of the book series: Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering ((LNICST,volume 133))

Included in the following conference series:

• International Conference on Cloud Computing

1535 Accesses

Running MapReduce in a shared cluster has become a recent trend to process large-scale data analytical applications while improving the cluster utilization. However, the network sharing among various applications can make the network bandwidth for MapReduce applications constrained and heterogeneous. This further increases the severity of network hotspots in racks, and makes existing task assignment policies which focus on the data locality no longer effective. To deal with this issue, this paper develops a model to analyze the relationship between job completion time and the assignment of both map and reduce tasks across racks. We further design a network-aware task assignment strategy to shorten the completion time of MapReduce jobs in shared clusters. It integrates two simple yet effective greedy heuristics that minimize the completion time of map phase and reduce phase, respectively. With large-scale simulations driven by Facebook job traces, we demonstrate that the network-aware strategy can shorten the average completion time of MapReduce jobs, as compared to the state-of-the-art task assignment strategies, yet with an acceptable computational overhead.

The research was supported in part by a grant from National Natural Science Foundation of China (NSFC) under grant No.61133006.

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

Access this chapter

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Available as EPUB and PDF
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Note that we fill up the available slots in racks before starting the next wave. Hence, the task computation time ( \(w_{i}^{m}\tau _{m}\) , \(w_{i}^{r}\tau _{r}\) ) in Eq. ( 4 ) is fixed as \(\lceil p / \sum _{i \in \mathcal {R}}s_{i}^{m}\rceil \tau _{m}\) , \(\lceil q / \sum _{i \in \mathcal {R}}s_{i}^{r}\rceil \tau _{r}\) . It is omitted when calculating the phase makespan for simplicity.

Dean, J., Ghemawat, S.: MapReduce: simplified data processing on large clusters. In: Proceedings of OSDI, December 2004

Google Scholar  

Zaharia, M., Konwinski, A., Joseph, A.D., Katz, R.H., Stoica, I.: Improving MapReduce performance in heterogeneous environments. In: Proceedings of OSDI, December 2008

Hindman, B., Konwinski, A., Zaharia, M., Ghodsi, A., Joseph, A.D., Katz, R.H., Shenker, S., Stoica, I.: Mesos: a platform for fine-grained resource sharing in the data center. In: Proceedings of NSDI, March 2011

Palanisamy, B., Singh, A., Liu, L., Jain, B.: Purlieus: locality-aware resource allocation for MapReduce in a cloud. In: Proceedings of SC, November 2011

Ballani, H., Jang, K., Karagiannis, T., Kim, C., Gunawardena, D., O’Shea, G.: Chatty tenants and the cloud network sharing problem. In: Proceedings of NSDI, April 2013

Ananthanarayanan, G., Kandula, S., Greenberg, A., Stoica, I., Lu, Y., Saha, B., Harris, E.: Reining in the outliers in Map-Reduce clusters using mantri. In: Proceedings of OSDI, October 2010

Zaharia, M., Borthakur, D., Sarma, J.S., Elmeleegy, K., Shenker, S., Stoica, I.: Delay scheduling: a simple technique for achieving locality and fairness in cluster scheduling. In: Proceedings of Eurosys, April 2010

Hammoud, M., Sakr, M.F.: Locality-aware reduce task scheduling for MapReduce. In: Proceedings of CloudCom, November 2011

Chen, Y., Ganapathi, A., Griffith, R., Katz, R.: The case for evaluating MapReduce performance using workload suites. In: Proceedings of MASCOTS, July 2011

Jalaparti, V., Ballani, H., Costa, P., Karagiannis, T., Rowstron, A.: Bridging the tenant-provider gap in cloud services. In: Proceedings of SOCC, October 2012

Aora, S., Puri, M.C.: A variant of time minimizing assignment problem. Eur. J. Oper. Res. 110 (2), 314–325 (1998)

Article   Google Scholar  

Chen, F., Kodialam, M., Lakshman, T.V.: Joint scheduling of processing and shuffle phases in MapReduce Systems. In: Proceedings of Infocom, March 2012

Guo, Z., Fox, G., Zhou, M.: Investigation of data locality in MapReduce. In: Proceedings of CCGrid, May 2012

Download references

Author information

Authors and affiliations.

Services Computing Technology and System Lab, Cluster and Grid Computing Lab, School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, 430074, China

Fei Xu, Fangming Liu, Dekang Zhu & Hai Jin

You can also search for this author in PubMed   Google Scholar

Corresponding author

Correspondence to Fangming Liu .

Editor information

Editors and affiliations.

Electrical and Computer Engineering, The University of British Columbia, Vancouver, British Columbia, Canada

Victor C.M. Leung

School of Computer Science and Technology, Huazhong University of Science and Technology, Wuhan, China

Rights and permissions

Reprints and permissions

Copyright information

© 2014 Institute for Computer Sciences, Social Informatics and Telecommunications Engineering

About this paper

Cite this paper.

Xu, F., Liu, F., Zhu, D., Jin, H. (2014). Boosting MapReduce with Network-Aware Task Assignment. In: Leung, V., Chen, M. (eds) Cloud Computing. CloudComp 2013. Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol 133. Springer, Cham. https://doi.org/10.1007/978-3-319-05506-0_8

Download citation

DOI : https://doi.org/10.1007/978-3-319-05506-0_8

Published : 30 April 2014

Publisher Name : Springer, Cham

Print ISBN : 978-3-319-05505-3

Online ISBN : 978-3-319-05506-0

eBook Packages : Computer Science Computer Science (R0)

Share this paper

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

• Publish with us

Policies and ethics

• Find a journal
• Track your research

• Cover Letters
• Jobs I've Applied To
• Saved Searches
• Subscriptions

Marine Corps

Coast guard.

• Space Force
• Military Podcasts
• Benefits Home
• Military Pay and Money
• Veteran Health Care
• VA eBenefits
• Veteran Job Search
• Military Skills Translator
• Upload Your Resume
• Veteran Employment Project
• Vet Friendly Employers
• Career Advice
• Military Life Home
• Military Trivia Game
• Veterans Day
• Spouse & Family
• Military History
• Discounts Home
• Featured Discounts
• Veterans Day Restaurant Discounts
• Electronics
• Join the Military Home
• Contact a Recruiter
• Military Fitness

Marine Corps Combat Instructor Role Once Again a Special Duty Assignment

Combat instructors -- Marines who teach entry-level devil dogs basic warfighting skills -- are once again a special duty assignment.

As of May, the combat instructor, which is open to infantry Marines, is again one of these assignments after it was dropped from the criteria several years ago. The change was announced by the service's Manpower and Reserve Affairs division earlier this month.

Special duty assignments, or SDAs, are billets outside of a Marine's primary job and include being a recruiter , drill instructor and security guard. Sometimes those assignments are voluntary, but other times Marines are ordered into them.

Read Next: Army Identifies Explosive Ordnance Officer Who Died After a Fall During Training at Fort Johnson

"I went through combat instructor school back in 2015," Gunnery Sgt. Tyler Stokes, an enlisted assignments monitor for combat instructors, said in a video released by the service. "It's an extremely rewarding duty because you actually get to affect and to teach the warfighting skills that all Marines learn through the entry-level training pipeline, and it's really critical for the operational readiness of the force."

Stokes said that the commandant of the Marine Corps , Gen. Eric Smith, issued guidance earlier this year that said the combat instructor role would once again be a special duty assignment.

Combat instructors teach Marines weapons handling, employment of automatic weapons, the nuances of munition types, land navigation, communications, tactics and patrolling, among other tasks critical for young troops entering the Corps.

Typically, tours for combat instructors, and other special duty assignments, are three years. Marines coming back for a second tour may have their assignment shortened to two years, according to a previous Marine Corps message.

Marines assigned to the combat instructor role are primarily sent to the Corps' two infantry schools, located on each coast. Specifically, they are assigned to Camp Pendleton , California, or Camp Lejeune , North Carolina.

Prior to being assigned to the installations, prospective combat instructors go through the Marine Combat Instructor School, or MCIS, a nine-week course that includes written exams, combat conditioning, employment of different weapons systems and other tasks that Marines will be expected to hand down to future generations of infantrymen.

The job is open to volunteers, a spokesperson from Manpower and Reserve Affairs wrote in an email to Military.com on Tuesday.

"However, it may be staffed with involuntary assignments to fill vacancies and achieve maximum billet fill," Capt. Sarah Eason, the spokesperson, added. "Unlike the other SDAs, there are only a limited number of combat instructor billets open to any primary military occupational specialty (MOS), and these routinely fill with volunteers."

The special duty assignment also comes with some perks, Eason said, including special pay , the Marine Corps Combat Instructor Ribbon, promotion board precepts, and a "choice of specific geographic area for the next duty station following tour completion," she said.

Related: Marine Corps Offering Thousands of Dollars in Bonuses in Push for More Intelligence Specialists

Drew F. Lawrence

You May Also Like

In 2022, turnover within the DoD child care sector ranged from 34% at Marine Corps child care facilities to 50% turnover...

The departure of USS Ronald Reagan — one of America’s largest warships and a nuclear-powered Nimitz-class aircraft carrier —...

The officials who briefed reporters on the report's results pointed to command climate as a significant factor in the...

Debate over the bill, rushed to the House floor by GOP leadership this week, showed Washington's deeply fractured outlook on...

Military News

• Investigations and Features
• Military Opinion

Select Service

• National Guard

Most Popular Military News

For decades, recipients of the Purple Heart were honored with medals that had been forged during World War II, leftover stock...

The April issue of the Defense Department's Medical Surveillance Monthly Report, published last week, was focused entirely on...

The recommendation from the House Armed Services Committee in its draft version of the National Defense Authorization Act, or...

The Army has eliminated a significant part of its online training for enlisted troops -- a learning program that has drawn...

The Department of Veterans Affairs caregiver program, the beleaguered electronic health records program, veteran homelessness...

Latest Benefits Info

• VA Fertility Benefits for Military Veterans
• Virginia Veterans Rally the Troops, State Leaders in Support of Education Benefits
• Burial at Sea: A Time-Honored Tradition
• 4 Tips for Flying Space-A
• The Mental Burden of Using Military Benefits

More Military Headlines

Air Force, Marine Corps and Navy V-22 Ospreys were all given the green light to fly again in early March and have been slowly...

Russian authorities arrested Staff Sgt. Gordon Black, 34, in Vladivostok, a port city in the country, earlier this month and...

Texas Gov. Greg Abbott announced the pardon just a few minutes after the Texas Board of Pardons and Paroles announced that it...

• Staff Sgt. Gordon Black Reportedly Pleads Guilty to Theft While Being Held by Russia
• Texas Governor Pardons Ex-Army Sergeant Convicted of Killing Black Lives Matter Protester
• Army Reservist's Family Describes Struggle to Get Help Before Mass Shooting in Maine
• Military Ospreys Can't Fly More Than 30 Minutes from Landing Airfield Months After Grounding Lifted
• Florida Deputy's Killing of Black Airman Renews Debate on Police Killings and Race
• 6 Air Force Bases Selected to Host Air Task Forces in Test of New Deployment Model
• US Navy Flagship Carrier USS Ronald Reagan Leaves Its Japan Home Port After Nearly 9 Years
• Secretary of Defense Lloyd Austin to Speak at 2024 Naval Academy Graduation Ceremony

Military Benefits Updates

• Fertility Benefits for Active-Duty Service Members
• How Marines Took an Airfield in the Philippines in a Show Against China
• Privatized Barracks Would Get Deeper Look Under House's Draft Defense Bill
• Power Outages and an Urgent Warning: NTSB Details Dali Crew’s Scramble Before Key Bridge Collapse
• Coast Guard Tweaks Tattoo Policy to Allow Bigger Designs on Hands, Ink Behind Both Ears
• Man Accused of Aiming Laser at Coast Guard Helicopter Trying to Land at Massachusetts Hospital

Entertainment

• Jeff Bridges and Dave Bautista Headline All-Star Cast in New Take on 'Beowulf' Epic
• ‘Unconventional’ Demystifies Military Life While Showing the Power of a New Generation of Veterans
• Navy Veteran and 'King of B-Movies' Roger Corman Dies at 98