PSPACE

Some algebraic and geometric computations in PSPACE

John Canny

Citations: 581 • 1988

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

Motion planning in the presence of moving obstacles

John H. Reif, Micha Sharir

Citations: 171 • 1985

Complexity of the Generalized Mover's Problem.

John H. Reif

Citations: 42 • 1985

The classical AI planning problems in the mirror of Horn linear logic: semantics, expressibility, complexity

Max Kanovich, Jacqueline Vauzeilles

Citations: 26 • 2001

The Complexity of Fine Motion Planning

B. K. Natarajan

Citations: 22 • 1988

Parameterized complexity analysis in robot motion planning

Marco Cesati, H. Todd Wareham

Citations: 19 • 2002

Computational Complexity of Motion Planning of a Robot through Simple Gadgets

Erik D. Demaine, Isaac Grosof, Jayson Lynch, Mikhail Rudoy

Citations: 12 • 2018

Complexity analysis and optimal algorithms for decentralized decision making

Daniel S. Bernstein, Shlomo Zilberstein

Citations: 11 • 2005

Tractable Reasoning about Group Beliefs

Barbara Dunin‐Kȩplicz, Andrzej Szałas, Rineke Verbrugge

Citations: 8 • 2014

Decision Procedures for Epistemic Logic Exploiting Belief Bases

Emiliano Lorini, Benito Fabian Romero Jimenez

Citations: 8 • 2019

Task and Motion Planning Is PSPACE-Complete

William Vega-Brown, Nicholas Roy

Citations: 6 • 2020

On decidability and complexity of low-dimensional robot games

Reino Niskanen, Igor Potapov, J. Reichert

Citations: 5 • 2019

Toward a General Complexity Theory of Motion Planning: Characterizing Which Gadgets Make Games Hard

Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

Citations: 4 • 2020

Relocating Units in Robot Swarms with Uniform Control Signals is PSPACE-Complete.

David Caballero, Angel A. Cantu, Timothy Gomez, Austin Luchsinger, Robert Schweller, Tim Wylie

Citations: 4 • 2020

Toward a General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard

Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

Citations: 4 • 2018

PSPACE-Hard 2D Super Mario Games: Thirteen Doors

Erik D. Demaine

Citations: 3 • 2020

A General Theory of Motion Planning Complexity: Characterizing Which Gadgets Make Games Hard.

Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

Citations: 3 • 2018

Bayesian Optimization for Polynomial Time Probabilistically Complete STL Trajectory Synthesis

Vince Kurtz, Hai Lin

Citations: 3 • 2019

Robot Games with States in Dimension One

Reino Niskanen

Citations: 2 • 2016