doi: 10.3934/jimo.2022015
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Aggregation and Adjustment mechanisms for disaster relief task allocation with uneven distribution

1. 

The State Key Laboratory of Management and Control for Complex Systems, Institute of Automation, Chinese Academy of Sciences, China

2. 

School of Artificial Intelligence, University of Chinese Academy of Sciences, China

* Corresponding author: Danli Wang

Received  April 2021 Revised  November 2021 Early access February 2022

Fund Project: This research is supported by the National Natural Science Foundation of China under Grant No. 61872363 and 61672507; the National Key Research and Development Program under Grant No. 2016YFB0401202; the Research and Development Foundation of The Institute of Automation, Chinese Academy of Sciences under Grant No.Y9J2FZ0801; the Natural Science Foundation of Beijing & Key project of Science and Technology Plan of Beijing Municipal Education Commission under Grant No. 21JD0044; and the Ruwei Dai Academician Station of Tengzhou of Shangdong Province

The use of unmanned aerial vehicles (UAVs) to perform disaster relief task is becoming more and more popular. Generally, UAVs for rescuing are required to be heterogeneous, since the types of rescue missions are diverse. There are many researches on the task allocation of heterogeneous UAVs, in which they setup tasks to be randomly distributed when simulation. However, in most cases the distribution of tasks is regular rather than random. Therefore, we setup a set of special scenarios to simulate real disaster relief tasks, where most tasks concentrate in a few small areas and others are distributed randomly. LAL algorithm is an appropriate alternative to deal with assignment problems in scenarios where tasks are completely randomly distributed, but with a bit poor performance in the scenarios above mentioned. In order to obtain better results, this paper proposes three algorithms based on LAL algorithm in such scenarios. They are the Aggregation-LAL (A-LAL) using aggregation mechanism, Dynamic Adjustment-LAL (DA-LAL) using dynamic adjustment mechanism and Aggregation and Adjustment (AA-LAL) algorithms.Through the experiments in the NetLogo simulation environment, the proposed algorithms are evaluated. The result shows improvements, which are average 5% obtained by AA-LAL, of task allocation in our special scenarios compared with existing algorithms.

Citation: Xinwei Ma, Danli Wang, Nan Zheng, Song Zhang. Aggregation and Adjustment mechanisms for disaster relief task allocation with uneven distribution. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2022015
References:
[1]

A. Altan, Ö. Aslan and R. Hacıoğlu, Model reference adaptive control of load transporting system on unmanned aerial vehicle,, in 2018 6th International Conference on Control Engineering & Information Technology (CEIT), IEEE, 2018, 1–5. doi: 10.1109/CEIT.2018.8751858.

[2]

A. Altan, Ö. Aslan and R. Hacıoğlu, Real-time control based on narx neural network of hexarotor uav with load transporting system for path tracking,, in 2018 6th International Conference On Control Engineering & information Technology (CEIT), IEEE, 2018, 1–6. doi: 10.1109/CEIT.2018.8751829.

[3]

A. Altan and R. Hacıoğlu, Model predictive control of three-axis gimbal system mounted on uav for real-time target tracking under external disturbances,, Mechanical Systems and Signal Processing, 138 (2020), 106548.  doi: 10.1016/j.ymssp.2019.106548.

[4]

J. C. AmorimV. Alves and E. P. de Freitas, Assessing a swarm-gap based solution for the task allocation problem in dynamic scenarios,, Expert Systems with Applications, 152 (2020), 113437.  doi: 10.1016/j.eswa.2020.113437.

[5]

U. BaroudiM. AlshabotiA. Koubaa and S. Trigui, Dynamic multi-objective auction-based (dymo-auction) task allocation,, Applied Sciences, 10 (2020), 3264.  doi: 10.3390/app10093264.

[6]

S.-Q. ChenY.-M. WangH.-L. Shi and X.-X. Zhang, A decision-making method for uncertain matching between volunteer teams and rescue tasks,, International Journal of Disaster Risk Reduction, 58 (2021), 102138.  doi: 10.1016/j.ijdrr.2021.102138.

[7]

M. B. DiasR. ZlotN. Kalra and A. Stentz, Market-based multirobot coordination: A survey and analysis,, Proceedings of the IEEE, 94 (2006), 1257-1270.  doi: 10.21236/ADA526116.

[8]

P. R. FerreiraF. Dos SantosA. L. BazzanD. Epstein and S. J. Waskow, Robocup rescue as multiagent task allocation among teams: Experiments with task interdependencies,, Autonomous Agents and Multi-Agent Systems, 20 (2010), 421-443.  doi: 10.1007/s10458-009-9087-8.

[9]

P. R. Ferreira Jr, F. S. Boffo and A. L. Bazzan, 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, 2007, 1–3.

[10]

W. HanC. LiangB. JiangW. Ma and Y. Zhang, Major natural disasters in china, 1985–2014: Occurrence and damages, International Journal of Environmental Research and Public Health, 13 (2016), 1118.  doi: 10.3390/ijerph13111118.

[11]

N. Hooshangi and A. A. Alesheikh, Agent-based task allocation under uncertainties in disaster environments: An approach to interval uncertainty,, International Journal of Disaster Risk Reduction, 24 (2017), 160-171.  doi: 10.1016/j.ijdrr.2017.06.010.

[12]

N. Hooshangi and A. A. Alesheikh, Developing an agent-based simulation system for post-earthquake operations in uncertainty conditions: a proposed method for collaboration among agents,, ISPRS International Journal of Geo-Information, 7 (2018), 27.  doi: 10.3390/ijgi7010027.

[13]

B. Horling and V. Lesser, A survey of multi-agent organizational paradigms,, Knowledge Engineering Review, 19 (2004), 281-316.  doi: 10.1017/S0269888905000317.

[14]

F. HuS. Yang and W. Xu, A non-dominated sorting genetic algorithm for the location and districting planning of earthquake shelters,, International Journal of Geographical Information Science, 28 (2014), 1482-1501.  doi: 10.1080/13658816.2014.894638.

[15]

N. Kalra and A. Martinoli, Comparative study of market-based and threshold-based task allocation,, in Distributed Autonomous Robotic Systems, Springer, 7 (2006), 91–101. doi: 10.1007/4-431-35881-1_10.

[16]

V. A. KazakovaA. S. Wu and G. R. Sukthankar, Respecializing swarms by forgetting reinforced thresholds, Swarm Intelligence, 14 (2020), 171-204.  doi: 10.1007/s11721-020-00181-3.

[17]

A. Khamis, A. Hussein and A. Elmogy, Multi-robot task allocation: A review of the state-of-the-art,, Cooperative Robots and Sensor Networks, 2015, 31–51. doi: 10.1007/978-3-319-18299-5_2.

[18]

M.-H. KimH. Baik and S. Lee, Response threshold model based uav search planning and task allocation,, Journal of Intelligent & Robotic Systems, 75 (2014), 625-640.  doi: 10.1007/s10846-013-9887-6.

[19]

H. Kitano, S. Tadokoro, I. Noda, H. Matsubara, T. Takahashi, A. Shinjou and S. Shimada, Robocup rescue: Search and rescue in large-scale disasters as a domain for autonomous agents research,, in IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No. 99CH37028), vol. 6, IEEE, 1999,739–743. doi: 10.1109/ICSMC.1999.816643.

[20]

D.-H. LeeS. A. Zaheer and J.-H. Kim, A resource-oriented, decentralized auction algorithm for multirobot task allocation, IEEE Transactions on Automation Science and Engineering, 12 (2015), 1469-1481.  doi: 10.1109/TASE.2014.2361334.

[21]

T. Lemaire, R. Alami and S. Lacroix, A distributed tasks allocation scheme in multi-uav context,, in IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA'04. 2004, vol. 4, IEEE, 2004, 3622–3627. doi: 10.1109/ROBOT.2004.1308816.

[22]

M.-Y. LiX.-J. ZhaoZ.-P. FanP.-P. Cao and X.-N. Qu, A model for assignment of rescuers considering multiple disaster areas, International Journal of Disaster Risk Reduction, 38 (2019), 101201.  doi: 10.1016/j.ijdrr.2019.101201.

[23]

S. Li and K. L. Teo, Post-disaster multi-period road network repair: Work scheduling and relief logistics optimization,, Annals of Operations Research, 283 (2019), 1345-1385.  doi: 10.1007/s10479-018-3037-2.

[24]

P. Scerri, A. Farinelli, S. Okamoto and M. Tambe, Allocating tasks in extreme teams,, in Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, 2005,727–734. doi: 10.1145/1082473.1082584.

[25]

C. SchumacherP. R. ChandlerM. Pachter and L. S. Pachter, Optimization of air vehicles operations using mixed-integer linear programming,, Journal of the Operational Research Society, 58 (2007), 516-527.  doi: 10.1057/palgrave.jors.2602176.

[26]

J. SchwarzrockI. ZacariasA. L. BazzanR. Q. de Araujo FernandesL. H. Moreira and E. P. de Freitas, Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence,, Engineering Applications of Artificial Intelligence, 72 (2018), 10-20.  doi: 10.1016/j.engappai.2018.03.008.

[27]

J. ShiZ. Yang and J. Zhu, An auction-based rescue task allocation approach for heterogeneous multi-robot system,, Multimedia Tools and Applications, 79 (2020), 14529-14538.  doi: 10.1007/s11042-018-7080-4.

[28]

D. B. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem,, Mathematical programming, 62 (1993), 461-474.  doi: 10.1007/BF01585178.

[29]

J. TangK. ZhuH. GuoC. GongC. Liao and S. Zhang, Using auction-based task allocation scheme for simulation optimization of search and rescue in disaster relief,, Simulation Modelling Practice and Theory, 82 (2018), 132-146.  doi: 10.1016/j.simpat.2017.12.014.

[30]

S. Tisue and U. Wilensky, Netlogo: A simple environment for modeling complexity, in International Conference on Complex Systems, vol. 21, Boston, MA, 2004, 16–21.

[31]

H. WuH. LiR. Xiao and J. Liu, Modeling and simulation of dynamic ant colony's labor division for task allocation of uav swarm,, Physica A: Statistical Mechanics and its Applications, 491 (2018), 127-141.  doi: 10.1016/j.physa.2017.08.094.

[32]

R. Xu and D. Wunsch, Clustering, vol. 10, John Wiley & Sons, 2008.

show all references

References:
[1]

A. Altan, Ö. Aslan and R. Hacıoğlu, Model reference adaptive control of load transporting system on unmanned aerial vehicle,, in 2018 6th International Conference on Control Engineering & Information Technology (CEIT), IEEE, 2018, 1–5. doi: 10.1109/CEIT.2018.8751858.

[2]

A. Altan, Ö. Aslan and R. Hacıoğlu, Real-time control based on narx neural network of hexarotor uav with load transporting system for path tracking,, in 2018 6th International Conference On Control Engineering & information Technology (CEIT), IEEE, 2018, 1–6. doi: 10.1109/CEIT.2018.8751829.

[3]

A. Altan and R. Hacıoğlu, Model predictive control of three-axis gimbal system mounted on uav for real-time target tracking under external disturbances,, Mechanical Systems and Signal Processing, 138 (2020), 106548.  doi: 10.1016/j.ymssp.2019.106548.

[4]

J. C. AmorimV. Alves and E. P. de Freitas, Assessing a swarm-gap based solution for the task allocation problem in dynamic scenarios,, Expert Systems with Applications, 152 (2020), 113437.  doi: 10.1016/j.eswa.2020.113437.

[5]

U. BaroudiM. AlshabotiA. Koubaa and S. Trigui, Dynamic multi-objective auction-based (dymo-auction) task allocation,, Applied Sciences, 10 (2020), 3264.  doi: 10.3390/app10093264.

[6]

S.-Q. ChenY.-M. WangH.-L. Shi and X.-X. Zhang, A decision-making method for uncertain matching between volunteer teams and rescue tasks,, International Journal of Disaster Risk Reduction, 58 (2021), 102138.  doi: 10.1016/j.ijdrr.2021.102138.

[7]

M. B. DiasR. ZlotN. Kalra and A. Stentz, Market-based multirobot coordination: A survey and analysis,, Proceedings of the IEEE, 94 (2006), 1257-1270.  doi: 10.21236/ADA526116.

[8]

P. R. FerreiraF. Dos SantosA. L. BazzanD. Epstein and S. J. Waskow, Robocup rescue as multiagent task allocation among teams: Experiments with task interdependencies,, Autonomous Agents and Multi-Agent Systems, 20 (2010), 421-443.  doi: 10.1007/s10458-009-9087-8.

[9]

P. R. Ferreira Jr, F. S. Boffo and A. L. Bazzan, 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, 2007, 1–3.

[10]

W. HanC. LiangB. JiangW. Ma and Y. Zhang, Major natural disasters in china, 1985–2014: Occurrence and damages, International Journal of Environmental Research and Public Health, 13 (2016), 1118.  doi: 10.3390/ijerph13111118.

[11]

N. Hooshangi and A. A. Alesheikh, Agent-based task allocation under uncertainties in disaster environments: An approach to interval uncertainty,, International Journal of Disaster Risk Reduction, 24 (2017), 160-171.  doi: 10.1016/j.ijdrr.2017.06.010.

[12]

N. Hooshangi and A. A. Alesheikh, Developing an agent-based simulation system for post-earthquake operations in uncertainty conditions: a proposed method for collaboration among agents,, ISPRS International Journal of Geo-Information, 7 (2018), 27.  doi: 10.3390/ijgi7010027.

[13]

B. Horling and V. Lesser, A survey of multi-agent organizational paradigms,, Knowledge Engineering Review, 19 (2004), 281-316.  doi: 10.1017/S0269888905000317.

[14]

F. HuS. Yang and W. Xu, A non-dominated sorting genetic algorithm for the location and districting planning of earthquake shelters,, International Journal of Geographical Information Science, 28 (2014), 1482-1501.  doi: 10.1080/13658816.2014.894638.

[15]

N. Kalra and A. Martinoli, Comparative study of market-based and threshold-based task allocation,, in Distributed Autonomous Robotic Systems, Springer, 7 (2006), 91–101. doi: 10.1007/4-431-35881-1_10.

[16]

V. A. KazakovaA. S. Wu and G. R. Sukthankar, Respecializing swarms by forgetting reinforced thresholds, Swarm Intelligence, 14 (2020), 171-204.  doi: 10.1007/s11721-020-00181-3.

[17]

A. Khamis, A. Hussein and A. Elmogy, Multi-robot task allocation: A review of the state-of-the-art,, Cooperative Robots and Sensor Networks, 2015, 31–51. doi: 10.1007/978-3-319-18299-5_2.

[18]

M.-H. KimH. Baik and S. Lee, Response threshold model based uav search planning and task allocation,, Journal of Intelligent & Robotic Systems, 75 (2014), 625-640.  doi: 10.1007/s10846-013-9887-6.

[19]

H. Kitano, S. Tadokoro, I. Noda, H. Matsubara, T. Takahashi, A. Shinjou and S. Shimada, Robocup rescue: Search and rescue in large-scale disasters as a domain for autonomous agents research,, in IEEE SMC'99 Conference Proceedings. 1999 IEEE International Conference on Systems, Man, and Cybernetics (Cat. No. 99CH37028), vol. 6, IEEE, 1999,739–743. doi: 10.1109/ICSMC.1999.816643.

[20]

D.-H. LeeS. A. Zaheer and J.-H. Kim, A resource-oriented, decentralized auction algorithm for multirobot task allocation, IEEE Transactions on Automation Science and Engineering, 12 (2015), 1469-1481.  doi: 10.1109/TASE.2014.2361334.

[21]

T. Lemaire, R. Alami and S. Lacroix, A distributed tasks allocation scheme in multi-uav context,, in IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA'04. 2004, vol. 4, IEEE, 2004, 3622–3627. doi: 10.1109/ROBOT.2004.1308816.

[22]

M.-Y. LiX.-J. ZhaoZ.-P. FanP.-P. Cao and X.-N. Qu, A model for assignment of rescuers considering multiple disaster areas, International Journal of Disaster Risk Reduction, 38 (2019), 101201.  doi: 10.1016/j.ijdrr.2019.101201.

[23]

S. Li and K. L. Teo, Post-disaster multi-period road network repair: Work scheduling and relief logistics optimization,, Annals of Operations Research, 283 (2019), 1345-1385.  doi: 10.1007/s10479-018-3037-2.

[24]

P. Scerri, A. Farinelli, S. Okamoto and M. Tambe, Allocating tasks in extreme teams,, in Proceedings of the Fourth International Joint Conference on Autonomous Agents and Multiagent Systems, 2005,727–734. doi: 10.1145/1082473.1082584.

[25]

C. SchumacherP. R. ChandlerM. Pachter and L. S. Pachter, Optimization of air vehicles operations using mixed-integer linear programming,, Journal of the Operational Research Society, 58 (2007), 516-527.  doi: 10.1057/palgrave.jors.2602176.

[26]

J. SchwarzrockI. ZacariasA. L. BazzanR. Q. de Araujo FernandesL. H. Moreira and E. P. de Freitas, Solving task allocation problem in multi unmanned aerial vehicles systems using swarm intelligence,, Engineering Applications of Artificial Intelligence, 72 (2018), 10-20.  doi: 10.1016/j.engappai.2018.03.008.

[27]

J. ShiZ. Yang and J. Zhu, An auction-based rescue task allocation approach for heterogeneous multi-robot system,, Multimedia Tools and Applications, 79 (2020), 14529-14538.  doi: 10.1007/s11042-018-7080-4.

[28]

D. B. Shmoys and É. Tardos, An approximation algorithm for the generalized assignment problem,, Mathematical programming, 62 (1993), 461-474.  doi: 10.1007/BF01585178.

[29]

J. TangK. ZhuH. GuoC. GongC. Liao and S. Zhang, Using auction-based task allocation scheme for simulation optimization of search and rescue in disaster relief,, Simulation Modelling Practice and Theory, 82 (2018), 132-146.  doi: 10.1016/j.simpat.2017.12.014.

[30]

S. Tisue and U. Wilensky, Netlogo: A simple environment for modeling complexity, in International Conference on Complex Systems, vol. 21, Boston, MA, 2004, 16–21.

[31]

H. WuH. LiR. Xiao and J. Liu, Modeling and simulation of dynamic ant colony's labor division for task allocation of uav swarm,, Physica A: Statistical Mechanics and its Applications, 491 (2018), 127-141.  doi: 10.1016/j.physa.2017.08.094.

[32]

R. Xu and D. Wunsch, Clustering, vol. 10, John Wiley & Sons, 2008.

Figure 1.  Unreasonable assignment of tasks in LAL
Figure 2.  Example of A-LAL algorithm. Task_A, task_B and task_C are assigned to agent_1 in order
Figure 3.  Unreasonable assignment of task_A
Figure 4.  Total reward of each algorithm for different scenarios
Figure 5.  Quantity of completed tasks of each algorithm for different scenarios
Figure 6.  Makespan of each algorithm for different scenarios
Figure 7.  Quality of each algorithm for different scenarios
Figure 8.  Total number of exchanged messages of each algorithm for different scenarios
Figure 9.  Runtime of each algorithm in different scenarios
Table 1.  Quality of each type of UAVs to detect the different types of task
UAV/task $ a_0 $ $ a_1 $ $ a_2 $ $ a_3 $
$ s_0 $ 1.0 0 0.3 0.5
$ s_1 $ 0 0 1.0 0
$ s_2 $ 0.2 0 0 1.0
$ s_3 $ 0 1.0 0 0.3
UAV/task $ a_0 $ $ a_1 $ $ a_2 $ $ a_3 $
$ s_0 $ 1.0 0 0.3 0.5
$ s_1 $ 0 0 1.0 0
$ s_2 $ 0.2 0 0 1.0
$ s_3 $ 0 1.0 0 0.3
Table 2.  Experimental scenarios
scenario number of UAVs number of tasks ticks as deadline px area size
i 3 15 300 $ 100 \times 100 $
ii 6 25 300 $ 150 \times 150 $
iii 9 35 300 $ 200 \times 200 $
iv 15 100 300 $ 250 \times 250 $
v 30 200 300 $ 400 \times 400 $
vi 50 300 300 $ 500 \times 500 $
vii 60 400 300 $ 600 \times 600 $
viii 100 500 300 $ 750 \times 750 $
scenario number of UAVs number of tasks ticks as deadline px area size
i 3 15 300 $ 100 \times 100 $
ii 6 25 300 $ 150 \times 150 $
iii 9 35 300 $ 200 \times 200 $
iv 15 100 300 $ 250 \times 250 $
v 30 200 300 $ 400 \times 400 $
vi 50 300 300 $ 500 \times 500 $
vii 60 400 300 $ 600 \times 600 $
viii 100 500 300 $ 750 \times 750 $
Table 3.  The mean (St. dev.) of total reward, makespan, quantity and quality of the completed tasks, number of exchanged messages and algorithm's runtime with deadline of 300 ticks for 1000 runs of each algorithm in less-tasks scenarios (scenarios i, ii and iii)
LAL A-LAL DA-LAL AA-LAL
3 UAVs and 15 tasks in area of 100 $ \times $ 100 pixels
Total reward 6.81 ($ \pm $1.96) $ 7.21 (\pm2.02)^{**} $ $ 7.10 (\pm1.95)^{**} $ $ 7.26 (\pm1.98)^{**} $
Elapsed time 0.82 ($ \pm $0.12) $ 0.82 (\pm0.12) $ $ 0.84 (\pm0.11)^{**} $ $ 0.84 (\pm0.11)^{**} $
Comp. tasks $ 0.79 (\pm0.15) $ $ 0.78 (\pm0.16) $ $ 0.79 (\pm0.16) $ $ 0.79 (\pm0.16) $
Quality $ 0.74 (\pm0.19) $ $ 0.76 (\pm0.20) $ $ 0.79 (\pm0.20)^{**} $ $ 0.78 (\pm0.21)^{**} $
Sending token $ 16.48 (\pm5.14) $ $ 12.45 (\pm4.13)^{**} $ $ 16.21 (\pm4.63) $ $ 13.07 (\pm4.32)^{**} $
Total runtime $ 0.39 (\pm0.10) $ $ 0.35 (\pm0.10)^{**} $ $ 0.55 (\pm0.25)^{**} $ $ 0.39 (\pm0.12)^{**} $
6 UAVs and 25 tasks in area of 150 $ \times $ 150 pixels
Total reward $ 15.53 (\pm2.31) $ $ 16.50 (\pm2.24)^{**} $ $ 15.81 (\pm2.26)^{**} $ $ 16.80 (\pm2.23)^{**} $
Elapsed time $ 0.90 (\pm0.06) $ $ 0.91 (\pm0.06) $ $ 0.93 (\pm0.04)^{**} $ $ 0.92 (\pm0.05)^{**} $
Comp. tasks $ 0.87 (\pm0.11) $ $ 0.88 (\pm0.10) $ $ 0.88 (\pm0.10)^* $ $ 0.89 (\pm0.10)^{**} $
Quality $ 0.82 (\pm0.13) $ $ 0.83 (\pm0.13)^{**} $ $ 0.86 (\pm0.12)^{**} $ $ 0.86 (\pm0.12)^{**} $
Sending token $ 26.83 (\pm3.61) $ $ 19.02 (\pm3.31)^{**} $ $ 27.88 (\pm3.67)^{**} $ $ 19.53 (\pm3.42)^{**} $
Total runtime $ 0.72 (\pm0.10) $ $ 0.59 (\pm0.10)^{**} $ $ 0.84 (\pm0.20)^{**} $ $ 0.63 (\pm0.12)^{**} $
9 UAVs and 35 tasks in area of 200 $ \times $ 200 pixels
Total reward $ 24.25 (\pm2.59) $ $ 25.81 (\pm2.40)^{**} $ $ 24.83 (\pm2.48)^{**} $ $ 25.96 (\pm2.35)^{**} $
Elapsed time $ 0.94 (\pm0.03) $ $ 0.95 (\pm0.03) $ $ 0.96 (\pm0.02)^{**} $ $ 0.95 (\pm0.02)^{**} $
Comp. tasks $ 0.90 (\pm0.07) $ $ 0.91 (\pm0.07)^{**} $ $ 0.91 (\pm0.07)^* $ $ 0.91 (\pm0.07)^{**} $
Quality $ 0.85 (\pm0.10) $ $ 0.87 (\pm0.09)^{**} $ $ 0.88 (\pm0.10)^{**} $ $ 0.89 (\pm0.09)^{**} $
Sending token $ 36.84 (\pm3.10) $ $ 23.95 (\pm3.07)^{**} $ $ 38.37 (\pm3.43)^{**} $ $ 24.73 (\pm3.46) ^{**} $
Total runtime $ 1.18 (\pm0.14) $ $ 0.91 (\pm0.12)^{**} $ $ 1.23 (\pm0.17)^{**} $ $ 0.94 (\pm0.14) ^{**} $
a The ‘*’ or ‘**’ in the table indicates the result of the t-Test between LAL and the other three algorithms, of which ‘**’ means p-value < 0.01 and ‘*’ means 0.01 ≤ p-value < 0.05. The same as ‘*’ or ‘**’ in the Table 4.
LAL A-LAL DA-LAL AA-LAL
3 UAVs and 15 tasks in area of 100 $ \times $ 100 pixels
Total reward 6.81 ($ \pm $1.96) $ 7.21 (\pm2.02)^{**} $ $ 7.10 (\pm1.95)^{**} $ $ 7.26 (\pm1.98)^{**} $
Elapsed time 0.82 ($ \pm $0.12) $ 0.82 (\pm0.12) $ $ 0.84 (\pm0.11)^{**} $ $ 0.84 (\pm0.11)^{**} $
Comp. tasks $ 0.79 (\pm0.15) $ $ 0.78 (\pm0.16) $ $ 0.79 (\pm0.16) $ $ 0.79 (\pm0.16) $
Quality $ 0.74 (\pm0.19) $ $ 0.76 (\pm0.20) $ $ 0.79 (\pm0.20)^{**} $ $ 0.78 (\pm0.21)^{**} $
Sending token $ 16.48 (\pm5.14) $ $ 12.45 (\pm4.13)^{**} $ $ 16.21 (\pm4.63) $ $ 13.07 (\pm4.32)^{**} $
Total runtime $ 0.39 (\pm0.10) $ $ 0.35 (\pm0.10)^{**} $ $ 0.55 (\pm0.25)^{**} $ $ 0.39 (\pm0.12)^{**} $
6 UAVs and 25 tasks in area of 150 $ \times $ 150 pixels
Total reward $ 15.53 (\pm2.31) $ $ 16.50 (\pm2.24)^{**} $ $ 15.81 (\pm2.26)^{**} $ $ 16.80 (\pm2.23)^{**} $
Elapsed time $ 0.90 (\pm0.06) $ $ 0.91 (\pm0.06) $ $ 0.93 (\pm0.04)^{**} $ $ 0.92 (\pm0.05)^{**} $
Comp. tasks $ 0.87 (\pm0.11) $ $ 0.88 (\pm0.10) $ $ 0.88 (\pm0.10)^* $ $ 0.89 (\pm0.10)^{**} $
Quality $ 0.82 (\pm0.13) $ $ 0.83 (\pm0.13)^{**} $ $ 0.86 (\pm0.12)^{**} $ $ 0.86 (\pm0.12)^{**} $
Sending token $ 26.83 (\pm3.61) $ $ 19.02 (\pm3.31)^{**} $ $ 27.88 (\pm3.67)^{**} $ $ 19.53 (\pm3.42)^{**} $
Total runtime $ 0.72 (\pm0.10) $ $ 0.59 (\pm0.10)^{**} $ $ 0.84 (\pm0.20)^{**} $ $ 0.63 (\pm0.12)^{**} $
9 UAVs and 35 tasks in area of 200 $ \times $ 200 pixels
Total reward $ 24.25 (\pm2.59) $ $ 25.81 (\pm2.40)^{**} $ $ 24.83 (\pm2.48)^{**} $ $ 25.96 (\pm2.35)^{**} $
Elapsed time $ 0.94 (\pm0.03) $ $ 0.95 (\pm0.03) $ $ 0.96 (\pm0.02)^{**} $ $ 0.95 (\pm0.02)^{**} $
Comp. tasks $ 0.90 (\pm0.07) $ $ 0.91 (\pm0.07)^{**} $ $ 0.91 (\pm0.07)^* $ $ 0.91 (\pm0.07)^{**} $
Quality $ 0.85 (\pm0.10) $ $ 0.87 (\pm0.09)^{**} $ $ 0.88 (\pm0.10)^{**} $ $ 0.89 (\pm0.09)^{**} $
Sending token $ 36.84 (\pm3.10) $ $ 23.95 (\pm3.07)^{**} $ $ 38.37 (\pm3.43)^{**} $ $ 24.73 (\pm3.46) ^{**} $
Total runtime $ 1.18 (\pm0.14) $ $ 0.91 (\pm0.12)^{**} $ $ 1.23 (\pm0.17)^{**} $ $ 0.94 (\pm0.14) ^{**} $
a The ‘*’ or ‘**’ in the table indicates the result of the t-Test between LAL and the other three algorithms, of which ‘**’ means p-value < 0.01 and ‘*’ means 0.01 ≤ p-value < 0.05. The same as ‘*’ or ‘**’ in the Table 4.
Table 4.  The mean (St.dev.) of total reward (T.r.), elapsed time (E.t.), quantity (C.t.) and quality (Q.) of the completed tasks, number of exchanged messages (S.t.) and algorithm's runtime (R.t.) with deadline of 300 ticks for 200 runs of each algorithm in more-tasks scenarios (scenarios iv, v, vi, vii and viii)
LAL A-LAL DA-LAL AA-LAL
15 UAVs and 100 tasks in area of 250 $ \times $ 250 pixels
T.r. $ 70.95 (\pm5.43) $ $ 76.03 (\pm4.44)^{**} $ $ 71.56 (\pm5.68) $ $ 76.09 (\pm4.82)^{**} $
E.t. $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $
C.t. $ 0.81 (\pm0.05) $ $ 0.85 (\pm0.04)^{**} $ $ 0.82 (\pm0.05) $ $ 0.85 (\pm0.05)^{**} $
Q. $ 0.90 (\pm0.06) $ $ 0.91 (\pm0.05)^{**} $ $ 0.92 (\pm0.06)^{**} $ $ 0.92 (\pm0.06)^{**} $
S.t. $ 86.81 (\pm5.27) $ $ 42.80 (\pm4.27)^{**} $ $ 88.86 (\pm6.35)^{**} $ $ 43.34 (\pm5.55)^{**} $
R.t. $ 7.09 (\pm0.71) $ $ 4.41 (\pm0.54)^{**} $ $ 7.47 (\pm1.17)^{**} $ $ 4.54 (\pm0.63)^{**} $
30 UAVs and 200 tasks in area of 400 $ \times $ 400 pixels
T.r. $ 147.09 (\pm7.81) $ $ 155.81 (\pm6.57) ^{**} $ $ 145.82 (\pm8.16) $ $ 154.81 (\pm7.38) ^{} $
E.t. $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $
C.t. $ 0.80 (\pm0.04) $ $ 0.84 (\pm0.03) ^{**} $ $ 0.80 (\pm0.04) $ $ 0.83 (\pm0.03) ^{**} $
Q. $ 0.92 (\pm0.05) $ $ 0.94 (\pm0.04) ^{**} $ $ 0.94 (\pm0.05) $ $ 0.94 (\pm0.04) ^{**} $
S.t. $ 169.40 (\pm8.19) $ $ 73.69 (\pm6.15) ^{**} $ $ 170.18 (\pm8.54) $ $ 73.69 (\pm6.33) ^{**} $
R.t. $ 31.83 (\pm4.78) $ $ 17.10 (\pm2.70) ^{**} $ $ 31.84 (\pm4.24) $ $ 17.40 (\pm2.81) ^{**} $
50 UAVs and 300 tasks in area of 500 $ \times $ 500 pixels
T.r. $ 237.02 (\pm10.12) $ $ 248.77 (\pm8.36) ^{**} $ $ 238.00 (\pm9.84) $ $ 250.18 (\pm8.42) ^{**} $
E.t. $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) ^{**} $ $ 0.99 (\pm0.01) ^{**} $
C.t. $ 0.85 (\pm0.03) $ $ 0.88 (\pm0.02) ^{**} $ $ 0.85 (\pm0.03) $ $ 0.89 (\pm0.02) ^{**} $
Q. $ 0.93 (\pm0.04) $ $ 0.95 (\pm0.03) ^{**} $ $ 0.94 (\pm0.04) ^{**} $ $ 0.95 (\pm0.03) ^{**} $
S.t. $ 273.05 (\pm10.39) $ $ 114.91 (\pm7.12) ^{**} $ $ 277.85 (\pm9.38) ^{**} $ $ 116.66 (\pm7.76) ^{**} $
R.t. $ 81.92 (\pm15.51) $ $ 43.72 (\pm5.77) ^{**} $ $ 83.41 (\pm8.27) $ $ 43.01 (\pm5.84) ^{**} $
60 UAVs and 400 tasks in area of 600 $ \times $ 600 pixels
T.r. $ 303.29 (\pm11.09) $ $ 315.07 (\pm10.91) ^{**} $ $ 303.45 (\pm10.97) $ $ 313.86 (\pm10.44) ^{**} $
E.t. $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $
C.t. $ 0.80 (\pm0.02) $ $ 0.83 (\pm0.02) ^{**} $ $ 0.80 (\pm0.02) $ $ 0.83 (\pm0.02) ^{**} $
Q. $ 0.94 (\pm0.03) $ $ 0.95 (\pm0.03) ^{**} $ $ 0.95 (\pm0.03) ^{**} $ $ 0.96 (\pm0.03) ^{**} $
S.t. $ 339.74 (\pm10.52) $ $ 135.63 (\pm6.96) ^{**} $ $ 344.07 (\pm10.64) ^{**} $ $ 136.00 (\pm7.95) ^{**} $
R.t. $ 149.66 (\pm15.38) $ $ 80.99 (\pm9.61) ^{**} $ $ 153.22 (\pm17.03) $ $ 82.08 (\pm11.10) ^{**} $
100 UAVs and 500 tasks in area of 750 $ \times $ 750 pixels
T.r. $ 416.84 (\pm11.40) $ $ 434.06 (\pm11.06) ^{**} $ $ 417.13 (\pm12.08) $ $ 434.20 (\pm9.92) ^{**} $
E.t. $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $
C.t. $ 0.88 (\pm0.02) $ $ 0.91 (\pm0.02) ^{**} $ $ 0.89 (\pm0.02) $ $ 0.91 (\pm0.02) ^{**} $
Q. $ 0.94 (\pm0.02) $ $ 0.95 (\pm0.02) ^{**} $ $ 0.95 (\pm0.03) ^{**} $ $ 0.96 (\pm0.02) ^{**} $
S.t. $ 480.17 (\pm10.80) $ $ 205.26 (\pm9.56) ^{**} $ $ 489.75 (\pm12.79) ^{**} $ $ 207.83 (\pm9.33) ^{**} $
R.t. $ 309.44 (\pm35.44) $ $ 158.06 (\pm20.67) ^{**} $ $ 314.83 (\pm36.04) $ $ 161.18 (\pm20.50) ^{**} $
LAL A-LAL DA-LAL AA-LAL
15 UAVs and 100 tasks in area of 250 $ \times $ 250 pixels
T.r. $ 70.95 (\pm5.43) $ $ 76.03 (\pm4.44)^{**} $ $ 71.56 (\pm5.68) $ $ 76.09 (\pm4.82)^{**} $
E.t. $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $
C.t. $ 0.81 (\pm0.05) $ $ 0.85 (\pm0.04)^{**} $ $ 0.82 (\pm0.05) $ $ 0.85 (\pm0.05)^{**} $
Q. $ 0.90 (\pm0.06) $ $ 0.91 (\pm0.05)^{**} $ $ 0.92 (\pm0.06)^{**} $ $ 0.92 (\pm0.06)^{**} $
S.t. $ 86.81 (\pm5.27) $ $ 42.80 (\pm4.27)^{**} $ $ 88.86 (\pm6.35)^{**} $ $ 43.34 (\pm5.55)^{**} $
R.t. $ 7.09 (\pm0.71) $ $ 4.41 (\pm0.54)^{**} $ $ 7.47 (\pm1.17)^{**} $ $ 4.54 (\pm0.63)^{**} $
30 UAVs and 200 tasks in area of 400 $ \times $ 400 pixels
T.r. $ 147.09 (\pm7.81) $ $ 155.81 (\pm6.57) ^{**} $ $ 145.82 (\pm8.16) $ $ 154.81 (\pm7.38) ^{} $
E.t. $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $ $ 0.98 (\pm0.01) $
C.t. $ 0.80 (\pm0.04) $ $ 0.84 (\pm0.03) ^{**} $ $ 0.80 (\pm0.04) $ $ 0.83 (\pm0.03) ^{**} $
Q. $ 0.92 (\pm0.05) $ $ 0.94 (\pm0.04) ^{**} $ $ 0.94 (\pm0.05) $ $ 0.94 (\pm0.04) ^{**} $
S.t. $ 169.40 (\pm8.19) $ $ 73.69 (\pm6.15) ^{**} $ $ 170.18 (\pm8.54) $ $ 73.69 (\pm6.33) ^{**} $
R.t. $ 31.83 (\pm4.78) $ $ 17.10 (\pm2.70) ^{**} $ $ 31.84 (\pm4.24) $ $ 17.40 (\pm2.81) ^{**} $
50 UAVs and 300 tasks in area of 500 $ \times $ 500 pixels
T.r. $ 237.02 (\pm10.12) $ $ 248.77 (\pm8.36) ^{**} $ $ 238.00 (\pm9.84) $ $ 250.18 (\pm8.42) ^{**} $
E.t. $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) ^{**} $ $ 0.99 (\pm0.01) ^{**} $
C.t. $ 0.85 (\pm0.03) $ $ 0.88 (\pm0.02) ^{**} $ $ 0.85 (\pm0.03) $ $ 0.89 (\pm0.02) ^{**} $
Q. $ 0.93 (\pm0.04) $ $ 0.95 (\pm0.03) ^{**} $ $ 0.94 (\pm0.04) ^{**} $ $ 0.95 (\pm0.03) ^{**} $
S.t. $ 273.05 (\pm10.39) $ $ 114.91 (\pm7.12) ^{**} $ $ 277.85 (\pm9.38) ^{**} $ $ 116.66 (\pm7.76) ^{**} $
R.t. $ 81.92 (\pm15.51) $ $ 43.72 (\pm5.77) ^{**} $ $ 83.41 (\pm8.27) $ $ 43.01 (\pm5.84) ^{**} $
60 UAVs and 400 tasks in area of 600 $ \times $ 600 pixels
T.r. $ 303.29 (\pm11.09) $ $ 315.07 (\pm10.91) ^{**} $ $ 303.45 (\pm10.97) $ $ 313.86 (\pm10.44) ^{**} $
E.t. $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $
C.t. $ 0.80 (\pm0.02) $ $ 0.83 (\pm0.02) ^{**} $ $ 0.80 (\pm0.02) $ $ 0.83 (\pm0.02) ^{**} $
Q. $ 0.94 (\pm0.03) $ $ 0.95 (\pm0.03) ^{**} $ $ 0.95 (\pm0.03) ^{**} $ $ 0.96 (\pm0.03) ^{**} $
S.t. $ 339.74 (\pm10.52) $ $ 135.63 (\pm6.96) ^{**} $ $ 344.07 (\pm10.64) ^{**} $ $ 136.00 (\pm7.95) ^{**} $
R.t. $ 149.66 (\pm15.38) $ $ 80.99 (\pm9.61) ^{**} $ $ 153.22 (\pm17.03) $ $ 82.08 (\pm11.10) ^{**} $
100 UAVs and 500 tasks in area of 750 $ \times $ 750 pixels
T.r. $ 416.84 (\pm11.40) $ $ 434.06 (\pm11.06) ^{**} $ $ 417.13 (\pm12.08) $ $ 434.20 (\pm9.92) ^{**} $
E.t. $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $ $ 0.99 (\pm0.01) $
C.t. $ 0.88 (\pm0.02) $ $ 0.91 (\pm0.02) ^{**} $ $ 0.89 (\pm0.02) $ $ 0.91 (\pm0.02) ^{**} $
Q. $ 0.94 (\pm0.02) $ $ 0.95 (\pm0.02) ^{**} $ $ 0.95 (\pm0.03) ^{**} $ $ 0.96 (\pm0.02) ^{**} $
S.t. $ 480.17 (\pm10.80) $ $ 205.26 (\pm9.56) ^{**} $ $ 489.75 (\pm12.79) ^{**} $ $ 207.83 (\pm9.33) ^{**} $
R.t. $ 309.44 (\pm35.44) $ $ 158.06 (\pm20.67) ^{**} $ $ 314.83 (\pm36.04) $ $ 161.18 (\pm20.50) ^{**} $
[1]

Linet Ozdamar, Dilek Tuzun Aksu, Elifcan Yasa, Biket Ergunes. Disaster relief routing in limited capacity road networks with heterogeneous flows. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1367-1380. doi: 10.3934/jimo.2018011

[2]

Steve Drekic, Jae-Kyung Woo, Ran Xu. A threshold-based risk process with a waiting period to pay dividends. Journal of Industrial and Management Optimization, 2018, 14 (3) : 1179-1201. doi: 10.3934/jimo.2018005

[3]

Jinlong Guo, Bin Li, Yuandong Ji. A control parametrization based path planning method for the quad-rotor uavs. Journal of Industrial and Management Optimization, 2022, 18 (2) : 1079-1100. doi: 10.3934/jimo.2021009

[4]

Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103

[5]

Sin-Man Choi, Ximin Huang, Wai-Ki Ching. Minimizing equilibrium expected sojourn time via performance-based mixed threshold demand allocation in a multiple-server queueing environment. Journal of Industrial and Management Optimization, 2012, 8 (2) : 299-323. doi: 10.3934/jimo.2012.8.299

[6]

Junjie Peng, Ning Chen, Jiayang Dai, Weihua Gui. A goethite process modeling method by Asynchronous Fuzzy Cognitive Network based on an improved constrained chicken swarm optimization algorithm. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1269-1287. doi: 10.3934/jimo.2020021

[7]

Yingjing Shi, Rui Li, Honglei Xu. Control augmentation design of UAVs based on deviation modification of aerodynamic focus. Journal of Industrial and Management Optimization, 2015, 11 (1) : 231-240. doi: 10.3934/jimo.2015.11.231

[8]

Miao Yu. A solution of TSP based on the ant colony algorithm improved by particle swarm optimization. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 979-987. doi: 10.3934/dcdss.2019066

[9]

Zhongqiang Wu, Zongkui Xie. A multi-objective lion swarm optimization based on multi-agent. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022001

[10]

Yufeng Zhou, Bin Zheng, Jiafu Su, Yufeng Li. The joint location-transportation model based on grey bi-level programming for early post-earthquake relief. Journal of Industrial and Management Optimization, 2022, 18 (1) : 45-73. doi: 10.3934/jimo.2020142

[11]

Raymond Ching Man Chan, Henry Ying Kei Lau. An AIS-based optimal control framework for longevity and task achievement of multi-robot systems. Numerical Algebra, Control and Optimization, 2012, 2 (1) : 45-56. doi: 10.3934/naco.2012.2.45

[12]

Cheng-Ta Yeh, Yi-Kuei Lin. Component allocation cost minimization for a multistate computer network subject to a reliability threshold using tabu search. Journal of Industrial and Management Optimization, 2016, 12 (1) : 141-167. doi: 10.3934/jimo.2016.12.141

[13]

Jafar Sadeghi, Mojtaba Ghiyasi, Akram Dehnokhalaji. Resource allocation and target setting based on virtual profit improvement. Numerical Algebra, Control and Optimization, 2020, 10 (2) : 127-142. doi: 10.3934/naco.2019043

[14]

Frederike Kissling, Christian Rohde. The computation of nonclassical shock waves with a heterogeneous multiscale method. Networks and Heterogeneous Media, 2010, 5 (3) : 661-674. doi: 10.3934/nhm.2010.5.661

[15]

Min Zhang, Gang Li. Multi-objective optimization algorithm based on improved particle swarm in cloud computing environment. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1413-1426. doi: 10.3934/dcdss.2019097

[16]

Ning Lu, Ying Liu. Application of support vector machine model in wind power prediction based on particle swarm optimization. Discrete and Continuous Dynamical Systems - S, 2015, 8 (6) : 1267-1276. doi: 10.3934/dcdss.2015.8.1267

[17]

Abdulrazzaq T. Abed, Azzam S. Y. Aladool. Applying particle swarm optimization based on Padé approximant to solve ordinary differential equation. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 321-337. doi: 10.3934/naco.2021008

[18]

Yunhai Xiao, Soon-Yi Wu, Bing-Sheng He. A proximal alternating direction method for $\ell_{2,1}$-norm least squares problem in multi-task feature learning. Journal of Industrial and Management Optimization, 2012, 8 (4) : 1057-1069. doi: 10.3934/jimo.2012.8.1057

[19]

Lili Liu, Xianning Liu, Jinliang Wang. Threshold dynamics of a delayed multi-group heroin epidemic model in heterogeneous populations. Discrete and Continuous Dynamical Systems - B, 2016, 21 (8) : 2615-2630. doi: 10.3934/dcdsb.2016064

[20]

Shunfu Jin, Wuyi Yue, Zsolt Saffer. Analysis and optimization of a gated polling based spectrum allocation mechanism in cognitive radio networks. Journal of Industrial and Management Optimization, 2016, 12 (2) : 687-702. doi: 10.3934/jimo.2016.12.687

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (230)
  • HTML views (109)
  • Cited by (0)

Other articles
by authors

[Back to Top]