Численное моделирование роевого алгоритма планирования пути в двухмерной некартографированной среде

Аннотация

Исследуется эффективность роевых алгоритмов планирования пути в двумерной некартографированной среде. В качестве критериев эффективности используется число итераций в процессе поиска пути и оценка вероятности успешного достижения цели. В ходе исследования изменяется максимальная скорость перемещения роя и максимальное число итераций, в течение которых допускается отсутствие уменьшения расстояния до цели. Предполагается, что каждая частица может определять состояние среды в некоторой локальной области. Под определением состояния имеется в виду определение наличия препятствия в ячейке среды. Для решения проблемы локальных минимумов предлагается вводить виртуальное препятствие в точке локального минимума. Данный подход в целом известен. Новизна этого подхода заключается в том, что решается задача обнаружения локального минимума роем частиц. При одиночном движении обнаружение локального минимума тривиально и сводится к проверке движения к ранее посещенным ячейкам. В групповом случае требуется новое решение задачи обнаружения локального минимума. В данной статье приводится обзор и анализ задачи планирования пути, формулировка проблемы, постановка задачи, математическое описание алгоритмов глобального роевого планирования пути с предложенными модификациями, псевдокоды алгоритмов планирования и результаты численного исследования. В ходе численных исследований определены критерии эффективности планирования пути в среде размером 100100 ячеек со случайно размещаемыми препятствиями.