{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,2]],"date-time":"2026-05-02T10:04:47Z","timestamp":1777716287566,"version":"3.51.4"},"reference-count":33,"publisher":"SAGE Publications","issue":"12","license":[{"start":{"date-parts":[[2013,9,18]],"date-time":"2013-09-18T00:00:00Z","timestamp":1379462400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/journals.sagepub.com\/page\/policies\/text-and-data-mining-license"}],"content-domain":{"domain":["journals.sagepub.com"],"crossmark-restriction":true},"short-container-title":["The International Journal of Robotics Research"],"published-print":{"date-parts":[[2013,10]]},"abstract":"<jats:p>Many multi-robot scenarios involve navigation of a set of networked robots through a constrained environment to achieve coverage, maintain a predefined shape, sense at predefined locations, or to satisfy some other distance-defined property. When new robots and tasks are added to a network of already deployed interchangeable robots, a trade-off arises in seeking to minimize cost to execute the tasks and the level of disruption to the system. This paper examines a navigation-oriented variant of this problem in which robots are physically routed through an existing network. We propose a parametrizable method to tune emphasis between minimizing global travel cost (or energy, or distance), minimizing interruption (i.e. obtaining the fewest number of robot reassignments), reducing travel distance per robot, and completing all operations as soon as possible. Since these are related optimization criteria, a single parameter provides sufficient flexibility to balance between them.<\/jats:p>\n                  <jats:p>Paths through the network are computed via a task-allocation formulation in which destination locations of newly deployed robots are added as tasks to an existing allocation. We adapt the graph matching variant of the Hungarian Algorithm\u2014originally designed to solve the optimal assignment problem in complete bipartite graphs\u2014to construct routing paths in sparse networks. We do this by constructing a three-dimensional graph that incorporates logical aspects of the Hungarian bipartite graph, and spatial elements of the Euclidean graph. The approach has several useful features including being particularly effective at generating multiple simultaneous, non-interfering paths. When new agent\u2013task pairs are inserted, the assignment is globally reallocated in an incremental fashion so that it requires only linear time when the robots\u2019 traversal options have bounded degree. The algorithm is studied systematically in simulation and also validated with physical robots.<\/jats:p>","DOI":"10.1177\/0278364913498788","type":"journal-article","created":{"date-parts":[[2013,9,19]],"date-time":"2013-09-19T03:52:09Z","timestamp":1379562729000},"page":"1475-1494","update-policy":"https:\/\/doi.org\/10.1177\/sage-journals-update-policy","source":"Crossref","is-referenced-by-count":8,"title":["Physically routing robots in a multi-robot network: Flexibility through a three-dimensional matching graph"],"prefix":"10.1177","volume":"32","author":[{"given":"Lantao","family":"Liu","sequence":"first","affiliation":[{"name":"Department of Computer Science & Engineering, Texas A&M University"}]},{"given":"Dylan A","family":"Shell","sequence":"additional","affiliation":[{"name":"Department of Computer Science & Engineering, Texas A&M University"}]}],"member":"179","published-online":{"date-parts":[[2013,9,18]]},"reference":[{"issue":"2","key":"bibr1-0278364913498788","first-page":"1","volume":"4","author":"Agmon N","year":"2010","journal-title":"Journal of Physical Agents"},{"key":"bibr2-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2011.5980269"},{"key":"bibr3-0278364913498788","doi-asserted-by":"publisher","DOI":"10.3182\/20120914-2-US-4030.00029"},{"key":"bibr4-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1287\/inte.20.4.133"},{"key":"bibr5-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1137\/0801026"},{"key":"bibr6-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898717754"},{"key":"bibr7-0278364913498788","volume-title":"Graph Theory. Graduate Texts in Mathematics","volume":"173","author":"Diestel R","year":"2005"},{"key":"bibr8-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/AERO.2006.1655803"},{"key":"bibr9-0278364913498788","first-page":"3","author":"Elmaliach Y","year":"2009","journal-title":"Annals of Math and Artificial Intelligence"},{"key":"bibr10-0278364913498788","first-page":"713","author":"Fox D","year":"2001","journal-title":"Advances in neural information processing systems (NIPS-14)"},{"key":"bibr11-0278364913498788","volume-title":"Proceedings of the international conference on advanced robotics","author":"Gerkey B","year":"2003"},{"key":"bibr12-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1177\/0278364904045564"},{"key":"bibr13-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-13022-9_72"},{"key":"bibr14-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1023\/A:1019625207705"},{"key":"bibr15-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/SASO.2007.41"},{"key":"bibr16-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"bibr17-0278364913498788","volume-title":"Combinatorial Optimization: Networks and Matroids","author":"Lawler E","year":"2001"},{"key":"bibr18-0278364913498788","first-page":"2886","volume-title":"Proceedings of IEEE international conference on robotics and automation","author":"Liu L","year":"2011"},{"key":"bibr19-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1177\/0278364911404579"},{"key":"bibr20-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1007\/s10514-012-9303-2"},{"key":"bibr21-0278364913498788","volume-title":"International symposium on distributed autonomous robotic systems","author":"Liu L","year":"2012"},{"key":"bibr22-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/ICRA.2012.6224704"},{"key":"bibr23-0278364913498788","volume-title":"Matching Theory","author":"Lov\u00e1sz L","year":"1986"},{"key":"bibr24-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.2008.4543197"},{"key":"bibr25-0278364913498788","unstructured":"Mills-Tettey GA, Stentz A, Dias MB (2007) The dynamic Hungarian algorithm for the assignment problem with changing costs. Technical Report CMU-RI-TR-07-27, Carnegie Mellon University."},{"issue":"1","key":"bibr26-0278364913498788","first-page":"32","volume":"5","author":"Munkres J","year":"1957","journal-title":"Journal of the SIAM"},{"key":"bibr27-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2007.4399631"},{"key":"bibr28-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1016\/j.robot.2007.08.005"},{"key":"bibr29-0278364913498788","first-page":"1019","volume-title":"IEEE international conference on robotics and automation","author":"Shen WM","year":"2002"},{"key":"bibr30-0278364913498788","first-page":"192","volume-title":"International conference on automation, robotics and control systems","author":"Topal S","year":"2009"},{"key":"bibr31-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2006.05.004"},{"key":"bibr32-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/ROBOT.1998.677362"},{"key":"bibr33-0278364913498788","doi-asserted-by":"publisher","DOI":"10.1109\/IROS.2008.4650734"}],"container-title":["The International Journal of Robotics Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364913498788","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/journals.sagepub.com\/doi\/pdf\/10.1177\/0278364913498788","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T10:17:55Z","timestamp":1777457875000},"score":1,"resource":{"primary":{"URL":"https:\/\/journals.sagepub.com\/doi\/10.1177\/0278364913498788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,9,18]]},"references-count":33,"journal-issue":{"issue":"12","published-print":{"date-parts":[[2013,10]]}},"alternative-id":["10.1177\/0278364913498788"],"URL":"https:\/\/doi.org\/10.1177\/0278364913498788","relation":{},"ISSN":["0278-3649","1741-3176"],"issn-type":[{"value":"0278-3649","type":"print"},{"value":"1741-3176","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9,18]]}}}