{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T21:16:43Z","timestamp":1760217403361,"version":"build-2065373602"},"reference-count":33,"publisher":"MDPI AG","issue":"3","license":[{"start":{"date-parts":[[2015,8,28]],"date-time":"2015-08-28T00:00:00Z","timestamp":1440720000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"US DoD Office of Naval Research","award":["N000140911174"],"award-info":[{"award-number":["N000140911174"]}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Robotics"],"abstract":"<jats:p>Multi-robot task allocation (MRTA) is an important area of research in autonomous multi-robot systems. The main problem in MRTA is to allocate a set of tasks to a set of robots so that the tasks can be completed by the robots while ensuring that a certain metric, such as the time required to complete all tasks, or the distance traveled, or the energy expended by the robots is reduced. We consider a scenario where tasks can appear dynamically and a task needs to be performed by multiple robots to be completed. We propose a new algorithm called SQ-MRTA (Spatial Queueing-MRTA) that uses a spatial queue-based model to allocate tasks between robots in a distributed manner. We have implemented the SQ-MRTA algorithm on accurately simulated models of Corobot robots within the Webots simulator for different numbers of robots and tasks and compared its performance with other state-of-the-art MRTA algorithms. Our results show that the SQ-MRTA algorithm is able to scale up with the number of tasks and robots in the environment, and it either outperforms or performs comparably with respect to other distributed MRTA algorithms.<\/jats:p>","DOI":"10.3390\/robotics4030316","type":"journal-article","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T10:55:58Z","timestamp":1441104958000},"page":"316-340","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":10,"title":["A Spatial Queuing-Based Algorithm for Multi-Robot Task Allocation"],"prefix":"10.3390","volume":"4","author":[{"given":"William","family":"Lenagh","sequence":"first","affiliation":[{"name":"Computer Science Department, University of Nebraska, Omaha, NE 68182, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prithviraj","family":"Dasgupta","sequence":"additional","affiliation":[{"name":"Computer Science Department, University of Nebraska, Omaha, NE 68182, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Angelica","family":"Munoz-Melendez","sequence":"additional","affiliation":[{"name":"Computer Science Department, Instituto Nacional de Astrofisica, Optica y Electronica, Tonantzintla, Pue. 72840 Mexico"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2015,8,28]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","unstructured":"Celik, G., and Modiano, E. (2010, January 15\u201317). Dynamic Vehicle Routing for Data Gathering in Wireless Networks. Proceedings of the 49th Conference on Decision and Control, Atlanta, GA, USA.","DOI":"10.1109\/CDC.2010.5717960"},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Gil Jones, E., Dias, M., and Stentz, A. (November, January 29). Learning-Enhanced Market-based Task Allocation for Oversubscribed Domains. Proceedings of the 2007 IEEE\/RSJ International Conference on Intelligent Robots and Systems, San Diego, CA, USA.","DOI":"10.1109\/IROS.2007.4399534"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1007\/s10514-010-9202-3","article-title":"Time-Extended Multi-Robot Coordination for Domains with Intra-Path Constraints","volume":"30","author":"Dias","year":"2011","journal-title":"Auton. Robots"},{"key":"ref_4","doi-asserted-by":"crossref","first-page":"758","DOI":"10.1109\/TRA.2002.803462","article-title":"Sold!: Auction Methods for Multirobot Coordination","volume":"18","author":"Gerkey","year":"2002","journal-title":"IEEE Trans. Robot. Autom."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lim, S., and Rus, D. (2012, January 14\u201318). Stochastic Motion Planning with Path Constraints and Application to Optimal Agent, Resource, and Route Planning. Proceedings International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6224707"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"607","DOI":"10.1109\/TASE.2009.2028577","article-title":"A Collaborative Multiagent Taxi-Dispatch System","volume":"7","author":"Seow","year":"2010","journal-title":"IEEE Trans. Autom. Sci. Eng."},{"key":"ref_7","unstructured":"Gil Jones, E., Browning, B., Dias, M., Argall, B., Veloso, M., and Stentz, A. (2006, January 15\u201319). Dynamically Formed Heterogeneous Robot Teams Performing Tightly-Coordinated Tasks. Proceedings of the International Conference on Robotics and Automation, Orlando, FL, USA."},{"key":"ref_8","first-page":"5","article-title":"Multi-Robot Task Allocation for Performing Cooperative Foraging Tasks in an Initially Unknown Environment","volume":"338","author":"Dasgupta","year":"2011","journal-title":"Innovation in Defense Support Systems-2, Studies in Computational Intelligence"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"939","DOI":"10.1177\/0278364904045564","article-title":"A Formal Analysis and Taxonomy of Task Allocation in Multi Robot Systems","volume":"23","author":"Gerkey","year":"2004","journal-title":"Int. J. Robot. Res."},{"key":"ref_10","unstructured":"Liu, L., and Shell, D. (2011). Robotics: Science and Systems VII, MIT Press."},{"key":"ref_11","first-page":"1257","article-title":"Market-based multirobot coordination: A survey and analysis","volume":"94","author":"Dias","year":"2006","journal-title":"Proc. IEEE Spec. Issue Multirobot Syst."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Bruer, L. (2003). From Markov Jump Processes to Spatial Queues, Springer.","DOI":"10.1007\/978-94-010-0239-4"},{"key":"ref_13","unstructured":"Munoz-Melendez, A., Dasgupta, P., and Lenagh, W. (2012, January 28\u201331). A stochastic queuing model for multi-robot task allocation. Proceedings of the 9th International Conference on Informatics in Control, Automation and Robotics (ICINCO), Rome, Italy."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Ahmed, S., Pongthawornkamol, T., Nahrstedt, K., Caesar, M., and Wang, G. (2009, January 18\u201321). Topology-aware optimal task allocation for publish\/subscribe-based mission critical environment. Proceedings of the IEEE Military Communications Conference (MILCOM), Boston, MA, USA.","DOI":"10.1109\/MILCOM.2009.5379968"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"1495","DOI":"10.1177\/0278364913496484","article-title":"A comprehensive taxonomy for multi-robot task allocation","volume":"32","author":"Stentz","year":"2013","journal-title":"Int. J. Robot. Res."},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1177\/0278364906061160","article-title":"Market-Based Multi-robot Coordination for Complex Tasks","volume":"25","author":"Zlot","year":"2006","journal-title":"Int. J. Robot. Res."},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Li, X., Sun, D., and Yang, J. (2009, January 19\u201323). Networked Architecture for Multi-Robot Task Reallocation in Dynamic Environment. Proceedings of the 2009 IEEE International Conference on Robotics and Biomimetics (ROBIO), Guilin, China.","DOI":"10.1109\/ROBIO.2009.5420629"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"900","DOI":"10.1016\/j.robot.2010.03.011","article-title":"Repeated auctions for robust task execution by a robot team","volume":"58","author":"Nanjanath","year":"2010","journal-title":"Robot. Auton. Syst."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"936","DOI":"10.1177\/0278364911404579","article-title":"Assessing Optimal Assignment Under Uncertainty: An Interval-Based Approach","volume":"30","author":"Liu","year":"2011","journal-title":"Int. J. Robot. Res."},{"key":"ref_20","unstructured":"Liu, L., and Shell, D. (2010, January 14\u201318). Tunable Routing Solutions for Multi-Robot Navigation via the Assignment Problem: A 3D Representation of the Matching Graph. Proceedings of the International Conference on Robotics and Automation, Saint Paul, MN, USA."},{"key":"ref_21","unstructured":"Liu, L., and Shell, D. (2012). Robotics: Science and Aystems VIII, MIT Press."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Sucan, I., and Kavraki, L. (2012, January 14\u201318). Accounting for Uncertainty in Simultaneous Task and Motion Planning Using Task Motion Multigraphs. Proceedings of the International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6224885"},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Pavone, M., Smith, S., Bullo, F., and Frazzoli, E. (2009, January 10-12). Dynamic Multi-Vehicle Routing with Multiple Classes of Demands. Proceedings of the American Control Conference, St. Louis, MO, USA.","DOI":"10.1109\/ACC.2009.5160557"},{"key":"ref_24","doi-asserted-by":"crossref","unstructured":"Zhang, K., Collins, E., and Barbu, A. (2012, January 14\u201318). An Efficient Stochastic Clustering Auction for Heterogeneous Robot Teams. Proceedings of the International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6224588"},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Luo, L., Chakraborty, N., and Sycara, K. (2012, January 14\u201318). Competitive Analysis of Repeated Greedy Auction Algorithm for Online Multi-Robot Task Assignment. Proceedings of the International Conference on Robotics and Automation, Saint Paul, MN, USA.","DOI":"10.1109\/ICRA.2012.6225195"},{"key":"ref_26","unstructured":"Braitenberg, V. (1984). Vehicles: Experiments in synthetic psychology, MIT Press."},{"key":"ref_27","unstructured":"Woosley, B., and Dasgupta, P. (2013, January 22\u201324). Multi-robot Task Allocation with Real-Time Path Planning. Proceedings of the Twenty-Sixth International Florida Artificial Intelligence Research Society Conference (FLAIRS-26 Conference), St. Pete Beach, FL, USA."},{"key":"ref_28","unstructured":"Murphy, R. (2000). Introduction to AI Robotics, The MIT Press."},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1002\/nav.3800020109","article-title":"The Hungarian Method for the Assignment Problem","volume":"2","author":"Kuhn","year":"1955","journal-title":"Naval Res. Logist. Q."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1104","DOI":"10.1109\/TC.1980.1675516","article-title":"The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver","volume":"C-29","author":"Smith","year":"1980","journal-title":"IEEE Trans. Comput."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Van Mieghem, P. (2014). Performance Analysis of Complex Networks and Systems, Cambridge University Press.","DOI":"10.1017\/CBO9781107415874"},{"key":"ref_32","unstructured":"Nisan, N., and Segal, I. Exponential communication inefficiency of demand queries. Proceedings of the 10th Conference on Theoretical Aspects of Rationality and Knowledge (TARK \u201905\"), Singapore."},{"key":"ref_33","doi-asserted-by":"crossref","first-page":"1372","DOI":"10.1137\/050641181","article-title":"On the computational power of demand queries","volume":"39","author":"Blumosen","year":"2015","journal-title":"SIAM J. Compt."}],"container-title":["Robotics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2218-6581\/4\/3\/316\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T20:47:41Z","timestamp":1760215661000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2218-6581\/4\/3\/316"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,8,28]]},"references-count":33,"journal-issue":{"issue":"3","published-online":{"date-parts":[[2015,9]]}},"alternative-id":["robotics4030316"],"URL":"https:\/\/doi.org\/10.3390\/robotics4030316","relation":{},"ISSN":["2218-6581"],"issn-type":[{"type":"electronic","value":"2218-6581"}],"subject":[],"published":{"date-parts":[[2015,8,28]]}}}