Авторы:  (1) Айя Херрур, факультет информационной инженерии и компьютерных наук Университета Тренто;  (2) Марко Роболь, факультет информационной инженерии и компьютерных наук Университета Тренто;  (3) Марко Ровери, факультет информационной инженерии и компьютерных наук Университета Тренто;  (4) Паоло Джорджини, факультет информационной инженерии и компьютерных наук Университета Тренто.  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 раз на каждой сетке, чтобы учесть случайность и обеспечить надежность результатов.  Этот документ   под лицензией CC 4.0. доступен на arxiv

Part of HackerNoon's growing list of open-source research papers, promoting free access to academic material.

EScholar Technologies

EScholar

Этот звук создан на языке оригинала истории!

Слишком долго; Читать

Boost your HackerNoon story @ $159.99! 🚀

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

About Author

КОММЕНТАРИИ

БИРКИ

ЭТА СТАТЬЯ БЫЛА ПРЕДСТАВЛЕНА В

Related Stories

Краткое введение в теорию мозга Больцмана

Модель Bitcoin UTXO, обеспечивающая работу уникальной экосистемы

От форумов до лент новостей: как алгоритмы социальных сетей формируют цифровое взаимодействие

Плавание по водам: разработка RAG-приложений промышленного уровня с использованием озер данных

Краткое введение в теорию мозга Больцмана

Модель Bitcoin UTXO, обеспечивающая работу уникальной экосистемы

От форумов до лент новостей: как алгоритмы социальных сетей формируют цифровое взаимодействие

Плавание по водам: разработка RAG-приложений промышленного уровня с использованием озер данных

Light-Mode

Classic

Newspaper

Dark-Mode

Neon Noir

Minty

HN StartUps