Исследование методов и разработка алгоритмов планирования и моделирования целенаправленного поведения Тарханов Тимур Сейфединович

Содержание к диссертации

Введение

Глава 1. Методы интеллектуального планирования 10

1.1. Введение... 10

1.2. Хронология подходов интеллектуального планирования при классических допущениях 12

1.3. Планирование как доказательство теорем 14

1.4. Поиск в пространстве состояний 15

1.4.1. Постановка задачи STRIPS-планирования 16

1.4.2. Алгоритм STRIPS 19

1.4.3. Неполнота алгоритма STRIPS. Аномалия Суссмана 20

1.4.5. Вычислительная сложность задачи STRIPS-планирования 23

1.4.6. Языковые средства описания доменов планирования 26

1.5. Поиск в пространстве планов 27

1.5.1. Основная идея 27

1.5.2. Основные определения 28

1.5.3. Алгоритм SNLP 31

1.5.4. Принцип малой связности 32

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

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

1.6.2. Синтез планов на основе техники прямого распространения оіраничений 34

1.6.2.1. Основные определения

1.6.2.2. Алгоритм Graphplan 40

1.7. Выводы 44

Глава 2. Синтез планов на основе преобразования взаимовлияний действий 45

2.1. Введение... 45

2.2. Постановка задачи 48

2.3. Прогрессивная и регрессивная модели среды 52

2.4. Взаимовлияние дейстпий: конфликты и согласия 56

2.5. Преобразования 59

2.5.1. Преобразование последовательностей действий 59

2.5.2. Преобразование взаимовлияний 61

2.6. Минимальные планы. Бесполезные действия 63

2.7. Синтез планов на основе разрешения конфликтов...74

2.7.1. Планирование на основе преобразования взаимовлияний 74

2.7.2. Планирование на основе полного разрешения конфликтов 75

2.7.3. Планирование за конечное время 80

2.8. Эффективность алгоритма TCRPA...84

2.9. Заключение... 93

Глава 3. Моделирование целенаправленного поведения динамических интеллектуальных систем. 94

3.1. Динамические интеллектуальные системы 94

3.2. Основные определения 98

3.3. Постановка задачи моделирования целенаправленного поведения. 103

3.4. Реализация средств моделирования целенаправленного поведения для динамических интеллектуальных систем... 106

3.4.1. Архитектура инструментальных программных средств 106

3.4.2. Средства представления знаний 108

3.4.3. Средства моделирования динамики и целенаправленного поведения 112

3.5. Выводы... 113

Заключение 114

Литература 115

• Вычислительная сложность задачи STRIPS-планирования
• Синтез планов на основе техники прямого распространения оіраничений
• Планирование на основе полного разрешения конфликтов
• Архитектура инструментальных программных средств

Введение к работе

Актуальность работы

Теория динамических интеллектуальных систем является в настоящее

время интегрирующим базисом различных направлений искусственного интеллекта [18].

Динамические интеллектуальные системы возникают, в частности, при интеграции экспертных систем с системами имитационного моделирования сложных технических (или иных) систем, при создании интеллектуальных систем различного назначения, при решении задач поддержки принятия решений, в клинической деятельности при создании систем поддержки лечебно-диагностического процесса и практически при всех реализациях экспертных систем реального времени [22].

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

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

Тем не менее, можно отметить некоторые успешные разработки в области моделирования целенаправленного поведения:

- система парирования нештатных ситуаций и оптимального управления космического аппарата Deep Space One [108], запущенного NASA в 1998 году. Система основана на классическом алгоритме SAT-планирования [67];

система Optimum-AIV [36], используемая Европейским Космическим Агентством для сборки, компоновки и тестирования космических аппаратов. Система разработана с использованием инструментария O-Plan [101];

система Sipe-2 [107] используется на производственных упаковочных линиях, при этом учитываются производственные и ресурсные ограничения. В основе Sipe-2 лежит алгоритм иерархического планирования.

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

Работа выполнена в рамках следующих проектов:

Тема №01.200.111813 «Исследование дискретных динамических систем, основанных на знаниях».

Тема №01.200.111814 «Создание инструментальных программных средств динамических систем, основанных на знаниях».

Проект Миннауки РФ - ГНТП № 0201.04.334. "Разработка инструментальных программных средств интегрированных интеллектуальных систем для моделирования поведения сложных систем".

Проект РФФИ 00-01-00595 «Планирование поведения в динамических системах, основанных на знаниях».

Комплексная программа научных исследований Президиума РАН «Интеллектуальные компьютерные системы» Проект №2.3. «Инструментальные программные средства динамических интеллектуальных систем».

Мероприятие 20 «Создание инструментальных средств проектирования интеллектуальных систем на базе суперкомпьютера и разработка на их основе универсальной моделирующей среды»

программы Союзного государства «Разработка и освоение в серийном производстве семейства высокопроизводительных вычислительных систем с параллельной архитектурой (суперкомпьютеров) и создание прикладных программно-аппаратных комплексов на их основе» (шифр "СКИФ"), тема № 01.200.111810.

Цель работы

Целью диссертационной работы является исследование существующих

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

Для достижения поставленной цели в работе решаются следующие задачи:

1) разработка языка представления знаний для динамических
интеллектуальных систем;

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

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

Методы исследования

В работе для проведения исследований были использованы методы

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

Научная новизна

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

классических допущениях;

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

Практическая значимость работы

Алгоритм моделирования целенаправленного поведения является

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

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

Апробация работы

Основные результаты работы докладывались и обсуждались на

следующих конференциях и семинарах:

VII национальная конференция по искусственному интеллекту с международным участием КИИ-2000 в г.Переславль (2000);

XXVIII международная конференция "Информационные технологии в науке, образовании, телекоммуникации и бизнесе" IT+SE'2001 в г.Гурзуф(2001);

международный конгресс "Искусственный интеллект в 21 веке" ІСАГ2001 вп.Дивноморск(2001)

семинары Исследовательского центра искусственного интеллекта ИПС РАН (г.Переславль-Залесский).

По теме диссертации опубликовано 6 печатных работ.

Структура и объём работы

Диссертационная работа состоит из введения, трёх глав, заключения и

списка литературы. Общий объём основного текста диссертации — 119 страниц, список литературы содержит 111 наименований. В работе 16 рисунков и 1 таблица.

Содержание работы

В первой главе дана общая характеристика задачи интеллектуального

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

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

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

Даны основные определения и факты теории динамических интеллектуальных систем. Дана постановка задачи моделирования целенаправленного поведения для динамических интеллектуальных систем.

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

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

і Глава 1. Методы интеллектуального планирования

1.1. Введение

Планирование является основой интеллектуального управления, т.е.

управления изменением среды в желаемом направлении [18]. Работы по созданию эффективных алгоритмов синтеза плана уже около 30 лет сохраняют высокую степень актуальности в искусственном интеллекте, что привело в последние годы к появлению достаточно интересных результатов.

В задаче планирования можно выделить две фундаментальные составляющие - среда и агент:

1) Среда. Для построения плана и управления его выполнением

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

2) Агент - аппаратная или программная система, обладающая
следующими свойствами:

автономность — способность работать без внешнего управляющего воздействия;

реактивность - возможность воспринимать среду, реагировать на ее

изменения;

активность - способность ставить цели и инициативно действовать для достижения поставленной цели;

коммуникативность — способность взаимодействовать с другими агентами (или людьми) [110].

Примером интеллектуального агента является софтбот (программный
робот) - система, взаимодействующая с компьютерной средой
посредством выполнения команд и интерпретации результатов команд и

других сообщений среды [69].

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

Сложность задачи синтеза плана зависит от множества свойств среды и агента, в том числе:

1. изменяется ли среда только в результате действий агента или вне зависимости от них;

2. является ли состояние среды полностью или частично известным;

3. достаточно ли датчиков агента для того, чтобы получить состояние среды;

(4) оказывают ли действия агента детерминированное или же
стохастическое воздействие на состояние среды.

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

Трудность разработки эффективного алгоритма планирования объясняется вычислительной сложностью задачи планирования, которая относится к классу PSPACE-полных задач [51, 46]. Более подробно об этом сказано в разделе 1.4.5.

Ещё один важный момент состоит в і ом, что работы в области планирования при классических допущениях способствуют пониманию проблем планирования с неклассическими допущениями [1, 38, 55], которое более адекватно задачам реального уровня сложі;і>сти.

Среди отечественных работ, посвященп.-іх проблемам планирования, особо отметим [2,11,23, 9,35].

1.2. Хронология подходов интеллектуального планирования при классических допущениях

На рис.1 представлена хронология подходов к решению задачи

интеллектуального планирования при классических допущениях.

Планирование как доказательств о теорем (GPS 1963, QA3 1969)

Планирование как поиск в пространство состояний (STRPS 1971, PRODIGY1987, Warplan 1975)

Планирование как поиск в пространстве планов (hterPlan 1975, Tweak 1987, SNLP 1991, UCPOP 1992)

Иерархическое планирование (NOAH 1975, NONLIN 1977, SIPE 1985, O-Plan 1986)

Планирование как задача удовлетворения ограничений, выполнимости пропозициональных формул (Graphplan 1995, SATPIan 1996)

Эвристическое планирование (HSP 1998, FF 2000, LPG 2002)

Рис. 1. Хронология подходов классического планирования

Начало исследованиям в области планирования положено работами [57,

87, 86, 53], в которых планирование рассматривалось как доказательство

теорем.

Системам на основе доказательства теорем был присущ ряд недостатков. Наиболее существенными из них являлись: 1) крайне низкая производительность, 2) проблема фрейма. Более подробно проблема фрейма изложена в [92].

Эти недостатки привели к созданию подходов, основанных на поиске в пространстве состояний [52, 99, 80,42, 41].

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

13 планирования была сформулирована как поиск в пространстве частично-упорядоченных планов [47, 100, 76, 90].

Одновременно с развитием идеи частичных планов развивалась идея иерархического планирования [97, 96, 111], которое подразумевает создание планировщиком иерархии абстракций (подцелей). Это упрощает процедуру планирования — в начале создается план в общих чертах, затем выполняется детализация — спуск по иерархии. Это позволяет сосредочить вычислительные мощности на решении первостепенных задач. Иерархическое планирование также интересно тем, что лишь на основе этого подхода создано большинство реально работающих систем [101, 107].

Иерархическое планирование возможно как при поиске плана в пространстве состояний [96], так и при-поиске планов в пространстве планов [97].

В начале 90-х годов, в связи с появлением высокопроизводительных алгоритмов решения задачи удовлетворения ограничений (CSP-задача), задачи проверки истинности в пропозициональной логике (SAT-задача), стала популярной постановка задачи планирования как CSP-задачи [43] и как SAT-задачи [66]. Это позволило значительно повысить скорость синтеза планов. Одновременно с этим появились работы, в которых задача планирования рассматривалась как задача целочисленного линейного программирования (ILP-задача) [68] или как задача построения бинарных диаграмм решений (BDD-задача) [98, 49].

Начиная с 1998 года, стали появляться первые планировщики, использующие эвристики для поиска плана [44, 59, 65, 93, 56]. Конечно же, использование эвристик для решения задач не является свежей идеей. Но лишь недавно появились механизмы автоматизированного извлечения эвристик из описания домена планирования. В значительной степени, эгому способствовало выделение некоторых свойств структур, используемых алгоритмами Graphplan и Satplan.

14 В разделах 1.3-1.6 будут подробнее рассмотрены некоторые подходы к решению задачи планирования при классических допущениях на примерах работы конкретных алгоритмов.

1.3. Планирование как доказательство теорем

Одним из примеров системы доказательства теорем, использовавшейся

для решения задачи планирования, является система QA3 [57].

В системе QA3 одно множество утверждений использовалось для описания начального состояния, а другое - для описания эффектов действий. Чтобы следить за тем, какие факты являются истинными и в каком состоянии, в каждый предикат включаются переменные, отвечающие состоянию. Целевое условие описывалось формулой с переменной, связанной квантором существования.

Задача системы состоит в том, чтобы доказать существование состояния, в котором истинно целевое условие. В основе доказательства лежит метод резолюций [94].

Эксплуатация QA3 показала, что вывод в т. і кой системе получается очень медленным.

Кроме того, для неё не существовало сколько-нибудь приемлемого решения проблемы фрейма [92]. Суть этой проблемы состоит в том, что действие может иметь нелокальный эффект, т.е., в общем случае, не ясно какие формулы, описывающие состояние системы, изменяются при применении действия. Это, приводило к тому, что в описание действия включались утверждения об изменении (не изменении) каждого факта, представленного в состоянии. Очевидно, что в сложных предметных областях описание эффектов действия значительно усложняется. Достаточно злеіачтное решение проблемы фрейма предложено в [13].

1.4. Поиск в пространстве состояний

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

пространстве состояний, является STRIPS (STanforci Research Institute Problem Solver) [52].

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

Идея алгоритма STRIPS заимствована из сие: -мы GPS (General Problem Solver), разработанной для доказательства теорем [87]. Метод, использованный в GPS, назывался анализ средств и целей Cneans-ends analysis). Он подразумевает рассмотрение тех действий в текицем состоянии, которые имеют отношение к цели. Однако при таком под?, оде возникает следующая проблема: применять ли действия связанные с целью сразу же, как только они найдены или же приостановить применение дейсті пя пока не будут найдены все действия имеющие отношение к цели? STRIPS применяет действия сразу, достигая каждой цели по отдельности.

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

Для решения проблемы фрейма STRIPS допус :сает следующее:

в состоянии, к которому применяете! правило, изменяется выполнимость лишь тех формул, которые описа.'Ы в эффекте действия, а все остальные остаются неизменными.

Рассмотрим постановку задачи планирования при классических допущениях в терминах STRIPS.

1.4.1. Постановка задачи STRIPS-планирования

Пусть L - язык исчисления предикатов 1-го порядка (ИГГПП).

Определение 1.4.1. Факт f некоторая правильно построенная замкнутая формула L.

Определение 1.4.2. Состояние s - некоторое множество фактов.

По сути, состояние s - это эрбрановская интерпретация множества фактов. Таким образом, каждый факт из s выполним или невыполним в s, в соответствии с обычным определением понятия выполнимости в ИППП.

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

Приведём пример описания среды в терминах STRIPS:

s = {ATR(a), AT(B,b), АТ(С.с), VuVxVy ((AT(u,x) л (x Ф у)) -> ^ATfu.y))}

Здесь, ATR(a) означает, что "робот находится в комнате а", АТ(В,Ь) -"ящик В находится в комнате Ь", АТ(С,с) - "ящик С находится в комнате с", последняя сложная формула — "один объект не может находиться в разных местах", х, у, и - переменные в области значений, охватывающей доступное множество объектов. Имена конкретных объектов из этого множества: 'а', Ъ', 'с' - соответственно 'комната а*, 'комната Ь', 'комната с'; 'А', 'В', 'С -соответственно 'ящик А',' ящик В', 'ящик С.

Действия агента описываются с помощью правил.

Определение 1.4.3. Правило R-это , где С - предусловие правила, А -список добавлений, D - список удалений.

Предусловие С описывает множество фактов, которые должны быть выполнимы в состоянии s перед применением правила R. Список удалений D описывает множество фактов удаляемых из s при применении правила R. Список добавлений А описывает множество фактов, добавляемых в s при применении правила R.

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

Во-первых, при описании правила R затруднительно или невозможно явно выразить все удаляемые факты в различных случаях применения R. Поэтому в STRIPS принято такое ограничение, что в списке удалений выражаются лишь атомарные факты. При этом после применения правила контролируется выполнимость сложных фактов из s, которые содержат в своём описании удалённые атомарные формулы. Однако, как показано в [72] это не уберегло STRIPS от некорректностей. Оказывается, для списка добавлений А также необходимо было ввести подобное ограничение. Вместе с тем, в предусловии сложные факты могут фигурировать.

Во-вторых, если в описании- домена планирования допустимы функциональные символы, то это приводит к полуразрешимой задаче планирования, так как в множество фактов в s может быть добавлено потенциально бесконечное количество формул [47].

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

Пример правила.

Имя правила: Push (х, у, z)

Предусловие: C(R) = {ATR (у), АТ(х, у)}

Список добавлений: A(R) = {ATR (у), АТ(х, у)}

Список удалений: D(R) = {ATR (z), АТ(х, z)}

В приведённом примере, STRIPS-правило Push (х, у, z) описывает действие робота по перемещению ящика х из комнаты у в комнату z. Здесь, х, у, z - переменные.

Выполнение агентом действия сводите;: к применению правила. Применение правила модифицирует состояние s.; Дадим формальное определение применения правила STRIPS.

18 Определение 1.4.4. Правило R ^-применимо в состоянии s, если С0 выполнимо в s, где С - предусловие правила R, 9 - подстановка на место каждой переменной в правиле R некоторых констант.

Применение правила R преобразует состояние s в s* следующим образом: s' = (s-(D(R)0))u(A(R)0)).

Это преобразование обозначается так: S => S .

В определении 1.4.4. можно видеть использование STRIPS-допущения для решения проблемы фрейма.

STRIPS-допущение

при применении некоторого правила R к состоянию s выполнимость факта fes изменяется, только если факт f описан либо в списке удалений D(R), либо в списке добавлений A(R).

" Технически, при проверке применимости некоторого правила R, STRIPS выполняет полную подстановку на место всех переменных некоторых констант. Возможны различные варианты подстановок. Некоторые варианты подстановки могут давать примеры правил, применимые (или же неприменимые) в состоянии s. Однако, как подметили авторы STRIPS [52J, в алгоритм STRIPS можно внести незначительные модификации для применения неполностью означенных правил. В этом случае, в состоянии S появились бы факты с переменными в описании. Как будет видно далее, неполная подстановка активно используется планировщиками в пространстве планов. Соответствующее свойство этих планировщиков получило название малого связывания (least commitment).

Дадим постановку задачи STRIPS-планирования.

Определение 1.4.5. Будем называть доменом планирования Р = , где So - начальное состояние, LR — конечное множество правил.

19 Определение 1.4.6. Будем называть задачей планирования Т = <Р, G>, где G -описание целевого факта агента, или просто цель.

Решение задачи планирования Т заключается в нахождении плана, который достигает цели G.

Определение 1.4.7. План Plan- это последоват .льность состояний So, ..., s_n, последовательность правил Rj, ..., R„, и последовательность подстановок 0ь..., 0_П, такая что, G выполнима в s„. Длина плана Plan равна п.

Plan :s.

_{«Л V2 Wn}

^S2'"

1.4.2. Алгоритм STRIPS

Опишем алгоритм STRIPS (рис.2)

STRIPS

вход: ER, s, G выход: plan

1. S=S₀

2. пока G не выполнимо в s делать

1. выбрать компоненту g из G

2. выбрать правило ReER такое, ч і о ge A(R)

3. STRIPS (SR, s, C(R))

4. применить R к s

5. добавить R в plan

3 вернуть plan

Рис. 2. Алгоритм STRIPS

Изначально на вход алгоритма STRIPS подаётся множество правил ZR, начальное состояние So, цель G.

Будем полагать, что в множестве /R. все правила полностью конкретизированы.

Вначале в стек целей помещается главная цель G.

Если цель не является простой, т.е. содержит конъюнкцию литералов, то система STRIPS добавляет в стек в некотором порядке каждый из литералов составной цели (п. 1.1). Когда верхняя цель стоса является однолитергшьной,

20 система ищет действие (п. 1.2), которое содержит и списке добавлений литерал, сопоставимый с этой целью. Если такое действие не применимо к текущему состоянию, тогда его предусловие помещается и стек целей, иначе действие применяется к текущему состоянию (п. 1.5.) и nor щается в план (plan). Если верхняя цель в стеке соответствует текущему сої. юянию, то она удаляется из стека. Алгоритм STRIPS завершается, когда стек ii\ <; г.

1.4.3. Неполнота алгоритма STRIPS. Аномалия Суссмана

Существуют задачи, для которых STRII S либо не может построить

план, либо находит не минимальный план.

Причина этого кроется в том, что STM.'S удовлетворяет каждую компоненту составной цели по отдельности, Скз учёта их взаимосвязи. Особенность предметной области, где цели взаимосвязаны (взаимодействуют) получила название взаимосвязи целей.

Примечание. Впервые некорректность S'] iUPS'a была вскрыта в 1973 году Аленом Брауном в Массачусетском техно: к : ическом институте. Браун попытался решить задачу, рассматриваемую в эт^.м разделе на планировщике HACKER. HACKER был создан Джеральдом Суссманом на основе планировщика STRIPS, поэтому задача получила название аномалия Суссмана (Sussman Anomaly).

Рассмотрим аномалию Суссмана [99].

Дано:

Объекты:

3 кубика - А, В, С.

Состояние описывается предикатами:

ontable (х) - кубик х на столе,

clear (х) - над кубиком х пусто,

handempty - рука агента пуста,

holding (х) - рука агента держит кубик х,

on (х,у) - кубик х находится на кубике у.

х, у —переменные.

21 Правила: Rl: pickup (x) - поднять кубик со стола

С (Rl): ontable (х) & clear (х) handempty

A (Rl): holding (х)

D (Rl): ontable (х), clear (х), handempty R2: putdown (x) — опустить кубик на стол

С (R2): holding (х)

A (R2): ontable (х), clear (х), handempty

D (R2): holding (х) R3: stack (х,у) - положить кубик на другой кубик

C(R3): holding (х) & clear (у)

A(R3): handempty, on (x,y), clear (x)

D(R3): holding (x), clear (y) R4: unstack (x,y) - снять кубик с другою кубика

C(R4): handempty & on(x,y) & clear (x)

A(R4): holding (x), clear (y)

D(R4): handempty, on(x,y), clear (x) Начальное состояние s₀ и цель G изображены на рис.3. Таким образом, цель G= {On (А,В) & On (В,С)}.

Рис. 3. Аномалия Суссмана

Поскольку цель G является составной, то STRIPS расщепляет её на

отдельные компоненты - On (А,В) и On (В,С), которые помещаются в стек и

удовлетворяются по очереди.

Положим, что On (А,В) наверху стека, тогда планировщик находит

следующую последовательность правил для удовлетворения On (А,В):

UNSTACK(C,A), PUTDOWN(C), PICKUP(A), STACK (A,B). Применяет

найденную последовательность к состоянию So. Получается ситуация, изображённая на рис.4, в которой On (А,В) выполнима. Цель On (А,В) удаляется из стека целей.

On (А.В) удовлетворено

^эис. 4. Удовлетворение первой цели

Далее, из ситуации на рис.4 , удовлетворяется следующая цель в стеке -

On (В,С). В результате имеем: UNSTACK(C,A), PUTDOWN(C), PICKUP(A),

STACK (A,B), UNSTACK(A.B). PUTDOWNfA\ PICKUPfB), STACK (B.C).

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

на рис.5. Цель On (В,С) удовлетворена и удаляется из стека. Однако цель

Оп(А,В), удовлетворённая на предыдущем этапе, перестает быть выполнимой.

On (В.С)

удовлетворено

On (А.В)

нарушено

^Зис. 5. Удовлетворение второй цели

И, поэтому, теперь планировщик пытается из ситуации на рис.5

удовлетворить On (А,В). Это приводит к добавлению ещё двух правил к

имеющейся последовательности.

В результате получаем план: UNSTACK(C,A), PUTDOWN(C),

PICKUP(A), STACK (A,B), UNSTACK(A,B), PUTDOWN(A), PICKUP(B),

STACK (B,C), PICKUP(A), STACK (А.В). Подчёркнутые правила применяются.

Цель On (А,В) & On (В,С) достигается. План построен.

Однако существует другой план, содержащий меньше действий: UNSTACK(C,A), PUTDOWN(C), PICKUP(B), STACK (B,C),

PICKUP(A), STACK(A,B).

1.4.5. Вычислительная сложность задачи STRIPS-планирования

Описание задачи классического планирования в терминах STRIPS

допускается любым планировщиком. Поэтому рассмотрим вычислительную сложность задачи STRIPS-планирования [51,46, 50].

Приведём вторую теорему Чапмэна о неразрешимости. Теорема 1.4.8. Задача планирования Т не разрешима, если в языке описания домена планирования Р допустимы функциональные символы. Доказательство: приведено в [47].

Теорема 1.4.9. Задача планирования Т разрешима, если в языке описания домена планирования Р недопустимы функциональные символы. Доказательство: приведено в [50].

Далее будем рассматривать случай разрешимой задачи планирования, вычислительная сложность которой (табл.1), варьируется от постоянного времени до EXPSPACE-полноты в зависимости от ограничений, накладываемых на язык домена, планирования Р.

Таблица 1. Вычислительная сложность задачи планирования

Примечания:

1. Действия имеют не более чем одно предусловие

2. Для некоторых множеств действий имеет место либо PSpace-полнота, либо NP-полнота

24 Пояснения к таблице 1:

1. в графе "ограничения языка" описаны ограничения, накладываемые на язык L домена планирования Р;

2. в графе "как заданы действия" — "априорно" означает, что множество ZR в задаче планирования Т фиксировано, а параметрами являются So и G;

3. в графе "существование плана" представлена вычислительная сложность следующей задачи: "Существует ли для задачи планирования Т= 0, SR, G> план, который достигает цели G?";

4. в графе "существование плана длиной ^ к" представлена вычислительная сложность следующей задачи: "Существует ли для задачи планирования Т= и заданного целого числа к, план длиной меньшей либо равной к, который достигает цели G?"

Заметим, что задача "существование минимального по длине плана", как минимум, равна по сложности "задаче существовании плана длиной к".

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

1. Если нет никаких ограничений на описание домена планирования Р, тогда любое конкретизированное деііствие может появиться несколько раз в плане. Количество конкретизированных действий экспоненциально. Размер каждого состояния в худшем случае является экспоненциальным. Таким образом, пространство состояний в котором необходимо осуществить поиск также экспоненциально. Это приводит к тому что, задача "существование плана" EXPSPASE-полна (строка 1).

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

25 экспоненциальной длины. Таким образом, сложность планирования снижается до NEXPTIME-полноты.

3. Если дополнительно к ограничениям в пункте (2) добавить ограничения на предусловия, так чтобы они не содержали негативных атомов (строка 3), тогда порядок действий в плане не имеет значения. Это снижает сложность задачи "существование плана" до EXPTIME-полноты. Однако, для задачи "существование плана < к" сложность не снижается и остается NEXPTIME-полной (строка 1), так как из-за константы к приходится перебирать всё множество последовательностей длины < к.

4. Если предусловие действия содержит не более одного литерала (строки 4, 8, 12), тогда использование техники обратного поиска позволяет снизить сложность планирования, так как количество подцелей в этом случае не увеличивается. В этом случае сложность варьируется от NLOGSPACE до PSPACE-полноты.

5. Все соображения, изложенные в пунктах 1-4 также справедливы для случая ограничения языка домена планирования Р нульместными предикатами (строки 9-13). Кроме того, заметим, что для этого случая, мощность |SR|, а также размер любого состояния s, снижается с экспоненциального до полиномиального. Естественно, что планирование в этом случае существенно легче, чем в случае допущения k-местных предикатов. В общем случае, снижение сложности планирования можно добиться за счёт ограничения местности предиката некоторой постоянной j. 1 Гри этом нульместное ограничение соответствует случаю, когда j=0.

(6) Когда множество действий ZR задано априорно, то местность
предикатов и количество переменных в каждом действии постоянно. В этом
случае сложность планирования снижается и варьируется в пределах от const до
PSPACE-полноты (строки 5, 6, 7, 8,13).

1.4.6. Языковые средства описания доменов планирования

Необходимость описания и решения задач в более сложных доменах

привело к появлению языка описания действий ADL (Action Description Language) [89], являющегося расширением STRIPS-языка. ADL позволяет выражать условные эффекты действий (эффекты, которые применяются только тогда, когда дополнительные условия истинны в момент применения действия), квантифицированные эффекты (эффекты применяются к группе объектов вместо одного), в предусловиях стало возможным выражать дизъюнкции, квантифицированные формулы, и прочие логические связки.

Одним из первых планировщиков, который поддерживал расширенный синтаксис языка ADL, являлся UCPOP.

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

1.5.1. Основная идея

Первым подобным планировщиком являлся NOAH (Nets Of Action

Hierarchies) [97]. NOAH строил оптимальный план для аномалии Суссмана.

В 1991 году МакАлистер и Розенблитт [76] доказали полноту SNLP -алгоритма частично-упорядоченного планирования, что во многом предопределило направление дальнейших исследований.

Начнём с примера, демонстрирующего особенности частично-упорядоченных планов.

Пусть, агенту необходимо выполнить несколько задач в комнате А, и несколько задач в комнате В (рис. 6.).

комната А

warn.

комната В

_шнеш

Рис. 6. Иллюстрация к частично-улорядоченным планам Агент способен выполнять:

1. действия Aj, ..., A_n, Bj, ..., B_m, которые доставляют, соответственно, факты Рі (іє l..n) и Qj (jg l..m). Предусловие C(A.) = IN(A), предусловие C(Bj) = IN(B).

2. действие GO (А), которое не имеет предусловий, но имеет в списке добавлений IN(A), а в списке удалений IN (В);

3. действие GO(B), которое не имеет предусловий, но имеет в списке добавлений IN(B), а в списке удалениіі IN (А).

Необходимо достичь цели G = {Р_ь ..., P_n, Qj,..., Q_m}. Очевидно, что цель G может быть достигнута после исполнения плана Plan = {GO(A); Aj; ...; A_n; GO(B); Bj; ...; B_m}. Заметим, что порядок

28 выполнения действий А{, и порядок выполнения действий Bj не имеет значения, поскольку они выполняются в разных комнатах. Следовательно, план (GO(A), А_п;...; A], GO(B), B_m,...; Bi} будет эквивалентен вышеприведённому плану.

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

1.5.2. Основные определения

Введём несколько базовых определений для описания алгоритма SNLP.

Определение 1.5.1. Шаг плана - это пара <№, R>, где № - уникальный номер шага, R — некоторое правило.

Два разных шага могут соответствовать одному и тому же правилу. Таким образом, допустимы планы, содержащие более одного вхождения данного правила.

В SNLP нелинейный план изначально всегда содержит два шага: 1) стартовый - START, соответствующий правилу, которое имеет список добавлений, задающих множество начальных фактов (начальное состояние среды), но не имеет предусловий и списка добавлений, и 2) конечный - FINISH, соответствующий действию, которое в качестве предусловий имеет целевые формулы, но не имеет списка добавлений и списка удалений. Определение 1.5.2. Причинная связь - это тройка , где f - некоторый факт, W - шаг, имеющий в предусловии атом f, S - шаг, имеющий факт f в списке добавлений.

Определение 1.5.3. Угроза V для причинной связи -это шаг, который либо добавляет, либо удаляет факт f, и при этом не является ни шагом S, ни шагом W.

Определение 1.5.4. Защитное ограничение - это отношение порядка "<", заданное на шагах плана, при этом S

29 выполнен до шага W, и наоборот, S>W означает, что шаг S должен быть выполнен после шага W.

Определение 1.5.5. Нелинейный план Plan =

4. каждый шаг плана участвует либо в причинной связи, либо в защитном ограничении;

5. любой шаг W с предусловием f состоит в некоторой причинной связи ;

6. имеется шаг-угроза V для причинной связи и нелинейный план содержит либо защитное ограничение VW. Определение 1.5.6. Топологическая сортировка нелинейного плана Plan - это линейная последовательность всех шагов, которая удовлетворяет следующим условиям:

7. первый шаг в последовательности - START;

8. последний шаг в последовательности — FINISH;

3. для каждой причинной связи шаг S в последовательности предшествует шагу W;

4. для каждого защитного ограничения U

Определение 1.5.7. Топологическая сортировка нелинейного плана является решением, если применение последовательности действий шагов между шагами START и FINISH из начального состояния, которое задаётся списком добавлений шага START, приводит в состояние, ; котором содержатся все предусловия шага FINISH.

В работе [76] доказывается теорема о полноте частично-упорядоченного планирования.

Теорема 1.5.1. Любая топологическая сортировка нелинейного плана, обладающего полнотой, является решением задачи планирования Т.

Определение 1.5.8. Нелинейный план является противоречивым, если на нём невозможно осуществить топологическую сортировку.

Следствие 1.5.1. Противоречивый нелинейный план не является решением

задачи планирования.

Доказательство: Немедленно следует из теоремы 1.5.2.1.

Алгоритм SNLP является систематичным в том смысле, что в процессе поиска, осуществляемого в пространстве частично-упорядоченных планов, один и тот же план или эквивалентные планы никогда не рассматриваются дважды. Теорема 1.5.2. Алгоритм SNLP систематичен [76].

1.5.3. Алгоритм SNLP

Опишем алгоритм SNLP (рис.7.)

SNLP

вход: SR, Plan

выход: Plan

результат: "план построенУплан не построен"

1. если Plan противоречив то вернуть Р1ап=0, "План не построен"

2. если Plan обладает полнотой то вернуть Plan, "план построен"

3. если в Plan'e имеется шаг-угроза V для причинної! связи и Plan не содержит защитного ограничения VW, то недетерминированно выполнить:

либо (a) SNLP (Plan+(V(Plan+(V>W))

4. если существует некоторый шаг W с предусловием f, для которого
не существует причинной связи , то
недетермированно выполнить:

либо (а) выбрать недетерминированно некоторый шаг S, добавляющий f и выполнить SNLP (Plan+)

либо (b) выбрать недетерминированно правило ReZR,
добавляющее f, и создать новый шаг S, ассоциированный с выбранным
правилом R, и выполнить SNLP (Plan+)

Рис. 7. Алгоритм SNLP

На вход процедуры подаётся множество правил ER, а также,

нелинейный план Plan, не обладающий полнотой, который содержит шаги START и FINISH. Далее Plan уточняется путём добавления причинных связей и защитных ограничений, до тех пор, пока не обнаружится такое уточнение, что план либо противоречив, либо обладает полнотой.

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

32 можно осуществлять выполнение пунктов а) и Ь), не произвольным образом, а с учётом более иерархичного предусловия^ вовлечённого в причинную связь.

1.5.4. Принцип малой связности

Очень часто нелинейные планировщики называют планировщиками,

обладающими малой связностью (least commitment).

Неформальный принцип малой связности утверждает, что планировщику следует всегда осуществлять сначала выбор таких действий, которые его меньше связывают. Частичная подстановка - один из примеров малого связывания. Так, при поиске плана можно начать с анализа последствий более конкретного действия, например, MOVE (Л, В), а можно выбрать менее связывающее действие, например, MOVE (А, х), где х — некоторая переменная, вместо которой можно подставить любой объект. Нелинейность ещё один пример малого связывания, например, можно выбрать действие Put (А, х) в качестве первого шага плана, с другой стороны, мы можем предположить что Put (А, х) появляется где-то в середине плана без точного указания места.

Однако принцип малой связности не гарантирует нелинейным планировщикам значительного превосходства над линейными [103].

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

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

Многие задачи в ИИ, а также в других областях информатики, могут

быть рассмотрены как задачи удоплетворения ограничений [70, 83], для которых существует множество высокопроизводительных алгоритмов. В связи с этим стала популярной формулировка задачи планирования, как задачи удовлетворения ограничений [62, 67, 43].

CSP-задача предъявляет требования к переменным в форме ограничений. Множество возможных значений переменных конечно, и называется доменом. Ограничения указывают, какие кортежи значений допустимы для определённого множества переменных. Ограничение может быть задано явно, путём перечисления допустимых кортежей или неявно, в форме алгебраического выражения. Решением CSP-задачи является такое означивание переменных, при котором учтены все ограничения.

Определение 1.6.1. Задача удовлетворения ограничений — это тройка , где:

(1) V = {vi,..., v_n} -множество переменных.

2. D = {D_b..., D_n} — множество доменов. Каждый домен D; — конечное множество, содержащее возможные значения, соответствующей переменной.

3. С = {Cj ,..., С„} - множество ограничений. Ограничение С - отношение, определённое на подмножестве всех переменных, то есть DiX...xD_n з Q.

Заданное (частичное или полное) означивание переменных удовлетворяет ограничению Q, если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит Сі. Множество всевозможных означиваний всех переменных является пространством, содержащим решение CSP-задачи.

Решением CSP-задачи является такое означивание всех переменных, при котором все ограничения удовлетворены. Если для некоторой задачи имеется,

34 по крайней мере, одно решение, то задача является разрешимой, иначе неразрешимой, или же противоречивой, или же переограниченной.

В некоторых случаях необходимо получить все решения. Иногда, может быть сформулирована задача ограниченной оптимизации, а именно: найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. Иногда необходимо просто выяснить, разрешима ли задача. В любом случае вычислительная сложность CSP-задачи NP-полная [74].

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

В этом разделе рассмотрим алгоритм планирования — Graphplan [43], который использует технику прямого распространения ограничений.

На момент своего создания (1994) Graphplan показал впечатляющие результаты для ряда тестовых задач классического планирования. По производительности он превзошёл планировщики Prodigy [104], UCPOP [90], SNLP'[76], TOCL, POCL, ТОРІ [42].

Создатели Graphplan'a Блюм и Фёст объясняют этот успех способностью Graphplan'a анализировать множество планов одновременно. Однако, как показал Камбхампати [64] производительность Graphplan'a объясняется тем, что он обрабатывает компоненты множества планов без разделения, используя уточнения дизъюнктивных планов.

Graphplan оказал сильное влияние на последующие работы в области планирования. Его алгоритм был модернизирован многими независимыми исследователями. На сегодня популярными постреализациями являются: 1) IPP (Interference Progression Planner) [68] - включена поддержка языка ADL, 2) STAN (STate ANalysis planner) [73] - повышена производительность в сравнении с GraphPlan'oM, 3) TGP (Temporal GraphPlan) [106] - добавлена возможность обработки темпоральных зависимостей, 4) SGP (Sensory

1.6.2,1, Основные определения

Graphplan принимает на вход стандартное STRIPS-описание задачи

планирования и переводит это описание в компактную структуру, которая называется граф планирования (Planning Graf), из которой впоследствии извлекает частично-упорядоченный план. Важно отметить, что граф планирования это не граф состояний, который получается при работе планировщика в пространстве состояний.

Graphplan сочетает в себе свойства как планировщика в пространстве состояний, так и планировщика в пространстве планов. Т.е. он не обладает свойством малого связывания и при этом строит частично-упорядоченные планы.

При изложении Graphplan'a будем пользоваться терминологией из оригинальной работы [43].

Определение 1.6.2. Факты F — множество элементарных ППФ без переменных из домена планирования Р.

Перед основной стадией работы Graphplan создаёт множество действий, осуществляя для каждого правила ReZR всевозможные варианты подстановки индивидов на места всех переменных. Имеется также специальный вид действия 'no-op' - "ничего не делать".

Определение 1.6.3. Действия Acts — множество полностью конкретизированных правил из ER, а также действие 'no-op'. Действие 'no-op' имеет предусловие C('no-op')=f, список добавлений А('по-op')=f, и пустой список удалений D('no-op')=0, где f- произвольный факт из F.

Определение 1.6.4. Граф планирования PG — ориентированный ярусный граф с двумя типами узлов и с тремя типами рёбер.

Два типа узлов в PG таковы: 1) FN — множество узлов, ассоциированных с фактами F, и 2) AN - множество узлов, ассоциированных с действиями Acts. Ассоциацию некоторого факта feF с узлом fnePG, будем обозначать как fii->f.

36 Ассоциацию некоторого действия act є Acts с узлом aneANcz PG, будем обозначать как an->act.

Множество узлов PG разбито на непересекающиеся подмножества b ALi, ... AL_n._b FL_n>, где FL - ярус, содержащий узлы-факты, AL - ярус, содержащий узлы-действия, FL₀ содержит узлы-факты, соответствующие фактам So-

Любой ярус ALiCzPG содержит узлы-действия an-^act, такие что Nodes(C(act<-an))eFLi и не существует fiii, fn₂ eNodes(C(act<-an)) и 2>eMXF, где Nodes(C(act<-an)) - узлы на ярусе FLj, ассоциированные, с фактами из предусловия C(act).

Любой ярус фактов FLjCzPG (i>0) содержит узлы-факты fh->f, такие что, для любого апє ALi-icPG справедливо (feD(act<-an) ИЛИ feA(act^-an)). Рёбра устанавливаются между узлами, расположенными на ярусах. Три типа рёбер PG таковы:

1. ребро-предусловие - устанавливается между узлом-фактом fh-^f на некотором ярусе FLj и узлом-действием an->act на ярусе AL;, если факт feC(act);

2. ребро-добавление - устанавливается между узлом-действием an->act на некотором ярусе ALj и узлом-фактом fh->f на ярусе FLj+i, если f eA(act);

3. ребро-удаление — устанавливается между узлом-действием an->act на некотором ярусе ALi и узлом-фактом frr>f на ярусе FLj+i, если f eD(act).

Из определения видно, что ярусы PG чередуются так: ярус фактов | ярус действий и т.д. Первый ярус графа содержит факты, характеризующие начальное состояние. Ярусы в PG от самого первого до последнего содержат:

По сути, граф планирования PG позволяет представлять пространство состояний без разделения. Точнее, множество состояний хранящиеся совместно, например, на ярусе FLj+i, получаются в результате всевозможных альтернативных вариантов применения действий, расположенных в ярусах ALj по ALj (i

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

Дадим формальное определение понятию мьютекс.

Мьютекс - это отношение взаимоисключения между двумя узлами на одном ярусе. Существуют мьютексы между действиями и между фактами.

Определение 1.6.5. Мьютексы MXF - отношения взаимоисключения между

узлами-фактами 2>, где fii_b fii2 - узлы-факты, находящиеся на одном

ярусе, такие, что:

либо, 1) все действия на предыдущем ярусе, добавляющие факт fh|, удаляют

факт біг;

либо, 2) все действия на предыдущем ярусе добавляющие факт fn_:, удаляют

факт fiii.

Определение 1.6.6. Мьютексы МХА — отношения взаимоисключения между

узлами-действиями <ап_ь ап₂>, где ап_ь ап₂ - узлы-действия, находящиеся на

одном ярусе, такие, что:

либо, 1) действие ani удаляет предусловие или же эффект действия агь,

либо, 2) предусловие действия ani и предусловие действия ап₂ состоят в

мьютексе mxf є MXF.

Замечание. Мьютекс между парой узлов пі и п₂, может иметь место на некотором ярусе L, и не иметь место на некотором последующем ярусе L\ С другой стороны, если между парой узлов П| и П2 на некотором ярусе L не существует мьютекса, то и на последующих ярусах после L, пара узлов nj и пг не будут состоять в мьютексе.

Мьютексы превращают граф планирования в граф ограничений в смысле CSP-задачи. Метод, который используется для построения графа планирования, называется прямым распространением ограничений.

Свойство 1.6.1. Пара ярусов фактов FLj и FLj - идентичны, если FLj и FLj содержат: 1) одинаковые факты, И 2) одинаковые мьютексы. Свойство 1.6.2. Граф Планирования PG является стабилизированным, если существуют пара смежных ярусов фактов FLj и FLj* і и FLj идентичен FLj+i.

Пусть граф PG стабилизирован, и имеется пара идентичных ярусов-фактов FLj, FLj+i gPG. Тогда,

Утверждение 1.6.1. Ярус фактов FLkePG идентичен ярусу фактов FLjgPG, где k>ieN.

Доказательство: Действительно, во-первых, из-за существования "по-ор"-действий, факт f однажды появившись на некотором ярусе фактов, будет иметь место во всех последующих ярусах фактов. Во-вторых, множество фактов, которые могут быть созданы STRIPS-правилами конечно. Следовательно, должен существовать такой ярус фактов Q, содержащий факты, которые будут иметь место во всех последующих ярусах фактов. В-третьих, если два факта р и q, появившиеся на одном ярусе, не состоят в мьютексе, то и в последующих ярусах они также не будут состоять в мьютексе. Таким образом, должен существовать такой ярус фактов Р после Q, что все последующие ярусы фактов имеют множества мьютексов идентичные тем, что в Р. Утверждение доказано.

Цель G является разрешимой (достижимой) в 2-х случаях: 1) если она удовлетворяется тривиальным образом, т.е. компоненты цели G имеют место в начальном ярусе фактов, 2) если в графе PG существует подграф Plan, который

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

Пусть задача планирования Т имеет план длиной п. Теорема 1.6.1. План длиной п можно извлечь из графа планирования PG, содержащего п ярусов-действий [43].

Теорема 1.6.2. Алгоритм GraphPlan возвращает "план не существует", только если цель G не достижима [43].

Теорема 1.6.3. Алгоритм GraphPlan обладает полнотой [43].

1.6,2.2. Алгоритм Graphplan

Опишем алгоритм GraphPlan (рис. 8).

GRAPHPLAN вход: Acts, So, G выход: Plan

1. t=0 - номер начальной стадии

2. GS — множество для хранения разрешимых/неразрешимых целей

3. PG.FL₀ S₀

4. пока PG не стабилизирован или пока цель G не разрешима делать

1. РАСШИРЕНИЕ ГРАФА ПЛАНИРОВАНИЯ PG

2. ПОИСК ПЛАНА в PG

3. переход к следующей стадии (t=t+l)

5. если "цель G разрешима" то вернуть Plan иначе вернуть Р1ап=0

РАСШИРЕНИЕ ГРАФА ПЛАНИРОВАНИЯ вход: FL_t

1. создание следующего яруса действий AL_t+i

4. для каждого действия acteACTS, применимого в FLt, если для каждой пары фактов її, f₂ eC(act) не существуют узлы fhi-> f_b fh₂ -^ f₂, такие что fh|, 6 є FLt и fhj, fh₂ є mxf то создать в AL_t+j узел-действие an -> act и создать рёбра-предусловия между an и соответствующими узлами fneFL_t

5. выявить мьютексы тха на ярусе AL_t+i

2. создание следующего яруса фактов FL_t+i

6. для каждого узла aneAL_t+i добавить в FL_t+i узлы-факты, ассоциированные с фактами из A(act4-an) и D(act^-an) и соединить соответствующими рёбрами-добавления или рёбрами-удаления узлы FLt+i и узлы AL_t+i

7. выявить мьютексы mxf на ярусе FL_t-n

Рис.8. Алгоритм GraphPlan

ПОИСК ПЛАНА

результат: "цель G разрешима"/"цель G пока не разрешима"

1. если GNcFLt то добавить GN в GSj¹, где і - номер текущего яруса фактов,

t - номер текущей стадии, GN - множество узлов-фактов, ассоциированных с целевыми компонентами

2. если GSj¹ разрешимо то вернуть "цель G разрешима" иначе вернуть

"цель G пока не разрешима"

РАЗРЕШИМОСТЬ ЦЕЛИ

вход: GSj¹

выход: "GSj¹ разрешимо" / " GSj¹ не разрешимо"

1. GS/ - множество (под)целей на і-ом ярусе фактов

2. Comb - множество всех комбинаций А_соть действий яруса ALj.i таких, что любая пара действий в А^ть не состоит в мьютексе тхаєМХА, и при этом Асоть доставляет GSj¹

3. для каждой Acomb^Comb создать подцель GSj./, состоящую из

предусловий действий в А_С0П)ь

4. если цели GSjV разрешимы то добавить тройку 1 , А_соть, GSj*> в

Plan и вернуть "GS/ разрешимо"

5. если цели в GSj¹ не разрешимы то вернуть "GSj¹ не разрешимо"

Рис. 8. Алгоритм GraphPIan

В начале Graphplan формирует первичный ярус фактов FL₀.

Graphplan работает по стадиям (переменная t в алгоритме). В каждой

стадии выполняется:

1. расширение графа планирования PG,

2. поиск плана в графе PG.

На этапе расширения графа PG на основе текущего яруса фактов создаётся новый ярус действий, а затем, на основе нового яруса действий, формируется новый ярус фактов. Во вновь сформированных ярусах выявляются мьютексы MXF и МХА (процедура Расширение Графа Планирования).

Graphplan строит частично-упорядоченный план. Извлечение плана осуществляется с помощью техники обратного хода от текущего яруса к начальному ярусу. Как утверждает автор Graphplan'a, эта техника позволяет более эффективно использовать информацию о мьютексах между действиями и фактами в графе PG.

Опишем эту технику.

Перед поиском плана Graphplan проверяет следующее условие:

"справедливо ли, что GNc=FL_TCK и для каждой пары узлов gnbg^eGN и gni,gn2^mxf, где GN—множество целевых фактов, ассоциированных с узлами на ярусе FLtck"'.

Если это так, тогда возможно план существует, и Graphplan приступает к поиску.

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

Более точно происходит следующее.

Изначально формируется множество GS - хранилище (под)целевых наборов GSi*¹.

GS^ — множество целей, выбираемые из яруса фактов с номером і, при поиске плана на стадии t.

Начиная с текущего яруса FLj (вначале i=t) в GS^ заносятся целевые факты GNcFLj. Далее на ярусе действий с номером і-l выделяются всевозможные комбинации действий (А_соть), доставляющие GS^ (множество Comb). Устанавливается подцель GSi.^, в которую помещаются предусловия выделенных действий, расположенные на ярусе фактов FLm. Для каждой из комбинаций действий А_сотьсСотЬ процесс продолжается рекурсивно, до тех пор, пока GSj..^ окажется тривиально разрешимой, либо не найдётся комбинации действий, доставляющей GSi.j¹¹, т.е. Comb = 0.

Если подцель GSj..^ оказывается разрешимой, то при возврате из рекурсии в план Plan помещаются тройки i.i^t, Aco_mb, GSi^ , в которой для каждого действия из Aco_mb, известно какие (под)цели из GS_i^t достигает действие, и какие цели из GSj..^ необходимо достичь, прежде чем выполнить действие.

Для получения линейного плана необходимо пыполнить топологическую сортировку нелинейного плана Plan, с учётом целевых ограничений GS_i^t.

Опишем ещё одну незначительную, но интересную особенность Graphplan'a.

В практической реализации алгоритма для повышения эффективности обратной техники извлечения плана, используется хеширование. В хеш-таблице на каждой стадии t запоминаются целевые наборы GSi^t, которые оказались НЕ разрешимыми в ярусе фактов і. На каждой стадии при поиске плана проверяется наличие в хэш-таблице разрешаемой подцели GSi.^. Если подцель GSj..^ в хеш-таблице, то поиск плана немедленно прекращается, и исходная цель GS^, также помещается в хеш, как неразрешимая.

1.7. Выводы

В настоящей главе дана постановка задачи интеллектуального

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

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

3. планирование как доказательство теорем;

4. планирование как поиск в пространстве состояний;

5. планирование как поиск в пространстве планов;

6. иерархическое планирование;

7. планирование как CSP-задача, SAT-задача, ILP-задача, BDD-задача;

8. эвристическое планирование.

В качестве ключевых работ в области классического планирования следует отметить: STRIPS [52] — решение проблемы фрейма, SNLP [76] — доказательство полноты алгоритма частично-упорядоченного планирования, GRAPHPLAN [43] - значительное повышение производительности за счёт использования техники удовлетворения ограничений, SATPLAN [67] — использование эффективных методов решения задачи выполнимости пропозициональных формул, HSP [44] - для повышения скоросги поиска планов использована эвристика, извлекаемая из описания задачи планирования.

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

Вычислительная сложность задачи STRIPS-планирования

По сути, состояние s - это эрбрановская интерпретация множества фактов. Таким образом, каждый факт из s выполним или невыполним в s, в соответствии с обычным определением понятия выполнимости в ИППП.

Неформально, состояние представляет модель среды, в которой действует агент. Приведём пример описания среды в терминах STRIPS: Здесь, ATR(a) означает, что "робот находится в комнате а", АТ(В,Ь) -"ящик В находится в комнате Ь", АТ(С,с) - "ящик С находится в комнате с", последняя сложная формула — "один объект не может находиться в разных местах", х, у, и - переменные в области значений, охватывающей доступное множество объектов. Имена конкретных объектов из этого множества: а , Ъ , с - соответственно комната а , комната Ь , комната с ; А , В , С -соответственно ящик А , ящик В , ящик С. Действия агента описываются с помощью правил. Определение 1.4.3. Правило R-это C,A,D , где С - предусловие правила, А -список добавлений, D - список удалений. Предусловие С описывает множество фактов, которые должны быть выполнимы в состоянии s перед применением правила R. Список удалений D описывает множество фактов удаляемых из s при применении правила R. Список добавлений А описывает множество фактов, добавляемых в s при применении правила R. Как оказалось, такое описание дейстиий без дополнительных ограничений приводит к некоторым трудностям. Во-первых, при описании правила R затруднительно или невозможно явно выразить все удаляемые факты в различных случаях применения R. Поэтому в STRIPS принято такое ограничение, что в списке удалений выражаются лишь атомарные факты. При этом после применения правила контролируется выполнимость сложных фактов из s, которые содержат в своём описании удалённые атомарные формулы. Однако, как показано в [72] это не уберегло STRIPS от некорректностей. Оказывается, для списка добавлений А также необходимо было ввести подобное ограничение. Вместе с тем, в предусловии сложные факты могут фигурировать. Во-вторых, если в описании- домена планирования допустимы функциональные символы, то это приводит к полуразрешимой задаче планирования, так как в множество фактов в s может быть добавлено потенциально бесконечное количество формул [47]. Для обхода подобных трудностей, при описании STRIPS-задачи планирования общепринято использовать лишь элементарные термы без функциональных символов. В приведённом примере, STRIPS-правило Push (х, у, z) описывает действие робота по перемещению ящика х из комнаты у в комнату z. Здесь, х, у, z - переменные. Выполнение агентом действия сводите;: к применению правила. Применение правила модифицирует состояние s.; Дадим формальное определение применения правила STRIPS. Определение 1.4.4. Правило R -применимо в состоянии s, если С0 выполнимо в s, где С - предусловие правила R, 9 - подстановка на место каждой переменной в правиле R некоторых констант. Это преобразование обозначается так: S = S . В определении 1.4.4. можно видеть использование STRIPS-допущения для решения проблемы фрейма. STRIPS-допущение при применении некоторого правила R к состоянию s выполнимость факта fes изменяется, только если факт f описан либо в списке удалений D(R), либо в списке добавлений A(R). " Технически, при проверке применимости некоторого правила R, STRIPS выполняет полную подстановку на место всех переменных некоторых констант. Возможны различные варианты подстановок. Некоторые варианты подстановки могут давать примеры правил, применимые (или же неприменимые) в состоянии s. Однако, как подметили авторы STRIPS [52J, в алгоритм STRIPS можно внести незначительные модификации для применения неполностью означенных правил. В этом случае, в состоянии S появились бы факты с переменными в описании. Как будет видно далее, неполная подстановка активно используется планировщиками в пространстве планов. Соответствующее свойство этих планировщиков получило название малого связывания (least commitment). Дадим постановку задачи STRIPS-планирования. Определение 1.4.5. Будем называть доменом планирования Р = So, XR , где So - начальное состояние, LR — конечное множество правил. Определение 1.4.6. Будем называть задачей планирования Т = Р, G , где G -описание целевого факта агента, или просто цель.

Синтез планов на основе техники прямого распространения оіраничений

На вход процедуры подаётся множество правил ER, а также, нелинейный план Plan, не обладающий полнотой, который содержит шаги START и FINISH. Далее Plan уточняется путём добавления причинных связей и защитных ограничений, до тех пор, пока не обнаружится такое уточнение, что план либо противоречив, либо обладает полнотой.

Для случая абстрактного планирования, приведённая процедура может быть расширена следующим образом. Необходимо создать иерархию утверждений, которая будет отражать трудность достижения тех или иных условий. Для этого каждому утверждению сопоставляется некоторое число, характеризующее его иерархический уровень. Малые числа могут указывать на низкий уровень иерархичности, большие числа - на высокий уровень иерархичности. Для того чтобы процедура удовлетворяла предусловия, спускаясь с вершины иерархии утверждений, в процедуре SNLP на шаге 3 и 4 можно осуществлять выполнение пунктов а) и Ь), не произвольным образом, а с учётом более иерархичного предусловия вовлечённого в причинную связь.

Очень часто нелинейные планировщики называют планировщиками, обладающими малой связностью (least commitment). Неформальный принцип малой связности утверждает, что планировщику следует всегда осуществлять сначала выбор таких действий, которые его меньше связывают. Частичная подстановка - один из примеров малого связывания. Так, при поиске плана можно начать с анализа последствий более конкретного действия, например, MOVE (Л, В), а можно выбрать менее связывающее действие, например, MOVE (А, х), где х — некоторая переменная, вместо которой можно подставить любой объект. Нелинейность ещё один пример малого связывания, например, можно выбрать действие Put (А, х) в качестве первого шага плана, с другой стороны, мы можем предположить что Put (А, х) появляется где-то в середине плана без точного указания места. Однако принцип малой связности не гарантирует нелинейным планировщикам значительного превосходства над линейными [103]. быть рассмотрены как задачи удоплетворения ограничений [70, 83], для которых существует множество высокопроизводительных алгоритмов. В связи с этим стала популярной формулировка задачи планирования, как задачи удовлетворения ограничений [62, 67, 43]. CSP-задача предъявляет требования к переменным в форме ограничений. Множество возможных значений переменных конечно, и называется доменом. Ограничения указывают, какие кортежи значений допустимы для определённого множества переменных. Ограничение может быть задано явно, путём перечисления допустимых кортежей или неявно, в форме алгебраического выражения. Решением CSP-задачи является такое означивание переменных, при котором учтены все ограничения. Определение 1.6.1. Задача удовлетворения ограничений — это тройка V, D, С , где: (1) V = {vi,..., vn} -множество переменных. (2) D = {Db..., Dn} — множество доменов. Каждый домен D; — конечное множество, содержащее возможные значения, соответствующей переменной. (3) С = {Cj ,..., С„} - множество ограничений. Ограничение С - отношение, определённое на подмножестве всех переменных, то есть DiX...xDn з Q. Заданное (частичное или полное) означивание переменных удовлетворяет ограничению Q, если каждая переменная получила такое значение, что соответствующий кортеж значений принадлежит СІ. Множество всевозможных означиваний всех переменных является пространством, содержащим решение CSP-задачи. Решением CSP-задачи является такое означивание всех переменных, при котором все ограничения удовлетворены. Если для некоторой задачи имеется, по крайней мере, одно решение, то задача является разрешимой, иначе неразрешимой, или же противоречивой, или же переограниченной. В некоторых случаях необходимо получить все решения. Иногда, может быть сформулирована задача ограниченной оптимизации, а именно: найти такое решение, в котором значения переменных оптимизировали бы некоторый заданный функционал. Иногда необходимо просто выяснить, разрешима ли задача. В любом случае вычислительная сложность CSP-задачи NP-полная [74]. В этом разделе рассмотрим алгоритм планирования — Graphplan [43], который использует технику прямого распространения ограничений. На момент своего создания (1994) Graphplan показал впечатляющие результаты для ряда тестовых задач классического планирования. По производительности он превзошёл планировщики Prodigy [104], UCPOP [90], SNLP [76], TOCL, POCL, ТОРІ [42].

Создатели Graphplan a Блюм и Фёст объясняют этот успех способностью Graphplan a анализировать множество планов одновременно. Однако, как показал Камбхампати [64] производительность Graphplan a объясняется тем, что он обрабатывает компоненты множества планов без разделения, используя уточнения дизъюнктивных планов.

Graphplan оказал сильное влияние на последующие работы в области планирования. Его алгоритм был модернизирован многими независимыми исследователями. На сегодня популярными постреализациями являются: 1) IPP (Interference Progression Planner) [68] - включена поддержка языка ADL, 2) STAN (STate ANalysis planner) [73] - повышена производительность в сравнении с GraphPlan oM, 3) TGP (Temporal GraphPlan) [106] - добавлена возможность обработки темпоральных зависимостей, 4) SGP (Sensory

Graphplan принимает на вход стандартное STRIPS-описание задачи планирования и переводит это описание в компактную структуру, которая называется граф планирования (Planning Graf), из которой впоследствии извлекает частично-упорядоченный план. Важно отметить, что граф планирования это не граф состояний, который получается при работе планировщика в пространстве состояний.

Планирование на основе полного разрешения конфликтов

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

Сформулируем и докажем теорему, которая показывает возможность использования операции полного разрешения конфликтов для поиска планов. Пусть имеется последовательность seq, не являющаяся планом, и последовательность plan, являющаяся некоторым конкретным планом. Теорема 2.7.1. Полное разрешение конфликтов последовательности seq такое, что u(seq)=plan и seq plan возвращает одну и только одну последовательность reseRES cSEQ такую, что #(res)=plan, либо res=plan. Доказательство: А. Докажем существование последовательности действий res, такой что /j(res)=plan. Рассмотрим произвольный конфликт cf=aff[xCF(seq). 1. В соответствии с основным положением #(seq)=plan, существуют действия /j(a)=a , h(x)=%\ где а ,хІЄРІап« Напомним, что в плане не существует конфликтных действий. Следовательно, должно существовать некоторое действие Р , не позволяющее конфликтовать паре действий Й(а)=а и Й(х) Х такое, что: a P x eplan. 2. По определению полного разрешения конфликтов некоторая последовательность reseRESseq содержит действие P"eres, которое подобно Р єріап и является действием, разрешающим конфликт cf=afJ7eCF(seq). Заметим, в множестве результирующих последовательностей RES54 имеются всевозможные варианты расположения Р" между действиями h(av)=a и й(х")=Х TCea",x"eres. 3. а) для любого действия n" p"eres верно, что /f Qi jieseq, б) для любого действия neseq верно, что й(ц)=и єр1ап, в) из а) и б) следует что, Ц" І . 4. Количество альтернативных расположений Р єріап среди действий plan a, подобных действиям из res (имеется в виду подобие, выведенное в 3 пункте: ц" а ) и между действиями й(а)=а и Ц%)=Х\ конечно. 5. из 2, 3, 4 и по определению 2.5.1. (гомоморфизм последовательностей) следует, что существует такая последовательность действий reseKESscq, что /i(res)=plan. B. Единственность существования res, такого, что /i(res)=plan, следует из того факта, что не существует альтернативного порядка следования действий в res, для которого сохранилось бы утверждение /i(res)=plan. Следовательно, последовательность res единственна. C. Докажем возможность res=plan. 1. В любой последовательности reseRESscq количество действий больше чем в seq. 2. Количество действий в плане конечно. 3. Тогда из А.5, C.l, С.2 следует, что в одном из вариантов пошагового разрешения действительно имеет место res=plan. Теорема доказана. Обратим внимание, на интересное свойство последовательности init. Свойство 2.7.1. Начальная последовательность init такова, что Ь (i it) = plan, где plan — это любой существующий план для задачи Т. Доказательство: Очевидно. Основной идеей алгоритма CRPA является полное разрешение конфликтов некоторой исходной последовательности действий seq, дли которой справедливо /i(seq)=plan. Полное разрешение конфликтов приводит к множеству последовательностей, которые в свою очередь могут также содержать конфликты. Разрешение конфликтов продолжается для очередных последовательностей, до тех пор, пока не будут получены бесконфликтные последовательности действий. Основываясь на свойстве 2.7.1., алгоритм CRPA начинает с разрешения конфликтов в последовательности init=(start, finish). Более того, задача планирования Т может оказаться тривиально разрешимой, то есть Gczso, и как следствие eff(start)=pre(flnish) без каких-либо конфликтов. Множество взаимовлияний, порождаемое последовательностью init, будем называть первичными взаимовлияниями. Теорема 2.7.2. Если для задачи планирования Т существует решение, то алгоритм CRPA найдёт план. Доказательство: l.Ha вход CRPA подаётся последовательность seq=init, обладающая свойством h (seq) = plan, где plan - это некоторый конкретный план. 2. Алгоритм CRPA есть не что иное, как процедурная реализация пошагового полного разрешения конфликтов входной последовательности seq. 3. Из 1 и 2, и в соответствии с теоремой 2.7.1. следует, что существует одна из рекурсивных ветвей алгоритма, которая возвращает конкретный план plan. Теорема доказана. Утверждение 2.73. Если для задачи планирования Т существует решение, то алгоритм CRPA найдёт все планы. Доказательство: Это так поскольку, относі; гліьно любого плана plan, решающего задачу планирования Т, справедливо у ъерждение /i(init)=plan. В этом разделе затронем вопрос о конем11 ости алгоритма в случае не существования плана. Если для задачи планирования Т не существует решения, тогда для начальной последовательности init не выполнимо утверждение /j(init)=plan. Из-за этого алгоритм CRPA будет работать бесконечно. Другими словами, говоря, последовательность init содержит конфликты, которые не могут быть преобразованы к некоторому множеству согласий путём пошагового преобразования конфликтов. Иначе говорі, последовательность ink несогласуема. Определим понятие несогласуемоГ, последовательности в общем случае.

Архитектура инструментальных программных средств

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

В настоящее время среди динамических систем [12] достаточно хорошо изучены различные классы дискретных систем, такие как дискретно-аргументные системы [4], системы с нечеткой информацией [3], логико-динамические системы [14], системы на конечных множествах (т-цспи) [34].

В последнее время активно исследуются так называемые гибридные динамические системы, т.е. системы которые состоят из двух взаимодействующих компонент: континуальной и дискретной -дифференциальные автоматы [102], модель Нерода-Кона [84], модель Брокета [45] и некоторые другие. Развитие этого направления связано с возросшим интересом к созданию высокоавтномных систем управления. Примерами гибридных систем являются системы контроля загруженности путей, системы контроля за химическими процессами, системы управления летательными аппаратами.

Совсем недавно выделился другой класс подобных систем - с дискретной частью, основанной на знаниях [17, 20, 21, 26]. Далее, будем именовать их динамическими интеллектуальными системами (ДИС). В динамических интеллектуальных системах для описания состояния используют базы данных, а для задания функций реакции и перехода - базы знаний.

В отличие от дискретных систем, ДИС обладают гладкой компонентой (возможно, не одной); в отличие от гибридных систем — более сложно устроенными состояниями, чем таблица состояний "дискретной" части или вектор фазового пространства "гладкой" части гибридной системы.

Ещё одно отличие - как от первого, так и от второго класса — заключается в том, что каждое из состояний образуется путем замыкания некоторого порождающего множества событий. Это порождающее множество состоит из наборов фактов и аксиом. Среди фактов - факты, наблюдаемые и прогнозируемые из предыдущего состояния; среди аксиом — как точные, так и эмпирические знания.

Динамические интеллектуальные системы возникают, в частности, при интеграции экспертных систем с системами имитационного моделирования сложных технических (или иных) систем, при создании интеллектуальных систем различного назначения, при решении задач поддержки принятия решений [6], в клинической деятельности при создании систем поддержки лечебно-диагностического процесса и практически при всех реализациях экспертных систем реального времени [22].

Рассмотрим некоторые задачи, решаемые динамическими интеллектуальными системами. В задаче стыковки космического корабля со станцией [5] необходимо описать состояние космического корабля (значения скоростей, координаты центра масс, скорости вращения относительно осей симметрии, относительную дальность до цели, значение угла промаха и т.д.), отражать очень динамичное изменение состояния, представлять цели управления космическим кораблём в подобной ситуации (нахождение станции, ориентация на станцию, вход в зону активного сближения, облет станции, стыковка, расхождение со станцией), строить план целенаправленного полёта. В задаче оптимальной компоновки вычислительного комплекса из выбранного набора компонентов нужно учитывать характеристики (электрические, механические, напряжение питания, потребляемую мощность и др.) различных компонентов, множество ограничений на взаимное расположение компонентов в структуре комплекса, ограничения, накладываемые на совместимость компонент и т.д. [79]. При решении весьма актуальной задачи реинжиниринга бизнес-процессов очень важным этапом является моделирование бизнес-процессов. На этом этапе необходимо учесть множество материальных, информационных и финансовых потоков, интенсивность поступления заказов в различные периоды времени по различным видам продукции и услуг. Следствием подобной динамичности бизнес-процесса является неравномерность использования структурных подразделений предприятия, оборудования, информационной системы, источников финансовых средств [32]. Как показывает практика, основные проблемы [71] при разработке прикладных динамических интеллектуальных систем таковы: динамичность: необходимо учитывать изменение входных данных, а также постоянно отслеживать истинность выведенных фактов; асинхронность и «непредсказуемость событий: события в окружающей среде могут появляться одновременно, в то время как моделирование происходит в большинстве случаев последовательно. Большинство созданных систем, предполагают, что все процессы, протекающие в среде, упорядочены и предсказуемы. Однако в большинстве предметных областей могут появляться непредсказуемые события, которые необходимо обработать; неточные или ошибочные данные: Входные данные могут быть неточны, или неверны, например, в результате повреждения сенсора. Т.о., ДИС должна распознать и корректно обработать неточные или же неверные данные; внешний интерфейс: В отличие от статических систем, основанных на знаниях, ДИС должны быть снабжены набором сенсоров для восприятия параметров окружающей среды.

Похожие диссертации на Исследование методов и разработка алгоритмов планирования и моделирования целенаправленного поведения

Исследование методов и разработка алгоритмов автоматического планирования траектории на плоскостиЯковлев, Константин Сергеевич

Разработка и исследование методов и алгоритмов для моделирования адаптивных веб-ресурсов на основе нечетких ультраграфов Целых Алексей Александрович

Разработка и исследование методов и алгоритмов определения живучести транспортных сетей в геоинформационных системах на основе нечетких графовЯстребинская, Дина Николаевна

Разработка и исследование методов и алгоритмов интерпретации баз знаний с онтологиямиХла Мьо Аунг

Разработка и исследование методов и алгоритмов субполосного кодирования речевых сообщений при хранении и передаче речевых данныхБолдышев, Алексей Владимирович

Исследование методов, разработка моделей и алгоритмов формирования элементов знаковой картины мира субъекта деятельностиПанов Александр Игоревич

Разработка и исследование методов и алгоритмов нечеткой классификации объектов имиджей документовСрун Совила

Исследование и разработка бионических методов и алгоритмов для решения задач транспортного типаПолуян, Анна Юрьевна

Разработка и исследование субполосных методов и алгоритмов сегментации речевых сигналовФирсова, Александра Александровна

Разработка и исследование интегрированных алгоритмов размещения элементов на основе методов эволюционного моделированияБалюк Любовь Владимировна