Система планирования решений задач на основе дедуктивных и ассоциативных методов

Планирование в сложных проблемных областях всегда рассматривалось как род интеллектуальной деятельности. Интерес специалистов по искусственному интеллекту (ИИ) к автоматизации планирования возник чуть ли не одновременно с формированием ИИ как направления научных исследований. В начале 60-х годов появились первые системы автоматического планирования. Самая известная из них — универсальный решатель задач — GPS (General Problem Solver, см. [Newell et al., 59]). За прошедшее время были достигнуты значительные успехи в создании планирующих систем, многие из которых и сейчас применяются в различных практических областях: планировании проведения экспериментов, проектировании циклов производства, управлении роботами.

Автоматизация планирования по-прежнему является актуальной темой исследований, поскольку становится необходимым применение программ-планировщиков в новых сложных проблемных областях, где предъявляются высокие требования к качеству получаемых планов. На современном уровне развития программирования реализованные в системах ИИ приемы и методы планирования все еще не адекватны приемам и методам, применяемым человеком при решении сложных задач. Решению этой проблемы также уделяется большое внимание.

Рассмотрим появившиеся за последние несколько лет системы искусственного интеллекта, которые осуществляют планирование в каких-либо проблемных областях. При рассмотрении не будем ограничиваться одной узкой областью, поскольку цель обзора — исследовать современное состояние дел в приложениях искусственного интеллекта для планирования.

Среди большого количества разнообразных исследовательских тем в рассматриваемой области можно выделить четыре основных направления: 1. Повышение эффективности систем планирования и автоматически генерируемых планов. К этому направлению относятся работы, посвященные модификации ранее разработанных методов планирования, а также поиску новых методов планирования и специальных методов, предназначенных для получения эффективных планов. Примерами систем, разработанных в этом направлении, могут служить: АВALONE (CLAM) — [Melis and Whittle, 97]- IPP.

Koehler, 98]- UCPOP+PARSE — [Barrett and Weld, 94]- PBR (UCPOP) — [Ambite and Knoblock, 97].

2. Применение автоматических планировщиков и решателей задач в практических проблемных областях. Исследования в данном направлении нацелены на адаптацию методов планирования, успешно решающих модельные задачи, к решению реальных задач, в которых приходится иметь дело с неполными и противоречивыми данными. Такой подход проявился в системах: BURIDAN -[Kushmerick et al., 94]- СЕР — [Aylett et al., 98].

3. Новые способы организации процесса планирования. В этом направлении ведутся разработки систем, которые при планировании сочетают различные методы и стратегии. Также исследуются возможности построения планировщиков без использования схемы логического вывода — на основе других парадигм, например, парадигмы генетического программирования. Новые способы организации планирования предложены в системах: OMEGA -[Melis and Whittle, 97]- SYNERGY — [Muslea, 97].

4. Разработка средств поддержки планирования. Работы в этом направлении ведутся с целью обеспечить взаимодействие между пользователем и планирующей системой на качественно новом уровне. Разрабатываются средства создания баз знаний, системы объяснений и системы-ассистенты, которые решают задачи планирования при активном участии пользователя. Системы: TRAINS-96 — [Ferguson et al., 96]- TRIPS — [Ferguson et al., 98]- O-Plan — [Tate, 96]- EXPECT — [Gil and Melz, 96].

Перейдем к детальному рассмотрению систем планирования, перечисленных выше.

Процедура планирования ABALONE применяется в решателе CLAM, предназначенном для автоматического доказательства теорем (см. [Melis and Whittle, 97]). Она реализует метод доказательства теорем по аналогии, который, как считают авторы, существенно увеличивает возможности системы автоматического доказательства теорем. Основная идея метода в том, что, имея план доказательства исходной теоремы, можно построить план доказательства для целевой теоремы. Для этого строится отображение (mapping) исходной теоремы в целевую. Затем на основании этого отображения осуществляется преобразование исходного плана в план для целевой теоремы. При этом в план доказательства могут быть добавлены новые шаги, а также он может быть переформулирован.

Авторы называют свой метод внешней аналогией, поскольку целевая и исходная теоремы могут быть совершенно независимы. Например теорема sum (x)+sum (y)=sum (x+y) может быть доказана аналогично доказательству теоремы x<>(y<>z)=(xoy)<>z. В ряде других систем (PLAGIATOR, Mural) используется внутренняя аналогия, где теоремы должны быть больше похожи. Реализованный в ABALONE подход имеет меньше ограничений по применению.

Процедура планирования по аналогии ABALONE представляет собой последовательность шагов:

1. Найти отображение исходной теоремы в целевую.

2. Расширить его, сопоставляя правила исходного доказательства и правила для доказательства целевой теоремы.

3. Принять решение о переформулировании (на основании образцов из отображения).

4. Следуя исходному плану применить по аналогии методы для целевой теоремы. Что означает:

— Произвести переформулирование.

— Если условия применения метода выполнены, то применить метод, иначе попытаться добиться выполнения условий.

— Если этого невозможно добиться, то оставить в плане изъян.

Учет условий, ассоциированных с методами, позволяет контролировать корректность полученного плана. Изъяны в планах, остающиеся, когда аналогия не позволяет построить полного доказательства, могут быть устранены с помощью обычной техники доказательства (дедуктивно).

В работе [Melis and Whittle, 97] авторы приводят пример доказательства по аналогии и результаты экспериментов. Применение планирования по аналогии повысило эффективность решателя clam и позволило получить доказательства теорем, на которых ранее решатель терпел неудачу. Стоит отметить, что для некоторых теорем были получены неполные планы доказательств. Авторы считают, что новая версия решателя, которая будет расширена другими методами доказательства, будет способна полностью решить эти задачи.

В решателе IPP усовершенствован традиционный метод планирования на основе «расписания целей» (goal agenda), что позволило ускорить нахождение плана (см. [Koehler, 98]). IPP применяется для решения задач планирования, постановка которых состоит из набора операторов проблемной области, набора ограничений, начального и целевого состояний. Описание целевого состояния для рассматриваемых задач можно представить в виде цепочки целей, которые необходимо достигнуть. К задачам такого рода относятся широко известные модельные задачи: «мир кубиков», «задача о саквояже», «ханойские башни».

Авторы предлагают, прежде чем начинать планирование проанализировать связи между целями, то есть определить отношение порядка в пространстве целей. Упорядочивание может быть проблемно-зависимым (например, кубик должен быть сначала покрашен, а лишь потом отполирован) или проблемно-независимым. Примером отношения порядка, независимого от проблемной области, может служить отношение, определяемое авторами следующим образом:

Цель В предшествует цели, А (В -< А), если не существует плана, исполнимого из любого состояния, в котором, А удовлетворена, достигающего цели В и оставляющего цель, А достигнутой при своем выполнении.

В работе предложены еще несколько способов определения отношения порядка целей, а также способ упорядочивания наборов целей.

При упорядочивании целей получается ориентированный граф, вершины которого — цели, а ребра указывают порядок целей. На основе такого графа строится расписание целей, использовать которое можно разными способами:

• определить стратегию выбора текущей цели в соответствии с расписанием;

• повторно использовать планы для подзадач при достижении последующих целей;

• собирать главный план путем комбинирования планов для подзадач. Нахождение плана по расписанию целей (gb g2, ., gn) предлагается осуществлять по следующему алгоритму:

1) Найти план pi достижения цели gi из начального состояния I. По полученному плану построить начальное состояние 12 для планирования цели g2. (I2 — R (I, pi)).

2) Найти план р2 достижения цели g2 из начального состояния 12. Построить начальное состояние 1з для достижения цели g3. (I3 = R (I, pi°p2)) п) Найти план рп достижения цели gn из начального состояния In = R (I, pi°p20—°pn-i)-В работе [Koehler, 98] приводятся результаты решения различных задач с использованием данного метода. Как показывают эксперименты, упорядочивание целей перед началом решения некоторых задач позволяет сильно сузить перебор (а значит, уменьшить объем требуемой памяти и время построения плана), но в то же время полученные планы не являются оптимальными. Авторы утверждают, что выигрыш по памяти и времени счета с лихвой окупает небольшое снижение эффективности планов.

Еще один результат исследований, проведенных разработчиками системы IPP, состоит в том, что для некоторых проблемных областей упорядочивание целей не приносит ожидаемых результатов. Авторам не удалось применить свой подход в задаче «логистика» (logistics), задаче «поезда» (trains) и задаче «ракета» (rocket). Эти домены специфичны тем, что в них, по-видимому, не существует естественных способов упорядочивания целей.

В работе [Barrett and Weld, 94] предлагается новый подход к построению планировщика на основе декомпозиции задач, применение которого позволяет повысить скорость поиска планов, не снижая их эффективности. Традиционно в системах, базирующихся на декомпозиции задач, реализуется построение плана сверху вниз путем разбиения целей на подцели и действия до тех пор, пока не будет получен план, состоящий только из действий. Авторы предлагают подход к редукции задач на основе восходящего разбора плана (plan parsing). Его основаалгоритм UCPOP+PARSE, состоящий из следующих шагов:

1. Инициализация. Построение начального плана Р и начального множества разборов Parses.

2. Проверка на окончание. Если Р решает задачу, то вернуть Р в качестве результата.

3. Уточнение. Получить множество возможных уточнений плана стандартной процедурой UCPOP-refine-plan, и случайным образом выбрать текущий план Р из множества.

4. Разбор. Изменить множество разборов Parses в соответствии с новым текущим планом. Если получено пустое множество разборов, то выбрать другой текущий план.

5. Перейти на шаг 2.

Алгоритм является модификацией или, своего рода, надстройкой над алгоритмом планирования системы UCPOP. Процедура UCPOP-refine-plan для текущего плана возвращает множество планов порождаемых исправлением одного «изъяна» в текущем плане. Если исправляемый «изъян» — невыполненное предусловие какого-либо действия, то новый план получается добавлением в текущий план новой причинной связи (возможно, и новых действий). Если исправляется конфликт между действиями, то происходит либо переупорядочивание шагов плана, либо добавляются новые подцели, либо накладываются новые ограничения.

В алгоритме UCPOP+PARSE используются схемы редукции (декомпозиции) целей, которые как и набор возможных действий в проблемной области должны быть заранее определены пользователем. Эти схемы компилируются в процедуры init-parses и extend-parses. Первая вызывается в начале планирования и создает множество разборов, соответствующих цели задачи (при этом выясняется какие схемы декомпозиции можно применить для нее). Процедура extend-parses строит множество разборов, соответствующих текущему плану. При этом схемы редукции рассматриваются как грамматика, описывающая язык планов, которые можно построить по этим схемам. Пересечение множества предложений этого языка с множеством всевозможных цепочек действий дает множество решений. Если для текущего плана невозможно построить разбор, то он отвергается, и рассматривается другой план. Таким образом, осуществление разбора планов одновременно с их построением гарантирует, что в план будут добавлены только те действия, которые будут полезны при достижении цели. Это главное преимущество предложенного метода, по сравнению с обычным планированием в UCPOP.

Авторы приводят пример решения задачи по предложенному алгоритму. Метод, основанный на разборе планов, сравнивается с обычной редукцией задач. Приводятся два типа абстрактных задач, для первого из которых метод UCPOP+PARSE дает решение, а редукция порождает бесконечный цикл, а для второго типа задач наблюдается обратная картина. Но неясно, могут ли такие задачи возникать на практике. Сравнение двух схем, проведенное авторами на тестовых задачах, не позволило однозначно выявить преимущество одной схемы над другой. Авторы также проводили сравнение UCPOP+PARSE с UCPOP при решении тестовых задач. Результаты показывают, что разбор планов позволяет сократить время планирования и требуемые ресурсы.

Разработанный алгоритм сочетает в себе особенности планирования на основе ограничений и планирования, базирующегося на редукции задач, что роднит данную систему с предыдущей (IPP), авторы которой также пытались переосмыслить и модифицировать традиционную схему. Продолжение своих исследований разработчики UCPOP+PARSE видят в том, чтобы реализовать методы автоматического распознавания и накопления схем декомпозиции задач.

В отличие от методов сокращения затрат на планирование, применяемых в рассмотренных выше системах UCPOP+PARSE и IPP, метод PBR предназначен для поиска высокоэффективных планов (см. [Ambite and Knoblock, 97]), то есть основное внимание уделяется не эффективности поиска, а эффективности плана.

Авторы видят два источника сложности поиска эффективного плана:

• выполнимость (сложность нахождения какого-либо плана для решения проблемы);

• оптимизация (сложность поиска оптимального решения в соответствии с выбранной ценой).

В разных проблемных областях соотношение этих составляющих разное. Распространены, так называемые, оптимизационные проблемные области, где неэффективное решение найти легко, и основную трудность составляет поиск оптимального решения (например, «мир кубиков»), В таких случаях авторы предлагают применять метод — «планирование через переписывание» (Planning By Rewriting). Его идея состоит в том, чтобы сначала найти неоптимальное, но законченное решение задачи — начальный план, состоящий из действий, а потом модифицировать его до тех пор, пока не будет получен план требуемого уровня эффективности (его цена будет снижена до приемлемого уровня).

Метод восходит к известным методам локального поиска, применяемым при решении оптимизационных задач. Схема действий в методе такова:

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

2) Создается множество планов, полученных переписыванием исходного по какому-либо из правил переписывания планов. Каждое из правил представляется в виде: если <условия> то заменить <заменяемое> на <замена>, где <условия> - это список образцов, которые бывают трех типов (операторы, причинные связи, ограничения), <заменяемое> - удаляемые из плана образцы, а <замена> - добавляемые в план образцы. Правило применяется, только если в текущем плане распознаны все образцы из его условия, тогда производится предписываемая правилом замена операторов, связей или ограничений, входящих в план.

3) Среди полученного множества выбирается следующее приближение к эффективному плану. Для этого могут использоваться так называемые методы «спуска». Например, можно выбрать первый план с ценой меньшей, чем у предыдущего, или взять тот, у которого наименьшая цена среди всех рассматриваемых планов.

4) Если очередной план обладает достаточной эффективностью, то процесс прекращается и текущий план возвращается в качестве результата. Иначе осуществляется переход на второй шаг.

Методы «спуска» имеют недостаток, заключающийся в том, что может быть получен локальный, а не глобальный минимум. В таких случаях, авторы рекомендуют применять традиционные приемы: рестарт и случайное блуждание.

Предложенный метод РВЕ реализован в системе на базе планировщика иСРОР. Решались задачи в трех областях — «мир кубиков», «планирование выполнения запросов» и «управление производством». Начальный план находился традиционным методом, а затем включался процесс переписывания плана. Испытания показали, что поиск оптимального плана по предложенной схеме требует меньше времени. Метод может успешно применяться при планировании выполнения запросов, где важно иметь какое-либо решение в случае, когда время поиска оптимального решения превышает выделенный для этого интервал.

Авторы предложили список универсальных правил переписывания, которые могут повысить эффективность планов в любой проблемной области:

• «переупорядочивание» (изменение порядка этапов плана);

• «сжатие» (замена большого подплана меньшим, более дешевым);

• «расширение"1 (замена одного действия на последовательность более мелких и дешевых);

• «распараллеливание» (уменьшение количества упорядочивающих ограничений в плане).

Эти универсальные правила являются образцами для создания конкретных правил для конкретных областей, что позволяет считать PBR универсальным методом поиска высокоэффективных планов.

Разработчики PBR, как и разработчики UCPOP+PARSE, фактически, предлагают использовать при планировании методы, которые традиционно применяются при разработке программ, что довольно естественно, так как программы и планы имеют много общего. Однако с этим связаны проблемы применимости методов. В области программирования применимость методов повышения эффективности обосновывается довольно сложно. Для планирования эти проблемы приобретают дополнительную сложность, поскольку планы не являются столь же формализованными конструкциями, как программы.

От методов повышения эффективности планов перейдем к следующему направлению исследований в рассматриваемой области. Исследователей в этом направлении интересует применение методов планирования для решения практических задач.

Проблема построения выводов на основе неопределенных данных давно исследуется специалистами в области ИИ. Так одна из первых экспертных систем, успешно осуществляющих рассуждения при наличии неопределенности, — MYCIN — была создана в середине семидесятых годов. Следующая рассматриваемая нами работа показывает, что исследования этой проблемы еще продолжаются. Ее авторы предлагают BURIDAN — алгоритм вероятностного планирования, основанный на.

1 Примеров правил типа «расширение» в экспериментальных задачах найдено не было, но авторы считают, что в некоторых проблемных областях подобные правила могут быть актуальны (см. [Ambite and Knoblock, 97]). распространении ограничений (см. [Kushmerick et al., 94]). Он предназначен для решения задач, описанных в терминах пространства состояний и набора операторов, обладающих следующими особенностями:

1) Текущее состояние проблемной области в любой момент времени t определено неоднозначно. Оно описывается набором состояний, каждому из которых приписана вероятность того, что именно это состояние является текущим.

2) Эффекты от применения операторов также неоднозначны. Применение оператора изменяет состояние проблемной области на одно из вероятных состояний.

3) Решением задачи считается последовательность операторов, позволяющая достичь целевого состояния с вероятностью не меньше заданной.

Алгоритм BURIDAN основан на предложенном Сасердоти (см. [Sacerdoti, 77]) методе планирования путем распространения ограничений. Планирование происходит циклически. Каждый раз выбирается один из частичных планов и оценивается вероятность его успеха, и если она превышает необходимый уровень, то частичный план выдается в качестве решения. В противном случае осуществляется уточнение текущего плана, после чего следует выбор нового текущего плана, его оценка и т. д. В целом, алгоритм BURIDAN напоминает алгоритм планирования на основе распространения ограничений (например, реализованный в системе UCPOP). Разница лишь в том, что в UCPOP оценивается завершенность плана, а в BURIDAN — вероятность его успеха.

Для алгоритма BURIDAN авторами предложены структуры для описания состояний проблемной области и операторов с учетом указанной неопределенности. Также разработана специальная сетевая структура для представления частичных планов, используемая при планировании. Предложены методы вычисления вероятности успеха частичных планов.

В работе [Kushmerick et al., 94] приводится пример решения задачи планирования действий робота при наличии неопределенности, демонстрирующий особенности алгоритма. Результаты работы можно рассматривать, как удачную попытку модифицировать традиционный алгоритм, применимый для надежных данных, с целью его использования при планировании в условиях неопределенности.

Еще одна работа (см. [Aylett et al., 98]) исследует возможность применения традиционных методов планирования для решения практических задач. В ней рассматривается применение системы искусственного интеллекта для планирования технологических процессов на химическом производстве. Авторы подчеркивают, что разработанный ими планировщик СЕР работает в реальной проблемной области (а не в демонстрационной, как «мир кубиков») и решает практические задачи.

Каждая задача, которая решается СЕР, делится на три части:

1) собственно, планирование технологического процесса;

2) обеспечение безопасности;

3) выработка последовательности открывания вентилей (организация потока) при транспортировке химических реагентов по трубам.

Проблемная область (конкретное химическое производство) описывается набором операторов, определяющих функционирование узлов производства, схемой, определяющей основные узлы, агрегаты и связи между ними, и ограничениями, накладываемыми по соображениям безопасности. Для представления операторов выбран подход, предложенный в системе STRIPS (явно указываются позитивные и негативные эффекты применения оператора), и, в целом, чувствуется влияние этой системы на СЕР.

В статье большое внимание уделяется инженерии знаний в выбранной проблемной области. Анализ особенностей химического производства, проведенный авторами, показывает, что задача организации потока должна решаться одновременно с остальными задачами. Произвести организацию потока независимо от планирования технологического процесса в общем случае невозможно. Кроме того, операторный подход при организации потока не применим, так как нельзя заранее определить все последствия применения того или иного оператора. Для решения этой задачи авторы предложили создать специальный «под-решатель» — планировщик потока. Он по необходимости вызывается основным планировщиком, решающим общую задачу планирования технологического процесса.

Для повышения универсальности СЕР каждому планировщику потоков ставится в соответствие специальный макрооператор. Таким образом, СЕР может использоваться на разных химических установках, особенности организации потока в каждой из которых описаны в библиотеке макрооператоров. Такой подход предложен, с целью обеспечить компромисс между универсальностью системы и ее специализацией, необходимой для решения задач в реальной проблемной области.

В системах относящихся к следующему направлению исследований особое внимание уделяется организации процесса планирования. В работе [Melis, 98] рассматривается построение системы автоматического доказательства теорем, в которой применяются несколько стратегий при поиске доказательства. Это одна из работ, направленных на поиск новых способов организации планирования.

Основными отправными пунктами в исследовании для авторов работы являются следующие положения:

• Использование разных стратегий позволяет адаптировать планирование к временным ресурсам выделенным, для него. Например, при большом ресурсе времени можно применять одну стратегию, а при малом — другую.

• Применение различных стратегий соответствует тому, как люди решают сложные задачи. Примерами стратегий, используемых человеком, являются: применение правил, аналогия, вникание в детали.

Подход с использованием нескольких стратегий реализован в системе OMEGA (другой вариант названия — OMEGA) — планировщике доказательств теорем. Как и во многих системах планирования знания представлены в OMEGA в виде операторов. Оператор OMEGA — это структура со следующими полями:

• предпосылка (premises), цели и допущения, добавляемые в план при применении оператора;

• заключение (conclusions), цели, для достижения которых служит оператор;

• условия применимости (application-conditions);

• описание схемы доказательства (proof-schema).

Постановка задачи состоит из начального состояния (допущений, в условиях которых нужно доказать теорему) и целевого состояния (формулировки утверждения теоремы).

Система использует более пяти методов построения доказательства, в частности: прямой поиск в пространстве состояний (forward state-space), обратный поиск в пространстве состояний (backward state-space), иерархическое планирование (expansion of abstract operators), уточнение на основе абстракции (abstractrefinement), изолированное уточнение (island-refinement) и другие. Два последних из перечисленных методов предложены авторами работы. Они используются совместно и позволяют уточнять план доказательства на основе абстракции-конкретизации. Абстрактное уточнение плана производится для аналога исходной теоремы на более высоком уровне абстракции. При этом в план добавляются абстрактные шаги, которые затем в ходе изолированного уточнения отображаются в действия (шаги начального уровня абстракции).

При планировании с использованием любого метода происходит уточнение одной и той же структуры данных — плана доказательства. Общая процедура планирования такова:

1. Осуществляется проверка, не является ли план, поданный на вход, решением. Если является, то он выдается в качестве ответа. Если процедура проверки терпит неудачу, то результатом работы является неуспех, иначе осуществляется переход на следующий шаг.

2. Выбирается одна из стратегий уточнения плана и применяется. (Здесь нет точки возврата.).

3. Рекурсивно вызывается процедура планирования для уточненного плана. Управление выбором стратегий осуществляется с помощью специальных управляющих правил. Эти правила подобны тем, которые используются в системе PRODIGY. Они содержат метапредикаты, описывающие условия, которые накладываются на историю планирования, текущее состояние, ресурсы, ограничения. Авторы проводят классификацию управляющих правил:

• о стратегии (например, если обратный поиск и прямой поиск неудачны, то применить метод абстрактного уточнения);

• об операторе (такие управляющие правила описывают способ отбора операторов для различных стратегий);

• о цели;

• о способах абстракции (для абстрактного уточнения);

• о способах отображения абстрактных шагов (для изолированного уточнения).

В работе [Melis, 98] приводится пример построения доказательства теоремы с использованием различных стратегий. В целом, работа не позволяет судить о степени завершенности разрабатываемой системы планирования, применяющей несколько стратегий. К сожалению, не приведен язык описания управляющих правил. Все же необходимо отметить, что автору удалось показать, что планирование с использованием нескольких стратегий является перспективным методом решения сложных интеллектуальных задач, к которым относится задача построения доказательств теорем.

Следующая рассматриваемая система — SYNERGY — система планирования общего назначения, основанная на парадигме генетического программирования (см. [Muslea, 97], [Muslea, 98]). Генетическое программирование является альтернативой традиционным декларативному и процедурному подходам. Система в процессе планирования не использует ни логический вывод, ни редукцию подзадач. Вместо этого для построения плана производятся искусственные мутации, скрещивание, воспроизведение и отбор по пригодности среди частичных планов, каждый из которых представляется особью некоторой популяции.

Общая схема работы системы такова: система получает на вход задачу А, преобразует ее в задачу генетического программирования (GP-problem) В, затем решает задачу В по алгоритму генетического программирования и преобразует полученное решение задачи В в план для искомой задачи А. Основное преимущество такой схемы состоит в том, что алгоритм генетического программирования обладает высоким параллелизмом, поскольку оценка пригодности каждой особи в популяции производится независимо.

Решение задачи генетического программирования происходит следующим образом:

1. Создается начальная популяция частичных планов, составленных из «строительных блоков» — функций и терминалов, которые получены в ходе анализа исходной задачи.

2. Проверяется пригодность особей в популяции. Если какой-то частичный план обладает достаточной пригодностью, то он возвращается системой в качестве ответа, в противном случае — переход на третий шаг.

3. Создается новая популяция путем репродукции (включения особей предыдущей популяции в новую без изменений) и скрещивания (получения новых особей, составленных из компонент особей предыдущей популяции). Затем осуществляется переход на второй шаг.

Система SYNERGY решает задачи планирования в разных проблемных областях. Это обеспечивается специальным проблемно-независимым механизмом преобразования исходных задач в задачи генетического программирования. Постановка исходной задачи для SYNERGY включает в себя описание проблемной области:

• множество состояний;

• набор операторов;

• дополнительная информация (эвристики, и т. д.) — и собственно постановку задачи:

• начальное состояние;

• целевое состояние, которое нужно достичь.

Преобразование в задачу генетического программирования происходит в системе автоматически, поэтому в SYNERGY наложены ограничения на представление операторов проблемной области. Операторы имеют процедурное представление на языке Лисп, и в их явно указаны удаляемые и добавляемые при их применении факты. Переформулированная постановка задачи представляет собой набор функций и терминалов (строительного материала для частичных планов), функций оценки пригодности и примеров пригодности.

Система успешно решает различные модельные задачи: «мир кубиков», задачу о поиске пути для робота, поиск пути для двух роботов (усложненный вариант предыдущей задачи, при котором возможны конфликты), задачу о портфеле. Автор приводит результаты экспериментов и сравнивает SYNERGY с системой UCPOP (традиционная система планирования основанная на методе «распространения ограничений»). Сравнение показывает, что для простых задач SYNERGY проигрывает по скорости, но сложные решает гораздо быстрее. Немаловажным достоинством своей системы автор считает то, что при преобразовании задач сохраняется строгая типизация операторов, что предотвращает генерацию заведомо негодных планов с неверной структурой. Тем самым решается главная проблема, связанная с разницей между областью планирования, в которой типы играют важную роль, и генетическим программированием, где типизация отсутствует.

Уместно заметить, что эффективность SYNERGY при решении задачи зависит от используемой функции оценки пригодности. Правильно подобранная функция пригодности позволяет получить решение на небольшом числе порожденных популяций, но универсальной функции пригодности эффективной для каждой задачи нет. Пользователь, предлагая системе использовать ту или иную функцию пригодности, участвует в планировании, и во многом от него зависит эффективность поиска ответа. Следует иметь в виду, что задача нахождения подходящей функции оценки пригодности зачастую сложнее, чем исходная задача, для которой система ищет ответ.

К недостаткам системы можно отнести и то, что SYNERGY не имеет возможности выдать пользователю логичное объяснение процесса построения плана. Тем не менее, работы над системами планирования, базирующимися на парадигме генетического программирования, еще только в начале.

Созданию средств поддержки планирования посвящены работы [Gil and Melz, 96] и [Gil and Swartout, 96], в которых описывается среда EXPECT, автоматизирующая процесс занесения новых знаний пользователем. EXPECT проводит анализ базы знаний и находит ошибки и пропуски в ней, после чего предлагает пользователю способы, как их исправить. Особенностью системы является явное представление стратегий решения задач в виде методов. Это повышает гибкость системы, поскольку при использовании новой стратегии система позволяет адаптировать существующую базу знаний к ней. Для других средств, основанных на ограничении ролей (role-limiting), таких как SALT, MOLE, MORE и PROTEGE, характерна жесткая привязка к конкретной стратегии решения задач. Каждое из таких средств позволяет создавать базы знаний, подразумевающих использование при планировании единственной стратегии или схемы, которая не может быть изменена. Среда EXPECT от этого недостатка избавлена.

Знания в базах, создаваемы с помощью EXPECT, делятся на три типа:

• факты проблемной области;

• терминология (описание основных типов и ролей);

• методы (знания о способах решения задач).

Основным модулем системы, предназначенным для поиска ошибок в базе знаний, является специальный решатель задач (problem solver). Для выяснения взаимосвязей между методами в базе, перед решателем ставится обобщенная абстрактная цель, которая представляет собой все типы целей из проблемной области. Решатель ищет способы достижения поставленной цели. В результате его работы строится дерево поиска, на основании которого можно судить о полноте и корректности базы знаний. Типичные ошибки обнаруживаемые системой:

1) в теле метода поставлена цель, для достижения которой в базе не существует соответствующих методов;

2) в теле метода используется роль, не определенная для данного типа;

3) выражение из тела метода имеет неверные аргументы;

4) выражение имеет несоответствующий тип результата.

С каждым типом ошибок в системе EXPECT связаны способы исправления ошибки, которые будут предложены пользователю при ее обнаружении. Например, ошибку первого типа можно исправить одним из следующих способов: изменить тело методаизменить тип цели в каком-либо другом методедобавить новый метод.

Авторы рассматривают процесс накопления знаний с помощью EXPECT на различных примерах. Продемонстрировано, как EXPECT помогает создавать базы знаний для разных проблемных областей, и как происходит адаптация существующей базы знаний при изменении стратегии (на примере стратегии выдвижения и проверки гипотез). Среда использует один и тот же механизм для накопления как проблемно-зависимых знаний, так и проблемно-независимых и может использоваться для любых стратегий решения задач, которые определит пользователь.

В качестве недостатка системы можно отметить, что EXPECT исследует базу знаний только на полноту и синтаксическую корректность, не уделяя внимания поиску противоречий и уменьшению избыточности.

Обеспечение высокого уровня взаимодействия с пользователем важно не только при создании баз знаний. Одним из новых подходов к планированию является планирование со смешанной инициативой (mixed initiative planning), при котором пользователь активно участвует в процессе планирования (см. [Tate, 97]). Система TRAINS-96 (см. [Ferguson et al., 96]) и ее более поздняя версия TRIPS (см. [Ferguson et al., 98]) — интегрированные системы планирования, разработанные в Рочестерском университете. Особенностью этих систем является тесное взаимодействие с пользователем в ходе решения задачи. Системы ведут диалог с пользователем на естественном языке, и решение находится в результате тесного взаимодействия с ним.

Система TRIPS сочетает планирование с распознаванием и генерацией речи и является интеллектуальным помощником в решении задач перевозки и логистики. Архитектура системы состоит из трех слоев:

1. Слой «обработки модальности», который осуществляет акты взаимодействия системы с пользователем.

2. Слой управления диалогом — ядро системы.

3. Слой специальных решателей, осуществляющих планирование, составление расписаний и решение других задач из проблемной области.

Второй слой обеспечивает интеграцию интеллектуальных возможностей системы. Он организован в виде двух взаимодействующих агентов-модулей: агента поддержки разговора (conversational agent — СА) и менеджера планирования (problem solving manager — PSM). СА координирует всю активность системы, связанную со взаимодействием с пользователем. Общение с пользователем поделено на отдельные акты взаимодействия (запросы, вопросы, предположения, предложения, подтверждения, опровержения и социальные акты: приветствия, поздравления и извинения). Система обрабатывает акты взаимодействия, произведенные пользователем, генерирует ответные акты и передает задания PSM на основании правил вида: интерпретация -> ответ. PSM распределяет полученные задачи среди набора решателей и возвращает ответ. Взаимодействие между агентами происходит на языке, основанном на языке представления знаний KQML, используемом в многоагентных системах.

В работе [Ferguson et al., 98] приводится пример диалога с пользователем, в ходе которого решается задача составления плана и расписания перевозок. Испытания предшественника TRIPS — системы TRAINS-96 показали, что во время работы контрольной группы пользователей 90% сеансов работы закончились успешно, т. е. поставленные задачи были решены. Совместная работа пользователя и системы над общим планом позволяет решать более сложные задачи, чем те, с которыми каждый из них может справиться в одиночку.

Крупный проект по созданию открытой архитектуры планирования O-Plan ведется в Институте приложений искусственного интеллекта (AIAI) Эдинбургского университета при поддержке агентства DARPA и исследовательской лаборатории военно-воздушных сил США (US Air Force Research Laboratory, Rome). Планирование со смешанной инициативой и планирование на основе ограничений являются одними из главных тем этого проекта (см. [Tate, 97]). Архитектура O-Plan представляет собой набор взаимодействующих интеллектуальных агентов, каждый из которых является либо постановщиком задач, либо планировщиком, либо исполнителем планов. В роли агентов могут выступать как программы, так и люди. Разработанная структура программного агента включает в себя следующие компоненты:

• представление возможностей агента по обработке данных;

• вычислительные средства агента, обеспечивающие обработку данных;

• средства манипуляции ограничениями и средства поддержки планирования и формирования команд;

• компоненты принятия решения о последующих действиях агента;

• средства взаимодействия с другими агентами.

Взаимодействие между агентами происходит на основе представления планов как наборов ограничений на базе модели, описанной в работе [Tate, 96]. Модель — это иерархия универсальных типов ограничений, пригодных для представления планов из любой предметной области. В модели предусмотрены средства для представления временных ограничений, ограничений на используемые ресурсы и другие специальные виды ограничений. Модель обеспечивает высокоуровневое взаимодействие между планирующими интеллектуальными агентами (людьми и программами).

В рамках проекта O-Plan были разработаны системы планирования для решения различных задач: конструирования орбитальной платформы, планирования и управления запуском спутника, проектирования и постройки зданий, логистики, планирования эвакуации гражданского населения, принятия решений в кризисной ситуации.

В обзорной части мы рассмотрели современные системы планирования, относящиеся к перечисленным выше направлениям исследований в области ИИ. В данной диссертационной работе проблема планирования решений сложных задач рассматривается на примере решателя геометрических задач (РГЗ, решатель). В рамках классификации, введенной в обзоре, его можно отнести к исследовательским системам первого и третьего направлений в области ИИ (повышение эффективности планирования и разработка новых способов управления планированием). РГЗ имеет ряд особенностей по сравнению с рассмотренными системами:

1. Решатель реализует планирование на основе стереотипов (подход, предложенный в работе [Корухова и Любимский, 94]), построенное на естественных для человека принципах планирования.

2. В созданной версии решателя предложена схема организации планирования, которая предоставляет возможности по добавлению и настройке методов планирования, применяемых при решении задач, без внесения изменений в основную часть РГЗ. Эти возможности значительно больше, чем предоставляемые системой OMEGA. В решатель включен класс специальных управляющих стереотипов, реализующих различные методы и стратегии планирования, обеспечивающих сочетание различных методов и управляющих построением плана.

3. В рамках РГЗ предложен новый метод планирования — ассоциативное планирование на основе близких ситуаций. Этот метод используется в сочетании с другими методами планирования, реализованными в РГЗ, что позволяет получать эффективные решения задач. Планирование на основе близких ситуаций относится к методам планирования по аналогии, таким как метод ABALONE в системе clam Реализованный в решателе метод существенно отличается от метода ABALONE и других методов такого типа. В рамках ассоциативного планирования аналогия проводится между ситуациями в проблемной области, а не между решениями различных задач. При этом не предполагается построение отображения решаемой задачи в задачу, для которой известно решение. Ассоциативное планирование используется на различных шагах решения задачи для уточнения целей из графа планирования.

4. Для решателя разработана система поддержки планирования, которая предоставляет пользователю удобные средства для работы с РГЗ. Функции системы поддержки включают в себя построение чертежа решаемой задачи, выдачу объяснения найденного решения, визуализацию графа планирования и прослеживание изменений состояния задачи на чертеже в ходе планирования. Средства взаимодействия с пользователем у решателя уступают средствам системы.

TRIPS, реализующей общение на естественном языке, но при разработке РГЗ и не ставилось задачи достичь подобного уровня, а все внимание уделялось реализации методов планирования. Заметим, что построение планов системой TRIPS осуществляется во многом благодаря активному участию пользователя в решении задачи.

Работа состоит из четырех глав. В первой главе описана организация РГЗ, и показано, каким образом в системе решена проблема сочетания разных методов планирования при решении задачи. Вводится понятие управляющего стереотипаэлемента базы знаний, представляющего знания о методе планирования и позволяющего управлять ходом решения.

Вторая глава посвящена стратегиям планирования, применяемым в решателе. Даются описания каждой используемой стратегии, и обсуждаются вопросы их совместного применения при решении задач. Особое внимание уделено ассоциативному планированию. Вводится основное понятие ассоциативного планирования — близкая ситуация. Рассматривается применение близких ситуаций для построения уточнений планов.

Особенности реализации РГЗ обсуждаются в третьей главе. Детально рассмотрен алгоритм поиска близких ситуаций и строение сетевых структур, используемых при распознавании ситуаций. Приводятся критерии отбора близких ситуаций для получения эффективных планов. Также, в третьей главе приведено описание реализации программной среды поддержки планирования, являющейся составной частью решателя. Среда поддержки имеет в своем составе средства пользовательского интерфейса и систему объяснения решения. Особое внимание в системе уделено визуализации геометрических объектов решаемой задачи.

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

Гпава 1. Организация системы планирования решений сложных задач на основе стереотипов.

Решение сложных задач на ЭВМ, то есть таких задач, в которых пространство поиска решения велико, невозможно без использования в программе-решателе специальных знаний о предметной области. Знания являются неотъемлемой составляющей любой интеллектуальной системы. Эта составляющая либо явно выражена и представлена в базе знаний системы, либо неявно присутствует в нейронной сети или нейроподобной структуре (см. [Мтэку, 91]). Системы, простроенные на нейросетевых технологиях, пока еще не находят широкого применения в области планирования. Причиной тому, видимо, является специфика задачи планирования, которая состоит в том, чтобы для заданной цели составить последовательность из формально определенных действий или этапов плана. Нейронные сети лучше справляются с задачами распознавания образов и прогнозирования, при решении которых осуществляется вывод заключения из подаваемых на вход наблюдений. Учитывая специфику нейронных сетей, в дальнейшем изложении мы исключаем их из рассмотрения.

Знания хранятся в базе знаний в определенном представлении, от которого во многом зависит способ построения планов. Широко применяются следующие способы представления знаний: в виде правил (или продукций), в виде семантических сетей и фреймовое представление. Наиболее адекватным при решении многошаговых, многовариантных задач является фреймовый подход.

В 1975 году М. Минский ввел понятие фрейма для представления знаний. Фреймы стали широко использоваться в системах искусственного интеллекта, появились даже языки представления знаний, базирующиеся на фреймах: ГЛЬ, КЯЬ и другие. Главные атрибуты фреймовых структур, такие как наследование свойств, абстракции прототип — экземпляр (аналоги: класс — объект), специфическая «локализация» данных нашли позже свое воплощение в концепциях объектно-ориентированного программирования и при создании экспертных систем. Однако в полной мере фреймовый подход к построению систем решения сложных задач себя не исчерпал. Интересной представляется возможность использования фреймовых структур для представления не только объектов реального мира и их взаимосвязей, но и для формализации приемов и способов решения задач. Человек, решая сложную задачу, привлекает свой, а иногда и чужой, накопленный опыт. Пробует применить подходящие стереотипные решения: обнаруживая известную ситуацию, предпринимает те действия, которые у него с данной ситуацией ассоциируются. Такие действия приводят к появлению уже новых ситуаций, в которых можно применить другие известные стереотипные приемы решения. Процесс применения стереотипов повторяется и довольно быстро (в сравнении с полным перебором вариантов) приводит к нужному решению, либо к убеждению, что такого решения нет.

Идея планирования на основе стереотипов — конструкций для представления стереотипных решений была предложена и описана в работах [Корухова и Любимский, 94] и [Корухова и др., 94]. В основу рассматриваемого авторами интеллектуального решателя, положены принципы планирования, которыми обычно руководствуется человек, решая сложную задачу:

• многоуровневость планирования, рассмотрение нескольких альтернативных планов и сравнение их между собой в процессе решения;

• поиск не обязательно оптимального, но хорошего плана;

• однократное уточнение общих участков различных планов решения;

• не обязательно последовательный (слева направо) порядок уточнения подцелей. При рассматриваемом подходе построение плана осуществляется программойадминистратором с привлечением базы знаний. Администратору задается формулировка задачи, включающая цель (нахождение искомой величины или доказательство факта), а результатом его работы является план решения задачи, представляющий собой последовательность шагов по достижению поставленной цели. В процессе планирования администратор управляет выбором и применением стереотипов, хранящихся в базе знаний решателя. Основными частями описания стереотипа являются ситуация, определяющая условия, в которых стереотип применим, и действия, котсфые добавляются при применении стереотипа в создаваемый план. Действия стереотипа состоят либо в выводе новых фактов, либо в разбиении какой-либо цели на подцели. Стереотипы также имеют характеристики, на основании которых администратор осуществляет их отбор.

В ходе планирования решения производится с и.

•-О построение графа планирования решения (ГПР) и.

Условные обозначения: осуществляется вывод новых фактов из условий задачи (в ' • - уточненная цель зависимости от стратегии планирования). Узлы ГПР ^ неуТочненная цель соответствуют подцелям, а воображаемые дуги — Рис. 1.1 переходам от одной подцели к другой. Первоначально граф планирования имеет вид, представленный на рисунке 1.1, и цель и подлежит уточнению. Узел Б соответствует условиям задачи и считается уточненной целью. Цели в графе уточняются в результате применения стереотипов, при этом с уточняемой целью связывается одна или несколько цепочек подцелей. План считается завершенным, если в ГПР появляется путь из начальной вершины в концевую, состоящий из уточненных целей и элементарных целей, которым не требуется уточнение, или если в ходе вывода добавляется факт, соответствующий поставленной в задаче цели. Использование стереотипов при планировании удобно, по следующим причинам:

1) Посредством стереотипов реализуется как прямой логический вывод, так и обратный, при котором текущая цель уточняется цепочкой подцелей.

2) Потенциально существует возможность оформить в виде стереотипов некоторые этапы работы администратора (такие как выбор текущей уточняемой цели в ГПР или выбор лучших стереотипов для уточнения цели), что позволяет реализовывать различные стратегии, не изменяя алгоритма администратора.

Выдвинутые в [Корухова и др., 94] идеи развиваются в данной диссертационной работе. Автор использует подход к планированию на основе стереотипов для реализации решателя геометрических задач и существенно расширяет его, вводя стереотипы для организации процесса планирования.

Основные результаты диссертационной работы состоят в следующем:

1. Предложен новый метод планирования решений — ассоциативное планирование на основе «близких» (частично распознанных) ситуаций, рассчитанный на совместное использование с традиционными дедуктивными методами. При реализации метода разработан эффективный алгоритм поиска близких ситуаций. Сочетание предложенного метода с дедуктивными методами планирования позволяет в ряде случаев построить более эффективное решение задачи.

2. Для систем планирования решений разработан новый способ представления знаний об управлении планированием в виде управляющих стереотипов. Такой способ представления дает возможность сочетать в ходе решения задачи различные стратегии поиска решения. Использование в планирующей системе управляющих стереотипов делает ее открытой для добавления новых стратегий планирования.

3. Реализована новая версия экспериментального решателя геометрических задач, на работе которой продемонстрировано автоматическое решение задач при гибком сочетании ассоциативных и дедуктивных методов в ходе планирования на основе управляющих стереотипов.

Заключение

.