More Web Proxy on the site http://driver.im/

research-article

Open access

Towards Real Time Multi-robot Routing using Quantum Computing Technologies

Authors:

Duncan RussellAuthors Info & Claims

HPCAsia '19: Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region

Pages 111 - 119

https://doi.org/10.1145/3293320.3293333

Published: 14 January 2019 Publication History

Abstract

In this paper, we investigate the potential for current quantum computing technologies to provide good solutions to the NP-hard problem of routing multiple robots on a grid in real time. A hybrid quantum-classical approach has been presented in detail. Classical computation is used to generate candidate paths, while quantum annealing is used to select the optimal combination of paths. This second process is generally the most time consuming when performed clasically. The performance is benchmarked classically and on a D-Wave 2000Q with up to 200 robots and has shown that producing valid solutions for the problem of multi-robot routing is achievable with the current quantum annealing technology. The current limitations of using quantum annealing are also discussed.

References

[1]

Steven H Adachi and Maxwell P Henderson. 2015. Application of quantum annealing to training of deep neural networks. arXiv preprint arXiv:1510.06356 (2015).

[2]

Zhengbing Bian, Fabian Chudak, Robert Brian Israel, Brad Lackey, William G Macready, and Aidan Roy. 2016. Mapping constrained optimization problems to quantum annealing with application to fault diagnosis. Frontiers in ICT 3 (2016), 14.

[3]

Michael Booth and Steven P. Reinhardt. 2017. Partitioning Optimization Problems for Hybrid Classical / Quantum Execution TECHNICAL REPORT. Technical Report. D-Wave Systems Inc.

[4]

W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider. 2005. Coordinated multi-robot exploration. IEEE Transactions on Robotics 21, 3 (June 2005), 376--386.

Digital Library

[5]

Edward Farhi, Jeffrey Goldstone, and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028 (2014).

[6]

Edward Farhi, Jeffrey Goldstone, Sam Gutmann, and Michael Sipser. 2000. Quantum computation by adiabatic evolution. arXiv preprint quant-ph/0001106 (2000).

[7]

Neil Gershenfeld and Isaac L Chuang. 1998. Quantum computing with molecules. Scientific American 278, 6 (1998), 66--71.

[8]

Lov K Grover. 1997. Quantum mechanics helps in searching for a needle in a haystack. Physical review letters 79, 2 (1997), 325.

[9]

Peter E Hart, Nils J Nilsson, and Bertram Raphael. 1968. A formal basis for the heuristic determination of minimum cost paths. IEEE transactions on Systems Science and Cybernetics 4, 2 (1968), 100--107.

[10]

Matthew B Hastings, Dave Wecker, Bela Bauer, and Matthias Troyer. 2014. Improving quantum algorithms for quantum chemistry. arXiv preprint arXiv:1403.1539 (2014).

Digital Library

[11]

Mark W Johnson. 2018. Future Hardware Directions of Quantum Annealing. In Qubits Europe 2018. Retrieved September 12, 2018 from https://www.dwavesys.com/sites/default/files/mwj_dwave_qubits2018.pdf

[12]

Mark W Johnson, Mohammad HS Amin, Suzanne Gildert, Trevor Lanting, Firas Hamze, Neil Dickson, R Harris, Andrew J Berkley, Jan Johansson, Paul Bunyk, et al. 2011. Quantum annealing with manufactured spins. Nature 473, 7346 (2011), 194.

[13]

Stephen P Jordan. 2008. Quantum computation beyond the circuit model. arXiv preprint arXiv:0809.2307 (2008).

Digital Library

[14]

Richard M. Karp. 1972. Reducibility Among Combinatorial Problems. In Proceedings of a symposium on the Complexity of Computer Computations, held March 20--22, 1972, at the IBM Thomas J. Watson Research Center, Yorktown Heights, New York, USA. 85--103. http://www.cs.berkeley.edu/%7Eluca/cs172/karp.pdf

[15]

Andrew D King, Juan Carrasquilla, Jack Raymond, Isil Ozfidan, Evgeny Andriyash, Andrew Berkley, Mauricio Reis, Trevor Lanting, Richard Harris, Fabio Altomare, et al. 2018. Observation of topological phenomena in a programmable lattice of 1,800 qubits. Nature 560, 7719 (2018), 456.

[16]

Gary Kochenberger, Jin-Kao Hao, Fred Glover, Mark Lewis, Zhipeng Lü, Haibo Wang, and Yang Wang. 2014. The unconstrained binary quadratic programming problem: a survey. Journal of Combinatorial Optimization 28, 1 (2014), 58--81.

Digital Library

[17]

Richard Y Li, Rosa Di Felice, Remo Rohs, and Daniel A Lidar. 2018. Quantum annealing versus classical machine learning applied to a simplified computational biology problem. NPJ quantum information 4, 1 (2018), 14.

[18]

F. Neukart, G. Compostella, C. Seidel, D. von Dollen, S. Yarkoni, and B Parney. 2017. Traffic flow optimization using a quantum annealer. Frontiers in ICT 4 (2017), 29.

[19]

Michael A Nielsen and Isaac L Chuang. 2000. Quantum computation and quantum information. Cambridge University Press.

Digital Library

[20]

Peter W Shor. 1999. Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM review 41, 2 (1999), 303--332.

Digital Library

[21]

Olawale Titiloye and Alan Crispin. 2011. Graph coloring with a distributed hybrid quantum annealing algorithm. In KES International Symposium on Agent and Multi-Agent Systems: Technologies and Applications. Springer, 553--562.

Digital Library

[22]

Tony T Tran, Minh Do, Eleanor G Rieffel, Jeremy Frank, Zhihui Wang, Bryan O'Gorman, Davide Venturelli, and J Christopher Beck. 2016. A hybrid quantum-classical approach to solving scheduling problems. In Ninth Annual Symposium on Combinatorial Search.

Cited By

Windmann S(2024)Quantum computer-aided job scheduling for storage and retrieval systemsat - Automatisierungstechnik10.1515/auto-2023-007272:1(15-21)Online publication date: 10-Jan-2024
https://doi.org/10.1515/auto-2023-0072
Gomes CFernandes JFalcao GKar STayur S(2024)A Systematic Mapping Study on Quantum and Quantum-inspired Algorithms in Operations ResearchACM Computing Surveys10.1145/370087457:3(1-35)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3700874
Rabih BHassan ABassem JAdnan Y(2024)New approach to solve unconstrained binary quadratic problemRAIRO - Operations Research10.1051/ro/202408758:4(3241-3262)Online publication date: 8-Aug-2024
https://doi.org/10.1051/ro/2024087
Show More Cited By

Index Terms

Towards Real Time Multi-robot Routing using Quantum Computing Technologies

Recommendations

Quantum computing
Encyclopedia of Computer Science

In a conventional computer, information is represented by quantities that obey the laws of classical physics, such as the voltage levels in a logic circuit. But as the size of microelectronics shrinks, the underlying quantum physics will eventually ...
Problems and Solutions in Quantum Computing and Quantum Information
Quantum Computing: A Gentle Introduction

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

HPCAsia '19: Proceedings of the International Conference on High Performance Computing in Asia-Pacific Region

January 2019

143 pages

ISBN:9781450366328

DOI:10.1145/3293320

Copyright © 2019 Owner/Author.

This work is licensed under a Creative Commons Attribution International 4.0 License.

In-Cooperation

Sun Yat-Sen University
CCF: China Computer Federation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 14 January 2019

Check for updates

Qualifiers

Research-article
Research
Refereed limited

Conference

HPC Asia 2019

HPC Asia 2019: International Conference on High Performance Computing in Asia-Pacific Region

January 14 - 16, 2019

Guangzhou, China

Acceptance Rates

HPCAsia '19 Paper Acceptance Rate 15 of 32 submissions, 47%;

Overall Acceptance Rate 69 of 143 submissions, 48%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
1,142
Total Downloads

Downloads (Last 12 months)234
Downloads (Last 6 weeks)24

Reflects downloads up to 13 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Windmann S(2024)Quantum computer-aided job scheduling for storage and retrieval systemsat - Automatisierungstechnik10.1515/auto-2023-007272:1(15-21)Online publication date: 10-Jan-2024
https://doi.org/10.1515/auto-2023-0072
Gomes CFernandes JFalcao GKar STayur S(2024)A Systematic Mapping Study on Quantum and Quantum-inspired Algorithms in Operations ResearchACM Computing Surveys10.1145/370087457:3(1-35)Online publication date: 11-Nov-2024
https://dl.acm.org/doi/10.1145/3700874
Rabih BHassan ABassem JAdnan Y(2024)New approach to solve unconstrained binary quadratic problemRAIRO - Operations Research10.1051/ro/202408758:4(3241-3262)Online publication date: 8-Aug-2024
https://doi.org/10.1051/ro/2024087
Rocutto LMaronese MDragoni DCavalli ACavazzoni C(2024)Comparing Adiabatic Quantum Computers for satellite images feature extractionFuture Generation Computer Systems10.1016/j.future.2024.04.027Online publication date: Apr-2024
https://doi.org/10.1016/j.future.2024.04.027
Yan FIliyasu ALi NSalama AHirota K(2024)Quantum robotics: a review of emerging trendsQuantum Machine Intelligence10.1007/s42484-024-00225-56:2Online publication date: 28-Nov-2024
https://doi.org/10.1007/s42484-024-00225-5
Vandelli MLignarolo ACavazzoni CDragoni D(2024)Evaluating the practicality of quantum optimization algorithms for prototypical industrial applicationsQuantum Information Processing10.1007/s11128-024-04560-123:10Online publication date: 9-Oct-2024
https://doi.org/10.1007/s11128-024-04560-1
McGeoch CFarré P(2023)Milestones on the Quantum Utility Highway: Quantum Annealing Case StudyACM Transactions on Quantum Computing10.1145/36253075:1(1-30)Online publication date: 16-Dec-2023
https://dl.acm.org/doi/10.1145/3625307
Osaba EVillar-Rodriguez E(2023)QOPTLib: A Quantum Computing Oriented Benchmark for Combinatorial Optimization ProblemsBenchmarks and Hybrid Algorithms in Optimization and Applications10.1007/978-981-99-3970-1_4(49-63)Online publication date: 22-Aug-2023
https://doi.org/10.1007/978-981-99-3970-1_4
Gachnang PEhrenthal JHanne TDornberger R(2022)Quantum Computing in Supply Chain Management State of the Art and Research DirectionsAsian Journal of Logistics Management10.14710/ajlm.2022.143251:1(57-73)Online publication date: 23-May-2022
https://doi.org/10.14710/ajlm.2022.14325
Osaba EVillar-Rodriguez EOregi I(2022)A Systematic Literature Review of Quantum Computing for Routing ProblemsIEEE Access10.1109/ACCESS.2022.317779010(55805-55817)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3177790
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents