Планирование задач в сложноструктурированных ситуациях тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Габдрахманов, Ильшат Накипович

• Габдрахманов, Ильшат Накипович
• кандидат технических наук
• 2006

Оглавление диссертации кандидат технических наук Габдрахманов, Ильшат Накипович

ВВЕДЕНИЕ

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

Список литературы диссертационного исследования кандидат технических наук Габдрахманов, Ильшат Накипович, 2006 год

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.