Реализация алгоритмов поиска пути для агента Pacman: DFS, BFS, Uniform Cost Search и A* для навигации в лабиринте

Описание

Учебно-исследовательский проект на основе классической задачи поиска пути в лабиринте — агент Pacman должен находить оптимальные маршруты к целевой точке и эффективно собирать еду, разбросанную по карте. Задача типичная для курсов искусственного интеллекта: на простой и наглядной среде отработать фундаментальные алгоритмы поиска, которые лежат в основе навигации роботов, маршрутизации в сетях, планирования действий ИИ-агентов и решения комбинаторных задач.
Цель — реализовать и сравнить несколько алгоритмов поиска, понять их сильные и слабые стороны на разных типах задач (поиск одной цели, поиск множества целей, поиск с препятствиями), а также спроектировать эвристические функции для информированного поиска.

Решение

Реализовал четыре фундаментальных алгоритма поиска для агента Pacman:
Поиск в глубину (DFS) — обход графа состояний через стек. Быстро находит хоть какое-то решение, но не гарантирует оптимальности. Хорошо показывает себя на задачах, где важно просто дойти до цели, а не пройти кратчайшим путём.
Поиск в ширину (BFS) — обход через очередь, гарантирует кратчайший путь по количеству шагов. Реализован с отслеживанием посещённых состояний, чтобы избежать зацикливания и экспоненциального взрыва.
Поиск с равномерной стоимостью (UCS) — расширение BFS с учётом стоимости переходов. Использует приоритетную очередь, гарантирует оптимальный путь по суммарной стоимости даже когда разные шаги стоят по-разному (например, разные клетки лабиринта имеют разный вес).
Алгоритм A* — информированный поиск с эвристической функцией. Реализовал несколько эвристик: манхэттенское расстояние для одиночной цели, эвристика на основе MST для задачи обхода всех точек еды. A* комбинирует фактическую стоимость пути и прогноз до цели — за счёт этого исследует меньше состояний, чем UCS, при тех же гарантиях оптимальности.
Общая архитектура: все алгоритмы построены на едином абстрактном интерфейсе задачи поиска (SearchProblem) — состояния, переходы, проверка цели, стоимость действия. Это позволило применять одни и те же алгоритмы к разным задачам: поиск одной точки, поиск всех углов лабиринта, эффективный сбор всей еды.
Дополнительно проработал задачи на проектирование собственных эвристик и доказательство их допустимости (admissibility) и состоятельности (consistency) — без этих свойств A* теряет гарантии оптимальности.

Результат

Рабочая реализация классических алгоритмов поиска с визуализацией работы агента в графической среде Pacman. На наглядных примерах видно, как разные алгоритмы ведут себя на одной и той же задаче — какие исследуют больше состояний, какие находят более короткие пути, как эвристика A* влияет на эффективность.
Проект полезен:
• как демонстрация владения фундаментальными алгоритмами ИИ
• как основа для более сложных задач — мультиагентного поиска, adversarial search (минимакс, альфа-бета отсечение), планирования с неопределённостью
• как учебный материал для понимания, почему один и тот же алгоритм может решать задачи навигации робота, поиска в графе соцсети и планирования логистики
Алгоритмы из этого проекта — это база для любых задач, где нужно искать оптимальное решение в пространстве состояний: от GPS-навигации до планировщиков в игровых ИИ.

Презентация проекта