{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,21]],"date-time":"2025-11-21T12:28:56Z","timestamp":1763728136828,"version":"3.41.0"},"reference-count":76,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2022,6,11]],"date-time":"2022-06-11T00:00:00Z","timestamp":1654905600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62076060, 61932007, 71971109, 61703097"],"award-info":[{"award-number":["62076060, 61932007, 71971109, 61703097"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Natural Science Foundation of Jiangsu Province of China","award":["BK20201394"],"award-info":[{"award-number":["BK20201394"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Intell. Syst. Technol."],"published-print":{"date-parts":[[2022,10,31]]},"abstract":"<jats:p>\n            As an essential problem in robotics, foraging means that robots collect objects from a given environment and return them to a specified location. On many occasions, robots are required to perform foraging tasks in adversarial environments, such as battlefield rescue, where potential adversaries may damage robots with a certain probability. The longer an individual robot moves through adversarial environments, the higher the probability of being damaged by adversaries. The robot system can gain utility only when the robot brings carried objects back to a predetermined home station. Such a risk of being damaged makes returning home at different locations potentially relevant to the expected utility produced by the robot. Thus, the individual robot faces a dilemma when it responds to the potential risks in adversarial environments: whether to return the carried resources home or continue foraging tasks. In this article, two fundamental environment settings are discussed, homogeneous cases and heterogeneous cases. The former is analyzed as having both the optimal substructure property and the non-aftereffect property. Then, we present a dynamic programming (DP) algorithm that can find an optimal solution with polynomial time complexity. For the latter, it is proven that finding an optimal solution is\n            <jats:inline-formula content-type=\"math\/tex\">\n              <jats:tex-math notation=\"LaTeX\" version=\"MathJax\">\\( \\mathcal {NP} \\)<\/jats:tex-math>\n            <\/jats:inline-formula>\n            -hard. We then propose a heuristic algorithm: A division hierarchical path planning (DHPP) algorithm that is based on the idea of dividing the foraging routes generated initially into a certain number of subroutes to dilute risks. Finally, these algorithms are extensively evaluated in simulations, concluding that in adversarial environments, they can significantly improve the productivity of an individual robot before it is damaged.\n          <\/jats:p>","DOI":"10.1145\/3514499","type":"journal-article","created":{"date-parts":[[2022,2,4]],"date-time":"2022-02-04T22:16:06Z","timestamp":1644012966000},"page":"1-29","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["A Foraging Strategy with Risk Response for Individual Robots in Adversarial Environments"],"prefix":"10.1145","volume":"13","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7929-0682","authenticated-orcid":false,"given":"Kai","family":"Di","sequence":"first","affiliation":[{"name":"Southeast University, Southeast University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yifeng","family":"Zhou","sequence":"additional","affiliation":[{"name":"Southeast University, Southeast University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7983-1549","authenticated-orcid":false,"given":"Fuhan","family":"Yan","sequence":"additional","affiliation":[{"name":"Chongqing University of Posts and Telecommunications, Chongqing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jiuchuan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Nanjing University of Finance and Economics, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shaofu","family":"Yang","sequence":"additional","affiliation":[{"name":"Southeast University, Southeast University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yichuan","family":"Jiang","sequence":"additional","affiliation":[{"name":"Southeast University, Southeast University, Nanjing, China"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2022,6,11]]},"reference":[{"doi-asserted-by":"publisher","key":"e_1_3_2_2_2","DOI":"10.24963\/ijcai.2017\/731"},{"doi-asserted-by":"publisher","key":"e_1_3_2_3_2","DOI":"10.5555\/2208436.2208459"},{"doi-asserted-by":"publisher","key":"e_1_3_2_4_2","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","first-page":"1683","volume-title":"Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems","author":"Alers Sjriek","year":"2014","unstructured":"Sjriek Alers, Daniel Claes, Karl Tuyls, and Gerhard Weiss. 2014. Biologically inspired multi-robot foraging. In Proceedings of the International Conference on Autonomous Agents and Multi-Agent Systems. 1683\u20131684."},{"doi-asserted-by":"publisher","key":"e_1_3_2_7_2","DOI":"10.1007\/s11590-012-0559-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_8_2","DOI":"10.1109\/TRO.2016.2524018"},{"key":"e_1_3_2_9_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_10_2","DOI":"10.1109\/ROBOT.2000.844042"},{"key":"e_1_3_2_11_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_12_2","DOI":"10.1126\/science.153.3731.34"},{"key":"e_1_3_2_13_2","volume-title":"Applied Dynamic Programming","author":"Bellman Richard E.","year":"2015","unstructured":"Richard E. Bellman and Stuart E. Dreyfus. 2015. Applied Dynamic Programming. Princeton University Press."},{"doi-asserted-by":"publisher","key":"e_1_3_2_14_2","DOI":"10.1098\/rstb.1998.0310"},{"doi-asserted-by":"publisher","key":"e_1_3_2_15_2","DOI":"10.1109\/ACC.2000.878915"},{"doi-asserted-by":"publisher","key":"e_1_3_2_16_2","DOI":"10.1007\/s10479-011-0895-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_17_2","DOI":"10.1145\/3078847"},{"doi-asserted-by":"publisher","key":"e_1_3_2_18_2","DOI":"10.1145\/3078842"},{"doi-asserted-by":"publisher","key":"e_1_3_2_19_2","DOI":"10.1177\/0278364918781009"},{"key":"e_1_3_2_20_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, Massachusetts."},{"doi-asserted-by":"publisher","key":"e_1_3_2_21_2","DOI":"10.1007\/BF01417909"},{"doi-asserted-by":"publisher","key":"e_1_3_2_22_2","DOI":"10.1109\/TCBB.2013.2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_23_2","DOI":"10.1007\/s10846-019-00996-1"},{"issue":"1","key":"e_1_3_2_24_2","first-page":"1","article-title":"Risk-aware collection strategies for multirobot foraging in hazardous environments","volume":"1","author":"Di Kai","year":"2022","unstructured":"Kai Di, Yifeng Zhou, Jiuchuan Jiang, Fuhan Yan, Shaofu Yang, and Yichuan Jiang. 2022. Risk-aware collection strategies for multirobot foraging in hazardous environments. ACM Transactions on Autonomous and Adaptive Systems 1, 1 (2022), 1\u201339.","journal-title":"ACM Transactions on Autonomous and Adaptive Systems"},{"doi-asserted-by":"publisher","key":"e_1_3_2_25_2","DOI":"10.1109\/ICDM.2002.1183896"},{"doi-asserted-by":"publisher","key":"e_1_3_2_26_2","DOI":"10.5555\/3288898.3288948"},{"doi-asserted-by":"publisher","key":"e_1_3_2_27_2","DOI":"10.1145\/2875441"},{"doi-asserted-by":"publisher","key":"e_1_3_2_28_2","DOI":"10.1007\/s00265-015-2035-5"},{"doi-asserted-by":"publisher","key":"e_1_3_2_29_2","DOI":"10.1609\/aaai.v33i01.33019452"},{"doi-asserted-by":"publisher","key":"e_1_3_2_30_2","DOI":"10.5735\/086.045.0505"},{"doi-asserted-by":"publisher","key":"e_1_3_2_31_2","DOI":"10.1007\/11539902_91"},{"doi-asserted-by":"publisher","key":"e_1_3_2_32_2","DOI":"10.1016\/0377-2217(95)00050-X"},{"doi-asserted-by":"publisher","key":"e_1_3_2_33_2","DOI":"10.1177\/0278364904045564"},{"doi-asserted-by":"publisher","key":"e_1_3_2_34_2","DOI":"10.1007\/978-0-387-77778-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_35_2","DOI":"10.24963\/ijcai.2019\/908"},{"doi-asserted-by":"publisher","key":"e_1_3_2_36_2","DOI":"10.1007\/978-3-662-10306-7"},{"key":"e_1_3_2_37_2","volume-title":"Robust Statistics","author":"Huber Peter J.","year":"2004","unstructured":"Peter J. Huber. 2004. Robust Statistics, Vol. 523. John Wiley & Sons."},{"doi-asserted-by":"publisher","key":"e_1_3_2_38_2","DOI":"10.1093\/genetics\/141.4.1537"},{"doi-asserted-by":"publisher","key":"e_1_3_2_39_2","DOI":"10.1109\/90.865077"},{"doi-asserted-by":"publisher","key":"e_1_3_2_40_2","DOI":"10.1016\/0196-6774(85)90012-4"},{"doi-asserted-by":"publisher","key":"e_1_3_2_41_2","DOI":"10.1007\/s10514-017-9694-1"},{"key":"e_1_3_2_42_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_43_2","DOI":"10.1177\/0278364908091153"},{"doi-asserted-by":"publisher","key":"e_1_3_2_44_2","DOI":"10.1007\/s10732-010-9153-z"},{"doi-asserted-by":"publisher","key":"e_1_3_2_45_2","DOI":"10.1057\/jors.1996.190"},{"doi-asserted-by":"publisher","key":"e_1_3_2_46_2","DOI":"10.1177\/0278364906063426"},{"key":"e_1_3_2_47_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_48_2","DOI":"10.1109\/IROS.2007.4399605"},{"doi-asserted-by":"publisher","key":"e_1_3_2_49_2","DOI":"10.1016\/j.artint.2019.02.004"},{"doi-asserted-by":"publisher","key":"e_1_3_2_50_2","DOI":"10.1109\/IROS.2016.7759561"},{"doi-asserted-by":"publisher","key":"e_1_3_2_51_2","DOI":"10.1038\/275642a0"},{"key":"e_1_3_2_52_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 traveler problem. In Proceedings of the AAAI Conference on Artificial Intelligence. 969\u2013974."},{"doi-asserted-by":"publisher","key":"e_1_3_2_53_2","DOI":"10.1016\/0304-3975(91)90263-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_54_2","DOI":"10.2307\/1543482"},{"doi-asserted-by":"publisher","key":"e_1_3_2_55_2","DOI":"10.1016\/j.ejor.2012.08.015"},{"doi-asserted-by":"publisher","key":"e_1_3_2_56_2","DOI":"10.1007\/s11721-016-0118-1"},{"doi-asserted-by":"publisher","key":"e_1_3_2_57_2","DOI":"10.1109\/TAES.2012.6237608"},{"doi-asserted-by":"publisher","key":"e_1_3_2_58_2","DOI":"10.1002\/net.21628"},{"doi-asserted-by":"publisher","key":"e_1_3_2_59_2","DOI":"10.5555\/1883405.1883419"},{"doi-asserted-by":"publisher","key":"e_1_3_2_60_2","DOI":"10.1109\/70.97883"},{"doi-asserted-by":"publisher","key":"e_1_3_2_61_2","DOI":"10.2307\/1936663"},{"doi-asserted-by":"publisher","key":"e_1_3_2_62_2","DOI":"10.1287\/ijoc.3.4.376"},{"doi-asserted-by":"publisher","key":"e_1_3_2_63_2","DOI":"10.1016\/j.chemolab.2006.08.015"},{"key":"e_1_3_2_64_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_65_2","DOI":"10.1109\/IROS.2006.281996"},{"key":"e_1_3_2_66_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_67_2","DOI":"10.1109\/TAES.2017.2761139"},{"doi-asserted-by":"publisher","key":"e_1_3_2_68_2","DOI":"10.1007\/s00442-016-3648-8"},{"doi-asserted-by":"publisher","key":"e_1_3_2_69_2","DOI":"10.1016\/j.ejor.2010.03.045"},{"doi-asserted-by":"publisher","key":"e_1_3_2_70_2","DOI":"10.1016\/j.cie.2016.01.018"},{"doi-asserted-by":"publisher","key":"e_1_3_2_71_2","DOI":"10.1007\/978-0-387-30440-3_217"},{"doi-asserted-by":"publisher","key":"e_1_3_2_72_2","DOI":"10.1007\/s10618-011-0221-2"},{"doi-asserted-by":"publisher","key":"e_1_3_2_73_2","DOI":"10.1016\/j.robot.2019.01.017"},{"doi-asserted-by":"publisher","key":"e_1_3_2_74_2","DOI":"10.1007\/s10846-018-0841-5"},{"key":"e_1_3_2_75_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."},{"doi-asserted-by":"publisher","key":"e_1_3_2_76_2","DOI":"10.1177\/0278364915625785"},{"key":"e_1_3_2_77_2","first-page":"2725","volume-title":"Proceedings of the International Joint Conference on Artificial Intelligence","author":"Zhang Ruohan","year":"2016","unstructured":"Ruohan Zhang and Zhao Song. 2016. Maximum sustainable yield problem for robot foraging and construction system. In Proceedings of the International Joint Conference on Artificial Intelligence. 2725\u20132731."}],"container-title":["ACM Transactions on Intelligent Systems and Technology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514499","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3514499","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T19:30:21Z","timestamp":1750188621000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3514499"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,11]]},"references-count":76,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2022,10,31]]}},"alternative-id":["10.1145\/3514499"],"URL":"https:\/\/doi.org\/10.1145\/3514499","relation":{},"ISSN":["2157-6904","2157-6912"],"issn-type":[{"type":"print","value":"2157-6904"},{"type":"electronic","value":"2157-6912"}],"subject":[],"published":{"date-parts":[[2022,6,11]]},"assertion":[{"value":"2020-11-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-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}