Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 157

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 157)

от этапа в декомпозиции с)', для которого предусловие Р является внешним результатом). В данном примере связь Ви?1с)Ноинеал'" — 'Ф Рзпзн)т заменяется связью Раупи?1с)ех — '-— " '5Рйпз эй. На этом завершаются4 дополнения, требуемые для формирования декомпозиций в контексте применения планировщика РОР. Необходимость в дополнительных модификациях алгоритма РОР связана с тем, что действия высокого уровня скрывают информацию об их конечных примитивных реализациях.

В частности, в первоначальном алгоритме РОР осуществляется возврат с индикатором неудачи, если текущий план включает неразрешимый конфликт, т.е. если одно из действий конфликтует с причинной связью, но не может быть переупорядочено так, чтобы оно находилось до или после этой связи (подобный пример приведен на рис. 11.4). При использовании действий высокого уровня, с другой стороны, с виду неразрешимые конфликты иногда могут быть разрешены путем декомпозиции конфликтующих действий и чередования их этапов. Соответствующий пример приведен на рис. 12.5. Таким образом, может возникнуть такая ситуация, что путем декомпозиции может быть получен полный и согласованный план из примитивных действий, даже если не существует полного и согласованного плана из действий высокого уровня.

Такая возможность означает, что полный планировщик НТХ не должен использовать многие варианты отсечения, которые предусмотрены 4 Должны быть также предусмотрены некоторые другие небольшие модификации, которые требуются лля разрешения конфликтов в лействиях высокого уровня; заинтересованный читатель может ознакомиться со статьями, указанными в конце данной главы. Глава 12.

Планирование и осуществление действий в реальном мире 577 для стандартного планировшика РОР. Еше один способ организации работы может состоять в том, чтобы отсечение применялось в любом случае, в надежде на то, что ни одно решение не будет упушено. И'агсй Семь Науру(бйе) Ишай Науру(не) Снам -т Нан а) Первпиачвльиаа прпблепа б) Неспгласпваииый абстрактный план в) Декпиппзишш плака б) лпя пплучеиия согласованного решеиия ))гс. 12.5. Задача "Дары волхвов", взятая из одноименного расоагта ОТенргг, может слузкивь примерам несогласованного абстрактного плана, который, тем не менее, может быть декомпонован в согласованное решение. На рис.

!2.5„а приведена постановка задачи: упоры бедняков есть только две ценные вещи — у него золотые часы, а у нее прекрасные длинные волосы. Каждый из супругов собирается купить подарок, чтобы сделать другому приятное. Он собирается продать свои часы, чтобы купшпь серебряный гр бень для ее волос, а она собирается продать свои волосы, чтобы купить золотую цепочку длн его часов. Частичный план, показанный на рис. 12 5, б, является несогласованным, поскольку не существует способа упорядочит~ абстрактные этапы ОбчесошЬ (Подарить гребень) и о)лгеспабгг (Подарить цепочку) без кон4лггкта.

(Мы предполагаем, что действие обчесошь шпеет предусчавгге на1п (Волосьг), посколысу если бы у жены к таму времени уже не было ее длинных волос, то действие не имело намеченного результата — сделать ей приятное, и аналогично для действия ОбчеСЬа1п.) На рис. 12 5, в показана декомпозиция этапа 0).чесошЬ с помощью метода о1че... (опссес)1г.) (Получение...

под залог). На первом этапе декомпозиции муж получает в свою собственность гребень и вручает его своей жене, дав обязательство передать часы в качестве оплаты в последующую дату. На впюроп этапе он вручает свои часы и выполняет данное обязател~ство. Декампозици» этапа О1чеС па ' г1 осуществляется с помощью аналогичного метода. При условии, что оба этапа дарения упорядочиваготся перед этапами доставки залога, такая декомпозиция становится решением задачи. (Обратите внимание на то, что теперь задача определена тик, что супруги получат удовольствие от использования цепочки вместе с часами и гребня вместе с волосами даже после того, как потеряют право владения на часы и волосы.) Обсуждение вопроса Вначале необходимо отметить определенные сложности: чистая задача планирования НТХ неразрешима (если единственным допустимым способом уточнения 578 Часть \У. Планирование плана является декомпозиция), даже если соответствующее пространство состояний конечно! На первый взгляд такая ситуация может показаться весьма бесперспективной, поскольку основной смысл планирования НТХ состоит в обеспечении высокой эффективности составления планов.

Указанные сложности возникают потому, что декомпозиции действий могут оказаться рекурсивными (например, если выход на прогулку рассматривается как выполнение одного шага с последующим выходом на прогулку), поэтому планы НТХ могут приобретать произвольную длину. В частности, даже кратчайшее решение НТХ может оказаться неопределенно длинным, так что становится невозможным нахождение способа завершения поиска за какоето постоянное время. Тем не менее существуют по меньшей мере три описанных ниже способа исправления указанного положения. 1.

Исключить рекурсию, поскольку она действительно требуется лишь в очень немногих проблемных областях. В таком случае все планы НТХ приобретают конечную длину и могут быть успешно исследованы. 2. Ограничить длину решений, которые нас интересуют. Поскольку пространство состояний является конечным, план, включающий больше этапов, чем имеется состояний в пространстве состояний, обязательно должен включать цикл, в котором неоднократно посещается одно и то же состояние. Мы ничего не потеряем, исключив решения НТХ такого рода, поэтому следует контролировать длину поиска. 3. Принять гибридный подход, в котором сочетается планирование РОР и НТХ. Для определения того, существует ли план, достаточно применить планирование с частичным упорядочением, отдельно взятое, поэтому, безусловно, задача планирования с помощью гибридного подхода является разрешимой.

При использовании третьего метода необходимо соблюдать определенную осторожность. В планировании РОР примитивные действия могут соединяться в цепочки произвольными способами, поэтому иногда приходится сталкиваться с такими решениями, которые очень трудно понять и которые не имеют такой аккуратной иерархической организации, как планы НТХ. Приемлемым компромиссом является управление гибридным поиском таким образом, чтобы операции декомпозиции действий стали предпочтительными по сравнению с операциями добавления новых действий, хотя и не до такой степени, чтобы вырабатывались планы НТХ произвольной длины, прежде чем появится возможность добавления каких-либо примитивных действий.

Один из способов осуществления такого управления состоит в использовании функции стоимости, которая предоставляет благоприятные условия действиям, введенным путем декомпозиции; чем более благоприятными являются эти условия, тем больше поиск будет напоминать чистое планирование НТХ и тем более иерархическим будет решение. Иерархические планы обычно намного проще для выполнения в реальных условиях, поэтому их легче исправить, если что-то при их осуществлении нарушается. Еще одной важной характерной особенностью планов НТХ является возможность совместного использования подзадач. Напомним, что совместным ислользованоем подзадач называется применение одного и того же действия для реализации двух разных этапов в декомпозиции планов. Если совместное использование подзадач запрещено, то каждая конкретизация декомпозиции й' должна быть выполнена Глава 12. Планирование и осушествление действий в реальном мире 579 только одним способом, а не многими, что приводит к отсечению значительной части пространства поиска.

Обычно такое отсечение обеспечивает некоторую экономию времени и в худшем случае приводит к решению, лишь немного более длинному, чем оптимальное. Но в некоторых случаях возникают более сушественные проблемы. Например, рассмотрим цель: "Насладись медовым месяцем и создай большую семью". Библиотека планов может содержать решение "вступи в брак и отправляйся на Гавайи" для первой подцели и "вступи в брак и заведи двух детей" для второй. Без совместного использования подзадач план будет включать два разных действия по вступлению в брак для одного человека, но такой вариант многие считают весьма нежелательным.

Интересным примером анализа затрат и результатов совместного использования подзадач является применение этого метода при оптимизации компиляторов. Рассмотрим задачу компиляции выражения сап (х) -вуп (х) . В большинстве компиляторов такая задача выполняется путем слияния результатов двух отдельных вызовов процедур тривиальным способом; все этапы процедуры вычисления тангенса сап выполняются перед каким-либо из этапов вычисления синуса в1п. Но рассмотрим следующие аппроксимации для эуп и сап с помошью рядов Тэйлора: х 22ха 17х, х1 х х еапх=ха — ь — + —; аьпх=х — — + — —— 3 15 315 ' б 120 50ао Планировщик НТХ с совместным использованием подзадач может выработать более эффективное регцение, поскольку он способен выбрать вариант реализации многочисленных этапов вычисления аьп в сочетании с существующими этапами вычисления сап.

В большинстве компиляторов межпроцедурное совместное использование этапов такого рода не осуществляется, поскольку для них потребовалось бы слишком много времени на рассмотрение всех возможных совместно используемых планов. Вместо этого в большинстве компиляторов каждый субплан вырабатывается независимо и только после этого, возможно, происходит модификация результата с помощью локального оптимизатора. Если учесть все эти дополнительные сложности, вызванные введением декомпозиций действий, можно ли рассчитывать на то, что планирование НТМ окажется эффективным? Фактические причины сложностей трудно проанализировать на практике, поэтому рассмотрим идеализированный случай.

Предположим, например, что необходимо составить план с и действиями. Для неиерархического планировшика с прямым поиском в пространстве состояний при наличии Ь допустимых действий в каждом состоянии затраты составят 0(Ь") . А применительно к планировшику НТХ предположим, что структура декомпозиции является регулярной: каждое непримитивное действие имеет с) возможных декомпозиций, каждая из которых сводится к К действиям на следуюшем, более низком уровне. Необходимо определить, сколько разных деревьев декомпозиции существует в этой структуре.

Итак, если имеется и действий на примитивном уровне, то количество уровней ниже корня равно 1од,п, поэтому количество внутренних узлов декомпозиции определяется выражением 1+)с-~)с'~-...+)г'"х" '= (п-1) 7 ()с-1) . Каждый внутренний узел имеет с( возможных декомпозиций, поэтому существует с('" """ " возможных регулярных деревьев декомпозиции, которые могут быть сформированы. Исследуя эту формулу, можно определить, что уменьшение значения с( и увеличение значения )с позволяет получить огромную экономию: по сути затраты измеряются корнем х-й степени от 580 Часть 1У.

Характеристики

Список файлов книги