The DOI matches its Crossref record; 16 of the 18 references it cites were found in a registry or an index.
Deadlock-Free Method for Multi-Agent Pickup and Delivery Problem Using Priority Inheritance with Temporary Priority
Open accessAbstract
This paper proposes a control method for the multi-agent pickup and delivery problem (MAPD problem) by extending the priority inheritance with backtracking (PIBT) method to make it applicable to more general environments. PIBT is an effective algorithm that introduces a priority to each agent, and at each timestep, the agents, in descending order of priority, decide their next neighboring locations in the next timestep through communications only with the local agents. Unfortunately, PIBT is only applicable to environments that are modeled as a bi-connected area, and if it contains dead-ends, such as tree-shaped paths, PIBT may cause deadlocks. However, in the real-world environment, there are many dead-end paths to locations such as the shelves where materials are stored as well as loading/unloading locations to transportation trucks. Our proposed method enables MAPD tasks to be performed in environments with some tree-shaped paths without deadlock while preserving the PIBT feature; it does this by allowing the agents to have temporary priorities and restricting agents’ movements in the trees. First, we demonstrate that agents can always reach their delivery location without deadlock. Our experiments indicate that the proposed method is very efficient, even in environments where PIBT is not applicable, by comparing them with those obtained using the well-known token passing method as a baseline.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Comprehensive end-to-end workflow orchestration”
From The Rise of Agentic AI: A Review of Definitions, Frameworks, Architectures, Applications, Evaluation Metrics, and Challenges (2025) · cites this paper as [69]
In the citing paper
“Multiagent pickup and delivery systems address the coordination task, collision avoidance tasks, and other delay reduction tasks [69].”
From The Rise of Agentic AI: A Review of Definitions, Frameworks, Architectures, Applications, Evaluation Metrics, and Challenges (2025) · cites this paper as [69]
In the citing paper
“Exact coordinates of the agent help to plan a path that is entirely collision-free with respect to any agents involved [69].”
From The Rise of Agentic AI: A Review of Definitions, Frameworks, Architectures, Applications, Evaluation Metrics, and Challenges (2025) · cites this paper as [69]
Citations
Cites
A Multiagent Approach to Autonomous Intersection Management
Dresner, K., & Stone, P. (2008) · Journal of Artificial Intelligence Research · doi:10.1613/jair.2502 · Cited by 1,372
Conflict-based search for optimal multi-agent pathfinding
Sharon, G., Stern, R., Felner, A., & Sturtevant, N. (2014) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.006 · Cited by 1,268
Silver, D. (2005) · Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment · doi:10.1609/aiide.v1i1.18726 · Cited by 740
Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks
Stern, R., Sturtevant, N., Felner, A., Koenig, S., Ma, H., Walker, T. T., Li, J., Atzmon, D., Cohen, L., Kumar, T. K. S., et al. (2021) · Proceedings of the International Symposium on Combinatorial Search · doi:10.1609/socs.v10i1.18510 · Cited by 691
Coordinating hundreds of cooperative, autonomous vehicles in warehouses
Wurman, P. R., & Mountz, M. (2008) · Cited by 566
Finding 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 370
Subdimensional expansion for multirobot path planning
Wagner, G., & Choset, H. (2014) · Artificial Intelligence · doi:10.1016/j.artint.2014.11.001 · Cited by 365
Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems
Chung, J. J., Miklić, D., Sabattini, L., Tumer, K., & Siegwart, R. (2019) · Adaptive Agents and Multi-Agents Systems · Cited by 330
Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks
Ma, H., Li, J., Kumar, T. K. S., & Koenig, S. (2017) · Adaptive Agents and Multi-Agents Systems · doi:10.5555/3091125.3091243 · Cited by 196
Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems
Larson, K. S., Winikoff, M., Das, S., & Durfee, E. H. (2017) · Cited by 195
Cited by
Sorted by citations
Bandi, A., Kongari, B., Naguru, R., Pasnoor, S., & Vilipala, S. V. (2025) · Future Internet · doi:10.3390/fi17090404 · Cited by 207
Multi-Agent Pickup and Delivery with external agents
Bonalumi, L., Flammini, B., Azzalini, D., & Francesco Amigoni, A. (2025) · Robotics and Autonomous Systems · doi:10.1016/j.robot.2025.105000 · Cited by 4
Fujisawa, Y., Shimada, D., Miyashita, Y., & Sugawara, T. (2024) · IEEE/WIC/ACM International Conference on Web Intelligence and Intelligent Agent Technology (WI-IAT) · doi:10.1109/wi-iat62293.2024.00042 · Cited by 4
Self-citationMulti-robot navigation in social mini-games: definitions, taxonomy, and algorithms
Chandra, R., Singh, S. K., Luo, W., & Sycara, K. P. (2026) · Autonomous Robots · doi:10.1007/s10514-026-10251-w · Cited by 2
Greedy Priority Inheritance With Backtracking for Multi-Agent Pathfinding Problem
Tang, M., Li, Y., Gan, L., Zhang, C., Sun, Y., & Wu, J. (2026) · IEEE Transactions on Automation Science and Engineering · doi:10.1109/tase.2026.3703194
Metadata
- Authors
- Fujitani, Y., Yamauchi, T., Miyashita, Y., & Sugawara, T.
- Affiliations
- Waseda University (JP)
- Corresponding author
- Fujitani, Yukita
- Venue
- Procedia Computer Science
- Publisher
- Elsevier BV
- Published
- 2022
- Volume
- 207
- Pages
- 1552-1561
- ISSN
- 1877-0509 (ISSN-L)
- OpenAlex
- W4312590108
- Cited by
- 9
- References
- 18
- Citations by year
- 2026: 6 · 2025: 2 · 2024: 1
- FWCI
- 0.27
- Type
- conference paper
- Language
- en
- Open access
- diamond
- doi.org
- Licence
- Locations
- Procedia Computer Science (publishedVersion, cc-by-nc-nd)
- arXiv (Cornell University) (submittedVersion)
- arXiv (Cornell University)
- Funders
- Japan Society for the Promotion of Science (20H04245)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Robotic Path Planning Algorithms
- Physical Sciences › Engineering › Industrial and Manufacturing Engineering › Advanced Manufacturing and Logistics Optimization
- Physical Sciences › Computer Science › Artificial Intelligence › Multi-Agent Systems and Negotiation
- Keywords
- deadlock avoidance, multi-agent coordination, token passing, local communication
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
