Алгоритмы детерминированного поиска, часть 1

Обучение решению задач планирования ИИ с помощью алгоритмов детерминированного поиска

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

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

В качестве примера мы будем использовать игру Pacman. Подробности игрового процесса и другую информацию можно прочитать по ссылке. Короче говоря, миссия Pacman состоит в том, чтобы съесть все маленькие точки (еду), избегая призраков.

Если Пакман встречает призрака, он проигрывает. Он выигрывает после того, как съел все продукты.

Большие точки - это капсулы, которые, когда Пакман съедает их, дают Пакману временную силу поедать призраков.

Вы можете поискать в Github реализацию игрового движка Pacman, написанную на Python.

Мировое представительство Pacman

Чтобы решить проблемы планирования в Pacman, сначала нам нужно представить, как выглядит Pacman World. Ниже приведены все объекты в Pacman World:

1. Пакман
2. Призраки
3. Еда
4. Капсулы
5. Стены

Стены жесткие, положение и количество стен фиксированы. Продукты и Капсулы фиксируются в позициях, но их количество может уменьшаться.

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

Мы можем написать Pacman World, как показано во фрагменте кода выше. Вы можете видеть, что у нас есть все объекты, реализованные в нашем классе вместе с их геттерами.

Самое важное — это реализация операторов равенства (== и !=), которые будут часто использоваться алгоритмами для сравнения состояний мира.

Шаблоны действий и предиктор состояния

Следующий бит, который нам нужен, — это шаблон действия и предиктор его состояния. Есть 4 действия, которые может выполнять Пакман, а именно:

1. Иди вверх (на север)
2. Спуститься (на юг)
3. Идите налево (запад)
4. Идите направо (восток)

Реализация шаблона действия выглядит так:

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

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

for action in actions:
 if action.pre(pacman_world):
  predicted_pacman_world = action.eff()

Предпосылки всех простых действий, которые у нас есть:

1. действие законно (не двигаться к стене)
2. не встретит призрака

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

Проблема планирования

Мы рассмотрим один пример задачи планирования, начнем с простого.

Из этого начального состояния с 4 едой в углу и без привидений.

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

Алгоритмы

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

Поиск в ширину

Мы реализуем BFS как экземпляр алгоритма детерминированного поиска с выбором узлов и отсечением узлов следующим образом:

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

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

• Время планирования: 185 секунд

Поиск в глубину

1. Выбор узла
   Выберите узел с наибольшей длиной
2. Сокращение
   Проверка цикла

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

• Время планирования: 37 секунд

Скалолазание

1. Node Selection
   Выберите узел, который минимизирует эвристику, для нашей реализации это просто любые узлы, потому что мы не реализовали эвристическую функцию
2. Сокращение
   Очистить границу, чтобы мы следовали только текущему пути

Как мы видим в процессе обрезки, нет гарантии, что у нас будет решение. Этот алгоритм не решает нашу задачу планирования.

Единая стоимость поиска

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

Этот алгоритм дает нам оптимальное решение и более короткое время планирования по сравнению с BFS.

• Время планирования: 106 секунд

A*

1. Выбор узла
   Выберите узел, минимизирующий f(v) = стоимость + эвристика. Для нашей текущей реализации это будет то же самое, что и поиск по единой стоимости, потому что мы не реализовали эвристику.
2. Сокращение
   Удаление повторяющихся путей с более высокой стоимостью

Из-за процесса сокращения время планирования меньше, чем при поиске по единой стоимости. Результат оптимальный.

• Время планирования: 24 секунды

Ветви и границы в глубину (DFSBB)

Этот алгоритм оценивает все возможные пути в DFS и выбирает лучший. Однако для нашей задачи планирования этот алгоритм выполняется слишком долго. На этот раз мы пропустим этот алгоритм.

Жадный поиск по первому наилучшему (GBFS)

1. Выбор узла
   Выберите узел, минимизирующий эвристику.
2. Сокращение
   То же, что и A*

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

• Время планирования: 51 секунда

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