{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T09:08:31Z","timestamp":1774602511265,"version":"3.50.1"},"reference-count":59,"publisher":"ASME International","issue":"9","license":[{"start":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T00:00:00Z","timestamp":1719964800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.asme.org\/publications-submissions\/publishing-information\/legal-policies"}],"funder":[{"DOI":"10.13039\/100000084","name":"Directorate for Engineering","doi-asserted-by":"publisher","award":["CMMI 2048020"],"award-info":[{"award-number":["CMMI 2048020"]}],"id":[{"id":"10.13039\/100000084","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-21-1-2530"],"award-info":[{"award-number":["N00014-21-1-2530"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["asmedigitalcollection.asme.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,9,1]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>In various applications of multi-robotics in disaster response, warehouse management, and manufacturing, tasks that are known a priori and tasks added during run time need to be assigned efficiently and without conflicts to robots in the team. This multi-robot task allocation (MRTA) process presents itself as a combinatorial optimization (CO) problem that is usually challenging to be solved in meaningful timescales using typical (mixed)integer (non)linear programming tools. Building on a growing body of work in using graph reinforcement learning to learn search heuristics for such complex CO problems, this paper presents a new graph neural network architecture called the covariant attention mechanism (CAM). CAM can not only generalize but also scale to larger problems than that encountered in training, and handle dynamic tasks. This architecture combines the concept of covariant compositional networks used here to embed the local structures in task graphs, with a context module that encodes the robots\u2019 states. The encoded information is passed onto a decoder designed using multi-head attention mechanism. When applied to a class of MRTA problems with time deadlines, robot ferry range constraints, and multi-trip settings, CAM surpasses a state-of-the-art graph learning approach based on the attention mechanism, as well as a feasible random-walk baseline across various generalizability and scalability tests. Performance of CAM is also found to be at par with a high-performing non-learning baseline called BiG-MRTA, while noting up to a 70-fold improvement in decision-making efficiency over this baseline.<\/jats:p>","DOI":"10.1115\/1.4065883","type":"journal-article","created":{"date-parts":[[2024,7,3]],"date-time":"2024-07-03T13:41:49Z","timestamp":1720014109000},"update-policy":"https:\/\/doi.org\/10.1115\/crossmarkpolicy-asme","source":"Crossref","is-referenced-by-count":5,"title":["Learning to Allocate Time-Bound and Dynamic Tasks to Multiple Robots Using Covariant Attention Neural Networks"],"prefix":"10.1115","volume":"24","author":[{"given":"Steve","family":"Paul","sequence":"first","affiliation":[{"name":"University at Buffalo Department of Mechanical and Aerospace Engineering, , Buffalo, NY 14260"}]},{"given":"Souma","family":"Chowdhury","sequence":"additional","affiliation":[{"name":"University at Buffalo Department of Mechanical and Aerospace Engineering, , Buffalo, NY 14260"}]}],"member":"33","published-online":{"date-parts":[[2024,8,6]]},"reference":[{"issue":"9","key":"2025080520021289100_CIT0001","doi-asserted-by":"publisher","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. Rob. Res."},{"issue":"1","key":"2025080520021289100_CIT0002","doi-asserted-by":"publisher","first-page":"30","DOI":"10.1186\/s12544-019-0368-2","article-title":"Last Mile Delivery by Drones: An Estimation of Viable Market Potential and Access to Citizens Across European Cities","volume":"11","author":"Aurambout","year":"2019","journal-title":"Eur. Transp. Res. Rev."},{"key":"2025080520021289100_CIT0003","doi-asserted-by":"publisher","first-page":"103905","DOI":"10.1016\/j.robot.2021.103905","article-title":"Multi-robot Task Allocation in Disaster Response: Addressing Dynamic Tasks With Deadlines and Robots With Range and Payload Constraints","volume":"147","author":"Ghassemi","year":"2022","journal-title":"Rob. Auton. Syst."},{"key":"2025080520021289100_CIT0004","first-page":"2312","article-title":"Multi-robot Task Allocation for Fire-Disaster Response Based on Reinforcement Learning","author":"Tian","year":"2009"},{"issue":"6","key":"2025080520021289100_CIT0005","doi-asserted-by":"publisher","first-page":"060803","DOI":"10.1115\/1.4062326","article-title":"Making Robotic Swarms Trustful: A Blockchain-Based Perspective","volume":"23","author":"Thakur","year":"2023","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"5","key":"2025080520021289100_CIT0006","doi-asserted-by":"publisher","first-page":"051003","DOI":"10.1115\/1.4046587","article-title":"An Extended Bayesian Optimization Approach to Decentralized Swarm Robotic Search","volume":"20","author":"Ghassemi","year":"2020","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2025080520021289100_CIT0007","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1007\/s00500-014-1274-0","article-title":"Memetic Algorithms for Optimal Task Allocation in Multi-robot Systems for Inspection Problems With Cooperative Tasks","volume":"19","author":"Liu","year":"2015","journal-title":"Soft Comput."},{"key":"2025080520021289100_CIT0008","doi-asserted-by":"crossref","DOI":"10.1109\/MRS50823.2021.9620707","article-title":"Learning Robot Swarm Tactics Over Complex Adversarial Environments","author":"Behjat","year":"2021"},{"key":"2025080520021289100_CIT0009","first-page":"492","article-title":"Decentralised Online Planning for Multi-robot Warehouse Commissioning","author":"Claes","year":"2017"},{"issue":"6","key":"2025080520021289100_CIT0010","doi-asserted-by":"publisher","first-page":"061011","DOI":"10.1115\/1.4047261","article-title":"A Generative Approach for Scheduling Multi-robot Cooperative Three-Dimensional Printing","volume":"20","author":"Poudel","year":"2020","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"4","key":"2025080520021289100_CIT0011","doi-asserted-by":"publisher","first-page":"041008","DOI":"10.1115\/1.4064409","article-title":"Probing an Easy-to-Deploy Multi-agent Manufacturing System Based on Agent Computing Node: Architecture, Implementation, and Case Study","volume":"24","author":"Wang","year":"2024","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"5","key":"2025080520021289100_CIT0012","doi-asserted-by":"publisher","first-page":"051013","DOI":"10.1115\/1.4062349","article-title":"An Adaptive Job Shop Scheduling Mechanism for Disturbances by Running Reinforcement Learning in Digital Twin Environment","volume":"23","author":"Fang","year":"2023","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"key":"2025080520021289100_CIT0013","first-page":"409","article-title":"Multi-robot Heuristic Goods Transportation","author":"Yan","year":"2012"},{"key":"2025080520021289100_CIT0014","doi-asserted-by":"crossref","DOI":"10.1109\/INDIN.2015.7281731","article-title":"Multi-agent Approach for Task Allocation and Scheduling in Cooperative Heterogeneous Multi-Robot Team: Simulation Results","author":"Maoudj","year":"2015"},{"key":"2025080520021289100_CIT0015","first-page":"638","article-title":"Graph Learning-Based Fleet Scheduling for Urban Air Mobility Under Operational Constraints, Varying Demand & Uncertainties","author":"Paul","year":"2024"},{"key":"2025080520021289100_CIT0016","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/j.robot.2016.10.008","article-title":"A Taxonomy for Task Allocation Problems With Temporal and Ordering Constraints","volume":"90","author":"Nunes","year":"2017","journal-title":"Rob. Auton. Syst."},{"issue":"2","key":"2025080520021289100_CIT0017","first-page":"171","article-title":"Optimization of Non-linear Multiple Traveling Salesman Problem Using k-Means Clustering, Shrink Wrap Algorithm and Meta-heuristics","volume":"9","author":"Nallusamy","year":"2010","journal-title":"Int. J. Nonlinear Sci."},{"key":"2025080520021289100_CIT0018","doi-asserted-by":"crossref","DOI":"10.1137\/1.9781611973594","volume-title":"Vehicle Routing: Problems, Methods, and Applications","author":"Toth","year":"2014"},{"key":"2025080520021289100_CIT0019","first-page":"31","volume-title":"Cooperative Robots and Sensor Networks","author":"Khamis","year":"2015"},{"issue":"1","key":"2025080520021289100_CIT0020","doi-asserted-by":"publisher","first-page":"80","DOI":"10.1287\/mnsc.6.1.80","article-title":"The Truck Dispatching Problem","volume":"6","author":"Dantzig","year":"1959","journal-title":"Manage. Sci."},{"issue":"3","key":"2025080520021289100_CIT0021","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1016\/j.omega.2004.10.004","article-title":"The Multiple Traveling Salesman Problem: An Overview of Formulations and Solution Procedures","volume":"34","author":"Bektas","year":"2006","journal-title":"Omega"},{"key":"2025080520021289100_CIT0022","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1016\/j.cie.2015.12.007","article-title":"The Vehicle Routing Problem: State of the Art Classification and Review","volume":"99","author":"Braekers","year":"2016","journal-title":"Comput. Ind. Eng."},{"issue":"3","key":"2025080520021289100_CIT0023","doi-asserted-by":"publisher","first-page":"756","DOI":"10.1016\/j.ejor.2009.06.034","article-title":"An Exact Algorithm for a Vehicle Routing Problem With Time Windows and Multiple Use of Vehicles","volume":"202","author":"Azi","year":"2010","journal-title":"Eur. J. Oper. Res."},{"key":"2025080520021289100_CIT0024","doi-asserted-by":"crossref","DOI":"10.1115\/DETC2018-85683","article-title":"Multi-criteria Mission Planning for a Solar-Powered Multi-robot System","author":"Wang","year":"2018"},{"key":"2025080520021289100_CIT0025","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1016\/j.robot.2016.02.003","article-title":"Task Allocation and Collision-Free Path Planning of Centralized Multi-robots System for Industrial Plant Inspection Using Heuristic Methods","volume":"80","author":"Jose","year":"2016","journal-title":"Rob. Auton. Syst."},{"key":"2025080520021289100_CIT0026","doi-asserted-by":"publisher","first-page":"105400","DOI":"10.1016\/j.cor.2021.105400","article-title":"Reinforcement Learning for Combinatorial Optimization: A Survey","volume":"134","author":"Mazyavkina","year":"2021","journal-title":"Comput. Oper. Res."},{"issue":"5","key":"2025080520021289100_CIT0027","doi-asserted-by":"publisher","first-page":"741","DOI":"10.1016\/j.trc.2009.12.006","article-title":"Complexity of the VRP and SDVRP","volume":"19","author":"Archetti","year":"2011","journal-title":"Transp. Res. Part C: Emerg. Technol."},{"key":"2025080520021289100_CIT0028","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s10288-016-0306-2","article-title":"Vehicle Routing Problems With Multiple Trips","volume":"14","author":"Cattaruzza","year":"2016","journal-title":"4or"},{"issue":"7","key":"2025080520021289100_CIT0029","doi-asserted-by":"publisher","first-page":"1257","DOI":"10.1109\/JPROC.2006.876939","article-title":"Market-Based Multirobot Coordination: A Survey and Analysis","volume":"94","author":"Dias","year":"2006","journal-title":"Proc. IEEE"},{"key":"2025080520021289100_CIT0030","first-page":"246","article-title":"Auction-Based Task Allocation for Multi-robot Teams in Dynamic Environments","author":"Schneider","year":"2015"},{"key":"2025080520021289100_CIT0031","first-page":"23","article-title":"Decentralized Hungarian-Based Approach for Fast and Scalable Task Allocation","author":"Ismail","year":"2017"},{"key":"2025080520021289100_CIT0032","first-page":"83","article-title":"Decentralized Dynamic Task Allocation in Swarm Robotic Systems for Disaster Response","author":"Ghassemi","year":"2019"},{"issue":"2","key":"2025080520021289100_CIT0033","doi-asserted-by":"publisher","first-page":"347","DOI":"10.1515\/jisys-2018-0267","article-title":"Iterated Local Search for Time-Extended Multi-robot Task Allocation With Spatio-temporal and Capacity Constraints","volume":"28","author":"Mitiche","year":"2019","journal-title":"J. Intell. Syst."},{"issue":"12","key":"2025080520021289100_CIT0034","doi-asserted-by":"publisher","first-page":"3281","DOI":"10.1016\/j.cor.2009.03.008","article-title":"Iterated Local Search for the Team Orienteering Problem With Time Windows","volume":"36","author":"Vansteenwegen","year":"2009","journal-title":"Comput. Oper. Res."},{"issue":"2","key":"2025080520021289100_CIT0035","doi-asserted-by":"publisher","first-page":"021010","DOI":"10.1115\/1.4039638","article-title":"Bio-inspired Coalition Formation Algorithms for Multirobot Systems","volume":"18","author":"Qian","year":"2018","journal-title":"ASME J. Comput. Inf. Sci. Eng."},{"issue":"1","key":"2025080520021289100_CIT0036","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s10514-021-10022-9","article-title":"Dynamic Multi-robot Task Allocation Under Uncertainty and Temporal Constraints","volume":"46","author":"Choudhury","year":"2022","journal-title":"Auton. Rob."},{"key":"2025080520021289100_CIT0037","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1007\/s10489-016-0771-5","article-title":"Dynamic Task Allocation for Multi-robot Search and Retrieval Tasks","volume":"45","author":"Wei","year":"2016","journal-title":"Appl. Intell."},{"key":"2025080520021289100_CIT0038","article-title":"Attention, Learn to Solve Routing Problems!","author":"Kool","year":"2019"},{"key":"2025080520021289100_CIT0039","first-page":"3243","article-title":"Exploratory Combinatorial Optimization With Reinforcement Learning","author":"Barrett","year":"2020"},{"key":"2025080520021289100_CIT0040","first-page":"6348","article-title":"Learning Combinatorial Optimization Algorithms Over Graphs","author":"Khalil","year":"2017"},{"key":"2025080520021289100_CIT0041","article-title":"Learning the Multiple Traveling Salesmen Problem with Permutation Invariant Pooling Networks","author":"Kaempfer","year":"2018","journal-title":"ArXiv"},{"key":"2025080520021289100_CIT0042","first-page":"539","article-title":"Combinatorial Optimization With Graph Convolutional Networks and Guided Tree Search","author":"Li","year":"2018"},{"key":"2025080520021289100_CIT0043","first-page":"22","article-title":"A Note on Learning Algorithms for Quadratic Assignment With Graph Neural Networks","volume":"1050","author":"Nowak","year":"2017","journal-title":"Stat"},{"key":"2025080520021289100_CIT0044","first-page":"8944","article-title":"Multi-robot Coverage and Exploration Using Spatial Graph Neural Networks","author":"Tolstaya","year":"2021"},{"key":"2025080520021289100_CIT0045","article-title":"Multi-agent Routing Value Iteration Network","author":"Sykora","year":"2020"},{"key":"2025080520021289100_CIT0046","article-title":"Learning Combinatorial Optimization Algorithms Over Graphs","author":"Dai","year":"2017"},{"key":"2025080520021289100_CIT0047","first-page":"8815","article-title":"Learning Scalable Policies Over Graphs for Multi-robot Task Allocation Using Capsule Attention Networks","author":"Paul","year":"2022"},{"key":"2025080520021289100_CIT0048","doi-asserted-by":"crossref","DOI":"10.1115\/DETC2022-90123","article-title":"A Scalable Graph Learning Approach to Capacitated Vehicle Routing Problem Using Capsule Networks and Attention Mechanism","author":"Paul","year":"2022"},{"key":"2025080520021289100_CIT0049","doi-asserted-by":"crossref","first-page":"260","DOI":"10.1007\/978-3-540-32274-0_17","volume-title":"Adaptive Agents and Multi-agent Systems II","author":"Strens","year":"2005"},{"issue":"3","key":"2025080520021289100_CIT0050","doi-asserted-by":"publisher","first-page":"4509","DOI":"10.1109\/LRA.2020.3002198","article-title":"Learning Scheduling Policies for Multi-robot Coordination With Graph Attention Networks","volume":"5","author":"Wang","year":"2020","journal-title":"IEEE Rob. Autom. Lett."},{"issue":"24","key":"2025080520021289100_CIT0051","doi-asserted-by":"publisher","first-page":"241745","DOI":"10.1063\/1.5024797","article-title":"Predicting Molecular Properties With Covariant Compositional Networks","volume":"148","author":"Hy","year":"2018","journal-title":"J. Chem. Phys."},{"issue":"1","key":"2025080520021289100_CIT0052","doi-asserted-by":"publisher","first-page":"4766","DOI":"10.1038\/s41467-024-49207-y","article-title":"Real-Time Outage Management in Active Distribution Networks Using Reinforcement Learning Over Graphs","volume":"15","author":"Jacob","year":"2024","journal-title":"Nat. Commun."},{"key":"2025080520021289100_CIT0053","article-title":"Attention Is All You Need","author":"Vaswani","year":"2017"},{"key":"2025080520021289100_CIT0054","first-page":"5779","article-title":"Efficient Planning of Multi-robot Collective Transport Using Graph Reinforcement Learning With Higher Order Topological Abstraction","author":"Paul","year":"2023"},{"key":"2025080520021289100_CIT0055","article-title":"Inductive Representation Learning on Large Graphs","author":"Hamilton","year":"2017"},{"key":"2025080520021289100_CIT0056","first-page":"26","article-title":"Graph Capsule Convolutional Neural Networks","volume":"1050","author":"Verma","year":"2018","journal-title":"Stat"},{"key":"2025080520021289100_CIT0057","doi-asserted-by":"publisher","author":"Paul","year":"2024","DOI":"10.5281\/zenodo.11910732"},{"key":"2025080520021289100_CIT0058","author":"Force","year":"2011"},{"issue":"2","key":"2025080520021289100_CIT0059","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1002\/net.3230100205","article-title":"An Algorithm to Solve the m\u00d7N Assignment Problem in Expected Time O (mn Log n)","volume":"10","author":"Karp","year":"1980","journal-title":"Networks"}],"container-title":["Journal of Computing and Information Science in Engineering"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/24\/9\/091005\/7360167\/jcise_24_9_091005.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article-pdf\/24\/9\/091005\/7360167\/jcise_24_9_091005.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,6]],"date-time":"2025-08-06T00:02:52Z","timestamp":1754438572000},"score":1,"resource":{"primary":{"URL":"https:\/\/asmedigitalcollection.asme.org\/computingengineering\/article\/24\/9\/091005\/1201342\/Learning-to-Allocate-Time-Bound-and-Dynamic-Tasks"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,8,6]]},"references-count":59,"journal-issue":{"issue":"9","published-print":{"date-parts":[[2024,9,1]]}},"URL":"https:\/\/doi.org\/10.1115\/1.4065883","relation":{},"ISSN":["1530-9827","1944-7078"],"issn-type":[{"value":"1530-9827","type":"print"},{"value":"1944-7078","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,8,6]]},"article-number":"091005"}}