Parallel Quantum Rapidly-Exploring Random Trees
In this paper, we present the Parallel Quantum Rapidly-Exploring Random Tree (Pq-RRT) algorithm, a parallel version of the Quantum Rapidly-Exploring Random Trees (q-RRT) algorithm. Parallel Quantum RRT is a parallel quantum algorithm formulation of a sampling-based motion planner that uses Quantum A...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2024-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/10485279/ |
| _version_ | 1797221985466449920 |
|---|---|
| author | Paul Lathrop Beth Boardman Sonia Martinez |
| author_facet | Paul Lathrop Beth Boardman Sonia Martinez |
| author_sort | Paul Lathrop |
| collection | DOAJ |
| description | In this paper, we present the Parallel Quantum Rapidly-Exploring Random Tree (Pq-RRT) algorithm, a parallel version of the Quantum Rapidly-Exploring Random Trees (q-RRT) algorithm. Parallel Quantum RRT is a parallel quantum algorithm formulation of a sampling-based motion planner that uses Quantum Amplitude Amplification to search databases of reachable states for addition to a tree. In this work we investigate how parallel quantum devices can more efficiently search a database, as the quantum measurement process involves the collapse of the superposition to a base state, erasing probability information and therefore the ability to efficiently find multiple solutions. Pq-RRT uses a manager/parallel-quantum-workers formulation, inspired by traditional parallel motion planning, to perform simultaneous quantum searches of a feasible state database. We present symbolic runtime comparisons between parallel architectures, then results regarding likelihoods of multiple parallel units finding any and all solutions contained with a shared database, with and without reachability errors, allowing efficiency predictions to be made. We offer simulations in dense obstacle environments showing efficiency, density/heatmap, and speed comparisons for Pq-RRT against q-RRT, classical RRT, and classical parallel RRT. We then present Quantum Database Annealing, a database construction strategy that uses a temperature construct to define database creation over time for balancing exploration and exploitation. |
| first_indexed | 2024-04-24T13:14:08Z |
| format | Article |
| id | doaj.art-96d4b67300284a86939947a9ee041c5f |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-04-24T13:14:08Z |
| publishDate | 2024-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-96d4b67300284a86939947a9ee041c5f2024-04-04T23:00:45ZengIEEEIEEE Access2169-35362024-01-0112471734718910.1109/ACCESS.2024.338331310485279Parallel Quantum Rapidly-Exploring Random TreesPaul Lathrop0https://orcid.org/0000-0002-6374-7510Beth Boardman1https://orcid.org/0000-0001-8152-5578Sonia Martinez2https://orcid.org/0000-0001-6756-1484Department of Mechanical and Aerospace Engineering, University of California at San Diego, San Diego, CA, USALos Alamos National Laboratory, Los Alamos, NM, USADepartment of Mechanical and Aerospace Engineering, University of California at San Diego, San Diego, CA, USAIn this paper, we present the Parallel Quantum Rapidly-Exploring Random Tree (Pq-RRT) algorithm, a parallel version of the Quantum Rapidly-Exploring Random Trees (q-RRT) algorithm. Parallel Quantum RRT is a parallel quantum algorithm formulation of a sampling-based motion planner that uses Quantum Amplitude Amplification to search databases of reachable states for addition to a tree. In this work we investigate how parallel quantum devices can more efficiently search a database, as the quantum measurement process involves the collapse of the superposition to a base state, erasing probability information and therefore the ability to efficiently find multiple solutions. Pq-RRT uses a manager/parallel-quantum-workers formulation, inspired by traditional parallel motion planning, to perform simultaneous quantum searches of a feasible state database. We present symbolic runtime comparisons between parallel architectures, then results regarding likelihoods of multiple parallel units finding any and all solutions contained with a shared database, with and without reachability errors, allowing efficiency predictions to be made. We offer simulations in dense obstacle environments showing efficiency, density/heatmap, and speed comparisons for Pq-RRT against q-RRT, classical RRT, and classical parallel RRT. We then present Quantum Database Annealing, a database construction strategy that uses a temperature construct to define database creation over time for balancing exploration and exploitation.https://ieeexplore.ieee.org/document/10485279/Sampling-based motion planningquantum computingparallel computing |
| spellingShingle | Paul Lathrop Beth Boardman Sonia Martinez Parallel Quantum Rapidly-Exploring Random Trees IEEE Access Sampling-based motion planning quantum computing parallel computing |
| title | Parallel Quantum Rapidly-Exploring Random Trees |
| title_full | Parallel Quantum Rapidly-Exploring Random Trees |
| title_fullStr | Parallel Quantum Rapidly-Exploring Random Trees |
| title_full_unstemmed | Parallel Quantum Rapidly-Exploring Random Trees |
| title_short | Parallel Quantum Rapidly-Exploring Random Trees |
| title_sort | parallel quantum rapidly exploring random trees |
| topic | Sampling-based motion planning quantum computing parallel computing |
| url | https://ieeexplore.ieee.org/document/10485279/ |
| work_keys_str_mv | AT paullathrop parallelquantumrapidlyexploringrandomtrees AT bethboardman parallelquantumrapidlyexploringrandomtrees AT soniamartinez parallelquantumrapidlyexploringrandomtrees |