Алгоритм исследования роботов

Я пытаюсь разработать алгоритм для робота, пытающегося найти флаг (расположенный в неизвестном месте), который находится в мире, содержащем препятствия. Задача робота - захватить флаг и привести его к своей домашней базе (которая представляет его исходную позицию). На каждом шагу робот видит только ограниченную окрестность (он не знает, как мир выглядит заранее), но у него есть неограниченная память для хранения уже посещенных ячеек.

Я ищу любые предложения о том, как это сделать эффективным образом. Особенно первая часть; а именно, добраться до флага.

Ответ 1

Простой поиск по ширине и глубине Первый поиск будет работать, хотя и медленно. Обязательно запретите боту проверять пути, которые имеют один и тот же квадрат несколько раз, поскольку это приведет к тому, что эти алгоритмы будут работать намного дольше в стандартных случаях и неограниченно в случае невозможности достижения флага.

A * - более элегантный подход, особенно если вы знаете расположение флага относительно себя. Wikipedia, как обычно, делает достойную работу с объяснением этого. Классической эвристикой, которую следует использовать, является дальность комплектования (количество ходов без препятствий) до места назначения.

Эти алгоритмы полезны для обратного пути - не столько часть "найти флаг".

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

Этот класс должен будет иметь возможность получить список смежных квадратов и знать, если он проходит.

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

Edit: Что касается привязки неизвестной области к неизвестному объекту...

Вы можете использовать что-то вроде алгоритм залога, пока не найдете границы своего пространства, записывая всю информацию по мере продвижения. Затем взгляните на все невидимые квадраты, используя ваш любимый алгоритм дрейфа/траектории. Если в какой-то момент вы видите флаг, остановите свое действие и используйте свой любимый алгоритм поиска пути, чтобы вернуться домой.

Ответ 2

Отчасти это будет путь, например, с помощью алгоритм A *.

Часть его будет изучаться. Любая ячейка с неизвестным соседом стоит изучить. Лучшими клетками для изучения являются те, которые ближе всего к роботу и с самым большим неисследованным районом.

Если робот видит стены, некоторые кандидаты на исследования могут быть недоступны, и исследование может потребоваться, даже если флаг уже виден.

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

Ответ 3

С помощью простого DFS поиск по крайней мере вы найдете флаг:)

Ответ 4

Ну, есть две части. 1) Поиск флага 2) Возвращение домой

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

Как только флаг обнаружен, вы можете либо вернуться туда же, либо найти более прямой маршрут. Если это более прямой маршрут, вам нужно будет использовать карту, которую вы создали, чтобы найти прямой маршрут.

Ответ 5

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

Ответ 6

Если вы встретили препятствие, вы можете пойти, чтобы определить его точные размеры, и после его измерения вернитесь к предыдущему курсу. Без препятствий в дальности видимости вы можете попытаться просто направиться в направлении ближайшей непроверенной области.

Возможно, это не самый быстрый способ, но, я думаю, это хороший момент для начала.

Ответ 7

Я думаю, что подход будет заключаться в том, чтобы построить график, когда путешествует робот. Будет функция, которая вернет роботу конкретное состояние сетки. Это необходимо, так как робот заранее не узнает состояние сетки.

Вы можете применить эвристику в поиске, так что вероятность достижения флага увеличивается.

Ответ 8

Как уже упоминалось, A * хорошо подходит для глобального планирования, если вы знаете, где вы находитесь и где ваша цель. Но если у вас нет этого глобального знания, существует класс алгоритмов, называемых алгоритмами "ошибок", которые вы должны изучить.

Что касается исследования, если вы хотите, чтобы флаг был самым быстрым, в зависимости от того, какая часть локального соседства может видеть ваш бот, вы должны попытаться не перекрывать эту окрестность. Например, если ваш бот может видеть одну ячейку вокруг него в каждом направлении, вы должны изучить каждую третью колонку. (столбцы 1, 4, 7 и т.д.). Но если бот может видеть только ячейку, в которой он сейчас находится, то самое оптимальное, что вы можете сделать, это не возвращаться к тому, что вы уже посетили.