Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів
The trajectory planning problem in a state space with obstacles and feasibility constraints has been studied. The rapidly exploring random tree method has been considered, in which each iteration has performed random sampling, selection of the nearest tree vertex, construction of a candidate extensi...
Збережено в:
| Дата: | 2026 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
Kamianets-Podilskyi National Ivan Ohiienko University
2026
|
| Онлайн доступ: | https://mcm-tech.kpnu.edu.ua/article/view/353085 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Mathematical and computer modelling. Series: Technical sciences |
Репозитарії
Mathematical and computer modelling. Series: Technical sciences| _version_ | 1865214124723535872 |
|---|---|
| author | Гентош, Леся |
| author_facet | Гентош, Леся |
| author_sort | Гентош, Леся |
| baseUrl_str | http://mcm-tech.kpnu.edu.ua/index.php/2308-5916/oai |
| collection | OJS |
| datestamp_date | 2026-05-12T19:50:46Z |
| description | The trajectory planning problem in a state space with obstacles and feasibility constraints has been studied. The rapidly exploring random tree method has been considered, in which each iteration has performed random sampling, selection of the nearest tree vertex, construction of a candidate extension, feasibility checking, and insertion of a new vertex into the tree. In parallel implementations on a graphics processing unit, nearest-vertex selection has become the latency-limiting stage because exhaustive distance evaluation has been followed by a global minimum reduction that has required multi-stage synchronization and frequent access to global memory, resulting in a large synchronization-induced hidden time constant. An improved parallel planning method has been proposed that has combined batch-based macro-steps for tree expansion with replacement of the standard nearest-vertex kernel by an exact sorting-based nearest-neighbor search optimized for a graphics processing unit. The batch organization has overlapped independent candidate generation and feasibility checks and has applied a coordinated tree update after all subtasks have completed, while the sorting-based search has ordered vertices by projections onto a leading direction and has performed guaranteed candidate-set shrinking so that exact distance evaluation has been executed only for a small subset. Numerical experiments on the nearest-vertex stage have confirmed a pronounced reduction of the normalized hidden constant, and an end-to-end analysis based on Amdahl’s law has indicated increasing overall speedup as nearest-vertex selection has become dominant, particularly for large trees and higher-dimensional representations. Additional end-to-end tests in two-dimensional environments of size 100×100 and 200×200 with varying obstacle counts have demonstrated consistent runtime improvements, with the relative benefit tending to grow for more cluttered scenes. |
| doi_str_mv | 10.32626/2308-5916.2026-29.39-48 |
| first_indexed | 2026-05-15T01:00:05Z |
| format | Article |
| id | mcmtechkpnueduua-article-353085 |
| institution | Mathematical and computer modelling. Series: Technical sciences |
| keywords_txt_mv | keywords |
| language | English |
| last_indexed | 2026-05-15T01:00:05Z |
| publishDate | 2026 |
| publisher | Kamianets-Podilskyi National Ivan Ohiienko University |
| record_format | ojs |
| spelling | mcmtechkpnueduua-article-3530852026-05-12T19:50:46Z A Parallel Trajectory Planning Method in the State Space with Exact Sorting-Based Neighbor Search Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів Гентош, Леся The trajectory planning problem in a state space with obstacles and feasibility constraints has been studied. The rapidly exploring random tree method has been considered, in which each iteration has performed random sampling, selection of the nearest tree vertex, construction of a candidate extension, feasibility checking, and insertion of a new vertex into the tree. In parallel implementations on a graphics processing unit, nearest-vertex selection has become the latency-limiting stage because exhaustive distance evaluation has been followed by a global minimum reduction that has required multi-stage synchronization and frequent access to global memory, resulting in a large synchronization-induced hidden time constant. An improved parallel planning method has been proposed that has combined batch-based macro-steps for tree expansion with replacement of the standard nearest-vertex kernel by an exact sorting-based nearest-neighbor search optimized for a graphics processing unit. The batch organization has overlapped independent candidate generation and feasibility checks and has applied a coordinated tree update after all subtasks have completed, while the sorting-based search has ordered vertices by projections onto a leading direction and has performed guaranteed candidate-set shrinking so that exact distance evaluation has been executed only for a small subset. Numerical experiments on the nearest-vertex stage have confirmed a pronounced reduction of the normalized hidden constant, and an end-to-end analysis based on Amdahl’s law has indicated increasing overall speedup as nearest-vertex selection has become dominant, particularly for large trees and higher-dimensional representations. Additional end-to-end tests in two-dimensional environments of size 100×100 and 200×200 with varying obstacle counts have demonstrated consistent runtime improvements, with the relative benefit tending to grow for more cluttered scenes. Досліджено задачу планування траєкторій у просторі станів з перешкодами та обмеженнями на допустимість переходів. Розглянуто метод дерева швидкого випадкового пошуку, у якому на кожній ітерації виконуються формування випадкового зразка, вибір найближчого вузла дерева, побудова кандидатного розширення, перевірка допустимості та приєднання нового вузла до дерева. Показано, що у паралельних реалізаціях із використанням графічного процесора операція вибору найближчого вузла стає обмежувальною за затримкою, оскільки після повного перебору відстаней необхідне глобальне зведення до мінімуму з багатоетапною синхронізацією та частими зверненнями до глобальної пам’яті, що формує значну синхронізаційно зумовлену приховану константу часу. Запропоновано удосконалений паралельний метод планування, який поєднує пакетну організацію макрокроків розширення дерева із заміною стандартного ядра визначення найближчого вузла на впорядкований точний пошук найближчих сусідів, оптимізований для графічного процесора. Пакетування забезпечує накладання незалежних операцій формування кандидатів і перевірок допустимості та узгоджене оновлення дерева після завершення всіх підзадач, тоді як впорядкований пошук виконує впорядкування вузлів за проєкціями на провідний напрямок і гарантоване звуження множини кандидатів, тому точний мінімум відстані обчислюється лише для невеликої підмножини. Чисельні експерименти на етапі визначення найближчого вузла підтвердили істотне зменшення нормованої прихованої константи, а аналітична оцінка наскрізного прискорення показала зростання виграшу за умов домінування цієї операції, що є характерним для великих дерев і високорозмірних подань. Додаткові наскрізні тести у двовимірних середовищах розміром 100×100 і 200×200 з різною кількістю перешкод продемонстрували стабільне скорочення часу виконання, причому відносний виграш, як правило, є більшим для більш захаращених конфігурацій. Kamianets-Podilskyi National Ivan Ohiienko University 2026-05-15 Article Article Рецензована Стаття application/pdf https://mcm-tech.kpnu.edu.ua/article/view/353085 10.32626/2308-5916.2026-29.39-48 Mathematical and computer modelling. Series: Technical sciences; 2026: Mathematical and computer modelling. Series: Technical sciences. Issue 29; 39-48 Математичне та комп'ютерне моделювання. Серія: Технічні науки ; 2026: Математичне та комп'ютерне моделювання. Серія: Технічні науки. Випуск 29; 39-48 2308-5916 10.32626/2308-5916.2026-29 en https://mcm-tech.kpnu.edu.ua/article/view/353085/346518 Авторське право (c) 2026 Леся Гентош https://creativecommons.org/licenses/by-nc-nd/4.0 |
| spellingShingle | Гентош, Леся Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| title | Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| title_alt | A Parallel Trajectory Planning Method in the State Space with Exact Sorting-Based Neighbor Search |
| title_full | Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| title_fullStr | Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| title_full_unstemmed | Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| title_short | Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| title_sort | паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів |
| url | https://mcm-tech.kpnu.edu.ua/article/view/353085 |
| work_keys_str_mv | AT gentošlesâ aparalleltrajectoryplanningmethodinthestatespacewithexactsortingbasedneighborsearch AT gentošlesâ paralelʹnijmetodplanuvannâtraêktoríjuprostorístanívízvporâdkovanimtočnimpošukomsusídív AT gentošlesâ paralleltrajectoryplanningmethodinthestatespacewithexactsortingbasedneighborsearch |