تقرير
Parallel Quantum Rapidly-Exploring Random Trees
العنوان: | Parallel Quantum Rapidly-Exploring Random Trees |
---|---|
المؤلفون: | Lathrop, Paul, Boardman, Beth, Martínez, Sonia |
سنة النشر: | 2023 |
المجموعة: | Computer Science Quantum Physics |
مصطلحات موضوعية: | Quantum Physics, Electrical Engineering and Systems Science - Systems and Control, 68W20 |
الوصف: | 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 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 for Pq-RRT and q-RRT that uses a temperature construct to define database creation over time for balancing exploration and exploitation. Comment: 14 pages, 15 figures |
نوع الوثيقة: | Working Paper |
URL الوصول: | http://arxiv.org/abs/2310.15303 |
رقم الأكسشن: | edsarx.2310.15303 |
قاعدة البيانات: | arXiv |
الوصف غير متاح. |