The DOI matches its Crossref record; 42 of the 42 references it cites were found in a registry or an index.
PRIMAL: Pathfinding via Reinforcement and Imitation Multi-Agent Learning
Open accessAbstract
Multi-agent path finding (MAPF) is an essential component of many large-scale, real-world robot deployments, from aerial swarms to warehouse automation. However, despite the community's continued efforts, most state-of-the-art MAPF planners still rely on centralized planning and scale poorly past a few hundred agents. Such planning approaches are maladapted to realworld deployments, where noise and uncertainty often require paths be recomputed online, which is impossible when planning times are in seconds to minutes. We present PRIMAL, a novel framework for MAPF that combines reinforcement and imitation learning to teach fully decentralized policies, where agents reactively plan paths online in a partially observable world while exhibiting implicit coordination. This framework extends our previous work on distributed learning of collaborative policies by introducing demonstrations of an expert MAPF planner during training, as well as careful reward shaping and environment sampling. Once learned, the resulting policy can be copied onto any number of agents and naturally scales to different team sizes and world dimensions. We present results on randomized worlds with up to 1024 agents and compare success rates against state-of-the-art MAPF planners. Finally, we experimentally validate the learned policies in a hybrid simulation of a factory mockup, involving both real world and simulated robots.
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
Deep Residual Learning for Image Recognition
He, K., Zhang, X., Ren, S., & Sun, J. (2016) · 2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR) · doi:10.1109/cvpr.2016.90 · Cited by 235,474
Very Deep Convolutional Networks for Large-Scale Image Recognition
Simonyan, K., & Zisserman, A. (2014) · arXiv · doi:10.48550/arxiv.1409.1556 · Cited by 114,148
Reinforcement Learning: An Introduction
Sutton, R. S., & Barto, A. G. (1998) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.1998.712192 · Cited by 27,225
Reinforcement Learning: An Introduction
(2005) · IEEE Transactions on Neural Networks · doi:10.1109/tnn.2004.842673 · Cited by 24,496
Asynchronous Methods for Deep Reinforcement Learning
Mnih, V., Badia, A. P., Mirza, M., Graves, A., Lillicrap, T. P., Harley, T., Silver, D., & Kavukcuoglu, K. (2016) · arXiv · doi:10.48550/arxiv.1602.01783 · Cited by 7,132
LaValle, S. M. (2006) · Cambridge University Press eBooks · doi:10.1017/cbo9780511546877 · Cited by 5,211
LaValle, S. M. (2006) · Cited by 4,177
Schaul, T., Quan, J., Antonoglou, I., & Silver, D. (2015) · arXiv · doi:10.48550/arxiv.1511.05952 · Cited by 3,120
A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning
Ross, S., Gordon, G. J., & Bagnell, J. A. (2018) · Carnegie Mellon University · doi:10.1184/r1/6550949 · Cited by 1,941
Counterfactual Multi-Agent Policy Gradients
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., & Whiteson, S. (2018) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v32i1.11794 · Cited by 1,873
Reciprocal n-Body Collision Avoidance
van den Berg, J., Guy, S. J., Lin, M., & Manocha, D. (2011) · Springer Tracts in Advanced Robotics · doi:10.1007/978-3-642-19457-3_1 · Cited by 1,858
Incorporating Nesterov Momentum into Adam
Dozat, T. (2016) · Cited by 1,595
Programmable self-assembly in a thousand-robot swarm
Rubenstein, M., Cornejo, A., & Nagpal, R. (2014) · Science · doi:10.1126/science.1254295 · Cited by 1,308 · cited 1×
“Given the rapid development of affordable robots with embedded sensing and computation capabilities, manufacturing applications will soon regularly involve the deployment of thousands of robots [1], [2].”
BackgroundConflict-based search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. R. (2015) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.006 · Cited by 1,242
Learning to Communicate with Deep Multi-Agent Reinforcement Learning
Foerster, J. N., Assael, Y. M., de Freitas, N., & Whiteson, S. (2016) · arXiv · doi:10.48550/arxiv.1605.06676 · Cited by 1,217
Cooperative Multi-agent Control Using Deep Reinforcement Learning
Gupta, J. K., Egorov, M., & Kochenderfer, M. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-71682-4_5 · Cited by 874
Learning Complex Dexterous Manipulation with Deep Reinforcement Learning and Demonstrations
Rajeswaran, A., Kumar, V., Gupta, A., Vezzani, G., Schulman, J., Todorov, E., & Levine, S. (2018) · Robotics: Science and Systems XIV · doi:10.15607/rss.2018.xiv.049 · Cited by 847
Multi-agent Reinforcement Learning: An Overview
Buşoniu, L., Babuška, R., & De Schutter, B. (2010) · Studies in Computational Intelligence · doi:10.1007/978-3-642-14435-6_7 · Cited by 741
Erdmann, M., & Lozano-Pérez, T. (1987) · Algorithmica · doi:10.1007/bf01840371 · Cited by 736
Overcoming Exploration in Reinforcement Learning with Demonstrations
Nair, A., McGrew, B., Andrychowicz, M., Zaremba, W., & Abbeel, P. (2018) · 2018 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2018.8463162 · Cited by 712
Decentralized non-communicating multiagent collision avoidance with deep reinforcement learning
Chen, Y. F., Liu, M., Everett, M., & How, J. P. (2017) · 2017 IEEE International Conference on Robotics and Automation (ICRA) · doi:10.1109/icra.2017.7989037 · Cited by 645
Leveraging Demonstrations for Deep Reinforcement Learning on Robotics Problems with Sparse Rewards
Vecerik, M., Hester, T., Scholz, J., Wang, F., Pietquin, O., Piot, B., Heess, N., Rothörl, T., Lampe, T., & Riedmiller, M. (2017) · arXiv · doi:10.48550/arxiv.1707.08817 · Cited by 478
Counterfactual Multi-Agent Policy Gradients
Foerster, J., Farquhar, G., Afouras, T., Nardelli, N., & Whiteson, S. (2017) · arXiv (Cornell University) · doi:10.48550/arxiv.1705.08926 · Cited by 401
Subdimensional expansion for multirobot path planning
Wagner, G., & Choset, H. (2015) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.001 · Cited by 369
Self-citationFinding Optimal Solutions to Cooperative Pathfinding Problems
Standley, T. (2010) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v24i1.7564 · Cited by 358
Howard, A., Parker, L. E., & Sukhatme, G. S. (2006) · The International Journal of Robotics Research · doi:10.1177/0278364906065378 · Cited by 281
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem
Barer, M., Sharon, G., Stern, R., & Felner, A. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v5i1.18315 · Cited by 274
Reinforcement Learning from Imperfect DemonstrationsPreprint
Gao, Y., Xu, H., Lin, J., Yu, F., Levine, S., & Darrell, T. (2018) · arXiv (Cornell University) · doi:10.48550/arxiv.1802.05313 · Cited by 222
Erdmann, M., & Lozano-Perez, T. (1986) · Proceedings. 1986 IEEE International Conference on Robotics and Automation · doi:10.1109/robot.1986.1087401 · Cited by 208
Bridges: a uniquely flexible HPC resource for new communities and data analytics
Nystrom, N. A., Levine, M. J., Roskies, R. Z., & Scott, J. R. (2015) · Proceedings of the 2015 XSEDE Conference on Scientific Advancements Enabled by Enhanced Cyberinfrastructure - XSEDE '15 · doi:10.1145/2792745.2792775 · Cited by 195
Using a PRM planner to compare centralized and decoupled planning for multi-robot systems
Sanchez, G., & Latombe, J.-C. (2003) · Proceedings 2002 IEEE International Conference on Robotics and Automation (Cat. No.02CH37292) · doi:10.1109/robot.2002.1014852 · Cited by 189
Confidence-based policy learning from demonstration using Gaussian mixture models
Chernova, S., & Veloso, M. (2007) · Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems · doi:10.1145/1329125.1329407 · Cited by 162
MAPP: a Scalable Multi-Agent Path Planning Algorithm with Tractability and Completeness Guarantees
Wang, K.-H. C., & Botea, A. (2014) · arXiv (Cornell University) · doi:10.48550/arxiv.1401.3905 · Cited by 162
Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem
Max, B., Guni, S., Roni, S., & Ariel, F. (2014) · Frontiers in Artificial Intelligence and Applications · doi:10.3233/978-1-61499-419-0-961 · Cited by 162
A Framework for Coordinated Surface Operations Planning at Dallas-Fort Worth International Airport
Balakrishnan, H., & Jung, Y. (2007) · AIAA Guidance, Navigation, and Control Conference and Exhibit · doi:10.2514/6.2007-6553 · Cited by 138
Conflict-Based Search For Optimal Multi-Agent Path Finding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2021) · Proceedings of the AAAI Conference on Artificial Intelligence · doi:10.1609/aaai.v26i1.8140 · Cited by 93
ODrM* optimal multirobot path planning in low dimensional search spaces
Ferner, C., Wagner, G., & Choset, H. (2013) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2013.6631119 · Cited by 93
Self-citationDistributed Reinforcement Learning for Multi-robot Decentralized Collective Construction
Sartoretti, G., Wu, Y., Paivine, W., Kumar, T. K. S., Koenig, S., & Choset, H. (2019) · Springer proceedings in advanced robotics · doi:10.1007/978-3-030-05816-6_3 · Cited by 91
Self-citationConflict-Based Search for Optimal Multi-Agent Path Finding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v3i1.18222 · Cited by 74
Pareto-optimal coordination of multiple robots with safety guarantees
Cui, R., Gao, B., & Ji, G. L. (2011) · Autonomous Robots · doi:10.1007/s10514-011-9265-9 · Cited by 66
Distributed Learning for the Decentralized Control of Articulated Mobile Robots
Sartoretti, G., Shi, Y., Paivine, W., Travers, M. J., & Choset, H. (2018) · Proceedings - IEEE International Conference on Robotics and Automation/Proceedings · doi:10.1109/icra.2018.8460802 · Cited by 14
Self-citationHeuristic Planning for Decentralized MDPs with Sparse Interactions
Melo, F. S., & Veloso, M. (2012) · Springer tracts in advanced robotics · doi:10.1007/978-3-642-32723-0_24 · Cited by 7
Research works printed but not linked: 6
- 10.1109/CSSE.2008.920 · doi:10.1109/csse.2008.920
- leroy, 0, Multiple path coordination for mobile robots: A geometric algorithm, Proc 16th Int Joint Conf Artif Intell, 1118
- ma, 0, Multi-agent path finding with payload transfers and the package-exchange robot-routing problem, Proc AAAI Conf Artif Intell, 3166
- cáp, 0, Asynchronous decentralized prioritized planning for coordination in multi-robot system, Proc IEEE/RSJ Int Conf Intell Robots Syst, 3822
- 10.1007/978-3-540-73424-6_2 · doi:10.1007/978-3-540-73424-6_2
- lowe, 0, Multi-agent actor-critic for mixed cooperative-competitive environments, Proc 31st Conf Neural Inf Process Syst, 6382
Cited by
Quo vadis artificial intelligence?
Jiang, Y., Li, X., Luo, H., Yin, S., & Kaynak, O. (2022) · Discover Artificial Intelligence · doi:10.1007/s44163-022-00022-8 · Cited by 544
Deep reinforcement learning based mobile robot navigation: A review
Zhu, K., & Zhang, T. (2021) · Tsinghua Science and Technology · doi:10.26599/tst.2021.9010012 · Cited by 499
A review of cooperative multi-agent deep reinforcement learning
Oroojlooy, A., & Hajinezhad, D. (2023) · Applied Intelligence · doi:10.1007/s10489-022-04105-y · Cited by 482
Mobile Robot Path Planning in Dynamic Environments Through Globally Guided Reinforcement Learning
Wang, B., Liu, Z., Li, Q., & Prorok, A. (2020) · IEEE Robotics and Automation Letters · doi:10.1109/lra.2020.3026638 · Cited by 372
Graph Neural Networks for Decentralized Multi-Robot Path Planning
Li, Q., Gama, F., Ribeiro, A., & Prorok, A. (2020) · 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) · doi:10.1109/iros45743.2020.9341668 · Cited by 271
Metadata
- Authors
- Sartoretti, G., Kerr, J., Shi, Y., Wagner, G., Kumar, T. K. S., Koenig, S., & Choset, H.
- Venue
- IEEE Robotics and Automation Letters
- Published
- 2019-07
- Volume
- 4
- Issue
- 3
- Pages
- 2378-2385
- ISSN
- 2377-3766 (ISSN-L)
- 2377-3774
- OpenAlex
- W2892258706
- Cited by
- 417
- References
- 42
- FWCI
- 13.63
- Type
- journal article
- Language
- en
- Open access
- green
- Licence
- Funders
- National Science Foundation (ACI-1445606, 1409987, 1724392, 1817189, 1837779)
- CMU Manufacturing Futures Initiative
- Richard King Mellon Foundation
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.