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

Question

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

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

Answer 1

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

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

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

---

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

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

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

---

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

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

Answer 2

Часть этого будет указывать пути, например, с алгоритмом A * .

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

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

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

Answer 3

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

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

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

Answer 4

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

Answer 5

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

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

Answer 6

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

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

Answer 7

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

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

Answer 8

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