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

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

УДК 004. 896
МУЛЬТИАГЕНТНОЕ МОДЕЛИРОВАНИЕ И ПЛАНИРОВАНИЕ ЛОГИСТИКИ Аксенов К. А. 1, Неволина А. Л. Аксенова О.П. х, Смолий Е. Ф. 1
1 ФГАОУ ВПО «Уральский федеральный университет имени первого Президента России Б. Н. Ельцина»
Екатеринбург, Россия (620 002, г. Екатеринбург, ул. Мира, 19), e-mail: wiper99@mail. ru__________
В работе представлены тенденции развития мультиагентного планирования, систем поддержки принятия решений и систем имитационного моделирования. Проведено сравнение двух перспективных подходов (сетей потребностей-возможностей и мультиагентной модели процессов преобразования ресурсов) и их соответствующих программных реализаций (MAGENTA и BPsim). Несмотря на активное применение средств концептуального моделирования на основе языка UML в области разработки информационных систем, применение данных средств в инженерии имитационного моделирования ограниченно. Преимуществом подхода интеграции концептуального и имитационного моделирования является возможность быстрого перехода от концептуальных к моделям проектирования и применения (программной реализации). При решении задачи перехода от концептуальной модели к имитационной могут быть использованы онтологии или модели представления знаний.
Ключевые слова: мультиагентная система, имитационное моделирование, планирование, логистика, процесс преобразования ресурсов.
MULTI AGENT SIMULATION AND SCHEDULING OF LOGISTIC Aksyonov K.A. 1, Nevolina A.L. 1, Aksyonova O.P. 1, Smoliy E.F. 1
1Ural Federal University named after First President of Russia B.N. Yeltsin, Ekaterinburg, Russia (620 002,
Ekaterinburg, Mira street, 19), e-mail: wiper99@mail. ru________________________________________
In this work was described trends of evolution multi agent intelligent scheduling, decision support systems and simulation systems for task of logistic scheduling. The comparison of two perspective approaches of intelligent scheduling (the Needs-and-Means Networks and the model of multi agent resources conversion process) and related information technologies (MAGENTA and BPsim) was described. Despite active application of conceptual modeling tools based on UML language in the area of information systems development, application of such tools in simulation modeling engineering is limited. An advantage of conceptual and simulation modeling integration approach is the capability of rapid transition from conceptual models to the models of engineering and application (program implementation). To define a transition from conceptual models to simulation models one may use ontologies or knowledge representation models.
Key words: multi agent system, simulation, scheduling, logistic, resources conversion process.
Введение
Одним из прикладных направлений мультиагентных технологий является планирование. Понятие агент соответствует аппаратно или программно реализованной сущности, которая способна действовать в интересах достижения целей, поставленных перед ней владельцем и/или пользователем, и которая обладает определенными интеллектуальными способностями [8- 9].
В [8] обсуждается пример применения мультиагентной системы (МАС) для
планирования работы гибкой производственной системы. К преимуществам обсуждаемой
мультиагентной системы планирования отнесены следующие: 1) формализация точек
принятия решений (сценариев обработки отдельных ситуаций) в виде агентов, что по сути
1
своей относится к этапу формализации знаний- 2) планировщик «встраивается» динамично (работает в реальном времени) посредством взаимодействий (переговоров) между отдельными элементами МАС и тем самым готов изменять план в случае задержек или неожиданных (внештатных) ситуаций- 3) сеть агентов, связанная отношениями,
самостоятельно координирует свои действия.
Дополнительное преимущество от мультиагентного планирования — возможность автоматического информирования участников процесса об изменениях на объекте управления, что дает прозрачность управления. В процессе разработки и внедрения МАС планирования происходит формализация знаний о предметной области и автоматизируется процесс принятия решений, тем самым облегчается деятельность, связанная с принятием решений.
К наиболее значительным практическим результатам применения МАС можно отнести развитие и применение на практике аппарата сетей потребностей и возможностей (ПВ-сетей) [4]. Данный подход придерживается «классического» понимания мультиагентной системы и ориентирован на решение задач в вычислительных сетях.
Аппарат ПВ-сетей, разработанный В. А. Виттихом, П. О. Скобелевым Г. А. Ржевским, программно реализован в виде технологии MAGENTA, которая нашла применение в семействе прикладных интеллектуальных систем планирования для следующих объектов [4]: предприятия, управляющего океанским танкерным флотом- транспортного предприятия, занимающегося перевозками грузов- организации, деятельность которой связана с управлением проектами.
Мультиагентный подход также нашел свое развитие в имитационном моделировании (ИМ). Так, система ИМ AnyLogic [2] поддерживает моделирование реактивных агентов. Для формализации поведения агентов в AnyLogic используются диаграммы состояний (State Chart) расширения UML-RT.
В контексте ИМ происходит трансформация понятия агента в направлении уменьшения значимости свойств коммуникации (на уровне сетевых протоколов) и возможности перемещения по сети в сторону интеллектуальности (учет большего объема данных и знаний, сложности реализации машины логического вывода — как это развивается в системах G2 и BPsim [1- 5- 6]) и социальности (моделирования социального поведения, внутренних убеждений, намерений и целей агентов).
Современное состояние систем имитационного моделирования и принятия решений
За последние десятилетия существенно расширилась область применимости систем имитационного моделирования (СИМ). Во-первых, СИМ, или программные имитационные модели, встраиваются в контур управления предприятием, интегрируются через интерфейсы обмена данными с датчиками, контроллерами, корпоративной информационной системой и тем самым получают данные о текущей ситуации на объекте управления. Во-вторых, большинство СИМ в процессе имитационного эксперимента позволяют изменять/обновлять исходные данные и адаптировать решение исходя из ситуации. В-третьих, в большинстве прикладных систем поддержки принятия решений (СППР), использующих подсистему ИМ или имитационную модель, для формализации знаний лиц, принимающих решения (ЛИР), и алгоритмов управления используются подсистемы оптимизации или улучшения решений на основе эвристик.
Так, о таких проектах для задач логистики, управления производством и строительства говорится в [2- 5- 6]. Таким образом, можно говорить об открытых интегрируемых модулях/системах ИМ. Также необходимо отметить активное применение в СППР элементов экспертных систем (баз знаний (БЗ) и машин логического вывода (МЛВ)) и онтологий. При решении задачи перехода от концептуальной модели к ИМ могут быть использованы онтологии или модели представления знаний.
В ПВ -сетях [4] онтология используется для формализации точек принятия решений распределенной сети объекта управления (логистической цепи). Так, для задачи грузоперевозок выделяют следующих агентов: грузовик, техосмотр, заказ, автозаправочная станция, водитель.
Мультиагентная модель процесса преобразования ресурсов (МИИР) [1] используется для решения задач моделирования и принятия решений в области производственных, логистических, организационно-технических и бизнес-систем. В контексте МППР агентам соответствуют элементы системы управления или модели ЛИР. МИИР реализована в результате интеграции имитационного, ситуационного, экспертного и мультиагентного моделирования. Средство BPsim является программной реализацией МИИР [1- 5- 6].
Семантическая модель МИИР [1] расширена элементами онтологии проектов логистики, представленной в [7], и адаптирована под специфику задачи снабжения сети
автозаправочных станций. Интегрированная онтология МППР и топливной логистики сети автозаправочных станций представлена на рисунке 1.
Наследование

^& quot-споргаД
Рис. 1. Интегрированная онтология МИИР и топливной логистики сети автозаправочных
станций
Анализ существующих подходов
В [4] И. О. Скобелев относит технологию MAGENTA к первому поколению мультиагентных платформ и освещает результаты разработки мультиагентной платформы второго поколения. К особенностям мультиагентной платформы второго поколения относится управление «флотилией мобильных ресурсов, имеющих датчики GPS/ГЛОНАСС на борту», а также то, что часть платформы развернута у водителя на мобильном устройстве.
К одному из требований к мультиагентной платформе планирования относится поддержка полного цикла управления, состоящего из следующих этапов [4]:
1) реакция на событие (дискретно-событийное управление). В реальном времени поступают события, которые нужно планировать и учитывать-
2) динамическое планирование (перепланирование / диспетчеризация) —
3) согласование и пересмотр планов «на лету» (изменения вносятся в планы ресурсов без останова и перезапуска программной системы, путем корректировки расписания) —
4) мониторинг и контроль исполнения планов.
Успешность внедрения систем планирования связана с фактором «доверия» пользователя (специалиста по логистике или диспетчера), на плечах которого лежит ответственная задача планирования и управления грузоперевозками. К дополнительным требованиям системы планирования, с целью повышения доверия, можно отнести следующие:
1) согласование планов в ходе диалога с пользователем-
2) ручная корректировка плана, включая ручное планирование.
Рассмотрим следующие подходы и модели мультиагентного планирования: 1) МППР [1]- 2) ПВ-сети [4]- 3) модель активных и пассивных преобразователей (АПП) Б. И. Клебанова и И. М. Москалева [3]- 4) подход, реализованный в системе AnyLogic [2].
При проектировании систем планирования цепей поставок важно вести контроль сроков выполнения поставок и отдельных заказов, диагностировать узкие места логистической цепи. Таким образом, необходимы средства анализа и моделирования, основанные на аппарате систем массового обслуживания. Результаты анализа рассмотренных подходов приведены в таблице 1.
Таблица 1
Сравнение подходов
Характеристики МППР ПВ-сеть АПП AnyLogic
1. Различные типы ресурсов, заявки, + + + +
очереди заявок, конфликты на ресурсах
2. Учет времени, операция дискретная + + + +
3. Коммуникации агентов + + НЕТ +
4. Использование геоданных + + НЕТ +
5. Планирование маршрута + + НЕТ НЕТ
6. Распределение заказов + + + НЕТ
7. Разработка онтологий + + + НЕТ
8. Настройка МЛВ (блок эвристик) + + НЕТ НЕТ
9. Вычислительные сети НЕТ + НЕТ НЕТ
10. ИМ + НЕТ + +
13. Дискретно-событийный подход + + + +
14. Полный цикл управления
— Реакция на внешнее событие + + НЕТ НЕТ
— Планирование + + + НЕТ
— Диспетчеризация + + + НЕТ
— Пересмотр планов «на лету» + + НЕТ НЕТ
— Ручная корректировка плана + + НЕТ НЕТ
— Интерфейс диспетчера + + НЕТ НЕТ
В целом можно отметить, что подходы отличаются следующим.
1. В подходах используется разное распределение и представление знаний. В ПВ-сети каждый агент владеет только своими знаниями и для решения общей задачи планирования и управления необходима функция коммуникации агентов, тем самым ПВ-сеть представляет систему децентрализованного управления. В системе AnyLogic разработан набор блоков для имитационного моделирования транспортных систем, но нет средств работы со знаниями (онтологиями). В силу того что в МППР и АПП знания обо всем объекте управления находятся в общей БЗ, то МППР представляет в большей степени систему централизованного управления, информация в которую поступает из распределенных источников информации (датчиков остатков топлива, системы мониторинга транспортных средств и корпоративной системы логистического предприятия).
2. Подходы отличаются технической реализацией: последние применения ПВ-сети ориентированы на распределенные вычисления и сети, программная реализация моделей МППР, АПП и система AnyLogic являются локальными СИМ.
3. Задачи планирования и диспетчеризации решаются с помощью ПВ-сетей и модели МППР, система AnyLogic на решение данных задач не ориентирована (требуется программно реализовывать блок планирования). Подход АПП не ориентирован на решение задач планирования и диспетчеризации систем логистики. К недостаткам подхода ПВ-сетей в [4] относится «нервность» при обработке новых событий, поступающих в систему, которая проявляется в следующем: 1) большая часть составленных рейсов корректируется в ходе выполнения (23% всех решений пересматриваются через 1 час после принятия, только 10% всех решений живут более 3 часов) — 2) в целом количество фаз проактивности, давших результат по улучшению расписания, варьируется от 0 до 18% в течение часа- 3) система информирует участников цепи логистики обо всех связанных с ними изменениях, что вносит напряженность. Программная реализация модели МППР усилена блоками агентных эвристик, реализованных на основе продукционной и фреймовой экспертной подсистем, а также блоком диагностики и фильтрации ситуаций, что в целом существенно снижает уровень «нервности» логистической цепи.
Разработка СППР планирования развоза топлива на основе комплекса ВРзіш
Динамическая модель МППР и система БРбіш применяются для решения задачи планирования развоза топлива по сети автозаправочных станций. Сеть предприятия состоит из 24 АЗС. Парк бензовозов — 12. Входными данными задачи являются остатки топлива на АЗС и состояние парка бензовозов. После завершения работы алгоритма планирования пользователь может скорректировать план. В дальнейшем план экспортируется в модуль ИМ и корректируется по результатам имитационного эксперимента. В имитационной модели по каждой емкости АЗС отслеживаются остатки и динамика потребления топлива.
Поступающие события с объекта управления обрабатываются в блоке диагностики ситуаций, на основе результата работы данного блока принимается решение о корректировке плана (не корректировать, корректировать частично, корректировать полностью). Примеры ситуаций: сломался бензовоз, появился новый бензовоз, не работает нефтебаза, появился новый заказ. Структура СППР представлена на рисунке 2.
События
Реальные данные об остатках емкостей Модуль
Тестовые данные об планирования остатках емкостей
Модуль
имитации
Модуль настройки модели
План развоза
-План развоза
Рис. 2. Структура СППР Результаты опытной эксплуатации прототипа СППР показали согласованность результатов вычислительного эксперимента с действиями диспетчера, в условиях изменений на объекте управления.
Заключение
Мультиагентное планирование является результатом гибридизации распределенных вычислений, дискретно-событийного моделирования и экспертных систем. Исследованные в работе два подхода мультиагентного планирования (МППР и ПВ-сети) достаточно хорошо
ориентированы на решение задач логистики. Среди достоинств подхода ПВ-сетей можно отметить масштабную апробацию на логистических объектах.
Работа выполнена в рамках договора № 02. G25. 31. 0055 (проект 2012−218−03−167).
Список литературы
1. Аксенов К. А. Теория и практика средств поддержки принятия решений: монография. — Germany, Saarbrucken: LAP LAMBERT Academic Publishing GmbH & amp- Co. KG, 2011. — 341 с.
2. Борщев А. В. Применение имитационного моделирования в России: мат. 3-й Всерос.
конф. ИММОД 2007. — СПб., 2007. — С. 11−16. — URL:
http: //www. anylogic. ru/upload/iblock/981/98110c406433a4ed72833480ad775068. pdf (дата
обращения: 02. 06. 2013).
3. Москалев И. М. Система анализа и оптимизации процессов преобразования ресурсов: дис. … канд. техн. наук. — Екатеринбург, 2006. — С. 138−150.
4. Скобелев П. О. Мультиагентные технологии для управления ресурсами в реальном времени // Механика, управление и информатика (Таруса, 2−4 марта 2011 г.) — Таруса, 2011. -URL: http: //www. iki. rssi. ru/seminar/2 011 030 204/presentation/20 110 30303. pdf (дата обращения: 02. 06. 2013).
5. Aksyonov K.A., Bykov E.A., Skvortsov A.A., Aksyonova O.P., Smoliy E.F. Intelligent system for scheduling transportation within gas stations network. Proceedings of the 2012 Winter Simulation Conference (WSC 2012). — Berlin, Germany. 2012. — URL: http: //informs-sim. org/wsc12papers/includes/files/pos194. pdf (дата обращения: 02. 06. 2013).
6. Aksyonov K.A., Bykov E.A., Wang Kai, Aksyonova O.P. Application of simulation-based decision support systems to optimization of construction corporation processes. Proceedings of the 2012 Winter Simulation Conference (WSC 2012). — Berlin, Germany, 2012. — URL: http: //informs-sim. org/wsc12papers/includes/files/pos172. pdf (дата обращения: 02. 06. 2013).
7. Kowalski M., Zelewski S., Bergenrodt D., Klupfel H. Application of new techniques of artificial intelligence in logistics: an ontology-driven case-based reasoning approach // Proceedings of ESM'-2012 (ESM — European Simulation and Modelling Conference) October 22−24, 2012, FOM University of Applied Sciences. — Essen, Germany. — P. 323−328.
8. Jennings N.R. On agent-based software engineering // Artificial Intelligence. — 2000, vol. 117, — P. 277−296. — URL: http: //www. agentfactory. com/~rem/day4/Papers/AOSE-Jennings. pdf (дата обращения: 02. 06. 2013).
9. Wooldridge M. Agent-based software engineering // IEEE Proc. Software Engineering. — 1997, № 144 (1). — P. 26−37.
Рецензенты:
Поршнев С. В., д.т.н., профессор, заведующий кафедрой радиоэлектроники
информационных систем, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина», г. Екатеринбург.
Доросинский Л. Г., д.т.н., профессор, заведующий кафедрой информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б. Н. Ельцина», г. Екатеринбург.

ПоказатьСвернуть
Заполнить форму текущей работой