Содержание к диссертации
Введение
1. Методы и системы интеллектуального планирования 10
1.1. Классическое планирование 13
1.2. Частично упорядоченное планирование 18
1.3. Планирование с использование графов планирования 20
1.4. Иерархическое планирование 22
1.5. Планирование как задача удовлетворения ограничений 26
1.6. Эвристическое планирование 28
1.7. Условное планирование 30
1.8. Согласованное планирование 31
1.9. Стохастическое планирование 32
1.10. Планирование с обучением 34
1.11. Гибридное планирование 35
1.12. Практическое планирование 36
1.13. Выводы по главе и постановка задач исследования 42
2. Модели предметной области и проблемной ситуации планирования 45
2.1. Модель предметной области планирования 46
2.1.1. Описание задач предметной области 46
2.1.2. Описание концептов 74
2.1.3. Описание правил вывода фактов 79
2.2. Модель проблемной ситуации планирования 79
2.2.1. Описание объектов проблемной ситуации 81
2.2.2. Представление планов 83
2.2.3. Описание ограничений проблемной ситуации 84
2.3. Выводы по главе 86
3. Методы планирования и анализа сложноструктурированных ситуаций 88
3.1. Алгоритм метода планирования 88
3.2. Анализ ситуаций 93
3.3. Выводы по главе 98
4. Экспериментальные исследования планирующей системы 100
4.1. Методика описания предметных областей и проблемных ситуаций планирования 100
4.2. Система автоматизированного проектирования технологических процессов свободной ковки на прессах 107
4.3. Система автоматизированного планирования маркетинговых исследований 126
4.4. Выводы по главе 133
Заключение 135
Литература 137
- Иерархическое планирование
- Практическое планирование
- Описание задач предметной области
- Алгоритм метода планирования
Введение к работе
В настоящее время методы интеллектуального планирования находят широкое применение в медицине, космонавтике, авиастроении, производстве, военном деле, программировании, робототехнике, компьютерных играх и интернет-технологиях.
Значительный вклад в развитие теоретических исследований и практических разработок в сфере интеллектуального планирования внесли как зарубежные исследователи: Fikes R.O. (США), Ghallab М.(Франция), Kambhampati S. (США), Kautz Н. (США), McAHester D.A. (США), Nau D.S. (США), Nilsson N.J. (США), Rosenblit D. (США), Sacerdoti E.D. (США), Tate А. (Великобритания), Traverso P. (Италия), Weld D.S. (США), Wilkins D.E. (США), так и отечественные ученые: Аверкин А.Н., Поспелов Д.А., Осипов Г.С., Стефанюк В.Л., Ефимов Е.И., Алиев Р.А., Кузин Е.С.
За более чем тридцать лет существования систем планирования задач, как одного из направлений искусственного интеллекта, были разработаны десятки методов синтеза планов. Опыт использования таких систем показывает, что наиболее эффективными планирующими системами, применяемыми в практических задачах, являются иерархические (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, использующего декомпозиционные шаблоны в описании методов решения задач.
Автор выражает свою благодарность к.т.н., доценту кафедры «Машины и технология обработки металлов давлением» Ижевского государственного технического университета Морозову С.А. за помощь в проведении экспериментальных исследований предложенного метода на примерах синтеза технологических процессов свободной ковки поковок на прессах.
Аннотация работы по главам. В первой главе диссертационной работы приведен обзор существующих методов и систем интеллектуального планирования. В выводах по главе обобщены недостатки предмета исследования и поставлены задачи диссертационного исследования.
Вторая глава посвящена описанию моделей предметной области и сложно структурированной проблемной ситуации планирования. Предлагается новый компактный способ описания декомпозиций задач. Рассмотрены типовые случаи использования декомпозиций задач и способы их описания с помощью декомпозиционных шаблонов.
В третьей главе описываются алгоритмы методов планирования и анализа сложно структурированной ситуации. Предлагаются подходы для разрешения тупиковых ситуаций в случаях, когда план решения проблемной ситуации не был найден. Описан способ представления информации в логике предикатов первого порядка для описания сложно структурированных объектов предметной области.
В четвертой главе описываются две системы, в состав которых включена разработанная планирующая система, использующая описанный в данной работе метод иерархического планирования. Первая система - это система автоматизированного проектирования технологических процессов свободной ковки поковок на прессах, а вторая - система автоматического планирования маркетинговых исследований. Приведены две методики описания планируемых задач и сложно структурированных объектов проблемной ситуации планирования. Изложены результаты экспериментальных исследований, проведенных в рамках реализованных систем.
В заключении работы приведена ее общая характеристика и основные выводы по полученным результатам исследования.
Иерархическое планирование
Существенный прорыв в интеллектуальном планировании (AI Planning) совершили методы иерархического планирования (Hierarchical Task Network Planning) [25,83]. Одним из отличий иерархического планирования является то, что планы состоят из задач, а не действий. Поэтому иерархическое планирование еще называют планированием задач. Основу методов иерархического планирования составляет, описанная экспертом, иерархия задач (пространство задач) (HTN - Hierarchical Task Network).
HTN-планирование делит задачи на простые (simple, primitive task) и сложные (complex task). Сложные задачи могут решаться различными способами - методами. Каждый метод (method) описывает решение сложной задачи как частично упорядоченной или строго упорядоченной последовательности подзадач, которые ,в свою очередь, могут иметь свои методы решения [122,133,141]. В качестве цели планирования для таких планирующих систем задается одна из сложных задач или их последовательность.
Решение простой задачи у исполнителя не вызывает затруднений, а сложные задачи могут решаться различными способами - методами. Как правило, описания простых задач в методах иерархического планирования не отличаются от описаний действий классического планирования, хотя предусловия простых задач могут отсутствовать в случае использования строго упорядоченной декомпозиции задач. Метод решения сложной задачи представляет собой декомпозицию (decomposition) сложной задачи, как последовательности подзадач, выполнением которых решается сложная задача.
Для наглядного представления иерархии задач обычно используют И-ИЛИ графы (AND-OR graph). ИЛ И-вершины которого представляю сложные задачи, а И-вершины методы решения сложных задач. Этот граф также используется иерархическими алгоритмами планирования для поиска планов, И-ИЛИ граф задач может содержать циклы, что усложняет процесс синтеза планов. Поиск плана на данном графе называют поиском в пространстве задач, В иерархиях И-ИЛИ графа имеется чередование вершин задач и вершин методов.
Планы иерархических методов планирования содержат только простые задачи, но иногда для пояснения пользователю предлагается иерархический план. Иерархический план представляет собой дерево, вершиной которого является цель планирования, а листьями - простые задачи. В некоторых случаях данное дерево может быть подграфом исходного И-ИЛИ графа. Иерархическая планирующая система рекурсивно, используя описания методов, осуществляет декомпозицию задач, до тех пор, пока не построит дерево решения, листья которого будут представлять план решения проблемной ситуации [84,133,141].
Планы, создаваемые иерархическими планирующими системами, более понятны пользователю, т.к. их планы могут быть представлены в виде иерархии. Иерархия задач позволяет увидеть план, состоящий из простых задач, в виде более крупных задач, которые постепенно детализируются.
Планирующая система SHOP2 создает каждый шаг плана в том порядке, в котором они потом будут исполняться. Поэтому данной планирующей системе полностью известно состояние среды планирования на каждом шаге процесса синтеза плана. Данная система на IPC в 2002 году получила одну из четырех наград за продемонстрированную эффективность ее алгоритма. В данной системе имеется возможность использования темпоральных рассуждений [53,61] в процессе поиска плана.
Система СФИНКС (Система Формального Интеллекта Комплексных Стратегий) [21] является разработкой отечественной школы иерархического планирования.
Иерархические планирующие системы нашли широкое применение в промышленных системах и демонстрируют отличные результаты. Хотя для успешного функционирования иерархической планирующей системы инженер по знаниям должен обладать высокой квалификацией. Он должен минимизировать количество методов решения сложных задач предметной области и увеличить количество задач в декомпозициях методов. Также он должен избегать рекурсивных декомпозиций задач, которые относят задачу иерархического синтеза планов к классу NP-полных задач [55,85].
Большинство исследователей рекомендует избегать применения рекурсивных декомпозиций задач в иерархическом планировании. Аргументируют они это тем, что в редких предметных областях на самом деле требуется рекурсия. Существует два способа избавления от рекурсивных декомпозиций: 1. Эксперт предлагает сделать сложную задачу, описанную с помощью рекурсивной декомпозиции, простой задачей. Таким образом, эксперт поручает решение о том как задачу исполнять агенту, а не планирующей системе. Это может привести к тому, что планирование станет бессмысленным, когда множество сложных задач станет практически пустым. 2. Сначала эксперт исследует каждую рекурсивную декомпозицию на типовых проблемных ситуациях. Таким образом, он определяет самую длинную последовательность задач, порожденную рекурсивной деком-позицей. Если длина такой последовательности равна п, то эксперт создает п методов решения сложной задачи, описанной ранее с помощью рекурсивной декомпозиции. Каждый г -ый метод содержит декомпозицию из последовательности задач длиной г. В нестандартных проблемных ситуациях планирующие системы, использующие такие описания, не способны синтезировать планы.
Практическое планирование
Планирующие системы делятся на два крупных класса. - Универсальные планирующий системы (domain independent planning systems). У таких планирующих систем существуют язык, с помощью которого эксперт может описать предметную область и проблемную ситуацию планирования. Сам алгоритм такой системы не подвергается изменению при его использовании для планирования в различных предметных областях. - Ориентированные на конкретную предметную область (domain dependent planning systems). В таких планирующих системах в алгоритм синтеза плана зашиты знания о предметной области. Второй вид планирующих систем эффективен в сравнении с первым, но не обладает гибкостью в представлении знаний о предметной области. Знания о предметной области планирования постоянно меняются, и такой вид планирующих систем трудно приспособить для решения задач в других предметных областях. Как правило, приложениями интеллектуального планирования являются промышленные системы, которые содержат подсистемы планирования привязанные к конкретной предметной области. Существуют специальные инструменты для создания планирующих систем с привязкой на предметную область. Для этого требуется описание предметной области планирования и универсальная планирующая система. Для работы универсальных планирующих систем инженеру по знаниям необходимо выполнить описание следующей информации: 1) предметной области планирования: а) классов объектов предметной области планирования; б) видов отношений между классами объектов; в) константных объектов; 2) проблемной области планирования: а) множества объектов, которые могут быть использованы для дости жения цели планирования или могут на нее повлиять; б) начального состояния среды планирования; в) цели планирования; г) ограничений, которым должен удовлетворять план. В 1998 году был разработан универсальный язык описания предметных областей и проблемных ситуаций планирования для большинства видов планирующих систем PDDL (Planning Domain Definition Language) [92,93]. В силу того, что каждый планировщик умеет работать только с определенной информацией, в данный язык были введены описания требований к планирующей системе, которая сможет воспользоваться описаниями предметной области и проблемной ситуацией планирования. Язык PDDL используется в международных соревнованиях планирующих систем IPC (International Planning Competitions), которые проводятся раз в два года в рамках международной конференции по автоматическому планированию и составлению расписаний ICAPS (International Conference on Automated Planning and Scheduling). Данные соревнования планирующих систем проводятся с 1998 года. Синтаксис языка PDDL во многом схож с синтаксисом функционального языка программирования LISP [65,66]. Следует отметить, что большинство планирующих систем реализовано на языке LISP. Не является исключением и первая планирующая система STRIPS. Язык системы STRIPS послужил одним из прототипов данного языка описания предметных областей. Как правило, планирующие системы сначала реализуются на языке LISP, а затем, после прохождения исследовательского этапа системы, создаются более эффективные реализации на компилируемых процедурных или объектно-ориентированных языках программирования. В описании среды планирования также могут использоваться различные методы представления знаний: логические, продукционные, семантические сети, фреймы и онтологии [12,30]. Для наглядного представления планов на практике могут использоваться различные графические представления и диаграммы, в том числе временные [147]. Например планирующая система BURIDAN содержит программу для визуального просмотра планов VCR. Существуют инструменты трехмерной визуализации планов, созданных иерархическими планирующими системами [113]. Первые системы планирования в основном ориентировались на абстрактные проблемы, которые были далеки от практики. Например, создавали планы для мира кубиков. Данные предметные области используются до сих пор в соревнованиях планирующих систем и служат тестовой базой для дальнейшего практического воплощения планирующих систем. Приведем наиболее яркие примеры применения планирующих систем. 1. Экспертная система планирования (ЭСПЛАН) [3] предназначена для построения планов производства нефтепродуктов. Система использует нечеткие рассуждения, что позволяет системе учитывать опыт специалистов плановых служб предприятия. У системы имеется свой собственный продукционный язык описания предметной области планирования. Данная система является частью автоматизированной системы управления предприятием Новобакинского нефтеперабатывающего завода и используется для составления планов производства различных нефтепродуктов, на основе имеющегося сырья и технологических установок. Система реализована на языке Пролог [9,29,58]. 2. Планирующая система RAX-PS (Remote Agent Experiment Planner Scheduler) [107] использовалась на борту аппарата Deep Space One. Она в течении недели осуществляла синтез планов для управления ионной двигательной установкой, предназначенной для корректировки курса и ориентации аппарата в пространстве. 3. Система О-Plan используется в составлении планов перевозки грузов самолетами, проектирования и строительства домов, а также для управления проектами (project managing) [78,142]. Эта же система была использована в компании Hitachi для синтеза производственных планов. Синтез планов осуществлялся в проблемных ситуациях с 350 различными изделиями, 35 сборочными установками с использованием более двух тысяч двухсот различных операций. Некоторые планы содержали до миллиона операций, охватывающие месячный план производства изделий в три рабочие смены [70].
Описание задач предметной области
В случае успешной проверки предусловия задачи task осуществляется унификация [44,45] предусловия задачи с ее параметрами Parameters(tasк). Атрибуты задачи представляют собой либо переменные (11), либо константы (10), либо вычисляются с помощью функций (9). В процессе планирования атрибуты задач, в отличии от параметров, не унифицируются.
Множество атрибутов позволяет определить различные свойства задачи, которые могут быть использованы в оценке созданного плана. Так для оценки трудоемкости плана необходимо в атрибуты задачи ввести нормировочные коэффициенты. Трудоемкость плана будет складываться из трудоемкостей задач, входящих в него. Тоже самое можно сказать об атрибутах, характеризующих сложность и качество плана. При создании плана можно указать ограничения по трудоемкости, сложности и качеству плана. Планирующая система, если решения были найдены, выдаст оптимальный план, удовлетворяющий заданным ограничениям.
Множество Agents задает классы (профессии) агентов [50,83], которые могут выполнить данную задачу. В качестве агентов могут быть автоматы, программы и люди. Например, задача «Установка программы» должна выполняться агентом «Администратор» в предметной области «Администрирование операционной системы». Предусловия и ограничения задачи могут содержать дополнительные требования к агентам.
Такие задачи, как «отпилить», «обрубить», «ударить молотком по гвоздю» и т.п., являются простыми для предметной области «Плотницкие работы».
Сложные задачи. При решении сложной задачи перед планирующей системой встает задача выбора: каким из имеющихся в распоряжении способов задачу выполнить. Сложные задачи не могут быть исполнены агентами предметной области непосредственно. Планировщик должен решать как их исполнять в условиях конкретной ситуации. Сложная задача t Є ComplexTasks может решаться в рамках предметной области различными способами- методами. Как правило, метод описывает решение сложной задачи как решение строго упорядоченной или частично упорядоченной последовательности задач. Эти последовательности могут содержать простые и сложные задачи.
Множество методов Methods [38,125] в описании предметной области domain содержит различные способы решения сложных задач предметной области. Сложные задачи могут иметь несколько методов решения, которые могут быть применены в различных условиях и давать различные результаты после их исполнения.
Каждый метод т Methods описывает решение одной из сложных задач и представляет собой следующую пятерку: т = (task, precondition, decomposition, Attributes, Constraints), где task Є ComplexTasks - наименование задачи, решение которой описывается данным методом; precondition - предусловие метода, описываемое грамматикой (3 - 13); decomposition - шаблон, описывающий множество декомпозиций [48] задачи task; Attributes - множество атрибутов (22), описывающих метод (параметры сложной задачи, связанной с методом; надежность; качество; длительность и т.п.); Constraints - формула (3 -13), описывающая ограничения применимости метода в текущей планируемой ситуации. Предусловие метода описывает ситуацию, в которой он может быть применен. Как и в случае простых задач формула, описывающая предусловие метода, может содержать логические связки: «И», «ИЛИ» и «НЕ». Подмножество атрибутов Attributes метода содержит параметры сложной задачи, которые можно определить с помощью формулы (24). Сложная задача может иметь различное количество параметров, что достигается за счет применения методов в описании сложных задач. Эффект метода и связанной с ним сложной задачи определяется эффектами задач, входящих в его декомпозицию. Эффекты множества методов Methods(task) = {(task, d, р, At, Ад, С) Є Methods} одной сложной задачи task безусловно имеют общую составляющую, которая и содержит назначение задачи. Тем не менее каждый из методов имеет свою специфическую составляющую, которая и характеризует этот метод с положительных и отрицательных сторон. Чтобы не перегружать предусловие метода проверками различных ограничений, используется формула Constraints (3- 13). Данная формула осуществляет только проверку ситуации, т.к. она не унифицируется с параметрами метода в отличии от предусловия метода.
Декомпозиция задачи, заданная методом, описывает последовательность задач Seq = Tasks , необходимых для решения задачи task. Каждая из возможных декомпозиций или все декомпозиции задачи task могут быть заданы декомпозиционным шаблоном метода.
Алгоритм метода планирования
Алгоритм планирования осуществляет планирование задач в том порядке, в котором задачи будут исполняться агентами, присутствующими в проблемной ситуации. Каждый раз, выбирая очередную задачу из текущей проблемной ситуации, алгоритм рассматривает два случая.
В первом случае рассматриваемая задача является простой. Тогда планировщик проверяет предусловие задачи. Если проверка предусловия задачи прошла успешно, то задача включается в текущий план с назначением ей исполнителей. Если предусловие задачи не соответствует текущей ситуации, то данный вариант построения плана исключается из рассмотрения (выполняется откат) и помещается в список тупиковых ситуаций.
Во втором случае рассматриваемая задача является сложной. Тогда данную задачу необходимо редуцировать с помощью одного или нескольких методов, предусловия которых истинны в текущей проблемной ситуации и которые описывают редукцию этой задачи. Таким образом, дерево поиска пополняется альтернативными способами решения данной задачи.
Если декомпозиционный шаблон построен с использованием кванторов типа гпс quantifier (см. формулу (32)), то алгоритм планировщика использует стратегию поиска в ширину при обходе и построении вершин дерева решения, соответствующих данному декомпозиционному шаблону. Если декомпозиционный шаблон построен с использованием кванторов типа dec quantifier (см. формулу (33)), то алгоритм планировщика использует стратегию поиска в глубину при обходе и построении вершин дерева решения, соответствующих данному декомпозиционному шаблону. Если были использованы декомпозиционные шаблоны с кванторами типа cut quantifier (см. формулу (34)) в очередном найденном алгоритмом плане, то алгоритм удаляет альтернативные поддеревья решений, в построении которых использовались данные декомпозиционные шаблоны, найденного плана. Если декомпозиционный шаблон построен с использованием квантора star quantifier (см. формулу (35)), то алгоритм использует в синтезе фрагмента плана поиск в пространстве состояний.
Алгоритм вполне стандартен для планирующих систем, осуществляющих поиск в пространстве задач, но имеет некоторые отличительные черты. Во-первых, это разбор декомпозиционных шаблонов и построение дерева поиска на их основе. Во-вторых, данный алгоритм пытается создать план, когда на заданном описании задач предметной области или описании проблемной ситуации решение не найдено. Для этого планировщик ведет запись всех точек отката. Если все возможные варианты опробованы и план не найден, то планировщик сортирует все тупиковые ситуации, в которых произошел откат, по перспективности их разрешения. Данная возможность алгоритма будет рассмотрена в следующем параграфе данной главы.
В процессе выбора адекватного метода или задачи в текущей ситуации планировщику необходимо проанализировать все имеющиеся факты ситуации и ограничения потенциальных методов и задач, которые могут быть использованы для решения проблемной ситуации. Для этого описания методов и задач должны наиболее полно описывать ситуации и ограничения их применения. Перед тем как выбрать метод вычисления атрибута объекта, присутствующего в проблемной ситуации, планировщик осуществляет вычисление всех необходимых фактов, на основе логического вывода, для оценки применимости метода.
Семантика ситуаций заключается в том, что в них отображаются множества предметов сцены, множества действий и множества участников. Все эти множества разбиты в деревья классов и связанных различными классами отношений. Использование такого способа облегчает описание объектов и позволяет применять данньїе описания для решения задач, не связанных с планированием [33]. Для определения некоторого факта объекта может потребоваться рекурсивное вычисление фактов для его подобъектов.
В процессе синтеза плана и вывода фактов планирующая система осуществляет преобразование описания концептов предметной области и объектов проблемной ситуации в описания, использующие логику предикатов первого порядка [4,16,17]. Для этого осуществляются следующие преобразования:
