- PVSM.RU - https://www.pvsm.ru -
Как вы думаете, что машины с искусственным интеллектом сегодня уже умеют делать, а что нет?
На фото робот, умеющий складывать полотенца.
В дистанционном курсе CS188.1x Artificial Intelligence [1] от Калифорнийского университета в Беркли профессор Dan Klein [2] приводит список некоторых задач в области искусственного интеллекта. Часть из них уже решены (полностью или частично), а другая часть — еще нет. Курс посвящен алгоритмам ИИ, на которых базируются многие современные интеллектуальные системы. Хочется вкратце поделиться тем, с чего он начинается и подробней рассказать про первое практическое задание.
Первые две недели были посвящены:
(Для справки ссылки на Википедию: неинформированный метод поиска [7] — поиск в глубину [8], поиск в ширину [9], алгоритм Дейкстры [10], информированный метод поиска [11] — A* [12]).
В качестве обзора достижений в области искусственного интеллекта профессор Dan Klein составил следующий список того, что ИИ уже умеет, а что еще нет. Каждый год он отмечает, какие задачи переходят из категории "нет" в категорию "под вопросом", а какие из категории "под вопросом" в категорию "да":
На третей неделе был практический проект. В нем требовалось реализовать все упомянутые в лекциях алгоритмы. В частности, поиск пути в лабиринте с различными условиями в мире Pacman'а.
Исходники заданий на Python (zip-архив [14]) можно скачать с официального сайта курса [15], где есть весь материал: видеолекции, презентации, описания заданий.
Далее я переведу текст первого задания и опишу, что нужно запустить, чтобы проверить решение. Для выполнения заданий на вашем компьютере должен быть установлен Python, например, в сборке Anaconda [16].
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, остальные получается из него относительно просто.
Для справки, общий алгоритм поиска на псевдокоде из лекций заключается в следующем:
Описание терминов можно найти в лекциях [5] или вики [8].
Важное примечание 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 в руководстве [3] к курсу.
По началу может показаться, что окружающего кода слишком много и в нем трудно разобраться, но это быстро проходит. Весь код отлично задокументирован, так что вы никогда не потеряетесь.
Для тех, кто особо хочет поломать голову, самые сложные задания — №6 [17] и №8 [18].
Я старался излагать коротко, поэтому рекомендую посмотреть лекции [19] с сайта курса. Там же вы найдете много других практических тем и заданий.
На Хабре есть еще несколько статей об этом курсе. Раз [20] и два [21], а из третьей [22] я о нем и узнал.
Желаю удачи вашему Pacman!
Автор: e777
Источник [23]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/python/88332
Ссылки в тексте:
[1] CS188.1x Artificial Intelligence: https://www.edx.org/course/artificial-intelligence-uc-berkeleyx-cs188-1x-0
[2] Dan Klein: http://www.cs.berkeley.edu/~klein/
[3] Введению: http://ai.berkeley.edu/tutorial.html
[4] видео: https://www.youtube.com/watch?v=tONNlv6osG4
[5] видео: https://www.youtube.com/watch?feature=player_embedded&v=afwPe_OqPX0
[6] видео: https://www.youtube.com/watch?feature=player_embedded&v=OGcG4jSKOVA
[7] неинформированный метод поиска: https://ru.wikipedia.org/wiki/%D0%9D%D0%B5%D0%B8%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0
[8] поиск в глубину: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D0%B3%D0%BB%D1%83%D0%B1%D0%B8%D0%BD%D1%83
[9] поиск в ширину: https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B8%D1%81%D0%BA_%D0%B2_%D1%88%D0%B8%D1%80%D0%B8%D0%BD%D1%83
[10] алгоритм Дейкстры: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B
[11] информированный метод поиска: https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B8%D1%80%D0%BE%D0%B2%D0%B0%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0
[12] A*: https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0_A*
[13] складывать белье: http://www.youtube.com/watch?v=gy5g33S0Gzo
[14] zip-архив: https://s3-us-west-2.amazonaws.com/cs188websitecontent/projects/release/search/v1/001/search.zip
[15] курса: http://ai.berkeley.edu/home.html
[16] Anaconda: https://store.continuum.io/cshop/anaconda/
[17] №6: http://ai.berkeley.edu/search.html#Q6
[18] №8: http://ai.berkeley.edu/search.html#Q8
[19] лекции: http://ai.berkeley.edu/lecture_videos.html
[20] Раз: http://habrahabr.ru/post/159433/
[21] два: http://megamozg.ru/post/7378/
[22] третьей: http://habrahabr.ru/post/250557/
[23] Источник: http://habrahabr.ru/post/255285/
Нажмите здесь для печати.