NTRS - NASA Technical Reports Server

Back to Results
Phase Transitions in Planning Problems: Design and Analysis of Parameterized Families of Hard Planning ProblemsThere are two common ways to evaluate algorithms: performance on benchmark problems derived from real applications and analysis of performance on parametrized families of problems. The two approaches complement each other, each having its advantages and disadvantages. The planning community has concentrated on the first approach, with few ways of generating parametrized families of hard problems known prior to this work. Our group's main interest is in comparing approaches to solving planning problems using a novel type of computational device - a quantum annealer - to existing state-of-the-art planning algorithms. Because only small-scale quantum annealers are available, we must compare on small problem sizes. Small problems are primarily useful for comparison only if they are instances of parametrized families of problems for which scaling analysis can be done. In this technical report, we discuss our approach to the generation of hard planning problems from classes of well-studied NP-complete problems that map naturally to planning problems or to aspects of planning problems that many practical planning problems share. These problem classes exhibit a phase transition between easy-to-solve and easy-to-show-unsolvable planning problems. The parametrized families of hard planning problems lie at the phase transition. The exponential scaling of hardness with problem size is apparent in these families even at very small problem sizes, thus enabling us to characterize even very small problems as hard. The families we developed will prove generally useful to the planning community in analyzing the performance of planning algorithms, providing a complementary approach to existing evaluation methods. We illustrate the hardness of these problems and their scaling with results on four state-of-the-art planners, observing significant differences between these planners on these problem families. Finally, we describe two general, and quite different, mappings of planning problems to QUBOs, the form of input required for a quantum annealing machine such as the D-Wave II.
Document ID
Document Type
Conference Paper
Hen, Itay (Stinger Ghaffarian Technologies, Inc. (SGT, Inc.) Moffett Field, CA, United States)
Rieffel, Eleanor G. (NASA Ames Research Center Moffett Field, CA United States)
Do, Minh (Stinger Ghaffarian Technologies, Inc. (SGT, Inc.) Moffett Field, CA, United States)
Venturelli, Davide (Universities Space Research Association Moffett Field, CA, United States)
Date Acquired
September 26, 2014
Publication Date
July 31, 2014
Subject Category
Cybernetics, Artificial Intelligence and Robotics
Report/Patent Number
Meeting Information
28th AIAA Conference on Artificial Intelligence(Quebec City)
Funding Number(s)
Distribution Limits
Public Use Permitted.

Available Downloads

NameType 20140012632.pdf STI