Планирование задач в сложноструктурированных ситуациях

• Автор: Габдрахманов, Ильшат Накипович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Ижевск
• Количество страниц: 180 с. : ил.

СОДЕРЖАНИЕ
ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

1.9. Стохастическое планирование.
1 Планирование с обучением.
1 Гибридное планирование.
1 Практическое планирование
1 Выводы по главе и постановка задач исследования
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. Выводы по главе
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


В чистом классическом планировании изменения представляют собой упорядоченные множества добавлений и удалений предикатов из состояния среды планирования. Первой планирующей системой, в которой выполнялся синтез последовательности действий, является STRIPS (Stanford Research Institute Problem Solver) [,]. В основе системы STRIPS был использован метод анализа средств и целей(МЕА - Means-Ends Analysis), который был впервые использован в универсальном решателе задач (GPS - General Problem Solver) [6]. Система STRIPS имела свой язык описания среды планирования и предназначалась для использования в проекте Shakey [1], который представлял собой робот, умеющий переносить предметы из одних помещений в другие. STRIPS. Система STRIPS в процессе направленного поиска плана использует пространство состояний (state space). STRIPS осуществляет выбор действий, двигаясь от целевого состояния к начальному, с помощью метода анализа средств и целей, а создание плана осуществляется от начального состояния. Целевое состояние (goal state) представляет собой конъюнкцию равноправных подцелей (subgoals). В основе метода анализа средств и целей лежит выбор ветви поиска, посредством анализа различий между текущим и желаемым состоянием. Для этого система GPS использовала таблицу различий (difference table), а система STRIPS - списки добавлений и вычеркиваний действий. Система STRIPS в выборе релевантного действия в текущем состоянии использует метод резольвенций. Теоремами для логического вывода служат предусловия действий, а аксиомами - факты текущего состояния среды планирования. Хотя система STRIPS не осуществляет полный перебор пространства состояний, ее эффективность очень низка. Реальные планы создаваемые системой могут состоять из небольшого количества действий. Это связано с тем, что синтез планов с использованием классических методов планирования относится к PSPACE-сложным задачам. Авторы системы STRIPS через год представили новую модификацию системы, которая позволяла строить обобщенные планы (lifting plans) для повторного использования полученных планов []. Для представления обобщенных планов использовались треугольные таблицы, которые также служили для проверки корректности исполнения плана. Изначально система STRIPS создавала планы, действия которых содержали, в качестве параметров, конкретные объекты и константы. Обобщенные планы содержат действия, параметрами которых являются переменные. Система ПРИР (система принятия решений интегрального робота) [] использует метод анализа средств и целей. Для описания действий системы используется порождающая грамматика. План представляет собой одно из правильных предложений, построенных на основе описанной пользователем грамматики. Зарубежные исследователи практически не используют явно такой аппарат математической лингвистики в представлении задач планирования, но указывают на возможность его применения. Еще одна отечественная система АЛПЕВ [] использует в поиске решений ситуационное исчисление (situation calculus) [9], которое является одним из формализмов, используемых в интеллектуальном планировании. Классические методы планирования характеризиуются PSPACE - сложностью []. Планирующие системы данного класса страдают от комбинаторного взрыва. На практике такие планирующие системы не могут создавать планы длиной более - действий. Для разрешения этой проблемы предпринималось не мало попыток, но применение на практике этих методов до сих пор невозможно. Планирующая система ABSTRIPS для решения этой проблемы использует иерархию абстрактных пространств поиска. Что позволяет системе на каждом уровне абстракции отделять важную информацию от несущественной. Данная планирующая система осуществляет синтез плана последовательно. Сначала она строит максимально абстрактный план. Затем последовательно (рекурсивно) полученный план детализируется. Детализация иерархии абстракций выполняется на основе назначения литералам предусловий действий рангов и значений критичности. В ранних системах планирования (STRIPS, HACKER и др. Это допущение говорило о том, что подцели необходимо достигать последовательно.