ИССЛЕДОВАНИЕ МЕТОДОВ ПЛАНИРОВАНИЯ ДВИЖЕНИЯ В ДВУМЕРНЫХ КАРТОГРАФИРОВАННЫХ СРЕДАХ
Аннотация
В статье исследуются задача планирования движения в двумерных картогра-фированных средах. Проводится обзор и анализ известных алгоритмов планирова-ния, базирующихся на диаграммах Вороного, вероятностной дорожной карте, быстро растущих случайных деревьев, алгоритмах Дейкстры, А*, D* и их модифи-кациях, искусственных потенциальных полях и интеллектуальных эвристиках. На основе проведенного анализа делается вывод о том, что классические методы в динамических средах требуют значительных затрат по времени расчетов и объ-ему используемой памяти. Делается вывод об актуальности разработки алгорит-мов, повышающих эффективность известных методов планирования.
В этой связи данная статья посвящена разработке модифицированного алго-ритма быстро растущих случайных деревьев и исследованию его эффективности по сравнению с известными методами. В статье представлен модифицированный алгоритм быстро растущих случайных деревьев, отличающийся тем, что при про-верке наличия пути в новый потенциальный узел графа проверяется путь в некото-рую область возле указанного узла. Это позволяет снизить количество узлов в строящемся дереве. Разработанный алгоритм вначале сравнивается с традицион-ным алгоритмом быстрорастущих случайных деревьев. Сравнение производится по времени расчета траектории, объему требуемой памяти, длине пути и про-центу ситуаций, в которых успешно найдена траектория в целевую точку. Далее осуществляется сравнение разработанного алгоритма с алгоритмами планирова-ния других классов. При исследовании используются репрезентативные выборки численных экспериментов и различные среды, отличающиеся плотностью распо-ложения препятствий и наличием лабиринтов. Также проводится исследование ал-горитмов планирования с использованием результатов экспериментов на наземном колесном роботе.
По результатам численных и реальных экспериментов делаются выводы о преимуществах и недостатках разработанного алгоритма планирования движе-ния и о целесообразности его применения в различных средах.
Планирование движения; двумерная среда, метод случайных деревьев, опти-мизация алгоритмов планирования, сравнительный анализ.
