Метрики производительности алгоритмов эвристического поиска в грид-средах

3 Экспериментальная среда и показатели производительности

Алгоритмы эвристического поиска играют важную роль в таких областях, как роботизированный поиск пути, поскольку они определяют оптимальный путь с учетом начальной и целевой позиции. Среды на основе сетки обычно используются для представления сценариев реальной среды, где эти алгоритмы могут быть реализованы, например, в автономной навигации и робототехнике [6]. В этом исследовании мы всесторонне анализируем хорошо известные алгоритмы эвристического поиска, а именно D*, D* Lite, LPA*, LRTA*, RTAA* и ARA* в различных грид-средах. Мы используем эвристику евклидова расстояния, чтобы направлять поиск алгоритмов и оценивать влияние некоторых характеристик сетки, таких как плотность препятствий и размер сетки, на производительность алгоритмов.

В нашем исследовании мы используем среды на основе сетки из-за их простоты и легкости управления, а также из-за того, что они обычно используются в задачах планирования пути в исследовательском сообществе. Сетки состоят из белых ячеек, обозначающих проходимые состояния, тогда как черные представляют собой непреодолимые препятствия. Агент в нашей модели может двигаться в восьми направлениях со стоимостью, равной 1 для горизонтальных и вертикальных движений и √ 2 для диагональных движений. Мы использовали два типа сеточных сред: случайно сгенерированные сеточные среды и персонализированные сеточные среды.

Случайно генерируемые среды на основе сеток. Сетки характеризуются тремя параметрами:

размер сетки (NxN), плотность препятствий и расстояние между начальным и целевым состояниями. Чтобы исследовать влияние каждого параметра на производительность алгоритмов поиска, мы варьировали каждый параметр независимо, сохраняя при этом другие параметры постоянными. Вариации включали изменение размера сетки, изменение расстояния от старта до ворот и изменение плотности препятствий. Для каждой сетки в варианте мы сгенерировали десять случайных экземпляров одних и тех же параметров сетки (например, сетка с плотностью препятствий 0,25, размером 300x300 и расстоянием от начала до цели 140 имеет десять экземпляров, которые были сгенерированы случайным образом).

Персонализированная сетка: предназначена для моделирования более конкретных сценариев. Эти сетки имеют фиксированный размер (71x31 единиц) и фиксированное положение как для начального, так и для целевого состояния, и они были разделены на две части в зависимости от конфигурации препятствий:

• Конфигурация горизонтальных стен: для этих экспериментов мы добавляем горизонтальные стены шириной в половину сетки каждые 10 единиц длины сетки. Мы добавили стены в двух ориентациях: один раз слева направо и один раз справа налево в вновь созданной сетке.

• Конфигурация длины горизонтальной стены. Здесь мы добавляем все возможные стены, которые можно разместить внутри.

длину сетки, и каждый раз, когда мы генерируем новую сетку, мы увеличиваем длину всех стен на 2 единицы.

Мы использовали эти две разные среды для проведения тщательного анализа, стремясь выявить нюансы производительности алгоритма поиска при наличии двух различных препятствующих сценариев. В первом случае препятствия разбросаны по сетке случайным образом, тогда как во втором конструкции, похожие на стены, выглядят как масса связанных препятствий.

Для оценки производительности различных поисковых алгоритмов, использованных в экспериментах, мы выбрали следующие метрики:

• Стоимость пути: метрика измеряет длину пути или количество выполненных действий от начала до целевого состояния. Это указывает на качество решения.

• Потребление памяти: измеряет объем памяти, необходимый алгоритму для поиска решения. Важно проверить масштабируемость алгоритма, она измеряется в (КБ).

• Время решения: представляет общее время, необходимое алгоритму для поиска решения в (мс), измеряемое в миллисекундах (мс).

Мы проводили эксперименты на 27-ядерном процессоре Intel i9 с тактовой частотой 3,30 ГГц, оснащенном 250 ГБ оперативной памяти и работающем под управлением Ubuntu Linux 22.04. Использование следующих настроек: Все алгоритмы использовали евклидово расстояние в качестве эвристической функции. Для LRTA* и RTAA* мы устанавливаем количество израсходованных узлов равным 250 для каждой итерации. Алгоритм ARA* был запущен с весом эвристики 2,5. Мы запускали каждый алгоритм по 100 раз на каждой сетке, чтобы учесть случайность и обеспечить надежность результатов.