Computational solution and analysis of disentanglement puzzles

Disentanglement puzzles, as a type of mechanical puzzles whose goal is to separate pieces from each other. Traditionally these puzzles are designed for human entertainment, leaving reputations of challenging to solve. The intrinsic difficulty of such puzzles also poses various challenges to the state-of-the-art algorithms from various research areas in computer sciences. For example, the present motion planning algorithms from robotics usually fail to solve disentanglement puzzles, and no geometry processing tools have been designed for the analysis and design of disentanglement puzzles. Mathematically the disentanglement puzzles can be represented with their corresponding Configuration Space, or C-Space. This concept is widely used among robotics, physical simulation, and geometry processing. For example, the motions of robot arms, state transitions of physical systems, and the deformation of geometries can all be abstracted as vector calculus over a point in the corresponding C-space. The challenges of disentanglement puzzles come from their equally challenging C-space. Unfortunately, the C-space is usually not well understood due to the curse of dimensionality, and thus commonly represented in an implicit manner. Such a practice creates a challenge in motion planning called "narrow passage problem", which refers to the difficulties for a motion planning algorithm to discover a path where one or more narrow tunnels must be involved. This is the exact problem that blocks the solving of disentanglement puzzles in computational methods. This thesis focuses on better understanding the disentanglement puzzles and their C-space. The crucial goal is to develop a motion planning algorithm that can solve these puzzles with reasonable performance. Additional goals include suggesting novel techniques to help the analysis of existing puzzles, and potentially design of new puzzles. The proposed thesis consists of four technical chapters after a dedicated chapter for related works. The first technical chapter discusses the construction of a navigation function that can go through narrow tunnels by employing simulation electromagnetic fields. It proposes a few algorithms under this category, their performance and limitations. The second technical chapter explores the possibility of utilizing reinforcement learning to accelerate the solution of similar but novel puzzles with the training results from existing puzzles. It discusses the challenges to apply reinforcement learning methods in motion planning, and suggests disentanglement puzzles can serve as a new class of task/dataset to evaluate reinforcement learning algorithms. The third technical chapter proposes a scalable motion planning system, that can solve disentanglement puzzles through detecting narrow tunnels in C-space. It presents algorithms to detect key features of puzzle pieces, schemes to locate candidate narrow tunnels by assembling those features, and a distributed motion planning algorithm to search the C-space from a large number of potential narrow tunnels. The last technical chapter focuses on the analysis of wire puzzles. It proposes a set of metrics to quantify puzzle vs. non-puzzle, and suggests two common approaches to design disentanglement puzzles. With this set of metrics, this chapter makes new applications like automatic puzzle design possible.