The DOI matches its Crossref record; 38 of the 38 references it cites were found in a registry or an index.
A comprehensive taxonomy for multi-robot task allocation
Abstract
Task allocation is an important aspect of many multi-robot systems. The features and complexity of multi-robot task allocation (MRTA) problems are dictated by the requirements of the particular domain under consideration. These problems can range from those involving instantaneous distribution of simple, independent tasks among members of a homogenous team, to those requiring the time-extended scheduling of complex interrelated multi-step tasks for members of a heterogenous team related by several constraints. The existing widely used taxonomy for task allocation in multi-robot systems was designed for problems with independent tasks and does not deal with problems with interrelated utilities and constraints. While that taxonomy was a ground-breaking contribution to the MRTA literature, a survey of recent work in MRTA reveals that it is no longer a sufficient taxonomy, due to the increasing importance of interrelated utilities and constraints in realistic MRTA problems under consideration. Thus, in this paper, we present a new, comprehensive taxonomy, iTax, that explicitly takes into consideration the issues of interrelated utilities and constraints. Our taxonomy maps categories of MRTA problems to existing mathematical models from combinatorial optimization and operations research, and hence draws important parallels between robotics and these fields.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
The Hungarian method for the assignment problem
Kuhn, H. W. (1955) · Naval Research Logistics Quarterly · doi:10.1002/nav.3800020109 · Cited by 13,120
Proceedings of the 19th International Joint Conference on Artificial Intelligence
Pujol, J. M., Delgado, J., Ramon Sangüesa, A., & Flache, A. (2005) · International Joint Conference on Artificial Intelligence · Cited by 5,771
(2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515 · Cited by 4,008
Proceedings. 1985 IEEE International Conference on Robotics and Automation
(1985) · doi:10.1109/robot.1985 · Cited by 3,673
Branch-and-price: column generation for solving huge integer programs
Barnhart, C., Johnson, E. L., Nemhauser, G. L., Savelsbergh, M. W. P., & Vance, P. H. (1998) · Operations Research · doi:10.1287/opre.46.3.316 · Cited by 2,219
Brucker, P. (2004) · Springer eBooks · doi:10.1007/978-3-540-24804-0 · Cited by 2,064
A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems
Gerkey, B. P., & Matarić, M. J. (2004) · The International Journal of Robotics Research · doi:10.1177/0278364904045564 · Cited by 1,753
ALLIANCE: an architecture for fault tolerant multirobot cooperation
Parker, L. E. (1998) · IEEE Transactions on Robotics and Automation · doi:10.1109/70.681242 · Cited by 1,312
The multiple traveling salesman problem: an overview of formulations and solution procedures
Bektas, T. (2006) · Omega · doi:10.1016/j.omega.2004.10.004 · Cited by 1,153
Methods for task allocation via agent coalition formation
Shehory, O., & Kraus, S. (1998) · Artificial Intelligence · doi:10.1016/s0004-3702(98)00045-9 · Cited by 1,080
Sold!: auction methods for multirobot coordination
Gerkey, B. P., & Mataric, M. J. (2002) · IEEE Transactions on Robotics and Automation · doi:10.1109/tra.2002.803462 · Cited by 1,012
The dial-a-ride problem: models and algorithms
Cordeau, J., & Gilbert Laporte, A. (2007) · Annals of Operations Research · doi:10.1007/s10479-007-0170-8 · Cited by 890
An approximation algorithm for the generalized assignment problem
Shmoys, D. B., & Tardos, É. (1993) · Mathematical Programming · doi:10.1007/bf01585178 · Cited by 726
Complexity of Scheduling under Precedence Constraints
Lenstra, J. K., & Kan, A. H. G. R. (1978) · Operations Research · doi:10.1287/opre.26.1.22 · Cited by 557
Scheduling independent tasks to reduce mean finishing time
Bruno, J., Coffman, E. G., & Sethi, R. (1974) · Communications of the ACM · doi:10.1145/361011.361064 · Cited by 504
Coordination for Multi-Robot Exploration and Mapping
Simmons, R. G., Apfelbaum, D., Burgard, W., Fox, D., Moors, M., Thrun, S., & Younes, H. L. S. (2000) · Cited by 502
Balas, E., & Padberg, M. W. (1976) · SIAM Review · doi:10.1137/1018115 · Cited by 449
A Branch-and-Price Algorithm for the Generalized Assignment Problem
Savelsbergh, M. (1997) · Operations Research · doi:10.1287/opre.45.6.831 · Cited by 437
Combined vehicle routing and scheduling with temporal precedence and synchronization constraints
Bredström, D., & Rönnqvist, M. (2007) · European Journal of Operational Research · doi:10.1016/j.ejor.2007.07.033 · Cited by 399
1. An Overview of Vehicle Routing Problems
Toth, P., & Vigo, D. (2002) · Society for Industrial and Applied Mathematics eBooks · doi:10.1137/1.9780898718515.ch1 · Cited by 343
Auction-Based Multi-Robot Routing
Lagoudakis, M. G., Markakis, E., Kempe, D., Keskinocak, P., Kleywegt, A. J., Koenig, S., Tovey, C. A., Meyerson, A., & Jain, S. A. (2005) · Robotics: Science and Systems · doi:10.15607/rss.2005.i.045 · Cited by 310
Multi-robot coalition formation
Vig, L., & Adams, J. A. (2006) · IEEE Transactions on Robotics · doi:10.1109/tro.2006.878948 · Cited by 275
Proceedings of the 20th international joint conference on Artifical intelligence
Sangal, R., Mehta, H., & Bagga, R. (2007) · Cited by 223
Task allocation via coalition formation among autonomous agents
Shehory, O. M., & Kraus, S. (1995) · Cited by 220
Building Multirobot Coalitions Through Automated Task Solution Synthesis
Parker, L. E., & Tang, F. (2006) · Proceedings of the IEEE · doi:10.1109/jproc.2006.876933 · Cited by 189
Robot exploration with combinatorial auctions
Berhault, M., Huang, H., Keskinocak, P., Koenig, S., Elmaghraby, W., Griffin, P., & Kleywegt, A. (2004) · Proceedings 2003 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS 2003) (Cat. No.03CH37453) · doi:10.1109/iros.2003.1248932 · Cited by 183
Coalition formation with spatial and temporal constraints
Ramchurn, S. D., Polukarov, M., Farinelli, A., Truong, C., & Jennings, N. R. (2010) · Adaptive Agents and Multi-Agents Systems · doi:10.65109/duna4341 · Cited by 129
Colton, S., Bundy, A., & Walsh, T. (2000) · National Conference on Artificial Intelligence · Cited by 118
GRAMMPS: a generalized mission planner for multiple mobile robots in unstructured environments
Brumitt, B. L., & Stentz, A. (2002) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.1998.677360 · Cited by 115
Self-citationLima, P. U., & Custódio, L. (2005) · Springer eBooks · doi:10.1007/10992388_1 · Cited by 101
Resource-Constrained Assignment Scheduling
Mazzola, J. B., & Neebe, A. W. (1986) · Operations Research · doi:10.1287/opre.34.4.560 · Cited by 94
On multi-robot task allocation
Matarić, M. J., & Gerkey, B. P. (2003) · Cited by 86
Multi-robot routing under limited communication range
Mosteo, A. R., Montano, L., & Lagoudakis, M. G. (2008) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/robot.2008.4543419 · Cited by 61
Korsah, G. A., Balajee Kannan, A., Brett Browning, A., Stentz, A., & Dias, M. B. (2012) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2012.6225234 · Cited by 57
Self-citationA personnel assignment problem
Ramanan, P., Deogun, J. S., & Liu, C. L. (1984) · Journal of Algorithms · doi:10.1016/0196-6774(84)90043-9 · Cited by 49
Multi-robot routing with rewards and disjoint time windows
Melvin, J., Keskinocak, P., Koenig, S., Tovey, C. A., & Özkaya, B. Y. (2007) · IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros.2007.4399625 · Cited by 40
Exploring Bounded Optimal Coordination for Heterogeneous Teams with Cross-Schedule Dependencies
Korsah, G. A. (2018) · KiltHub Repository · doi:10.1184/r1/6716585 · Cited by 31
Self-citation
Cited by
Multi-robot Task Allocation: A Review of the State-of-the-Art
Khamis, A., Hussein, A., & Elmogy, A. (2015) · Studies in Computational Intelligence · doi:10.1007/978-3-319-18299-5_2 · Cited by 505
Cooperative Heterogeneous Multi-Robot Systems: A Survey
Rizk, Y., Awad, M., & Tunstel, E. W. (2020) · ACM Computing Surveys · doi:10.1145/3303848 · Cited by 449
A taxonomy for task allocation problems with temporal and ordering constraints
Nunes, E., Manner, M., Mitiche, H., & Gini, M. (2017) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2016.10.008 · Cited by 252
Robots for Elderly Care in the Home: A Landscape Analysis and Co-Design Toolkit
Bardaro, G., Antonini, A., & Motta, E. (2022) · International Journal of Social Robotics · doi:10.1007/s12369-021-00816-3 · Cited by 92
Metadata
- Authors
- Korsah, G. A., Stentz, A., & Dias, M. B.
- Venue
- The International Journal of Robotics Research
- Publisher
- SAGE Publications
- Published
- 2013-10
- Volume
- 32
- Issue
- 12
- Pages
- 1495-1512
- ISSN
- 0278-3649 (ISSN-L)
- 1741-3176
- OpenAlex
- W1972391046
- Cited by
- 652
- References
- 38
- FWCI
- 29.52
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.