Анализ методов интеллектуального планирования.

Хронология подходов интеллектуального планирования при классических допущениях

На рисунке 1. представлена хронология подходов к решению задачи интеллектуального планирования при классических допущениях.

Рисунок 1 - Хронология подходов классического планирования

Начало исследованиям в области планирования положено работами [26,41,40, 25], в которых планирование рассматривалось как доказательство теорем.

Системам на основе доказательства теорем был присущ ряд недостатков. Наиболее существенными из них являлись: 1) крайне низкая производительность, 2) проблема фрейма.

Эти недостатки привели к созданию подходов, основанных на поиске в пространстве состояний [24, 49, 38,16].

Алгоритмы на основе поиска в пространстве состояний в некоторых случаях оказались негибкими, и в новом поколении методов задача планирования была сформулирована как поиск в пространстве частично-упорядоченных планов [20, 22, 34, 42].

Одновременно с развитием идеи частичных планов развивалась идея иерархического планирования [47, 46, 55], которое подразумевает создание планировщиком иерархии абстракций (подцелей). Это упрощает процедуру планирования - вначале создается план в общих чертах, затем выполняется детализация - спуск по иерархии. Это позволяет сосредочить вычислительные мощности на решении первостепенных задач. Иерархическое планирование также интересно тем, что лишь на основе этого подхода создано большинство реально работающих систем [51, 54].

Иерархическое планирование возможно как при поиске плана в пространстве состояний [46], так и при поиске планов в пространстве планов [47].

В начале 90-х годов, в связи с появлением высокопроизводительных алгоритмов решения задачи удовлетворения ограничений (CSP-задача), задачи проверки истинности в пропозициональной логике (SAT-задача), стала популярной постановка задачи планирования как CSP-задачи [17] и как SAT-задачи [31]. Это позволило значительно повысить скорость синтеза планов. Одновременно с этим появились работы, в которых задача планирования рассматривалась как задача целочисленного линейного программирования (ILP-задача) [33] или как задача построения бинарных диаграмм решений (BDD-задача) [48, 21].

Начиная с 1998 года, стали появляться первые планировщики, использующие эвристики для поиска плана [18, 27, 30, 44]. Конечно же, использование эвристик для решения задач не является свежей идеей. Но лишь недавно появились механизмы автоматизированного извлечения эвристик из описания домена планирования. В значительной степени, этому способствовало выделение некоторых свойств структур, используемых алгоритмами Graphplan и Satplan.

В разделах 1.2.3-1.2.6 будут подробнее рассмотрены некоторые подходы к решению задачи планирования при классических допущениях на примерах работы конкретных алгоритмов.

Планирование как доказательство теорем

Одним из примеров системы доказательства теорем, использовавшейся для решения задачи планирования, является система QA3 [26].

В системе QA3 одно множество утверждений использовалось для описания начального состояния, а другое - для описания эффектов действий. Чтобы следить за тем, какие факты являются истинными и в каком состоянии, в каждый предикат включаются переменные, отвечающие состоянию. Целевое условие описывалось формулой с переменной, связанной квантором существования.

Задача системы состоит в том, чтобы доказать существование состояния, в котором истинно целевое условие. В основе доказательства лежит метод резолюций [45].

Эксплуатация QA3 показала, что вывод в такой системе получается очень медленным.

Кроме того, для неё не существовало сколько-нибудь приемлемого решения проблемы фрейма [43]. Суть этой проблемы состоит в том, что действие может иметь нелокальный эффект, т.е., в общем случае, не ясно какие формулы, описывающие состояние системы, изменяются при применении действия. Это, приводило к тому, что в описание действия включались утверждения об изменении (не изменении) каждого факта, представленного в состоянии. Очевидно, что в сложных предметных областях описание эффектов действия значительно усложняется. Достаточно элегантное решение проблемы фрейма предложено в [7].

Поиск в пространстве состояний

Первым планировщиком, осуществляющим планирование в пространстве состояний, является STRIPS (STanforci Research Institute Problem Solver) [52].

STRIPS изначально разрабатывался для решения задачи формирования плана поведения робота, перемещающего предметы через множество помещений.