Оптимизация алгоритма планирования пути A-star

Введение. Автономные мобильные роботы должны уметь самостоятельно планировать глобальную и локальную траектории своего движения. Алгоритм планирования пути A-star позволяет вычислить кратчайший путь между начальной и конечной точками на карте местности с известными статичными препятствиями. В реальных условиях при введении дополнительной информации о карте местности (труднопроходимые или опасные участки, участки с ограничением скорости) и учете затрат на их преодоление алгоритм может приводить к неоптимальному для данных условий решению задачи. Цель исследования. Рассмотреть варианты оптимизации алгоритма планирования пути A-star для применения в различных условиях, имеющих ограничения по количеству поворотов, привязку к критическим точкам на карте местности, труднопроходимые и опасные участки. Оценить качество проведенной оптимизации. Материалы и методы. Исследования проводятся путем компьютерного моделирования алгоритма A-star и вариантов его оптимизации в среде MATLAB. Критериями оценки качества оптимизации алгоритма являются скорость расчета пути и его оптимальность относительно выбранных параметров. Результаты. Приводятся результаты расчета пути, выполненные с помощью алгоритма A-star до и после оптимизации. В обоих случаях оцениваются и сравниваются: время расчета, количество проанализированных полигонов, число поворотов и длина пути. Заключение. В большинстве случаях в результате оптимизации алгоритма увеличивается длина пути и время расчета, но незначительно. При этом новый путь соответствует заданным условиям, является кратчайшим в этих условиях и, следовательно, оптимальным. Предложенные в статье варианты оптимизации позволяют вычислить путь с учетом дополнительной информации, оценить длину пути и скорость расчета. На основе этих оценок можно выбрать метод планирования пути, подходящий для отдельного сценария.