Scientific journal
Modern problems of science and education
ISSN 2070-7428
"Перечень" ВАК
ИФ РИНЦ = 1,006

MULTI AGENT SIMULATION AND SCHEDULING OF LOGISTIC

Aksenov K.A. 1 Nevolina A.L. 1 Aksenova O.P. 1 Smoliy E.F. 1
1 Ural Federal University named after First President of Russia B.N. Yeltsin
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.
resources conversion process
logistic
scheduling
simulation
multi agent system

Введение

Одним из прикладных направлений мультиагентных технологий является планирование. Понятие агент соответствует аппаратно или программно реализованной сущности, которая способна действовать в интересах достижения целей, поставленных перед ней владельцем и/или пользователем, и которая обладает определенными интеллектуальными способностями [8; 9].

В [8] обсуждается пример применения мультиагентной системы (МАС) для планирования работы гибкой производственной системы. К преимуществам обсуждаемой мультиагентной системы планирования отнесены следующие: 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.

Рис. 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) система информирует участников цепи логистики обо всех связанных с ними изменениях, что вносит напряженность. Программная реализация модели МППР усилена блоками агентных эвристик, реализованных на основе продукционной и фреймовой экспертной подсистем, а также блоком диагностики и фильтрации ситуаций, что в целом существенно снижает уровень «нервности» логистической цепи.

Разработка СППР планирования развоза топлива на основе комплекса BPsim

Динамическая модель МППР и система BPsim применяются для решения задачи планирования развоза топлива по сети автозаправочных станций. Сеть предприятия состоит из 24 АЗС. Парк бензовозов - 12. Входными данными задачи являются остатки топлива на АЗС и состояние парка бензовозов. После завершения работы алгоритма планирования пользователь может скорректировать план. В дальнейшем план экспортируется в модуль ИМ и корректируется по результатам имитационного эксперимента. В имитационной модели по каждой емкости АЗС отслеживаются остатки и динамика потребления топлива.

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

Рис. 2. Структура СППР

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

Заключение

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

Работа выполнена в рамках договора № 02.G25.31.0055 (проект 2012-218-03-167).

Рецензенты:

Поршнев С.В., д.т.н., профессор, заведующий кафедрой радиоэлектроники информационных систем, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.

Доросинский Л.Г., д.т.н., профессор, заведующий кафедрой информационных технологий, ФГАОУ ВПО «Уральский федеральный университет им. первого Президента России Б.Н. Ельцина», г. Екатеринбург.