ANYTIME SOLVING BY SOLUTION REFINEMENT BY Chris Sexton BS in Computer Science, Indiana University, 2008 THESIS Submitted to the University of New Hampshire in Partial Fulfillment of the Requirements for the Degree of Masters of Science in Computer Science December, 2012 This thesis has been examined and approved. Thesis director, Wheeler Ruml, Associate Professor of Computer Science Radim Bartoˇs, Chair, Associate Professor of Computer Science Philip J. Hatcher, Professor of Computer Science Michel Charpentier, Associate Professor of Computer Science Date ACKNOWLEDGMENTS Completingathesisisimpossibletoachievewithoutsupport. IwouldliketothankProfessor Wheeler Ruml, my thesis advisor, for his guidance and support through the process. His influence in instruction, group research, and personal research is invaluable. I would like to give a special thanks to Ethan Burns who provided the thoughtfully crafted search framework that I used in my code implementations. For their ideas and comradery, I would liketothanktheentireUNHAIgroup, bothpastandpresent. Finally, Iwouldliketothank my lovely wife, Madeleine, who has supported me and put up with my absence throughout my time as a graduate student. iii TABLE OF CONTENTS ACKNOWLEDGMENTS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii LIST OF FIGURES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vi Chapter 1 Introduction 1 1.1 Domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 Chapter 2 Previous Work 6 2.1 Suboptimal Search Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.2 Weighted A* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3 Beam Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.4 Constructive Solvers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 2.5 Joint and LPA* . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.6 Iterative Tunneling Search with A* . . . . . . . . . . . . . . . . . . . . . . . 15 Chapter 3 Anytime Solution Refinement 17 3.1 Local Search Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 3.2 Node Selection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 3.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 Chapter 4 Windowing 31 4.1 Iterative Windowing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Offset Windows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 4.3 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 iv Chapter 5 Discussion 38 5.1 Limitations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 5.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40 BIBLIOGRAPHY 42 v LIST OF FIGURES 1-1 A 15 tile puzzle in its goal configuration . . . . . . . . . . . . . . . . . . 3 1-2 Sample blocks world states. . . . . . . . . . . . . . . . . . . . . . . . . . 4 1-3 A start and goal state with blocks A & B deadlocked . . . . . . . . . . . 5 2-1 Beam and weighted A* search with varying beam widths and weights respectively. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 2-2 Best first vs breadth first beam search . . . . . . . . . . . . . . . . . . . 9 2-3 The decomposition of the 15 puzzle. . . . . . . . . . . . . . . . . . . . . 12 2-4 A constructive solver for tiles . . . . . . . . . . . . . . . . . . . . . . . . 13 2-5 ITSA* Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 3-1 A shortcut in the subpath from G to G shown by the dotted lines and s g the node, 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 ∗ 3-2 Pseudocode for solution refinement . . . . . . . . . . . . . . . . . . . . . 18 3-3 Refinement using A* over several puzzles. . . . . . . . . . . . . . . . . . 23 3-4 Refinement versus beam search . . . . . . . . . . . . . . . . . . . . . . . 24 3-5 Time profile of refinement using A* over several puzzle sizes. . . . . . . 25 3-6 Refinement on blocks world . . . . . . . . . . . . . . . . . . . . . . . . . 27 3-7 Time profile of refinement using A* and wA* (w=1.5) over several blocks world domains . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 4-1 Pseudocode for incremental windows . . . . . . . . . . . . . . . . . . . . 32 4-2 Pseudocode for offset windows . . . . . . . . . . . . . . . . . . . . . . . . 33 4-3 Time profile of sliding tile refinement using iterative window sizes. . . . 35 4-4 Time profile of blocks world refinement using iterative window sizes. . . 36 vi Solving problems with large state spaces is a difficult task to undertake. For most problems that scale in size, there is a scale at which state of the art optimal solving fails. There are many suboptimal methods that provide solutions at the expense of solution length, but these also have an eventual point of failure. This thesis investigates problems at a size at which even the most popular suboptimal solversfail. Domainsoftenhavedomain-specificconstructiveheuristicsthatquicklyprovide poor solutions, even for large problems. We present solution refinement over constructed solutionsasamethodofimprovingapoorqualitybutquicklyobtainedsolutionbysearching in the solution path for shortcuts. These shortcuts are found incrementally, leading to improved solutions on problems where traditional suboptimal algorithms fail to find any solution. Several improvements to solution refinement will be presented in order to improve the quality of solutions found and the speed at which they are obtained. Suboptimal search will be used to allow search to find shortcuts between nodes more distant. Next, incremen- tally changing the search distance will provide quality solutions faster than statically set distances. Finally, offset search will provide a more complete coverage of the search space in order to maximize the number of shortcuts found. vii CHAPTER 1 Introduction Inthefieldofheuristicsearch, itisusefultoexploredomainswhichcanbescaledinsizeand complexity. This property gives access to more difficult problems, pushing the state of the art in solving methods. For example, in the sliding tile domain, the size of the puzzle can be scaled to increase the complexity of solving the puzzle. Similarly, the towers of Hanoi domain offers scaling in the number of discs that need to be sorted in order to solve the puzzle. When scaled to even a modest size, these problems quickly become intractable for optimal search algorithms like A* (Hart et al., 1968). Suboptimal search algorithms such as weighted A* (Pohl, 1970) may be used beyond this point, but even these will fail on very large problems. This thesis presents a method of solving large state space search problems for which traditional search methods have undesirable performance. When searching for solutions in large state spaces, the traditional approach for finding solutions is to craft heuristics which provide a high level of guidance for the problem at hand and search sub-optimally. By preferring the heuristic value, h(n), instead of the underestimate of the solution length, f(n) = g(n)+h(n), beam search (Bisiani, 1992) and weighted A* search can find solutions to problems where A* fails. IDA* (Korf et al., 2001) offers only linear memory usage, but exponential time complexity. Like A*, weighted A* has worst-case exponential memory complexity, but offers better search guidance, potentially expanding many fewer nodes on the path to a solution and therefore is able to solve more difficult problems. However, weighted A* only works up to a certain point due to its space complexity. Beyond this, beam search can be used, but it provides no guarantee on solution optimality, and can produce very long paths, but has a small memory footprint. 1 In order to solve problems where other search methods falter, one option is to use a domain-specific constructive solution. Using a hand-crafted solver, we can find solutions to problems in linear time, with some downsides. The first downside is that the domain used must be solvable in this manner. Problems which have recursive solutions are ideal in this situation. The second downside is that the length of the solutions acquired through these methods are unlikely to be short. A similar method exists in planning with scheduling problems. In order to reduce the makespan of a plan, each action can be quickly planned to be taken sequentially. Once a satisfacting plan is obtained, actions which are independent may be rescheduled to run in parallel, shortening the makespan of the entire plan. In this thesis, a method of improving solutions returned by deterministic solvers will be presented, exploring the space between hand-crafted solvers and heuristic search. The improvement is achieved by using the deterministic solution path as guidance for heuristic search, finding shortcuts between nodes. Refinement is a generic process for solving a class of problems in which solutions can be obtained and heuristic guidance between any two nodes can be computed. This thesis makes two conclusions. First, a refinement method will be shown be shown to reduce the length of constructive solutions in the tiles puzzle by up to 40% on small 15- puzzlespuzzlesand10%onlarge80-puzzles. Intheblocksworlddomain,similarthoughnot as extensiveshortcuts willbe found. Second, these refinement solverswillproduce solutions orders of magnitude shorter than those produced by beam search and will always return a path, even for very difficult problems. Where weighted A* and beam search fail, solution refinement will produce anytime results on every instance. This work suggests an avenue for future work in augmenting or complementing constructive heuristics, using instead of trying to replace them with general-purpose heuristic search. 2 1.1 Domains We will primarily examine two domains in this thesis, the N-tile puzzle and blocks world. These will be detailed in order to understand the reasons why they are complex problems. 1.1.1 Sliding Tiles Blank 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Figure 1-1: A 15 tile puzzle in its goal configuration The sliding tile puzzle is very well known in the field of heuristic search. A set of N tiles are laid out in a square grid n tiles wide and n tiles tall, where n = √N +1. There is one blank space in the puzzle used to move tiles. Any tile adjacent to the blank can be swapped with the blank, moving both the blank and the tile. A simple goal configuration is presented in Figure 1-1. The sliding tile puzzle presents a very large state space even at small puzzle sizes. The puzzle can be scaled up simply by adding rows and columns. Each puzzle has N tiles and increases the complexity of the state space. It has been shown that solving the N puzzle optimally is NP-Hard (Ratner and Warmuth, 1986). The first optimal solver for the 24 puzzle used iterative-deepening-A* (IDA*) (Korf and Taylor, 1996) and generated between 8 billion and 8 trillion nodes before finding the 2 solution. The state space of an nxn puzzle is (n )!/2 (Korf and Taylor, 1996; Sadikov 13 and Bratko, 2007). For a 15 puzzle, this is 1.0 10 reachable states, for the 80 puzzle, × 120 2.8 10 . While a major point of heuristic search is to avoid searching every node in a × 3