Рассел С., Норвиг П. Искусственный интеллект. Современный подход (2-е изд., 2006) (1245267), страница 151
Текст из файла (страница 151)
554 Часть!Ч. Планирование В языке Бгг)рз применяются описания действий в терминах их предусловий и результатов, а также описания начальных и целевых состояний в виде коньюнкций положительных литералов. В языке АРЕ некоторые ограничения языка Бгг)рз ослаблены и допускается использование дизъюнкции, отрицания и кванторов. Поиск в пространстве состояний может действовать в прямом (прогрессивном) направлении или в обратном (регрессивном) направлении. Эффективные эвристики могут быть получены путем принятия предположения о независимости подцелей, а также с помощью различных ослаблений задачи планирования. В алгоритмах планирования с частичным упорядочением (Рап)а1-Огдег Р1апп)пя — РОР) пространство планов исследуется без стремления к созданию полностью упорядоченной последовательности действий. Такие алгоритмы действуют в обратном направлении от цели, добавляя в план действия, нужные для достижения каждой подцепи.
Такой подход становится особенно эффективным при решении задач, приемлемых для использования подхода по принципу "разделяй и властвуй". Граф планирования может формироваться инкрементно, начиная с начального состояния. Каждый его уровень содержит надмножество всех литералов или действий, которые могут обнаруживаться на данном временном этапе.
Кроме того, на каждом уровне условно задаются отношения взаимного исключения, или взаимно исключаюшие отношения между литералами или действиями, которые не могут происходить одновременно. Графы планирования позволяют получать полезные эвристики для планировшиков в пространстве состояний и планировщиков с частичным упорядочением и могут использоваться непосредственно в алгоритме Стар)зр1ап. Алгоритм стар)зр1ап обрабатывает граф планирования, используя обратный поиск для извлечения плана. Этот алгоритм допускает определенное частичное упорядочение между действиями.
В алгоритме Бдтр1ап задача планирования преобразуется в пропозициональные аксиомы и после этого к ним применяется алгоритм проверки выполнимости для поиска модели, соответствуюшей действительному плану. Было разработано несколько разных пропозициональных представлений, обладающих различной степенью компактности и эффективности. Каждый из основных подходов к планированию имеет своих сторонников, и еше не достигнуто полное согласие в том, какой из этих подходов является наилучшим. Конкуренция между этими подходами и их взаимное обогащение привели к существенному повышению эффективности систем планирования.
БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ Направление планирования в области искусственного интеллекта сформировалось на основе исследований в части поиска в пространстве состояний, локазательства теорем и теории управления, а также на основании практических потребностей робототехники, составления расписаний и других проблемных областей.
Первой Глава 11. Основы планирования 555 важной системой планирования стала система 8!г(рз [466], которая наглядно иллюстрирует продуктивность взаимодействия этих научных направлений. Система Бгг[рз была разработана как планирующий компонент программного обеспечения для проекта создания робота 8!зайеу в институте БК1.
Модель ее общей структуры управления была создана на основе программы ОРБ (Оепега) РгоЫет Бо1чег — общий решатель задач) [!129] — системы поиска в пространстве состояний, в которой используется анализ целей и средств (теапз — епоз апа!уз[а). В системе 5гг1рз применялась одна из версий системы доказательства теорем ОА3 [592] в качестве процедуры определения истинности предусловий для действий.
Точные определения для языка 81г)рз и анализ этого языка представлены Лифшицем [928]. Байлендер [213] показал, что простые задачи планирования 8!г[рз являются РБРАСЕ-полными. В [467] приведена историческая ретроспектива проекта 5гг[рз и дан краткий обзор того, как этот проект связан с более современными разработками в области планирования. Способ представления действий, использовавшийся в системе 51г[рз, оказал гораздо более значительное влияние на дальнейшие разработки, чем ее алгоритмический подход. С тех пор почти во всех системах планирования применяется тот или иной вариант языка Бгг(рз. К сожалению, из-за огромного разнообразия вариантов задача их сравнения стала чрезмерно трудной. Со временем возникло лучшее понимание ограничений и компромиссов между формальными подходами.
В языке АРЕ (Ас11оп Резсг!р!1оп 1.апйиа8е — язык описания действий) [!!95] ослаблены некоторые ограничения языка 81г]рз и создана возможность представлять более реалистичные задачи. В [1119] рассматриваются схемы, применимые для компиляции определений АРЕ в определения 51г[рз. Для использования в качестве стандартизированного синтаксиса, допускающего синтаксический анализ с помощью компьютера, который предназначен для представления определений на языках 8!г[рз, АОЕ и других языках, был предложен язык РОР1 (РгоЫет Оота[п Резспрйоп Еапйца8е — язык описания проблемной области) [548]. РРРЕ использовался в качестве стандартного языка для соревнований по планированию на конференции А!Р8, начиная с 1998 гола.
В первой половине 1970-х годов планировщики в основном применялись для получения полностью упорядоченных последовательностей действий. Декомпозиция задачи осуществлялась путем вычисления субплана для каждой подцели с последующей увязкой субпланов в единую цепочку в некотором порядке. Вскоре было обнаружено, что такой подход, названный;з.
линейным планированием в [1337], является неполным. Он не позволяет решать некоторые очень простые задачи, такие как аномалия Зюссмана (см. упр. 11.! 1), обнаруженная Алленом Брауном во время экспериментов с системой Нас[гег [1474]. Полный планировщик должен обеспечивать сь чередование действий из различных субпланов в пределах единой последовательности. Понятие упорядочиваемых подцелей [837] точно соответствует множеству задач, для которых планировщики без чередования позволяют получить полное решение.
Одним из решений проблемы чередования оказалось планирование с регрессией от цели. Это — метод, в котором этапы полностью упорядоченного плана переупорядочиваются так, чтобы можно было избежать конфликта между подцелями. Данный подход был предложен Уолдингером [! 551], кроме того, использовался в системе %агр1ап Уоррена [1554]. Система %агр!ап замечательна также тем, что была первым планировщиком, написанным на языке логического программирования (Рго1о8), и остается одним из лучших примеров невероятной экономии объема кода, 556 Часть 1У. Планирование которая иногда может быть достигнута с использованием логического программирования: программа т(гагр)ап состоит только из 100 строк кода, что составляет лишь небольшую часть размера сравнимых с ней планировшиков на то время.
Система 1п(егр!ап [1493), [1494) обеспечивала также произвольное чередование этапов плана, что дало возможность преодолеть аномалию Зюссмана и связанные с ней проблемы. К основным идеям, лежащим в основе планирования с частичным упорядочением, относятся обнаружение конфликтов [1493) и защита достигнутых условий от вмешательства [1474). Первыми примерами средств создания планов с частичным упорядочением (которые в то время назывались сетями задач) были планировщик ]ч[оа1т Сакердоти [1337), [1338] н система ]ч[оп! [п Тейта [1494), [1495)'. Планирование с частичным упорядочением в течение следующих 20 лет стало ведущим направлением разработок, несмотря на то, что в течение основной части этого периода специфика данной области не нашла широкого понимания.
Система Тчгеай Чепмена [234) стала образцом логической реконструкции и упрощения работ по планированию, проводимых в то время; формулировки, используемые в этой системе, были достаточно ясными для того, чтобы можно было доказывать полноту и разрешимость (либо )х[Р-трудность и неразрешимость) различных формулировок задач планирования. Эта работа Чепмена привела к созданию Макаллестером и Розенблиттом [1008) полного планировщика с частичным упорядочением, который впервые можно было вполне обоснованно считать имеющим достаточно простое и доступное для чтения описание [1008). Одна из реализаций алгоритма Макаллестера и Розенблитта, разработанная Содерлендом н Уэлдом и получившая название 8]х!1 Р [1444], нашла широкое распространение и впервые позволила многим исследователям изучать и проводить эксперименты по планированию с частичным упорядочением.
Алгоритм рОр, описанный в этой главе, основан на алгоритме 8!х!1 Р. Кроме того, группа Уэлда разработала ()СРОР [1202), первый планировщик для задач, представленных на языке АР) . В планировщике ОСРОР применяется эвристика, в которой учитывается количество невыполненных целей. Применяемый в нем алгоритм работал немного быстрее, чем 8]х[[.Р, но редко оказывался способным находить планы, состоящие больше чем примерно из десяти этапов. Хотя для планировщика ()СРОР были разработаны усовершенствованные эвристики [543], [751), направление планирования с частичным упорядочением постепенно вытеснялось из перспективных исслелований в 1990-х годах по мере появления более быстрых методов.
Но в [1135] было показано, что эта область исследований вполне заслуживает возобновления к ней интереса: предложенный в этой работе планировцзик ДРОР при использовании точной эвристики, полученной из графа планирования, оказался намного более масштабируемым по сравнению с планировщиком Стар)зр1ап и сумел составить конкуренцию самым быстрым планировщикам в пространстве состояний. Работы Аврима Блюма и Меррика Фурста [139], [140) способствовали дальнейшему пробуждению интереса к этой области планирования, поскольку созданная ими система Стар)тр1ап оказалась на несколько порядков величин быстрее по сравнению с планировщиками с частичным упорядочением, применявшимися в то з В терминологии существует некоторая путаница.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
