Решение лабиринтов с помощью методов поиска пути ИИ: A * против Tremaux

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

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

Кстати, если вы хотите сразу перейти к хорошему и просто поиграть с лабиринтами, то перейдите к решателю лабиринтов на javascript. В противном случае читайте дальше.

Существует множество способов прохождения лабиринта и поиска пути. Для нашего робота мы рассмотрим два случая.

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

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

Доступны изображения с высоты птичьего полета

Предполагая, что у робота есть воздушная планировка лабиринта, ИИ может выбрать использование алгоритмов поиска пути A* или Tremaux. Существует множество других доступных алгоритмов лабиринта, но мы обсудим эти два подробно.

Имея макет лабиринта, оба A а алгоритм Тремо обеспечит успешный путь через лабиринт. [А Поиск](http://en.wikipedia.org/wiki/A*_search_algorithm) лучше работает в лабиринтах с неоднородными плитками и препятствиями на путях (такими как большие дорожки для ходьбы, открытые площадки, упавшие камни и т. д.) , в то время как Tremaux лучше работает со сложными лабиринтами «классического» стиля (пиксельные плитки фиксированного размера) с множеством проходов во многих направлениях. Используя любой из алгоритмов, ИИ определит решение и сможет успешно пройти лабиринт.

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

Нет доступных изображений

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

В этом сценарии А поиск будет невозможен, так как для его эвристического расчета требуется знание местоположения выхода. На каждом этапе А вычисляет, какая плитка на пути является следующим лучшим ходом, все ближе и ближе к выходу. Это определяется расчетом на плитке выхода и соседних плитках. Общие эвристики — это манхэттенское расстояние (разница в X + разница в Y до целевой плитки) или диагональное расстояние (максимум разницы в X и разности Y до целевой плитки).

При поиске A* вне изображения робот может выбрать альтернативу, например алгоритм Тремо. Этот метод похож на реальную прогулку по лабиринту. Вы можете отслеживать только ближайшие плитки, видимые вам. Робот начинает двигаться в случайном направлении и продолжает двигаться, пока не упрется в стену. Затем он поворачивает направо, пока не появится путь, по которому можно пройти. Каждый раз, когда алгоритм делает шаг, он помечает плитку как посещенную. Алгоритм всегда пытается сначала посетить непосещенную плитку.Однако, если новые плитки не найдены, он будет возвращаться к посещенной плитке, увеличивая отметку на плитке до 2, пока не найдет непосещенную плитку. Он никогда не будет посещать одну и ту же плитку более двух раз (за исключением того, что алгоритм застрял в тупике, и в этом случае он повторно посетит плитку, на которую уже вернулся, чтобы выйти из ловушки. Решение лабиринта — это все плитки, которые были посещены только один раз.

Печать решения

В алгоритме Тремо путь решения состоит из всех плиток, которые были посещены один раз, как показано ниже:

1
2
3
4
5
6
7
8
9
// Печатаем путь к решению.
за (вар х = ; х < это.ходок.лабиринт.ширина; х++) {
за (вар у = ; у < это.ходок.лабиринт.высота; у++) {
если (это.walker.visited[x][y] == 1) {
это.walker.context.fillStyle = 'красный';
это.walker.context.fillRect(x * 10, г * 10, 10, 10);
}
}
}

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

1
2
3
4
5
6
7
8
9
10
11
12
// Компилируем путь решения.
если (currentNode.x == это.end.x && currentNode.y == это.конец.у) {
пока(текущий родитель) {
рет.толчок (текущий);
текущий = текущий.родительский;
}
}

// Печатаем путь к решению.
за (вар я в это.решение) {
это.context.fillRect(это.решение[i].x * 10, это.solution[i].y * 10, 10, 10);
}

A* Эвристика поиска

Обратите внимание: чтобы ИИ мог использовать поиск A* для поиска пути решения, ему необходимо знать точку выхода. Он использует эти данные в своем эвристическом расчете, как показано ниже (где pos0 — текущая плитка, а pos1 — выходная плитка).

Манхэттен Расстояние

1
2
3
4
5
6
это.манхэттен = функция(поз0, поз1) {
вар д1 = Математика.abs(pos1.x — pos0.x);
вар д2 = Математика.abs(pos1.y — pos0.y);

возвращаться д1 + д2;
}

Диагональное расстояние

1
2
3
4
5
6
это.диагональное расстояние = функция(поз0, поз1) {
вар д1 = Математика.abs(pos1.x — pos0.x);
вар д2 = Математика.abs(pos1.y — pos0.y);

возвращаться (2 * Математика.max(d1, d2));
}

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

Требования к интеллекту

Чтобы найти путь через лабиринт, поиск A* и алгоритм Тремо имеют определенные критерии, которые обычно должны выполняться. Оба алгоритма предполагают, что лабиринт разрешим (т.е. есть вход и выход). Tremaux требует, чтобы каждая плитка на пути была размером в 1 единицу без каких-либо препятствий на пути, кроме стен. То есть лабиринт должен содержать четко очерченные узкие проходы. Тремо не требует знания точки выхода, когда начинает поиск в лабиринте. Поскольку он, по сути, выполняет поиск в глубину, ему просто нужно знать, когда остановиться (т. е. когда посещается плитка выхода).

А поиск имеет тенденцию быть более гибким и обычно может искать вокруг препятствий и путей переменного размера. Однако А имеет другие требования и ограничения. Он должен знать точку выхода, прежде чем начать свои вычисления. Это также требует явного определения эвристики. Движение с буквой А Алгоритм поиска обычно 4- или 8-направленный, включая диагонали. Рассмотрим следующий пример A поиск с использованием только горизонтального и вертикального перемещения по сравнению с включением диагоналей:

A* Поиск — без диагоналей

A* Поиск — с диагональю

Скорость поиска и сложность лабиринта

Хотя оба алгоритма найдут решение для лабиринта, каждый из них работает лучше, в зависимости от характеристик лабиринта. В следующем лабиринте, показанном ниже, Тремо выполняет более прямой поиск, чтобы найти решение (оставляя большую часть карты неисследованной). Поиск A* занимает больше времени, исследуя почти всю карту, чтобы найти решение. Это, скорее всего, связано с направлением туннелей лабиринта, ведущих от точки выхода, и необходимостью высокой степени обратного пути.

A* Поиск Решение сложного лабиринта

Алгоритм Тремо, решающий сложный лабиринт

Попробуй сам

Поэкспериментируйте с различными лабиринтами, используя поисковые алгоритмы Tremaux и A*, или даже создайте свой собственный. Решатель лабиринта JavaScript позволяет выбрать любой алгоритм решения лабиринта и запускает его на выбранной карте. Карты можно создавать «на лету», передавая объект JSON в URL-адресе. Подробности смотрите в инструкциях к демо.

Скачать на GitHub

Как то, что вы видите? Весь исходный код проекта доступен на GitHub. Это включает в себя демонстрационную страницу и динамический выбор лабиринтов.

об авторе

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