Как вы думаете, что машины с искусственным интеллектом сегодня уже умеют делать, а что нет?
На фото робот, умеющий складывать полотенца.
В дистанционном курсе 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 SearchAgentpython pacman.py -l mediumMaze -p SearchAgentpython 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!
Автор: e777
