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

Xinwei Ma; Danli Wang; Nan Zheng; Song Zhang

doi:10.3934/jimo.2022015

Article Contents

2023, Volume 19, Issue 3: 1734-1754. Doi: 10.3934/jimo.2022015

This issue Previous Article A dynamic analysis of a monopolist's quality improvement, process innovation and goodwill Next Article A global optimization method for multiple response optimization problems

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
^* Corresponding author: Danli Wang

Received: April 2021

Revised: November 2021

Early access: February 2022

Published: March 2023

This research is supported by the National Natural Science Foundation of China under Grant No. 61872363; the Natural Science Foundation of Beijing & Key project of Science and Technology Plan of Beijing Municipal Education Commission under Grant No. 21JD0044; the Strategic Priority Research Program of Chinese Academy of Sciences, Grant No. XDA27000000; 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; and the Ruwei Dai Academician Station of Tengzhou of Shandong Province.

Abstract / Introduction Full Text(HTML) Figure(9) / Table(4) Related Papers Cited by

Abstract

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.

Note: The project funding information is updated.

Keywords:

Mathematics Subject Classification: Primary: 68T42, 90C27.

Citation:

Full Text(HTML)

Figure 1. Unreasonable assignment of tasks in LAL

Download: Full-size image PowerPoint slide

Figure 2. Example of A-LAL algorithm. Task_A, task_B and task_C are assigned to agent_1 in order

Download: Full-size image PowerPoint slide

Figure 3. Unreasonable assignment of task_A

Download: Full-size image PowerPoint slide

Figure 4. Total reward of each algorithm for different scenarios

Download: Full-size image PowerPoint slide

Figure 5. Quantity of completed tasks of each algorithm for different scenarios

Download: Full-size image PowerPoint slide

Figure 6. Makespan of each algorithm for different scenarios

Download: Full-size image PowerPoint slide

Figure 7. Quality of each algorithm for different scenarios

Download: Full-size image PowerPoint slide

Figure 8. Total number of exchanged messages of each algorithm for different scenarios

Download: Full-size image PowerPoint slide

Figure 9. Runtime of each algorithm in different scenarios

Download: Full-size image PowerPoint slide

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

| Show Table

DownLoad: CSV

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 $

| Show Table

DownLoad: CSV

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.

| Show Table

DownLoad: CSV

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) ^{**} $

| Show Table

DownLoad: CSV

Related Papers

Cited by

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. Amorim, V. 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. Baroudi, M. Alshaboti, A. 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. Chen, Y.-M. Wang, H.-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. Dias, R. Zlot, N. 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. Ferreira, F. Dos Santos, A. L. Bazzan, D. 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. Han, C. Liang, B. Jiang, W. 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. Hu, S. 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. Kazakova, A. 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. Kim, H. 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. Lee, S. 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. Li, X.-J. Zhao, Z.-P. Fan, P.-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. Schumacher, P. R. Chandler, M. 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. Schwarzrock, I. Zacarias, A. L. Bazzan, R. Q. de Araujo Fernandes, L. 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. Shi, Z. 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. Tang, K. Zhu, H. Guo, C. Gong, C. 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. Wu, H. Li, R. 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.