Coordinating Pebble Motion on Graphs, the Diameter of Permutation Groups, and Applications

By D. Kornhauser, Gary L. Miller, Paul (Pavlos) Spirakis. IEEE Annual Symposium on Foundations of Computer Science, 2015

344 citations recorded by the source corpus.

We have obtaincd some results in pebble coordination problems and the diameter of permutation groups.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/09fc6c0b0e8b5f9577eec260feff1e9f98ba358f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

In Discrete Mathematics and Combinatorics

In Geometry and Topology

Citations in the corpus

Suboptimal Variants of the Conflict-Based Search Algorithm for the Multi-Agent Pathfinding Problem (2014, background): “Early work presented a theoretical polynomial-time al-gorithm for ﬁnding valid solutions to MAPF (Kornhauser, Miller, and Spirakis 1984).”
Subdimensional expansion for multirobot path planning (2015, background): “Operator Decomposition (OD) [2] and Enhanced Partial Expansion A* (EPEA*) [12, 13] are lazy variants of A* designed for multirobot path planning which delay enumerating paths that are expensive based on a heuristic, thereby dramatically reducing the effective branching factor of multirobot systems.”
On the diameter of permutation groups (2011, background): “Indeed, this has long been a problem of interest in computer science (see [KMS84], [McK84], [BHK + 90], [BBS04], [BH05]).”
Optimal Multirobot Path Planning on Graphs: Complete Algorithms and Effective Heuristics (2015, background): “…LaValle (2013a,b), besides demonstrating signiﬁcantly improved computational performance due to the addition of the k -way split heuristic, we have substantially extended the generality of our ILP-based algorithmic framework, which now supports all common global time-and distance-based objectives.”
Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs (2013, background): “For complete formulations of PMG and MPPp, see (Kornhauser, Miller, and Spirakis 1984; Surynek 2010).”
Conflict-based search for optimal multi-agent pathfinding (2012, methodology): “A* always begins by expanding a state and inserting its successors into the open list (denoted OPEN).”
Growth in groups: ideas and perspectives (2013, neutral): “t(n) generating Alt(n), diamΓ(Alt(n),A) ≪ (log|G|)O(1) ≪ nO(1). This special case of the conjecture actually predates Babai; [BS92, p. 232] calls it “folkloric”. There are earlier references in print [KMS84], [McK84] where the question is posed as to the exact conditions under which a bound of nO(1)”