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