{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,16]],"date-time":"2026-07-16T14:12:07Z","timestamp":1784211127080,"version":"3.55.0"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T00:00:00Z","timestamp":1660348800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T00:00:00Z","timestamp":1660348800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-19-1-7032"],"award-info":[{"award-number":["FA9550-19-1-7032"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Swarm Intell"],"published-print":{"date-parts":[[2022,9]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>This paper addresses in-schedule dependent task allocation problems for multi-robot systems. One of the main issues with those problems is the inherent NP-hardness of combinatorial optimisation. To handle this issue, this paper develops a decentralised task allocation algorithm by leveraging the submodularity concept and a sampling process of task sets. Our theoretical analysis reveals that the proposed algorithm can provide an approximation guarantee of 1\/2 of the optimal solution for the monotone submodular case and 1\/4 for the non-monotone submodular case, both with polynomial time complexity. To examine the performance of the proposed algorithm and validate the theoretical analysis, we introduce two task allocation scenarios and perform numerical simulations. The simulation results confirm that the proposed algorithm achieves a solution quality which is comparable to state-of-the-art algorithms in the monotone case and much better quality in the non-monotone case with significantly lower computational complexity.<\/jats:p>","DOI":"10.1007\/s11721-022-00213-0","type":"journal-article","created":{"date-parts":[[2022,8,13]],"date-time":"2022-08-13T03:20:53Z","timestamp":1660360853000},"page":"233-260","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Sample greedy based task allocation for multiple robot systems"],"prefix":"10.1007","volume":"16","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9938-0370","authenticated-orcid":false,"given":"Hyo-Sang","family":"Shin","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Teng","family":"Li","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hae-In","family":"Lee","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Antonios","family":"Tsourdos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,8,13]]},"reference":[{"key":"213_CR1","doi-asserted-by":"crossref","unstructured":"Badanidiyuru, A., & Vondr\u00e1k, J. (2014). Fast algorithms for maximizing submodular functions. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1497\u20131514.","DOI":"10.1137\/1.9781611973402.110"},{"key":"213_CR2","doi-asserted-by":"crossref","unstructured":"Buchbinder, N., Feldman, M., Naor, J. S., & Schwartz, R. (2014). Submodular maximization with cardinality constraints. In Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), SIAM, pp. 1433\u20131452.","DOI":"10.1137\/1.9781611973730.80"},{"issue":"4","key":"213_CR3","doi-asserted-by":"publisher","first-page":"912","DOI":"10.1109\/TRO.2009.2022423","volume":"25","author":"H-L Choi","year":"2009","unstructured":"Choi, H.-L., Brunet, L., & How, J. P. (2009). Consensus-based decentralized auctions for robust task allocation. IEEE Transactions on Robotics, 25(4), 912\u2013926.","journal-title":"IEEE Transactions on Robotics"},{"key":"213_CR4","doi-asserted-by":"crossref","unstructured":"Corah, M., & Michael, N. (2018). Distributed submodular maximization on partition matroids for planning on large sensor networks. In 2018 IEEE Conference on Decision and Control (CDC), IEEE, pp. 6792\u20136799.","DOI":"10.1109\/CDC.2018.8619396"},{"issue":"3","key":"213_CR5","doi-asserted-by":"publisher","first-page":"726","DOI":"10.1016\/j.automatica.2007.07.022","volume":"44","author":"J Cort\u00e9s","year":"2008","unstructured":"Cort\u00e9s, J. (2008). Distributed algorithms for reaching consensus on general functions. Automatica, 44(3), 726\u2013737.","journal-title":"Automatica"},{"issue":"7","key":"213_CR6","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1109\/JPROC.2006.876939","volume":"94","author":"MB Dias","year":"2006","unstructured":"Dias, M. B., Zlot, R., Kalra, N., & Stentz, A. (2006). Market-based multirobot coordination: A survey and analysis. Proceedings of the IEEE, 94(7), 1257\u20131270.","journal-title":"Proceedings of the IEEE"},{"key":"213_CR7","doi-asserted-by":"crossref","unstructured":"Ding, H., & Castan\u00f3n, D. (2017). Multi-agent discrete search with limited visibility. In 2017 IEEE 56th Annual Conference on Decision and Control (CDC), IEEE, pp. 108\u2013113.","DOI":"10.1109\/CDC.2017.8263651"},{"key":"213_CR8","unstructured":"Dolhansky, B. W., & Bilmes, J. A. Deep submodular functions: Definitions and learning, Advances in Neural Information Processing Systems 29."},{"key":"213_CR9","unstructured":"Feldman, M., Harshaw, C., & Karbasi, A. (2017). Greed is good: Near-optimal submodular maximization via greedy optimization. In Proceedings of the 2017 Conference on Learning Theory (COLT), Vol. 65, PMLR, pp. 1\u201327."},{"issue":"9","key":"213_CR10","doi-asserted-by":"publisher","first-page":"939","DOI":"10.1177\/0278364904045564","volume":"23","author":"BP Gerkey","year":"2004","unstructured":"Gerkey, B. P., & Matari\u0107, M. J. (2004). A formal analysis and taxonomy of task allocation in multi-robot systems. The International journal of robotics research, 23(9), 939\u2013954.","journal-title":"The International journal of robotics research"},{"issue":"2","key":"213_CR11","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1109\/TCSI.2015.2512721","volume":"63","author":"S Giannini","year":"2016","unstructured":"Giannini, S., Petitti, A., Di Paola, D., & Rizzo, A. (2016). Asynchronous max-consensus protocol with time delays: Convergence results and applications. IEEE Transactions on Circuits and Systems I: Regular Papers, 63(2), 256\u2013264.","journal-title":"IEEE Transactions on Circuits and Systems I: Regular Papers"},{"issue":"11","key":"213_CR12","doi-asserted-by":"publisher","first-page":"6103","DOI":"10.1109\/TSP.2012.2211593","volume":"60","author":"F Iutzeler","year":"2012","unstructured":"Iutzeler, F., Ciblat, P., & Jakubowicz, J. (2012). Analysis of max-consensus algorithms in wireless channels. IEEE Transactions on Signal Processing, 60(11), 6103\u20136107.","journal-title":"IEEE Transactions on Signal Processing"},{"issue":"12","key":"213_CR13","doi-asserted-by":"publisher","first-page":"1495","DOI":"10.1177\/0278364913496484","volume":"32","author":"GA Korsah","year":"2013","unstructured":"Korsah, G. A., Stentz, A., & Dias, M. B. (2013). A comprehensive taxonomy for multi-robot task allocation. The International Journal of Robotics Research, 32(12), 1495\u20131512.","journal-title":"The International Journal of Robotics Research"},{"issue":"4","key":"213_CR14","first-page":"3736","volume":"6","author":"JG Kotwal","year":"2015","unstructured":"Kotwal, J. G., & Dhope, T. S. (2015). Solving task allocation to the worker using genetic algorithm. International Journal of Computer Science and Information Technologies, 6(4), 3736\u20133741.","journal-title":"International Journal of Computer Science and Information Technologies"},{"key":"213_CR15","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1017\/CBO9781139177801.004","volume":"3","author":"A Krause","year":"2014","unstructured":"Krause, A., & Golovin, D. (2014). Submodular function maximization. Tractability, 3, 71\u2013104.","journal-title":"Tractability"},{"key":"213_CR16","doi-asserted-by":"crossref","unstructured":"Kumar, R. R., Varakantham, P., & Kumar, A. (2017). Decentralized planning in stochastic environments with submodular rewards. In AAAI, pp. 3021\u20133028.","DOI":"10.1609\/aaai.v31i1.10709"},{"key":"213_CR17","doi-asserted-by":"crossref","unstructured":"Li, T., Shin, H.-S., & Tsourdos, A. (2019). Efficient decentralized task allocation for uav swarms in multi-target surveillance missions. In 2019 International Conference on Unmanned Aircraft Systems (ICUAS), IEEE, pp. 61\u201368.","DOI":"10.1109\/ICUAS.2019.8798293"},{"key":"213_CR18","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1057\/jos.2010.3","volume":"4","author":"CM Macal","year":"2010","unstructured":"Macal, C. M., & North, M. J. (2010). Tutorial on agent-based modelling and simulation, Journal of. Simulation, 4, 151\u2013162.","journal-title":"Simulation"},{"key":"213_CR19","doi-asserted-by":"crossref","unstructured":"Minoux, M. (1978). Accelerated greedy algorithms for maximizing submodular set functions. In Optimization Techniques, Springer, pp. 234\u2013243.","DOI":"10.1007\/BFb0006528"},{"key":"213_CR20","unstructured":"Mirzasoleiman, B., Badanidiyuru, A., Karbasi, A. (2016). Fast constrained submodular maximization: Personalized data summarization. In Proceedings of the 33rd International Conference on Machine Learning (ICML), Vol. 48, pp. 1358\u20131367."},{"issue":"9","key":"213_CR21","doi-asserted-by":"publisher","first-page":"1520","DOI":"10.1109\/TAC.2004.834113","volume":"49","author":"R Olfati-Saber","year":"2004","unstructured":"Olfati-Saber, R., & Murray, R. M. (2004). Consensus problems in networks of agents with switching topology and time-delays. IEEE Transactions on Automatic Control, 49(9), 1520\u20131533.","journal-title":"IEEE Transactions on Automatic Control"},{"issue":"22","key":"213_CR22","doi-asserted-by":"publisher","first-page":"258","DOI":"10.1016\/j.ifacol.2015.10.340","volume":"48","author":"G Qu","year":"2015","unstructured":"Qu, G., Brown, D., & Li, N. (2015). Distributed greedy algorithm for satellite assignment problem with submodular utility function. IFAC-PapersOnLine, 48(22), 258\u2013263.","journal-title":"IFAC-PapersOnLine"},{"key":"213_CR23","doi-asserted-by":"publisher","first-page":"206","DOI":"10.1016\/j.automatica.2019.03.007","volume":"105","author":"G Qu","year":"2019","unstructured":"Qu, G., Brown, D., & Li, N. (2019). Distributed greedy algorithm for multi-agent task assignment problem with submodular utility functions. Automatica, 105, 206\u2013215.","journal-title":"Automatica"},{"key":"213_CR24","doi-asserted-by":"crossref","unstructured":"Segui-Gasco, P., Shin, H.-S., Tsourdos, A., & Segui, V. (2015). Decentralised submodular multi-robot task allocation. In 2015 IEEE\/RSJ International Conference on Intelligent Robots and Systems (IROS), IEEE, pp. 2829\u20132834.","DOI":"10.1109\/IROS.2015.7353766"},{"key":"213_CR25","doi-asserted-by":"publisher","first-page":"259","DOI":"10.1016\/j.inffus.2020.08.001","volume":"64","author":"H-S Shin","year":"2020","unstructured":"Shin, H.-S., He, S., & Tsourdos, A. (2020). Sample greedy gossip distributed kalman filter. Information Fusion, 64, 259\u2013269.","journal-title":"Information Fusion"},{"key":"213_CR26","unstructured":"Song, H. O., Lee, Y. J., Jegelka, S., & Darrell, T. (2014). Weakly-supervised discovery of visual pattern configurations. In Advances in Neural Information Processing Systems, pp. 1637\u20131645."},{"key":"213_CR27","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.automatica.2018.11.020","volume":"100","author":"X Sun","year":"2019","unstructured":"Sun, X., Cassandras, C. G., & Meng, X. (2019). Exploiting submodularity to quantify near-optimality in multi-agent coverage problems. Automatica, 100, 349\u2013359.","journal-title":"Automatica"},{"key":"213_CR28","doi-asserted-by":"crossref","unstructured":"Williams, R. K., Gasparri, A., & Ulivi, G. (2017). Decentralized matroid optimization for topology constraints in multi-robot allocation problems. In 2017 IEEE International Conference on Robotics and Automation (ICRA), IEEE, pp. 293\u2013300.","DOI":"10.1109\/ICRA.2017.7989038"}],"container-title":["Swarm Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11721-022-00213-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11721-022-00213-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11721-022-00213-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,8,24]],"date-time":"2022-08-24T14:31:11Z","timestamp":1661351471000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11721-022-00213-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,8,13]]},"references-count":28,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,9]]}},"alternative-id":["213"],"URL":"https:\/\/doi.org\/10.1007\/s11721-022-00213-0","relation":{},"ISSN":["1935-3812","1935-3820"],"issn-type":[{"value":"1935-3812","type":"print"},{"value":"1935-3820","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,8,13]]},"assertion":[{"value":"4 March 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 July 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}