Содержание к диссертации
ВВЕДЕНИЕ — 4
1. ВЫБОР ПРИНЦИПОВ ОРГАНИЗАЦИИ ЭКСПЕРТНЫХ СИСТЕМ ДЛЯ ОПТИМИЗАЦИИ ПЛАНИРОВАНИЯ ДЕЙСТВИЙ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ « 9
1Л. Назначение и функции интеллектуальных агентов 9
1.2. Описание знаний интеллектуальных агентов 14
1.3. Задача планирования действий интеллектуального агента 16
1.3.1, Среда функционирования интеллектуальных агентов и ее основные характеристики , 16
1.3.2, Постановка задачи планирования интеллектуальных агентов 18
1.3.3, История исследовании и текущее состояние 22
1.4. Анализ перспектив развития и выбор принципов организации экспертных систем для оптимизации планирования действий интеллектуальных агентов 28
1.4.L Особенности разработки и применения экспертных систем 28
1.4-2. Использование искусственных нейронных сетей в экспертных системах 33
1.5. Постановка задачи диссертационной работы 41
2. ФОРМИРОВАНИЕ КЛАССА ПЕРСПЕКТИВНЫХ СТРАТЕГИЙ ПЛАНИРОВАНИЯ ДЕЙСТВИЙ ИНТЕЛЛЕКТУАЛЬНЫХ АГЕНТОВ 44
2,1 - Представление алгоритмов нелинейного планирования в пространстве состояний 44
2.2. Обобщенный алгоритм нелинейного планирования в пространстве состояний 54
2.2.1. Конструктор решений. 56
2.2.2. Уточнение частичного плана. , 57
2.2.3. Проверка состоятельности модифицированного плана 59
2*2.4. Оптимизация уточненного плана 60
2.3. Анализ особенностей реализаций нелинейных систем планирования и их представление через обобщенный алгоритм планирования 62
2.3.1. Алгоритм NONLIN. 62
2.3.2. Алгоритм TWEAK 64
2.3.3. Алгоритм SNLP 66
2.3.4. Алгоритм UA 67
2.3.5. Формирование базиса класса нелинейных систем планирования 69
2.4. Выводы 72
3. АНАЛИЗ КРИТЕРИЕВ ОПТИМИЗАЦИИ ПЛАНИРОВАНИЯ ДЕЙСТВИЙ. 73
3.1. Анализ известных подходов к оптимизаіщи планирования действий 73
3.2. Анализ показателей производительности алгоритмов планирования».. 75
3,2.L Универсальные показатели производительности. 75
3.2.2. Оценка специфических особенностей алгоритмов планирования 77
3.3. Параметризация предметной области 83
3.4. Характеристики задачи планирования 86
3.5. Экспериментальный анализ производительности сравниваемых алгоритмов 87
3.6. Выбор алгоритма планирования с позиций теории исследования операций 93
3.7. Формирование критериев эффективности алгоритма 97
3.8. Концепция системы выбора оптимального алгоритма 103
3.9. Выводы , 104
4. АПРИОРНЫЙ ВЫБОР ОПТИМАЛЬНОГО АЛГОРИТМА РЕШЕНИЯ ЗАДАЧИ ПЛАНИРОВАНИЯ 106
4.1. Анализ задачи априорного выбора 106
4.2. Критерий отбора доступной информации 106
4.3. Оценка значения критерия эффективности 109
4.4. Построение канонических регрессионных моделей ПО
4.5. Применение средств анализа данных на основе искусственных нейронных сетей 114
4.6. Использование регрессионных моделей для выбора оптимального алгоритма 120
4.7. Выводы 124
5. ЭКСПЕРТНАЯ СИСТЕМА ВЫБОРА ОПТИМАЛЬНОГО АЛГОРИТМА ПЛАНИРОВАНИЯ И ЕЕ ПРАКТИЧЕСКОЕ ПРИМЕНЕНИЕ 126
5.1. Примененимость выбора оптимального алгоритма в прикладньгх системах 126
5.2. Анализ требований к системе выбора оптимального алгоритма планирования 127
5.3. Особенности практической реализации 128
5.4. Использование системы выбора алгоритма планирования для управления комплексной вычислительной средой 130
5.4.1. Задача управления комплексной вычислительной средой 130
5.4.2. Моделирование предметной области 134
5.4.3. Архитектура системы управления вычислительной средой 137
5.4.4. Оценка эффективности 138
5.5. Выводы 141
ЗАКЛЮЧЕНИЕ 143
ПРИЛОЖЕНИЕ 1. АКТ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИИ В КОРПОРАЦИИ XEROX 145
ПРИЛОЖЕНИЕ 2. АКТ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИИ В КОРПОРАЦИИ EDS 154
ПРИЛОЖЕНИЕ 3. АКТ ВНЕДРЕНИЯ РЕЗУЛЬТАТОВ ДИССЕРТАЦИИ В САНКТ-ПЕТЕРБУРГСКОМ ГОСУДАРСТВЕННОМ ПОЛИТЕХНИЧЕСКОМ УНИВЕРСИТЕТЕ 163
СПИСОК ЛИТЕРАТУРЫ 165
Введение к работе
Решение значительного числа научных и технических задач не может быть выполнено за один или несколько очевидных шагов. Причиной этого может быть, например, большое число разнообразных условий и ограничений, неполная информация о предметной области, множество используемых параметров. Одним из наиболее распространенных способов решения таких сложных задач является построение плана — упорядоченного набора несложных действий, последовательное выполнение которых обеспечивает достижение поставленной цели.
Автоматизация такого рода деятельности относится к области исследования и разработки интеллектуальных систем. В настоящее время понятие интеллектуальной системы широко используется, причем зачастую в различных смыслах, в научных, технических и маркетинговых целях, в частности, в ряде случаев интеллектуальные системы отождествляются с экспертными системами искусственного интеллекта (понимаемыми, правда, в достаточно широком смысле). В данной работе под интеллектуальной системой понимается техническая система, реализованная на основе концепций искусственного интеллекта, и, следовательно, обладающая способностью воспроизведения отдельных функций творческой деятельности человека. К подобным функциям в первую очередь относятся сбор, представление и использование знаний, анализ информации и принятие решений, а также планирование деятельности. Интересной особенностью является тот факт, что с одной стороны системы планирования сами по себе являются разновидностью интеллектуальных систем, а с другой стороны они являются одним из основных факторов, определяющих функциональность других интеллектуальных систем. Поэтому вопросы, связанные с изучением проблемы построения планов как важной составляющей теории решения задач, занимают одно из ведущих мест в исследованиях по тематике искусственного интеллекта.
Следует отметить, что в последние годы интерес к исследованиям в области планирования действий значительно возрос. Это объясняется, с одной стороны, экспоненциальным ростом мощности вычислительных систем и одновременным падением стоимости самого оборудования, что обеспечивает его широкую доступность, а с другой стороны, расширением области применения научных результатов путем решения качественно новых задач. Наиболее ярко подобная ситуация проявляется в тех сферах, где применяются информационные технологии, развитие которых стимулирует появление таких классов задач, как сбор и обработка слабоструктурированной информации, распределенной по источникам с различной внутренней архитектурой, разными способами доступа. Одним из основных факторов эффективного решения перечисленных задач является использование методов теории планирования.
Несмотря на значительный прогресс, достигнутый в области систем и алгоритмов планирования, текущее состояние характеризуется двумя особенностями:
1. В общем случае вычислительная сложность нахождения плана остается достаточно высокой- Несмотря на непрерывно растущую производительность вычислительной аппаратуры, усложнение решаемых задач за счет повышения насыщенности сред и увеличение длины генерируемых планов налагает весомые ограничения на практическую применимость данного подхода.
2. К настоящему времени было разработано достаточно большое число развитых алгоритмов планирования, причем с каждым годом их становится все больше и больше. При этом ни один из известных алгоритмов не является ярко выраженным лидером, более того, результаты сравнительных тестов показывают значительные изменения соотношения от задачи к задачи.
При этом основной областью применения технологий планирования является подмножество интеллектуальных систем, известное как интеллектуальные агенты, В первой главе данной работы проводится формальный анализ концепции ИА, которые определяются как интеллектуальные программные роботы, обладающие такими свойствами как автономность, реактивность, целеустремленность и коммуникативность- При этом целеустремленность (способность агента к активным действиям, направленным на достижение поставленной цели) определяет необходимость планирования деятельности агента, а автономность обуславливает локальную реализацию подсистемы планирования, а также ограниченность доступных вычислительных ресурсов.
Анализ известных научных работ по тематике планирования позволяет выделить ряд областей, непосредственно влияющих на эффективность применения систем планирования при разработке интеллектуальных агентов, которым не было уделено должного внимания:
- методы анализа и сравнения производительности алгоритмов планирования;
- исследование зависимости производительности алгоритма планирования от типа предметной области и задачи планирования;
- оптимизация процесса планирования.
Перечисленные факторы определяют цель диссертационной работы: создание научно обоснованной системы методов и средств для эффективного планирования действий интеллектуальных агентов. Для достижения поставленной цели необходимо решить следующие задачи:
1. Выполнить анализ текущего состояния и направлений развития систем планирования действий в искусственном интеллекте и выделить наиболее перспективные подходы к их совершенствованию,
2. Построить унифицированное формализованное представление процесса построения плана действий и определить множество альтернатив, состоящее из потенциально оптимальных алгоритмов планирования.
3. Разработать комплексный подход к сравнительному анализу алгоритмов построения планов действий.
4. Сформировать критерии оптимальности алгоритма планирования и определить принципы динамического выбора алгоритма эффективного планирования действий интеллектуальных агентов,
5. Разработать методы динамического выбора алгоритмов эффективного планирования действий интеллектуальных агентов.
6. Построить прототип экспертной системы для динамического выбора алгоритмов эффективного планирования действий и подтвердить целесообразность использования предложенного инструментария.
Научная новизна диссертационной работы заключается в следующем: L Проведена формализация процесса нелинейного планирования в системах искусственного интеллекта и доказан общий случай теоремы о систематичности уточнения частичного плана с использованием двусторонней защиты казуальных связей,
2. Построен базис пространства нелинейных алгоритмов, позволяющий производить синтез новых конкурентоспособных алгоритмов планирования, не требующий низкоуровневой разработки функциональных модулей программного обеспечения.
3. Предложена расширенная система показателей для анализа качества функционирования интеллектуальных агентов на этапе генерации плана действий, впервые определены способы формирования критериев оптимальности алгоритма планирования и принципы его динамического выбора.
4. Впервые решена задача регрессионной оценки значений показателей качества алгоритмов планирования действий интеллектуальных агентов и предложен способ снижения сложности регрессионной модели с сохранением точности результатов за счет введения критерия отбора значимой информации.
5. Разработаны методы априорного динамического выбора оптимального алгоритма построения планов действий интеллектуальных агентов на основании анализа известной информации о среде функционирования агента, типе и условиях задачи планирования» повышающие эффективность их действий.
6. Определены функциональные спецификации и архитектура экспертной системы, обеспечивающей автоматизацию динамического выбора эффективных алгоритмов планирования действий интеллектуальных агентов.
Практическая исследования состоит в том, что полученные результаты могут быть использованы для повышения качества функционирования интеллектуального программного обеспечения» основанного на построении планов действий. Экспериментально продемонстрированные преимущества предложенных методов позволяют рекомендовать их применение для проектирования нового поколения интеллектуальных агентов. Созданный прототип нейросетевой экспертной системы представляет собой программную реализацию готового инструментария для разработки и совершенствования интеллектуальных агентов. Практическая значимость подтверждена успешным внедрением результатов исследования в процесс сопровождения вычислительной инфраструктуры, используемой корпорациями Xerox и EDS, Материалы диссертационной работы внедрены в учебный процесс кафедры автоматики и вычислительной техники СПбГПУ, Представленные внедрения подтверждены соответствующими актами.
Диссертационная работа состоит из введения, пяти глав и заключения. В первой главе анализ концепции интеллектуальных агентов, определение задачи планирования и обзор существующих методов построения плана действий. Вторая часть первой главы содержит обзор известных подходов к построению экспертных систем и анализ их потенциальности применимости для решения задачи выбора оптимального алгоритма планирования.
Вторая глава посвящена детальному анализу класса нелинейных алгоритмов планирования. Представленные теоретические результаты предоставляют необходимый фундамент для сравнительного анализа алгоритмов планирования, а также позволяют сформировать обобщенный алгоритм планирования и определить базис пространства нелинейных алгоритмов.
В третьей главе определяются необходимые средства для сравнительного анализа алгоритмов планирования, такие как расширенная система показателей качества алгоритма планирования, набор характеристик предметной области и задачи планирования. Также приводятся экспериментальные результаты сравнения алгоритмов в соответствии с предложенной методикой, определяются принципы оптимальности алгоритма с использованием теории исследования операций, выдвигается концепция системы априорного выбора оптимального алгоритма планирования,
В четвертой главе сформулированы статистические критерии отбора информации, а также разработаны методы выбора алгоритма на основе априорной оценки эффективности с использованием классических регрессионных моделей и искусственных нейронных сетей. Также приведены экспериментальные данные, демонстрирующие преимущество предлагаемого подхода над альтернативными стратегиями выбора алгоритма планирования Пятая глава посвящена вопросам применения разработанного подхода в прикладных задачах- В ней определены необходимые условия применимости, приведено описание прототипа экспертной системы для автоматизированного априорного определения локально оптимального алгоритма и результаты применения прототипа в системе управления гетерогенными вычислительными ресурсами.
Основные результаты диссертации представлялись на международных, всероссийских и региональных конференциях, включая III международную научно-техническую конференцию "Новые информационные технологии и системы" (Пенза, 10-11 декабря 1998 г.), молодежную научно-техническую конференцию «Наукоемкие технологии и интеллектуальные системы 2001», (Москва, 21 -22 марта 2001 г.), VII международную конференцию «Информационные сети, системы и технологии» (Минск, 2-4 октября 2001 г.), научную конференцию студентов и аспирантов «XXX Юбилейная неделя науки СПбГТУ» (Санкт-Петербург, 26 ноября - 1 декабря 2001 г.), V международную конференцию по мягким вычислениям и измерениям (Санкт-Петербург, 25-27 июня 2002 г.), II и III Всероссийские научно-технические конференции «Прикладные и теоретические вопросы современных информационных технологий» (Улан-Уде, 18 - 22 сентября 2001 г. и 30 июля - 6 августа 2002 г,), Международную конференцию «Информационные технологии в образовании, технике и медицине» (Волгоград, 24-26 сентября 2002 г,)- По теме диссертационной работы сделано 11 публикаций.
