{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,6,25]],"date-time":"2024-06-25T06:38:13Z","timestamp":1719297493657},"reference-count":75,"publisher":"Association for Computing Machinery (ACM)","issue":"3-4","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61932007, 62076060, 71971109, and 62176056"],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of Jiangsu Province of China","award":["BK20201394"]},{"name":"Defense Industrial Technology Development Program","award":["JCKY2021214B002"]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"\n Existing studies on the multirobot foraging problem often assume safe settings, in which nothing in an environment hinders the robots\u2019 tasks. In many real-world applications, robots have to collect objects from hazardous environments like earthquake rescue, where possible risks exist, with possibilities of destroying robots. At this stage, there are no targeted algorithms for foraging robots in hazardous environments, which can lead to damage to the robot itself and reduce the final foraging efficiency. A motivating example is a rescue scenario, in which the lack of a suitable solution results in many victims not being rescued after all available robots have been destroyed. Foraging robots face a dilemma after some robots have been destroyed: whether to take over tasks of the destroyed robots or continue executing their remaining foraging tasks. The challenges that arise when attempting such a balance are twofold: (1) the loss of robots adds new constraints to traditional problems, complicating the structure of the solution space, and (2) the task allocation strategy in a multirobot team affects the final expected utility, thereby increasing the dimension of the solution space. In this study, we address these challenges in two fundamental environmental settings: homogeneous and heterogeneous cases. For the former case, a decomposition and grafting mechanism is adopted to split this problem into two weakly coupled problems: the foraging task execution problem and the foraging task allocation problem. We propose an exact foraging task allocation algorithm, and graft it to another exact foraging task execution algorithm to find an optimal solution within the polynomial time. For the latter case, it is proven\n \n \\( \\mathcal {NP} \\)<\/jats:tex-math>\n <\/jats:inline-formula>\n -hard to find an optimal solution in polynomial time. The decomposition and grafting mechanism is also adopted here, and our proposed greedy risk-aware foraging algorithm is grafted to our proposed hierarchical agglomerative clustering algorithm to find high-utility solutions with low computational overhead. Finally, these algorithms are extensively evaluated through simulations, demonstrating that compared with various benchmarks, they can significantly increase the utility of objects returned by robots before all the robots have been stopped.\n <\/jats:p>","DOI":"10.1145\/3514251","type":"journal-article","created":{"date-parts":[[2022,3,26]],"date-time":"2022-03-26T11:15:57Z","timestamp":1648293357000},"page":"1-38","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Risk-aware Collection Strategies for Multirobot Foraging in Hazardous Environments"],"prefix":"10.1145","volume":"16","author":[{"ORCID":"http:\/\/orcid.org\/0000-0002-7929-0682","authenticated-orcid":false,"given":"Kai","family":"Di","sequence":"first","affiliation":[{"name":"Southeast University, Nanjing, China"}]},{"given":"Yifeng","family":"Zhou","sequence":"additional","affiliation":[{"name":"Southeast University, Nanjing, China"}]},{"given":"Jiuchuan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Nanjing University of Finance and Economics, Nanjing, China"}]},{"given":"Fuhan","family":"Yan","sequence":"additional","affiliation":[{"name":"Chongqing University of Posts and Telecommunications, Chongqing, China"}]},{"given":"Shaofu","family":"Yang","sequence":"additional","affiliation":[{"name":"Southeast University, Nanjing, China"}]},{"given":"Yichuan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Southeast University, Nanjing, China"}]}],"member":"320","published-online":{"date-parts":[[2022,7,6]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/731"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/2208436.2208459"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2008.04.003"},{"key":"e_1_3_2_5_2","first-page":"1311","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems","author":"Alers Sjriek","year":"2011","unstructured":"Sjriek Alers, Daan Bloembergen, Daniel Hennes, Steven De Jong, Michael Kaisers, Nyree Lemmens, Karl Tuyls, and Gerhard Weiss. 2011. Bee-inspired foraging in an embodied swarm. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 1311\u20131312."},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-012-0559-4"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2016.2524018"},{"key":"e_1_3_2_8_2","first-page":"1777","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems","author":"Baker Chris A. B.","year":"2016","unstructured":"Chris A. B. Baker, Sarvapali Ramchurn, W. T. Luke Teacy, and Nicholas R. Jennings. 2016. Planning search and rescue missions for UAV teams. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 1777\u20131782."},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2000.844042"},{"key":"e_1_3_2_10_2","first-page":"1024","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems","author":"Beck Zolt\u00e1n","year":"2016","unstructured":"Zolt\u00e1n Beck, Luke Teacy, Alex Rogers, and Nicholas R. Jennings. 2016. Online planning for collaborative search and rescue by heterogeneous robot teams. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 1024\u20131033."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1126\/science.153.3731.34"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10479-011-0895-2"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3078847"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-015-0117-7"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.1145\/2661829.2661882"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.5555\/2692097.2692099"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1109\/TRO.2009.2022423"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364918781009"},{"key":"e_1_3_2_19_2","volume-title":"Introduction to Algorithms","author":"Cormen Thomas H.","year":"2009","unstructured":"Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. 2009. Introduction to Algorithms. MIT Press, Cambridge, MA."},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.6.1.80"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01417909"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2013.2"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2002.1183896"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-017-1151-6"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21496"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00265-015-2035-5"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33019452"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1109\/SIS.2007.368024"},{"key":"e_1_3_2_29_2","first-page":"415","volume-title":"Annales Zoologici Fennici","author":"Gautrais Jacques","year":"2008","unstructured":"Jacques Gautrais, Christian Jost, and Guy Theraulaz. 2008. Key behavioural factors in a self-organised fish school model. In Annales Zoologici Fennici, Vol. 45. BioOne, 415\u2013428."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/0377-2217(95)00050-X"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-2217(99)00073-9"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-77778-8"},{"key":"e_1_3_2_33_2","volume-title":"Robust Statistics","author":"Huber Peter J.","year":"2004","unstructured":"Peter J. Huber. 2004. Robust Statistics. Vol. 523. John Wiley & Sons."},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1109\/90.865077"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90012-4"},{"key":"e_1_3_2_36_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-017-9694-1"},{"key":"e_1_3_2_37_2","first-page":"3122","volume-title":"Proceedings of the IEEE International Conference on Robotics and Automation","author":"Khan Asif","year":"2014","unstructured":"Asif Khan, Evsen Yanmaz, and Bernhard Rinner. 2014. Information merging in multi-UAV coperative search. In Proceedings of the IEEE International Conference on Robotics and Automation. IEEE, 3122\u20133129."},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.cie.2019.01.020"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364908091153"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10732-010-9153-z"},{"key":"e_1_3_2_41_2","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1996.190"},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364906063426"},{"key":"e_1_3_2_43_2","first-page":"1325","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems","author":"Liemhetcharat Somchaya","year":"2015","unstructured":"Somchaya Liemhetcharat, Rui Yan, Rui Yan, and Keng Peng Tee. 2015. Continuous foraging and information gathering in a multi-agent team. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 1325\u20131333."},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.02.004"},{"key":"e_1_3_2_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2016.7759561"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1109\/TII.2017.2757606"},{"key":"e_1_3_2_47_2","first-page":"969","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Nikolova Evdokia","year":"2008","unstructured":"Evdokia Nikolova and David R. Karger. 2008. Route planning under uncertainty: The canadian traveller problem. In Proceedings of the AAAI Conference on Artificial Intelligence. 969\u2013974."},{"key":"e_1_3_2_48_2","first-page":"36","volume-title":"Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems","author":"Panait Liviu","year":"2004","unstructured":"Liviu Panait and Sean Luke. 2004. A pheromone-based utility model for collaborative foraging. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems. IEEE, 36\u201343."},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.2307\/1543482"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2012.08.015"},{"key":"e_1_3_2_51_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-016-0118-1"},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAES.2012.6237608"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1002\/net.21628"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0065-3454(06)36007-X"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.5555\/1883405.1883419"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1109\/70.97883"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.3.4.376"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.chemolab.2006.08.015"},{"key":"e_1_3_2_59_2","first-page":"4544","volume-title":"Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems","author":"Shapira Yaniv","year":"2015","unstructured":"Yaniv Shapira and Noa Agmon. 2015. Path planning for optimizing survivability of multi-robot formation in adversarial environments. In Proceedings of the IEEE\/RSJ International Conference on Intelligent Robots and Systems. 4544\u20134549."},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2006.281996"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11721-014-0093-3"},{"key":"e_1_3_2_62_2","first-page":"1093","volume-title":"Proceedings of the International Conference on Autonomous Agents & Multiagent Systems","author":"Sless Efrat","year":"2014","unstructured":"Efrat Sless, Noa Agmon, and Sarit Kraus. 2014. Multi-robot adversarial patrolling: Facing coordinated attacks. In Proceedings of the International Conference on Autonomous Agents & Multiagent Systems. 1093\u20131100."},{"issue":"12","key":"e_1_3_2_63_2","first-page":"1","article-title":"Sophisticated collective foraging with minimalist agents: A swarm robotics test","volume":"35","author":"Talamali Mohamed S.","year":"2019","unstructured":"Mohamed S. Talamali, Thomas Bose, Matthew Haire, Xu Xu, James A. R. Marshall, and Andreagiovanni Reina. 2019. Sophisticated collective foraging with minimalist agents: A swarm robotics test. Int. J. Robot. Res. 35, 12 (2019), 1\u201332.","journal-title":"Int. J. Robot. Res."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1109\/TAES.2017.2761139"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1287\/trsc.3.3.192"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00442-016-3648-8"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2010.03.045"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018957401093"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1177\/02783640022066716"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-30440-3_217"},{"key":"e_1_3_2_71_2","first-page":"185","article-title":"Towards an engineering science of robot foraging","author":"Winfield Alan F. T.","year":"2009","unstructured":"Alan F. T. Winfield. 2009. Towards an engineering science of robot foraging. Distrib. Auton. Robot. Syst. (2009), 185\u2013192.","journal-title":"Distrib. Auton. Robot. Syst."},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-011-0221-2"},{"key":"e_1_3_2_73_2","first-page":"1","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multiagent Systems","author":"Yehoshua Roi","year":"2015","unstructured":"Roi Yehoshua and Noa Agmon. 2015. Adversarial modeling in the robotic coverage problem. In Proceedings of the International Conference on Autonomous Agents and Multiagent Systems. 1\u20137."},{"key":"e_1_3_2_74_2","first-page":"1493","volume-title":"Proceedings of the European Conference on Artificial Intelligence","author":"Yehoshua Roi","year":"2016","unstructured":"Roi Yehoshua and Noa Agmon. 2016. Multi-robot adversarial coverage. In Proceedings of the European Conference on Artificial Intelligence. 1493\u20131501."},{"key":"e_1_3_2_75_2","doi-asserted-by":"publisher","DOI":"10.1177\/0278364915625785"},{"key":"e_1_3_2_76_2","article-title":"Expertise-aware truth analysis and task allocation in Mobile crowdsourcing","author":"Zhang Xiaomei","year":"2019","unstructured":"Xiaomei Zhang, Yibo Wu, Lifu Huang, Heng Ji, and Guohong Cao. 2019. Expertise-aware truth analysis and task allocation in Mobile crowdsourcing. IEEE Trans. Mobile Comput. (2019).","journal-title":"IEEE Trans. Mobile Comput."}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514251","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T21:40:15Z","timestamp":1672609215000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514251"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,12,31]]},"references-count":75,"journal-issue":{"issue":"3-4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3514251"],"URL":"https:\/\/doi.org\/10.1145\/3514251","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"value":"1556-4665","type":"print"},{"value":"1556-4703","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,12,31]]},"assertion":[{"value":"2021-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-07-06","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}