PSPACE

Some algebraic and geometric computations in PSPACE

John Canny

引用数: 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

引用数: 317 • 2005

Motion planning in the presence of moving obstacles

John H. Reif, Micha Sharir

引用数: 171 • 1985

Complexity of the Generalized Mover's Problem.

John H. Reif

引用数: 42 • 1985

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

Max Kanovich, Jacqueline Vauzeilles

引用数: 26 • 2001

The Complexity of Fine Motion Planning

B. K. Natarajan

引用数: 22 • 1988

Parameterized complexity analysis in robot motion planning

Marco Cesati, H. Todd Wareham

引用数: 19 • 2002

Computational Complexity of Motion Planning of a Robot through Simple Gadgets

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

引用数: 12 • 2018

Complexity analysis and optimal algorithms for decentralized decision making

Daniel S. Bernstein, Shlomo Zilberstein

引用数: 11 • 2005

Tractable Reasoning about Group Beliefs

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

引用数: 8 • 2014

Decision Procedures for Epistemic Logic Exploiting Belief Bases

Emiliano Lorini, Benito Fabian Romero Jimenez

引用数: 8 • 2019

Task and Motion Planning Is PSPACE-Complete

William Vega-Brown, Nicholas Roy

引用数: 6 • 2020

On decidability and complexity of low-dimensional robot games

Reino Niskanen, Igor Potapov, J. Reichert

引用数: 5 • 2019

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

Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

引用数: 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

引用数: 4 • 2020

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

Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

引用数: 4 • 2018

PSPACE-Hard 2D Super Mario Games: Thirteen Doors

Erik D. Demaine

引用数: 3 • 2020

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

Erik D. Demaine, Dylan Hendrickson, Jayson Lynch

引用数: 3 • 2018

Bayesian Optimization for Polynomial Time Probabilistically Complete STL Trajectory Synthesis

Vince Kurtz, Hai Lin

引用数: 3 • 2019

Robot Games with States in Dimension One

Reino Niskanen

引用数: 2 • 2016