Труды КНЦ вып.9 (ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ вып. 10/2018(9))

Тем не менее, существует ряд более серьезных ограничений в представлениях STRIPS и ADL. Во-первых, это атомарное время. В указанных представлениях нет явной модели времени. Нельзя указать продолжительность действия или указать временные ограничения для целей или действий. Фактически, действия моделируются так, как если бы они были мгновенные и бесперебойные, поэтому нет никаких условий для одновременных действий или представления внешних или экзогенных событий. Во-вторых, нет возможности указывать потребности в ресурсах или потребление ресурсов. В-третьих, нет возможности моделировать неопределенность. Первоначальное состояние мира, как и результаты действий, должны быть достоверно известны. Наконец, единственными типами целей являются цели достижения. Невозможно указать цель, которая была бы связана с поддержанием состояния или достижением состояния к крайнему сроку. Отчасти это происходит из-за того, что нет явной модели времени. Также нет возможности указывать цель, которая предполагает оптимизацию. В классическом планировании оптимизация обычно считается несущественной - достаточно просто найти допустимый план. Для устранения некоторых из перечисленных недостатков представления STRIPS и/или ADL были расширены. В частности, в работе [4] были разработаны более богатые модели времени в рамках представления STRIPS и освещены аспекты представления и использования различных типов ресурсов, а в работе [5] рассматривались возможности учета различных форм неопределенности. В [6] введены более интересные типы целей. Все эти усовершенствования в языках представления задач планирования требуют методов, расширяющих возможности классических методов планирования. Однако эти расширения, как правило, оказывают значительное негативное влияние на производительность. Для решения задач классического планирования был разработан ряд различных методов. Здесь мы приведем краткий обзор наиболее важных подходов, перечислим их преимущества и недостатки. До недавнего времени большинство классических работ по планированию сосредотачивалось на построении планов путем обратного поиска или поиска от цели (Goal-directed Planning). Однако, если действия упорядочены только частично, необходимы дополнительные средства, чтобы убедиться, что неупорядоченные действия не мешают друг другу. Для планирования с учетом отношения частичного порядка на множестве действий были разработаны POCL (Partial Order Causal Link) - планировщики [1]. Несмотря на все усилия в области целенаправленного классического планирования (в частности, планирование POCL), эти планировщики не имели большого практического успеха. Хотя коэффициент ветвления обычно ниже при поиске в обратном направлении от целей, он по-прежнему достаточно велик. Как следствие, успех целенаправленного планирования сильно зависит от используемых эвристик. В 1995 году Блюм и Фурст представили систему планирования, названную Graphplan [7], которая использует совсем другой подход для поиска планов. Основная идея состоит в том, чтобы выполнить анализ достижимости, чтобы исключить многие комбинации и последовательности действий, которые несовместимы друг с другом. Как и при планировании POCL, технология Graphplan была расширена для поддержки операторов с кванторами и других особенностей языка ADL [8]. Были предприняты попытки расширить Graphplan для работы с неопределенностью [9, 10], но эти усилия до сих пор не доказали 25