Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 88
Текст из файла (страница 88)
333"; этот предел все еще является экспоненциальным, но гораздо более низким по сравнению с достигнутыми ранее пределами для худшего случая. Алгоритмы проверки выполнимости все еще остаются очень активной областью исследования; хорошей отправной точкой для изучения этой темы может служить сборник статей под редакцией Дю и др. [418]. Истоки идей по созданию агентов на основе логических схем можно проследить до оригинальной статьи Мак-Каллока и Питтса [1017], которая послужила началом исследований в области нейронных сетей.
Вопреки сложившемуся общему мнению, эта статья касаяась реализации проекта агента на основе логической схемы в мозгу. Однако агенты на основе логической схемы долго не привлекаяи значительного внимания 337 Глава 7. Логические агенты исследователей в области искусственного интеллекта. Самым заметным исключением из этого правила явились работы Стена Розеншайна [760], [1308], который разработал способы компиляции агентов на основе логических схем из декларативных описаний проблемной среды. Логические схемы для обновления высказываний, хранящихся в регистрах, тесно связаны с аксиомой состояния-преемника, разработанной для логики первого порядка Рейтером [1277]. В работах Рода Брукса [189], [190] продемонстрирована эффективность использования проектов на основе логической схемы для управления роботами; к этой теме мы вернемся в главе 25. Брукс [192] утверждает, что для искусственного интеллекта необходимы лишь проекты на основе логических схем, а методы представления и формирования логических рассуждений являются громоздкими, дорогостояшими и ненужными.
Но, по мнению авторов, ни один из этих подходов, отдельно взятых, не является достаточным. Мир вампуса был придуман Грегори Йобом [1633]. Любопытно то, что Йоб разработал этот мир, поскольку ему надоели игры, которые проводятся в мире, прел- ставленном в виде квадратной решетки: топология его первоначального мира вампуса представляла собой додекаэдр, а мы снова поместили вампуса в старую скучную квадратную решетку. Майкл Генезерет был первым, кто указал, что мир вампуса мох<но использовать как испьпательную площадку для агентов.
УПРАЖНЕНИЯ 7.1. Опишите мир вампуса в соответствии со свойствами проблемной среды, перечисленными в главе 2. 7.2. Предположим, что агент достиг пункта, показанного на рис. 7.3, а, получив такие результаты восприятия: в квадрате [1, 1] — ничего, в квадрате [2, 1] — ветерок, а в квадрате [1, 2] — неприятный запах. В настоящий момент агента интересует содержимое квадратов [1,3], [2,2] и [3,1]. Каждый из них может содержать яму, и самое большее в одном из них может находиться вампус.
На основе примера, приведенного на рис. 7.4, сконструируйте множество возможных миров. (Должно быть найдено 32 таких возможных мира.) Отметьте миры, в которых существующая база знаний является истинной, а также те, в которых истинным является каждое из следующих высказываний: аз = "В квадрате [2,21 нет ямы" а~ = "В квадрате [1,3] есть вампус" Наосновании этого покажите, что кВ 1 а, икВ 1 ам 7.3.
Рассмотрите задачу определения того, является ли некоторое высказывание пропозициональной логики истинным в данной модели. а) Напишите рекурсивный алгоритм р1-Тки? (В,и], который возвращает схие тогда и только тогда, когда высказывание в является истинным в модели зв (где зв присваивает истинностное значение каждому символу в в). Этот алгоритм должен заканчивать свою работу за время, линейно зависящее от размера высказывания.
(Еше один вариант состоит в том, чтобы воспользваться версией этой функции из оперативного репозитария кода.) 338 Часть Ш. Знания и рассуждения б) Приведите три примера высказываний, в отношении которых можно определить, являются ли они истинными или ложными, в частичной модели, в которой не заданы истинностные значения для некоторых из символов. в) Покажите, что в общем случае истинностное значение высказывания (если оно имеется) невозможно эффективно определить в частичной модели. г) Доработайте свой алгоритм рг -ткаче? так, чтобы он иногда позволял судить об истинностном значении по частичным моделям, сохраняя вместе с тем свою рекурсивную структуру и линейную зависимость времени прогона от размера высказывания.
Приведите три примера высказываний, истинность которых в частичной модели не обнаруживается вашим алгоритмом. д) Проведите исследование того, позволяет ли этот модифицированный алгоритм повысить эффективность алгоритма тТ-епгаз1э?. 7.4. Докажите каждое из приведенных ниже утверждений. а) Высказывание а является допустимым тогда и только тогда, когда тгие 1 сс б) Для любого высказывания о.
истинно, что Ра?эе ~ а. в) Истинно, что а ~ В тогда итолькотогда, когда высказывание(а ~ (3) допустимо. г) Истинно,что а - =()тогда итолькотогда, когла высказывание(а с=> В) допустимо. д) Истинно, что и ~ (3 тогда и только тогда, когда высказывание (а л — р) недостижимо. 7.5. Рассмотрите словарь, состоящий только из четырех высказываний, А, и, С и (З. Сколько существует моделей для каждого из следующих высказываний? а) (АлВ) м (ВлС) б)АнВ в) А<=~В<=>С 7.6. В этой главе мы определили четыре различных бинарных логических связки.
а) Имеются ли какие-либо другие логические связки, которые могут оказаться полезными? б) Сколько может быть определено разных бинарных связок? в) Почему некоторые из них не очень полезны? 7.7. Используя любой предпочитаемый вами метод, проверьте каждую из эквивалентностей, приведенных в листинге 7.4. 7.8. Определите, является ли каждое из приведенных ниже высказываний дейст- вительным, невыполнимым или ни тем ни другим. Проверьте полученные вами результаты с помощью истинностных таблиц или правил эквивалентности, приведенных в листинге 7.4. а) Ято)ге =ь англо?ге б) Яно?се =ь Рзхе в) (Ягпо)ге ~ Езде) ~ (- Яао)ге ~ — Уз'.хе) Глава 7.
Логические агенты 339 7.9. 7.10. 7.11. г) Бто(се ч ВХке ч -Ике 4 ((Бто?се а Неае) =ь Вбке) с=> ((Ято(се ~ Вбке) ч (Неае .=> Нбене) 1 е) (ято(се =ь Жке) => ( (ятоке л неас) =ь Взке) ж) Вдд ч РитЬ ч (Взд =ь РитЫ З) (Вбд л РитЫ ч — РитЬ (Адаптировано из (78/.) Можете ли вы доказать на основании приведенных ниже рассуждений, что единорог — мифическое сушество? А что насчет того, что это волшебное сушество? Существо, вооруженное рогом? Если единорог — мифическое сушество, то он бессмертен, а если нс мифическое, то он — смертное млекопитаюшее.
Если единорог либо бессмертен, либо является млекопитаюшим, то он вооружен рогом. Единорог является волшебным сушеством, если он вооружен рогом. Любое высказывание пропозициональной логики логически эквивалентно утверждению, что любой возможный мир, в котором это высказывание было бы ложным, не имеет места. На основании этого наблюдения докажите, что любое высказывание может быть записано в конъюнктивной нормальной форме.
М!пезусесрег (минный тралыцик) — широко известная компьютерная игра, которая тесно связана с миром вампуса. Мир минного тральщика представляет собой прямоугольную решетку из ь квадратов с и разбросанными по ним невидимыми минами. Агент может проверить любой квадрат; если он проверяет заминированный квадрат, его ждет немедленная смерть. В игре М[пезиеерег наличие мин раскрывается путем показа в каждом проверенном квадрате количества мин в квадратах, соседних по горизонтали, вертикали или диагонали. Цель игры состоит в том, чтобы проверить каждый незаминированный квадрат. а) Допустим, что высказывание х„, является истинным тогда и только тогда, когда в квадрате [ з, 7'1 находится мина. Составьте утверждение, согласно которому в квадратах, соседних по отношению к квадрату [1, 11, имеется точно две мины, в виде высказывания, включающего определенную логическую комбинацию высказываний х,,;.
б) Обобщите ваше утверждение, составленное при выполнении упр. 7.11, а, и объясните, как следует формировать высказывание СНЕ с утверждением, что (с из п соседних квадратов содержат мины. в) Точно объясните, как агент может использовать алгоритм РВЬЬ для доказательства того, что данный квадрат содержит (или не содержит мину), игнорируя глобальное ограничение, согласно которому всего имеется точнонмин. г) Предположим, что глобальное ограничение конструируется с помощью метода, созданного вами при выполнении упр. 7.11, б. Как зависит количество выражений в этом ограничении от Н и Н? Предложите способ осуществления такой модификации алгоритма РВЬЬ, чтобы в нем не требовалось явно представлять это глобальное ограничение.
340 Часть Ш. Знания и рассуждения д) Становятся ли недействительными какие-либо выводы, полученные при создании метода, о котором речь идет в задании 7.11, в, если учитывается это глобальное ограничение? е) Приведите примеры конфигураций проверочных значений, которые порождают такие далеко идущие зависимости, что содержимое любого непроверенного квадрата может предоставить информацию о содержимом какого-то далеко отстоящего от него квадрата. (Подсказка. Рассмотрите доску с размерами Мх1,) 7.12. В данном упражнении рассматривается связь между выражениями и импликативными высказываниями. а) Покажите, что выражение ( — Р, ч ... ч — р„м (з) логически эквивалентно импликативному высказыванию (Р, л ... л Р ) => О.
б) Покажите, что каждое выражение (независимо от количества положительных литералов) может быть записано в форме (Р, л ... л р,) (ц, ч ... ч Я,), где р и 0 — пропозициональные символы. База знаний, состоящая из таких высказываний, находится в 'в.
импликативной нормальной форме, или в форме Ковальского. в) Составьте полное правило резолюции для высказываний в импликативной нормальной форме. 7.13. В этом упражнении речь идет о проектировании агента для мира вампуса на основе логической схемы. а) Запишите уравнение, аналогичное уравнению 7.4, для высказывания лхгоь, которое должно быть истинным, если у агента все еше есть стрела.
Составьте соответствующую логическую схему. б) Повторите залание 7.13, а для высказывания ьасупдлудпс (агент смотрит вправо), используя в качестве образца уравнение 7.5. в) Создайте версии уравнений 7.7 и 7.8 для поиска вампуса и начертите логическую схему. 7.14. Обсудите понятие оптимального поведения в мире вампуса.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
