АНАЛИЗ РАЗЛИЧНЫХ ПОДХОДОВ К ПЛАНИРОВАНИЮ
Планирование — это область искусственного интеллекта, которая в настоящее время привлекает значительный интерес. Одна из причин такой ситуации состоит в том, что в планировании объединяются два основных направления развития искусственного интеллекта, которые рассматривались нами до сих пор, — поиск и логика. Это означает, что любой планировщик может рассматриваться либо как программа, в которой осуществляется поиск решения, либо как такая программа, которая (конструктивно) доказывает существование решения. Такое перекрестное обогащение идеями, взятыми из этих двух областей, привело не только к повышению производительности, которое за последнее десятилетие достигло нескольких порядков величины, но и к расширению использования планировщиков в производственных приложениях. К сожалению, у нас еще нет четкого понимания того, какие методы являются в наибольшей степени подходящими для задач того или иного типа. Вполне возможно также, что появятся новые методы, которые вытеснят существующие.
Планирование главным образом представляет собой такое занятие, в котором приходится держать под контролем комбинаторный взрыв. Если в проблемной области имеется р примитивных высказываний, то количество состояний становится равным 2Р. В сложных проблемных областях величина р может стать весьма значительной. Следует также учитывать, что объекты в проблемной области характеризуются не только свойствами (Location, Color и т.д.), но и отношениями (At, On, Between и т.д.). При наличии d объектов в проблемной области с тернарными от-
,3
ношениями количество состояний достигает 2а . Ha этом основании можно сделать вывод, что в наихудшем случае попытка решить задачу планирования становится безнадежной.
Мощным средством преодоления подобной пессимистической ситуации становится подход по принципу "разделяй и властвуй". В наилучшем случае (при полной декомпонуемости задачи) подход "разделяй и властвуй" обеспечивает экспоненциальное ускорение работы. Однако декомпонуемость нарушается из-за отрицательных взаимодействий между действиями. Планировщики с частичным упорядочением позволяют справиться с такой ситуацией с помощью причинных связей — мощного подхода к формированию представлений, но, к сожалению, каждый конфликт должен быть разрешен с помощью выбора определенного варианта (связанного с размещением конфликтующего действия до или после связи), а количество таких вариантов может увеличиваться экспоненциально. Алгоритм Graphplan позволяет избежать необходимости использования этих вариантов на этапе формирования графа, поскольку в нем для регистрации конфликтов используются взаимно исключающие связи, а выбор варианта, касающегося того, как должны быть разрешены эти конфликты, фактически не осуществляется. Алгоритм SATplan предоставляет аналогичный набор взаимно исключающих отношений, но в нем для этого применяется общая форма CNF, а не специальная структура данных. Насколько успешным окажется такой подход, зависит от области применения решателя задач SAT.
Иногда возможность эффективного решения задачи обеспечивается путем определения того, какие отрицательные взаимодействия могут быть исключены. Задача называется имеющей упорядочиваемые подцели, если существует такой порядок подцелей, что планировщик может достичь их в указанном порядке, не будучи вынужденным отменять какую-либо из ранее достигнутых подцелей. Например, если в мире блоков цель состоит в построении столбика (например, в котором блок А стоит на В, который, в свою очередь, стоит на С, стоящем, в свою очередь, на столе, Table), то подцели являются упорядочиваемыми снизу вверх: если вначале будет достигнута подцель "С на Table", то никогда не придется ее отменять в ходе достижения других подцелей. Планировщик, в котором используется такой прием с упорядочением снизу вверх, способен решить любую задачу в проблемной области мира блоков без возвратов (хотя и может оказаться, что он не всегда находит самый короткий план).
В качестве более сложного примера укажем, что для планировщика Remote Agent, который управлял космическим аппаратом Deep Space One агентства NASA, было определено, что высказывания, касающиеся управления космическим аппаратом, являются упорядочиваемыми. По-видимому, в этом нет ничего удивительного, поскольку космический аппарат проектируется его разработчиками так, чтобы была возможность управлять им как можно проще (разумеется, с учетом всех прочих ограничений). Пользуясь преимуществом последовательного упорядочения целей, планировщик Remote Agent был способен в процессе планирования устранять основную часть поиска. Это означает, что он оказался достаточно быстродействующим для того, чтобы с его помощью можно было управлять этим космическим аппаратом в реальном времени, а такая задача раньше казалась невыполнимой.
Существует несколько способов ограничения комбинаторного взрыва. Как было показано в главе 5, есть несколько методов управления возвратами в задачах удовлетворения ограничений (Constraint Satisfaction Problem — CSP), таких как возвраты, управляемые зависимостями. Все эти методы могут применяться и в планировании. Например, задачу извлечения решения из графа планирования можно сформулировать как булеву задачу CSP, переменные которой указывают, должно ли данное конкретное действие произойти в данное конкретное время. Эту задачу CSP можно решить с использованием любого из алгоритмов, приведенных в главе 5, такого как алгоритм с минимальными конфликтами. Тесно связанный с этим метод, используемый в системе Blackbox, состоит в преобразовании графа планирования в выражение CNF, а затем извлечении плана с использованием решателя задач SAT. По-видимому, такой подход обладает более высокой производительностью, чем SATplan, и причиной этого, скорее всего, является то, что в графе планирования уже устранены многие невозможные состояния и действия из рассматриваемой задачи. Кроме того, такой подход действует лучше по сравнению с алгоритмом Graphplan, по-видимому, из-за того, что поиск условий выполнимости, подобный алгоритму WalkSAT, характеризуется гораздо большей гибкостью, чем ограниченный поиск с возвратами, используемый в алгоритме Graphplan.
Нет никакого сомнения в том, что такие планировщики, как Graphplan, SATplan и Blackbox, привели к значительному прогрессу в области планирования, поскольку позволили, во-первых, поднять уровень производительности систем планирования, а во-вторых, дали возможность понять связанные с этим представительные и комбинаторные проблемы. Однако эти методы по своей сути являются пропозициональными и поэтому предназначены исключительно для использования в тех проблемных областях, которые они способны представить. (Например, задачи планирования экспедиторской доставки с несколькими десятками объектов и местонахождений могут потребовать гигабайтов памяти для хранения соответствующих выражений CNF.) Создается впечатление, что для достижения дальнейшего прогресса в этой области потребуются представления и алгоритмы в логике первого порядка, хотя такие структуры, как графы планирования, по-прежнему будут оставаться полезным источником эвристик.
В этой главе определена задача планирования в детерминированных, полностью наблюдаемых вариантах среды. В ней описаны основные представления, используемые для задач планирования, и представлено несколько алгоритмических подходов к их решению. Наиболее важные понятия, изложенные в этой главе, перечислены ниже.
• Системы планирования основаны на использовании алгоритмов решения задач, которые применяются к явным представлениям состояний и действий в пропозициональной логике (или логике первого порядка). Такие представления обеспечивают возможность получения эффективных эвристик, а также разработки мощных и гибких алгоритмов для решения задач планирования.
• В языке Strips применяются описания действий в терминах их предусловий и результатов, а также описания начальных и целевых состояний в виде конъюнкций положительных литералов. В языке ADL некоторые ограничения языка Strips ослаблены и допускается использование дизъюнкции, отрицания и кванторов.
• Поиск в пространстве состояний может действовать в прямом (прогрессивном) направлении или в обратном (регрессивном) направлении. Эффективные эвристики могут быть получены путем принятия предположения о независимости подцелей, а также с помощью различных ослаблений задачи планирования.
• В алгоритмах планирования с частичным упорядочением (Partial-Order Planning — POP) пространство планов исследуется без стремления к созданию полностью упорядоченной последовательности действий. Такие алгоритмы действуют в обратном направлении от цели, добавляя в план действия, нужные для достижения каждой подцели. Такой подход становится особенно эффективным при решении задач, приемлемых для использования подхода по принципу "разделяй и властвуй".
• Граф планирования может формироваться инкрементно, начиная с начального состояния. Каждый его уровень содержит надмножество всех литералов или действий, которые могут обнаруживаться на данном временном этапе. Кроме того, на каждом уровне условно задаются отношения взаимного исключения, или взаимно исключающие отношения между литералами или действиями, которые не могут происходить одновременно. Графы планирования позволяют получать полезные эвристики для планировщиков в пространстве состояний и планировщиков с частичным упорядочением и могут использоваться непосредственно в алгоритме Graphplan.
• Алгоритм Graphplan обрабатывает граф планирования, используя обратный поиск для извлечения плана. Этот алгоритм допускает определенное частичное упорядочение между действиями.
• В алгоритме SATplan задача планирования преобразуется в пропозициональные аксиомы и после этого к ним применяется алгоритм проверки выполнимости для поиска модели, соответствующей действительному плану. Было разработано несколько разных пропозициональных представлений, обладающих различной степенью компактности и эффективности.
• Каждый из основных подходов к планированию имеет своих сторонников, и еще не достигнуто полное согласие в том, какой из этих подходов является наилучшим. Конкуренция между этими подходами и их взаимное обогащение привели к существенному повышению эффективности систем планирования.