Первые две недели курса CS188.1x Artificial Intelligence или самообучение алгоритмам ИИ

Как вы думаете, что машины с искусственным интеллектом сегодня уже умеют делать, а что нет?


На фото робот, умеющий складывать полотенца.

В дистанционном курсе CS188.1x Artificial Intelligence от Калифорнийского университета в Беркли профессор Dan Klein приводит список некоторых задач в области искусственного интеллекта. Часть из них уже решены (полностью или частично), а другая часть — еще нет. Курс посвящен алгоритмам ИИ, на которых базируются многие современные интеллектуальные системы. Хочется вкратце поделиться тем, с чего он начинается и подробней рассказать про первое практическое задание.

Первые две недели были посвящены:

• Введению в программирование на Python;
• Истории развития и обзору современных достижений в области ИИ (видео);
• Неинформированному методу поиска (видео) — поиск в глубину, поиск в ширину, алгоритм Дейкстры;
• информированному методу поиска (видео) — A*.

(Для справки ссылки на Википедию: неинформированный метод поиска — поиск в глубину, поиск в ширину, алгоритм Дейкстры, информированный метод поиска — A*).

В качестве обзора достижений в области искусственного интеллекта профессор Dan Klein составил следующий список того, что ИИ уже умеет, а что еще нет. Каждый год он отмечает, какие задачи переходят из категории "нет" в категорию "под вопросом", а какие из категории "под вопросом" в категорию "да":

• Хорошо играть в настольный теннис — да;
• Хорошо играть в Jeopardy (Своя игра) — да;
• Безопасно управлять автомобилем по извилистым горным дорогам — да;
• Безопасно управлять автомобилем по Telegraph Avenue (улица) — под вопросом;
• Покупка бакалеи на неделю через интернет — да;
• Покупка бакалеи на неделю в обычном магазине — нет;
• Открывать и доказывать новые математические теоремы — под вопросом;
• Успешно вести диалог с человеком в течении часа — нет;
• Выполнять хирургические операции — под вопросом;
• Убирать посуду и складывать белье — да;
• Переводить разговорный китайский в разговорный английский в реальном времени — да;
• Писать интересные истории — нет.

На третей неделе был практический проект. В нем требовалось реализовать все упомянутые в лекциях алгоритмы. В частности, поиск пути в лабиринте с различными условиями в мире Pacman'а.

Исходники заданий на Python (zip-архив) можно скачать с официального сайта курса, где есть весь материал: видеолекции, презентации, описания заданий.

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

Задача N1. Поиск заданной позиции. Алгоритм поиска в глубину

Pacman живет в мире извилистых коридоров и вкусных круглых точек. И эффективная навигация в этом мире будет его первым шагом к победе.



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

Для начала убедитесь, что класс SearchAgent работает корректно:

python pacman.py -l tinyMaze -p SearchAgent -a fn=tinyMazeSearch

Эта команда говорит SearchAgent использовать tinyMazeSearch в качестве алгоритма поиска, который реализован в search.py. Pacman должен успешно пройти лабиринт.

Для того, чтобы выполнить первое задание нужно дописать только одну функцию depthFirstSearch, которая находится в файле search.py и должна реализовывать алгоритм поиска в глубину (depth-first search или DFS).

Замечание. Алгоритмы — поиск в глубину (DFS), поиск в ширину (BFS), алгоритм Дейкстры (UCS) и А*, очень похожи и отличаются только в некоторых деталях реализации. Таким образом, реализовав DFS, остальные получается из него относительно просто.

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



Описание терминов можно найти в лекциях или вики.

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

Важное примечание 2: Убедитесь, что вы используете структуры данных Stack, Queue и PriorityQueue, реализованные в util.py. Эти реализации имеют особые свойства, которые необходимы для совместимости с autograder.py (см. ниже).

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

Ваш код должен быстро найти решение для:

python pacman.py -l tinyMaze -p SearchAgent

python pacman.py -l mediumMaze -p SearchAgent

python pacman.py -l bigMaze -z .5 -p SearchAgent

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

Подсказка: Если вы используете Stack в вашей реализации DFS, то решение, найденное для mediumMaze, должно иметь длину 130 элементов (при условии, что вы добавляете новые элементы в стек в порядке, предусмотренном getSuccessors. В случае, если добавлять их в обратном порядке, вы получите 246). Является ли найденное решение хотя бы экономичным? Если нет, подумайте о том, что поиск в глубину делает неправильно.

При запуске pacman.py поддерживает несколько входных параметров. Список всех вариантов и их значения можно вызвать командой:

python pacman.py -h

Или посмотреть в файле commands.txt.

Проверка задания

Архив включает в себя скрипт autograder.py, который позволит проверить реализацию всех заданий на вашем компьютере с помощью следующей команды:

python autograder.py

Для более подробной информации о работе autograder.py см. раздел Autograding в руководстве к курсу.

Пару слов напоследок

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

Для тех, кто особо хочет поломать голову, самые сложные задания — №6 и №8.

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

На Хабре есть еще несколько статей об этом курсе. Раз и два, а из третьей я о нем и узнал.

Желаю удачи вашему Pacman!