Pith. sign in

REVIEW 2 major objections 2 minor 221 references

On the Hardness of Optimal Motion on Trees

T0 review · 2 major / 2 minor · reviewed 2026-06-28 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Optimal multi-agent motion on trees is NP-hard for both labeled and colored cases across all standard objectives.

desk verdict Claims to settle long-open NP-hardness for MAPF and pebble motion on trees via a new Stack Rearrangement reduction, but the reductions need close checking for objective preservation. read the letter →

arxiv 2606.06686 v1 pith:C5SNXP5C submitted 2026-06-04 cs.RO cs.DS

Tzvika Geft This is my paper · ORCID
classification cs.ROcs.DS
keywords multi-agentpathfindingpebblemotionNP-hardnesstreesstackrearrangementplanningongraphs
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that several fundamental problems in moving multiple agents on tree-shaped graphs are NP-hard. It proves this for minimizing total distance traveled, the time until the last agent arrives, and the sum of arrival times, whether agents are unique or interchangeable within colors. The work resolves an open question on the complexity of pebble motion on trees by linking it to a newly proven hard problem of rearranging stacks of items. Readers should care because trees model many hierarchical networks, and knowing these problems are hard guides the search for approximations or special cases.

What carries the argument

A polynomial-time reduction from the NP-hard Stack Rearrangement problem to the various MAPF problems on trees that maintains the objective values.

What would settle it

Discovery of a polynomial-time algorithm solving any of these MAPF problems on trees, or construction of a specific instance where the claimed reduction does not hold.

Watch

Extended reading notes

Core claim

We prove that Multi-Agent Path Finding on trees is NP-hard for labeled agents and for agents with two colors, under the objectives of sum-of-costs, makespan, and flowtime. This includes the pebble motion problem with one move at a time. The proof proceeds by establishing NP-hardness for Stack Rearrangement and reducing it to the motion problems, with the hardness holding already on subdivided stars.

Load-bearing premise

The reductions from Stack Rearrangement to the MAPF variants on trees preserve both feasibility and the exact objective values.

Editorial extensions

If this is right

  • Stack Rearrangement is NP-hard.
  • Classical Pebble Motion on trees is NP-hard.
  • Two-colored Pebble Motion is NP-hard on any graph class.
  • Hardness holds for MAPF on subdivided stars under all three objectives.
  • These problems share a common tractability barrier.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Exact optimal solutions for these problems on trees will likely require exponential time in the worst case.
  • Research into parameterized algorithms or heuristics for tree-structured motion planning could be prioritized.
  • The stack rearrangement model might apply to other domains like warehouse logistics or data structure manipulations.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 2 minor

Summary. The manuscript claims to resolve the complexity of labeled and 2-colored MAPF on trees for distance, makespan, and flowtime by proving NP-hardness of Stack Rearrangement and then giving polynomial reductions from it to the MAPF variants (including one-move-at-a-time pebble motion). Hardness is asserted to hold already on subdivided stars, resolving the classical Pebble Motion problem on trees and supplying the first hardness result for colored pebble motion on any graph class with only two colors.

Significance. If the reductions are correct, the results close multiple long-open questions on basic discrete motion models, unify prior hardness results via a common stack-rearrangement barrier, and establish tightness for 2-colored pebble motion. The framework is notable for producing hardness on very simple trees.

major comments (2)
  1. [Reduction sections (likely §4–§6)] The central claims depend on the correctness of the polynomial reductions from Stack Rearrangement to labeled/colored MAPF on trees (including the pebble model) for all three objectives. The construction on subdivided stars must map feasible stack sequences to collision-free paths while preserving objective values (or an affine transformation) and enforcing color interchangeability; without an explicit verification that no extraneous moves or collisions are introduced, the transfer of NP-hardness cannot be confirmed for makespan and flowtime simultaneously.
  2. [Stack Rearrangement hardness proof (likely §3)] The NP-hardness proof for Stack Rearrangement itself is load-bearing; the reduction from a known hard problem to stacks must be checked for polynomial size and objective preservation before the downstream MAPF claims follow.
minor comments (2)
  1. [Preliminaries] Notation for the three objectives (distance, makespan, flowtime) should be introduced once with consistent symbols before the reductions are stated.
  2. [Figures illustrating reductions] Figure captions for the subdivided-star constructions should explicitly label which vertices correspond to stack positions versus routing paths.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their detailed review and for recognizing the potential impact of our results on long-standing open questions in MAPF and pebble motion. Below we respond point-by-point to the major comments. We maintain that the proofs in the manuscript are correct and self-contained, but we are prepared to expand explicit verification steps if that would strengthen the presentation.

read point-by-point responses

  1. Referee: [Reduction sections (likely §4–§6)] The central claims depend on the correctness of the polynomial reductions from Stack Rearrangement to labeled/colored MAPF on trees (including the pebble model) for all three objectives. The construction on subdivided stars must map feasible stack sequences to collision-free paths while preserving objective values (or an affine transformation) and enforcing color interchangeability; without an explicit verification that no extraneous moves or collisions are introduced, the transfer of NP-hardness cannot be confirmed for makespan and flowtime simultaneously.

    Authors: Sections 4–6 contain explicit bijections between optimal stack-rearrangement sequences and collision-free MAPF solutions on subdivided stars. Each stack operation is realized by a unique path for the corresponding agent (or color class), and the star subdivision plus the one-move-at-a-time rule prevent any bypassing or colliding moves outside the intended sequence. Objective preservation is shown via direct equality for distance and via affine transformations (with explicit constants) for makespan and flowtime; color interchangeability follows from the fact that same-color agents occupy interchangeable positions within each subdivided arm. We can add a short summary lemma that enumerates the forbidden extraneous configurations if the referee considers the current inline arguments insufficiently highlighted. revision: partial

  2. Referee: [Stack Rearrangement hardness proof (likely §3)] The NP-hardness proof for Stack Rearrangement itself is load-bearing; the reduction from a known hard problem to stacks must be checked for polynomial size and objective preservation before the downstream MAPF claims follow.

    Authors: Section 3 gives a direct polynomial-time reduction from 3-Partition. The constructed instance uses a linear number of stacks whose heights and item sizes are polynomial in the source instance; every feasible rearrangement sequence corresponds exactly to a feasible 3-Partition solution, and the total number of stack moves equals the 3-Partition objective plus a fixed additive constant independent of the instance. This establishes both NP-hardness and objective preservation for the base problem, which then transfers unchanged through the subsequent MAPF reductions. revision: no

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; hardness established via independent proof of Stack Rearrangement plus reductions

full rationale

The paper first proves NP-hardness of the new Stack Rearrangement problem, then gives explicit polynomial reductions from it to labeled/2-colored MAPF (including pebble motion) on trees for all three objectives. No load-bearing self-citation, self-definition, or fitted-input-as-prediction appears; the base hardness is established separately within the same manuscript rather than imported from prior author work. Reductions are described as preserving feasibility and objective values, but the derivation chain does not reduce any claimed result to its own inputs by construction. This matches the expected non-circular structure for a multi-problem hardness paper.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Standard complexity-theoretic paper; relies on the assumption that P does not equal NP to interpret the meaning of NP-hardness but introduces no free parameters or new entities.

assumptions (1)
  • standard math P does not equal NP
    Implicit background assumption used to conclude that NP-hard problems lack polynomial-time algorithms.

how reviews work

0 comments
Cite this review

Pith. "Pith review of On the Hardness of Optimal Motion on Trees." pith.science (2026). https://pith.science/paper/C5SNXP5C

@misc{pith2026260606686,
  author       = {Pith},
  title        = {Pith review of: On the Hardness of Optimal Motion on Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C5SNXP5C}},
  note         = {Machine review of arXiv:2606.06686}
}
read the original abstract

This paper presents a simple framework that settles the complexity of Multi-Agent Path Finding (MAPF) on trees across standard objectives--distance, makespan, and flowtime--for both labeled and colored variants. In MAPF, agents occupy the vertices of a graph and must move to target vertices without collisions while optimizing a given objective. In the labeled case, the agents are distinct and have respective targets; in the colored case, agents of the same color are interchangeable. While many MAPF variants are known to be intractable, several basic cases on trees have remained open. We prove NP-hardness on trees for both labeled and 2-colored MAPF under all three objectives. In particular, we resolve the classical Pebble Motion problem, where one pebble moves at a time to an adjacent empty vertex and the goal is to minimize the total number of moves. Despite being one of the most basic discrete motion models, its complexity on trees had remained open for several decades. Moreover, for colored Pebble Motion, we give the first hardness result on any graph class, already with two colors, which is tight. All of these results are established through the hardness of Stack Rearrangement, itself posed as an open problem, which asks to optimally rearrange items stored in stacks, and which we also prove to be NP-hard. Notably, the connection to stacks yields hardness already on very simple trees--subdivided stars--across all problems. Together, these results reveal a common tractability barrier that permeates several fundamental motion models, thereby unifying and strengthening prior hardness results.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

221 extracted references · 15 canonical work pages

  1. [1]

    AAAI Conference on Artificial Intelligence (AAAI) , year=

    Robust out-of-Order Retrieval for Grid-Based Storage at Maximum Capacity , author=. AAAI Conference on Artificial Intelligence (AAAI) , year=

  2. [2]

    Justin Kottinger and Tzvika Geft and Shaull Almagor and Oren Salzman and Morteza Lahijanian , title =

  3. [3]

    Introducing Delays in Multi Agent Path Finding , booktitle =

    Justin Kottinger and Tzvika Geft and Shaull Almagor and Oren Salzman and Morteza Lahijanian , editor =. Introducing Delays in Multi Agent Path Finding , booktitle =. 2024 , url =. doi:10.1609/SOCS.V17I1.31540 , timestamp =

    work page doi:10.1609/socs.v17i1.31540 2024

  4. [4]

    Schweller and Tim Wylie , title =

    David Caballero and Timothy Gomez and Robert T. Schweller and Tim Wylie , title =. Algorithmica , volume =

  5. [5]

    Wilson and Lydia E

    Randall H. Wilson and Lydia E. Kavraki and Tom. Two-Handed Assembly Sequencing , journal =. 1995 , timestamp =

    1995

  6. [6]

    Mikkel Abrahamsen and Tzvika Geft and Dan Halperin and Barak Ugav , title =

  7. [7]

    Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity , booktitle =

    Mikkel Abrahamsen and Tzvika Geft and Dan Halperin and Barak Ugav , editor =. Coordination of Multiple Robots along Given Paths with Bounded Junction Complexity , booktitle =. 2023 , url =. doi:10.5555/3545946.3598731 , timestamp =

    work page doi:10.5555/3545946.3598731 2023

  8. [8]

    Tzvika Geft , title =

Show all 221 references
  1. [9]

    Fine-Grained Complexity Analysis of Multi-Agent Path Finding on

    Tzvika Geft , editor =. Fine-Grained Complexity Analysis of Multi-Agent Path Finding on. Sixteenth International Symposium on Combinatorial Search,. 2023 , url =. doi:10.1609/SOCS.V16I1.27279 , timestamp =

    2023 doi

  2. [10]

    2024 , note =

    Tractability Frontiers in Multi-Robot Coordination and Geometric Reconfiguration , author=. 2024 , note =

    2024

  3. [11]

    International Workshop on the Algorithmic Foundations of Robotics (WAFR) , year =

    Tractability frontiers in multi-robot coordination and geometric reconfiguration , author=. International Workshop on the Algorithmic Foundations of Robotics (WAFR) , year =

  4. [12]

    Geft, Tzvika and Halperin, Dan and Nakar, Yonatan , journal=

  5. [13]

    Geft, Tzvika and Halperin, Dan , journal=

  6. [14]

    Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =

    Pankaj K. Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =

  7. [15]

    Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =

    Pankaj K. Agarwal and Tzvika Geft and Dan Halperin and Erin Taylor , title =. Comput. Geom. , volume =

  8. [16]

    Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , title =

    Pankaj K. Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , title =

  9. [17]

    Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , editor =

    Pankaj K. Agarwal and Boris Aronov and Tzvika Geft and Dan Halperin , editor =. On Two-Handed Planar Assembly Partitioning with Connectivity Constraints , booktitle =. 2021 , url =. doi:10.1137/1.9781611976465.105 , timestamp =

    2021 doi

  10. [18]

    Tzvika Geft and Dan Halperin , title =

  11. [19]

    Refined Hardness of Distance-Optimal Multi-Agent Path Finding , booktitle =

    Tzvika Geft and Dan Halperin , editor =. Refined Hardness of Distance-Optimal Multi-Agent Path Finding , booktitle =. 2022 , url =. doi:10.5555/3535850.3535905 , timestamp =

    2022 doi

  12. [20]

    2021 , note =

    Tzvika Geft and Dan Halperin , title =. 2021 , note =

    2021

  13. [21]

    2023 , note =

    Tzvika Geft and Noam Geller and Dan Halperin , title =. 2023 , note =

    2023

  14. [22]

    Agarwal and Mark de Berg and Benjamin Holmgren and Alex Steiger and Martijn Struijs , title =

    Pankaj K. Agarwal and Mark de Berg and Benjamin Holmgren and Alex Steiger and Martijn Struijs , title =. SoCG , series =

  15. [23]

    Kiril Solovey and Dan Halperin , title =. Int. J. Robotics Res. , volume =

  16. [24]

    and Schwartz, Jacob Theodore and Sharir, Micha , journal=

    Hopcroft, John E. and Schwartz, Jacob Theodore and Sharir, Micha , journal=. On the Complexity of Motion Planning for Multiple Independent Objects. 1984 , publisher=

    1984

  17. [25]

    Spirakis and Chee

    Paul G. Spirakis and Chee. Strong. Inf. Process. Lett. , volume =

  18. [26]

    Hearn and Erik D

    Robert A. Hearn and Erik D. Demaine , title =. Theor. Comput. Sci. , volume =

  19. [27]

    Wessel van der Heijden and Irina Kostitsyna and Lloyd E

    Thomas Brocken and G. Wessel van der Heijden and Irina Kostitsyna and Lloyd E. Lo. Multi-Robot Motion Planning of k-Colored Discs Is

  20. [28]

    Reconfigurations in Graphs and Grids , journal =

    Gruia C. Reconfigurations in Graphs and Grids , journal =

  21. [29]

    Mouawad and Naomi Nishimura , title =

    Alexandre Cooper and Stephanie Maaz and Amer E. Mouawad and Naomi Nishimura , title =

  22. [30]

    Adrian Dumitrescu and Minghui Jiang , title =. Comput. Geom. , volume =

  23. [31]

    2015 , publisher=

    Parameterized algorithms , author=. 2015 , publisher=

    2015

  24. [32]

    Bruno Courcelle , title =. Inf. Comput. , volume =

  25. [33]

    Bodlaender , title =

    Hans L. Bodlaender , title =. Theor. Comput. Sci. , volume =

  26. [34]

    SoCG , series =

    Bahareh Banyassady and Mark de Berg and Karl Bringmann and Kevin Buchin and Henning Fernau and Dan Halperin and Irina Kostitsyna and Yoshio Okamoto and Stijn Slot , title =. SoCG , series =

  27. [35]

    Matthew Turpin and Nathan Michael and Vijay Kumar , title =

  28. [36]

    International Conference on Fun with Algorithms , pages=

    Computational complexity of two-dimensional platform games , author=. International Conference on Fun with Algorithms , pages=. 2010 , organization=

    2010

  29. [37]

    Demaine and Alan Guo and Giovanni Viglietta , title =

    Greg Aloupis and Erik D. Demaine and Alan Guo and Giovanni Viglietta , title =. Theor. Comput. Sci. , volume =

  30. [38]

    Jonathan Gabor and Aaron Williams , title =

  31. [39]

    2020 , school=

    A framework for proving the computational intractability of motion planning problems , author=. 2020 , school=

    2020

  32. [40]

    Coulombe and Erik D

    Zachary Abel and Jeffrey Bosboom and Michael J. Coulombe and Erik D. Demaine and Linus Hamilton and Adam Hesterberg and Justin Kopinsky and Jayson Lynch and Mikhail Rudoy and Clemens Thielen , title =. Theor. Comput. Sci. , volume =

  33. [41]

    Wilfong , title =

    Gordon T. Wilfong , title =. Ann. Math. Artif. Intell. , volume =

  34. [42]

    Rolf H. M. Scheduling with

  35. [43]

    Pavel Surynek , title =

  36. [44]

    Demaine and S

    Erik D. Demaine and S. Coordinated Motion Planning: Reconfiguring a Swarm of Labeled Robots with Bounded Stretch , journal =

  37. [45]

    Jacopo Banfi and Nicola Basilico and Francesco Amigoni , title =

  38. [46]

    Tovey and Guni Sharon and T

    Hang Ma and Craig A. Tovey and Guni Sharon and T. K. Satish Kumar and Sven Koenig , title =

  39. [47]

    Russell Impagliazzo and Ramamohan Paturi , title =. J. Comput. Syst. Sci. , volume =

  40. [48]

    Russell Impagliazzo and Ramamohan Paturi and Francis Zane , title =. J. Comput. Syst. Sci. , volume =

  41. [49]

    Lower bounds based on the Exponential Time Hypothesis , journal =

    Daniel Lokshtanov and D. Lower bounds based on the Exponential Time Hypothesis , journal =

  42. [50]

    Kanj and Stefan Szeider , title =

    Ronald de Haan and Iyad A. Kanj and Stefan Szeider , title =. J. Artif. Intell. Res. , volume =

  43. [51]

    1982 , timestamp =

    David Lichtenstein , title =. 1982 , timestamp =

    1982

  44. [52]

    Knuth and Arvind Raghunathan , title =

    Donald E. Knuth and Arvind Raghunathan , title =. 1992 , timestamp =

    1992

  45. [53]

    Mark de Berg and Amirali Khosravi , title =

  46. [54]

    Time and Space Bounds for Planning , journal =

    Christer B. Time and Space Bounds for Planning , journal =

  47. [55]

    Machines , volume=

    Heuristics and Rescheduling in Prioritised Multi-Robot Path Planning: A Literature Review , author=. Machines , volume=. 2023 , publisher=

    2023

  48. [56]

    Kanj and Andrew Youngdahl , title =

    Eduard Eiben and Jonathan Gemmell and Iyad A. Kanj and Andrew Youngdahl , title =

  49. [57]

    Refining complexity analyses in planning by exploiting the exponential time hypothesis , journal =

    Meysam Aghighi and Christer B. Refining complexity analyses in planning by exploiting the exponential time hypothesis , journal =

  50. [58]

    CoRR , volume =

    Jingjin Yu , title =. CoRR , volume =

  51. [59]

    Workshop on the Algorithmic Foundations of Robotics,

    Jingjin Yu and Daniela Rus , title =. Workshop on the Algorithmic Foundations of Robotics,

  52. [60]

    Miller and Paul G

    Daniel Kornhauser and Gary L. Miller and Paul G. Spirakis , title =

  53. [61]

    Stefano Ardizzoni and Irene Saccani and Luca Consolini and Marco Locatelli and Bernhard Nebel , title =. J. Artif. Intell. Res. , volume =

  54. [62]

    American Journal of Mathematics , volume=

    Notes on the “15” puzzle , author=. American Journal of Mathematics , volume=. 1879 , publisher=

  55. [63]

    Journal of Combinatorial Theory, Series B , volume=

    Graph puzzles, homotopy, and the alternating group , author=. Journal of Combinatorial Theory, Series B , volume=. 1974 , publisher=

    1974

  56. [64]

    LaValle , title =

    Jingjin Yu and Steven M. LaValle , title =

  57. [65]

    Yakovlev , title =

    Zain Alabedeen Ali and Konstantin S. Yakovlev , title =

  58. [66]

    Gilad Fine and Dor Atzmon and Noa Agmon , title =

  59. [67]

    Solving simultaneous target assignment and path planning efficiently with time-independent execution , journal =

    Keisuke Okumura and Xavier D. Solving simultaneous target assignment and path planning efficiently with time-independent execution , journal =

  60. [68]

    Yakovlev , title =

    Stepan Dergachev and Konstantin S. Yakovlev , title =

  61. [69]

    Pierre Le Bodic and Edward Lam , title =

  62. [70]

    Sturtevant and Glenn Wagner and Pavel Surynek , title =

    Ariel Felner and Roni Stern and Solomon Eyal Shimony and Eli Boyarski and Meir Goldenberg and Guni Sharon and Nathan R. Sturtevant and Glenn Wagner and Pavel Surynek , title =

  63. [71]

    Sturtevant and Ariel Felner and Sven Koenig and Hang Ma and Thayne T

    Roni Stern and Nathan R. Sturtevant and Ariel Felner and Sven Koenig and Hang Ma and Thayne T. Walker and Jiaoyang Li and Dor Atzmon and Liron Cohen and T. K. Satish Kumar and Roman Bart. Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks , booktitle =

  64. [72]

    Studies in Complexity and Cryptography , series =

    Oded Goldreich , title =. Studies in Complexity and Cryptography , series =

  65. [73]

    Oded Goldreich , title =

  66. [74]

    Journal of Symbolic Computation , volume=

    The (n^2-1) -puzzle and related relocation problems , author=. Journal of Symbolic Computation , volume=. 1990 , publisher=

    1990

  67. [75]

    Demaine and Mikhail Rudoy , title =

    Erik D. Demaine and Mikhail Rudoy , title =. Theor. Comput. Sci. , volume =

  68. [76]

    Jingjin Yu , title =

  69. [77]

    SoCG , series =

    Eduard Eiben and Robert Ganian and Iyad Kanj , title =. SoCG , series =

  70. [78]

    Argyrios Deligkas and Eduard Eiben and Robert Ganian and Iyad Kanj and M. S. Ramanujan , title =

  71. [79]

    Bernhard Nebel , title =

  72. [80]

    Bernhard Nebel , title =. Artif. Intell. , volume =

  73. [81]

    Mover problems

    Adrian Dumitrescu. Mover problems. Thirty Essays in Geometric Graph Theory

  74. [82]

    Sliding Disks in the Plane , journal =

    Sergey Bereg and Adrian Dumitrescu and J. Sliding Disks in the Plane , journal =

  75. [83]

    van Kreveld and Golan Miglioli

    Dan Halperin and Marc J. van Kreveld and Golan Miglioli. Space-Aware Reconfiguration , journal =

  76. [84]

    Moving coins , journal =

    Manuel Abellanas and Sergey Bereg and Ferran Hurtado and Alfredo Garc. Moving coins , journal =

  77. [85]

    Buckley , title =

    Stephen J. Buckley , title =

  78. [86]

    Clarkson and Peter W

    Kenneth L. Clarkson and Peter W. Shor , title =. Discret. Comput. Geom. , volume =

  79. [87]

    2012 , url =

    Efi Fogel and Dan Halperin and Ron Wein , title =. 2012 , url =. doi:10.1007/978-3-642-17283-0 , isbn =

    2012 doi

  80. [88]

    Lin and Dinesh Manocha , title =

    Jur van den Berg and Jack Snoeyink and Ming C. Lin and Dinesh Manocha , title =. Robotics: Science and Systems , publisher =

  81. [89]

    Oren Salzman and Roni Stern , title =

  82. [90]

    Omri Kaduri and Eli Boyarski and Roni Stern , title =

  83. [91]

    Eric Ewing and Jingyao Ren and Dhvani Kansara and Vikraman Sathiyanarayanan and Nora Ayanian , title =

  84. [92]

    Aviv Adler and Mark de Berg and Dan Halperin and Kiril Solovey , title =

  85. [93]

    Workshop on the Algorithmic Foundations of Robotics,

    Israela Solomon and Dan Halperin , title =. Workshop on the Algorithmic Foundations of Robotics,

  86. [94]

    Robotics: Science and Systems , year =

    Kiril Solovey and Jingjin Yu and Or Zamir and Dan Halperin , title =. Robotics: Science and Systems , year =

  87. [95]

    Han and Jingjin Yu , title =

    Rupesh Chinta and Shuai D. Han and Jingjin Yu , title =

  88. [96]

    Tang and Vijay Kumar , title =

    Sarah Y. Tang and Vijay Kumar , title =

  89. [97]

    Oren Salzman and Michael Hemmer and Dan Halperin , title =

  90. [98]

    Kiril Solovey and Oren Salzman and Dan Halperin , title =. Int. J. Robotics Res. , volume =

  91. [99]

    Erdmann and Tom

    Michael A. Erdmann and Tom. On Multiple Moving Objects , journal =. 1987 , url =. doi:10.1007/BF01840371 , timestamp =

    1987 doi

  92. [100]

    van den Berg and Mark H

    Jur P. van den Berg and Mark H. Overmars , title =

  93. [101]

    David Silver , title =

  94. [102]

    Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots , journal =

    Michal C. Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots , journal =

  95. [103]

    Jonathan Morag and Yue Zhang and Daniel Koyfman and Zhe Chen and Ariel Felner and Daniel Harabor and Roni Stern , title =

  96. [104]

    Multi-Agent Pathfinding with Predefined Paths: To Wait, or Not to Wait, That Is the Question [Extended Abstract] , booktitle =

    Jir. Multi-Agent Pathfinding with Predefined Paths: To Wait, or Not to Wait, That Is the Question [Extended Abstract] , booktitle =

  97. [105]

    Wenying Wu and Subhrajit Bhattacharya and Amanda Prorok , title =

  98. [106]

    Ralf Regele and Paul Levi , title =

  99. [107]

    Proceedings, IEEE Aerospace Conference , volume=

    Applying kinodynamic randomized motion planning with a dynamic priority system to multi-robot space systems , author=. Proceedings, IEEE Aerospace Conference , volume=. 2002 , organization=

    2002

  100. [108]

    International Journal of Innovative Research in Science, Engineering and Technology , volume=

    A review: Priority based motion control of multiple robot systems , author=. International Journal of Innovative Research in Science, Engineering and Technology , volume=

  101. [109]

    Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation , booktitle =

    Kianoush Azarm and G. Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation , booktitle =

  102. [110]

    Raptis , title =

    Mehmet Ali Guney and Ioannis A. Raptis , title =. Robotics Auton. Syst. , volume =

  103. [111]

    Naval Research Logistics (NRL) , volume=

    Puzzle-based storage systems , author=. Naval Research Logistics (NRL) , volume=. 2007 , publisher=

    2007

  104. [112]

    Wurman and Raffaello D'Andrea and Mick Mountz , title =

    Peter R. Wurman and Raffaello D'Andrea and Mick Mountz , title =

  105. [113]

    Durham and T

    Jiaoyang Li and Andrew Tinka and Scott Kiesel and Joseph W. Durham and T. K. Satish Kumar and Sven Koenig , title =

  106. [114]

    arXiv preprint arXiv:2012.05893 , year=

    Flatland-RL: Multi-Agent Reinforcement Learning on Trains , author =. arXiv preprint arXiv:2012.05893 , year=

    2012

  107. [115]

    Pasareanu and Kasper S

    Robert Morris and Corina S. Pasareanu and Kasper S. Planning, Scheduling and Monitoring for Airport Surface Operations , booktitle =

  108. [116]

    Federico Pratissoli and Nicola Battilani and Cesare Fantuzzi and Lorenzo Sabattini , title =

  109. [117]

    Gleb Belov and Wenbo Du and Maria Garcia de la Banda and Daniel Harabor and Sven Koenig and Xinrui Wei , title =

  110. [118]

    Griffith and Srinivas Akella , title =

    Eric J. Griffith and Srinivas Akella , title =. Int. J. Robotics Res. , volume =

  111. [119]

    Nature , volume=

    Quantum phases of matter on a 256-atom programmable quantum simulator , author=. Nature , volume=. 2021 , publisher=

    2021

  112. [120]

    2001 , publisher=

    Quantum computation and quantum information , author=. 2001 , publisher=

    2001

  113. [121]

    Train Unit Shunting and Servicing: a Real-Life Application of Multi-Agent Path Finding , journal =

    Jesse Mulderij and Bob Huisman and Denise T. Train Unit Shunting and Servicing: a Real-Life Application of Multi-Agent Path Finding , journal =

  114. [122]

    Dor Atzmon and Amit Diei and Daniel Rave , title =

  115. [123]

    Train Route Planning as a Multi-agent Path Finding Problem , booktitle =

    Mauricio Salerno and Yolanda Escudero Mart. Train Route Planning as a Multi-agent Path Finding Problem , booktitle =

  116. [124]

    Vu and Sven Koenig , title =

    Jiaoyang Li and The Anh Hoang and Eugene Lin and Hai L. Vu and Sven Koenig , title =

  117. [125]

    Ayano Okoso and Keisuke Otaki and Tomoki Nishi , title =

  118. [126]

    Teng Guo and Jingjin Yu , title =

  119. [127]

    Kochenderfer and Marco Pavone , title =

    Shushman Choudhury and Kiril Solovey and Mykel J. Kochenderfer and Marco Pavone , title =. J. Artif. Intell. Res. , volume =

  120. [128]

    Kochenderfer and Marco Pavone , title =

    Shushman Choudhury and Kiril Solovey and Mykel J. Kochenderfer and Marco Pavone , title =. CoRR , volume =

  121. [129]

    Operations Research , volume=

    The humanitarian pickup and distribution problem , author=. Operations Research , volume=. 2019 , publisher=

    2019

  122. [130]

    Algorithm engineering , pages=

    Route planning in transportation networks , author=. Algorithm engineering , pages=. 2016 , publisher=

    2016

  123. [131]

    Transportation Research Part B: Methodological , volume=

    The data-driven time-dependent traveling salesperson problem , author=. Transportation Research Part B: Methodological , volume=. 2020 , publisher=

    2020

  124. [132]

    Proceedings of the AAAI Conference on Artificial Intelligence , volume=

    Multi-agent path finding with delay probabilities , author=. Proceedings of the AAAI Conference on Artificial Intelligence , volume=

  125. [133]

    Hanou and Mathijs Michiel de Weerdt and Jesse Mulderij , title =

    Issa K. Hanou and Mathijs Michiel de Weerdt and Jesse Mulderij , title =

  126. [134]

    Bruckstein , title =

    Dmitry Rabinovich and Michael Amir and Alfred M. Bruckstein , title =. Theor. Comput. Sci. , volume =

  127. [135]

    Ofir Gordon and Yuval Filmus and Oren Salzman , title =

  128. [136]

    Sturtevant , title =

    Guni Sharon and Roni Stern and Ariel Felner and Nathan R. Sturtevant , title =. Artif. Intell. , volume =

  129. [137]

    Ariel Felner and Jiaoyang Li and Eli Boyarski and Hang Ma and Liron Cohen and T. K. Satish Kumar and Sven Koenig , title =

  130. [138]

    Jiaoyang Li and Wheeler Ruml and Sven Koenig , title =

  131. [139]

    Max Barer and Guni Sharon and Roni Stern and Ariel Felner , title =

  132. [140]

    Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search , booktitle =

    Jiaoyang Li and Ariel Felner and Eli Boyarski and Hang Ma and Sven Koenig , editor =. Improved Heuristics for Multi-Agent Path Finding with Conflict-Based Search , booktitle =. 2019 , url =. doi:10.24963/ijcai.2019/63 , timestamp =

    2019 doi

  133. [141]

    Stuckey and Hang Ma and Sven Koenig , title =

    Jiaoyang Li and Daniel Harabor and Peter J. Stuckey and Hang Ma and Sven Koenig , title =. The Thirty-Third. 2019 , url =. doi:10.1609/aaai.v33i01.33016087 , timestamp =

    2019 doi

  134. [142]

    Jingyao Ren and Eric Ewing and T. K. Satish Kumar and Sven Koenig and Nora Ayanian , title =

  135. [143]

    Stuckey , title =

    Yue Zhang and Daniel Harabor and Pierre Le Bodic and Peter J. Stuckey , title =

  136. [144]

    Stuckey , title =

    Bojie Shen and Zhe Che and Jiaoyang Li and Muhammad Aamir Cheema and Daniel Damir Harabor and Peter J. Stuckey , title =

  137. [145]

    Bekris , title =

    Qandeel Sajid and Ryan Luna and Kostas E. Bekris , title =

  138. [146]

    Priority inheritance with backtracking for iterative multi-agent path finding , journal =

    Keisuke Okumura and Manao Machida and Xavier D. Priority inheritance with backtracking for iterative multi-agent path finding , journal =

  139. [147]

    Stuckey and Jiaoyang Li and Sven Koenig , title =

    Hang Ma and Daniel Harabor and Peter J. Stuckey and Jiaoyang Li and Sven Koenig , title =

  140. [148]

    Stuckey and Sven Koenig , title =

    Jiaoyang Li and Zhe Chen and Daniel Harabor and Peter J. Stuckey and Sven Koenig , title =

  141. [149]

    Stuckey , title =

    Edward Lam and Pierre Le Bodic and Daniel Damir Harabor and Peter J. Stuckey , title =

  142. [150]

    Stuckey , title =

    Graeme Gange and Daniel Harabor and Peter J. Stuckey , title =

  143. [151]

    Stuckey and Sven Koenig , title =

    Jiaoyang Li and Zhe Chen and Daniel Harabor and Peter J. Stuckey and Sven Koenig , title =. Thirty-Sixth. 2022 , url =. doi:10.1609/AAAI.V36I9.21266 , timestamp =

    2022 doi

  144. [152]

    Sumanth Varambally and Jiaoyang Li and Sven Koenig , title =

  145. [153]

    Hang Ma and Sven Koenig , title =

  146. [154]

    From Classical to Colored Multi-Agent Path Finding , booktitle =

    Roman Bart. From Classical to Colored Multi-Agent Path Finding , booktitle =

  147. [155]

    Kiril Solovey and Dan Halperin , title =. Int. J. Robotics Res. , volume =. 2014 , url =. doi:10.1177/0278364913506268 , timestamp =

    2014 doi

  148. [156]

    Efficient and Effective Techniques for Large-Scale Multi-Agent Path Finding , author=

  149. [157]

    Matteo Bellusci and Nicola Basilico and Francesco Amigoni , title =

  150. [158]

    Hang Ma and Jiaoyang Li and T. K. Satish Kumar and Sven Koenig , title =

  151. [159]

    Han and Jingjin Yu , title =

    Shuai D. Han and Jingjin Yu , title =

  152. [160]

    Bekris , title =

    Rui Wang and Kai Gao and Daniel Nakhimovich and Jingjin Yu and Kostas E. Bekris , title =

  153. [161]

    Kai Gao and Si Wei Feng and Baichuan Huang and Jingjin Yu , title =. Int. J. Robotics Res. , volume =

  154. [162]

    Bekris and Jingjin Yu , title =

    Kai Gao and Darren Lau and Baichuan Huang and Kostas E. Bekris and Jingjin Yu , title =

  155. [163]

    Kai Gao and Jingjin Yu , title =

  156. [164]

    Boris de Wilde and Adriaan ter Mors and Cees Witteveen , title =. J. Artif. Intell. Res. , volume =

  157. [165]

    Bekris , title =

    Ryan Luna and Kostas E. Bekris , title =

  158. [166]

    Jingjin Yu , title =. Auton. Robots , volume =

  159. [167]

    arXiv preprint arXiv:1801.10465 , year=

    Constant Factor Time Optimal Multi-Robot Routing on High-Dimensional Grids in Mostly Sub-Quadratic Time , author=. arXiv preprint arXiv:1801.10465 , year=

    arXiv

  160. [168]

    Hanlin Wang and Michael Rubenstein , title =

  161. [169]

    Ko. J. Artif. Intell. Res. , volume =

  162. [170]

    Canny and John H

    John F. Canny and John H. Reif , title =. 28th Annual Symposium on Foundations of Computer Science, Los Angeles, California, USA, 27-29 October 1987 , pages =

    1987

  163. [171]

    Kirkpatrick and Paul Liu , editor =

    David G. Kirkpatrick and Paul Liu , editor =. Characterizing minimum-length coordinated motions for two discs , booktitle =. 2016 , timestamp =

    2016

  164. [172]

    Bekris , title =

    Rahul Shome and Kiril Solovey and Andrew Dobson and Dan Halperin and Kostas E. Bekris , title =. Auton. Robots , volume =. 2020 , timestamp =

    2020

  165. [173]

    Ulmer , title =

    Mor Kaspi and Tal Raviv and Marlin W. Ulmer , title =. Networks , volume =

  166. [174]

    Reveliotis , title =

    Spyros A. Reveliotis , title =

  167. [175]

    2006 , publisher=

    Real-time management of resource allocation systems: A discrete event systems approach , author=. 2006 , publisher=

    2006

  168. [176]

    International Journal of Flexible Manufacturing Systems , volume=

    Deadlock avoidance for sequential resource allocation systems: Hard and easy cases , author=. International Journal of Flexible Manufacturing Systems , volume=. 2001 , publisher=

    2001

  169. [177]

    Reveliotis and Tom

    Spyros A. Reveliotis and Tom. Some new results on the state liveness of open guidepath-based traffic systems , booktitle =

  170. [178]

    Reveliotis and Elzbieta Roszkowska , title =

    Spyros A. Reveliotis and Elzbieta Roszkowska , title =

  171. [179]

    Reveliotis , title =

    Spyros A. Reveliotis , title =. Autom. , volume =

  172. [180]

    Diego Deplano and Mauro Franceschelli and Simon Ware and Rong Su and Alessandro Giua , title =

  173. [181]

    A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph , journal =

    Alexander Berndt and Niels van Duijkeren and Luigi Palmieri and Tam. A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph , journal =

  174. [182]

    Benedetta Flammini and Davide Azzalini and Francesco Amigoni , title =

  175. [183]

    Persistent and Robust Execution of

    Wolfgang H. Persistent and Robust Execution of

  176. [184]

    Federico Pecora and Henrik Andreasson and Masoumeh Mansouri and Vilian Petkov , title =

  177. [185]

    Kiril Solovey and Dan Halperin , title =

  178. [186]

    Omrit Filtser and Mayank Goswami and Joseph S. B. Mitchell and Valentin Polishchuk , title =

  179. [187]

    A Practical Approach to Multi-Agent Path Finding in Robotic Warehouses , author=

  180. [188]

    CoRR , volume =

    Teng Guo and Jingjin Yu , title =. CoRR , volume =

  181. [189]

    CoRR , volume =

    Jingtian Yan and Jiaoyang Li , title =. CoRR , volume =

  182. [190]

    Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances , booktitle =

    Michal C. Provably safe and deadlock-free execution of multi-robot plans under delaying disturbances , booktitle =

  183. [191]

    O'Kane and Marco Valtorta , title =

    Adem Coskun and Jason M. O'Kane and Marco Valtorta , title =

  184. [192]

    Path coordination for multiple mobile robots: a resolution-complete algorithm , journal =

    Thierry Sim. Path coordination for multiple mobile robots: a resolution-complete algorithm , journal =

  185. [193]

    IFAC Proceedings Volumes , volume=

    Coordination of multiple robots with assigned paths , author=. IFAC Proceedings Volumes , volume=. 2010 , publisher=

    2010

  186. [194]

    LaValle and Seth Hutchinson , title =

    Steven M. LaValle and Seth Hutchinson , title =

  187. [195]

    The international journal of robotics research , volume=

    Toward efficient trajectory planning: The path-velocity decomposition , author=. The international journal of robotics research , volume=. 1986 , publisher=

    1986

  188. [196]

    O'Donnell and Tom

    Patrick A. O'Donnell and Tom. Deadlock-free and collision-free coordination of two robot manipulators , booktitle =

  189. [197]

    Algorithms , volume =

    Laurent Bulteau and Mathias Weller , title =. Algorithms , volume =

  190. [198]

    Gutin and Anders Yeo , title =

    Gregory Z. Gutin and Anders Yeo , title =. The Constraint Satisfaction Problem , series =

  191. [199]

    arXiv preprint arXiv:2102.12331 , year=

    Iterative Refinement for Real-Time Multi-Robot Path Planning , author=. arXiv preprint arXiv:2102.12331 , year=

  192. [200]

    Coordinated Motion Planning Through Randomized

    Paul Liu and Jack Spalding. Coordinated Motion Planning Through Randomized

  193. [201]

    SoCG , series =

    Hyeyun Yang and Antoine Vigneron , title =. SoCG , series =

  194. [202]

    Shadoks Approach to Low-Makespan Coordinated Motion Planning , journal =

    Lo. Shadoks Approach to Low-Makespan Coordinated Motion Planning , journal =

  195. [203]

    Siddharth Gupta and Guy Sa'ar and Meirav Zehavi , title =. J. Artif. Intell. Res. , volume =

  196. [204]

    Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology , booktitle =

    Foivos Fioravantes and Dusan Knop and Jan Maty. Exact Algorithms and Lowerbounds for Multiagent Path Finding: Power of Treelike Topology , booktitle =

  197. [205]

    Computing Coordinated Motion Plans for Robot Swarms: The

    Fekete, S. Computing Coordinated Motion Plans for Robot Swarms: The. arXiv preprint arXiv:2103.15381 , year=

  198. [206]

    , journal=

    Garey, Michael R and Johnson, David S. , journal=. The rectilinear Steiner tree problem is. 1977 , publisher=

    1977

  199. [207]

    M. R. Garey and David S. Johnson , title =

  200. [208]

    Mathematics , volume=

    A Discrete-Event Mathematical Model for Resource Allocation Optimization: A Case Study of Vehicle Scheduling in a Signal-Free Intersection , author=. Mathematics , volume=. 2022 , publisher=

    2022

  201. [209]

    van Kreveld and Mark H

    Mark de Berg and Otfried Cheong and Marc J. van Kreveld and Mark H. Overmars , title =. 2008 , url =

    2008

  202. [210]

    Tovey , title =

    Craig A. Tovey , title =. Discret. Appl. Math. , volume =

  203. [211]

    On simplified

    Andreas Darmann and Janosch D. On simplified. Discret. Appl. Math. , volume =

  204. [212]

    2021 , publisher=

    Beyond the worst-case analysis of algorithms , author=. 2021 , publisher=

    2021

  205. [213]

    Incident Number 432 , url =

    McGregor, Sean , editor =. Incident Number 432 , url =. AI Incident Database , publisher =. 2022 , urldate =

    2022

  206. [214]

    Algorithmica , volume =

    Vincenzo Auletta and Angelo Monti and Mimmo Parente and Pino Persiano , title =. Algorithmica , volume =

  207. [215]

    Han and Nicholas M

    Shuai D. Han and Nicholas M. Stiffler and Kostas E. Bekris and Jingjin Yu , title =

  208. [216]

    Mario Szegedy and Jingjin Yu , title =

  209. [217]

    Mario Szegedy and Jingjin Yu , title =. Int. J. Robotics Res. , volume =

  210. [218]

    Algorithmica , volume =

    Gilad Goraly and Refael Hassin , title =. Algorithmica , volume =

  211. [219]

    Solving Multiagent Path Finding on Highly Centralized Networks , booktitle =

    Foivos Fioravantes and Dusan Knop and Jan Maty. Solving Multiagent Path Finding on Highly Centralized Networks , booktitle =

  212. [220]

    Demaine and Matias Korman and Anna Lubiw and Jayson Lynch and Zuzana Mas

    Oswin Aichholzer and Erik D. Demaine and Matias Korman and Anna Lubiw and Jayson Lynch and Zuzana Mas. Hardness of Token Swapping on Trees , booktitle =

  213. [221]

    CoRR , volume =

    Tomoki Nakamigawa and Tadashi Sakuma , title =. CoRR , volume =

Pith tools

Reviewed June 28, 2026 · model on record in the stance chip above.