Паралельний метод планування траєкторій у просторі станів із впорядкованим точним пошуком сусідів

• Datum: 2026
• 1. Verfasser: Гентош, Леся
• Format: Artikel
• Sprache: Englisch
• Veröffentlicht: Kamianets-Podilskyi National Ivan Ohiienko University 2026
• Online Zugang: https://mcm-tech.kpnu.edu.ua/article/view/353085
• Назва журналу: Mathematical and computer modelling. Series: Technical sciences

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.