ОСНОВЫ ПЛАНИРОВАНИЯ
В данной главе показано, каким образом агент может воспользоваться информацией о структуре задачи для создания сложных планов действий.
Планированием называется процесс выработки последовательности действий, позволяющих достичь цели. До сих пор в этой книге рассматривались два примера планирующих агентов: описанный в главе 3 агент, осуществляющий решение задач на основе поиска, и логический планирующий агент, который представлен в главе 10. Данная глава в основном посвящена описанию вопросов расширения области применения агентов и ее распространения на сложные задачи планирования, которые нельзя решить с помощью подходов, рассматривавшихся до сих пор.
В разделе 11.1 разрабатывается выразительный, но тщательно регламентированный язык для представления задач планирования, включая действия и состояния. Этот язык тесно связан с представлениями действий в пропозициональной логике и логике первого порядка, которые рассматривались в главах 7 и 10. В разделе 11.2 описано, как можно использовать эти представления в алгоритмах прямого и обратного поиска в основном с применением точных эвристик, которые могут создаваться автоматически исходя из структуры представления. (Используемый при этом способ аналогичен способу формирования эффективных эвристик для задач удовлетворения ограничений в главе 5.) В разделах 11.3—11.5 описаны алгоритмы планирования, которые выходят за рамки прямого и обратного поиска и позволяют воспользоваться имеющимся представлением задачи. В частности, представлены подходы, позволяющие не ограничиваться рассмотрением только полностью упорядоченных последовательностей действий.
В данной главе рассматриваются лишь такие варианты среды, которые являются полностью наблюдаемыми, детерминированными, конечными, статическими (изменения происходят только в результате действий агента) и дискретными (с точки зрения времени, действий, объектов и результатов). Такая среда называется средой классического планирования. В отличие от этого, неклассическое планирование предназначено для частично наблюдаемых или стохастических вариантов среды и для него требуется другой набор алгоритмов и проектов агентов, описанный в главах 12 и 17.
ЗАДАЧА ПЛАНИРОВАНИЯ
Рассмотрим, что может произойти, когда обычный агент, решающий задачи с помощью стандартных алгоритмов поиска (поиска в глубину, поиска А* и т.д.), сталкивается с крупными задачами реального мира. Это позволит нам научиться разрабатывать лучших планирующих агентов.
Наиболее очевидная сложность состоит в том, что агент, решающий задачи, может быть просто подавлен огромным количеством действий, не относящихся к делу. Рассмотрим задачу покупки одного экземпляра англоязычного издания настоящей книги с названием AI: A Modern Approach в электронном книжном магазине. Предположим, что агент-покупатель должен совершить одно действие, связанное с покупкой, в расчете на каждый возможный десятицифровой номер ISBN, что приводит к общему количеству действий, равному 10 миллиардам. В ходе применения алгоритма поиска агент должен исследовать состояния результатов всех 10 миллиардов действий, чтобы определить, какое из них соответствует цели, заключающейся в том, чтобы приобрести экземпляр книги с номером ISBN 0137903952. С другой стороны, разумный планирующий агент должен быть способным проработать процедуру покупки в обратном направлении, от явного описания цели, такого как Have{ISBN0137903952), и непосредственно сформировать действие Buy {ISBN013 7'903952). Для этого агенту требуется иметь общие знания о том, что действие Виу(х) приводит к результату Have{x). При наличии этих знаний и цели планировщик может определить в единственном шаге унификации, что правильным действием является Buy (ISBN013 7903952).
Еще одна сложность заключается в определении хорошей эвристической функции. Предположим, что цель агента состоит в том, чтобы купить четыре разных книги в оперативном режиме. Количество планов только для четырех этапов покупки будет составлять 1040, поэтому поиск без точной эвристики даже нет смысла рассматривать. Для человека очевидно, что хорошей эвристической оценкой для стоимости состояния является количество книг, которые еще предстоит купить; к сожалению, эта идея не столь очевидна для агента, решающего задачи, поскольку он рассматривает процедуру проверки цели как "черный ящик", который возвращает истину или ложь в ответ на каждое состояние. Поэтому агент, решающий задачи, не обладает автономностью; он требует, чтобы человек предоставлял ему эвристическую функцию для каждой новой задачи. С другой стороны, если планирующий агент имеет доступ к явному представлению цели как конъюнкции подцелей, то может использовать единственную эвристику, независимую от проблемной области, — количество невыполненных конъюнктов. Для задачи покупки книг цель будет представлять собой выражение Have {А) л Have {В) л Have {С) л Have{D), а состояние, содержащее выражение Have {А) л Have (С), будет иметь стоимость 2. Таким образом, агент автоматически получает правильную эвристику для этой задачи и для многих других. Ниже в этой главе будет показано, как формировать более сложные эвристики, в которых учитываются не только структура цели, но и возможные действия.
Наконец, агент-решатель задач может оказаться неэффективным из-за того, что не способен воспользоваться декомпозицией задачи. Рассмотрим задачу доставки множества пакетов ночной почты по соответствующим адресатам, которые разбросаны по всей Австралии. В данном случае имеет смысл найти аэропорт, ближайший к каждому адресату, и разделить общую задачу на несколько подзадач, по одной на каждый аэропорт. А в самом множестве пакетов, доставляемых через каждый конкретный аэропорт, можно определить в зависимости от города адресата допустимость дальнейшей декомпозиции. Как было описано в главе 5, способность выполнять декомпозицию такого рода обеспечивает повышение эффективности решателей задач удовлетворения ограничений. Такое же утверждение остается справедливым для планировщиков: в наихудшем случае может потребоваться время 0(п\) для поиска наилучшего плана доставки п пакетов, но если существует возможность выполнить декомпозицию этой задачи на к равных частей, затраты времени будут составлять только 0( (п/к) ! хк).
Как было отмечено в главе 5, идеально декомпонуемые задачи являются очень привлекательными, но встречаются редко1. Проекты многих систем планирования (особенно планировщиков с частичным упорядочением, описанных в разделе 11.3) основаны на предположении, что большинство задач реального мира являются "частично декомпонуемыми. Это означает, что планировщик может работать над подцелями независимо, но, скорее всего, ему потребуется также выполнить определенную дополнительную работу по объединению результирующих субпланов. Применительно к некоторым задачам такое предположение не оправдывается, поскольку велика вероятность того, что работа над одной подцелью будет приводить к разрушению результатов работы над другой подцелью. Именно из-за такого взаимодействия подцелей и являются трудноразрешимыми многие головоломки (подобные задаче игры в восемь).