Search
  • All Journals
Advanced Search
Search articles by Title, Author, Keywords, DOI
7.7CiteScore
2.0Impact Factor
Advanced Search
MAP  >  The Knowledge Engineering Review
2016 Volume 31
Article Contents
Next Previous
RESEARCH ARTICLE   Open Access    

Comparing planning problem compilation approaches for quantum annealing

  • 1.

    QuAIL

  • 2.

    Intelligent Systems Division

  • 3.

    Suite 220 Mountain View

  • 4.

    Suite 400 Greenbelt

More Information
  • Abstract: One approach to solving planning problems is to compile them to other problems for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances of quadratic unconstrained binary optimization (QUBO) problem. Early quantum annealers are now available, though their constraints restrict the types of QUBOs they can take as input. Here, we introduce the planning community to the key steps in compiling planning problems to QA hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we describe preliminary results from running an early quantum annealer on a parametrized family of hard planning problems. The results show that different mappings can substantially affect performance, even when many features of the resulting instances are similar. We conclude with insights gained from this early study that suggest directions for future work.
  • 加载中
  • Achlioptas D. & Friedgut E. 1999. A sharp threshold for k-colorability. Random Structures and Algorithms 14(1), 63–70.

    Google Scholar

    Achlioptas D. & Moore C. 2003. Almost all graphs with average degree 4 are 3-colorable. Journal of Computer and System Sciences 67(2), 441–471.

    Google Scholar

    Babbush R., O’Gorman B. & Aspuru-Guzik A. 2013. Resource efficient gadgets for compiling adiabatic quantum optimization problems. Annalen der Physik 525(10–11), 877–888.

    Google Scholar

    Blum A. & Furst M. 1997. Planning through planning graph analysis. Artificial Intelligence Journal 90, 281–330.

    Google Scholar

    Boros E. & Hammer P. L. 2002. Pseudo-boolean optimization. Discrete Applied Mathematics 123(1), 155–225.

    Google Scholar

    Cai J., Macready B. & Roy A. 2014. A practical heuristic for finding graph minors. arXiv:1406:2741.

    Google Scholar

    Chien S., Johnston M., Frank J., Giuliano M., Kavelaars A., Lenzen C., Policella N. & Verfailie G. 2012. A generalized timeline representation, services, and interface for automating space mission operations. In 12th International Conference on Space Operations.

    Google Scholar

    Coja-Oghlan A. 2013. Upper-bounding the k-colorability threshold by counting covers. arXiv:1305.0177.

    Google Scholar

    Culberson J., Beacham A. & Papp D. 1995. Hiding our colors. In Proceedings of the CP95 Workshop on Studying and Solving Really Hard Problems. 31–42.

    Google Scholar

    Das A. & Chakrabarti B. K. 2008. Colloquium: quantum annealing and analog quantum computation. Reviews of Modern Physics 80, 1061–1081.

    Google Scholar

    Do M. B. & Kambhampati S. 2001. Planning as constraint satisfaction: solving the planning graph by compiling it into CSP. Artificial Intelligence Journal 132(2), 151–1182.

    Google Scholar

    Dubois O. & Mandler J. 2002. On the non-3-colourability of random graphs. arXiv:math/0209087.

    Google Scholar

    Farhi E., Goldstone J., Gutmann S. & Sipser M. 2000. Quantum computation by adiabatic evolution. arXiv:quant-ph/0001106.

    Google Scholar

    Fikes R. E. & Nilsson N. J. 1972. STRIPS: a new approach to the application of theorem proving to problem solving. Artificial Intelligence 2(3), 189–208.

    Google Scholar

    Ghallab M., Nau D. & Traverso P. 2004. Automated Planning: Theory & Practice. Elsevier.

    Google Scholar

    International Planning Competition 2004. The International Planning Competition Website. http://icaps-conference.org/index.php/Main/Competitions.

    Google Scholar

    Kautz H. 2004. SATPLAN04: planning as satisfiability. Working Notes on the Fourth International Planning Competition (IPC-2004), 44–45.

    Google Scholar

    Kautz H. A. & Selman B. 1999. Unifying SAT-based and graph-based planning. In Proceedings of IJCAI'1999.

    Google Scholar

    Nielsen M. & Chuang I. L. 2001. Quantum Computing and Quantum Information, Cambridge, Cambridge University Press.

    Google Scholar

    Perdomo-Ortiz A., Fluegemann J., Biswas R. & Smelyanskiy V. N. 2015. A performance estimator for quantum annealers: gauge selection and parameter setting. arXiv preprint arXiv:1503.01083.

    Google Scholar

    Rieffel E. G. & Polak W. 2011. A Gentle Introduction to Quantum Computing, Cambridge, MA, MIT Press.

    Google Scholar

    Rieffel E. G., Venturelli D., Hen I., Do M. & Frank J. 2014. Parametrized families of hard planning problems from phase transitions. In Proceedings of the Twenty-Eighth AAAI Conference on Artificial Intelligence (AAAI-14). 2337–2343.

    Google Scholar

    Rieffel E. G., Venturelli D., O’Gorman B., Do M. B., Prystay E. M. & Smelyanskiy V. N. 2015. A case study in programming a quantum annealer for hard operational planning problems. Quantum Information Processing 14(1), 1–36.

    Google Scholar

    Smelyanskiy V. N, Rieffel E. G, Knysh S. I, Williams C. P, Johnson M. W., Thom M. C., Macready W. G. & Pudenz K. L. 2012. A near-term quantum computing approach for hard computational problems in space exploration. arXiv:1204.2821.

    Google Scholar

  • Cite this article

    Bryan O’Gorman, Eleanor Gilbert Rieffel, Minh Do, Davide Venturelli, Jeremy Frank. 2016. Comparing planning problem compilation approaches for quantum annealing. The Knowledge Engineering Review 31(5)465−474, doi: 10.1017/S0269888916000278
    Bryan O’Gorman, Eleanor Gilbert Rieffel, Minh Do, Davide Venturelli, Jeremy Frank. 2016. Comparing planning problem compilation approaches for quantum annealing. The Knowledge Engineering Review 31(5)465−474, doi: 10.1017/S0269888916000278
    shu
Download PDF

Article Metrics

Article views(32) PDF downloads(100)

Other Articles By Authors

RESEARCH ARTICLE   Open Access    

Comparing planning problem compilation approaches for quantum annealing

  • 1.

    QuAIL

  • 2.

    Intelligent Systems Division

  • 3.

    Suite 220 Mountain View

  • 4.

    Suite 400 Greenbelt

  • Published online: 22 February 2017
The Knowledge Engineering Review  31,  2016, 31(5): 465−474  |  Cite this article

Abstract: Abstract: One approach to solving planning problems is to compile them to other problems for which powerful off-the-shelf solvers are available; common targets include SAT, CSP, and MILP. Recently, a novel optimization technique has become available: quantum annealing (QA). QA takes as input problem instances of quadratic unconstrained binary optimization (QUBO) problem. Early quantum annealers are now available, though their constraints restrict the types of QUBOs they can take as input. Here, we introduce the planning community to the key steps in compiling planning problems to QA hardware: a hardware-independent step, mapping, and a hardware-dependent step, embedding. After describing two approaches to mapping general planning problems to QUBO, we describe preliminary results from running an early quantum annealer on a parametrized family of hard planning problems. The results show that different mappings can substantially affect performance, even when many features of the resulting instances are similar. We conclude with insights gained from this early study that suggest directions for future work.

    HTML

    Acknowledgments

    • The authors are grateful to Zhihui Wang for helpful discussions. This work was supported in part by the Office of the Director of National Intelligence (ODNI), the Intelligence Advanced Research Projects Activity (IARPA), via IAA 145483; by the AFRL Information Directorate under grant F4HBKC4162G001. The views and conclusions contained herein are those of the authors and should not be interpreted as necessarily representing the official policies or endorsements, either expressed or implied, of ODNI, IARPA, AFRL, or the US Government. The US Government is authorized to reproduce and distribute reprints for Governmental purpose notwithstanding any copyright annotation thereon. The authors also like to acknowledge support from the NASA Advanced Exploration Systems program and NASA Ames Research Center and NASA grant NNX12AK33A.

    Rights and permissions
    • © Cambridge University Press, 2017 2017Cambridge University Press
References (24)
  • About this article
    Cite this article
    Bryan O’Gorman, Eleanor Gilbert Rieffel, Minh Do, Davide Venturelli, Jeremy Frank. 2016. Comparing planning problem compilation approaches for quantum annealing. The Knowledge Engineering Review 31(5)465−474, doi: 10.1017/S0269888916000278
    Bryan O’Gorman, Eleanor Gilbert Rieffel, Minh Do, Davide Venturelli, Jeremy Frank. 2016. Comparing planning problem compilation approaches for quantum annealing. The Knowledge Engineering Review 31(5)465−474, doi: 10.1017/S0269888916000278
    shu

    • Catalog

      /

      DownLoad:  Full-Size Img  PowerPoint
      Return
      Return