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

?ГБ ОД

Московский Государственный Университет

О ' . . . г

имени М.В.Ломоносова с с ¡\

факультет Вычислительной Математики и Кибернетики

На правах рукописи УДК 519.95

Малышко Виктор Васильевич

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

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов, систем и сетей

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2000

Работа выполнена на кафедре Системного программирования факультета Вычислительной Математики и Кибернетики МГУ им. М.В. Ломоносова.

Научный руководитель:

доктор физико-математических наук,

профессор

Любимский Эдуард Зиновьевич

Официальные оппоненты:

доктор физико-математических наук,

профессор

кандидат физико-математических наук, старший научный сотрудник

Томилин Александр Николаевич

Бухштаб Юрий Александрович

Ведущая организация - Российский научно-исследовательский институт информационных технологий и автоматизированного проектирования Министерства Науки РФ.

Защита диссертации состоится 19 мая 2000 г. в 11 часов на заседании диссертационного совета Д 053.05.38 при факультете ВМиК МГУ по адресу: 119899, Москва, Воробьевы Горы, МГУ, ф-т ВМиК, ауд.685.

С диссертацией можно ознакомиться в библиотеке факультета ВМиК МГУ.

Автореферат разослан АЦ апреля 2000 г.

Ученый секретарь диссертационного совета кандидат физико-математических наук, профессор

Трифонов Н.П.

Общая характеристика работы

ктуальность темы

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

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

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

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

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

Тема данной работы связана с первым и третьим направлениями исследований из указанного списка.

Цель диссертационной работы

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

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

3) Экспериментальная реализация системы планирования - решателя геометрических задач (РГЗ) - на основе разрабатываемых методов и средств.

Научная новизна

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

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

рактическая ценность работы

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

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

пробация работы

Работа была представлена на заседании объединенного научно-сследовательского семинара кафедр Автоматизации систем вычислительных омплексов, Алгоритмических языков и Системного программирования 6 октября 999 г.

'труктура и объем диссертации

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

публикации

По теме диссертации опубликовано три печатные работы.

Краткое содержание работы

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

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

1 Корухова Л.С., Любимский Э.З. О процедурности и непроцедурное™ в задачах планирования целенаправленной деятельности. - М. Известия Академии Наук. Серия: «Техническая кибернетика», № 5, стр. 72-78, 1994.

Корухова Л.С., Любимский Э.З., Островский В.В. Программирование на основе стереотипов. - М. Препринт Института Прикладной Математики РАН, № 18, 1994.

Стереотипы также имеют характеристики, на основании которых администратор существляет их отбор.

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

ходе вывода фактов добавляется факт, соответствующий поставленной в задаче (ели.

В процессе решения задачи можно выделить следующие этапы: ввод условий адачи; применение методов шшшрования на различных шагах решения задачи в (икле, до момента достижения поставленной цели или возникновения тупика в «тении; выдача объяснения полученного решения. На каждом шаге решения юуществляется выбор одного из используемых в РГЗ методов планирования. При фименешш конкретного метода принимается решение о том, какой именно из пособов действий применять (каким из реализовашшх способов выбирать текущую (ель на ГПР, подлежащую уточнению, на основании какого критерия отбирать тереотипы для уточнения текущей цели или вывода новых фактов и т.д.). В этом ¡ыборе и заключается управление планированием, в зависимости от сделанного 1ыбора решение задачи пойдет тем или иным путем. Каждая из реализаций выше 'помянутых действий (выбор метода планирования, выбор текущей цели и т.д.) гредставляет собой фрагмент кода программы решателя, в достаточной степени гезависимый от остальной программы, то есть модуль, точнее, управляющий юдуль. Жесткая фиксация набора модулей и порядка их запуска приводит к тому, 1то при внесении изменений в управление планированием и добавлении новых методов планирования в решатель приходится изменять администратор РГЗ. Более ибкая организация управления решением должна предусматривать выбор управляющего модуля, которому будет передано управление. Предлагается 1роизводить этот выбор на основе стереотипов - при выполнении определенных

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

Управляющий стереотип (УС) представляет собой именованный элемент базы знаний, который на основе ситуации, сложившейся в ходе решения задачи, предписывает выполнить описанные в нем действия. Действия УС представляют собой последовательность операторов вызова управляющих модулей или операторов записи в дневник планирования. УС отличаются от стереотипов, используемых для уточнения целей ГОР и вывода новых фактов. Эти стереотипы называются функциональными стереотипами (ФС). Разница между управляющими и функциональными стереотипами состоит в том, что УС - это знания из области управления планированием, а ФС - знания о способах решения геометрических задач (предметной области).

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

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

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

На основании данных из дневника планирования производится распознавание туаций для управляющих стереотипов. Метод распознавания ситуаций УС »снован на использовании присоединенных процедур «если_добавлен», ;если_удален». Процедуры связаны с каждым слотом дневника и запускаются :аждый раз при записи значения в слот или удалении его из слота. Присоединенная гроцедура для слота дневника, на значение которого наложены условия в описании акой-либо ситуации, создается автоматически при компиляции описаний ситуаций оправляющих стереотипов перед запуском решателя. Действие процедуры состоит в ом, чтобы определить, какие изменения во множестве распознанных ситуащш фоизойдут при изменешш значения слота дневника. Производится добавление говых ситуаций к множеству распознанных или удаление из него ситуаций, условия :оторых нарушены. Данный метод достаточно эффективен, поскольку при вменении значения слота анализируются только непосредственно связанные с ним ¡итуации, что позволяет избежать полного перебора. В методе существенно 1спользуется то, что для распознавания ситуаций не требуется проверять свойства рупп объектов.

Алгоритм администратора решателя, который использует управляющие :тереотипы, состоит из следующих шагов: ;) начало сеанса работы;

1) распознавание ситуащш управляющих стереотипов на основании анализа

значений слотов дневника планирования; I) если есть распознанные ситуации, то выполняется разрешение конфликта (выбор

одного УС из нескольких применимых), иначе переход на шаг 6; I) выполнение действий выбранного УС;

>) если не установлен флаг окончания сеанса, то переход на шаг 2; >) освобождение ресурсов и окончание сеанса.

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

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

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

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

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

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

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

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

Критерии отбора перспективных близких ситуаций следующие:

1) условие «полезности»;

2) условие «доступности»;

3) комбинированный критерий.

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

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

Комбинированный критерий позволяет совместно оценить «полезность» и «доступность» близкой ситуации. При отборе близкой ситуации по данному критерию осуществляется проверка: лежит ли значение функции взвешивания для данной ситуации в априорно заданных пределах. Функция взвешивания представляет собой функцию от двух переменных - трудности ФС, связанного с ситуацией, и трудности цепочки целей для вывода недостающих фактов. С помощью комбинированного критерия исключаются из рассмотрения близкие ситуации, для которых значения обеих характеристик близки к предельным. В настоящее время в РГЗ используется следующая функция взвешивания: f(x, у) = х + у (где х - трудность ФС, а у - трудность цепочки целей).

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

Вставка ассоциативного уточнения в граф планирования не может привести к окончанию решения, так как: на всяком появившемся новом пути в графе будут

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

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

Заканчивается рассмотрение ассоциативного планирования, описанием алгоритма действий одного шага этого метода:

1. Среди неуточненных и недостигнутых целей в ГПР выбирается текущая цель для уточнения.

2. Формируется контекст текущей цели.

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

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

5. По набору стереотипов, отобранных ранее на шаге 3, строится ассоциативное уточнение текущей цели. Уточнение заносится в ГПР.

6. Осуществляется переход на следующий шаг планирования.

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

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

Особенности реализации РГЗ обсуждаются в третьей главе. Детально рассмотрен алгоритм поиска близких ситуаций и строение сетевых структур, используемых при распознавании ситуаций. Обычные алгоритмы сопоставления с образцом, такие как Rete-алгоритм2, используемый в продукционной системе ÓPS5 и Treat-алгоритм3, предложенный для различных продукционных систем, неприменимы для поиска близких ситуаций, поскольку предназначены для нахождения только полностью распознанных ситуаций. Для решателя был разработан алгоритм поиска близких ситуаций, подробное изложение которого содержится в пара1рафе 3.1 диссертации. Входными данными алгоритма являются факты из базы задачи решателя. Результатом его работы является список четверок вида: (имя функционального стереотипа, близкая ситуация, строка сопоставления, набор недостающих фактов).

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

: Forgy C.L. RETE: A fast algorithm for the many pattern / many object pattern match jroblem. - Artificial Intelligence, Vol. 19, pp. 17-37, 1982.

Miranker DP., Lofaso B.J. The organization and performance of a TREAT-based production system compiler. - The IEEE Transactions on Knowledge and Data Engineering. Vol. 3, No. 1, pp. 3-9, March 1991.

слотов объектов) подаются на вход сопоставителя ситуаций ФС. Его задачей является определение изменений во множестве распознанных ситуаций, вызванных поступившими фактами. Во избежание неэффективного рассмотрения всех ситуаций, они организуются в сеть - разновидность классификационной сети (сеть строится перед сеансом работы решателя). В узлах сети происходит обработка поступивших фактов, во время которой проверяются условия из описания ситуаций. В зависимости от результата проверок факты задерживаются в узлах или передаются дальше по сети. Если в результате обработки какие-либо факты оказываются в концевых узлах сети, это означает, что распознаны ситуации, связанные с данными концевыми узлами.

Для поиска близких ситуаций сопоставитель решателя в том виде, котором он описан выше, не пригоден. Означивающие наборы фактов для близких ситуаций будут остановлены в промежуточных узлах сети, поскольку по определению часть условий близких ситуаций не выполнена. Тем не менее, при интерпретации сети решателя в памяти узлов запоминаются данные, которые могут оказаться полезными при поиске близких ситуаций. Для этого при генерации каждого фрагмента 11е1е-сети, соответствующего некоторой ситуации ФС, узлы осуществляющие проверки фактов, вывод которых невозможен при работе решателя, расположены выше узлов проверяющих условия, которые можно удовлетворить выводом новых фактов (см. Рис. 1). Во время работы сопоставителя ситуаций на выход верхней части И^е-сети попадают все строки сопоставления для рассматриваемой ситуации, возможные

Рис. 1. Схема расположения узлов в Н.е1е-сети решателя.

текущем состоянии базы задачи. Они запоминаются в памяти специального апоминающего узла, чтобы затем быть использованными при поиске близких итуаций. Это полные строки сопоставления, поскольку узлов, в которых фоисходит означивание в нижней части 11е1е-сети нет. Некоторые из этих строк [роходят до конца нижнюю часть сети и попадают в терминальный узел - они оответствуют распознанным ситуациям. Эти строки запоминаются в памяти ■ерминального узла и в дальнейшем выдаются в ответ на запросы к сопоставителю итуаций. -Остальные строки сопоставления соответствуют близким ситуациям, юскольку для каждой из них в ситуации не выполнены только те условия, которые южно удовлетворить добавлением новых фактов (условия на значения слотов |бъекгов и проблемные отношения). То есть, каждая из строк соответствует [еполному означивающему набору фактов, который можно достроить. Остается шределить недостающие факты, чтобы можно было применить найденную близкую итуацию при планировании.

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

В диссертации предложен следующий алгоритм для поиска близких ситуаций:

1) Выбрать функциональный стереотип из базы стереотипов.

2) Если тип уточняемой ФС цели совпадает с типом текущей цели, то запомнить частичную строку сопоставления объектов из описания уточняемой стереотипом цели с объектами из текущей цели, иначе перейти к выбору другого стереотипа.

3) Для связанной со стереотипом ситуации найти запоминающий и терминальный узлы 11еТе-сети решателя.

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

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

6) Если есть еще нерассмотренные строки сопоставления в памяти запоминающего узла, то перейти на шаг 4.

7) Если в базе стереотипов остались нерассмотренные функциональные стереотипы, то перейти на шаг 1.

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

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

рагментов графа планирования и прослеживанием изменения состояния задачи на ;ртеже в ходе планирования.

В четвертой главе разбираются примеры решения задач, которые демонстрируют тместное применение разных методов планирования решений. На примерах ^демонстрировало, что совместное использование различных методов решения эзволяет повышать эффективность поиска решений некоторых задач. Для одной из осматриваемых задач эффективное решение найдено с использованием стратегии геместного применения ассоциативного планирования и обратной цепочки осуждений. Использование комбинированной стратегии, при которой поочередно эименяются прямая и обратная цепочка рассуждений, позволяет получать решения дач с меньшим числом липших выведенных фактов, чем при использовании )лько прямой цепочки рассуждений. Для разных задач этот эффект проявляется по-оному, и можно привести примеры задач, для которых при прямой цепочке осуждений не будет выведено лишних фактов. Тем не менее, реализация в мпателе различных методов планирования и средств, позволяющих сочетать и ш.честно использовать различные методы, дает значительные преимущества по ¡авнению с системами, ориентированными на использование единственного метода мления задач.

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

Основные результаты работы

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

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

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

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

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

.. В.В. Вакин, Л.С. Корухова, Э.З. .Любимский, В.В. Малышко. Ассоциативные 1етоды 1шанирования решений сложных задач. - М. Препринт Института [рикладной математики им. М.В. Келдыша РАН, № 81, 1997 г. :. Л.С.Корухова, Э.З.Любимский, Л.В. Максимов, В.В. Малышко. Программные редства поддержки немонотонного шшшрования. - М. Препринт Института ¡рикладной математики им. М.В. Келдыша РАН, № 75, 1998 г. . Л.С. Корухова, Э.З. Любимский, В.В. Малышко. Реализация стратегий шанирования на основе управляющих стереотипов. - М. Препринт Института грикладиой математики им. М.В. Келдыша РАН, № 13, 2000 г.

ВВЕДЕНИЕ.

ГЛАВА 1. ОРГАНИЗАЦИЯ СИСТЕМЫ ПЛАНИРОВАНИЯ РЕШЕНИЙ СЛОЖНЫХ ЗАДАЧ НА ОСНОВЕ СТЕРЕОТИПОВ.

1.1. Структура базы знаний решателя.

1.2. Понятие управляющего стереотипа.

1.3. Дневник планирования.

1.4. Алгоритм администратора решателя.

1.5. виды управляющих стереотипов.

ГЛАВА 2. СТРАТЕГИИ ПЛАНИРОВАНИЯ РЕШЕНИЙ ЗАДАЧ.

2.1. Метод обратной цепочки рассуждений.

2.2. Метод прямой цепочки рассуждений.

2.3. Ассоциативное планирование,.

2.3.1. Близкая ситуация. Определение

2.3.2. Использование близких ситуаций при планировании.

2.3.3. Способы отбора близких ситуаций для получения эффективного плана.

2.3.4. Построение уточнения плана на основе близких ситуаций.

2.4. Стратегии с применением различных методов.

ГЛАВА 3. РЕАЛИЗАЦИЯ РЕШАТЕЛЯ ГЕОМЕТРИЧЕСКИХ ЗАДАЧ.

3.1. Алгоритм поиска близких ситуаций.

3.1.1. Механизм распознавания ситуаций функциональных стереотипов.

3.1.2. Структура используемой в решателе Ые1е-сети.

3.1.3. Использование И^е-сети при поиске близких ситуаций.

3.2. Система объяснения решения.

ГЛАВА 4. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ.

Планирование в сложных проблемных областях всегда рассматривалось как род интеллектуальной деятельности. Интерес специалистов по искусственному интеллекту (ИИ) к автоматизации планирования возник чуть ли не одновременно с формированием ИИ как направления научных исследований. В начале 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 представляет собой набор взаимодействующих интеллектуальных агентов, каждый из которых является либо постановщиком задач, либо планировщиком, либо исполнителем планов. В роли агентов могут выступать как программы, так и люди. Разработанная структура программного агента включает в себя следующие компоненты:

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

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

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

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

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

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

В рамках проекта 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. Реализована новая версия экспериментального решателя геометрических задач, на работе которой продемонстрировано автоматическое решение задач при гибком сочетании ассоциативных и дедуктивных методов в ходе планирования на основе управляющих стереотипов.

Заключение

1. Корухова и др., 94. Корухова JI.C., Любимский Э.З., Островский В.В. Программирование на основе стереотипов. М. Препринт Института Прикладной Математики РАН, № 18, 1994.

2. Осута и Саэки, 90. Приобретение знаний. Под редакцией Осуги С., Саэки Ю./ Перевод с японского. М. Мир, 1990.

3. Попов,87. Попов Э.В. Экспертные системы. Решение неформализованных задач в диалоге с ЭВМ М.: Наука, 1987

4. Ambite and Knoblock, 97. Ambite J.L. and Knoblock C.A. Planning by Rewriting: Efficiently Generating High-Quality Plans. Proceedings of the 14th National Conference on Artificial Intelligence (AAAI-97). AAAI-Press. 1997

5. Aylett et al., 98. Aylett R.S., Soutter J., Petley G., Chung P.W.H., Rushton A. AI Planning in a Chemical Plant Domain. Proceedings of the 13th Biennial European Conference on Artificial Intelligence (ECAI-98). 1998.

6. Ferguson et al., 98. Ferguson G., Allen J. F. TRIPS: An Integrated Intelligent ProblemSolving Assistant. Proceedings of the 15th National Conference on Artificial Intelligence (AAAI-98). Wisconsin. 1998.

7. Forgy, 82. Forgy C.L. RETE: A fast algorithm for the many pattern / many object pattern match problem. Artificial Intelligence, Vol. 19, pp. 17-37, 1982.

8. Gil and Melz, 96. Gil Y., Melz E. Explicit Representation of Problem-Solving StrategiestVito Support Knowledge Acquisition. Proceedings of the 13 National Conference on Artificial Intelligence (AAAI-96). 1996.

9. Haraguchi and Arikawa, 86. Haraguchi M., Arikawa S. A Foundation of Reasoning by Analogy. Analogical Union of Logic Programs. Proceedings of the Logic Programming Conference. Tokyo, pp. 103-110. 1986

10. Koehler, 98. Koehler J. Solving Complex Planning Tasks through Extraction of Subproblems. Proceedings of the 4th International Conference on Artificial Intelligence Planning Systems (AIPS-98). 1998

11. Kushmerick et al., 94. Kushmerick N., Hanks S., Weld D. S. An Algorithm for Probabilistic Least-Commitment Planning. Proceedings of the 11th National Conference on Artificial Intelligence (AAAI-94). 1994.

12. Melis and Whittle, 97. Melis E., Whittle J. External Analogy in Inductive Theorem Proving. Proceedings of the 21st German Annual Conference on Artificial Intelligence (KI-97). Albert-Ludwigs University. 1997.

13. Miranker and Lofaso, 91. Miranker D.P., Lofaso B.J. The organization and performance of a TREAT-based production system compiler. The IEEE Transactions on Knowledge and Data Engineering. Vol. 3, No. 1, pp. 3-9 March 1991.

14. Newell et al., 59. Newell A., Shaw I.C., Simon H.A. Report on a General ProblemSolving Program. Proceedings of the International Conference on Information Processing, UNESCO, Paris, 1959, pp.256-264.

15. Sacerdoti, 77. Sacerdoti E.D. A structure for plans and behavior. New York. American Elsevier. 1977.

16. Tate, 96. Tate A. Representing Plans as a Set of Constraints the <I-N-OVA> Model. -Proceedings of the 3rd International Conference on Artificial Intelligence Planning Systems (AIPS-96). 1996.

17. Tate, 97. Tate A. Multi-agent Planning via Mutually Constraining the Space of Behaviour. AAAI-97 Spring Symposium on Mixed Initiative Interaction, Stanford University, 1997.