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

Содержание

Слайд 2

Литература Рассел С., Норвиг П. Искусственный интеллект: современный подход. – М.:

Литература

Рассел С., Норвиг П. Искусственный интеллект: современный подход. – М.: Вильямс,

2006. – 1408 с.
Люггер Дж. Искусственный интеллект: стратегии и методы решения сложных проблем. – М.: Вильямс, 2005. – 864 с.
Лорьер Ж.-Л. Системы искусственного интеллекта. –М.: Мир, 1991. – 568 с.
Попов Д. В., Ризванов Д.А. Системы искусственного интеллекта. Эвристический поиск и инженерия знаний: [учебное пособие для студентов высших учебных заведений, обучающихся по специальности 230105 - "Программное обеспечение вычислительной техники и автоматизированных систем"], ФГБОУ ВПО УГАТУ - Уфа: УГАТУ, 2012 - 117 с.
Слайд 3

Предыстория ИИ Философия основы ИИ, сформулировав идеи, что мозг в определенных

Предыстория ИИ

Философия основы ИИ, сформулировав идеи, что мозг в определенных отношениях напоминает

машину, оперирует знаниями, закодированными на внутреннем языке, мышление может использоваться для выбора наилучших действий.
Математика инструментальные средства для манипулирования высказываниями, обладающими логической достоверностью, а также недостоверными вероятностными высказываниями. Заложили основу формирования рассуждений об алгоритмах.
Экономика формализация проблемы принятия решений, максимизирующих ожидаемый выигрыш.
Психология идея «любая теория познания должна напоминать компьютерную программу», она должна подробно описывать механизм обработки информации, с помощью которого может быть реализована некоторая познавательная функция.
Вычислительная быстрые мощные компьютеры. техника
Теория управления проектирование устройств, которые действуют оптимально на основе обратной связи.
Лингвистика представление знаний, обработка естественного языка
Слайд 4

Краткая история ИИ 1943 McCulloch & Pitts: Boolean circuit model of

Краткая история ИИ

1943 McCulloch & Pitts: Boolean circuit model of brain
1950

Turing's "Computing Machinery and Intelligence"
1956 Dartmouth meeting: "Artificial Intelligence" adopted
1952—69 Look, Ma, no hands!
1950s Early AI programs, including Samuel's checkers program, Newell & Simon's Logic Theorist, Gelernter's Geometry Engine
1965 Robinson's complete algorithm for logical reasoning
1966—73 AI discovers computational complexity Neural network research almost disappears
1969—79 Early development of knowledge-based systems
1980-- AI becomes an industry
1986-- Neural networks return to popularity
1987-- AI becomes a science
1995-- The emergence of intelligent agents
Слайд 5

Что такое ИИ?

Что такое ИИ?

Слайд 6

Системы, которые действуют подобно людям Turing (1950) "Computing machinery and intelligence":

Системы, которые действуют подобно людям

Turing (1950) "Computing machinery and intelligence":
Возможности, которыми

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

Системы, которые думают подобно людям Существует 3 способа узнать, как думает

Системы, которые думают подобно людям

Существует 3 способа узнать, как думает человек:


интроспекция — попытка проследить за ходом собственных мыслей;
психологические эксперименты — наблюдение человека в действии;
через сканирование мозга – наблюдение за мозгом в действии.
Аллен Ньюэлл и Герберт Саймон “General Problem Solver” (GPS, 1961), не стремились к тому, чтобы эта программа правильно решала поставленные задачи. В большей степени их заботило ,чтобы запись этапов проводимых ею рассуждений совпадала с регистрацией рассуждений людей, решающих такие же задачи.
Когнитология – междисциплинарная область, в которой совместно используются компьютерные модели, взятые из искусственного интеллекта, и экспериментальные методы, взятые из психологии, для разработки точных и обоснованных теорий работы человеческого мозга.
Слайд 8

Системы, которые думают рационально Аристотель – законы «правильного мышления». Его силлогизмы

Системы, которые думают рационально

Аристотель – законы «правильного мышления».
Его силлогизмы стали образцом

для создания процедур доказательства, которые всегда позволяют прийти к правильным заключениям, если даны правильные предпосылки.
Основа этих исследований – предположение, что такие законы мышления управляют работой ума. На их основе развивается логика.
В 19 веке была разработана точная система логических обозначений для утверждений о предметах любого рода, которые встречаются в мире, и об отношениях между ними (сравните с обычной системой арифметических обозначений, которая предназначена в основном для формирования утверждений о равенстве и неравенстве чисел!!!).
К1965 г. были разработаны программы, которые могли в принципе решить любую разрешимую проблему, описанную в системе логических обозначений. Если же решение не существует, программа может так и не остановиться в процессе его поиска.
Проблемы:
довольно сложно любые неформальные знания выразить в формальных терминах, требуемых для системы логических обозначений, особенно если эти знания не являются полностью достоверными.
есть большая разница между решением проблемы «в принципе» и решением проблемы на практике.
Слайд 9

Системы, которые действуют рационально Агентом считается все, что действует («агент» произошло

Системы, которые действуют рационально

Агентом считается все, что действует («агент» произошло от

латинского «agere», действовать).Рациональный агент – это агент, который действует таким образом, чтобы можно было достичь наилучшего результата или, в условиях неопределенности, наилучшего ожидаемого результата.
Все навыки, необходимые для прохождения теста Тьюринга, позволяют также осуществлять рациональные действия.
Представление знаний и логический вывод позволяет агентам получать хорошие решений.
Необходимо уметь формировать понятные предложения на естественном языке, поскольку в сложный социум принимают только тех, кто способен правильно высказывать свои мысли.
Необходимо учиться не только ради приобретения эрудиции, но и в связи с тем, что лучшее представление о том, как устроен мир, позволяет вырабатывать более эффективные стратегии действий в этом мире.
Нужно обладать способностью к зрительному восприятию не только потому, что процесс визуального наблюдения позволяет получить удовольствие, но и потому, что зрение подсказывает, чего можно достичь с помощью определенного действия (например, быстрее всех получить лакомый кусочек).
Слайд 10

Системы, которые действуют рационально Преимущества подхода: более общий по сравнению с

Системы, которые действуют рационально
Преимущества подхода:
более общий по сравнению с подходом

на основе «законов мышления», поскольку правильный логический вывод – это просто один из нескольких возможных механизмов достижения рациональности.
более перспективный для научной разработки по сравнению с подходами, основанными на изучении человеческого поведения или человеческого мышления, поскольку стандарт рациональности четко определен и полностью обобщен.
Слайд 11

Различные подходы к построению систем ИИ Логический Структурный Эволюционный Имитационный Агентно-ориентированный подход

Различные подходы к построению систем ИИ

Логический
Структурный
Эволюционный
Имитационный
Агентно-ориентированный подход

Слайд 12

Логический подход Основа - Булева алгебра и исчисление предикатов. Практически каждая

Логический подход

Основа - Булева алгебра и исчисление предикатов.
Практически каждая система ИИ,

построенная на логическом принципе, представляет собой машину доказательства теорем. При этом исходные данные хранятся в базе данных в виде аксиом, правила логического вывода как отношения между ними. Каждая такая машина имеет блок генерации цели, и система вывода пытается доказать данную цель как теорему. Если цель доказана, то трассировка примененных правил позволяет получить цепочку действий, необходимых для реализации поставленной цели.
Отсутствие выразительности алгебры высказываний.
Добиться большей выразительности позволяет нечеткая логика. Основным ее отличием является то, что правдивость высказывания может принимать в ней кроме да/нет (1/0) еще и промежуточные значения — не знаю (0.5), пациент скорее жив, чем мертв (0.75), пациент скорее мертв, чем жив (0.25). Данный подход больше похож на мышление человека, поскольку он на вопросы редко отвечает только да или нет.
Большая трудоемкость, поскольку во время поиска доказательства возможен полный перебор вариантов.
Поэтому данный подход требует эффективной реализации вычислительного процесса, и хорошая работа обычно гарантируется при сравнительно небольшом размере базы данных.
Слайд 13

Структурный подход Попытки построения ИИ путем моделирования структуры человеческого мозга. Одной

Структурный подход

Попытки построения ИИ путем моделирования структуры человеческого мозга. Одной из

первых таких попыток был перцептрон Френка Розенблатта. Основной моделируемой структурной единицей в перцептронах (как и в большинстве других вариантов моделирования мозга) является нейрон.
Позднее возникли и другие модели, которые известны под термином "нейронные сети" (НС). Эти модели различаются по строению отдельных нейронов, по топологии связей между ними и по алгоритмам обучения.
Для моделей, построенных по мотивам человеческого мозга характерны:
не слишком большая выразительность;
легкое распараллеливание алгоритмов;
высокая производительность параллельно реализованных НС.
Нейронные сети работают даже при условии неполной информации об окружающей среде, то есть как и человек, они на вопросы могут отвечать не только "да" и "нет" но и "не знаю точно, но скорее да" (схожесть с человеческим мозгом).
Слайд 14

Эволюционный подход Основное внимание уделяется построению начальной модели и правилам, по

Эволюционный подход

Основное внимание уделяется построению начальной модели и правилам, по которым

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

Имитационный подход Это классический подход для кибернетики с одним из ее

Имитационный подход

Это классический подход для кибернетики с одним из ее базовых

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

Агентно-ориентированный подход Основан на использовании интеллектуальных (рациональных) агентов. Интеллект — это

Агентно-ориентированный подход

Основан на использовании интеллектуальных (рациональных) агентов. Интеллект — это вычислительная

часть (грубо говоря, планирование) способности достигать поставленных перед интеллектуальной машиной целей. Сама такая машина будет интеллектуальным агентом, воспринимающим окружающий его мир с помощью датчиков и способной воздействовать на объекты в окружающей среде с помощью исполнительных механизмов.
Основной акцент – на методах и алгоритмах, которые помогут интеллектуальному агенту выживать в окружающей среде при выполнении его задачи. Здесь значительно сильнее изучаются алгоритмы поиска и принятия решений.
Способ решения задачи основан на коммуникациях между агентами.
Слайд 17

Современное состояние разработок Robotic vehicles: A driverless robotic car named STANLEY

Современное состояние разработок

Robotic vehicles: A driverless robotic car named STANLEY sped

through the rough terrain of the Mojave dessert at 22 mph, finishing the 132-mile course first to win the 2005 DARPA Grand Challenge. No hands across America (driving autonomously 98% of the time from Pittsburgh to San Diego)
Autonomous planning and scheduling: NASA's on-board autonomous planning program controlled the scheduling of operations for a spacecraft.
Game playing: Deep Blue defeated the world chess champion Garry Kasparov in 1997
Spam fighting: Each day, learning algorithms classify over a billion messages as spam, saving the recipient from having to waste time deleting what, for many users, could comprise 80% or 90% of all messages.
Logistics planning: During the 1991 Gulf War, US forces deployed an AI logistics planning and scheduling program that involved up to 50,000 vehicles, cargo, and people at a time, and had to account for starting points, destinations, routes, and conflict resolution among all parameters.
Machine Translation: A computer program automatically translates from Arabic to English. None of the computer scientists of the team speak Arabic, but they do understand statistics and machine learning algorithms.
Proverb solves crossword puzzles better than most humans
Слайд 18

Умные машины: до "судного дня" осталось недолго (http://top.rbc.ru/economics/31/01/2013/842964.shtml)

Умные машины: до "судного дня" осталось недолго (http://top.rbc.ru/economics/31/01/2013/842964.shtml)

Слайд 19

Живое железо Сегодня появление таких технологических новинок, как распознающий движения контроллер

Живое железо
Сегодня появление таких технологических новинок, как распознающий движения контроллер

Kinect от Microsoft, на некоторое время "взрывает" среду избалованных продвинутыми девайсами потребителей, но с каждым разом публика все быстрее привыкает к "умным" новациям и ждет, когда контакт с искусственным разумом станет еще теснее. Не сидится спокойно и генераторам IT-идей. "Несмотря на то, что Kinect перенес взаимодействие на физический уровень, многое до сих пор происходит на плоском экране, иногда в 3D. Ввод информации улучшился, а вывод пока не очень. Мы работаем над трехмерными системами отображения на базе различных технологий, в том числе проективных. Нужно впустить компьютерный мир в наш, физический, сделать его более осязаемым. Для этого, однако, нужно распознать не только пользователя, но и пространство вокруг него – тогда мы сможем дополнять реальный мир виртуальными объектами в гораздо более удобной форме", - говорит исследователь Microsoft Research Шахрам Изади.
Его коллега из конкурирующей IBM, вице-президент по инновациям Берни Мейерсон, соглашается, добавляя, что компьютеры в ближайшие годы должны стать еще "умнее", помогать человеку получать информацию, эффективно ее использовать. "Когнитивные вычислительные системы помогут выделять в данных ключевое, успевать за скоростью их распространения, принимать более взвешенные решения, укреплять здоровье и повышать уровень жизни, разнообразить жизнь и устранять любые препятствия и барьеры: географические, языковые, связанные со стоимостью и доступностью услуг", - уверен Б.Мейерсон.
Слайд 20

Картинка на ощупь Уже в ближайшие пять лет, уверены разработчики из

Картинка на ощупь
Уже в ближайшие пять лет, уверены разработчики из IBM,

компьютеры совершат мощный прорыв в области имитации органов чувств человека. Известно, что тач-интерфейс является одним из главных трендов в области потребительской электроники. И сегодня ведутся разработки по его совершенствованию. Так, ученые IBM хотят "научить" сенсорный экран передавать тактильные ощущения. Такая фишка может прийтись по вкусу любительницам онлайн-шопинга: к привычному рассматриванию фотографии приглянувшегося платья добавиться возможность и "потрогать" его. Проводя пальцами по экрану с фотографией наряда, можно будет почувствовать текстуру материала, из которого он сделан.
Для реализации этой идеи используются технологии чувствительности к тактильным воздействиям, инфракрасному свету и давлению для имитации осязания, а также… стандартная функция вибрации сотового телефона. Она позволяет назначить каждому объекту уникальный набор вибрационных характеристик, который и будет передавать тактильные ощущения.
Слайд 21

Пиксель знает Разработчики IBM сетуют, что компьютеры сегодня понимают смысл изображения

Пиксель знает
Разработчики IBM сетуют, что компьютеры сегодня понимают смысл изображения только

по текстовым тегам и названию (само содержание изображения пока остается для компьютеров за гранью понимания). Но ученые не унывают и работают над тем, чтобы компьютерные системы научись, анализируя пиксели, понимать смысл изображения, как это делает человек.
Возможность компьютеров получать знания из визуальных данных окажет серьезное влияние на здравоохранение, розничную торговлю и сельское хозяйство, уверены в IBM. Так, техника сможет анализировать изображения компьютерной томографии, рентгеновских снимков и результатов УЗИ, при этом распознавая едва различимые или невидимые для человеческого глаза детали.
Слайд 22

Ухо искусственного разума У человеческого слухового аппарата тоже в скором времени

Ухо искусственного разума
У человеческого слухового аппарата тоже в скором времени появится

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

Компьютер-поварешка Исследователи IBM уверены: здоровая пища должна быть вкусной! Они разрабатывают

Компьютер-поварешка
Исследователи IBM уверены: здоровая пища должна быть вкусной! Они разрабатывают компьютерную

систему - по сути, цифровые вкусовые рецепторы - способную создавать новые рецепты, действуя по непростому алгоритму. Она будет расщеплять ингредиенты до их молекулярного уровня и составлять химические композиции пищевых соединений с учетом вкусовых и ароматических предпочтений людей.
Система позволит изучать то, как химические вещества взаимодействуют друг с другом, выяснять их вкусовые составляющие на молекулярном уровне и использовать эту информацию в сочетании с моделями восприятия для прогнозирования вкусовой привлекательности продукта, рассказывают в IBM. Наверняка, такая система не только поможет сделать здоровую пищу более приятной, она также удивит необычными комбинациями продуктов.
Слайд 24

Лови мое дыхание …И вот опять простуда. И вроде бы Минздрав

Лови мое дыхание
…И вот опять простуда. И вроде бы Минздрав предупреждал,

и старались обходить стороной заболевшего, но все равно, когда поняли, что простуда накрыла, было уже поздно. Подобная история может окончательно уйти в прошлое уже в ближайшие годы. Специалисты IBM обещают, что в следующие пять лет встроенные в компьютер или мобильный телефон крошечные датчики смогут на ранней стадии определить симптомы простуды или других заболеваний. "Анализируя запахи, биомаркеры и тысячи молекул в дыхании человека и соотнося их с нормой, компьютерные системы будут помогать врачам в диагностике и мониторинге различных заболеваний", - говорят в компании.
Работающие по аналогичному принципу датчики смогут собирать и анализировать данные там, где это считалось недоступным. В частности, компьютерные системы можно будет использовать в сельском хозяйстве для определения запаха и анализа состояния почвы. В городских условиях эта технология может применяться для мониторинга санитарного состояния и уровня загрязнения территорий и помещений, помогая службам города выявлять потенциальные проблемы прежде, чем они нанесут реальный ущерб.
Слайд 25

Человек-проводник Разработчики IT-инноваций постоянно твердят о сближении виртуального мира и реального,

Человек-проводник
Разработчики IT-инноваций постоянно твердят о сближении виртуального мира и реального, об

очеловечивании машины. Но такая конвергенция наводит на мысль и о возможности обратного процесса - компьютеризации самого человека. И эта мысль давно вышла за границы сценариев фантастических фильмов. Компания Ericsson, в свое время создавшая технологию Bluetooth, как раз работает в этом направлении.
"Сегодня мы активно работаем над развитием технологии, которая позволяет обмениваться информацией и связывать устройства через тело человека", - рассказала директор по коммуникациям Ericsson в России, Украине, СНГ и Центральной Азии Анастасия Тимошина. Она пояснила, что речь идет о технологии Сonnected Me, впервые представленной Ericsson в прошлом году. Сonnected Me позволяет передавать данные через тело человека на скорости до 10 Мбит/с, но в перспективе можно будет говорить о "разгоне" до 20-40 Мбит/c. А это значит, что уже в недалеком будущем станет возможна передача музыки и фотографий, обмен визитками, электронная оплата покупок в одно касание, пусть даже сегодня это кажется фантастикой.
Слайд 26

Интеллектуальные агенты

Интеллектуальные агенты

Слайд 27

Агенты и варианты среды Агентом является все, что может рассматриваться как

Агенты и варианты среды

Агентом является все, что может рассматриваться как воспринимающее

свою среду с помощью датчиков и воздействующее на эту среду с помощью исполнительных механизмов (например, человек, робот, ПО и т.д.).
Слайд 28

Агенты и варианты среды Термин «восприятие» используется для обозначения полученных агентом

Агенты и варианты среды

Термин «восприятие» используется для обозначения полученных агентом
сенсорных

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

Пример. Мир пылесоса Восприятие: местоположение (в каком квадрате он находится); состояние

Пример. Мир пылесоса

Восприятие:
местоположение (в каком квадрате он находится);
состояние квадрата (есть

ли мусор в этом квадрате).
Действия: переход влево, вправо, всасывание мусора или бездействие.
… ?
Слайд 30

Качественное поведение: концепция рациональности Рациональным агентом является такой агент, который выполняет

Качественное поведение: концепция рациональности

Рациональным агентом является такой агент, который выполняет правильные

действия; или более формально, агент, в котором каждая запись в таблице для функции агента заполнена правильно.
выполнение правильных действий?
Слайд 31

Показатели производительности Показатели производительности воплощают в себе критерии оценки успешного поведения

Показатели производительности

Показатели производительности воплощают в себе критерии оценки успешного поведения агента.


Последовательность действий агента вынуждает среду пройти через последовательность состояний. Если такая последовательность соответствует желаемому, то агент функционирует хорошо.
Не может быть одного постоянного показателя, подходящего для всех агентов.
?
Можно узнать у агента его субъективное мнение о том, насколько он удовлетворен своей собственной производительностью, но некоторые агенты не будут способны ответить, а другие склонны заниматься самообманом («зеленый виноград»).
Поэтому необходимо добиваться применения объективных показателей производительности, и, как правило, проектировщик, конструирующий агента, предусматривает такие показатели.
Слайд 32

Агент-пылесос Показатель производительности??? Рекомендация: лучше всего разрабатывать показатели производительности в соответствии

Агент-пылесос

Показатель производительности???
Рекомендация: лучше всего разрабатывать показатели производительности в соответствии с тем,

чего действительно необходимо добиться в данной среде, а не в соответствии с тем, как, по мнению проектировщика, должен вести себя агент.
Философская проблема предпочтительности: что лучше — бесшабашная жизнь со взлетами и падениями или безопасное, но однообразное существование? Что лучше — экономика, в которой каждый живет в умеренной бедности, или такая экономика, в которой одни ни в чем не нуждаются, а другие еле сводят концы с концами?
Слайд 33

Рациональность Зависит от следующих факторов: • Показатели производительности, которые определяют критерии

Рациональность

Зависит от следующих факторов:
• Показатели производительности, которые определяют критерии успеха.
• Знания

агента о среде, приобретенные ранее.
• Действия, которые могут быть выполнены агентом.
• Последовательность актов восприятия агента, которые произошли до
настоящего времени.
Рациональный агент – это агент, который для каждой возможной последовательности актов восприятия должен выбрать действие, которое, как ожидается, максимизирует его показатели производительности, с учетом фактов, предоставленных данной последовательностью актов восприятия и всех встроенных знаний, которыми обладает агент.
Является ли рациональным агент-пылесос?
Слайд 34

Всезнание, обучение и автономность 1. Необходимо различать рациональность и всезнание. Рациональность

Всезнание, обучение и автономность

1. Необходимо различать рациональность и всезнание.
Рациональность — это

максимизация ожидаемой производительности, а совершенство — максимизация фактической производительности.
Отказываясь от стремления к совершенству, мы не только применяем к агентам справедливые критерии, но и учитываем реальность.
Если от агента требуют, чтобы он выполнял действия, которые оказываются наилучшими после их совершения, то задача проектирования агента, отвечающего этой спецификации, становится невыполнимой.
2. Определение рационального агента требует, чтобы он не только собирал информацию, но и обучался в максимально возможной степени на тех данных, которые он воспринимает.
3. Рациональный агент должен быть автономным – он должен обучаться всему, что может освоить, для компенсации неполных или неправильных априорных знаний (например, агент-пылесос, который обучается прогнозированию того, где и когда появится дополнительный мусор, безусловно, будет работать лучше, чем тот агент, который на это не способен).
Слайд 35

Определение проблемной среды Факторы, определяющие проблемную среду: производительность; среда; исполнительные механизмы;

Определение проблемной среды

Факторы, определяющие проблемную среду:
производительность;
среда;
исполнительные механизмы;
датчики.
PEAS (Performance measure, Environment, Actuators,

Sensors)
Пример. Описание PEAS проблемной среды для автоматизированного такси
Слайд 36

Примеры типов агентов и их описаний

Примеры типов агентов и их описаний

Слайд 37

Свойства проблемной среды • Полностью наблюдаемая или частично наблюдаемая (если датчики

Свойства проблемной среды

• Полностью наблюдаемая или частично наблюдаемая (если датчики агента

предоставляют ему доступ к полной информации о состоянии среды в каждый момент времени, то такая проблемная среда называется полностью наблюдаемой).
• Детерминированная или стохастическая (если следующее состояние среды полностью определяется текущим состоянием и действием, выполненным агентом, то такая среда называется детерминированной; в противном случае она является стохастической).
• Эпизодическая или последовательная (в эпизодической проблемной среде опыт агента состоит из неразрывных эпизодов, каждый эпизод включает в себя восприятие среды агентом, а затем выполнение одного действия. При этом крайне важно то, что следующий эпизод не зависит от действий, предпринятых в предыдущих эпизодах. В эпизодических вариантах среды выбор действия в каждом эпизоде зависит только от самого эпизода. В последовательных вариантах среды текущее решение может повлиять на все будущие решения).
Слайд 38

Свойства проблемной среды • Статическая или динамическая (если среда может измениться

Свойства проблемной среды

• Статическая или динамическая (если среда может измениться в

ходе того, как агент выбирает очередное действие, то такая среда называется динамической для данного агента; в противном случае она является статической. Если с течением времени сама среда не изменяется, а изменяются показатели производительности агента, то такая среда называется полудинамической).
• Дискретная или непрерывная (различие между дискретными и непрерывными вариантами среды может относиться к состоянию среды, способу учета времени, а также восприятиям и действиям агента).
• Одноагентная или мультиагентная (ключевое различие состоит в том, следует ли или не следует описывать поведение объекта В как максимизирующее личные показатели производительности, значения которых зависят от поведения агента А. Например, в шахматах соперничающая сущность в пытается максимизировать свои показатели производительности, а это по правилам шахмат приводит к минимизации показателей производительности агента А. Таким образом, шахматы — это конкурентная мультиагентная среда. А в среде вождения такси, с другой стороны, предотвращение столкновений максимизирует показатели производительности всех агентов, поэтому она может служить примером частично кооперативной мультиагентной среды. Она является также частично конкурентной, поскольку, например, парковочную площадку может занять только один автомобиль).
Слайд 39

Какова среда реального мира? Полностью наблюдаемая или частично наблюдаемая? Детерминированная или

Какова среда реального мира?
Полностью наблюдаемая или частично наблюдаемая?
Детерминированная или стохастическая?
Эпизодическая или

последовательная?
Статическая или динамическая?
Дискретная или непрерывная?
Одноагентная или мультиагентная?
Частично наблюдаемая
Стохастическая
Последовательная
Динамическая
Непрерывная
Мультиагентная
Слайд 40

Недостаток: Если P – множество актов восприятия, T – срок существования

Недостаток:
Если P – множество актов восприятия, T – срок существования агента

(общее количество актов восприятия, которое может быть им получено), то поисковая
таблица будет содержать записей.

Структура агентов

Агент = Архитектура + Программа

Слайд 41

Простые рефлексные агенты Агенты выбирают действия на основе текущего акта восприятия,

Простые рефлексные агенты

Агенты выбирают действия на основе текущего акта восприятия, игнорируя

всю остальную историю актов восприятия.
Слайд 42

Простые рефлексные агенты Недостаток – агент работает, только если правильное решение

Простые рефлексные агенты

Недостаток – агент работает, только если правильное решение может

быть принято на основе исключительно текущего восприятия, т.е. если среда является полностью наблюдаемой.
Слайд 43

Рефлексные агенты, основанные на модели Агент поддерживает внутреннее состояние, которое зависит

Рефлексные агенты, основанные на модели

Агент поддерживает внутреннее состояние, которое зависит от

истории актов восприятия.
Программа агента содержит знания двух видов:
информация о том, как мир изменяется независимо от агента (например, что автомобиль, идущий на обгон, обычно становится ближе, чем в какой-то предыдущий момент).
информация о том, как влияют на мир собственные действия агента (например, при повороте агентом рулевого колеса по часовой стрелке автомобиль поворачивает вправо или что после проезда по автомагистрали в течение пяти минут на север автомобиль находится на пять миль севернее от того места, где он был пять минут назад).
Эти знания о том, «как работает мир» (которые могут быть воплощены в простых логических схемах или в сложных научных теориях) называются моделью мира.
Слайд 44

Рефлексные агенты, основанные на модели

Рефлексные агенты, основанные на модели

Слайд 45

Агенты, основанные на цели

Агенты, основанные на цели

Слайд 46

Агенты, основанные на полезности Функция полезности отображает состояние (или последовательность состояний)

Агенты, основанные на полезности

Функция полезности отображает состояние (или последовательность состояний) на

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

Обучающиеся агенты Основные компоненты: обучающийся компонент – отвечает за внесение усовершенствований;

Обучающиеся агенты

Основные компоненты:
обучающийся компонент – отвечает за внесение усовершенствований;
производительный компонент –

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

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

Слайд 48

Решение проблем посредством поиска

Решение проблем посредством поиска

Слайд 49

Агенты, решающие задачи Разновидность агентов, основанных на цели. Цели позволяют организовать

Агенты, решающие задачи

Разновидность агентов, основанных на цели.
Цели позволяют организовать поведение, ограничивая

выбор промежуточных этапов, которые пытается осуществить агент. Первым шагом в решении задачи является формулировка цели с учетом текущей ситуации и показателей производительности агента.
Цель –множество состояний мира, а именно тех состояний, в которых достигается такая цель. Задача агента состоит в том, чтобы определить, какая последовательность действий приведет его в целевое состояние.
Прежде чем это сделать, агент должен определить, какого рода действия и состояния ему необходимо рассмотреть (степень детализации).
Формулировка задачи представляет собой процесс определения того, какие действия и состояния следует рассматривать с учетом некоторой цели.
Слайд 50

Пример. Выходные в Румынии Currently in Arad. Flight leaves tomorrow from

Пример. Выходные в Румынии

Currently in Arad.
Flight leaves tomorrow from Bucharest
Formulate goal:
be

in Bucharest
Formulate problem:
states: various cities
actions: drive between cities
Find solution:
sequence of cities, e.g., Arad, Sibiu, Fagaras, Bucharest
Слайд 51

Пример. Выходные в Румынии

Пример. Выходные в Румынии

Слайд 52

Основные определения Процесс определения последовательности действий, которые приводят к достижению цели,

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

Процесс определения последовательности действий, которые приводят к достижению цели, называется

поиском.
Любой алгоритм поиска принимает в качестве входных данных некоторую задачу и возвращает решение в форме последовательности действий.
После того как решение найдено, могут быть осуществлены действия, рекомендованные этим алгоритмом. Такое осуществление происходит на стадии выполнения.
Слайд 53

Хорошо структурированные задачи и решения Задача может быть формально определена с

Хорошо структурированные задачи и решения

Задача может быть формально определена с помощью

следующих компонентов:
Начальное состояние, в котором агент приступает к работе.
In(Arad)
Описание возможных действий, доступных агенту (множество операторов, функция определения преемника).
{, ,
}
Начальное состояние и функция определения преемника, вместе взятые, неявно задают пространство состояний данной задачи — множество всех состояний, достижимых из начального состояния. Пространство состояний образует граф, узлами которого являются состояния, а дугами между узлами — действия.
Путем в пространстве состояний является последовательность состояний, соединенных последовательностью действий.
Слайд 54

Хорошо структурированные задачи и решения Проверка цели, позволяющая определить, является ли

Хорошо структурированные задачи и решения

Проверка цели, позволяющая определить, является ли данное

конкретное состояние целевым состоянием. Иногда имеется явно заданное множество возможных целевых состояний, и эта проверка сводится просто к определению того, является ли данное состояние одним из них.
{In {Bucharest) }.
Иногда цель задается в виде абстрактного свойства, а не явно перечисленного множества состояний. Например, в шахматах цель состоит в достижении состояния, называемого "матом", в котором король противника атакован и не может уклониться от удара.
Функция стоимости пути, которая назначает числовое значение стоимости каждому пути. Агент, решающий задачу, выбирает функцию стоимости, которая соответствует его собственным показателям производительности.
c(x, a, y)
Решением задачи является путь от начального состояния до целевого состояния.
Оптимальным решением является такое решение, которое имеет наименьшую стоимость пути среди всех прочих решений.
Слайд 55

Пространство состояний для мира пылесоса

Пространство состояний для мира пылесоса

Слайд 56

Мир пылесоса Состояния. Агент находится в одном из двух местонахождений, в

Мир пылесоса

Состояния. Агент находится в одном из двух местонахождений, в каждом

из которых может присутствовать или не присутствовать мусор. Поэтому существует 2х22=8 возможных состояний мира.
Начальное состояние. В качестве начального состояния может быть назначено любое состояние.
Функция определения преемника. Эта функция вырабатывает допустимые состояния, которые являются следствием попыток выполнения трех действий (Left, Right и Suck).
Проверка цели. Эта проверка сводится к определению того, являются ли чистыми все квадраты.
Стоимость пути. Стоимость каждого этапа равна 1, поэтому стоимость пути представляет собой количество этапов в этом пути.
Слайд 57

Задача игры в восемь Задача игры в восемь имеет 9!/2 =

Задача игры в восемь

Задача игры в восемь имеет 9!/2 = 181

440 достижимых состояний и легко решается.
Задача игры в пятнадцать (на доске 4x4) имеет около 1,3 триллиона состояний, и случайно выбранные ее экземпляры могут быть решены оптимальным образом за несколько миллисекунд с помощью наилучших алгоритмов поиска.
Задача игры в двадцать четыре (на доске 5x5) имеет количество состояний около 1025, и случайно выбранные ее экземпляры все еще весьма нелегко решить оптимальным образом с применением современных компьютеров и алгоритмов.
Слайд 58

Поиск решений

Поиск решений

Слайд 59

Представление узлов State. Состояние в пространстве состояний, которому соответствует данный узел.

Представление узлов

State. Состояние в пространстве состояний, которому соответствует данный узел.
Parent-Node. Узел

в дереве поиска, применявшийся для формирования данного узла (родительский узел).
Action. Действие, которое было применено к родительскому узлу для формирования данного узла.
Path-Cost. Стоимость пути (от начального состояния до данного узла), показанного с помощью указателей родительских узлов, которую принято обозначать как g(n).
Depth. Количество этапов пути от начального состояния, называемое также глубиной.
Необходимо различать узлы и состояния. Узел — это учетная структура данных, применяемая для представления дерева поиска, а состояние соответствует конфигурации мира. Поэтому узлы лежат на конкретных путях, которые определены с помощью указателей Parent-Node, а состояния – нет.
Два разных узла могут включать одно и то же состояние мира, если это состояние формируется с помощью двух различных путей поиска.
Слайд 60

Представление узлов Коллекция узлов, которые были сформированы, но еще не развернуты,

Представление узлов

Коллекция узлов, которые были сформированы, но еще не развернуты, называется

периферией. Каждый элемент периферии представляет собой листовой узел, т.е. узел, не имеющий преемников в дереве.
Коллекция узлов м.б. выражена в виде очереди.
Слайд 61

Измерение производительности решения задачи Полнота. Гарантирует ли алгоритм обнаружение решения, если

Измерение производительности решения задачи

Полнота. Гарантирует ли алгоритм обнаружение решения, если оно

имеется?
Оптимальность. Обеспечивает ли данная стратегия нахождение оптимального решения.
Временная сложность. За какое время алгоритм находит решение?
Пространственная сложность. Какой объем памяти необходим для осуществления поиска?
В искусственном интеллекте, где граф представлен неявно с помощью начального состояния и функции определения преемника и часто является бесконечным, сложность выражается в терминах трех величин: b – коэффициент ветвления или максимальное количество преемников любого узла, d – глубина самого поверхностного целевого узла и m – максимальная длина любого пути в пространстве состояний.
Слайд 62

Стратегии неинформированного поиска Uninformed search strategies use only the information available

Стратегии неинформированного поиска

Uninformed search strategies use only the information available in

the problem definition.
Breadth-first search
Uniform-cost search
Depth-first search
Depth-limited search
Iterative deepening search
Слайд 63

Uninformed search strategies A search strategy is defined by picking the

Uninformed search strategies

A search strategy is defined by picking the order

of node expansion
Strategies are evaluated along the following dimensions:
completeness: Is the algorithm guaranteed to find a solution when there is one?
optimality: Does the strategy find the optimal solution?
time complexity: How long does it take to find a solution?
space complexity: How much memory is needed to perform the search?
Time and space complexity are measured in terms of
b: the branching factor or maximum number of successors of any node
d: the depth of the shallowest goal node
m: the maximum length of any path in the state space
Слайд 64

Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue,

Breadth-first search

Expand shallowest unexpanded node
Frontier is a FIFO queue, i.e., new

successors go at end
Слайд 65

Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue,

Breadth-first search

Expand shallowest unexpanded node
Frontier is a FIFO queue, i.e., new

successors go at end
Слайд 66

Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue,

Breadth-first search

Expand shallowest unexpanded node
Frontier is a FIFO queue, i.e., new

successors go at end
Слайд 67

Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue,

Breadth-first search

Expand shallowest unexpanded node
Frontier is a FIFO queue, i.e., new

successors go at end
Слайд 68

Breadth-first search

Breadth-first search

Слайд 69

Properties of breadth-first search Complete? Yes (if b is finite) Time?

Properties of breadth-first search

Complete? Yes (if b is finite)
Time? 1+b+b2+b3+… +bd

+ b(bd-1) = O(bd+1)
Space? O(bd+1) (keeps every node in memory)
Optimal? Yes (if cost = 1 per step)
Space is the bigger problem (more than time)
Слайд 70

Uniform-cost search Expand least-cost unexpanded node Frontier is a queue ordered

Uniform-cost search

Expand least-cost unexpanded node
Frontier is a queue ordered by path

cost
Equivalent to breadth-first if step costs all equal
Complete? Yes, if step cost ≥ ε
Time? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε)) where C* is the cost of the optimal solution
Space? # of nodes with g ≤ cost of optimal solution, O(bceiling(C*/ ε))
Optimal? Yes – nodes expanded in increasing order of g(n)
Слайд 71

Depth-first search Expand deepest unexpanded node. Frontier = LIFO queue, i.e., put successors at front

Depth-first search

Expand deepest unexpanded node. Frontier = LIFO queue, i.e., put

successors at front
Слайд 72

Properties of depth-first search Complete? No: fails in infinite-depth spaces, spaces

Properties of depth-first search

Complete? No: fails in infinite-depth spaces, spaces with

loops
Modify to avoid repeated states along path
? complete in finite spaces
Time? O(bm): terrible if m is much larger than d
but if solutions are dense, may be much faster than breadth-first
Space? O(bm), i.e., linear space!
Optimal? No
Слайд 73

Depth-limited search = depth-first search with depth limit l, i.e., nodes

Depth-limited search

= depth-first search with depth limit l,
i.e., nodes at depth

l have no successors
Слайд 74

Iterative deepening search

Iterative deepening search

Слайд 75

Iterative deepening search

Iterative deepening search

Слайд 76

Iterative deepening search

Iterative deepening search

Слайд 77

Iterative deepening search

Iterative deepening search

Слайд 78

Iterative deepening search

Iterative deepening search

Слайд 79

Properties of iterative deepening search Complete? Yes Time? (d+1)b0 + d

Properties of iterative deepening search

Complete? Yes
Time? (d+1)b0 + d b1 +

(d-1)b2 + … + bd = O(bd)
Space? O(bd)
Optimal? Yes, if step cost = 1
Слайд 80

Comparing uninformed search strategies

Comparing uninformed search strategies

Слайд 81

Стратегии информированного (эвристического) поиска Помимо определения задачи используются знания, относящиеся к

Стратегии информированного (эвристического) поиска

Помимо определения задачи используются знания, относящиеся к данной

к данной конкретной проблемной области.
Подход носит название поиск по первому наилучшему совпадению (best first search).
Ключевой компонент – эвристическая функция h(n) (heuristic) – оценка стоимости наименее дорогостоящего пути от узла n до целевого узла.
Если n – целевой узел, то h(n)=0
Алгоритмы:
Жадный поиск по первому наилучшему совпадению (greedy best-first search)
Поиск A*
Слайд 82

Жадный поиск по первому наилучшему совпадению Предпринимаются попытки развертывания узла, который

Жадный поиск по первому наилучшему совпадению

Предпринимаются попытки развертывания узла, который рассматривается

как ближайший к цели на том основании, что он со всей вероятностью должен быстро привести к решению. Таким образом, при этом поиске оценка узлов производится с использованием только эвристической функции: f(n)=h(n).
Решение задачи поиска маршрута в Румынии на основе эвристической функции определения расстояния по прямой (Straight Line Distance — SLD), для которой принято обозначение hSLD.
Слайд 83

Пример. Выходные в Румынии

Пример. Выходные в Румынии

Слайд 84

Этапы жадного поиска пути до Бухареста

Этапы жадного поиска пути до Бухареста

Слайд 85

Этапы жадного поиска пути до Бухареста

Этапы жадного поиска пути до Бухареста

Слайд 86

Этапы жадного поиска пути до Бухареста

Этапы жадного поиска пути до Бухареста

Слайд 87

Этапы жадного поиска пути до Бухареста Найденное решение не оптимально: путь

Этапы жадного поиска пути до Бухареста

Найденное решение не оптимально: путь до

Бухареста через города Сибиу и Фэгэраш на 32 километра длиннее, чем путь через города Рымнику-Вылча и Питешти.

Оптимален ли путь?

Слайд 88

Свойства жадного поиска по наилучшему совпадению Complete? No – can get

Свойства жадного поиска по наилучшему совпадению

Complete? No – can get stuck

in loops, e.g., Iasi ? Neamt ? Iasi ? Neamt ?
Time? O(bm), but a good heuristic can give dramatic improvement
Space? O(bm) -- keeps all nodes in memory
Optimal? No
Слайд 89

Поиск А* f(n) = g(n) + h(n) f(n) – оценка стоимости

Поиск А*

f(n) = g(n) + h(n)
f(n) – оценка стоимости наименее

дорогостоящего пути решения, проходящего через узел n.
Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением g(n) +h (n).
Как оказалось, данная стратегия является больше чем просто разумной: если эвристическая функция h(n) удовлетворяет некоторым условиям, то поиск А* становится и полным, и оптимальным.
Слайд 90

Условия оптимальности: допустимость и непротиворечивость An admissible heuristic is one that

Условия оптимальности: допустимость и непротиворечивость

An admissible heuristic is one that never

overestimates the cost to reach the goal. Because g(n) is the actual cost to reach n along the current path, and f(n)=g(n) + h(n), we have as an immediate consequence that f(n) never overestimates the true cost of a solution along the current path through n.
Admissible heuristics are by nature optimistic because they think the cost of solving the problem is less than it actually is. An obvious example of an admissible heuristic is the straight-line distance hSLD that we used in getting to Bucharest. Straight-line distance is admissible because the shortest path between any two points is a straight line, so the straight line cannot be an overestimate.
Слайд 91

Поиск А* Поиск А* является оптимальным, при условии, что h(n) представляет

Поиск А*

Поиск А* является оптимальным, при условии, что h(n) представляет собой

допустимую эвристическую функцию, т.е. при условии, что h(n) никогда не переоценивает стоимость достижения цели.
Допустимые эвристические функции являются по своей сути оптимистическими функциями, поскольку возвращают значения стоимости решения задачи, меньшие по сравнению с фактическими значениями стоимости.
А поскольку g(n) — точная стоимость достижения узла n, из этого непосредственно следует, что функция f (n) никогда не переоценивает истинную стоимость достижения решения через узел n.
Слайд 92

Consistent (непротиворечивые) heuristics A heuristic is consistent if for every node

Consistent (непротиворечивые) heuristics

A heuristic is consistent if for every node n,

every successor n' of n generated by any action a, the estimated cost of reaching the goal from n is no greater than the step cost of getting to n plus the estimated cost of reaching the goal from n:
h(n) ≤ c(n,a,n') + h(n')
If h is consistent, we have
f(n') = g(n') + h(n')
= g(n) + c(n,a,n') + h(n')
≥ g(n) + h(n)
= f(n)
i.e., f(n) is non-decreasing along any path.
This is a form of the general triangle inequality, which stipulates that each side of a triangle cannot be longer than the sum of the other two sides.
Слайд 93

Optimality of A* (proof) Suppose some suboptimal goal G2 has been

Optimality of A* (proof)

Suppose some suboptimal goal G2 has been generated

and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G.
f(G2) = g(G2) since h(G2) = 0
g(G2) > g(G) since G2 is suboptimal
f(G) = g(G) since h(G) = 0
f(G2) > f(G) from above
Слайд 94

Optimality of A* (proof) Suppose some suboptimal goal G2 has been

Optimality of A* (proof)

Suppose some suboptimal goal G2 has been generated

and is in the fringe. Let n be an unexpanded node in the fringe such that n is on a shortest path to an optimal goal G.
f(G2) > f(G) from above
h(n) ≤ h^*(n) since h is admissible
g(n) + h(n) ≤ g(n) + h*(n)
f(n) ≤ f(G)
Hence f(G2) > f(n), and A* will never select G2 for expansion
Слайд 95

Поиск А* Предположим, что на периферии поиска появился неоптимальный целевой узел

Поиск А*

Предположим, что на периферии поиска появился неоптимальный целевой узел G2,

а стоимость оптимального решения равна С*.
В таком случае, поскольку узел G2 неоптимален, a h(G2) =0 (это выражение справедливо для любого целевого узла), можно вывести следующую формулу: f(G2) = g(G2) + h(G2) = g(G2) > С*
Теперь рассмотрим периферийный узел n, который находится в оптимальном пути решения (если решение существует, то всегда должен быть такой узел).
Если функция h(n) не переоценивает стоимость завершения этого пути решения, то f(n) = g(n) + h(n) ≤ С*
f (n) ≤ C* < f(G2) ? узел G2 не развертывается и поиск А* должен вернуть оптимальное решение.
Слайд 96

Поиск А*

Поиск А*

Слайд 97

Поиск А*

Поиск А*

Слайд 98

Поиск А*

Поиск А*

Слайд 99

Поиск А*

Поиск А*

Слайд 100

Поиск А*

Поиск А*

Слайд 101

Поиск А*

Поиск А*

Слайд 102

Properties of A* Complete? Yes (unless there are infinitely many nodes

Properties of A*

Complete? Yes (unless there are infinitely many nodes with

f ≤ f(G) )
Time? Exponential
Space? Keeps all nodes in memory
Optimal? Yes
Слайд 103

Поиск А* Если С* представляет собой стоимость оптимального пути решения, то:

Поиск А*
Если С* представляет собой стоимость оптимального пути решения, то:
• в

поиске А* развертываются все узлы со значениями f(n)<С*;
• в поиске А* могут развертываться некоторые дополнительные узлы, находящиеся непосредственно на "целевом контуре" (где f(n) =С*), прежде чем будет выбран целевой узел.
Слайд 104

Эвристические функции h1(n) = количество фишек, стоящих не на своем месте.

Эвристические функции

h1(n) = количество фишек, стоящих не на своем месте.
h2(n)

= сумма расстояний всех фишек от их целевых позиций (манхэттенское расстояние).
h1(S) = ?
h2(S) = ?
Слайд 105

Эвристические функции h1(n) = количество фишек, стоящих не на своем месте.

Эвристические функции

h1(n) = количество фишек, стоящих не на своем месте.
h2(n)

= сумма расстояний всех фишек от их целевых позиций (манхэттенское расстояние).
h1(S) = ? 8
h2(S) = ? 3+1+2+2+2+3+3+2 = 18
Решение имеет длину 26 ходов.
Слайд 106

Сравнение алгоритмов поиска

Сравнение алгоритмов поиска

Слайд 107

Доминирование If h2(n) ≥ h1(n) for all n (both admissible) then

Доминирование

If h2(n) ≥ h1(n) for all n (both admissible)
then h2 dominates

h1
h2 is better for search
Typical search costs (average number of nodes expanded):
d=12 IDS = 3,644,035 nodes A*(h1) = 227 nodes A*(h2) = 73 nodes
d=24 IDS = too many nodes A*(h1) = 39,135 nodes A*(h2) = 1,641 nodes
Слайд 108

Поиск в условиях противодействия (Игры)

Поиск в условиях противодействия
(Игры)

Слайд 109

Game definition A game can be formally defined as a kind

Game definition

A game can be formally defined as a kind of

search problem with the following elements:
S0: The initial state, which specifies how the game is set up at the start.
PLAYER(s): Defines which player has the move in a state.
ACTIONS(s): Returns the set of legal moves in a state.
RESULT(s, a): The transition model, which defines the result of a move.
TERMINAL-TEST(s): A terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states.
UTILITY(s, p): A utility function (also called an objective function or payoff function), defines the final numeric value for a game that ends in terminal state s for a player p. A zero-sum game is defined as one where the total payoff to all players is the same for every instance of the game.
Слайд 110

Game tree (2-player, deterministic, turns)

Game tree (2-player, deterministic, turns)

Слайд 111

Minimax Perfect play for deterministic games Idea: choose move to position

Minimax

Perfect play for deterministic games
Idea: choose move to position with highest

minimax value = best achievable payoff against best play
E.g., 2-ply game:
Слайд 112

Minimax algorithm

Minimax algorithm

Слайд 113

Optimal decisions in multiplayer games

Optimal decisions in multiplayer games

Слайд 114

Properties of minimax Complete? Yes (if tree is finite) Optimal? Yes

Properties of minimax

Complete? Yes (if tree is finite)
Optimal? Yes (against an

optimal opponent)
Time complexity? O(bm)
Space complexity? O(bm) (depth-first exploration)
For chess, b ≈ 35, m ≈100 for "reasonable" games ? exact solution completely infeasible
Слайд 115

α-β pruning example

α-β pruning example

Слайд 116

α-β pruning example

α-β pruning example

Слайд 117

α-β pruning example

α-β pruning example

Слайд 118

α-β pruning example

α-β pruning example

Слайд 119

α-β pruning example

α-β pruning example

Слайд 120

Properties of α-β Pruning does not affect final result Good move

Properties of α-β

Pruning does not affect final result
Good move ordering improves

effectiveness of pruning
With "perfect ordering" time complexity = O(bm/2)
? doubles depth of search
Слайд 121

Why is it called α-β? α is the value of the

Why is it called α-β?

α is the value of the best

(i.e., highest-value) choice found so far at any choice point along the path for max
If v is worse than α, max will avoid it
? prune that branch
Define β similarly for min
Слайд 122

The α-β algorithm

The α-β algorithm

Слайд 123

Evaluation functions For chess, typically linear weighted sum of features Eval(s)

Evaluation functions

For chess, typically linear weighted sum of features
Eval(s) = w1

f1(s) + w2 f2(s) + … + wn fn(s)
e.g., w1 = 9 with
f1(s) = (number of white queens) – (number of black queens), etc.
Слайд 124

Планирование

Планирование

Слайд 125

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

Основы планирования

Планированием называется процесс выработки последовательности действий, позволяющих достичь цели.
Среда называется

средой классического планирования, если она является:
полностью наблюдаемой;
детерминированной;
конечной;
статической (изменения происходят только в результате действий агента);
дискретной (сточки зрения времени, действий, объектов и результатов).
В отличие от этого, неклассическое планирование предназначено для частично наблюдаемых или стохастических вариантов среды и для него требуется другой набор алгоритмов и проектов агентов.
Слайд 126

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

Задача планирования

Рассмотрим ситуацию, когда обычный агент, решающий задачи с помощью стандартных

алгоритмов поиска (поиска в глубину, поиска А* и т.д.), сталкивается с крупными задачами реального мира.
Сложность 1.
Агент, решающий задачи, может быть просто подавлен огромным количеством действий, не относящихся к делу.
Слайд 127

Задача планирования Рассмотрим задачу покупки одного экземпляра англоязычного издания настоящей книги

Задача планирования

Рассмотрим задачу покупки одного экземпляра англоязычного издания настоящей книги с

названием «AI: A Modern Approach» в электронном книжном магазине.
Предположим, что агент-покупатель должен совершить одно действие, связанное с покупкой, в расчете на каждый возможный десятицифровой номер ISBN, что приводит к общему количеству действий, равному 10 миллиардам. В ходе применения алгоритма поиска агент должен исследовать состояния результатов всех 10 миллиардов действий, чтобы определить, какое из них соответствует цели, заключающейся в том, чтобы приобрести экземпляр книги с номером ISBN 0137903952.
С другой стороны, разумный планирующий агент должен быть способным проработать процедуру покупки в обратном направлении, от явного описания цели, такого как Have{ISBN0137903952), и непосредственно сформировать действие Buy(ISBN013 7'903952). Для этого агенту требуется иметь общие знания о том, что действие Вuу(х) приводит к результату Have(x).
При наличии этих знаний и цели планировщик может определить в единственном шаге унификации, что правильным действием является Buy( ISBN013 7903952).
Слайд 128

Задача планирования Сложность 2. Определение хорошей эвристической функции. Пусть цель агента

Задача планирования

Сложность 2.
Определение хорошей эвристической функции.
Пусть цель агента – купить

четыре разных книги. Количество планов только для четырех этапов покупки будет составлять 10^40, поэтому поиск без точной эвристики даже нет смысла рассматривать.
Для человека хорошей эвристической оценкой для стоимости состояния является количество книг, которые еще предстоит купить;
Для агента, решающего задачи, это не столь очевидно, поскольку он рассматривает процедуру проверки цели как "черный ящик", который возвращает истину или ложь в ответ на каждое состояние. Поэтому агент, решающий задачи, не обладает автономностью; он требует, чтобы человек предоставлял ему эвристическую функцию для каждой новой задачи.
С другой стороны, если планирующий агент имеет доступ к явному представлению цели как конъюнкции подцелей, то может использовать единственную эвристику, независимую от проблемной области, — количество невыполненных конъюнктов. Для задачи покупки книг цель будет представлять собой выражение Have (А)^Have (В)^Have(С)^Have(D), а состояние, содержащее выражение Have(А) ^ Have(С), будет иметь стоимость 2. Таким образом, агент автоматически получает правильную эвристику для этой задачи и для многих других.
Слайд 129

Задача планирования Сложность 3. Неспособность к декомпозиции задачи. Например, задача доставки

Задача планирования

Сложность 3.
Неспособность к декомпозиции задачи.
Например, задача доставки множества пакетов

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

Планирование с помощью поиска в пространстве состояний а) прямой (прогрессивный) поиск

Планирование с помощью поиска в пространстве состояний

а) прямой (прогрессивный) поиск
б) обратный

(регрессивный) поиск в пространстве состояний
Слайд 131

Прямой поиск в пространстве состояний Формулировка задач планирования в виде задач

Прямой поиск в пространстве состояний

Формулировка задач планирования в виде задач поиска

в пространстве состояний:
Начальное состояние
Все действия, применимые в некотором состоянии
Проверка цели
Стоимость этапа (обычно =1).
Пример с 10 аэропортами, в каждом имеются 5 самолетов и 20 ед. груза. Цель – переместить все грузы из аэропорта A в B.
Слайд 132

Обратный поиск в пространстве состояний Основное преимущество – позволяет рассматривать только

Обратный поиск в пространстве состояний

Основное преимущество – позволяет рассматривать только релевантные

действия.
Действие релевантно конъюнктивной цели, если оно достигает одного из конъюнктов данной цели.
Пример с 10 аэропортами, в каждом имеются 5 самолетов и 20 ед. груза. Цель – переместить все грузы из аэропорта A в B.
At(C1, В) ^ At(C2, В) ^ ... ^ At(C20, В)
Рассматривая конъюнкт At(C1,B) и двигаясь в обратном направлении, можно найти действия, имеющие этот результат. Таковым является только одно действие: Unload(Cl, p, В), где самолет р не задан.
Кроме этого, имеются множество нерелевантных действий, способных привести к целевому состоянию.
Какие???
В рассматриваемой задаче грузовых воздушных перевозок имеется около 1000 действий, ведущих в прямом направлении из начального состояния, но только 20 действий, позволяющих перейти в обратном направлении от цели.
Слайд 133

Обратный поиск в пространстве состояний Поиск в обратном направлении называют регрессивным

Обратный поиск в пространстве состояний

Поиск в обратном направлении называют регрессивным планированием.


Основной вопрос регрессивного планирования – есть ли такие состояния, из которых применение некоторого действия приводит к цели?
Вычисление описаний таких состояний называется регрессией цели через действие.
Пример. Цель At(C1, В) ^ At(C2, В) ^ ... ^ At(C20, В) и релевантное действие Unload(Cl, p, В), которое позволяет достичь первого конъюнкта. Соответствующее действие будет выполнимо, только если выполнены его предусловия. Поэтому любое состояние-преемник должно включать эти предусловия: ln(Cl,p) ^ At (р, В). Более того, подцель At (Cl, В) не должна быть истинной в состоянии-преемнике (нерелевантные действия).
Поэтому описание состояния-преемника будет:
In(C1, р) ^ At(p, В) ^ At(C2, В) ^ ... ^ At(C20, В)
Кроме выполнения требования, чтобы действия достигали некоторого желаемого литерала, должно также соблюдаться требование, чтобы действия не отменяли какие-либо желаемые литералы.
Любое действие, удовлетворяющее этому ограничению, называется совместимым. Например, действие Load(C2,p) не будет совместимым с текущей целью, поскольку оно отрицает литерал At (С2, В).
Слайд 134

Обратный поиск в пространстве состояний Формирование преемников для обратного поиска. Допустим,

Обратный поиск в пространстве состояний

Формирование преемников для обратного поиска.
Допустим, что

при наличии описания цели G имеется действие А, которое является релевантным и совместимым. Соответствующий преемник может быть определен следующим образом:
Любые положительные результаты действия А, которые появляются в цели G, удаляются.
Добавляется каждый литерал предусловия А, если он еще не присутствует в определении действия.
Для осуществления обратного поиска могут использоваться любые из стандартных алгоритмов поиска. Завершение работы происходит после выработки такого описания преемника, которое соответствует начальному состоянию задачи планирования.
В случае использования логики первого порядка для обеспечения соответствия с начальным состоянием может потребоваться подстановка переменных в описание преемника.
Например, после подстановки {р/ Р12}: In(C1,P12)^At(P12,В)^At(C2,В)^…^ At(C20, В) Затем данная подстановка должна быть применена к действиям, ведущим из этого состояния к цели, что приводит к получению решения [ Unload(Cl, Р12, В) ].
Слайд 135

Планирование с частичным упорядочением Недостаток прямого и обратного поиска в пространстве

Планирование с частичным упорядочением

Недостаток прямого и обратного поиска в пространстве состояний

– рассматриваются только строго линейные последовательности действий, непосредственно связанные с начальным или целевым состоянием, что не позволяет воспользоваться преимуществами декомпозиции задачи.
Более предпочтительным является подход, позволяющий работать над несколькими подцелями независимо, достигать их с помощью нескольких субпланов, а затем объединять эти субпланы. Еще одно преимущество такого подхода – большая гибкость при определении последовательности, в которой составляется окончательный план, т.е. планировщик вначале может работать над "очевидными" или "важными" решениями, не будучи вынужденным прорабатывать все этапы в хронологическом порядке.
Например, планирующий агент, который находится в Беркли и желает попасть в Монте-Карло, может вначале попытаться найти рейс из Сан-Франциско в Париж; получив информацию о времени отправления и прибытия этого рейса, он может затем заняться поиском способов того, как доехать и выехать из соответствующих аэропортов.
Общая стратегия, в которой в процессе поиска выбор определенных этапов откладывается на более позднее время, называется стратегией с наименьшим вкладом (least commitment).
Слайд 136

Пример задачи с надеванием пары туфель Goal(RightShoeOn ^ LeftShoeOn) Init() Action(RightShoe,

Пример задачи с надеванием пары туфель

Goal(RightShoeOn ^ LeftShoeOn)
Init()
Action(RightShoe, Precond: RightSockOn, Effect:

RightShoeOn)
Action(RightSock, Effect: RightSockOn)
Action(LeftShoe, Precond: LeftSockOn, Effect: LeftShoeOn)
Action(LeftSock, Effect: LeftSockOn)
Слайд 137

Планирование с частичным упорядочением Любой алгоритм планирования, способный включить в план

Планирование с частичным упорядочением

Любой алгоритм планирования, способный включить в план два

действия без указания того, какое из них должно быть выполнено первым, называется планировщиком с частичным упорядочением (partial-order planner).
Слайд 138

Линеаризация плана с частичным упорядочением Решение с частичным упорядочением соответствует шести

Линеаризация плана с частичным упорядочением

Решение с частичным упорядочением соответствует шести возможным

планам с полным упорядочением; каждый из них называется линеаризацией плана с частичным упорядочением.
Слайд 139

Планирование с частичным упорядочением Планирование с частичным упорядочением может быть реализовано

Планирование с частичным упорядочением

Планирование с частичным упорядочением может быть реализовано в

виде поиска в пространстве планов с частичным упорядочением (далее просто "планами»).
Поиск начинается с пустого плана. После этого рассматриваются способы уточнения плана до тех пор, пока не удастся составить полный план, который решает данную задачу. Действия, рассматриваемые в этом поиске, являются не действиями в мире, а действиями в планах: добавление в план этапа; наложение упорядочения, согласно которому одно действие должно занять место перед другим; и т.д.
Состояниями рассматриваемой задачи поиска являются планы (в основном незаконченные).
Слайд 140

Компоненты плана Множество действий, из которых состоят этапы плана. Эти действия

Компоненты плана

Множество действий, из которых состоят этапы плана. Эти действия берутся

из множества действий в задаче планирования. "Пустой" план содержит только действия Start и Finish. Действие Start не имеет предусловий, а его результатом являются все литералы в начальном состоянии задачи планирования. Действие Finish не имеет результатов, а его предусловиями являются литералы цели в задаче планирования.
Множество ограничений упорядочения. Каждое ограничение упорядочения находится в форме А -< В, которая читается как "А перед В" и означает, что действие А должно быть выполнено в какое-то время перед действием В, но не обязательно непосредственно перед ним. Ограничения упорядочения должны описывать правильный вариант частичного упорядочения. Любой цикл (такой как А -< В и В -< А) представляет противоречие, поэтому ни одно ограничение упорядочения не может быть добавлено в план, если оно создает цикл.
Слайд 141

Компоненты плана Множество причинных связей. Причинная связь между двумя действиями А

Компоненты плана

Множество причинных связей. Причинная связь между двумя действиями А и

В в плане записывается как (“А достигает р для В”).
Например, в следующей причинной связи утверждается, что RightSockOn (надет правый носок) представляет собой результат действия RightSock и предусловие действия RightShoe. В ней также содержится утверждение, что предусловие RightSockOn должно оставаться истинным со времени действия RightSock до времени действия RightShoe. Другими словами, план не может быть дополнен путем добавления какого-либо нового действия С, которое конфликтует с причинной связью.
Действие С конфликтует со связью , если С имеет результат ¬p и если С может (в соответствии с ограничениями упорядочения) происходить после А и перед В. Некоторые авторы называют причинные связи интервалами защиты, поскольку связь защищает предусловие р от его отрицания в интервале от А до В.
Множество открытых предусловий. Предусловие является открытым, если оно не достигнуто с помощью какого-то действия в плане. Планировщики действуют по принципу сокращения множества открытых предусловий до пустого множества без внесения противоречия.
Слайд 142

Пример задачи с надеванием пары туфель

Пример задачи с надеванием пары туфель

Слайд 143

Согласованный план Cогласованный план (consistent plan) – план, в котором не

Согласованный план

Cогласованный план (consistent plan) – план, в котором не имеется

циклов в ограничениях упорядочения и нет конфликтов с причинными связями. Согласованный план без открытых предусловий представляет собой решение.
Слайд 144

Формулировка задачи планирования Начальный план содержит действия Start и Finish, ограничение

Формулировка задачи планирования

Начальный план содержит действия Start и Finish, ограничение упорядочения

Start -< Finish, не включает ни одной причинной связи и имеет все предусловия в действии Finish в качестве открытых предусловий.
Функция определения преемника произвольным образом выбирает одно открытое предусловие р действия В и вырабатывает план-преемник для каждого возможного согласованного способа выбора действия А, которое достигает р. Согласованность обеспечивается принудительно следующим образом.
1. Причинная связь и ограничение упорядочения А -< В добавляются к плану. Действие А может быть существующим действием в плане или новым действием. Если оно является новым, добавить его к плану, а также добавить Start -< А и А -< Finish.
2. Разрешаются конфликты между новой причинной связью и всеми существующими действиями, а также между действием А (если оно является новым) и всеми существующими причинными связями. Конфликт между и С разрешается путем обеспечения того, чтобы действие С происходило в какое-то время за пределами интервала защиты, либо за счет добавления ограничения В -< С, либо путем добавления ограничения С-<А. Для одного из них или обоих добавляются состояния-преемники, если они приводят к созданию согласованных планов.
Слайд 145

Формулировка задачи планирования В ходе проверки цели осуществляется проверка того, является

Формулировка задачи планирования

В ходе проверки цели осуществляется проверка того, является ли

текущий план решением первоначальной задачи планирования. Поскольку вырабатываются только согласованные планы, в проверке цели достаточно только проконтролировать, есть ли еще открытые предусловия.
Слайд 146

Пример планирования с частичным упорядочением Пример задачи замены колеса со стертой покрышкой

Пример планирования с частичным упорядочением

Пример задачи замены колеса со стертой покрышкой

Слайд 147

Пример планирования с частичным упорядочением Поиск решения начинается с начального плана,

Пример планирования с частичным упорядочением

Поиск решения начинается с начального плана, содержащего

действие Start с результатом At (Spare, Тrunk) ^ At (Flat, Axle) и действие Finish с единственным предусловием At (Spare, Axle).
Затем вырабатываются преемники путем взятия открытого предусловия для его проработки (не допускающей отмены) и выбора среди возможных действий для его достижения.
1. Взять единственное открытое предусловие, At (Spare, Axle), действия Finish. Выбрать единственное применимое действие, PutOn( Spare, Axle).
2. Взять предусловие At (Spare, Ground) действия PutOn(Spare, Axle). Выбрать единственное применимое действие, Remove (Spare, Trunk), чтобы достичь его.
Слайд 148

Пример планирования с частичным упорядочением 3. Взять предусловие ¬At (Flat, Axle)

Пример планирования с частичным упорядочением

3. Взять предусловие ¬At (Flat, Axle) действия

PutOn(Spare, Axle). Просто для того чтобы поступить вопреки здравому смыслу, выберем действие LeaveOvernight, а не действие Remove (Flat, Axle). Действие LeaveOvernight также имеет результат ¬At(Spare, Ground), который означает, что оно конфликтует со следующей причинной связью:
Remove(Spare, Trunk) PutOn (Spare, Axle)
Чтобы разрешить этот конфликт, добавим ограничение упорядочения, которое помещает действие LeaveOvernight перед действием Remove(Spare, Trunk).
Слайд 149

Пример планирования с частичным упорядочением 4. В этот момент единственным оставшимся

Пример планирования с частичным упорядочением

4. В этот момент единственным оставшимся открытым

предусловием является предусловие At (Spare, Trunk) действия Remove (Spare, Trunk). Единственным действием, позволяющим достичь этого предусловия, является существующее действие Start, но причинная связь от Start к Remove(Spare, Trunk) конфликтует с результатом ¬At (Spare, Trunk) действия LeaveOvernight. В данный момент не существует способа разрешить конфликт с действием LeaveOvernight — его нельзя переупорядочить таким образом, чтобы оно находилось перед Start (поскольку ни одно действие не может происходить перед действием Start), и нельзя переупорядочить его так, чтобы оно находилось после Remove(Spare,Trunk) (поскольку уже имеется ограничение, которое упорядочивает его перед Remove(Spare,Trunk)). Поэтому необходимо вернуться к одному из предыдущих состояний, удалить действие LeaveOvernight и две последние причинные связи, возвратившись в состояние
Планировщик фактически доказал, что действие LeaveOvernight не может применяться в качестве способа замены колеса.
Слайд 150

Пример планирования с частичным упорядочением 5. Еще раз рассмотрим предусловие ¬At(Flat,Axle)

Пример планирования с частичным упорядочением

5. Еще раз рассмотрим предусловие ¬At(Flat,Axle) действия

PutOn(Spare, Axle). На этот раз выберем действие Remove (Flat, Axl е).
6. Снова возьмем предусловие At (Spare, Trunk) действия Remove(Spare,Trunk) и выберем действие Start, чтобы его достичь. На сей раз конфликты не возникают.
7. Возьмем предусловие At (Flat, Axle) действия Remove (Flat, Axle) и выберем действие Start для его достижения. Это дает нам полный согласованный план или решение.
Слайд 151

Планирование действий в пространстве задач При решении сложных задач пользуются разбиением

Планирование действий в пространстве задач

При решении сложных задач пользуются разбиением на

подзадачи.
Цель разбиения – прийти к решению совокупности элементарных (решающихся за 1 шаг перебора в пространстве состояний или решения которых известны) задач.
Описание задачи в пространстве состояний – тройка (S, F, G):
S - множество начальных состояний,
F - множество операторов, отображающих описание состояний,
G - множество целевых состояний.
Слайд 152

Планирование действий в пространстве задач Пример Маккарти. Ханойские башни. 3 колышка

Планирование действий в пространстве задач

Пример Маккарти. Ханойские башни.
3 колышка (1

2 3) и 3 диска (A,B,C).
3 подзадачи:
A A (1) (1, 1, 1) -> (1, 2, 2) (B)
B -> B Имя: (А) (2) (1, 2, 2) -> (3, 2, 2) Имя: (C)
C _ _ C (3) (3, 2, 2) -> (3, 3, 3) (D)
1 2 3 1 2 3.
Задача (2)-элементарная, (1) и (3) следует свести к совокупности элементарных.
В практических целях представления задач выполняют на графоподобных структурах.
Слайд 153

Планирование действий в пространстве задач Заключительные вершины соответствуют элементарным задачам.

Планирование действий в пространстве задач

Заключительные вершины соответствуют элементарным задачам.

Слайд 154

Применение ключевых операторов Пусть (S, F, G) – описание исходной задачи

Применение ключевых операторов

Пусть (S, F, G) – описание исходной задачи в

пространстве состояний,
g1, …, gn – последовательность промежуточных состояний, которые удалось выделить.
Необходимо свести задачу (S, F, G) к множеству подзадач (S, F, {g1}), ({g1}, F, {g2}), …, ({gn}, F, G). (1)
Различают 2 случая:
Состояние gi (i = 1÷n) определяется явно => подзадачи решаются в произвольном порядке.
gi (i = 1÷n) определяется неявно, например, ∃ множество Gi (i = 1÷n) ∀ элемент может служить в качестве основного промежуточного состояния gi. Тогда задача (S, F, Gi) должна быть решена раньше чем ({gi}, F, Gi+1).
Решая задачу в пространстве состояний, требуется определить решающую цепочку операторов.
Нахождение всей цепочки – сложная задача, но всегда можно выделить необходимый шаг решения.
Для определения основного промежуточного состояния можно пользоваться так называемыми «ключевыми операторами» (КО).
Обозначим f ∈ F КО для задачи (S, F, G).
Пусть Gf - множество состояний, к которым применим f.
Тогда первой следующей за (S, F, G) задачей будет (S, F, Gf).
Решая ее определяют основное состояние g ∈ Gf, и тогда можно сформулировать элементарную задачу:
({g}, F, {f(g)}), где f(g) = состояние, достигаемое применением f к g. (*)
Т.о. осталось решить задачу ({f(g)}, F, G).
Графическое представление сведения задачи к подзадачам с использованием КО
(без указания элементарной задачи (*) ):
(S, F, G) /\
/--\
/ f \
(S, F, Gf) ({f(g)}, F, G)
На следующем шаге находят КО задачи (S,F,Gf) и т.д.
В результате – последовательность промежуточных состояний g1,…,gn.
Слайд 155

Задача об обезьяне и банане (I) А - первоначальное нахождение обезьяны.

Задача об обезьяне и банане (I)

А - первоначальное нахождение обезьяны.
B

- первоначальное нахождение ящика.
С - точка над которой к потолку подвешены бананы.
А, В, С – точки в горизонтальной плоскости 3D-евклидова пространства.
Предполагается, что обезьяна может :
Подойти к ящику.
Переместить ящик в точку C.
Взобраться на ящик.
Сорвать бананы.
Слайд 156

Задача об обезьяне и банане (2) Решение. Очевидно, F = {f1,

Задача об обезьяне и банане (2)

Решение.
Очевидно, F = {f1, f2, f3,

f4}.
Действия и условия применимости операторов задаются в виде продукций:
fi(x1, x2, x3, x4) --> (y1, y2, y3, y4), где --> моделирует действие.
x1 – положение обезьяны (на полу).
x2 – { 1: обезьяна на ящике, 0: не на ящике.
x3 – положение ящика (на полу).
x4 – { 1: обезьяна сорвала бананы, 0: нет.
S = {(A, 0, B, 0)},
G = {(C, 1, C, 1)}.
Слайд 157

Задача об обезьяне и банане (3) Конструируем правила переписывания: Подойти(y1) f1(x1,

Задача об обезьяне и банане (3)

Конструируем правила переписывания:
Подойти(y1) f1(x1, 0, x3, x4)

--> (y1, 0, x3, x4)
Передвинуть(α) f2(x1, 0, x1, x4) --> ( α, 0, α, x4)
Взобраться f3(x1, 0, x1, x4) --> (x1, 1, x1, x4)
Сорвать f4(x1, 1, x1, 0 ) --> (x1, 1, x1, 1 )
Описание исходной задачи имеет вид: ({(A, 0, B, 0)},F,{(C, 1, C, 1)})
Зададим связи между возможными КО и различиями:
Если (x1 ≠ B) то применить f1.
Если (x3 ≠ C) то применить f2.
Если (x2 ≠ 1) то применить f3.
Если (x4 ≠ 1) то применить f4.
Слайд 158

Задача об обезьяне и банане (4) Шаг 1. Вычислить различия для

Задача об обезьяне и банане (4)

Шаг 1. Вычислить различия для исходной

задачи.
Основной признак целевого состояния x4 = 1. В списке {(A, 0, B, 0)}: х4 = 0.
Уменьшить это различие может оператор f4 => f4 – КО.
Для исходной задачи получим пару подзадач:
({(A, 0, B, 0)}, F, G) /\
/--\
/ f4 \
({(A, 0, B, 0)}, F, Gf4) ({f4(S1)}, F, G)
где S1 ∈ Gf4 – множеству состояний, к которым применим оператор f4.
Решая левую задачу найдем S1 – состояние, получаемое в результате решения левой подзадачи.
Состояние из Gf4 описывается уcловиями:
обезьяна в точке С.
ящик в точке С.
Обезьяна на ящике.
Шаги 2,3,4:… - самостоятельно.
Слайд 159

Планирование иерархической сети задач Метод планирования HTN (Hierarchical Task Network) рассматривает

Планирование иерархической сети задач

Метод планирования HTN (Hierarchical Task Network) рассматривает первоначальный

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

Планирование иерархической сети задач

Планирование иерархической сети задач

Слайд 161

Мультиагентное планирование Задача игры в парный теннис. Два агента играют в

Мультиагентное планирование

Задача игры в парный теннис. Два агента играют в одной

команде и могут присутствовать в одном из четырех мест:
[Left,Baseline] (слева, у задней линии),
[Right, Baseline] (справа, у задней линии),
[Left, Net] (слева, под сеткой) и
[Right, Net] (справа, под сеткой).
Мяч может быть отбит, если в нужном месте находится один и только один игрок
Цель – отбить мяч и обеспечить, чтобы хотя бы один из них играл под сеткой.
Слайд 162

Мультиагентное планирование Решением мультиагентной задачи планирования является совместный план (joint plan),

Мультиагентное планирование

Решением мультиагентной задачи планирования является совместный план (joint plan), состоящий

из действий для каждого агента. Совместный план представляет собой решение, если цель будет достигнута при условии, что каждый агент выполнит назначенные ему действия. Решением данной задачи игры в теннис является план:
Plan 1:
A: [Go(A, [Right, Baseline]), Hit(A, Ball)]
В: [NoOp(B), NoOp(B)]
Если оба агента имеют одинаковую базу знаний и если это решение является единственным, то все сложится идеально; каждый из агентов сможет определить это решение, а затем совместно выполнить его. Но к большому сожалению для этих агентов существует другой план, позволяющий так же успешно достичь цели, как и первый:
Plan 2:
A: [Go(A, [Left, Net]), NoOp(A)]
В: [Go(В, [Right, Baseline]), Hit(B, Ball)]
Слайд 163

Мультиагентное планирование Решение проблемы – координация

Мультиагентное планирование

Решение проблемы – координация

Слайд 164

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

Механизмы кординации

Простейший метод, с помощью которого группа агентов может обеспечить координацию

при выполнении совместного плана, состоит в принятии определенного соглашения (convention) до начала совместной деятельности. Соглашением является любое ограничение, касающееся выбора совместных планов, выходящее за рамки основного ограничения, в соответствии с которым совместный план должен работать, если ему следуют все агенты. Например, соглашение "придерживаться своей стороны поля" станет причиной того, что партнеры в парном теннисе выберут план 2, а соглашение, что "один игрок всегда остается у сетки", приведет их к плану 1.
Некоторые соглашения, такие как вождение по правильной стороне дороги, приняты настолько широко, что считаются общественными законами. Естественные языки также могут рассматриваться как соглашения.
Более общий подход состоит в использовании соглашений, независимых от проблемной области. Если каждый агент эксплуатирует один и тот же алгоритм планирования с одними и теми же входными данными, то может следовать соглашению о выполнении первого найденного осуществимого плана и быть уверенным в том, что другие агенты сделают такой же выбор. Более надежная, но и более дорогостоящая стратегия – выработать все совместные планы, а затем выбрать, тот из них, внешнее представление для вывода на печать которого находится на первом месте в алфавитном порядке.
Слайд 165

Механизмы кординации Модель поведения птицеподобного агента (который иногда именуется орнитоидом или

Механизмы кординации

Модель поведения птицеподобного агента (который иногда именуется орнитоидом или боидом

от слова boid, или birdoid) выполняет три перечисленных ниже правила, применяя определенный метод их комбинирования:
1. Отделение. Направлять свой полет подальше от соседей, если ты начинаешь
к ним слишком заметно приближаться.
2. Соединение в линию. Придерживаться направления полета, позволяющего
занять среднюю позицию по отношению к соседям.
3. Выравнивание. Рулить в сторону средней ориентации (направления
движения) соседей.
Если все птицы выполняют одни и те же описанные выше правила, то вся стая обнаруживает эмерджентное поведение (от слова emergent— появляющийся), совершая полет в виде одного псевдоустойчивого тела приблизительно с постоянной плотностью, которое не рассеивается со временем.
Слайд 166

Механизмы кординации При отсутствии применимого соглашения агенты могут использовать общение для

Механизмы кординации

При отсутствии применимого соглашения агенты могут использовать общение для получения

общих знаний об осуществимом совместном плане. Например, в парном теннисе игрок может крикнуть "Мой!" или "Твой!", имея в виду мяч, чтобы указать на предпочтительный для него совместный план.
Один игрок может неявно сообщить о предпочтительном совместном плане другому, просто выполнив его первую часть. В нашей задаче игры в теннис, если агент А направился к сетке, то агент B обязан отойти назад, к линии подачи, чтобы отбить мяч, поскольку план 2 является единственным совместным планом, который начинается с того, что агент А направляется к сетке. Такой подход к координированию действия, иногда называемый распознаванием плана (plan recognition), является применимым, если для безошибочного определения нужного совместного плана достаточно одного действия (или краткой последовательности действий).
Слайд 167

Многоагентная система – это система, в которой несколько взаимодействующих интеллектуальных агентов


Многоагентная система – это система, в которой несколько взаимодействующих интеллектуальных агентов

пытаются совместно достичь некоторый набор целей или выполнить некоторый набор задач (“Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence”, MIT, 1999)
Слайд 168

Свойства интеллектуального агента Агенты — это активные объекты (программные модули), которые

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

Агенты — это активные объекты (программные модули), которые могут

инициировать целенаправленную деятельность по восприятию среды и воздействию на неё.
Интеллектуальные агенты обладают следующими «ментальными» свойствами (или их подмножеством):
знания (knowledge)-постоянные, неизменяемые в процессе функционирования знания агента о себе, среде и других агентах;
убеждения (beliefs)-знания агента о среде (в том числе, о других агентах), которые могут стечением времени изменяться и становиться неверными;
желания (desires)-состояния, которых агент желает достичь (могут быть противоречивыми), аналогичны целям;
намерения (intentions)-действия, которые собирается выполнить вследствие своих желаний или в силу взятых на себя обязательств;
обязательства (commitments)-задачи, решение которых агент берет на себя в рамках кооперации с другими агентами по их просьбе или поручению.
Слайд 169

Принципы конструирования агента на основе спецификаций FIPA FIPA (FOUNDATION FOR INTELLIGENT

Принципы конструирования агента на основе спецификаций FIPA

FIPA (FOUNDATION FOR INTELLIGENT

PHYSICAL AGENTS) –Международная федерация по разработке интеллектуальных физических агентов
Слайд 170

Пример взаимодействия агентов (1): отдыхающим назначена одна и та же процедура

Пример взаимодействия агентов (1): отдыхающим назначена одна и та же процедура

Входные

данные:
Для отдыхающего № 1 назначено две процедуры типа Процедура № 1. Для отдыхающего № 2 назначена одна процедура того же типа.
График работы процедурного кабинета: 8.00-9.00, 9.00-10.00, 10.00-11.00

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

Слайд 171

Пример взаимодействия агентов (2): отдыхающим назначены разные процедуры Входные данные: Для

Пример взаимодействия агентов (2): отдыхающим назначены разные процедуры

Входные данные:
Для отдыхающего № 1

назначено две процедуры типа Процедура № 1. Для отдыхающего № 2 назначено две процедуры типа Процедура № 2.
Графики работ процедурных кабинетов:
Процедура №1 8.00-9.00, 9.00-10.00
Процедура №2 8.00-9.00, 9.00-10.00
Слайд 172

Пример взаимодействия агентов (3): отдыхающим назначены две одинаковые процедуры Входные данные:

Пример взаимодействия агентов (3): отдыхающим назначены две одинаковые процедуры

Входные данные: Для отдыхающих

№ 1 и № 2 назначено две разных процедуры
типа Процедура № 1 и Процедура № 2.
Графики работ процедурных кабинетов:
Процедура №1 8.00-9.00, 9.00-10.00
Процедура №2 8.00-9.00, 9.00-10.00