Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 162
Текст из файла (страница 162)
В обоих случаях истинностное значение герма С1еапь известно, поэтому в плане может использоваться проверка герма С1 еап1,. При использовании активных средств сбора информации с помощью датчиков (вотличие от автоматических средств сбора информации с помощью датчиков) агент получает новые данные восприятия только после выдачи запроса на их получение. Таким образом, после перемещения с помощью действия ьеЕс агент не знает, является ли левый квадрат грязным, поэтому лва послелних условных результата болыпе не появляются в описании действия в уравнении 12.2. Чтобы узнать, есть ли в квадрате мусор, агент может выполнить действие с)зескпупс следующим образом: Асеуоп (Спес)гпзге, Ктгесе: еиеп АСЬ л С1еаптп К(С1еапЬ) л инеп АСЬ л С1еапто К( — С1еапЬ) л иасап АСК л С1еапд: К(С1еапК) л ииеп АСК л С1еапК: К( С1еапК)) (12.3) Часть!Ч.
Планирование Можно легко показать, что выполнение действия ьеЕс, за которым следует действие с)зесЖз гс, при организации работы с помощью активных средств сбора информации приводит к получению тех же двух доверительных состояний, к которым приводило действие ьегс при использовании организации работы с помощью средств автоматического сбора информации. При активном сборе информации всегда имеет место то, что физические действия отображают доверительное состояние в единственное доверительное состояние-преемник. Многочисленные доверительные состояния могут быть введены только с помощью действий по сбору информации датчиками, которые позволяют получить конкретные знания и поэтому дают возможность использовать в планах условные проверки. Выше был описан общий подход к условному планированию на основе поиска в пространстве состояний А)ЧΠ— Ой.
Такой подход зарекомендовал себя как чрезвычайно эффективный применительно к некоторым контрольным задачам, но другие задачи оказались трудноразрешимыми. Теоретически можно доказать, что условное планирование принадлежит к более трудному классу сложности, чем классическое планирование. Напомним, что определение класса задач )х)Р состоит в том, что потенциальное решение может быть проверено для определения того, действительно ли оно является решением, за полиномиальное время. Это определение относится к классическим планам (по крайней мере, к планам, имеющим полиномиальные размеры), поэтому задача классического планирования относится к числу й)Р- трудных.
Но в условном планировании потенциальное решение должно быть проверено для определения того, что для всех возможных состояний существует некоторый путь через план, позволяющий достичь цели. Проверка такой комбинации "все/некоторые" не может быть выполнена за полиномиальное время, поэтому условное планирование труднее, чем )чР. Единственный способ выхода из этой ситуации состоит в том, чтобы игнорировать некоторые из возможных непредвиденных ситуаций, которые могут рассматриваться на этапе планирования, и реагировать на них, только когда они действительно возникают.
Именно этот подход рассматривается в следующем разделе. 12.5. КОНТРОЛЬ ВЫПОЛНЕНИЯ И ПЕРЕПЛАНИРОВАНИЕ Агент, контролирующий выполнение, проверяет свои восприятия для определения того, все ли идет в соответствии с планом. Закон Мэрфи говорит нам о том, что даже самые тщательно продуманные планы, которые составляют мыши, люди и агенты, занимающиеся условным планированием, часто оканчиваются неудачей. Проблема заключается в неограниченной недетерминированности — всегда могут возникнуть непредвиленные обстоятельства, для которых описания действий, подготовленные агентом, будут неправильными.
Поэтому в реальных вариантах среды всегда требуется контроль выполнения. Мы будем рассматривать два способа организации контроля выполнения: простую, но слабую форму, называемую контролем действий, в которой агент проверяет среду для определения того, что следующее действие окажется применимым, и более сложную, но и более эффективную форму, называемую контролем плана, в которой агент проверяет весь оставшийся план. Перепланируюший агент знает, что делать, когда происходит что-то непредвиденное: снова вызвать планировщик, чтобы он предложил ему новый план достижения Глава 12. Планирование и осуществление действий в реальном мире 595 цели.
Для предотвращения использования слигцком больших затрат времени на планирование такая операция обычно осуществляется в виде попытки исправить старый план — найти способ перехода из текущего непредвиденного состояния обратно в одно из тех состояний, которые были предусмотрены в плане. В качестве примера еще раз рассмотрим мир пылесоса с "двойным законом Мэрфи", показанный на рис. 12.6. В этом мире перемещение в чистый квадрат иногда приводит к тому, что в этом квадрате откладывается мусор, но что если агент не будет знать или задумываться об этом? Такой подход позволяет предложить очень простое решение: [ьеГс].
Если мусор не был оставлен после прибытия агента в квадрат во время фактического выполнения плана, то агент обнаружит, что цель достигнута. В противном случае, поскольку предусловие Суеапд неявного шага К1пзд)з НЕ ВЫПОлнЕно, агЕнт ВЫРаботает новый план: [Вис)с). Выполнение этого плана всегда приводит к успеху. Контроль выполнения и перепланирование, вместе взятые, образуют общую стратегию, которая может применяться и в полностью наблюдаемых, и в частично наблюдаемых вариантах среды, а также может распространяться ца самые различные прелставления, применяемые в планировании, включая планы в пространстве состояний, планы с частичным упорядочением и условные планы. Один из простых подходов к планированию в пространстве состояний показан в листинге 12.5. Планирующий агент начинает с цели и создает начальный план ее достижения. Затем агент приступает к последовательному выполнению лействий.
А переплапируюший агент, в отличие от других рассматриваемых нами планирующих агентов, следит за выполнением как оставшегося невыполненного сегмента плана р1ап, так и полного первоначального плана ьупо1е р1ап. В нем используется 'гь контроль действий: прежде чем выполнить следующее действие плана р1ап, агент проверяет свои результаты восприятия для определения того, не оказались ли вдруг невыполненными какие-либо предусловия плана. Если они лействительно являются таковыми, то агент пытается снова попасть в колею, перепланируя последовательность действий, которые должны помочь ему вернуться в некоторый пункт плана ийо1 е р?ап. Листинг 12.5.
Алгоритм агента, который занимается контролем действий н перепланированием. В нем в качестве процедуры используется полный алгоритм планирования в пространстве состояннй, называемый Р1аппег. Если предусловвя следующего действия не выполняются, агент проходит по циклу через возможные пункты р в плане мдоде зьдап, пытаясь найти такой нз нпх, путь к которому может быть запланирован с помощью алгоритма в1алдег. Этот путь называется герадг (поправка).
Если в алгоритме в1аппег удается найтп такую поправку герадг, агент соединяет герахг я остаток плана после пункта р, чтобы создать новый план. Затем агент возвращается к первому этапу нового плана гцпопдоп Кер1апп1пв-Ддеде[регсерг) гепипи действие асвдол пвавьо: КВ, база знаний [включает описания действий) р1ап, план, первоначально представленный пустым списком ьло1е р1ал, обыий план, первоначально представленный пустым списком [) поа1, цель Те11[КВ, Маке-ветсере-эепселсе[регсерг, С)) снггелг < — агаве-безсг1рвьоо)КВ, С) ДД ртап = [) ЕЬеп 59б Часть!У. Планирование нйо1е р1ап Ь- р1ап Ь вЂ” Р1аппег)сиггепе, доа1, КВ) хх предусловия Ргесопс)йгьопв)вьгве)р1ап)) не имеют в настоящее время значения Сгие хп КВ Епеп санс)дс)асея ь — яогс)ыпо1е р1ап, упорядоченный по расстояниям до текущего состояния сиггепг) Ыпс) состояние а среди возможных кандидатов сапд1с)асез, такое, что Еа11иге Ф гера1г < — Р1адпег)сиггепс, а, кВ) сопсзпиасхоп ь- хвост общего плана ы)1о1е р1ап, начинающийся с е ы)го1е р1ап ь- р1ап с в АррепЯгерадг, сопс1пнасхоп) гесчгп Рор)р1ап) Схематически этот процесс приведен на рис.
! 2.9. Перепланирую)ций агент обнаруживает, что в текущем состоянии не выполнены предусловия первого действия в плане р1ап. Поэтому он вызывает алгоритм планирования, чтобы получить новый субплан геразг, позволяющий перейти из текущего состояния в некоторое состояние В плана нйо1е р1ап. В данном примере оказалось, что состояние В находится на один шаг назад от текущего, оставшегося плана р1 ап (это удалось определить благоларя тому, что осуществляется контроль за выполнением всего плана, а не только оставшегося). Вообще говоря, следует выбирать состояние В так, чтобы оно было как можно ближе к текущему состоянию. Соединение плана герайг и части плана ьдзо1е р1ап от В и дальше, которую мы называем соп схппа ей оп, позволяет получить новый план р1 ап, и агент становится готовым возобновить выполнение плана.
нйо!е р(ап р)ап Рис. 12.9. Перед выполнением планировщик предлагает план, называемый здесь нпо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}
