БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕТКИ
Направление планирования в области искусственного интеллекта сформировалось на основе исследований в части поиска в пространстве состояний, доказательства теорем и теории управления, а также на основании практических потребностей робототехники, составления расписаний и других проблемных областей. Первой важной системой планирования стала система Strips [466], которая наглядно иллюстрирует продуктивность взаимодействия этих научных направлений. Система Strips была разработана как планирующий компонент программного обеспечения для проекта создания робота Shakey в институте SRI. Модель ее общей структуры управления была создана на основе программы GPS (General Problem Solver — общий решатель задач) [1129] — системы поиска в пространстве состояний, в которой используется анализ целей и средств (means—ends analysis). В системе Strips применялась одна из версий системы доказательства теорем QA3 [592] в качестве процедуры определения истинности предусловий для действий. Точные определения для языка Strips и анализ этого языка представлены Лифшицем [928]. Байлендер [213] показал, что простые задачи планирования Strips являются PSPACE-полными. В [467] приведена историческая ретроспектива проекта Strips и дан краткий обзор того, как этот проект связан с более современными разработками в области планирования.
Способ представления действий, использовавшийся в системе Strips, оказал гораздо более значительное влияние на дальнейшие разработки, чем ее алгоритмический подход. С тех пор почти во всех системах планирования применяется тот или иной вариант языка Strips. К сожалению, из-за огромного разнообразия вариантов задача их сравнения стала чрезмерно трудной. Со временем возникло лучшее понимание ограничений и компромиссов между формальными подходами. В языке ADL (Action Description Language — язык описания действий) [1195] ослаблены некоторые ограничения языка Strips и создана возможность представлять более реалистичные задачи. В [1119] рассматриваются схемы, применимые для компиляции определений ADL в определения Strips. Для использования в качестве стандартизированного синтаксиса, допускающего синтаксический анализ с помощью компьютера, который предназначен для представления определений на языках Strips, ADL и других языках, был предложен язык PDDL (Problem Domain Description Language — язык описания проблемной области) [548]. PDDL использовался в качестве стандартного языка для соревнований по планированию на конференции AIPS, начиная с 1998 года.
В первой половине 1970-х годов планировщики в основном применялись для получения полностью упорядоченных последовательностей действий. Декомпозиция задачи осуществлялась путем вычисления субплана для каждой подцели с последующей увязкой субпланов в единую цепочку в некотором порядке. Вскоре было обнаружено, что такой подход, названный линейным планированием в [1337], является неполным. Он не позволяет решать некоторые очень простые задачи, такие как аномалия Зюссмана (см. упр. 11.11), обнаруженная Алленом Брауном во время экспериментов с системой Hacker [1474]. Полный планировщик должен обеспечивать чередование действий из различных субпланов в пределах единой последовательности. Понятие упорядочиваемых подцелей [837] точно соответствует множеству задач, для которых планировщики без чередования позволяют получить полное решение.
Одним из решений проблемы чередования оказалось планирование с регрессией от цели. Это — метод, в котором этапы полностью упорядоченного плана переупорядочиваются так, чтобы можно было избежать конфликта между подцелями. Данный подход был предложен Уолдингером [1551], кроме того, использовался в системе Warplan Уоррена [1554]. Система Warplan замечательна также тем, что была первым планировщиком, написанным на языке логического программирования (Prolog), и остается одним из лучших примеров невероятной экономии объема кода, которая иногда может быть достигнута с использованием логического программирования: программа Warplan состоит только из 100 строк кода, что составляет лишь небольшую часть размера сравнимых с ней планировщиков на то время. Система Interplan [1493], [1494] обеспечивала также произвольное чередование этапов плана, что дало возможность преодолеть аномалию Зюссмана и связанные с ней проблемы.
К основным идеям, лежащим в основе планирования с частичным упорядочением, относятся обнаружение конфликтов [1493] и защита достигнутых условий от вмешательства [1474]. Первыми примерами средств создания планов с частичным упорядочением (которые в то время назывались сетями задач) были планировщик Noah Сакердоти [1337], [1338] и система Nonlin Тейта [1494], [1495]7.
Планирование с частичным упорядочением в течение следующих 20 лет стало ведущим направлением разработок, несмотря на то, что в течение основной части этого периода специфика данной области не нашла широкого понимания. Система Tweak Чепмена [234] стала образцом логической реконструкции и упрощения работ по планированию, проводимых в то время; формулировки, используемые в этой системе, были достаточно ясными для того, чтобы можно было доказывать полноту и разрешимость (либо NP-трудность и неразрешимость) различных формулировок задач планирования. Эта работа Чепмена привела к созданию Макаллестером и Ро-зенблиттом [1008] полного планировщика с частичным упорядочением, который впервые можно было вполне обоснованно считать имеющим достаточно простое и доступное для чтения описание [1008]. Одна из реализаций алгоритма Макаллестера и Розенблитта, разработанная Содерлендом и Уэлдом и получившая название SNLP [1444], нашла широкое распространение и впервые позволила многим исследователям изучать и проводить эксперименты по планированию с частичным упорядочением. Алгоритм POP, описанный в этой главе, основан на алгоритме SNLP.
Кроме того, группа Уэлда разработала UCPOP [1202], первый планировщик для задач, представленных на языке ADL. В планировщике UCPOP применяется эвристика, в которой учитывается количество невыполненных целей. Применяемый в нем алгоритм работал немного быстрее, чем SNLP, но редко оказывался способным находить планы, состоящие больше чем примерно из десяти этапов. Хотя для планировщика UCPOP были разработаны усовершенствованные эвристики [543], [751], направление планирования с частичным упорядочением постепенно вытеснялось из перспективных исследований в 1990-х годах по мере появления более быстрых методов. Но в [1135] было показано, что эта область исследований вполне заслуживает возобновления к ней интереса: предложенный в этой работе планировщик RePOP при использовании точной эвристики, полученной из графа планирования, оказался намного более масштабируемым по сравнению с планировщиком Graphplan и сумел составить конкуренцию самым быстрым планировщикам в пространстве состояний.
7 В терминологии существует некоторая путаница. Многие авторы используют термин нелинейный (nonlinear) вместо "частично упорядоченный" (partially ordered). Такое употребление терминов немного отличается от первоначального употребления, которое в работах Сакердоти относилось к чередующимся планам.
Работы Аврима Блюма и Меррика Фурста [139], [140] способствовали дальнейшему пробуждению интереса к этой области планирования, поскольку созданная ими система Graphplan оказалась на несколько порядков величин быстрее по сравнению с планировщиками с частичным упорядочением, применявшимися в то время. За ней вскоре последовали разработки других систем с графами планирования, такие как IPP [813], Stan [491] и SGP [1569]. Структура данных, весьма напоминающая граф планирования, была разработана немного раньше Галлабом и Ларуэл-лем [549], которые использовали такую структуру данных в планировщике с частичным упорядочением IxTeT для получения точных эвристик, применяемых для управления поиском. В [1136] приведен очень подробный анализ эвристик, полученных на основе графов планирования. Приведенное в этой главе описание графов планирования главным образом основано на этой работе и на конспектах лекций, подготовленных Суббарао Камбхампати (Subbarao Kambhampati). Как уже указывалось в этой главе, граф планирования позволяет управлять поиском решения задачи с помощью многих способов. Например, победителем соревнования по планированию на конференции AIPS 2002 года стал алгоритм LPG [544], в котором осуществляется поиск в графах планирования с использованием метода локального поиска, основанного на алгоритме WalkSAT.
Подход к планированию как проверке выполнимости и алгоритм SATplan были предложены Каутцем и Селманом [778], которых натолкнул на эту идею поразительный успех в использовании жадного локального поиска для решения задач проверки выполнимости (см. главу 7). Кроме того, Каутц и др. [777] исследовали различные формы пропозициональных представлений для аксиом Strips и обнаружили, что наиболее компактные формы не обязательно способствуют достижению наименьшей продолжительности вычисления решения. Систематический анализ был проведен Эрнстом и др. [442], которые разработали также автоматический "компилятор" для формирования пропозициональных представлений из формулировок задач на языке PDDL. Планировщик Blackbox, в котором объединены идеи алгоритмов Graphplan и SATplan, был разработан Каутцем и Селманом [779].
Повторное пробуждение интереса к планированию в пространстве состояний было в основном вызвано появлением программы UnPOP, разработанной Макдер-моттом [1024], который впервые предложил эвристику с учетом расстояния, основанную на ослабленной задаче с исключенными списками удаления. Само название UnPOP (отказ от POP) стало реакцией на чрезмерное в то время сосредоточение работ на планировании с частичным упорядочением; Макдермотт считал, что другие подходы не получают того внимания, которого они заслуживают. В алгоритме HSP (Heuristic Search Planner — планировщик с эвристическим поиском) Бонета и Гефф-нера [147] и его разработанных позже аналогах впервые удалось добиться практического применения поиска в пространстве состояний при решении крупных задач планирования. В то время самым успешным алгоритмом поиска в пространстве состояний был алгоритм FastForward, или FF, Хоффмана [667], который стал победителем в соревновании по планированию на конференции AIPS в 2000 году. В алгоритме FF используется упрощенная эвристика для графа планирования в сочетании с очень быстрым алгоритмом поиска, представляющим собой новаторское объединение прямого и локального поиска.
В дальнейшем появился интерес к использованию представления планов в виде бинарных диаграмм решения (binary decision diagram — BDD) — компактного описания конечных автоматов, которое широко исследовалось в сообществе разработчиков средств проверки аппаратного обеспечения [266], [1031]. Существуют методы доказательства свойств бинарных диаграмм решения, включая свойство быть решением задачи планирования. В [261] представлен планировщик, основанный на этом подходе. Применялись также другие представления; например, в [1549] приведен обзор использования целочисленного программирования для планирования.
Точки над "/" в этом вопросе еще окончательно не расставлены, но уже появились некоторые интересные сопоставления различных подходов к планированию. В [646] проанализировано несколько классов задач планирования и показано, что подходы на основе ограничений, такие как Graphplan и SATplan, являются наилучшими для NP-трудных проблемных областей, а подходы на основе поиска лучше подходят для проблемных областей, в которых приемлемые решения могут быть найдены без поиска с возвратами. Алгоритмы Graphplan и SATplan сталкиваются с затруднениями при использовании в проблемных областях со многими объектами, поскольку наличие большого количества объектов означает, что в этих алгоритмах приходится создавать много действий. В некоторых случаях возникновение такой проблемы можно отсрочить или вообще ее избежать, вырабатывая пропозиционали-зированные действия динамически, по мере необходимости, а не конкретизируя их все до начала поиска.
В [1567], [1568] приведены два превосходных обзора современных алгоритмов планирования. Любопытно наблюдать за тем, какие изменения произошли за пять лет, которые прошли за время между этими двумя обзорами: первый из них сосредотачивался на планировании с частичным упорядочением, а во втором были представлены алгоритмы Graphplan и SATplan. В книге Readings in Planning [19] приведена всеобъемлющая антология многих из самых лучших ранних статей в этой области, включая несколько хороших обзоров. В [1629] приведен обзор методов планирования с частичным упорядочением, который занимает целую книгу.
Исследования по планированию играли центральную роль в искусственном интеллекте со времени появления этого научного направления, а статьи по планированию занимают основной объем ведущих журналов и материалов конференций по искусственному интеллекту. Проводятся также специализированные конференции по планированию, такие как International Conference on AI Planning Systems (AIPS), International Workshop on Planning and Scheduling for Space и European Conference on Planning.
11.1. Опишите различие и сходство между решением задач и планированием.
11.2. При наличии аксиом, приведенных в листинге 11.1, определите все применимые конкретные экземпляры действия Fly(p, from, to) в состоянии, описанном следующим выражением:
At (Pi, JFK) л At(P2l SFO) A Plane (Pi) л Plane (P2) л Airport{JFK) A Airport{SFO)
11.3. Рассмотрим, как можно было бы преобразовать множество схем Strips в ак-
сиомы состояния-преемника ситуационного исчисления (см. главу 10).
• Изучите схему для действия Fly{p, from, to). Запишите логическое определение для предиката FlyPrecond{p, from, to, s), который является