We present and experimentally evaluate the hypothesis that cooperative parallel search is well suited for hard graph coloring problems near a previously identified transition between under-and overconstrained instances. We find that simple cooperative methods can often solve such problems faster than the same number of independent agents. Many A.I. programs involve search to solve NP hard problems. While intractable in the worst case, of more relevance to many applications is their behavior in typical situations. In fact, for many classes of such problems, most instances can be solved much more readily than might be expected from a worst case analysis.

Rieffel, Eleanor (NASA Ames Research Center) | Venturelli, Davide (NASA Ames Research Center) | Do, Minh (NASA Ames Research Center) | Hen, Itay (University of Southern California) | Frank, Jeremy (NASA Ames Research Center)

There are two complementary ways to evaluate planning algorithms: performance on benchmark problems derived from real applications and analysis of performance on parametrized families of problems with known properties. Prior to this work, few means of generating parametrized families of hard planning problems were known. We generate hard planning problems from the solvable/unsolvable phase transition region of well-studied NP-complete problems that map naturally to navigation and scheduling, aspects common to many planning domains. We observe significant differences between state-of-the-art planners on these problem families, enabling us to gain insight into the relative strengths and weaknesses of these planners. Our results confirm exponential scaling of hardness with problem size, even at very small problem sizes. These families provide complementary test sets exhibiting properties not found in existing benchmarks.

Cohen, Eldan (University of Toronto) | Beck, J. Christopher (University of Toronto)

In the recent years, there has been significant work on the difficulty of heuristic search problems, identifying different problem instance characteristics that can have a significant impact on search effort. Phase transitions in the solubility of random problem instances have proved useful in the study of problem difficulty for other classes of computational problems, notably SAT and CSP, and it has been shown that the hardest problems typically occur during this rapid transition. In this work, we perform the first empirical investigation of the phase transition phenomena for heuristic search. We establish the existence of a rapid transition in the solubility of an abstract model of heuristic search problems and show that, for greedy best first search, the hardest instances are associated with the phase transition region. We then perform a novel investigation of the behavior of heuristics of different strength across the solubility spectrum. Finally, we demonstrate that the behavior of our abstract model carries over to commonly used benchmark problems including the Pancake Problem, Grid Navigation, TopSpin, and the Towers of Hanoi. An interesting deviation is observed and explained in the Sliding Puzzle.

We introduce a parameter that measures the "constrainedness" of an ensemble of combinatorial problems. If problems are over-constrained, they are likely to be insoluble. If problems are under-constrained, they are likely to be soluble. This constrainedness parameter generalizes a number of parameters previously used in different NPcomplete problem classes. Phase transitions in different NP classes can thus be directly compared. This parameter can also be used in a heuristic to guide search.

We present a quantum computer heuristic search algorithm for graph coloring. This algorithm uses a new quantum operator, appropriate for nonbinary-valued constraint satisfaction problems, and information available in partial colorings. We evaluate the algorithm empirically with small graphs near a phase transition in search performance. It improves on two prior quantum algorithms: unstructured search and a heuristic applied to the satisfiability (SAT) encoding of graph coloring. An approximate asymptotic analysis suggests polynomial-time cost for hard graph coloring problems, on average.