Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 161
Текст из файла (страница 161)
Рассмотрим, как формируется граф А)ч(Р— ОК. Из доверительного состояния д мы показываем результат перемещения с помощью действия ЬеГ'с (другие действия не имеют смысла). Поскольку агент может оставить за собой мусор, эти два возможных начальных состояния мира становятся четырьмя возможными состояниями, как показано в прямоугольниках в и с Эти состояния формируют два различных доверительных состояния, которые классифицируются по доступной информации датчика~'. В доверительном состоянии и агент имеет информацию С2еапЬ, а в доверительном состоянии С вЂ” информацию С2сапЬ. В результате уборки мусора в состоянии Сагент переходит в состояние в.
После перехода с помощью действия ийд)зс из состояния В агент может оставить или не оставить за собой мусор, поэтому снова возникают четыре возможные состояния мира, которые подразделяются в соответствии со знаниями агента о том, является ли правый квадрат чистым, с2еапя (возврат в состояние л), или грязным, с2еапд (переход в доверительное состояние и). з Эти понятия представлены д разделе 3 б, к которому читателю может потребоваться обратиться еше раз, прежде чем изучать лаз ьнейши й матер иаз. э Этот феномен должен быть знаком родителям с маленькими детьми. Как обычно, приносим свои извинения тем, кто не янляется таковыми.
и Обратите внимание на то, что эти состояния не классифицируются по тому признаку, остается ди сзааи грязь после передвижения агента. Ветвление в пространстве доверительного состояния вызвано альтернативными результатами изменения знаний, а не альтернативными результатами физических изменений. Глава 12. Планирование и осуществление действий в реальном мире 591 Для описания доверительных состояний могут применяться три описанных ниже основных варианта.
1. Множества полных описаний состояния. Например, начальное доверительное состояние на рис. 12.8 может быть описано следующим образом: ( (АСЯ л С1еапЯ л С1еапъ), (АСЯ л С1еапл л С1еапъ) ) Это представление является простым в использовании, но очень дорогостоящим: если имеется и булевых высказываний, определяющих состояние, то ловерительное состояние может содержать 0(2") описаний физических состояний, каждый из которых имеет размер О(п), А если агент знает только небольшую часть этих высказываний, то могут возникать экспоненциально большие доверительные состояния, поскольку, чем меньше знает агент, тем больше количество возможных состояний, в которых он может находиться. 2.
Логические высказывания, которые точно представляют множество возможных миров в доверительном состоянии. Например, определение начального состояния можно записать слелующим образом; АСЯ л С1еапЯ Очевидно, что каждое ловерительное состояние можно представить с помощью одного и только одного логического высказывания; в случае необходимости можно было бы использовать дизъюнкцию всех конъюнктивных описаний состояния, но рассматриваемый пример показывает, что могут существовать более компактные высказывания.
Олин из недостатков общих логических высказываний состоит в том, что может существовать много различных, логически эквивалентных высказываний, которые описывают одно и то же доверительное состояние, поэтому проверка повторяющихся состояний в алгоритме поиска в графе может потребовать применения средств общего доказательства теорем. По этой причине желательно было бы использовать для высказываний каноническое представление, в котором каждое доверительное состояние соответствует одному и только одному высказыванию". В одном из таких представлений используется конъюнкция литералов, упорядоченных по именам термов; в качестве примера можно привести АСЯ л С1 еапЯ. Такое предстагпение можно рассматривать как стандартное представление состояния с учетом предположения об открытом мире, описанного в главе 11.
Не все логические высказывания могут быть записаны в указанной форме (например, не существует способа представления высказывания АСЬ и С2 еапЯ), но такой метод представления доверительных состояний может применяться во многих проблемных областях. 3.
Высказывания с оценкой знаний, описывающие знания агента (см. также раздел 7.7). Для данного начального состояния такое высказывание имеет следующий вид: К(АСЯ) л К(С1 пл) " Наиболее известным каноническим представлением лля пропозипионального высказывания общего вила являются бинарные диаграммы решения, или ВРР (Ь~пагу дес)з(оп гйаягат) 12001.
592 Часть 1ту. Планирование где к обозначает "знает, что", а и( Р) указывает, что агент знает" об истинности высказывания Р. В сочетании с высказываниями с оценкой знаний ис- пользуется предположение о замкнутом мире — если высказывания с оценкой знаний нет в списке, оно рассматривается как ложное.
Например, в приведенном выше высказывании неявно присутствуют термы К(02еапь) и К( 02еапг), поэтому оно представляеттот факт, что агент не знает истинностного значения герма 02 еапь. Как оказалось, второй и третий из описанных выше вариантов являются приблизительно эквивалентными, но мы будем использовать третий вариант — высказывания с оценкой знаний, поскольку они позволяют получить более реалистичное описание процесса получения информации с помошью датчиков и поскольку нам уже известно, как составлять описания 8(г(рз прп использовании предположения о замкнутом мире.
В обоих вариантах каждый пропозициональный символ может быть представлен в одном из трех видов: положительный, отрицательный или неизвестный. Поэтому сушествует точно Зп возможных доверительных состояний, которые могут быть описаны таким образом. С другой стороны, множество доверительных состояний представляет собой показательное множество (множество всех подмножеств) множества физических состояний. Количество физических состояний равно 2", поэтому количестно доверительных состояний равно 2', что намного превышает 3"; это означает, что варианты 2 и 3 являются чрезвычайно ограниченными с точки зрения представления доверительных состояний.
В настоящее время такая ситуация считается неизбежной, поскольку оз любая схема, снособная представить любое возможное бовери- тельное состояние, в наихудшем случае для представления каэ>сдого из них потребует >П 0(1од,2' ) ) =0(2") битов. Наши простые схемы требуют только 0(п) битов для представления каждо) о доверительного состояния, поэтому позволяют постичь компромисса, в котором выразительность принесена в жертву компактности.
В частности, если происходит некоторое действие, одно из предусловий которого неизвестно, то результирующее доверительное состояние не будет точно представимым и результат действия также станет неизвестным. Теперь необходимо решить, как должны действовать средства сбора информации с помошью датчиков. В данном случае имеются два варианта. Можно применить 'а. автоматический сбор информации с помошью датчиков, который означает, что на каждом временном этапе агент получает все доступные данные восприятия.
В примере, приведенном на рис. 12.8, предполагается, что с помошью датчиков происходит автоматический сбор информации о местонахождении агента и наличии мусора в локальном квадрате. Еше один вариант состоит в том, что можно настаивать на использовании Ъ. средств активного сбора информации с помошью датчиков, а это означает, что данные восприятия приобретаются только в результате выполнения конкретных ск действий по сбору информации с помощью датчиков, таких как " Это — такая же система обозначений, которая использовалась дяя агентов на основе логических схем, описанных в главе 7. Некоторые авторы применяют ее для передачи такого смысла, как "знает о том, является ли истинным высказывание р'*. Задача определения преобразования между этими двумя представлениями является несложной.
Глава 12. Планирование и осуществление действий в реальном мире 593 Спас)сР1пс и С)зес)гьосас1оп. Мы будем по очереди рассматривать каждый метод сбора информации с помощью датчиков. Теперь сформулируем одно из описаний действия с использованием высказываний о знаниях. Предположим, что агент в мире "альтернативного двойного закона Мэрфи" перемещается с помощью действия ьеГс, применяя автоматические средства сбора информации о наличии мусора в локальном квадрате; согласно правилам для этого мира, агент может оставить или не оставить за собой мусор, если квадрат был чистым. Этот результат, рассматриваемый как изменение физического состояния, должен быть дизьюнктивным, но если он рассматривается как результат изменения знаний, то просто сводится к тому, что у агента удаляются знания об истинности терма С1 еапк.
Агент должен также знать, является ли истинным терм С1 еапь, получив эти знании тем или иным способом, поскольку для сбора информации о наличии мусора в локальном квадрате предусмотрены датчики; кроме того, агент знает, что он находится в квадрате АСЬ.
Вся эта информация записывается слелующим образом: Асеуоп (ЬеГС, Вгесопс): АСК Кггесе: К(АСЬ) л К(АСК) л чнеп Сзеапд: К(С1еапК) л треп С1еапЬ: К(С1еапЬ) л чйиеп -осзеапдп К( С1еапЬ)) Обратите внимание на то, что предусловия и условия треп представляют собой простые высказывания, а не высказывания с оценкой знаний. Так и должно быть, поскольку результаты действий зависят от фактического состояния мира, но как мы могли бы проверить истинность этих условий, если все, что мы знаем, представляет собой доверительное состояние? Если агент знает истинность высказывания, например, к(Аск) в текущем доверительном состоянии, то это высказывание должно быть истинным в текущем физическом состоянии и, безусловно, соответствующее действие является применимым.
Если же агент не знает истинность какого-то высказывания (например, условия С1 еапь конструкции треп), то данное доверительное состояние должно включать миры, в которых терм С1еапь является истинным, и миры, в которых с1 еапь является ложным. Именно поэтому в результате данного действия возникает множество доверительных состояний. Таким образом, если начальным состоянием является (к(Аск) л к(с1еапк) ), то после движения ьегс двумя результирующими доверительными состояниями становятся (к(Ась) л к(с1еапь) ) и (к(Ась) л к( — с1еапь) ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
