Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 145
Текст из файла (страница 145)
11.3. Незаконченный план с частичным упорядочением для задачи замены колеса после выбора действий, соответствующих первым двум открытым нредусловиям. В ярямоугояьниках показаны деиствия, нредусловия которых находятся слева, а результаты — справа (результаты не показаны, кроме результатов деиствия Б саге). Оглашные линии со стрелками наказывают причинные связи, защищающие высказывание, находящееся у острия стрелки Глава 11. Основы планирования 533 3.
Взять предусловие АС(Р1аг,лх2е) действия РиСОп(Браге,лх1е). Просто для того чтобы поступить вопреки здравому смыслу, выберем действие ьеаиеОзгегпзд)(с, а не действие летсие (Ратас, Ах1е) . Но обратите внимание на то, что действие ЬеаиеОиегптд)зе также имеет результат -Ас (яраге, сгоипс)), который означает, что оно конфликтует со следующей причинной связью: летсие ( Брате, Ттип)с) ~~)~Я' — "-').ч'"" ) Ри Сои ( Брате, Ах1 е) Чтобы разрешить этот конфликт, добавим ограничение упорядочения, которое помещает действие ьеачгеОиегпзд)зс перед действием летсие ( Яраге, Тгип)с) . Возникающий при этом план показан на рис.
11.4. (Предлагаем читателю ответить на вопросы, почему такое дополнение позволяет разрешить конфликт и почему нет другого способа его разрешить?) Аг(5р ге, Гюле) ! ! ! ! ! г г ! ! Алзрлге, Гпгче) (::Л Б(ы( Агрл(лг,лиг) Аг(зрлтоычь ) ~(~, ) . ~Я 1 Аг(ип),Аг(е) Аг(Н(аг,лт(е) А)) Н(аьапыч ") АкзеагЕАае) А!)5рлге,агшлв) Аг 5рап,нолт) (еачсочет(ЗМ 4. В этот момент единственным оставшимся открытым предусловием является предусловие АС ( Брате, Тгип)с) действия летсие( Браге, Тгип)с) .
Единственным действием, позволяющим достичь этого предусловия, является сушествующее действие ясагс, но причинная связь от ясагс к летсие (Браге, тгип)с) конфликтует с результатом — Ас(Браге, тгипй) действия ьеаиеоиегпзд((с. В данный момент не существует способа разрешить конфликт с действием ЬеаиеОс егптд)зг — его нельзя переупорядочить таким образом, чтобы оно нахолилось перед Ясагс (поскольку ни одно действие не может происходить перед действием яеагс), и нельзя переупорядочить его таК, ЧтсбЫ ОНО НаХОдИЛОСЬ ПОСЛЕ )(Етс(гЕ(ЯраГЕ, Ттии)С) (ПОСКОЛЬКУ ужЕ имеется ограничение, которое упор)щочивает его перед детоие(яраге, тгип)с) ). Поэтому необходимо вернуться к одному из предыдущих состояний, удалить действие ьеаиеОчгегпзд)зс и две последние причинные связи, возвратившись в состояние, показанное на рис.
1!.3. Планировщик фактически доказал, что действие ьеаиеОиегпзд)зс не может применяться в качестве способа замены колеса. Рис. 11А План, возникающии после выбора Ьеаиеоиетпьд)зс в качестве деиствия для доопижения предусловия -в(с (в1ас, Ах1е!. Чтобы избежать конфликта с причинной связью, исходящей из действия нея)оие (Брате, ттип)с), которая защищает действие Ат (Брате, стоипс(), яа Ьеачгеочгетпьд))с накладывается ограничение, чтобы эпю действие происходило перед ветьочге ( Брате, Ттип)с), как показано штриховой линией со стрелкои 534 Часть 1чг.
Планирование 5. Еще раз рассмотрим предусловие -АС (Р1ас, Ах1е) действия РцЕОп( Браке, Ах1е) . На этот раз выберем действие летоуе(Р1ае, Ах1е) . б. Снова возьмем предусловие АГ(Брахе, тзцп)с) дЕйСтВия )(етоуЕ(Брахе, ткпп)с) и выберем действие Ясаке, чтобы его достичь. На сей раз конфликты не возникают. 7. Возьмелз предусловие Аг(е1ас, Ах1е) действия нетоуе(Г1ас, Ах1е) и выберем действие 8сапс для его достижения. Это дает нам полный согласованный план (иными словами, решение), как показано на рис. 11.5. л~(грасс.знте) '( Бмягг 33 лг(лрпм, утлс) ,и(млел. ~е) лкпаслгн) Лг(Юрасе.бегина) Ро)Оп(ьрагс,лх!е) лг(враге ля)е) [ Ргагзв 1 лирг ьлгге) Рнс. 11.5. Окончательное реигенае задачи замены колеса.
Обратите внимание на то, что дейст- вия Реппне (Брасе, тхппх) и Иетозге (Р1ас, зх1е) могут выполняться в любом порядке, нри 1 сломя, чнш они завершаются перед дег)станем эскоп (Брасе, Ах1е) Хотя данный пример очень прост, он иллюстрирует некоторые преимущества планирования с частичным упорядочением. Во-первых, причинные связи способствуют заблаговременному отсечению тех частей пространства поиска, которые не содержат решений из-за неустранимых конфликтов. Во-вторых, решение, приведенное на рис.
11.5, представляет собой план с частичным упорядочением. В данном случае преимушества невелики, поскольку имеются только две возможные линеаризации; тем не менее повышенная гибкость выбора вариантов может пойти агенту на пользу, например, если ему придется менять колесо в середине шоссе с интенсивным движением.
Этот пример также указывает на некоторые возможные усовершенствования, которые вполне могут быть осуществлены. Например, в данном случае налицо дублирование усилии: лействие ясаке соединяется связью с действием нетоуе(Браке, Тз цпк) до того, как конфликт вызывает возврат, а затем эта связь снова разрывается из-за возврата, даже несмотря на то, что она не участвует в конфликте. После этого в ходе продолжения поиска связь снова восстанавливается. Такое развитие событий является типичным для хро олопшеских возвратов, и его последствия могут быть смягчены с помощью возвратов, управляемых с учетом зависимостей.
Планирование с частичным упорядочением н несвязанными переменными В этом разделе рассматриваются сложности, которые могут возникнуть, если алгоритм РОР используется с представлениями действий в логике первого порядка, которые могут включать переменные. Предположим, что имеется задача в мире блоков (см. листинг 11.3) с открытым предусловием Оп (А, В) и следующим действием: и сох оп (моне Оз, х, у), Ргесопеи Оп(.Ь, х) л О1еаг(Ы л О1еаз-(у), Вьйесс: Оп(зз,у) л О1еаг(х) л -зоп(Ь,х) л —,О1еас(у) ) Глава 11. Основы планирования 535 Это действие достигает результата Оп (А, и), поскольку результат Оп ( Ь, у) унифицируется с термом Оп (А, и) с помощью подстановки (ЫА, у/В). Затем применим эту подстановку к действию и получим следующее: Асстоп(моъе(А, х, В) Рпесопс(: Оп(л,х) л С1еап(А) л с1еап(В) Еййесе: Оп(А, В) л С1еаг(х) л Оп(л,х) л С1еап(В) ) При этом переменная х остается несвязанной.
Тем самым в данном действии определено, что блок А нужно переместить откуда-то, а откуда, не сказано. В этом заключается еше один пример реализации принципа наименьшего вклада; мы можем отложить выполнение выбора до какого-то этапа, в котором сам план укажет для нас этот выбор. Например, предположим, что в начальном состоянии имеется предусловие Оп(А, Р). В таком случае для достижения предусловия Оп(А, х) может использоваться действие Яеапе со связыванием х С О.
Такая стратегия с ожиданием дополнительной информации перед выбором х часто является более эффективной по сравнению с опробованием любого возможного значения х и возвратом в ответ на неудачный выбор каждого из этих значений. Из-за наличия переменных в предусловиях и действиях процесс обнаружения и разрешения конфликтов усложняется. Например, после добавления к плану действия Мот е (А, х, В) потребуется следующая причинная связь: Моче(А, х, В) -" — '"4'Р.'пте)з Если имеется другое действие и, с результатом «Оп(А, а), то и, конфликтует, только если переменная а равна и. Чтобы учесть такую возможность, расширим представление планов для включения множества Ъ.
ограничений неравенства в форме яах, где а — переменная, а х — либо другая переменная, либо константный символ. В данном случае можно было бы разрешить конфликт путем добавления ограНИЧЕНИя ааВ, КОтОрОЕ ОЗНаЧаЕт, ЧтО В будущИХ дОПОЛНЕНИяХ К ПЛаНу раЗрЕШастея конкретизировать переменную а любым значением, кроме в.
При каждом применении к плану некоторой подстановки необходимо контролировать, чтобы подобные неравенства не противоречили этой подстановке. Например, подстановка, которая включает хну, конфликтует с ограничением неравенства хеу. Такие конфликты не могут быть разрешены, поэтому планировщику приходится выполнять возврат. Более подробный пример планирования по алгоритму РОР с переменными в мире блоков приведен в разделе 12.6. Эвристики для планирования с частичным упорядочением В отличие от планирования с полным упорядочением, планирование с частичным упорядочением обладает явным преимуществом, поскольку позволяет выполнять декомпозицию задач на подзадачи.
Оно имеет также определенный недостаток, который заключается в том, что состояния не представлены явно, поэтому труднее оценить, насколько далек план с частичным упорядочением от ситуации достижения цели. К тому же в настоящее время существует гораздо меньшее понимание того, как следует вычислять точные эвристики лля планирования с частичным упорядочением, чем для планирования с полным упорядочением. 536 Часть 1Ч. Планирование Наиболее очевидная эвристика состоит в подсчете количества различных открытых предусловий.
Такая эвристика может быть улучшена путем вычитания из указанной величины количества открытых предусловий, которые согласуются с литералами в состоянии ьсатс. Как и в случае с полным упорядочением, такая эвристика приводит к переоценке стоимости, если имеются действия, достигающие нескольких подцелей, и недооценке стоимости, если возникают отрицательные взаимодействия этапов плана. В следующем разделе представлен подход, позволяющий получать гораздо более точные эвристики из ослабленной задачи. Эвристическая функция используется для выбора плана, подлежащего уточнению. При наличии такого выбора алгоритм вырабатывает преемников на основе определения единственного открытого предусловия, которое следует дополнительно проработать.
Как и в случае выбора переменной в алгоритмах удовлетворения ограничений, такое решение оказывает большое влияние на эффективность. Для алгоритмов планирования может быть адаптирована эвристика с наиболее ограниченной переменной, применяемая в задачах СзР, и эта эвристика, по-видимому, неплохо действует. Ее идея состоит в том, чтобы определить открытое условие, которое может быть выполнено с помощью наименьшего количества способов. Возникают два особых случая применения этой эвристики. Во-первых, если какого-то открытого условия невозможно достичь с помощью любого действия, оно должно быть выбрано данной эвристикои; это — вполне целесообразно, поскольку раннее обнаружение неразрешимой ситуации позволяет сэкономить большой объем работы.
Во-вторых, если открытое условие может быть достигнуто только одним способом, оно также должно быть выбрано, поскольку такое решение неизбежно и позволяет налагать дополнительные ограничения на другие варианты выбора, которые еше должны быть сделаны. Хотя процедура полного вычисления количества способов выполнения каждого открытого условия является дорогостоящей и не всегда оправданной, эксперименты показали, что применение этих двух частных случаев обеспечивает весьлга существенное ускорение. 11.4.
ГРАФЫ ПЛАНИРОВАНИЯ Все предложенные выше эвристики для планирования с полным упорядочением и частичным упорядочением могут допускать неточности. В данном разделе показано, как можно воспользоваться специальной структурой данных, называемой 'ек графом планирования, для получения лучших эвристических оценок. Такие эвристики могут применяться в любом из методов поиска, рассмотренных нами до сих пор. Еше один вариант состоит в том, что решение может быть извлечено непосредственно из графа планирования с использованием специализированного алгоритма, например такого, который получил название Сгар1трзап. Граф планирования состоит из последовательности 'ж уровней, которые соответствуют временным этапам в плане, где уровень 0 представляет собой начальное состояние. Каждый уровень содержит множество литералов и множество действий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
