Разработка распределенного планировщика для систем поддержки принятия решений

Размещено на http://www.allbest.ru/

Разработка распределенного планировщика для систем поддержки принятия решений

А.Ю. Неделина

Аннотация

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

Анализ проблем эффективного управления сложными динамическими объектами показывает необходимость внедрения современных интеллектуальных технологий в процесс управления. Поскольку принятие компетентных решений в сложной, быстро меняющейся обстановке - достаточно непростая задача, актуальным является создание систем поддержки принятия решений реального времени (СППР РВ) для оказания помощи лицам, принимающим решения (ЛПР) [Вагин и др., 2001].

Процесс управления сложным объектом с помощью СППР РВ может быть представлен в виде схемы, представленной на рис. 1.

Рис.1. Схема процесса управления сложным объектом

К основным задачам, решаемым с помощью ИСППР РВ, относятся [Башлыков и др., 1994]:

диагностика и мониторинг - выяснение где, когда и какого типа возникла проблемная ситуация;

поиск решения (планирование) - нахождение оптимальной или допустимой последовательности действий для достижения поставленной цели или для разрешения возникшей проблемной ситуации;

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

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

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

В данной статье представлены концепция, архитектура и результаты вычислительных экспериментов функционального компонента планировщика DIPLAN (Distributed Planner), основанного на использовании распределенного подхода к решению задачи интеллектуального планирования.

Подход к задаче планирования. Рассмотрим задачу планирования как задачу поиска решения (построения плана действия) в пространстве состояний.

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

Проблемная область D определяется кортежем

D = <F, S, A, R>

где:

F - конечное множество булевских переменных;

- конечное множество состояний;

A - конечное множество действий;

- отношение перехода.

Действие допустимо в состоянии .

Задача планирования в пространстве состояний P для проблемной области D определяется кортежем

P = <D, I, G>

где:

- начальное состояние;

- множество целевых состояний.

План для задачи планирования P в проблемной области D определяется последовательностью пар (состояние, действие), которые отображают начальное состояние s₀ I в одно из целевых состояний s G, где

{(s, a) : s S, a A, a применимо в s};

;

.

Концепция планировщика DIPLAN. Разрабатываемый планировщик DIPLAN относится к системам планирования в пространстве состояний.

Пространство состояний в планировщике представляется в виде дерева T = (V,E), представленного на рис. 2., где множество вершин V - состояния системы, а множество ветвей E(VV) - операторы (действия в системе). Ветви отражают действия или изменения в системе, активизирующие переход из одного состояния в другое.

Рис.2. Дерево поиска решений

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

Схема взаимодействия блоков планировщика, отражающая процесс поиска решения, представлена на рис. 3.

Наиболее эффективные методы поиска поставленной цели в пространстве состояний - это эвристические методы поиска [Nilsson N., 1980]. Однако большая размерность задач и, как следствие, высокая трудоемкость вычислений существенно снижают применимость эвристических алгоритмов в интеллектуальных системах типа СППР РВ, где временной фактор является одним из определяющих.

Рис.3. Схема взаимодействия блоков планировщика DIPLAN

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

Сравнительный анализ реализаций параллельных алгоритмов эвристического поиска применительно к различным параллельным архитектурам, представленный в [Eremeyev et al., 2004], показал эффективность использования параллельных вычислительных структур класса MIMD-архитектуры (Multiple Instruction Multiple Data).

Классификация MIMD-архитектур приведена на рис.4.

Рис.4. Классификация параллельных архитектур класса MIMD

Распределенная структура планировщика ориентирована на параллельную архитектуру с распределенной памятью. Для программной реализации планировщика DIPLAN выбраны кластерные системы вследствие наилучшего соотношения цена/производительность [Воеводин и др., 2002; Buyya, 1999]. Среди основных преимуществ использования кластерных систем можно выделить следующие:

надежность, отказоустойчивость и постоянная доступность сетевых сервисов и данных;

распределение и балансировка нагрузки между узлами кластера.

Для блока поиска решения планировщика был предложен и реализован параллельный IDA* алгоритм итеративного поиска в глубину (Iterative-Deepening A*), который подробно описан в [Неделина, 2004].

Прототип планировщика DIPLAN. Основным функциональным компонентом планировщика является модуль поиска решения. При построении архитектуры планировщика использован мультиагентный подход - планирование в системе с несколькими агентами, работающими над достижением одной цели [Knapik et al., 1998; Тарасов, 2002].

Архитектура распределенного планировщика DIPLAN, состоящая из двух модулей, приведена на рис. 5.

распределенный планировщик интеллектуальный пространство

Рис. 5. Архитектура системы планирования DIPLAN

В DIPLAN разработано три класса агентов со следующими функциями:

интерфейсный агент (Interface agent) - отвечает за взаимодействие с пользователем или с системой типа СППР, спецификацию входных требований (т.е. преобразование исходных данных во внутренние структуры системы планирования), а также отображение полученного решения;

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

агенты-процессы (Process agents) - обрабатывают локальные подзадачи и пересылают результаты агенту координатору.

В планировщике DIPLAN агенты являются автономными процессами. Количество агентов-процессов может изменяться динамически в зависимости от количества доступных процессоров. Коммуникация агентов-процессов и агента-координатора реализуется в рамках модели передачи сообщений средствами параллельной технологии MPI (Message Passing Interface). MPI - стандарт программирования, предназначенный для поддержки работы параллельных процессов в терминах передачи сообщений [Gropp et al., 1994].

Результаты вычислительных экспериментов. Для тестирования и последующей оценки результатов вычислительных экспериментов использовалась тестовая задача (benchmark) - nn_головоломка при n=4 (15-Puzzle) [Korf, 1985]. В качестве математической модели описания задачи nn-головоломки выбрана матрица размерностью nn, где каждой фишки головоломки соответствует элемент матрицы, и позиция фишки определяется координатами строки и столбца.

Исходя из тестовой задачи, выбрана эвристическая функция Manhattan-Distance (MD-функция), оценивающая сумму кратчайших расстояний от ошибочно поставленных элементов до их целевого состояния [Korf, 1985; Felner et al., 2004].

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

где:

· (i_x,j_x)- позиция элемента x в некотором состоянии, (i, j)- (номер строки, номер столбца);

· (x DIV n, x MOD n)- позиция элемента x в целевом состоянии.

Приведем оценки вычислительной сложности предложенного параллельного IDA* алгоритма для блока поиска решения.

Трудоемкость последовательного IDA* алгоритма определяется следующей формулой

где:

· k_IDA* - количество раскрываемых вершин;

· f(i) - оценочная MD-функция для i-й вершины.

Число раскрываемых вершин в алгоритме IDA* можно определить как

, при

где:

· b - эвристический фактор ветвления;

· d - количество итераций.

В случае если b >1 для всех итераций, k_IDA* раскрываемых вершин в итерации растёт экспоненциально с числом итераций d.

Трудоемкость T_seq последовательного IDA* алгоритма, определяемая числом мультипликативных операций, для задачи nn-головоломка можно оценить следующим выражением:

при .

Трудоемкость параллельной версии IDA* алгоритма вычисляется следующим образом:

где p - количество процессоров.

Таким образом, ускорение, получаемое при параллельном выполнении разработанного IDA* алгоритма, для задачи nn-головоломка (при n=4) зависит только от числа процессоров:

, , при .

Реализация функционального компонента планировщика выполнена на языке С средствами параллельной технологии MPI с применением пакета mpich.nt.1.2.5. Моделирование выполнялось на параллельной системе, состоящей из рабочих станций Pentium III (2,8 ГГц), объединенных сетью Fast Ethernet.

Было проведено 100 экспериментов для задачи nn-головоломка (при n=4) в режиме моделирования параллельных вычислений на одном, 2-х и 4-х процессорах. Результаты 100 экспериментов были усреднены и разбиты на пять групп.

Характеристики реализации модуля поиска решения планировщика DIPLAN для 44-головоломки с использованием параллельного алгоритма IDA* и MD-функции представлены на рис.7. и рис.8.

Рис. 7. График зависимости времени вычисления решения от числа процессоров

Рис. 8. График зависимости ускорения решения от числа процессоров

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

Заключение

Полученные результаты использованы при выполнении НИР кафедры Прикладной математики МЭИ (ТУ) (научные руководители проф. Вагин В.Н. и проф. Еремеев А.П.) по тематике конструирования интеллектуальных (экспертных) СППР РВ с применением нетрадиционных логик. В дальнейшем планируется продолжить исследования в 2-х направлениях: расширить класс тестовых задач, а также исследовать теоретически и экспериментально реализацию модуля поиска решения применительно к параллельным архитектурам с общей памятью, а именно, SMP системам.

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

1. Башлыков А.А., Еремеев А.П. Экспертные системы поддержки принятия решений в энергетике. - М.: Изд-во МЭИ, 1994.

2. Вагин В.Н., Еремеев А.П. Некоторые базовые принципы построения интеллектуальных систем поддержки принятия решений реального времени // Изв. РАН Теория и системы управления, 2001, №6.

3. Воеводин В.В., Воеводин Вл.В. Параллельные вычисления.- СПб.: БВХ - Петербург, 2002.

4. Неделина А.Ю. Параллельные алгоритмы стратегического планирования // Доклады международной конференции «Информационные средства и технологии» (МФИ-2004), в 3-х томах, Т.1-М.: Янус-К, 2004.

5. Тарасов В.Б. От многоагентных систем к интеллектуальным организациям: философия, психология, информатика. - М.: Эдиториал УРСС, 2002.

6. Brenner W., Zarnekow R., Wittig H. Intelligente Softwareagenten. Grundlagen und Anwendungen, Springer-Verlag, Berlin Heidelberg, 1998.

7. Buyya R. High Performance Cluster Computing: Architectures and Systems, Prentice Hall PTR, NJ, 1999.

8. Eremeyev A.P., Nedelina A.Yu. Methods and algorithms of strategic planning for decision support systems // Proc. of the 6 Joint Conference on Knowledge-Based Software Engineering, IOS Press, 2004.

9. Felner A., Korf R.E., Hanan S. Additive Pattern Database Heuristics // J. of Artificial Intelligence Research, 2004, 22.

10. Gropp W., Lusk E., Thakur, R. Using MPI-2: advanced features of the message-passing Interface, MIT Press, Cambridge, 1994.

11. Knapik M., Johnson J. Developing intelligent Agents for distributed systems, McGraw-Hill, New York, 1998.

12. Korf R.E. Depth-first iterative-deepening: An optimal admissible tree search, Artificial Intelligence, 1985, 27(1).

13. Nilsson N. Principles of Artificial Intelligence, Tioga Publishing Co., Palo Alto, 1980.

Размещено на Allbest.ru