The Complexity of Sliding-Block Puzzles and Plank Puzzles (2008)
Sliding-block puzzles have long fascinated aficionados of recreational mathematics. From Sam Loyd’s infamous 14-15 puzzle to the latest whimsical variants such as Rush Hour TM, these puzzles seem...
TipOver TM is a popular puzzle in which the goal is to navigate a layout of vertical crates, tipping some over to reach others, so as to eventually reach a target crate. Crates can only tip into...
The Complexity of the Dyson Telescopes Puzzle (2007)
In this paper, we give a PSPACE-completeness reduction from QBF to the Dyson Telescopes Puzzle where opposing telescopes can overlap in at least two spaces. The reduction does not use tail ends of...
Amazons is PSPACE-complete (2005)
Amazons is a board game which combines elements of Chess and Go. It has become popular in recent years, and has served as a useful platform for both game-theoretic study and AI games research. Buro...
Building Grounded Abstractions for Artificial Intelligence Programming (2004)
Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach...
Building Grounded Abstractions for Artificial Intelligence Programming (2004)
Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach...
Building Grounded Abstractions for Artificial Intelligence Programming (2004)
Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach...
Building Grounded Abstractions for Artificial Intelligence Programming (2004)
Most Artificial Intelligence (AI) work can be characterized as either ``high-level'' (e.g., logical, symbolic) or ``low-level'' (e.g., connectionist networks, behavior-based robotics). Each approach...
Hearn, Robert A., Demaine, Erik D.
We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple graph...
The Nondeterministic Constraint Logic model of computation: Reductions and applications (2002)
Robert A. Hearn, Erik D. Demaine
Abstract. We present a nondeterministic model of computation based on reversing edge directions in weighted directed graphs with minimum in-flow constraints on vertices. Deciding whether this simple...
Playing Games with Algorithms: Algorithmic Combinatorial Game Theory (2001)
Demaine, Erik D., Hearn, Robert A.
Combinatorial games lead to several interesting, clean problems in algorithms and complexity theory, many of which remain open. The purpose of this paper is to provide an overview of the area to...
A.: Building Grounding Abstractions for Artificial Intelligence Programming (2001)
Gerald J. Sussman, Arthur C. Smith, Robert A. Hearn, Robert A. Hearn
Most Artificial Intelligence (AI) work can be characterized as either “high-level” (e.g., logical, symbolic) or “low-level ” (e.g., connectionist, behavior-based robotics). Each approach...
Intelligence Programming (2001)
Robert A. Hearn, Robert A. Hearn
Most Artificial Intelligence (AI) work can be characterized as either “high-level ” (e.g., logical, symbolic) or “low-level ” (e.g., connectionist networks, behavior-based robotics). Each...