Time complexity

The complexity of robot motion planning

John Canny

Citations: 1401 • 1988

On the “piano movers'” problem I. The case of a two‐dimensional rigid polygonal body moving amidst polygonal barriers

Jacob T. Schwartz, Micha Sharir

Citations: 451 • 1983

Structure and Intractability of Optimal Multi-Robot Path Planning on Graphs

Jingjin Yu, Steven M. LaValle

Citations: 414 • 2013

PSPACE-completeness of sliding-block puzzles and other problems through the nondeterministic constraint logic model of computation

Robert A. Hearn, Erik D. Demaine

Citations: 317 • 2005

Movement control algorithms for realization of fault-tolerant ad hoc robot networks

Prithwish Basu, Jason Redi

Citations: 276 • 2004

Distributed covering by ant-robots using evaporating traces

Israel A. Wagner, Michael Lindenbaum, Alfred M. Bruckstein⋆

Citations: 274 • 1999

On the Piano Movers' Problem: III. Coordinating the Motion of Several Independent Bodies: The Special Case of Circular Bodies Moving Amidst Polygonal Barriers

Jacob T. Schwartz, Micha Sharir

Citations: 243 • 1983

Efficient collision detection for animation and robotics

Ming C. Lin, John Canny

Citations: 234 • 1993

On the Approximation of Shortest Common Supersequences and Longest Common Subsequences

Tao Jiang, Ming Li

Citations: 212 • 1995

On Cooperative Patrolling: Optimal Trajectories, Complexity Analysis, and Approximation Algorithms

Fabio Pasqualetti, Antonio Franchi, Francesco Bullo

Citations: 198 • 2012

Planning optimal paths for multiple robots on graphs

Jingjin Yu, Steven M. LaValle

Citations: 192 • 2013

DARP: Divide Areas Algorithm for Optimal Multi-Robot Coverage Path Planning

Athanasios Ch. Kapoutsis, Savvas A. Chatzichristofis, Elias B. Kosmatopoulos

Citations: 191 • 2017

Construction of cellular automata over hexagonal and triangular tessellations for path planning of multi-robots

Jasmeena Tariq, A. Kumaravel

Citations: 191 • 2016

A Theory of Complexity, Periodicity and the Design Axioms

Nam P. Suh

Citations: 190 • 1999

The (n2−1)-puzzle and related relocation problems

Daniel Ratner, Manfred K. Warmuth

Citations: 188 • 1990

Cyclic Scheduling of Identical Parts in a Robotic Cell

Yves Crama, Joris van de Klundert

Citations: 187 • 1997

Motion planning in the presence of moving obstacles

John H. Reif, Micha Sharir

Citations: 176 • 1994

On the complexity of kinodynamic planning

John Canny, Bruce R. Donald, John H. Reif, Patrick Xavier

Citations: 176 • 1988

Motion planning in the presence of moving obstacles

John H. Reif, Micha Sharir

Citations: 171 • 1985

An optimal periodic scheduler for dual-arm robots in cluster tools with residency constraints

Salim Rostami, Babak Hamidzadeh, D. Camporese

Citations: 161 • 2001