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

Анотація

Досліджено задачу планування траєкторій у просторі станів з перешкодами та обмеженнями на допустимість переходів. Розглянуто метод дерева швидкого випадкового пошуку, у якому на кожній ітерації виконуються формування випадкового зразка, вибір найближчого вузла дерева, побудова кандидатного розширення, перевірка допустимості та приєднання нового вузла до дерева. Показано, що у паралельних реалізаціях із використанням графічного процесора операція вибору найближчого вузла стає обмежувальною за затримкою, оскільки після повного перебору відстаней необхідне глобальне зведення до мінімуму з багатоетапною синхронізацією та частими зверненнями до глобальної пам’яті, що формує значну синхронізаційно зумовлену приховану константу часу. Запропоновано удосконалений паралельний метод планування, який поєднує пакетну організацію макрокроків розширення дерева із заміною стандартного ядра визначення найближчого вузла на впорядкований точний пошук найближчих сусідів, оптимізований для графічного процесора. Пакетування забезпечує накладання незалежних операцій формування кандидатів і перевірок допустимості та узгоджене оновлення дерева після завершення всіх підзадач, тоді як впорядкований пошук виконує впорядкування вузлів за проєкціями на провідний напрямок і гарантоване звуження множини кандидатів, тому точний мінімум відстані обчислюється лише для невеликої підмножини. Чисельні експерименти на етапі визначення найближчого вузла підтвердили істотне зменшення нормованої прихованої константи, а аналітична оцінка наскрізного прискорення показала зростання виграшу за умов домінування цієї операції, що є характерним для великих дерев і високорозмірних подань. Додаткові наскрізні тести у двовимірних середовищах розміром 100×100 і 200×200 з різною кількістю перешкод продемонстрували стабільне скорочення часу виконання, причому відносний виграш, як правило, є більшим для більш захаращених конфігурацій.