Содержание
- 2. Литература Рассел С., Норвиг П. Искусственный интеллект: современный подход. – М.: Вильямс, 2006. – 1408 с.
- 3. Предыстория ИИ Философия основы ИИ, сформулировав идеи, что мозг в определенных отношениях напоминает машину, оперирует знаниями,
- 4. Краткая история ИИ 1943 McCulloch & Pitts: Boolean circuit model of brain 1950 Turing's "Computing Machinery
- 5. Что такое ИИ?
- 6. Системы, которые действуют подобно людям Turing (1950) "Computing machinery and intelligence": Возможности, которыми должен обладать компьютер:
- 7. Системы, которые думают подобно людям Существует 3 способа узнать, как думает человек: интроспекция — попытка проследить
- 8. Системы, которые думают рационально Аристотель – законы «правильного мышления». Его силлогизмы стали образцом для создания процедур
- 9. Системы, которые действуют рационально Агентом считается все, что действует («агент» произошло от латинского «agere», действовать).Рациональный агент
- 10. Системы, которые действуют рационально Преимущества подхода: более общий по сравнению с подходом на основе «законов мышления»,
- 11. Различные подходы к построению систем ИИ Логический Структурный Эволюционный Имитационный Агентно-ориентированный подход
- 12. Логический подход Основа - Булева алгебра и исчисление предикатов. Практически каждая система ИИ, построенная на логическом
- 13. Структурный подход Попытки построения ИИ путем моделирования структуры человеческого мозга. Одной из первых таких попыток был
- 14. Эволюционный подход Основное внимание уделяется построению начальной модели и правилам, по которым она может изменяться (эволюционировать).
- 15. Имитационный подход Это классический подход для кибернетики с одним из ее базовых понятий — "черным ящиком".
- 16. Агентно-ориентированный подход Основан на использовании интеллектуальных (рациональных) агентов. Интеллект — это вычислительная часть (грубо говоря, планирование)
- 17. Современное состояние разработок Robotic vehicles: A driverless robotic car named STANLEY sped through the rough terrain
- 18. Умные машины: до "судного дня" осталось недолго (http://top.rbc.ru/economics/31/01/2013/842964.shtml)
- 19. Живое железо Сегодня появление таких технологических новинок, как распознающий движения контроллер Kinect от Microsoft, на некоторое
- 20. Картинка на ощупь Уже в ближайшие пять лет, уверены разработчики из IBM, компьютеры совершат мощный прорыв
- 21. Пиксель знает Разработчики IBM сетуют, что компьютеры сегодня понимают смысл изображения только по текстовым тегам и
- 22. Ухо искусственного разума У человеческого слухового аппарата тоже в скором времени появится компьютерный конкурент. В течение
- 23. Компьютер-поварешка Исследователи IBM уверены: здоровая пища должна быть вкусной! Они разрабатывают компьютерную систему - по сути,
- 24. Лови мое дыхание …И вот опять простуда. И вроде бы Минздрав предупреждал, и старались обходить стороной
- 25. Человек-проводник Разработчики IT-инноваций постоянно твердят о сближении виртуального мира и реального, об очеловечивании машины. Но такая
- 26. Интеллектуальные агенты
- 27. Агенты и варианты среды Агентом является все, что может рассматриваться как воспринимающее свою среду с помощью
- 28. Агенты и варианты среды Термин «восприятие» используется для обозначения полученных агентом сенсорных данных в любой конкретный
- 29. Пример. Мир пылесоса Восприятие: местоположение (в каком квадрате он находится); состояние квадрата (есть ли мусор в
- 30. Качественное поведение: концепция рациональности Рациональным агентом является такой агент, который выполняет правильные действия; или более формально,
- 31. Показатели производительности Показатели производительности воплощают в себе критерии оценки успешного поведения агента. Последовательность действий агента вынуждает
- 32. Агент-пылесос Показатель производительности??? Рекомендация: лучше всего разрабатывать показатели производительности в соответствии с тем, чего действительно необходимо
- 33. Рациональность Зависит от следующих факторов: • Показатели производительности, которые определяют критерии успеха. • Знания агента о
- 34. Всезнание, обучение и автономность 1. Необходимо различать рациональность и всезнание. Рациональность — это максимизация ожидаемой производительности,
- 35. Определение проблемной среды Факторы, определяющие проблемную среду: производительность; среда; исполнительные механизмы; датчики. PEAS (Performance measure, Environment,
- 36. Примеры типов агентов и их описаний
- 37. Свойства проблемной среды • Полностью наблюдаемая или частично наблюдаемая (если датчики агента предоставляют ему доступ к
- 38. Свойства проблемной среды • Статическая или динамическая (если среда может измениться в ходе того, как агент
- 39. Какова среда реального мира? Полностью наблюдаемая или частично наблюдаемая? Детерминированная или стохастическая? Эпизодическая или последовательная? Статическая
- 40. Недостаток: Если P – множество актов восприятия, T – срок существования агента (общее количество актов восприятия,
- 41. Простые рефлексные агенты Агенты выбирают действия на основе текущего акта восприятия, игнорируя всю остальную историю актов
- 42. Простые рефлексные агенты Недостаток – агент работает, только если правильное решение может быть принято на основе
- 43. Рефлексные агенты, основанные на модели Агент поддерживает внутреннее состояние, которое зависит от истории актов восприятия. Программа
- 44. Рефлексные агенты, основанные на модели
- 45. Агенты, основанные на цели
- 46. Агенты, основанные на полезности Функция полезности отображает состояние (или последовательность состояний) на вещественное число, которое обозначает
- 47. Обучающиеся агенты Основные компоненты: обучающийся компонент – отвечает за внесение усовершенствований; производительный компонент – обеспечивает выбор
- 48. Решение проблем посредством поиска
- 49. Агенты, решающие задачи Разновидность агентов, основанных на цели. Цели позволяют организовать поведение, ограничивая выбор промежуточных этапов,
- 50. Пример. Выходные в Румынии Currently in Arad. Flight leaves tomorrow from Bucharest Formulate goal: be in
- 51. Пример. Выходные в Румынии
- 52. Основные определения Процесс определения последовательности действий, которые приводят к достижению цели, называется поиском. Любой алгоритм поиска
- 53. Хорошо структурированные задачи и решения Задача может быть формально определена с помощью следующих компонентов: Начальное состояние,
- 54. Хорошо структурированные задачи и решения Проверка цели, позволяющая определить, является ли данное конкретное состояние целевым состоянием.
- 55. Пространство состояний для мира пылесоса
- 56. Мир пылесоса Состояния. Агент находится в одном из двух местонахождений, в каждом из которых может присутствовать
- 57. Задача игры в восемь Задача игры в восемь имеет 9!/2 = 181 440 достижимых состояний и
- 58. Поиск решений
- 59. Представление узлов State. Состояние в пространстве состояний, которому соответствует данный узел. Parent-Node. Узел в дереве поиска,
- 60. Представление узлов Коллекция узлов, которые были сформированы, но еще не развернуты, называется периферией. Каждый элемент периферии
- 61. Измерение производительности решения задачи Полнота. Гарантирует ли алгоритм обнаружение решения, если оно имеется? Оптимальность. Обеспечивает ли
- 62. Стратегии неинформированного поиска Uninformed search strategies use only the information available in the problem definition. Breadth-first
- 63. Uninformed search strategies A search strategy is defined by picking the order of node expansion Strategies
- 64. Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue, i.e., new successors go at
- 65. Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue, i.e., new successors go at
- 66. Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue, i.e., new successors go at
- 67. Breadth-first search Expand shallowest unexpanded node Frontier is a FIFO queue, i.e., new successors go at
- 68. Breadth-first search
- 69. Properties of breadth-first search Complete? Yes (if b is finite) Time? 1+b+b2+b3+… +bd + b(bd-1) =
- 70. Uniform-cost search Expand least-cost unexpanded node Frontier is a queue ordered by path cost Equivalent to
- 71. 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 with loops Modify to avoid
- 73. Depth-limited search = depth-first search with depth limit l, i.e., nodes at depth l have no
- 74. Iterative deepening search
- 75. Iterative deepening search
- 76. Iterative deepening search
- 77. Iterative deepening search
- 78. Iterative deepening search
- 79. Properties of iterative deepening search Complete? Yes Time? (d+1)b0 + d b1 + (d-1)b2 + …
- 80. Comparing uninformed search strategies
- 81. Стратегии информированного (эвристического) поиска Помимо определения задачи используются знания, относящиеся к данной к данной конкретной проблемной
- 82. Жадный поиск по первому наилучшему совпадению Предпринимаются попытки развертывания узла, который рассматривается как ближайший к цели
- 83. Пример. Выходные в Румынии
- 84. Этапы жадного поиска пути до Бухареста
- 85. Этапы жадного поиска пути до Бухареста
- 86. Этапы жадного поиска пути до Бухареста
- 87. Этапы жадного поиска пути до Бухареста Найденное решение не оптимально: путь до Бухареста через города Сибиу
- 88. Свойства жадного поиска по наилучшему совпадению Complete? No – can get stuck in loops, e.g., Iasi
- 89. Поиск А* f(n) = g(n) + h(n) f(n) – оценка стоимости наименее дорогостоящего пути решения, проходящего
- 90. Условия оптимальности: допустимость и непротиворечивость An admissible heuristic is one that never overestimates the cost to
- 91. Поиск А* Поиск А* является оптимальным, при условии, что h(n) представляет собой допустимую эвристическую функцию, т.е.
- 92. Consistent (непротиворечивые) heuristics A heuristic is consistent if for every node n, every successor n' of
- 93. Optimality of A* (proof) Suppose some suboptimal goal G2 has been generated and is in the
- 94. Optimality of A* (proof) Suppose some suboptimal goal G2 has been generated and is in the
- 95. Поиск А* Предположим, что на периферии поиска появился неоптимальный целевой узел G2, а стоимость оптимального решения
- 96. Поиск А*
- 97. Поиск А*
- 98. Поиск А*
- 99. Поиск А*
- 100. Поиск А*
- 101. Поиск А*
- 102. Properties of A* Complete? Yes (unless there are infinitely many nodes with f ≤ f(G) )
- 103. Поиск А* Если С* представляет собой стоимость оптимального пути решения, то: • в поиске А* развертываются
- 104. Эвристические функции h1(n) = количество фишек, стоящих не на своем месте. h2(n) = сумма расстояний всех
- 105. Эвристические функции h1(n) = количество фишек, стоящих не на своем месте. h2(n) = сумма расстояний всех
- 106. Сравнение алгоритмов поиска
- 107. Доминирование If h2(n) ≥ h1(n) for all n (both admissible) then h2 dominates h1 h2 is
- 108. Поиск в условиях противодействия (Игры)
- 109. Game definition A game can be formally defined as a kind of search problem with the
- 110. Game tree (2-player, deterministic, turns)
- 111. Minimax Perfect play for deterministic games Idea: choose move to position with highest minimax value =
- 112. Minimax algorithm
- 113. Optimal decisions in multiplayer games
- 114. Properties of minimax Complete? Yes (if tree is finite) Optimal? Yes (against an optimal opponent) Time
- 115. α-β pruning example
- 116. α-β pruning example
- 117. α-β pruning example
- 118. α-β pruning example
- 119. α-β pruning example
- 120. Properties of α-β Pruning does not affect final result Good move ordering improves effectiveness of pruning
- 121. Why is it called α-β? α is the value of the best (i.e., highest-value) choice found
- 122. The α-β algorithm
- 123. Evaluation functions For chess, typically linear weighted sum of features Eval(s) = w1 f1(s) + w2
- 124. Планирование
- 125. Основы планирования Планированием называется процесс выработки последовательности действий, позволяющих достичь цели. Среда называется средой классического планирования,
- 126. Задача планирования Рассмотрим ситуацию, когда обычный агент, решающий задачи с помощью стандартных алгоритмов поиска (поиска в
- 127. Задача планирования Рассмотрим задачу покупки одного экземпляра англоязычного издания настоящей книги с названием «AI: A Modern
- 128. Задача планирования Сложность 2. Определение хорошей эвристической функции. Пусть цель агента – купить четыре разных книги.
- 129. Задача планирования Сложность 3. Неспособность к декомпозиции задачи. Например, задача доставки множества пакетов почты по соответствующим
- 130. Планирование с помощью поиска в пространстве состояний а) прямой (прогрессивный) поиск б) обратный (регрессивный) поиск в
- 131. Прямой поиск в пространстве состояний Формулировка задач планирования в виде задач поиска в пространстве состояний: Начальное
- 132. Обратный поиск в пространстве состояний Основное преимущество – позволяет рассматривать только релевантные действия. Действие релевантно конъюнктивной
- 133. Обратный поиск в пространстве состояний Поиск в обратном направлении называют регрессивным планированием. Основной вопрос регрессивного планирования
- 134. Обратный поиск в пространстве состояний Формирование преемников для обратного поиска. Допустим, что при наличии описания цели
- 135. Планирование с частичным упорядочением Недостаток прямого и обратного поиска в пространстве состояний – рассматриваются только строго
- 136. Пример задачи с надеванием пары туфель Goal(RightShoeOn ^ LeftShoeOn) Init() Action(RightShoe, Precond: RightSockOn, Effect: RightShoeOn) Action(RightSock,
- 137. Планирование с частичным упорядочением Любой алгоритм планирования, способный включить в план два действия без указания того,
- 138. Линеаризация плана с частичным упорядочением Решение с частичным упорядочением соответствует шести возможным планам с полным упорядочением;
- 139. Планирование с частичным упорядочением Планирование с частичным упорядочением может быть реализовано в виде поиска в пространстве
- 140. Компоненты плана Множество действий, из которых состоят этапы плана. Эти действия берутся из множества действий в
- 141. Компоненты плана Множество причинных связей. Причинная связь между двумя действиями А и В в плане записывается
- 142. Пример задачи с надеванием пары туфель
- 143. Согласованный план Cогласованный план (consistent plan) – план, в котором не имеется циклов в ограничениях упорядочения
- 144. Формулировка задачи планирования Начальный план содержит действия Start и Finish, ограничение упорядочения Start - Функция определения
- 145. Формулировка задачи планирования В ходе проверки цели осуществляется проверка того, является ли текущий план решением первоначальной
- 146. Пример планирования с частичным упорядочением Пример задачи замены колеса со стертой покрышкой
- 147. Пример планирования с частичным упорядочением Поиск решения начинается с начального плана, содержащего действие Start с результатом
- 148. Пример планирования с частичным упорядочением 3. Взять предусловие ¬At (Flat, Axle) действия PutOn(Spare, Axle). Просто для
- 149. Пример планирования с частичным упорядочением 4. В этот момент единственным оставшимся открытым предусловием является предусловие At
- 150. Пример планирования с частичным упорядочением 5. Еще раз рассмотрим предусловие ¬At(Flat,Axle) действия PutOn(Spare, Axle). На этот
- 151. Планирование действий в пространстве задач При решении сложных задач пользуются разбиением на подзадачи. Цель разбиения –
- 152. Планирование действий в пространстве задач Пример Маккарти. Ханойские башни. 3 колышка (1 2 3) и 3
- 153. Планирование действий в пространстве задач Заключительные вершины соответствуют элементарным задачам.
- 154. Применение ключевых операторов Пусть (S, F, G) – описание исходной задачи в пространстве состояний, g1, …,
- 155. Задача об обезьяне и банане (I) А - первоначальное нахождение обезьяны. B - первоначальное нахождение ящика.
- 156. Задача об обезьяне и банане (2) Решение. Очевидно, F = {f1, f2, f3, f4}. Действия и
- 157. Задача об обезьяне и банане (3) Конструируем правила переписывания: Подойти(y1) f1(x1, 0, x3, x4) --> (y1,
- 158. Задача об обезьяне и банане (4) Шаг 1. Вычислить различия для исходной задачи. Основной признак целевого
- 159. Планирование иерархической сети задач Метод планирования HTN (Hierarchical Task Network) рассматривает первоначальный план, который описывает задачу,
- 160. Планирование иерархической сети задач
- 161. Мультиагентное планирование Задача игры в парный теннис. Два агента играют в одной команде и могут присутствовать
- 162. Мультиагентное планирование Решением мультиагентной задачи планирования является совместный план (joint plan), состоящий из действий для каждого
- 163. Мультиагентное планирование Решение проблемы – координация
- 164. Механизмы кординации Простейший метод, с помощью которого группа агентов может обеспечить координацию при выполнении совместного плана,
- 165. Механизмы кординации Модель поведения птицеподобного агента (который иногда именуется орнитоидом или боидом от слова boid, или
- 166. Механизмы кординации При отсутствии применимого соглашения агенты могут использовать общение для получения общих знаний об осуществимом
- 167. Многоагентная система – это система, в которой несколько взаимодействующих интеллектуальных агентов пытаются совместно достичь некоторый набор
- 168. Свойства интеллектуального агента Агенты — это активные объекты (программные модули), которые могут инициировать целенаправленную деятельность по
- 169. Принципы конструирования агента на основе спецификаций FIPA FIPA (FOUNDATION FOR INTELLIGENT PHYSICAL AGENTS) –Международная федерация по
- 170. Пример взаимодействия агентов (1): отдыхающим назначена одна и та же процедура Входные данные: Для отдыхающего №
- 171. Пример взаимодействия агентов (2): отдыхающим назначены разные процедуры Входные данные: Для отдыхающего № 1 назначено две
- 172. Пример взаимодействия агентов (3): отдыхающим назначены две одинаковые процедуры Входные данные: Для отдыхающих № 1 и
- 174. Скачать презентацию