Лекции по "Системам искусственного интеллекта"

Лекции 

по 

системам 

искусственного  интеллекта

(СИИ) 

Улитина И.А.

2011 год 
 

Содержание:

Лекция 1. Введение в интеллектуальные системы

1.1. Основные понятия и определения

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

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

      Основным  предметом изучения дисциплины являются мыслительные способности человека и способы их реализации техническими средствами.

      Термин  интеллект (intelligence) происходит от латинского intellectus — что означает ум, рассудок, разум; мыслительные способности человека. Соответственно искусственный интеллект (artificial intelligence) — ИИ (AI) обычно толкуется как свойство автоматических систем брать на себя отдельные функции интеллекта человека, например, выбирать и принимать оптимальные решения на основе ранее полученного опыта и рационального анализа внешних воздействий. Искусственный интеллект (ИИ) - это наука о концепциях, позволяющих ВМ делать такие вещи, которые у людей выглядят разумными. Дать определение в обычном смысле этого слова невозможно, потому что интеллект - это сплав многих навыков в области обработки и представления информации.

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

1.2. Область применения

• Доказательства  теорем;
• Игры;
• Распознавание образов;
• Принятие решений;
• Адаптивное программирование;
• Сочинение машинной музыки;
• Обработка данных на естественном языке;
• Обучающиеся сети (нейросети);
• Вербальные концептуальные обучения.

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

     Искусственный интеллект в играх. Многие игры были бы не интересны, если бы их персонажи не обладали определенной интеллектуальностью. В принципе, искусственный интеллект в играх "ничем не хуже" интеллекта в других областях применения. Так что для него подходят все общеизвестные методы реализации ИИ. Но, конечно же, как и для других узкоспециальных задач, для игровой индустрии тоже выполняются следующие свойства:

• Выделились определенные наиболее популярные и простые приемы решения типовых "интеллектуальных" игровых задач.
• Многие задачи решаются вовсе не методами "настоящего" ИИ, а методами традиционной математики-информатики: решение уравнений, перебор, поиск оптимума функций и т.п. А то и вовсе компьютер жульничает: зачем искусственному персонажу "думать", где находится игрок (или, например, какие у того на руках карты), если программе по определению всегда известно точное местоположение последнего (или какие карты ему были розданы)...

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

     Передвижения  монстров.  Преследование  и Уклонение. Самый простой способ преследовать игрока - это двигаться непосредственно к нему, а наиболее простой способ избегать его - двигаться в противоположном направлении. Если на пути движения нет каких-либо препятствий может использоваться предельно простой алгоритм: он лишь сравнивает две позиции (позицию монстра и позицию игрока, например) и возвращает направление движения. Он не учитывает, есть ли что-то на пути, поэтому если между монстром и игроком стоит стена, то монстр будет бесконечно биться в нее головой.

     Патрулирующие монстры. В некоторых играх жанра "Бегай-и-Прыгай" (имеются в виду 2D-аркады типа "Чип и Дейл", "Черный плащ" и т.п.) монстры просто ходят из точки A в точку B, затем к C и так далее; последняя точка опять соединяется с первой. Это не намного сложнее, чем алгоритм преследования, описанный выше, с той лишь разницей, что монстры "преследуют" точки своего маршрута, а не игрока.

     Обход препятствий. Враги, управляемые вышеупомянутым алгоритмом, либо направляются прямо к игроку, либо бегут от него в противоположном направлении. Они не учитывают среду, в которой они движутся, - игнорируя стены, деревья и т.п. Самый простой способ решить эту проблему состоит в том, чтобы в каждом объекте хранить некоторую "информацию обхода". Тогда если монстр подбегает к непроходимому объекту, он мог бы "спрашивать" этот объект, куда двигаться, чтобы обойти его.

     В зависимости от направления, в котором произошло  соприкосновение, каждая поверхность возвращает монстру другую пару значений dx/dy.

     Правила, чтобы выбрать  эти значения, весьма просты:

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

     2. Если к препятствию  прикоснулись в  направлении одной  из координатных  осей, возвращать  информацию обхода от другой оси. Если препятствие имеет информацию обхода (-1, 1) и его касается кто-то, движущийся вдоль оси X, вы возвращаете часть Y информации обхода, в данном случае это значение 1.

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

     Маршрутные  точки, стиль Zelda. Монстры в игре "Zelda" движутся, в основном используя маршрутные точки (я говорю о простых монстрах, а не о "боссах"). В каждой точке маршрута они "осматриваются", и если игрок попадает в конус обзора одного из монстров, то целью становится не точка маршрута, а игрок. Этого эффекта можно достичь, если проверять в каждой точке маршрута, находится ли игрок не позади монстра (и таким образом может быть замечен, если монстр осматривается). Если монстр натыкается на препятствие, он не пытается обойти его, а движется в том же самом направлении снова и снова. Похоже, что подобный метод использует Diablo, только монстры в этой программе движутся немного вдоль препятствия, используя "метод тыка" в надежде нащупать проход к игроку.

     Жульничество - выслеживание игрока. Очень эффективный способ находить игрока состоит в использовании "следопытов" (например, собак) - некоторых агрессивных, мелких созданий, которые могут идти по следу игрока (если б они были не малы, игра была бы весьма несправедлива), по его запаху. Для реализации этой идеи вы можете в тех местах, где находился игрок, в качестве атрибута этих мест запоминать направление его движения. Это дало бы возможность следопыту эффективно идти по следу игрока. (Этот вид алгоритма прекрасно подошел бы для игр типа Pacman'а.)

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

1.3. Краткий исторический обзор развития работ в области ИИ.

      Начало  исследований в области ИИ (конец 50-х годов) связывают с работами Ньюэлла, Саймана и Шоу, исследовавших  процессы решения различных задач. Результатами их работ явились такие программы как "ЛОГИК-ТЕОРЕТИК", предназначенная для доказательства теорем в исчислении высказываний, и "ОБЩИЙ РЕШАТЕЛЬ ЗАДАЧ". Эти работы положили начало первому этапу исследований в области ИИ, связанному с разработкой программ, решающих задачи на основе применения разнообразных эвристических методов.

      Эвристический метод решения задачи при этом рассматривался как свойственный человеческому  мышлению "вообще", для которого характерно возникновение догадок о пути решения задачи с последующей проверкой их. Ему противопоставлялся используемый в ЭВМ алгоритмический метод, который интерпретировался как механическое осуществление заданной последовательности шагов, детерминированно приводящей к правильному ответу. Трактовка эвристических методов решения задач как сугубо человеческой деятельности и обусловила появление и дальнейшее распространение термина ИИ. В начале 70-х годов Ньюэлл и Саймон опубликовали много данных, подтверждающих, что их программы моделируют человеческое мышление и предложили общую методику составления программ, моделирующих мышление. Примерно в то время, когда работы Ньюэлла и Саймона стали привлекать к себе внимание, в Массачусетсском технологическом институте, Стэнфордском университете и Стэнфордском исследовательском институте также сформировались исследовательские группы в области ИИ. В противоположность ранним работам Ньюэлла и Саймона эти исследования больше относились к формальным математическим представлениям. Способы решения задач в этих исследованиях развивались на основе расширения математической и символической логики. Моделированию же человеческого мышления придавалось второстепенное значение.

     На  дальнейшие исследования в области  ИИ большое влияние оказало появление метода резолюций Робинсона, основанного на доказательстве теорем в логике предикатов (это функция с областью значений {0,1} (или «Истина» и «Ложь»), один из элементов логики первого и высших порядков) и являющегося исчерпывающим методом доказательства. При этом определение термина ИИ претерпело существенное изменение. Целью исследований, проводимых в направлении ИИ, стала разработка программ, способных решать "человеческие задачи". Так, один из видных исследователей ИИ того времени Р. Бенерджи в 1969 году писал: "Область исследований, обычно называемую ИИ, вероятно, можно представить как совокупность методов и средств анализа и конструирования машин, способных выполнять задания, с которыми до недавнего времени мог справиться только человек. При этом по скорости и эффективности машины должны быть сравнимы с человеком." Функциональный подход к направленности исследований по ИИ сохранился в основном до настоящего времени, хотя еще и сейчас ряд ученых, особенно психологов, пытаются оценивать результаты работ по ИИ с позиций их соответствия человеческому мышлению.