Software & Systems

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

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

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

– система Sipe-2 [5] используется на производственных линиях по розливу и упаковке пива, при этом она учитывает производственные и ресурсные ограничения пивзавода. Сердцем Sipe-2 является алгоритм иерархического планирования.

Существующие проблемы диктуют необходимость интеграции теорий экспертных систем, планирования и управления. Базисом такой интеграции могут послужить теоретические результаты, представленные в [6-8]. В этих работах был выделен класс динамических интеллектуальных систем с дискретной частью, основанной на знаниях. Подобные системы обладают рядом полезных свойств – невысокая чувствительность модели к априорной полноте описания состояний, нежесткие требования к формализму и высокая способность к адаптации в быстро изменяющейся среде. Для этих систем была установлена связь управляемости с архитектурой базы знаний и существованием плана целенаправленного поведения, а также выявлены условия устойчивости их траектории.

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

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

Архитектура динамической интеллектуальной системы

Основным модулем динамической интеллектуальной системы (далее – система), изображенной на рисунке, является база знаний, в которой содержатся знания, планы, цели функционирования динамической интеллектуальной системы. В системе принят гибридный метод представления знаний, который сочетает системы фреймов и продукционные системы [9].

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

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

Важной особенностью системы является асинхронная работа модуля интеллектуального планирования (МИП) и модуля анализа и управления (МАУ), то есть МИП постоянно формирует планы целенаправленного поведения системы, в то время как МАУ исполняет их.

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

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

Представление знаний

Основной когнитивной структурой базы знаний является прототип.

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

Объект – сущность, обладающая свойствами и функциональным назначением. Большинство свойств объекта на протяжении большого промежутка времени не меняется. Пример: 'стул', 'стол', 'монитор', 'комната' и т.д.

Ситуация – поименованный набор элементов предметной области и отношений между ними в текущий момент времени. Пример: 'тревога', 'брак', 'пожар', 'стабильная работа', 'столкновение' и т.д.

Процесс – описание закономерностей изменения свойств объектов. Например, 'подача топлива', 'вращение турбины', 'падение объекта' и т.д.

Объекты, ситуации, процессы обладают свойствами, и с ними могут быть связаны различные события. Например, свойствами объекта (ситуации, процесса) являются такие характеристики, как цвет, масса, объем, рост, длина, а событиями – такие, как 'включен', 'выключен', 'сломан', 'нажат' и т.д. События могут быть определены на свойствах, например, событие "повышенная температура тела человека" определено на свойстве 'температура' с областью характерных значений от 38 до 42 градусов.

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

Формально прототип – это:

Р=, где NР – имя прототипа; StrР – структура прототипа StrР: , где Аttr – множество атрибутов прототипа; Mагк – множество оценок прототипа; Inst – множество примеров, Rel – множество отношений, Rule – множество правил.

Подобная структура позволяет описывать ситуацию реального уровня сложности.

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

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

Для описания прототипа с помощью других прототипов определен слот – пример прототипа. Пример является представлением конкретного объекта, ситуации, процесса, созданного на основе прототипа. От родительского прототипа пример наследует структурную часть. Например, пусть имеются прототипы "колесо мотоцикла" и "мотоцикл", тогда примерами прототипа "колесо мотоцикла" будет пример "заднее колесо" и пример "переднее колесо".

Правило – это: R=<С, А, D>, где С – множество предусловий, А – множество добавляемых фактов, D – множество удаляемых фактов. Фактами называются атомарные формулы исчисления предикатов первого порядка без свободных переменных. Определены четыре категории правил: замыкания, перехода, управления, целеуказания.

Множество правил можно условно разделить на синхронные правила (категории 1, 3, 4), формирующие состояние системы s(t) на основе фактов в момент времени t, и диахронные (категория 2), формирующие состояние системы s(t+1) на основе фактов в момент времени t.

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

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

Правила целеуказания формируют множество целевых состояний системы.

Правила управления задают основные параметры управления системой для достижения целевого состояния.

Правила целеуказания и управления формируют целенаправленное поведение системы.

Правила перехода и замыкания формируют динамику изменения предметной области.

Время в системе дискретно. Задается временная шкала Т путем указания единицы измерения времени (с, час, сутки, дни, столетия и т.д.) и дискреты времени Dt. Тогда состояния системы представляются в моменты времени, кратные Dt.

Для пополнения базы знаний разработчик мо- жет использовать язык представления знаний. Ни- же приведен пример правила, записанного на этом языке.

Calc_tank_pos : transition rule

if true then

{

in V0:number = V;

in AV0:number = AV;

in X0:number = X;

in Y0:number = Y;

in A0:number = A;

out X1:number = X+1"sec";

out Y1:number = Y+1"sec";

out A1:number = A+1"sec";

A1=A0+AV0;

X1=X0+V0*cos(A0);

Y1=Y0+V0*sin(A0);

};

Здесь Calc_tank_pos – имя правила для расчета позиции автономной платформы в следующий момент времени, transition rule – категория правила (правило перехода), далее идет описание правила: true означает, что правило является некоторым вычислением, само вычисление описано в фигурных скобках.

Рабочая память

Текущее состояние системы отражается в рабочей памяти. Структуры рабочей памяти формируются на основе главного прототипа системы, который указывается пользователем. Обычно этот прототип является описанием предметной области. В ходе работы системы, слоты свойств и событий получают некоторые значения. При этом каждое новое значение не затирает предыдущего, то есть сохраняется история развития системы. Данные в рабочую память могут поступать: 1) от внешнего интерфейса, например, в ходе опроса датчиков, 2) от разработчика – через интерфейс разработчика, 3) от пользователя – через интерфейс пользователя.

В начале работы системы рабочая память содержит множество исходных фактов.

Установка целей системы

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

Приведем пример из прототипа интеллектуальной системы стыковки активного космического корабля и космической станции [10].

goals

Achieve Space.Docking;

Avoid Space.Collision;

Minimize Space.SpaceCraft.Fuel_volume;

end;

Здесь позитивным целевым фактом является стыковка активного корабля и станции (Docking), негативным целевым фактом – избежание их столкновения (Collision), сопутствующая цель – минимизация расхода топлива (Fuel_volume), Docking и Collision являются событиями в терминологии системы, а Fuel_volume – свойством.

Моделирование динамики

Система начинает функционировать после указания целей.

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

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

1.1.  Замыкание состояния системы

1.2.  Установку текущих целей системы

1.3.  Исполнение плана для достижения текущих целей

1.4.  Переход состояния системы

На этапе замыкания (п.1.1) на основе исходных фактов в рабочей памяти достраивается текущее состояние системы. По сути, здесь происходит выявление правил замыкания, применимых к множеству фактов в текущем состоянии, и исполнение этих правил.

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

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

На этапе перехода формируется ядро следующего состояния системы, а именно, исполняется множество правил переходов, применимых в текущем состоянии, которые выводят множество фактов в следующем состоянии системы.

Выполнение этапов происходит циклично, до тех пор, пока система не достигнет целевого состояния.

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

Моделирование целенаправленного поведения

Основой целенаправленного поведения системы является формирование и исполнение планов.

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

Для синтеза планов в системе используется расширение алгоритма Graphplan [11] для обработки континуальных действий и процессов. Алгоритм реализован как для фон-неймановской, так и для кластерной архитектуры вычислительных средств.

Алгоритм формирует временную последовательность действий. Каждый элемент этой последовательности синтаксически может быть представлен так:

t: (A1, A2, …, An).

Эта нотация предписывает исполнить действия A1, A2, …, An в момент времени t.

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

В этом случае подключается алгоритм поиска управления на континуальном уровне.

Введем некоторые термины и опишем этот алгоритм.

Расстояние – мера близости между континуальными переменными одного типа.

Перспективная комбинация действий – множество действий, применение которых приводит к сокращению расстояния.

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

1. Пока не достигнуто целевое состояние Выполнять

1.1. Поиск перспективной комбинации действий

1.2. Применение перспективной комбинации действий

1.3. Выявление запрещающего состояния

1.4. Установку негативной подцели

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

На этапе 1.2 перспективная комбинация действий применяется к текущему состоянию.

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

На этапе 1.4 выявленное запрещающее состояние помечается как негативное целевое состояние.

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

Алгоритм продолжает циклично выполнять этапы 1.1 – 1.4.

Алгоритм закончит работу за конечное время и в случае достижимости целевого состояния сформирует план либо установит, что плана не существует.

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

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

В перспективе планируется дополнить систему средствами обработки нечеткой информации. Модуль интеллектуального планирования будет расширен средствами адаптации планов и планирования на основе прецедентов.

Список литературы

1. Williams B., Nayak P. A Reactive Planner for a Model-Based Execution // Proceedings of the Fifteenth International Joint Conference on Artificial Intelligence (IJCAI-15). – Menlo Park, California, 1997. – pp.1178-1185.

2. Kautz H., Selman B. Pushing the Envelope: Planning Propositional Logic and Stochastic Search // Proceedings of the Thirteenth National Conference on Artificial Intelligence (NCAI-15) . – Menlo Park, California, 1996. – pp. 1194-1201.

3. Aarup M., Arentoft M., Parrod Y., Stokes I., Vadon H., Stader J. Optimum-AIV: A Knowledge-Based Planning and Scheduling System for Spacecraft AIV // Intelligent Scheduling / eds. Zweben M., Fox M.: Morgan Kaufmann, Inc, 1994. – pp. 451-469.

4. Currie K., Tate A. O-Plan: The Open planning architecture // Artificial Intelligence. – 1991. – № 52. – pp.49-86.

5. Wilkins D. Can AI planners solve practical problems? // Computational Intelligence. – 1990. – №6(4). – pp.232-246.

6. Осипов Г.С. Динамика в системах, основанных на знаниях // Изв. РАН: Теория и системы управления. – 1998. – №5. – С.24-28.

7. Лебедева Т.Г., Осипов Г.С. Архитектура и управляемость дискретных динамических систем, основанных на знаниях // Изв. РАН: Теория и системы управления. – 2000. – №5. – С.703-709.

8. Осипов Г.С., Жилякова Л.Ю., Виноградов А.Н. Динамические интеллектуальные системы. Представление знаний и основные алгоритмы. Моделирование целенаправленного поведения // Изв. РАН: Теория и системы управления. – 2002. – №6. – С.119-127.

9. Тарханов Т.С. Гибридное представление знаний для динамических интеллектуальных систем //Тр. междунар. конгресса: Искусственный интеллект в 21 веке (3-8 сентября 2001 г.) – М.: Физматлит, 2001. – С.272-279.

10. Виноградов А.Н. Интеллектуальная система с динамически изменяющейся целью // Там же. – С.339-348.

11. Blum A., Furst M. Fast planning through planning graph analysis // Proceedings of the 14th International Joint Conference on Artificial Intelligence (IJCAI–14). – Montreal, Canada, 1995. – pp.1636-1642.