Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 143
Текст из файла (страница 143)
Сушествует также возможность создавать ослабленные задачи, удаляя отрицательные результаты без удаления предусловий. Таким образом, если некоторое действие в первоначальной задаче имеет результат А л — В, то в ослабленной задаче будет иметь результат А. Это означает, что не нужно беспокоиться об отрицательных взаимодействиях субпланов, поскольку ни одно действие не способно удалить лите- 527 Глава 11.
Основы планирования ралы, достигнутые другим действием. Стоимость решения полученной в конечном итоге ослабленной задачи задает то, что принято называть эвристикой с Ъ. пустым списком удаления. Эта эвристика является весьма точной, но для ее вычисления требуется действительно выполнить некоторый (простой) алгоритм планирования. Тем не менее на практике поиск в условиях ослабленной задачи часто происходит достаточно быстро для того, чтобы имело смысл применение этой оценки стоимости. Описанные здесь эвристики могут использоваться либо в прогрессивном, либо врегрессивном направлении.
Ко времени написания данной книги первые места врейтинге эффективности занимали прогрессивные планировшики, в которых применялась эвристика с пустым списком удаления. Такая ситуация вполне может измениться в результате исследования новых эвристик и новых методов поиска. Поскольку задачи планирования являются экспоненциально трудными', ни один алгоритм не может быть достаточно эффективным лля решения всех задач, но с использованием эвристических методов, описанных в этой главе, могут быть решены многие практические задачи, и таких задач стало гораздо больше по сравнению с теми, которые были решаемыми всего лишь несколько лет тому назад. 11.3. ПЛАНИРОВАНИЕ С ЧАСТИЧНЫМ УПОРЯДОЧЕНИЕМ Прямой и обратный поиск в пространстве состояний представляют собой особые формы поиска полностью упорядоченного плана. В них рассматриваются только строго линейные последовательности действий, непосредственно связанные с начальным или целевым состоянием.
Это означает, что такие методы поиска не позволяют воспользоваться преимуществами декомпозиции задачи. Вместо того чтобы обеспечить отдельную проработку каждой подзадачи, эти методы вынуждены всегда поддерживать принятие решений о том, как упорядочить действия, относящиеся ко всем подзадачам.
Но обычно более предпочтительным является подход, позволяющий работать над несколькими подцелями независимо, достигать их с помощью нескольких субпланов, а затем объединять эти субпланы. Подобный подход обладает также тем преимушеством, что позволяет добиться большей гибкости при определении последовательности, в которой составляется окончательный план. Это означает, что планировшик вначале может работать над "очевидными" или "важными" решениями, не будучи вынужденным прорабатывать все этапы в хронологическом порядке. Например, планируюший агент, который находится в Беркли и желает попасть в Монте-Карло, может вначале попытаться найти рейс из Сан-Франциско в Париж; получив информацию о времени отправления и прибытия этого рейса, он может затем заняться поиском способов того, как доехать и выехать из соответствующих аэропортов. Обшая стратегия, в которой в процессе поиска выбор определенных этапов откладывается на более позднее время, называется стратегией с Ъ.
наименьшим вкладом (1еам сопцпйгпепг). Формального определения стратегии с наименьшим вкладом не существует, поскольку очевидно, что на любом этапе поиска должен быть сделан т Формально процедура планирования в стиле 5тпрв является РьРАСЕ-полной, если только не рассматриваются действия, которые имеют только положительные прсдусловия и лишь один литерал результата 12г4] 528 Часть 1~(.
Планирование определенный вклад в окончательное решение, так как в противном случае поиск окажется непродуктивным. Несмотря на такую неформальность, наименьший вклад — это полезная концепция для анализа того, какие решения должны быть приняты в любой задаче поиска. Приведенный в этом разделе первый конкретный пример будет гораздо проше по сравнению с планированием отпуска, проводимого в Монте-Карло. Рассмотрим простую задачу надевания пары туфель. Ее можно описать как формальную задачу планирования следующим образом: Ооат(ддядсэдоеоп п ЬеГСБйоеоп) Гпзс () Асехоп(ЯДРДСБДое,Рсесопои ЕдяъсБосяоп,ЕГСесс: Ятддсддоеоп) Ассдоп(лдядСБос(с,вггесс: Лдяпсдос(гоп) АсСДоп(ъеГСБпое,Рсесопс(: ЬеЕСБос(гоп,ЕйгесС: ЬеЮСБЬоеоп) Асг' (ЬесСБ (с,дссесс: ЬесСБ Коп) Планировщик должен быть способен предложить последовательность из двух действий, ((зр)зсдос)с (надеть правый носок), затем дздпсБ(зое (надеть правую туфлю), чтобы достичь первого конъюнкта этой цели, и последовательность еегсБОО)с (надеть левый носок), затем еегс5(зое (надеть левую туфлю), чтобы достичь второго конъюнкта.
После этого эти две последовательности могут быть объединены для создания окончательного плана. В ходе этого планировщик будет манипулировать двумя подпоследовательностями независимо, не задумываясь над тем, должно ли какое-то действие в одной последовательности быть выполнено до или после некоторого действия в другой. Любой алгоритм планирования, способный включить в план два действия без указания того, какое из них должно быть выполнено первым, называется Ъ. планировщиком с частичным упорядочением (рап(а!- ог((ег р!аппег).
На рис. 11.2 показан план с частичным упорядочением, который представляет собой решение задачи надевания туфель и носков. Обратите внимание на то, что это решение представлено в виде графа, а не последовательности действий. Заслуживают также внимания "фиктивные" действия„называемые Бсагс и еупд Б)з, которые отмечают начало и конец плана. Назвав эти ситуации действиями, мы можем упростить структуру плана, поскольку теперь каждый этап плана становится действием. Это решение с частичным упорядочением соответствует шести возможным планам с полным упорядочением; каждый из них называется Ж линеаризацией плана с частичным упорядочением.
Планирование с частичным упорядочением может быть реализовано в виде поиска в пространстве планов с частичным упорядочением. (Начиная с этого момента, мы будем называть их просто "планами".) Это означает, что поиск начинается с пустого плана. После этого рассматриваются способы уточнения плана до тех пор, пока не удастся составить полный план, который решает данную задачу. Действия, рассматриваемые в этом поиске, являются не действиями в мире, а действиями в планах: добавление в план этапа; наложение упорядочения, согласно которому одно действие должно занять место перед другим; и т.д. В данном разделе будет определен алгоритм РОР (Ран(а1-Ог((ег Р1апп(пд) для планирования с частичным упорядочением.
В соответствии с об(цепринятой традицией алгоритм РОР оформляется в виде отдельной программы, но мы вместо этого определим задачу планирования с частичным упорядочением как экземпляр задачи поиска. Это позволит нам сосредоточиться на этапах уточнения плана, которые могут Глава 11. Основы планирования 529 Планы с полным Гпорялоченисм План с частичным Гиорялочением Ееутхаслоп Ятгят3асяпп Ееутхяоеоп, Лтгятхяаепп о иявь Рис. 11.2. План надевания туфель и носков с частичным упорядочением и шесть сооптветпсптвую- шил линеаризаиий в виде планов с полным упорядочением Напомним, что состояниями рассматриваемой задачи поиска должны быть планы (в основном незаконченные). Чтобы избежать путаницы с состояниями мира, мы будем вести речь о планах, а не о состояниях.
Каждый план имеет описанные ниже четыре компонента, где первые два определяют этапы плана, а последние два выполняют функции учета, позволяющие определить, как может быть дополнен план. ° Множество действий, из которых состоят этапы плана. Эти действия берутся из множества действий в задаче планирования. "Пустой" план содержит только действия 8сагс и рзпзн)т. Действие Всакс не имеет предусловий, а его результатом являются все литералы в начальном состоянии задачи планирования.
Действие Ыпйн)т не имеет результатов, а его предусловиями являются литералы цели в задаче планирования. ° Множество 'в.ограничений упорядочения. Каждое ограничение упорядочения находится в форме А ч В, которая читается как "А перед В ' и означает, что действие А должно быть выполнено в какое-то время перед действием в, но не обязательно непосредственно перед ним.