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

На правах рукописи

ГАБДРАХМАНОВ Ильшат Накипович

ПЛАНИРОВАНИЕ ЗАДАЧ В СЛОЖНОСТРУКТУРИРОВАННЫХ СИТУАЦИЯХ

Специальность 05.13.01 — Системный анализ, управление и обработка информации (в машиностроении и вычислительной технике)

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

Ижевск 2006

Работа выполнена на кафедре Автоматизированные системы обработки информации и управления ГОУ ВПО «Ижевский государственный технический университет».

Научный руководитель: д.т.п., профессор

Кучугаиов Валерии Никапорович

Официальные оппоненты: доктор физико-математических наук, профессор

Бельтюков Анатолий Петрович

кандидат технических паук Милич Владимир Николаевич

Ведущая организации: Институт коиструкторско-техпологическои

информатики РАН . г. Москва

Защита состоится «б» июля 200С г. в 14 часон па заседании диссертационного совета К '212.065.01 при ГОУ ВПО «Ижевский государственны¡1 технический университет» по адресу: 420000, г. Ижевск, ул. Студенческая, 7.

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

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Ижевский государственный технический университет».

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

Ученый секретарь диссертационного совета к.т.п., доцент

Сяктерев В.Н.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

Значительный вклад в развитие теоретических исследований и практических разработок в сфере интеллектуального планирования внесли как зарубежные исследователи: Fikes R.O. (США), Ghallab М.(Франция), Kambhampati S. (США), Kautz Н. (США), McAllester D.A. (США), Nau D.S. (США), Nilsson N.J. (США), Rosenblit D. (США), Sacenloti E.D. (США), Tate А. (Великобритания), Traverso Р. (Италия). Weld D.S. (США), Wilkins D.E. (США), так и отечественные ученые: Аверкнн А.Н., Поспелов Д.А., Осипов Г.С., Стефашок В.Л., Ефимов Е.И., Алиев P.A., Кузин Е.С.

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

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

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

В процессе планирования необходимо анализировать информацию о предметной области с различных точек зрения. Одним из способов сокращения объемов работ по описанию предметных областей является структурирование информации. Как

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

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

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

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

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

Среди основных задач работы следует выделить:

1) анализ существующих методов и систем интеллектуального планирования задач;

2) разработка моделей предметной области и проблемной ситуации планирования задач;

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

4) разработка алгоритмов и программной системы планирования задач;

5) экспериментальное исследование разработанной системы планирования задач.

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

На защиту выносятся:

1) модель предметной области планирования;

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

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

4) алгоритм иерархического планирования задач;

5) разработанная универсальная планирующая система Г{еВНР;

С) система управления базами знаний КС:

7) система автоматизированного проектирования технологических процессов свободной ковки поковок па прессах;

8) спроектированная система автоматизированного планирования маркетинговых исследований;

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

Научная новизна полученных результатов заключается в:

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

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

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

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

Реализация результатов работы. Результаты работы используются в «Инженерно-технологическом центре «Кузнец»» при научно-исследовательском институте металлургической технологии для проектирования технологических карт процессов свободной ковки поковок па прессах, в ФГУП «Ижевский механический завод» для проектирования схем электронного документооборота и в Ижевском государственном техническом университете для обучения студентов специальностей «Системы автоматизированного проектирования» и «Автоматизированные системы обработки информации и управления» при изучении дисциплин «Системы искусственного интеллекта» и «Информационные технологии», а также в дипломном проектирова-

нии.

Апробация работы. Основные научные результаты, полученные в диссертационной работе, докладывались и обсуждались па: 3-ей международной научно-технической конференции «Информационные технология в инновационных проектах» (Ижевск, 2001): международной научно-технической конференции, посвященной 50-летию ИжГТУ (Ижевск, 2002); международной научно-технической конференции «Интеллектуальные системы» (Геленджик, 2004): па научно-техническом форуме с международным участием «Высокие технологии - 2004»(Ижевск, 2004): на 7-ой всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2004); па семинаре «Теоретические основы и приложения информатики» кафедры «Математическое обеспечение ЭВМ» Удмуртского государственного университета.

Публикации. Результаты работы отражены в 8 печатных работах.

Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 153 наименования, и четырёх приложений. Основная часть работы изложена па 151 странице машинописного текста, содержит 43 рисунка, 2 таблицы. Приложения содержат акты о внедрении, описание предметных областей и проблемных ситуаций планирования, использованных I! экспериментальных исследованиях, и описание грамматики расширения языка РВГ)Ь 3.0, использующего декомпозиционные шаблоны в описании методов решения задач.

Автор выражает спою благодарность к.т.н., доценту кафедры «МиТОМ Д» Ижевского государственного технического университета Морозову С.А. за помощь в проведении экспериментальных исследований предложенного метода на примерах синтеза технологических процессов свободной ковки поковок на прессах.

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

декомпозиций задач.

Функция планирования интеллектуальной системы предназначена для создания планов решения Plans всех возможных ПС Situations па основе описаний ПО планирования Domains:

planning : Domains х Situations —> Flans. Описание ПО планирования domain € Domains определяется как:

domain [пате. Tanks, hfethods, Concepts, Attributes(,/„„), где пате - наименование ПО; Tasks - множество всех задач ПО; Methods - множество методов решения сложных задач; Concepts - множество концептов ПО;

Attributes^,, - множество описаний атрибутов синтезируемых планов. Множество задач ПО domain можно представит!» в виде множеств простых и сложных задач Tasks = SimpleTasks U CmnplexTasks. Описание простых и сложных задач образуют пространство задач.

Простая задача t 6 SimpleTasks представляет собой действие, которое может

выполнить агепт(ы):

t = (пате, premnd, effect, Attributes, Agents),

где пате - наименование задачи;

precond - бескванторная формула логики предикатов первого порядка, описывающая условия применимости задачи;

effect. - бескванторная формула логики предикатов первою порядка, описывающая эффект задачи;

Attributes - множество атрибутов, описывающих задачу (параметры задачи являются подмножеством данного множества); Agents - типы агентов, способных выполнить задачу.

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

Множество методов Methods в описании ПО domain содержит различные способы решения сложных задач (СЗ). СЗ могут иметь несколько методов решения, которые могут быть применены в различных условиях и давать различные результаты после их исполнения.

Метод описывает решение одной из СЗ:

met.hnd = (t.ask, precoridition, décomposition, Attributes), где t.ask G ComplexTasks - задача, решение которой описывается данным методом; precondilion - предусловие метода, заданное в виде бескванторной формулы логики предикатов первого порядка;

décomposition - шаблон, описывающий множество декомпозиций задачи (ДЗ):

Attributes - множество описаний атрибутов метода, включающее описание параметров задачи.

Для сокращения описаний ДЗ предлагается использовать декомпозиционные шаблоны (ДШ):

Decompositions = {(q, о)}, где q е Quantifiers = {", '+', V, '?', (т,п), '+?', '*?', '??', (m,n,'?')> 'I?', '[]'• '+!', '*!', '?!', (ш,«,'!'), Т. '+?!', '*?!', '??!', (т,я,'?!'), '|?!'> '[]П " квантор ДШ; о € (Decompositions и Tasks)* - последовательность задач (ПЗ); Множество декомпозиций, порожденных ДШ (д, о), определяется функцией:

/((?,о)) =

о,

и W'.

i=l

0U и {о}' , {0, О),

UW,

{(>1,02,. ■ . ^Jj-i-Oj},

UM\ и {о}' U0,

О, 0},

m

UW.

?=п

{о./,0;-Ь . . • , Oo.Oi},

если <7 = ,

если д е {'+', '+!'},

если ? е {'*', '*!'},

если (? е {'?', '?!'},

если <7 е {(т, п), (т, п, '!')},

если ц е {'Г, '|!'} и

О = ("1,02.....<?>-1,Оу),

если д 6 {'+?', '+?!'},

если <j е {'*?', '*!?'},

если <? 6 {"??', '??!'}.

если qe {(т, н, '?'), (т, п, '?!')},

если q е {'!?', '|?!'} и

о = {Ol,02,..-,0j-l,0j),

oj-uOjY, если 7 € {'[]', '!]!'} и

О = [01,02----

где к - максимально возможное количество повторении ПЗ о;

X' - г'-ая степень расширенного декартового произведения отношения X; 2 - арность отнотпення о.

В описании ДЗ можно выделить следующие структурные элементы, которые можно реализовать с помощью ДШ:

1. ПЗ д, которая может встречаться в ДЗ ¿о более одного раза, обычно описываются следующим способом. В описание ПО вводят некоторую новую СЗ!.'. которая будет иметь две декомпозиции. Первый метод т\ будет осуществлять ДЗ I' на ПЗ д.

Второй метод тп'2 будет иметь рекуррентное определение задачи i', обеспечивающее

неоднократное включение ПЗ д в ДЗ t'. Фрагмент И-ИЛИ графа, описывающего

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

описание, строит дерево решения (ДР), представленное па рис. 2.

Если ПЗ д длиной к может быть продублирована всего гг раз, то

(kin + 1) , \ , , г,

nl ^ ^— 1 ") 1 ^ Для

<к.(п + 1)

количество вершин ДР будет равным п ^ + 1)

+

Рис. 1. Фрагмент П-ПЛП графа для попторяющсГюя ПЗ

синтеза и обхода этого ДР требуется п('2к + 3) 4+2 шагов алгоритма.

Дублирование ПЗ д можно добиться с помощью ДШ: ('+', д). {'+!',<?), ('+?',<?) и ('+?!', д). ДР, построенное с помощью ДШ C+'itf) и ('+!'.</)> представлено па рис. 3, а для ДШ ('+?',</) и (' I ?!',.</) - па рис. 4. Если ПЗ д длиной к может быть продублирована максимально п рал, то количество вершин ДР, представленных па рис. 3 и 4. будет равным: n(*íü+ü + i)+i.

Для описаний, использующих ДШ, требуется синтез ДР с меньшим па п(п — 1) количеством вершин. Для обхода ДР, построенных с использованием ДШ ('+', д) и ('+?'■.7), потребуется к(п + 1) + Ц^ +п + 3 шагов алгоритма планирования, что на (п — 1)(л + к) + '¿п — 1 шагов меньше, чем для обхода ДР, представленного па рис. 2.

Если при использовании ДШ ('+!',.7) первый найденный полный план решения ПС будет содержать h повторений ПЗ д и ПЗ 9 могла выполниться максимально п раз, то алгоритм выполнит к{п + 1)^1 + + 2 — ^ ^ + l) шагов

для обхода ДР.

Если при использовании ДШ ('+?!',<?) первый найденный полный план решения ПС будет содержат!, h повторений ПЗ д, то алгоритм выполнит k{h +1) + шагов для обхода ДР.

J

s 4

Í 4 j l¡ty

У7\ oo ♦

áó

4\

I

4

Рис. 2. ДР для попторяющойгя ПЗ

Рис. 3. ДР для ДШ (' +'.ц) и ('+!'.(/)

Рис. 4. ДР для ДШ С+Г.у) м ('+'.■!',д)

2. ПЗ д, которая может встречаться в ДЗ несколько раз или пи разу, в существующих системах иерархического планирования описывают следующим способом. В описание ПО планирования вводят СЗ /.', которая будет иметь два метода регпе-

Рис. 5. Фрагмент II-ПЛП графа для отсутствующей или

ния. Первый метод т\ редуцирует задачу L' па пустую ПЗ. Описание второго метода т'2 полпостыо совпадает с предыдущим случаем. Фрагмент И-ИЛИ графа, описывающего данную ситуацию представлен па рис. 5. Планирующая система, используя такое описание, строит ДР, представленное на рис. G. Если ПЗ д длиной к может быть продублирована всего п раз, то количество вершин ДР будет равным 1) ^ j для синтеза и обхода этого ДР потребуется (nf 1) + п + к + +'2 шагов алгоритма.

Игнорирование или дублирование ПЗ д можно добиться с помощью ДШ: ('С*!',.'?), ('*?', <7) " ('*?!',<;). ДР, построен- повторяющейся ПЗ ное с помощыо ДШ ('*', <?) " ('*!',(/), представлено па рис. 7, а для ДШ ('*?',д) и ('*?!', д) - па рисунке 8. Если ПЗ д длиной к может быть продублирована максимально п раз, то количество вершин ДР, представленных па рис. 7 и 8. будет равным: + +

Таким образом, для описаний, использующих ДШ, требуется синтез ДР с меньшим на n(n + 1) количеством вершин. Для обхода ДР, построенных с использованием ДШ С*',д) и ('*?',д), потребуется (n I I А: I l) I 3 шагов

алгоритма планирования, что на n(n + 1) — 1 шагов меньше, чем для обхода ДР, представленного па рис. G.

Если при использовании ДШ ('*!', д) первый найденный полный план решения ПС будет содержат!, h повторений ПЗ д и ПЗ д могла выполниться максимально п раз, то алгоритм выполнит (п + 1)^4? + к + +2 — ^ _

(/¡4- 1) шагов для обхода ДР.

Если при использовании ДШ ('*?!',</) первый найденный полный план решения ПС будет содержат!, h повторений ПЗ д, то алгоритм выполнит (/í + 1 )(Jy~ + к + 1^+3 шагов для обхода ДР.

Рис. G. ДР ДЛЯ отсутствующей или повторяющейся ПЗ

сгсгб

Рис. 7. ДР для ДШ С*',;/) и ('*!',я) Рис. 8. ДР для ДШ ('*?',<;) п (''*?!',.д)

3. Для описания ПЗ д, которая может встречаться в ДЗ £<) от т до п раз, в иерархических планирующих системах используют следующую схему. В описание

ПО вводят новую СЗ t', которая будет иметь единственный метод решения то'. Декомпозиция метода т' будет содержать новые задами t\ и t". СЗ t" будет редуцироваться с помощью методов т" и то'". Декомпозиция метода го" будет содержат1> ПЗ д, дополпи-тел1>ио простую задачу t'2 и задачу t". Для реализации фиксированного числа повторений ПЗ д необходимо реализовать счетчик munter, который хранится в текущей ПС планировщика. Инициализацию счетчика осуществляет задача t[. За увеличение счетчика будет отвечать задача t'2, а за контроль числа повторений предусловие метода го'". Предусловие метода гп" должно контролировать выражение (counter < т) (counter < п). Предусловие метода т'" должно содержать проверку условия counter > н. Фрагмент И-ИЛИ графа для этого случая представлен на рис. 9. Планирующая система, используя такое описание, строит ДР, представленное па рис. 10. Если ПЗ д состоит из к задач, то количество вершин ДР будет равным Згс + для снптеза и обхода этого ДР потребуется С(п + 1)(к(п + 2) + 3 п + 1G)\

I—-——1--rj-1-- I +5 шагов алгоритма.

Повторение ПЗ д от т до п раз в декомпозиции можно добиться с помощью ДШ: ((го, п), д), ((гп, п,'!'). д), ((т,п,'?'), д) и ((го, п' ?!'), д). ДР, построенное с помощью ДШ ((т. J?

и ((го, п/!'), д), представлено на рис. 11, а для ДШ ((т. п,' ?'), ^ д) и ({т, п,' ?!'),</) - па рис. 12. Если ПЗ д состоит из к задач * Ь<5.6

, то количество вершин ДР, представленных па рисунках 11

,„ , ((п - т + 1 )(кп + km + 2)\ , . •

и 12, будет равным: -- / W

Следовательно, для описаний, использующих данные ДШ,

Рис. 9. Фряг-MOirT И-ИЛП графа для ПЗ с фиксиропанпьш числом повторений

требуется синтез ДР с меньшим па

+2'

+

т — km колнмеством вершин. Для обхода ДР, постро-

Зп + 9 п + С + кпг 2 ■

о •

Рис. 10. ДР для ПЗ с

епных с использованием ДШ ((т, п),д) и ((т, п,' ?').$), по- фиксированным числом

, f(n - т. + 1)(кп + km + 2)\ , . „

требуется ---1 +к(п + т)+3 i

nOBTOpOIfHII

Зп

2 I km2

17п I 2т - km I 2кп I- 2к f 22

алгоритма планирования, что па —•—■ - ---—.—->-^

гов меньше, чем для обхода ДР, представленного па рис. 10.

Если при использовании ДШ((т, п.' У),д) первый найденный полный план решения ПС будет содержать /1 повторений ПЗ д и ПЗ д могла выполниться максимально

(п -т + 1 )(кп + кт + 2) - (/г - то + 1 )Шг + кт + 2) п раз, то алгоритм выполнит--—- ^ -—--

+ к(п + т) + 2 шагов для обхода ДР.

+

Рис. 11. ДР для ДШ {(m,n),;j) и ((»Ц «,'!'),!/)

Рис. 12. ДРдля ДШ ((ш,и/Г), у) и (('т.п.'Г!'),.у)

Если при использовании ДШ ('*?!',</) первый найденный полный план решения

ПС будет содержать h повторений ПЗ (/, то алгоритм выполнит k(h +п?) +3+

, /(h - т + 1 )(/.:/? + ктп + 2)\ по

I I ^---J шагов для обхода ДР.

•1. Для описания ПЗ д. которая является необязательной в ДЗ поступают следующим образом. Вводят новую задачу t', которую включают в ДЗ £(). Для задачи í' создаются два метода решения. Первый метод содержит ПЗ д, а в декомпозиции второго метода содержит пустую ПЗ. И-ИЛИ граф для данного случая представлен па рис. 13. ДР для данного описания совпадает с графом, изображенным па рис. 13. и содержит к + 3 вертгши, где к - количество задач в д. Для обхода данного ДР необходимо выполнить 2к 4- G шагов.

ДШ ('?',<?), С?!',д), ('??', д) и

Л ('??!', д) позволяют выполнить построение аналогичных ДР. ДР, построенное па основе ДШ ('?'. д) '?1'.д), представлено па рис. для ДШ ('??',</) и с??!', д) 9 - па рис. 15. Оба дерева содер-Рис. 15. ДР дчя ЖЛТ Одинаковое количество вер-ДШ {'i'!',/)) и шин к + 3, по отличаются поряд-('•''!'•.</) ком построения вершин. Для построения и обхода этих ДР необходимо выполнить к + 3 тагов.

При использовании ДШ ('?!',.r¡) в удачном случае обхода дерева займет 2к + 3 шагов, иначе 2к + 6 шагов. При использовании ДШ ('??!', д) в удачном случае обхода дерева займет 1 шага, иначе 2к + б шагов.

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

Использование ДШ (']', (g¡,gj,. ■ ■,g„-i,д„)), í'|!', (gi,g¿, ■. ■ -gn-\,gn)), (')?',

(j f) поетр

К "("?!l

1 V 14, a

Рис. 13. Фрагмент Рис. 14. ДР 11-11.П11 графа, для для ДШ ('!', у) необязательной ПЗ и (".'!', у)

• •-.ffri-1,0«)) и C|?!', (gug-i,----if„-i,S«)) позволяет указать последователь-

ноегь построения ДР. ДР, построенное с использованием ДШ ('|\ (31, д >, ■ ■ ■, 0« ь <?.<)) " СП'. (9i,92, ■ ■ ■ ,S„-i,0n))> проиллюстрировано па рис. 17, а для ДШ ('|?', (<7i,<72, • • •, 9п-и9п)) " CI?!'. (91,92, ■■■,9„-i,9,i)) - "а рис. 18.

Рис. 16. Фрагмент П-НЛП графа для задачи с несколькими методами решения

Рис. 17. ДР для ДШ

Рис. 18. ДР для ДШ (Т-". (УьУа.....,'А.-!•</..)) »

('!-'■ (i/i-.'/J.....,7.1-1.«..))

Пусть количество задач для каждого г?,- из (171,52, • • • ,0« -ь.7«) задана вектором (&1, ¿2,.... Агм_1, /с,,)- Количество вершин ДР, представленных па рис. 1С - 18 будет

,< ч

/,:, I /? ) 1, а для их обхода потребуется 2(^3 I п I 1) шагов. ¿=1 1 = 1

Пусть при использовании ДШ ('|!', (<?ь <?2, • ■ ■, ь7..-1, <7,.)) в первый найденный план

вошла декомпозиция д,п. Тогда для обхода ДР. построенного с использованием этого

шаблона, будет выполнено 2 — ' -п ~ т ' 1 шагов алгоритма.

! = 1 1 = 1

Пусть при использовании ДШ('|?!', ((?ь д2,..., 7„_], д,,)) в первый найденный план вошла декомпозиция д1П. Тогда для обхода ДР, построенного с использованием этого

т

шаблона, будет выполнено 2(£) /с,: I т I 1) шагов алгоритма.

¡=1

б. Для решения переборных задач в иерархическом планировании поступают следующим образом. Предположим, что сложную задачу Гц необходимо решить с помощью множества простых задач Т'= {¿1, <2, ...,¿„-1, £,,}• Причем решение задачи ¿о может включать все задачи из Т' либо их часть. Любая из задач множества Т' может

встречаться несколько раз и заранее не известен порядок этпх задач в решении. Для описания таких задач вводят в описание два метода решения задачи i(). Для реализации первого метода вводят в описание ПО дополнительную СЗ которая будет иметь |7""| методов решения, и

рекуррентное включение задачи f0. Каждая из декомпозиций методов задачи f[, будет содержать одну из задач множества Т'. Декомпозиция второго метода задачи Л) будет включат!» задачу /.",. предусловие которой содержит условие (цель) выхода

О -

Рис. 19. II-НЛП граф для переборных задач

из рекурсии. На рис. 19 проиллюстрирован фрагмент описания пространства задач для таких случаев. На основе такого описания иерархический планировщик строит ДР. представленное па рис. 20. Количество вернпш в этом дереве определяется выражением:

1 + ]Г кпк - 1 +

-(/•л'"1 п(1 -п'1)

1 - п

(1

где п - количество перебираемых задач; ц - количество задач в найденном плане.

Сравним данное ДР с ДР, построенным в пространстве состояний (рис.21). Ко-

ч

личество вершин дерева пространства состояний равно 1 I (1 + 5к)п = 1 +

А:-и

■Гит! 1 ........... _

количестве вершин данных деревьев решении со-

тг^--^ ~ТГ"-Репица в

- - (1-пГ

г, , Л,\ к —4яо'/+1 , 4п(1 — п'1)

ставляет ¿^ (1 + 4fc)n — —. --1—-^ в пользу методов планирования в

о (1—п)

пространстве состоянии.

о с ф р Ф ^

шА-

э у / '/ о j I

• • 4 9 ^ ♦

i: ii

Рис. 20. ДР дяя переборных задач

Мы предлагаем использовать два ДШ ('[]', д) и ('[]!', д) для планирования таких задач. При использовании первого шаблона планирующая система должна искать решения в пространстве состо-Рис. 21. ДР для плапиропания ячий, а при использовав пространство состояний т1ин второго - возвратит!,

первое найденное решение при поиске в пространстве состояний.

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

При описании объектов любой реальной ПО инженер по знаниям сталкивается со сложноструктурированпостью. Сложноструктуриропаилость ПО проявляется в различных иерархических отношениях между объектами и задачами. В первую очередь это иерархии отношений типа «Род-Вид» и «Класс-Экземпляр», во вторую-«Целое-Часть», в том числе и рекурсивные.

С целыо облегчения описания объектов ПС situation и описания ПО domain

предлагается использовать онтологии.

На множестве Concepts определено множество бинарных отношений KindOf, определяющих родовидовую классификацию концептов:

KindOf = {(апс, cfes) | апс, des е Concepts},

где Concepts = {name] name — наименование концепта} - множество концептов; апс - концепт-предок; des - концепт-потомок.

На множестве концептов Concepts и множестве атрибутов концептов Attributes определено множество отношений, определяющих собственные атрибуты концептов: I'ropertyOf - {(concept, atr)\ concept 6 Concepts, atr g Attributes},

где Attributes = {(name, type, expression)} - множество атрибутов, определяемых именем пате, типом знамений type и выражением expression, используемым для вычисления значений атрибута.

Отношения kiridof между концептами служат основой механизма наследования атрибутов. Так упорядоченное множество всех атрибутов концепта дол определяется как:

U {air| pof(con, atr) € PropertyOf},

Atrs(con) = U Atrs(y)

у AiK t'jm)

где Anc(c) = {а- | (x, c) € KindOf} - функция, возвращающая множество предков концепта с. В случае множественпого наследования Vc € Concepts |Лпс(с)| > О, а при единичном наследовании Vc € Concepts ].4яс(с)| < 1. Если |Лпс(с)| = О, то концепт с является базовым.

На множестве Concepts также определено множество отношений PartO/, определяющее транзитивные отношения «Целое-Часть» между концептами:

PartOf — {(precondition, assembling, Details)| assembling G Concepts}.

где precondition - формула, описывающая условие включения деталей Details в сбоку assembling;

Details - упорядоченное множество деталей, которое может содержать assembling-, assembling - концепт-сборка.

Такой способ описания состава объектов позволяет описывать множество декомпозиций концептов. Это бывает необходимо, когда состав объектов имеет необязательные элементы или содержит заранее неопределенное количество объектов указанного типа. D последнем случае требуется использование рекурсивного отношения partof 6 PartOf, в котором assembling 6 Details. Это самый сложный случай проявления сложиоструктурироваппости объектов ПС и их концептов. В итоге состав концепта можно представить в виде И-ИЛИ графа с циклами.

ПС планирования situation определяется как:

situation = (Т, О, t\ d, С),

где Т - множество целевых задач, заданных с помощью ДШ. Objects - множество объектов ПС: F - множество фактов ПС:

d - описание ПО, в рамках которой осуществляется планирование задач Т: С - множество ограничений па создаваем!,тП план.

На множествах объектов О и концептов Concepts определено бинарное отношение [nstnnrrOf, определяющее концепты ПО d. описывающие объекты О ПС situation:

InstanceOf — {(con, obj)\con S Concepts, obj € О}.

Множество значений атрибутов объектов О определяется следующим множеством трехместных отношений:

Values = {(о, а, г.')| о е О, с € Concepts (о), а 6 Л/гб(с), v S All-Values},

где AllValues - универсальное множество значений атрибутов объектов. Множество значений атрибутов объекта о 6 Objects можно определит!,:

Values(o) = {(о, а, г)|(о, с) € Inst.ancesOf,(a.vt,v) € ,4fr.s(c)}U

U {(obj, atr, v)\(obj, atr, v) 6 Values}. (1)

Ha множестве объектов О определено бинарное отношение detallof, которое определяет отношение «Целое-Часть» между объектами и образует следующее множество:

DetailOf ' {detailof (assemble, detail)] assemble, detail € O}. Описание состава объекта object должно удовлетворят!, следующей формуле:

VDet € n(netails(objert.))3 cil, cl2 e Concepts

instanceof (object, cl 1) & Det Ç Objects(cl'2)

parto f(precondition(object, Oet) ----- true, cil, cl'2) G PartOf.

где Details(o) = {c/ei| (o. det) € DetailOf} - множество агрегируемых объектов в объект о;

В(М) - булеаи множества М.

Результатом работы планирующей системы является множество плапов:

Plans = {(s. Р„, V)},

где s - ПС планирования, решение которой описывается планом /'„;

Р„ - упорядоченное множество простых задач, подставляющих решение ПС;

V - множество значений атрибутов плана AttributesПО d.

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

Пусть дана проблемная ситуация s(T, О, 1\ d. С), на основе которой необходимо найти план(ы). Упрощенно, алгоритм планирования будет выглядеть следующим образом:

1. Инициализация: создание начального множества планов Р = 0 и создание множества тупиковых ситуаций DD = 0.

2. Если подшаблоп X" С Т уже разобран, то Т — Т \ Т'.

3. Если Т = 0, то выдать созданное множество плапов Р и завершить работу алгоритма.

4. Выбор очередной задачи 1. G Т из текущей ситуации s'.

5. Формирование множества методов М для задачи t и удовлетворяющих текущему множеству фактов F, т.е. текущей проблемной ситуации s', а также удовлетворяющих ограничениям С. и выполнимыми агентами Л С О в свободное время от исполнения плапов Р. Проверка предусловий методов осуществляется па основе логического вывода.

С. Если AI ф 0. то переход к п. 10.

7. Если М = 0 и задача t S SinipleTasks. то переход к п. 12.

8. Если необходимо произвести откат, то занести текущую ситуацию s' в DD (DU = DD U {а'}) и произвести откат(п.2).

9. Если откат пе возможен, то переход к п. 18.

10. Недетерминированный выбор метода m € А/ и унификация выбранного метода с фактами F текущей ситуации.

11. Если метод m имеет декомпозиционный шаблон, то переход к п.17.

12. Если предусловие задачи t истинно па множестве фактов F проблемной ситуации, то унифицировать параметры задачи и выбрать агента а € А для выполнения задачи t.

13. Если предусловие задачи t ложно на множестве фактов F проблемной ситуации, то произвести откат и перейти к п.2.

14. Вычислить атрибуты задачи f, добавить задачу I и агента а в текущий план PL изменить множество фактов F согласно effect задачи f.

15. Вычислить атрибуты текущего плана PL

1С. Если заданные ограничения С не выполнимы для текущего плана Р1, то произвести откат переходом к п.2.

17. Добавить шаблон decomposition метода гп в Т на место задачи I и перейти к п.2.

18. Если множество DD = 0, то решение (план) не найдено.

19. Выбрать наиболее перспективную тупиковую ситуацию s' 6 DD.

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

21. Если ситуация s' по мнению пользователя гте разрешима, то DD = DD \ {s'} и перейти к п. 18, иначе переход к п.2 с последующим возвратом в п.22.

22. Выдать план Р1 и разрешенную тупиковую ситуацию s'.

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

В процессе синтеза плана и вывода фактов планирующая система осуществляет преобразование описаний концептов предметной области и объектов проблемной ситуации в клаузы логики предикатов первого порядка.

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

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

В рамках разработан- _ »

пой САПР ТП свободной ковки поковок на прес сах было проведено экспериментальное исследование разработанной планирующей системы. Для этого были созданы два описания предметной области планирования. Первое описание было выполнено с ис.полт>зопапи-

ем рекурсивных деком-

Рис. 22. Технологические процессы спободпоЯ копки па прессах

позиций задач (рис. 22),

а второе - с использованием декомпозиционных шаблонов. На рис. 23 приведено описание метода задачи «Рубка поковок» с использованием декомпозиционного шаблона. Было установлено, что второе описание является более компактным и. как следствие, инженер по знаниям затрачивает меньше времени для его описания.

(("Рубка поковок" ?индекс_поковки ?длина_поковки ?масса_поковки Тдокумент ?лнструн«нт ?пресс)Кэадача (К (Я* ()))#пр«дусловив нвтода

( + ! (?? ("Нагрев горячих слитков" "КИ 01-88, ТТП КП-002Потаяциом«тр КСП-ЗП"?яакс_т««пвр ?макс.врв«я_накс_т«м ?иакс_скор_яагр ?вр_магр 'вр.ввдвр 'расч^вр ?мин_вр1 ?кик_вр2 ?кин_врЗ ?макс_вр1 ?нвке_вр2 ?макс_врЗ)) ("Отрубить" ?индакс_поковки ?длина_поковки ?касса_поковки Тдокумаят ?янструнвнт ?прасс *врвчя)1Ятабпон

)

Рис. 23. Описание метода эадачп «Рубка поковок»

Для сравнения алгоритмов синтеза планов были исследованы результаты проектирования семнадцати различных валов круглого сечения с использованием планирующих систем Г!еОПР и 8НОР2. На рис. 2 1 представлены графики, изображающие количество итераций алгоритма для поиска планов ковки одного из валов. При использовании декомпозиционных шаблонов для синтеза технологических процессом ковки вала, представленного па рис. 24, необходимо на 20% меньше итераций алгоритма планировщика КеБНР, чем при использовании стандартной декомпозиции, а для семнадцати валов меньше па 28%.

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

обосновать себестоимость исследования, использовать опит проведения аналогичных исследований. Реализация САПМИ в рамках системы управления базами знаний КС позволяет использовать описание производства заказчика многократно.

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

Рис. 24. Количество итераций для синтеза плапоп

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

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

ЗАКЛЮЧЕНИЕ

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

2. Разработана модель проблемной ситуации планирования. Данная модель позволяет описывать сложноструктурированные объекты проблемных ситуаций планирования.

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

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

4500 ««за I 3500

г эаоо 8

| 2500

■ со стандартной аеюипголяией - КеОНР со ствцомтю*

■ Н«ОНР с иибгонно* Л'

2 (50й

г

| юоа

2« гь 31 зв

56 61 66 71

5. Разработана система управления базами знаний KG, предназначенная для описания предметных областей в виде оптологий и использующая основные элементы описанных в работе моделей предметных областей и проблемных ситуаций планирования. Для планирования задач и обеспечения удобства описания сложноструктурированных предметных областей и проблемных ситуаций планирования в состав дайной системы была интегрирована планирующая система ReDHP. Система KG была внедрена па ФГУП «Ижевский механический завод» для проектирования схем электронного документооборота.

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

7. Спроектирована система автоматизированного планирования маркетинговых исследований. Основой данной системы является планирующая система ReDHP. которая позволяет строить план исследования маркетинговой проблемы, описанной пользователем. На данный момент описано 120 задач, что составляет примерно 20 процентов ог всего объема задач, используемых в различных видах маркетинговых исследований.

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ ИЗЛОЖЕНЫ В СЛЕДУЮЩИХ ПУБЛИКАЦИЯХ

1. Кучуганов D.H., Габдрахманов И.Н. Система визуального проектирования баз знаний /7 Информационные технологии в инновационных проектах: Тр. III меж-

дунар. на.уч.-техп. конф. (Ижевск, 23-24 мая 2001 г.). 4.1. — Ижевск: Изд-во Ижевского радиозавода, 2001. — с. 140-143.

2. Морозов С.А., Габдрахманов И.Н., Баталов В.А. САПР технологических процессов свободной ковки /'/' Материалы Международной научно-технической конференции посвященной 50-летию ИжГТУ (19-22 февраля 2002г.). В пяти частях. Ч. 2. Инновационные технологии в машиностроении и приборостроении. -Ижевск: Изд-во ИжГТУ, 2002. - с. 191-190.

3. Кучугапов D.H., Габдрахманов И.Н. Планирование задач в сложноструктурированных ситуациях // Труды международных иаучпо-техпических конференций «Интеллектуальные системы (IEEE A IS'04)» и «Интеллектуальные САПР» (CAD 2004). Научное издание в 3-х томах. М.: Изд-во Физико-математической литературы , 2004, Т.1. с. 214-223.

4. Габдрахманов И.Н. Планирование задач па примере САПР технологических процессов свободной ковки // Информационные технологии в инновационных проектах: Сб. тр. пауч.-техпич. форума с междупар. участием: В 4 ч. Ч 1. .....Ижевск,

Изд-во ИжГТУ, 2004. - с. 28-35.

5. Габдрахманов И.Н., Кучугапов В.Н. Планирующий модуль для системы управления базами знаний // «Новые информационные технологии. Разработка и аспекты применения». Труды VI Всероссийской научной конференции с международным участием. Научное издание. — Таганрог. «ПБОЮЛ В.А. Кравцов». 2004. -с. 103-108.

G. Габдрахманов И.Н. Система автоматизированного планирования маркетинговых исследований ,// Интеллектуальные системы в производстве: период, пауч.-практ. журп. - 2000. Ж. Ижевск: Изд-во ИжГТУ, 2006. С. 144-150.

7. Кучугапов В.Н.. Габдрахманов И.Н., Шутов Е.А. Онтологическое проектирование обучающих систем // Вторая международная конференция по когнитивной пауке: Тезисы докладов: В 2 т. — Т. 2. — СПб.: Филологический факультет СПбГУ, 2006. с. 588-589.

8. Габдрахманов И.Н. Модели предметной области и проблемной ситуации в планировании задач //Вестник ИжГТУ: Периодический научно-теоретический журнал Ижевского государственного технического университета. —Ижевск: Изд-во ИжГТУ, 2006. -Вып. 3. -с. 13-16.

Подписано в печать 02.06.06. Формат С0х84/1С. Бумага офсетная. Усл. печ.л 1,0 Тираж 100 экз. Заказ 170 Издательство Ижевского государственного технического университета. -126069, г. Ижевск, Студенческая, 7

ВВЕДЕНИЕ

1. МЕТОДЫ И СИСТЕМЫ ИНТЕЛЛЕКТУАЛЬНОГО ПЛАНИРОВАНИЯ.

1.1. Классическое планирование.

1.2. Частично упорядоченное планирование.

1.3. Планирование с использование графов планирования.

1.4. Иерархическое планирование.

1.5. Планирование как задача удовлетворения ограничений.

1.6. Эвристическое планирование.

1.7. Условное планирование

1.8. Согласованное планирование.

1.9. Стохастическое планирование.

1.10. Планирование с обучением.

1.11. Гибридное планирование.

1.12. Практическое планирование.

1.13. Выводы по главе и постановка задач исследования.

2. МОДЕЛИ ПРЕДМЕТНОЙ ОБЛАСТИ И ПРОБЛЕМНОЙ СИТУАЦИИ ПЛАНИРОВАНИЯ.

2.1. Модель предметной области планирования.

2.1.1. Описание задач предметной области.

2.1.2. Описание концептов.

2.1.3. Описание правил вывода фактов.

2.2. Модель проблемной ситуации планирования

2.2.1. Описание объектов проблемной ситуации.

2.2.2. Представление планов.

2.2.3. Описание ограничений проблемной ситуации.

2.3. Выводы по главе.

3. МЕТОДЫ ПЛАНИРОВАНИЯ И АНАЛИЗА СЛОЖНОСТРУКТУРИРОВАННЫХ СИТУАЦИЙ

3.1. Алгоритм метода планирования.

3.2. Анализ ситуаций.

3.3. Выводы по главе.

4. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ ПЛАНИРУЮЩЕЙ СИСТЕМЫ.

4.1. Методика описания предметных областей и проблемных ситуаций планирования

4.2. Система автоматизированного проектирования технологических процессов свободной ковки на прессах.

4.3. Система автоматизированного планирования маркетинговых исследований.

4.4. Выводы по главе.

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

Значительный вклад в развитие теоретических исследований и практических разработок в сфере интеллектуального планирования внесли как зарубежные исследователи: Fikes R.O. (США), Ghallab М.(Франция), Kambhampati S. (США), Kautz Н. (США), McAllester D.A. (США), Nau D.S. (США), Nilsson N.J. (США), Rosenblit D. (США), Sacerdoti E.D. (США), Tate А. (Великобритания), Traverso P. (Италия), Weld D.S. (США), Wilkins D.E. (США), так и отечественные ученые: Аверкин А.Н., Поспелов Д.А., Осипов Г.С., Стефанюк B.JL, Ефимов Е.И., Алиев Р.А., Кузин Е.С.

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

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

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

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

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

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

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

Среди основных задач работы следует выделить:

1) анализ существующих методов и систем интеллектуального планирования задач;

2) разработка моделей предметной области и проблемной ситуации планирования задач;

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

4) разработка алгоритмов и программной системы планирования задач;

5) экспериментальное исследование разработанной системы планирования задач.

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

На защиту выносятся:

1) модель предметной области планирования;

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

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

4) алгоритм иерархического планирования задач;

5) разработанная универсальная планирующая система ReDHP;

6) система управления базами знаний KG;

7) система автоматизированного проектирования технологических процессов свободной ковки поковок на прессах;

8) спроектированная система автоматизированного планирования маркетинговых исследований;

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

Научная новизна работы состоит в:

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

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

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

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

Реализация результатов. Результаты работы используются в «Инженерно-технологическом центре «Кузнец»» при научно-исследовательском институте металлургической технологии для проектирования технологических карт процессов свободной ковки поковок на прессах, в ФГУП «Ижевский механический завод» для проектирования схем электронного документооборота и в Ижевском государственном техническом университете для обучения студентов специальностей «Системы автоматизированного проектирования» и «Автоматизированные системы обработки информации и управления» при изучении дисциплин «Системы искусственного интеллекта» и «Информационные технологии», а также в динломном проектировании.

Апробация работы. Основные научные результаты, полученные в диссертационной работе, докладывались и обсуждались на: 3-ей международной научно-технической конференции «Информационные технологии в инновационных проектах» (Ижевск, 2001); международной научно-технической конференции, посвященной 50-летию ИжГТУ (Ижевск, 2002); международной научно-технической конференции «Интеллектуальные системы» (Геленджик, 2004); на научно-техническом форуме с международным участием «Высокие технологии - 2004» (Ижевск, 2004); на 7-ой всероссийской научной конференции с международным участием «Новые информационные технологии. Разработка и аспекты применения» (Таганрог, 2004); на семинаре «Теоретические основы и приложения информатики» кафедры «Математическое обеспечение ЭВМ» Удмуртского государственного университета.

Публикации. Результаты работы отражены в 8 печатных работах.

Структура работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы, включающего 153 наименования, и четырёх приложений. Основная часть работы изложена на 151 странице машинописного текста, содержит 43 рисунка, 2 таблицы. Приложения содержат акты о внедрении, описание предметных областей и проблемных ситуаций планирования, использованных в экспериментальных исследованиях, и описание грамматики расширения языка PDDL 3.0, использующего декомпозиционные шаблоны в описании методов решения задач.

4.4. Выводы по главе

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

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

3. Разработано описание предметной области планирования маркетинговых исследований.

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

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

6. Разработано расширение языка PDDL для описания задач с использованием шаблонной декомпозиции задач.

7. Разработана методика описания предметной области планирования с использованием декомпозиционных шаблонов и применением онтоло-гий в описании объектов проблемной ситуации.

8. Разработана система управления базами знаний KG, позволяющая описывать сложноструктурированные предметные области и проблемные ситуации планирования в виде онтологий.

ЗАКЛЮЧЕНИЕ

В работе получены следующие основные выводы и результаты:

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

2. Разработана модель проблемной ситуации планирования. Данная модель позволяет описывать сложноструктурированные объекты проблемных ситуаций планирования.

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

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

5. Разработана система управления базами знаний KG, предназначенная для описания предметных областей в виде онтологий и использующая основные элементы описанных в работе моделей предметных областей и проблемных ситуаций планирования. Для планирования задач и обеспечения удобства описания сложноструктурированных предметных областей и проблемных ситуаций планирования в состав данной системы была интегрирована планирующая система ReDHP. Система KG была внедрена на ФГУП «Ижевский механический завод» для проектирования схем электронного документооборота.

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

7. Спроектирована система автоматизированного планирования маркетинговых исследований. Основой данной системы является планирующая система ReDHP, которая позволяет строить план исследования маркетинговой проблемы, описанной пользователем. На данный момент описано 120 задач, что составляет примерно 20 процентов от всего объема задач, используемых в различных видах маркетинговых исследований.

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

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

1. Аверкин А.Н., Гаазе-Рапопорт М.Г., Поспелов Д.А. Толковый словарь по искусственному интеллекту. — М.гРадио и связь, 1992.- 256 с.

2. Аверкин А.Н., Ефимов Е.И. Планирование действий. //Искусственный интеллект. Кн.2. Модели и методы: Справочник. //Под ред. Д.А.Поспелова. М.: Радио и связь. 1990. С.231-243.

3. Алиев Р.А., Гулько Д.Е., Шахназаров М.М. Экспертная система для производственного планирования// Изв. АН СССР. Техн. кибернетика, -1988. -т. -С. 118-128.

4. Аристова М.В., Игнатьев М.Б., Караваев Э.Ф. Логика — необходимая часть инструментария искусственного интеллекта// Изв. АН СССР. Сер. Техн. кибернетика. 1983. №3. с.128-133.

5. Бабаев И.О., Тимофеев А.В. Система планирования подвижного робота, основанная на методе резолюций с элементами обучения// Теория, принципы устройства и применение роботов и манипуляторов: Тр. V Всесоюзной симпоз. Л., 1974. с.180-184.

6. А.Н. Бездушный, Э.А. Гаврилова, В.А. Серебряков, А.В. Шкотин. Место онтологий в единой интегрированной системе РАН // Сборник научных трудов «Современные технологии в информационном обеспечении науки». Москва, 2003. - с.97 -115.

7. Беляевский И.К. Маркетинговое исследование: информация, анализ, прогноз: Учеб. пособие. — М.: Финансы и статистика, 2001. — 320 е.: ил.

8. Божук С.Г., Ковалик Л.Н. Маркетинговые исследования — СПб.: Питер, 2004. — 304 е.: ил. —(Серия «Маркетинг для профессионалов»)

9. Братко И. Программирование на языке Пролог для искусственного интеллекта: Пер. с англ. —М.: Мир, 1990. — 560 е., ил.

10. Вагин В.Н. Дедукция и обобщение в системах принятия решений. — М.: Наука. Гл. ред. физ.-мат. лит. 1988. — 384 с. — (Пробл. искусств, интеллекта).

11. И. Вагин В.Н., Головина Е.Ю., Загорянская А.А., Фомина М.В. Достоверный и правдоподобный вывод в интеллектуальных системах / Под ред. В.Н. Вагина, Д.А. Поспелова. М.: ФИЗМАТЛИТ, 2004. - 704 с.

12. Базы знаний интеллектуальных систем/ Т.А. Гаврилова, В.Ф. Хорошевский Спб: Питер, 2000. - 384с.: ил.

13. Гладун В.П. Эвристический поиск в сложных средах. — Киев: Наукова думка, 1977. 166 с.

14. Голубков Е.П. Маркетинговые исследования Электронный ресурс.// Маркетинг в России и за рубежом. — Москва, Издательство «ДЕЛО И СЕРВИС». 2000. - №5. - Режим доступа: http://www.dis.ru/ market/arhiv/2000/5/8. html, свободный. — Загл. с экрана. — Яз. рус.

15. Голубков Е.П. Маркетинговые исследования Электронный ресурс.// Маркетинг в России и за рубежом. — Москва, Издательство «ДЕЛО И СЕРВИС». 2001. - М. - Режим доступа: http://www.dis.ru/ market/arhiv/2001/l/4.html, свободный. — Загл. с экрана. — Яз. рус.

16. Гуц А.К. Математическая логика и теория алгоритмов: Учебное пособие. — Омск: Издательство Наследие. Диалог-Сибирь, 2003. — 108 с.

17. Дискретная математика для программистов // Ф.А. Новиков. — СПб.: Питер, 2001. 304 е.: ил.

18. Добрецов С.В., Шестаков С.М. Планирование действий в искусственном интеллекте// Демиург. 1998. - М. - СПб, 1998. - С.32-46.

19. Ефимов Е.И. Решатели интеллектуальных задач. М.: Наука, 1982. — 320с.

20. Ефимов Е.И. Сфинкс вычислительный комплекс, предназначенный дляобоснования интеллектуальных решений//-М.: ВЦ РАН, 1993. — 20с.

21. Иванов Д.А. Представление знаний и поддержка рассуждений с использованием ограничений: Автореф. дис. . канд. физ.-мат. наук: 007.51:681.3.06 / Моск. авиац. ин-т. М., 1993. -20 с.

22. Ильин В.А. Алгоритмы планирования поведения интегральных роботов в условиях неполной информации о структуре внешней среды. — Томск: Изд-во Том. ун-та, 1990. 270 с.

23. Искусственный интеллект — основа новой информационной технологии// Поспелов Г.С. М.: Наука, 1988. - 280с.: ил.

24. Каляев И.А., Носков В.П., Чернухин Ю.В. Однородная структура в системе иерархического планирования направления движения транспортного робота// Электронное моделирование. 1985. X5 2. — с.95-96.

25. Канович М.И, Минц Г.Е. Планирование при синтезе программу/Искусственный интеллект. Кн.2. Модели и методы: Справочник. //Под ред. Д.А.Поспелова. М.: Радио и связь. 1990. — С. 243 —251.

26. Корухова J1.C., Любимский Э.З., Максимов Л.В., Малышко В.В. Система объяснений в решателе геометрических задач. Кафедра системного программирования факультета вычислительной математики и кибернетики МГУ им. М.В.Ломоносова, 1998.

27. Корухова Л.С., Любимский Э.З., Малышко В.В. Программные средства реализации ассоциативного планирования. Препринт ИПМ №10, Москва, 2002. 29 с.

28. Клоксин У., Меллиш К. Программирование на языке Пролог /Пер. с англ. — М.: Мир, 1987. 336 с.

29. Кузин Е.С., Ройтман А.И., Фоминых И.Б., Хахалип Г.К. Интеллектуализация ЭВМ. Кн. 2 серии «Перспективы развития вычислительной техники» М., Высшая школа, 1989, с. 93-132.

30. Кузин Е.С., Фоминых И.Б. Алгоритм планирования целенаправленной деятельности робота в детерминированных квазистационарных средах. —

31. В кн.: Вопросы радиоэлектроники. Серия общетехническая, вып 8, 1975. с. 72-78.

32. Кучуганов В.Н. Автоматический анализ машиностроительных чертежей. — Иркутск: Изд-во Иркут. ун-та, 1985. — 112 с ил.

33. Кучуганов В.Н. Методология и инструментальные средства синтеза сценариев графического инженерного диалога и объектно ориентированных САПР: Дис. .док. тех. наук: 519.682.5 / Ижевский механический институт. Ижевск, 1993. - 284 с.

34. Лавров С.С., Залогова Л.А., Петрушина Т.И. Принципы планирования решения задач в системе автоматического синтеза про-грамм//Программирование. — 1999. — № 6. — С. 67-73.

35. Липаев В.В. Надежность программных средств. Серия «Информатизация России на пороге XXI века». М. СИНТЕГ, 1998. - 232 с.

36. Лорьер Ж.-Л. Системы искусственного интеллекта: Пер. с франц. — М.: Мир, 1991. -568с., ил.

37. Малхорта, Нэреш К. Маркетинговые исследования. Практическое руководство, 3-е издание.: Пер. с англ. — М.: Издательский дом "Вильяме", 2002. — 960 е.: — Парал. тит. англ.

38. А. Матросов, М. Чаунин "Самоучитель Perl", СПб.: БХВ Санкт-Петербург, 2000. - 425 с.

39. Нарииьяни О.И. ТЕОН -2: от Тезауруса к Онтологии и обратно // В сб. Межд. Семинар ДИАЛОГ'2002, Протвино, Июнь 11 -16,2002. -т.1, -с. 199 -154

40. Непейвода Н.Н. Некоторые семантические конструкции конструктивных логик схем программ// Вычислительные системы. —Вып.129. — Новосибирск, 1989. —с. 44-66.

41. Непейвода Н.Н. Построение правильных программ. — Вопросы кибернетики, 1978, т. 46, вып. 100-103. с. 88-122.

42. Нильсон Н. Искусственный интеллект. Методы поиска решений.: Пер. с англ. — М.: Издательство «Мир», 1973. — 270с.

43. Нильсон Н. Принципы искусственного интеллекта. : Пер. с англ. — М.: Радио и связь, 1985. — 376 е., ил.

44. Осипов Г.С. Искусственный интеллект: основные направления и состояние исследований//Компьютерра. — 2002. — № 30(455). —С. 16-19.

45. Перегудов Ф.И., Тарасенко Ф.П. Введение в системный анализ: Учеб. пособие для вузов. — М.: Высш. шк., 1989. — 367 е.: ил.

46. Погонин В.А. Методы и алгоритмы управления химико-технологическими процессами с применением роботов в условиях неопределенности: Автореф. дис. . д-ра техн. наук. — Тамбов., 2003. — 25 с.

47. Попов Э.В., Фирдман Г.Р. Алгоритмические основы интеллектуальных роботов и искусственного интеллекта. Главная редакция физико-математической литературы изд-ва «Наука», М., 1976. — 456 с.

48. Поспелов Г.С., Ириков В.А. Программно-целевое планирование и управление. —М.: Сов. радио, 1976. — 440 с.

49. Поспелов Г.С., Поспелов Д.А. Искусственный интеллект- прикладные си-стемы//Новости искусственного интеллекта. — 1998. — №4. — С.84-103.

50. Поспелов Д.А. Моделирование рассуждений. Опыт анализа мыслительных актов. — М.: Радио и связь, 1989. — 184 е.: ил.

51. Растригин JT. Искусственный интеллект//Радио. —1988. —№4. —С.22-23.

52. Рассел С., Норвиг П. Искусственный интеллект: современный подход, 2-е изд.: Пер. с англ. — М.: Издательский дом «Вильяме», 2006. — 1408 е.: ил. — Парал. тит. англ.

53. Семенов Е.И. Ковка и объемная штамповка. Учебник для вузов. М. «Высшая школа», 1972. 345с.

54. Стобо Д.Ж. Язык программирования пролог: Пер. с англ. — М.: Радио и связь, 1993. — 368 е.: ил.

55. Троицкий В.В. Методы и программные средства представления временных зависимостей в интеллектуальных системах поддержки принятия решений: Автореф. канд. тех. наук/ Моск. энерг. ин-т (тех. унв-т). — М., 2004. 20с.

56. Тыугу Э.Х. Концептуальное программирование. — М.: Наука. Главная редакция физико-математической литературы, 1984. — 256 с. (Проблемы искусственного интеллекта)

57. Уэйнрайт П. Apache для профессионалов. — М.: Лори, 2001. — 474с.

58. Хоггер К. Введение в логическое программирование: Пер. с англ. — М.: Мир, 1988. -348с., ил.

59. Хювеннен Э., Сеппянен Й. Мир Лиспа. В 2-х т. Т.1: Введение в язык Лисп и функциональное программирование. Пер. с финск. — М.:Мир, 1990. — 447 с.

60. Хювеннен Э., Сеппянен Й. Мир Лиспа. В 2-х т. Т.2: Методы и системы программирования. Пер. с финск. — М.: Мир,1990. — 319 с.

61. Шанин Н.А., Давыдов Г.В. и др. Алгоритм машинного поиска естественного логического вывода в исчислении высказываний. — М.; Л.; Наука, 1965. 40 с.

62. Avrim L. Blum and Merrick L. Furst. Fast planning through planning graph analysis. In Proceedings of the First International Conference (AIPS92), pages 20-27, College Park, MD, 1992.

63. Bacchus F., Chen X., P. van Beek, Walsh T. Binary vs Non-Binary Constraints, Artificial Intelligence vol 140, p. 1-37, 2002.

64. Beck H. The Management of Job-Shop Scheduling Constraints in TOSCA. Technical Report 121, AIAI, University of Edinburgh, 1993, pp. 2-14.

65. Blythe J. An Overview of Planning Under Uncertainty. Pre-print from AI Magazine, 20(2), Summer 1999, pp. 37-54.

66. Bonet В., Geffner H. Planning with incomplete information as heuristic search in belief space. In Artificial Intelligence Planning Systems, pages 52-61, 2000.

67. Bryce D. Kambhampati S. Heuristic guidance measures for Conformant Planning. In Procedings of the ICAPS workshop on Planning under uncertainty and incomplete information, pages 365-375, 2003.

68. Bylander T. Complexity results for serial decomposability. In Proceedings ofthe Tenth National Conference on Artificial Intelligence (AAAI-92), p. 729734, San Jose. AAAI Press. 1992.

69. Castellini C., Giunchiglia E., and Tacchella A. Improvements to sat-based conformant planning. In 6th European Conference on Planning, pages 241252, 2001.

70. Chapman D., Planning for Conjunctive Goals. Artificial Intelligence, vol. 32, №, 1987, pp. 333-377.

71. Cross S.E., Walker E. DART: Applying knowledge based planning and scheduling to crisis action planning. In Zweben M. and Fox M.S. (Eds.), Intelligent Scheduling, p. 711-729. Morgan Kaufmann, San Mateo, California.

72. Currie K. W., Tate A. O-Plan: The Open Planning Architecture. Artificial Intelligence 52 (1), pp. 49-86, 1991.

73. Denny М. Ontology Tools Survey, Revisited Электронный ресурс.// O'REILLY XML.COM. — Электрон, дан.,2004. Режим доступа: http://www.xml.eom/pub/a/2004/07/14/onto.html, свободный. — Загл. с экрана. — Яз. англ.

74. М. Do and S. Kambhampati. Planning as constraint satisfaction: Solving the planning graph by compiling it into CSP. Artif. Intell. 132(2): p. 151-182 (2001).

75. Doyle P. Planning. AI Quail Summary. Stanford University, 1997.

76. Erol K., Hendler J., Nau D. Semantics for Hierarchical Task-Network Planning. Technical report CS-TR-3239 UMIACS-TR-94-31 ISR-TR-95-9. 28 pages.

77. Erol, Hendler and Nau. UMCP: A Sound and Complete Procedure for

78. Hierarchical Task-Network Planning. In AIPS-94, pp. 249-254.

79. K. Erol, J. Hendler and D. S. Nau. HTN Planning: Complexity and Expressivity. In Proceedings of the Twelfth National Conference on Artificial Intelligence (AAAI-94), pp. 1123-1128, Seatle, 1994. AAAI Press.

80. F. Fages, J. Fowler, and T. Sola. A reactive clp scheme. In Proceedings of ICLP'95, Tokyo, 1995, pp. 136-150.

81. Falaschi M., Levi G., Palamidessi C., A Synchronization Logic: Axiomatic and Formal Semantics of Generalized Horn Clauses, Information and Control, 60, 1 -3, 1984, pp. 36 -39.

82. Fikes R.O., Nilsson N.J. STRIPS: A new approach to application of theorem proving to problem solving. Artificial Intelligence, 2(3-4), pp. 189-208, 1971.

83. Fikes R. REF-ARF: A System for Solving Problems Stated as Procedures, Artifiial Intelligence, 1(1/2): 27-120, 1970.

84. Fikes R.E., Hart P.E., Nilsson N.J., Learning and Executing Generalized Robot Plans. Artificial Intelligence, vol. 3, 1972, pp. 251-288.

85. Gerevini A., Long D. BNF Description of PDDL 3.0 Электронный ресурс., October 2005. — Режим доступа: http://www.cs.yale.edu/homes/dvm/ papers/pddl-bnf .pdf, свободный. — Загл. с экрана. — Яз. англ.

86. Ghallab М., Howe A., Knoblock С, McDermott D., Ram A., Veloso М., Weld D., Wilkins D. PDDL — The Planning Domain Definition Language. Technical Report DCS TR-1165, Yale Center for Computational Vision and Control, Connecticut, October 1998. 23 pages.

87. Ghallab M., Nau D., Traverso P. Automated Planning: Theory and Practice. Hardbound, 672 pages, 2004.

88. Ghosh S., Hendler J., Kambhampati S., Kettler B. UM Nonlin Version 1.2.21. User Manual. 33 pages.

89. Geverini A., Schubert L.K. Accelerating partial-order planners: some techniques for effective search control and pruning. Jornal of Artificial Intelligence Research, 5, p. 95-137.

90. Goldman R.R, Boddy M.S. Representing Uncertainty in Simple Planners. KR 1994: 238-245.

91. S.K. Gupta, D.A. Bourne, K. Kim, and S.S. Krishnan. Automated process planning for sheet metal bending operations. Journal of Manufacturing Systems, 17(5): 338-360, 1998.

92. Hammond, K. J. Case-based Planning: An Integrated Theory of Planning, Learning and Memory. Ph.D. Dissertation, Yale University. 1986. 307 pages.

93. Haslum P. Modern AI Planning: Reading List, Modern AI Planning Course at the Linkopings University, 2001.

94. Hoang, H., Lee-Urban, S., and Mucoz-Avila, H. Hierarchical Plan Representations for Encoding Strategic Game AI. In Proceedings of Artificial Intelligence and Interactive Digital Entertainment Conference (AIIDE-05), AAAI Press, 2005, 6 pages.

95. Hoffmann J. FF: The fast-forward planning system, The AI Magazine 22 (3), 2001, pages 57-62.

96. J. Hoffmann, B. Nebel, The FF Planning System: Fast Plan Generation Through Heuristic Search, in: Journal of Artificial Intelligence Research, Volume 14, 2001, pages 253-302.

97. G. Hripcsak. The Arden Syntax for medical logic modules: introduction. Computers in Biology and Medicine 1994;24(5):329-30.

98. L. Ihrig and S. Kambhampati. Derivational replay for partial-order planning.

99. Proceedings of AAAI-94, pages 116-125, 1994.

100. Kambhampati S., Mali A., Srivastava B. Hybrid Planning for Partially Hierarchical Domains. Proceedings of the Fifteenth National Conference on Artificial Intelligence(AAAI-98), Madison, Wisconsin, United States, 1998, pp. 882 888.

101. H. Kautz and B. Selman. Planning as Satisfiability. In Proceedings References 139 of the 10th European Conference on Artificial Intelligence (ECAI-92), pages 359-363, Vienna, Austria, 1992.

102. Kautz H., McAllester D.A., Selman B. Encoding plans in propositional logic. In Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning, p. 374 384, Cambridge, Massachusetts. Morgan Kaufmann. 1996.

103. Kautz H., Selman B. Blackbox: A New Approach to the Application of Theorem Proving to Problem Solving. AIPS98 Workshop on Planning as Combinatorial Search, pages 58-60, June 1998.

104. Koehler J. Solving Complex Planning Tasks Through Extraction of Subproblems. In AIPS-98, p.62-69, 1998.

105. Kushmerick N., Hanks S., Weld D.S., An Algorithm for Probabilistic Least-Commitment Planning. AAAI'94, pp. 1073-1078, 1994.

106. Long D. and Fox M. Efficient Implementation of the Plan Graph in STAN.

107. JAIR, 1998, V10, p.87-115.

108. Lotem A., Nau D., Hendler J. Using Planning Graphs for Solving HTN Planning Problems. In Proceedings of AAAI-99, 1999, p. 534-540.

109. Mali A., Kambhampati S. Encoding HTN Planning in prepositional logic. In Proceedings of AIPS-98, p. 190-198, 1998.

110. McAllester D., Rosenblit D. Systematic Nonlinear Planning. In Proceedings of AAAI-91, Vol 2, p. 634-639, Anaheim, Ca., 1991. AAAI Press.

111. McCarthy J., Hayes P.J., Some Philosophical Problems from the Standpoint of Artificial Intelligence. Machine Intelligence 4, American Elsevier, New York, 1969, pp. 463-502.

112. McCluskey T.L., Liu D., Simpson R.M. Using Knowledge Engineering and State Space Planning Techniques to Optimise an HTN Planner. Delft University of Technology, Published in refereed proceedings of PlanSig 2002, Holland, pp 1-11, 2002.

113. Nau D., Cao Y., Lotem A., Munoz-Avila H. SHOP: Simple Hierarchical Ordered Planning. Technical Report CS-TR-3981, UMIACS-TR-9904.

114. Nayak P., Gupta A., Rosenbloom P. Comparison of the Rete and Treat Production Matchers for Soar. (A summary). In Proceedings of the Seventh National Conference on Artificial Intelligence, pages 693-698. 1988.

115. Dana S. Nau, Tsz-Chiu Au, Okhtay Ilghami, Ugur Kuter, Hector Munoz-Avila, J. William Murdock, Dan Wu, Fusun Yaman. Applications of SHOP and SHOP2. IEEE Intelligent Systems 20(2): 34-41 (2005).

116. Nau D.S., Au T.C., Ilghami O., Kuter U., Murdock J.W., Wu D. and Yaman F. «SHOP2: An HTN Planning System»// Journal of Artificial Intelligence

117. Research (JAIR), Volume 20, pages 379-404, 2003.

118. Newell A., Shaw J. C., Simon H. A., Report on a general problem-solving program. IFIP Congress, 1959, pp. 256-264.

119. Nguyen X., Kambhampati S., Nigenda R.S. Planning graph as the basis for deriving heuristics for plan synthesis by state space and CSP search/ Artificial Intelligence 135, p. 73-123. 2002.

120. Nigenda R.S., Nguyen X., Kambhampati S. AltAlt: Combining the Advantages of Graphplan and Heuristic State Search. Department of Computer Science and Engineering Arizona State University, Tempe AZ 85287-5406.

121. Nguyen X., Kambhampati S. Reviving Partial Order Planning. Department of Computer Science and Engineering Arizona State University, Tempe AZ 85287-5406.

122. Peot, M, and Smith, D. Conditional nonlinear planning, In Proc. 1st Int. Conf. on AI Planning Systems, pp. 189197, 1992.

123. Requicha A.A.G., Spitz S.N. Inspection planning for Coordinate Measuring Machines: progress report. Proc. 26th NSF Design к Manufacturing Systems Conf., Vancouver, ВС, January 3-6, 2000.

124. Sacerdoti E. The nonlinear nature of plans. In Proceedings of the 4th International Joint Conference on Artificial Intelligence (IJCAI'1975), p. 206214. 1975.

125. E. Sirin, B. Parsia, D. Wu, J. Hendler, and D. Nau. HTN planning for web service composition using SHOP2. Journal of Web Semantics, l(4):377-396, 2004.

126. Shahar Y, Miksch S, and Johnson P. The Asgaard project: a task-specific framework for the application and critiquing of time-oriented clinical guidelines. Artificial Intelligence in Medicine 1998; 14: 29-51.

127. Smith S.J.J., Nau D.S., and Throop T. Computer bridge: A big win for AI planning. AI Magazine 19(2), pp. 93-105, 1998.

128. Smith D.E, Peot M.A. Postponing Threats in Partial-Order Planning. In Proceedings of the Eleventh National Conference on Artificial Intelligence, pages 500-506, Washington, DC, 1993.

129. Smith D. and Weld D. Conformant Graphplan In Proceedings 15th National Conf. on AI, pp. 889-896 ,1998.

130. Spalazzi L. A Survey on Case-Based Planning.// Artificial Intelligence Review. № 16. pp. 3-36, 2001

131. Tate A., INTERPLAN: A plan generation system which can deal with interactions between goals. University of Edinburgh, Machine Intelligence Research Unit, MIP-R-109, December 1974.

132. Tate, A., Generalizing project networks. In Proceedings IJCAI-77, Cambridge, MA, pp. 888-893, 1977.

133. Tate A., Dalton J., Levine J. O-Plan: a Web-based AI Planning Agent. ААА1/ IAAI2000: pp. 1131-1132.

134. Tate A., Hendler J., Drummond M. A Review of AI Planning Techniques. In Readings in Planning, Allen, J.; Hendler, J.; and Tate, A., eds., 26-49. San Mateo, California: Morgan Kaufmann Publishers, Inc. 1990.

135. Trubetskoy G. ONLamp.com: Introducing modpython Электронный ресурс. — Электрон, дан., 2003. — Режим доступа: http: //www. onlamp. com/ pub/a/python/2003/10/02/modpython.html, свободный. — Загл. с экрана. — Яз. англ.

136. Tu S.W., Musen M.A. The EON model of intervention protocols and guidelines. Proc AMIA Annu Fall Symp., pp.587-91, 1996.

137. Veloso M., Carbonell J., Perez A., Borrajo D., Fink E., Blythe J. Planningand Learning: The PRODIGY Architecture. Journal of Experimental and Theoretical Artificial Intelligence, 7(1): 81-120, 1995.

138. D. Vrakas, I. Vlahavas, ViTAPlan: A Visual Tool for Adaptive Planning. In Proceedings of the 9th Panhellenic Conference on Informatics, Thessaloniki, Greece, 2003.

139. Wandinger R. Achieving Several Goals Simultaneously. Machine Intelligence № 8, p. 94-136, 1977.

140. Warren D.H.D., WARPLAN: A System for Generating Plans. Department of Computational Logic Memo №76, University of Edinburgh, 1974.

141. Weld D.S. Recent Advances in AI Planning. AI Magazine, 20(2), p. 93-122, 1999.

142. Wilber, В. M. A Shakey Primer, Technical Report . Stanford Research Institute, 333 Ravenswood Ave, Menlo Park, CA 94025, November 1972.

143. Wilkins D.E. Can AI planners solve practical problems? Computation Intelligence, 6(4), p. 232-246, 1990.

144. Wilkins D.E. Using the SIPE-2 Planning System. A manual for SIPE-2, Version 6.1. 2000, 242 pages.