Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 159
Текст из файла (страница 159)
Непрерывное планирование. Все планировщики, рассматривавшиеся до сих пор, спроектированы так, что они достигают цели, а затем останавливаются, а непрерывный планировщик предназначен для того, чтобы заниматься планированием в течение всего срока своего существования. Он способен справляться с непредвиденными ситуациями в своей среде, даже если они возникают в ходе того, как агент занимается составлением плана.
Он способен также обеспечить отказ от целей и создание дополнительных целей с помощью формулировки цели. Непрерывное планирование описано в разделе 12.б. Рассмотрим один пример, позволяющий выяснить различия между агентами разных типов. Задача состоит в следующем: дано начальное состояние, в котором имеются стул, стол и несколько банок с краской, притом что все они имеют неизвестный цвет; достичь состояния, в котором стул и стол имеют одинаковый цвет. Классический планирующий агент не может справиться с этой задачей, поскольку начальное состояние задано не полностью, — мы не знаем, какой цвет имеет мебель.
Агент, осуществляющий планирование без использования датчиков, должен найти план, который работает, не требуя применения каких-либо датчиков во время его Глава 12. Планирование и осуществление действий в реальном мире 583 выполнения. Решение состоит в том, чтобы открыть любую банку с краской п нанести эту краску и на стул, и на стол, тем самым принудительно переведя их в такое состояние, в котором они имеют одинаковый цвет (даже несмотря на то, что агент так и не узнает, каким стал этот цвет). Принуждение является наиболее приемлемым, если обработка высказываний требует больших затрат или не существует возможности обеспечить восприятие.
Например, врачи часто предписывают антибиотик с широким спектром действия, а не используют условный план, согласно которому нужно выполнить анализ крови, затем дождаться получения результатов и только после этого выписать более специализированный антибиотик. Они принимают такое решение потому, что задержки и затраты, связанные с выполнением анализа крови, обычно слишком велики. Агент, занимающийся условным планированием, может создать лучший план. Он вначале определяет цвет стола и стула; если этот цвет является одинаковым, то план выполнен. В противном случае агент просматривает надписи на банках с краской; если имеется банка с краской такого же цвета, как и у одного из предметов мебели, то агент наносит эту краску и на другой предмет.
Если же оба эти предположения оказываются недействительными, агент окрашивает и стол, и стул произвольно выбранной краской. Перепланируюший агент может выработать тот же план, что и условный планировщик, или вначале предусмотреть меньше ответвлений и по мере необходимости заполнять остальные фрагменты плана в ходе его выполнения. Он также способен справзиться с неточностями в описании его действий.
Например, предположим, что действие пайпс (оЬ2, со2от) рассматривается как имеющее детерминированный результат Со2оз-(оЬ2, со2ок) . Условный планировщик будет просто считать, что желаемый результат достигнут непосредственно после выполнения действия, а перепланирующий агент способен проверить результат, и если он не был истинным (возможно, потому, что агент допустил небрежность и не прокрасил полностью какой-то участок), то имеет возможность затем перепланировать свои действия, чтобы снова покрасить дефектный участок. Мы вернемся к данному примеру на с. 596. Непрерывно планирующий агент, кроме учета непредвиденных событий, способен пересматривать свои планы должным образом, если, допустим, мы внесем дополнительную цель, чтобы сегодняшний обед прошел еше за этим столом, поэтому нужно будет отложить выполнение плана окрашивания.
В реальном мире в агентах применяется сочетание нескольких подходов. Производители автомобилей продают запасные колеса и надувные подушки безопасности, которые представляют собой физические воплощения ответвлений условного плана, позволяющих справляться с такими ситуациями, как проколы колес или аварии; с другой стороны, большинство водителей автомобилей никогда не учитывают такие возможности, поэтому отвечают на проколы и аварии как перепланируюшие агенты.
Как правило, агенты создают условные планы только для таких непредвиденных ситуаций, которые имеют важные последствия, а шансами на то, что дела пойдут не лучшим образом, нельзя пренебречь. Таким образом, водителю автомобиля, пред- принимающему поездку через пустыню Сахара, придется явно учесть возможность поломок в пути, тогда как поездка в соседний супермаркет требует гораздо меныцего заблаговременного планирования.
Агенты, описанные в этой главе, предназначены для осуществления действий в условиях недетерминированности, но не обладают способностью учитывать ком- 584 Часть 1У. Планирование промиссы между вероятностью успеха и стоимостью составления плана. В главе 16 рассматриваются дополнительные инструментальные средства, позволяющие справляться с этими проблемами.
12.4. УСЛОВНОЕ ПЛАНИРОВАНИЕ Условное планирование представляет собой один из способов учета неопределенности путем проверки того, что фактически происходит в среде при выполнении заранее заданных пунктов плана. Условное планирование можно проще всего объяснить на примере полностью наблюдаемых вариантов среды, поэтому начнем его описание с такого случая. Случай с частично наблюдаемой средой является более сложным, но и более интересным. Условное планирование в полностью наблюдаемых вариантах среды Полная наблюдаемость означает, что агент всегда знает текущее состояние.
Но если среда является недетерминированной, то агент не будет способен предвидеть результат своих действий. Агент, занимающийся условным планированием, преодолевает такую недетерминированность, встраивая в свой план (на этапе планирования) условные этапы, в которых проверяется состояние среды (на этапе выполнения), для определения того, что делать дальше. Поэтому проблема состоит в том, как создавать такие условные планы. Мы будем использовать в качестве примера проблемной области почтенный мир пылесоса, пространство состояний которого для данного детерминированного случая описано на с. 117.
Напомним, что доступными действиями являются кеГг, ядд)зс и япс)г. Нам потребуются определенные высказывания для описания этих состояний. Допустим, что предикат лгъ (лея) будет истинным, если агент находится в левом (правом) квадрате', а предикат Сзеапк (Сзеаля) истинен, если левый (правый) квадрат чист. Прежде всего необходимо дополнить язык бгпрз для того, чтобы он позволял учитывать недетерминированность.
Для этого предусмотрено, чтобы действия имели оь дизъюнктивные результаты, а это означает, что действие может иметь два или несколько различных результатов при каждом его выполнении. Например, допустим, что действие по перемещению кеГг (Влево) иногда оканчивается неудачей.
В таком случае следующее обычное описание действия: Лсек (бобе,ртесопгЗ: Лея,вббесг: ЛСЬ л Лпя) должно быть модифицировано так, чтобы в него был включен следующий дизъюнк- тивный результат; Лог' 1кобе,ртосопон Лея,вббесе: ЛСЬ ч Лея) (гг.з) Авторы сочли также целесообразным, чтобы действия имели са условные результаты, когда результат действия зависит от состояния, в котором оно выполняется. Условные результаты присутствуют в слоте кббесп дЕйСтВИя и имеЮт СИнтаКсИС Очевилно, что предикат лся является истинным тогда и только тогла, когда предикат Ась является истинным, и наоборот. Мы используем лва высказывания в основном для того, чтобы улучшить удобство чтения.
Глава 12. Планирование и осушествление действий в реальном мире 585 "зя)зеп <сопЖсйоп>: <е1Еесс>". Например, чтобы промоделировать действие Бис)г, необходимо записать следующее: Ассхап(лис)г, Ркесопг):, Е11есе: (мЬеп Аегп С1еапъ) л (маем АЕЯ: С1еапн))) Условные результаты не вносят недетерминированность, но позволяют ее моделировать.
Например, предположим, что в нашем распоряжении имеется не совсем исправный пылесос, который иногда оставляет мусор в квадрате назначения в процессе своего передвижения, но только если этот квадрат чист. Такую ситуацию можно промоделировать с помошью следуюшего описания, которое одновременно является и дизъюнктивным, и условным': Ассзоп(ьеес,Ртесопон Аея,еттесе: Аеъ м (Ась а ииеп с1еапгп с1еапь) ) Для создания условных планов требуются 'гв. условные этапы. Мы будем записывать их с использованием синтаксиса "хк < Сене> СЬеп р1ап„е1ее р1ап,", где <сенс> — булева функция переменных состояния.
Например, условным этапом для мира пылесоса может быть следующий: "зй Ась л с1еапп с)зеп пйд)зс е1ве Бцс)г". Выполнение такого этапа осушествляется очевидным способом. В результате вложения условных этапов линейные планы преврашаются в древовидные. Нам требуются условные планы, которые работают невзирая на то, какие результаты действий фактически будут получены. Такая проблема уже встречалась раньше в данной книге, но немного в другом виде. В играх с двумя игроками (см.
главу 6) была поставлена задача найти ходы, которые приводят к выигрышу независимо от того, какие ходы лелает противник. По этой причине задачи недетерминированного планирования часто называют сь играми против природы. Рассмотрим конкретный пример из мира пылесоса. В начальном состоянии робот-агент находится в правом квадрате мира, в котором нет мусора; поскольку среда полностью наблюдаема, агент знает полное описание состояния, Асп л С1еапп л С1еапд. В целевом состоянии робот должен находиться плевом квадрате мира, в котором нет мусора.
Такая задача была бы совершенно тривиальной, если бы пылесос не подчинялся "двойному закону Мэрфи" и не оставлял иногда мусор при его перемешении в чистый квадрат назначения, а иногда — при выполнении действия Яцс)г в чистом квадрате. "Дерево игры" лля этой среды показано на рис. 12.6. Действия выполняются роботом в узлах "состояния" этого дерева, а природа решает, каким должен быть результат в узлах "жеребьевки", обозначенных кружками.
Решением является поддерево, в котором, во-первых, рядом с каждым листовым узлом имеется целевой узел, во-вторых, задается одно действие в каждом из узлов "состояния" и, в третьих, включена каждая ветвь результата в каждом из узлов "жеребьевки". Решение на этом рИСуНКЕ ПОКаЗаНО жИрНЫМИ ЛИНИЯМИ; ОНО СООтВЕтСтнуЕт ПЛаНу [ЪЕГС, зй АГА п С1еапп л С1еапп сЬеп [] елее Бис)г). (На данное время, поскольку исполь- ь условный результат мьеп с1еапь; с1еапь может выглядеть немного странным. Но следует учитывать, что здесь с1еапь относится к снтуяцнн до выполнения действия, а с1еапь — к ситуации после выполнения действия. 586 Часть 1Ч. Планирование зуется планировшик в пространстве состояний, проверки в условных этапах приводят к получению полных описаний состояния.) Рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
