Опыт создания промышленных мультиагентных систем для управления мобильными ресурсами

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

ОПЫТ СОЗДАНИЯ ПРОМЫШЛЕННЫХ МУЛЬТИАГЕНТНЫХ СИСТЕМ ДЛЯ УПРАВЛЕНИЯ МОБИЛЬНЫМИ РЕСУРСАМИ

П.О. Скобелев (skobelev@kg.ru)

Институт проблем управления сложными системами РАН и Группа компаний «Генезис знаний», Самара

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

Введение

мультиагентный управление мобильный ресурс

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

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

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

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

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

1. История и особенности разработок

Для разработки мультиагентных систем в сфере транспортной логистики специалистами научно-производственной компании «Генезис знаний» (http://www.kg.ru) в Англии в 2000 году была создана компания Magenta Technology (http://www.magenta-technology.com), соучредителями которой стали два крупных Европейских инвестиционных фонда.

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

За прошедший период времени удалось разработать методы и средства динамического планирования [Скобелев, 2002], [Виттих и др., 2003], [Виттих, 2009], создать мультиагентную платформу для создания промышленных систем [Андреев и др., 2003], [Rzevski и др., 2007] и целое семейство динамических планировщиков мобильных ресурсов первого поколения для решения задач управления сложными транспортными сетями в реальном масштабе времени в самых различных сферах транспортной логистики [Rzevski и др., 2006], [Андреев и др., 2006].

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

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

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

Разработанная технология, позволяющая работать по событиям, легко интегрируется с современными системами спутниковой ГЛОНАСС/GPS навигации, базами данных о движении мобильных объектов, устройствами мобильной связи, электронными картами, а также любыми Интернет-сервисами, например, предоставления оперативных данных о погоде или пробках на дороге.

2. Краткое описание основных внедрений

Созданные мультиагентные планировщики были разработаны и внедрены для управления крупнейшим в мире танкерным флотом [Himoff и др., 2005], одним из крупнейших в Англии парков грузовиков [Himoff и др., 2006], самым большим парком корпоративных такси в Англии [Glashenko и др., 2009], сдачей машин в аренду [Rzevski, 2009] и ряде других приложений.

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

Например, разработанная мультиагентная система планирования и оптимизации корпоративных такси позволяет автоматически планировать 13 тысяч заказов в день на 800 машин, оснащенных средствами GPS-навигации, взаимодействуя с водителями через мобильные телефоны. В результате внедрения уже в первый месяц число реализованных заказов увеличилось на 7% при том же парке машин, теперь 97% всех заказов такси планируются автоматически, без участия диспетчеров; в 3,5 раза (до 2%) снизилась доля заказов, выполненных не вовремя; на 22,5% уменьшился холостой пробег такси, каждое такси теперь выполняет по 2 дополнительных поездки в неделю при тех же затратах времени и горючего, что отразилось в повышении доходности от каждой машины на 5%; заказ такси происходит на 40% быстрее; время подготовки новых операторов снизилось в 4 раза; более эффективно заработал веб-сайт, через который сейчас проходит уже около 16% заказов компании.

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

§ Продажа инновационных разработок требует участия разработчиков и занимает много времени (от 3 до 18 месяцев);

§ Критически важные для бизнеса приложения требуют затрат времени примерно в 3 раза больше, чем ожидается в начале проекта;

§ Объем разработки мультиагентной системы управления («движка») занимает не более 25% общего времени, все остальное время тратиться на вопросы, связанные с базами данных, интерфейсом пользователя и т.д.;

§ Разработка первой версии мультиагентной системы для управления ресурсами занимает от 3 до 6 месяцев;

§ Внедрение разработки часто занимает больше времени, чем сама разработка;

§ Примерное соотношение затрат труда (человеко-месяцев) по основным фазам проекта (на примере системы для аренды машин): проектирование - 10, разработка - 60, тестирование - 20, поставка и внедрение - 40 (на 6 станциях);

§ Разработанная система должна «выжить» в условиях постоянных ошибок пользователей;

§ Пользователи должны быть мотивированы на внедрение системы, в идеале, оплачиваться по результатам внедрения;

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

Кроме того, при разработке мультиагентных систем для управления ресурсами, базирующихся на использовании принципов самоорганизации и эволюции, возникает ряд новых дополнительных методических проблем [Rzevski и др., 2007], которые не так просто, но очень важно решать в условиях коммерческих разработок:

в условиях постоянных изменений в реальном времени очень трудно оценить, насколько текущее решение далеко от «оптимального»;

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

«эффект бабочки»: малые изменения на входе системы приводят к неожиданным для наблюдателя большим изменениям на выходе (как например в случае «катастроф» - больших структурных перестроек расписаний, возникающих спонтанно в произвольные моменты времени);

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

при повторном запуске, при казалось бы, тех же самых входных данных решение на выходе может оказаться другим (трудно создать «те же самые» входные условия, когда система никогда не останавливается);

в силу эволюционного подхода решение невозможно «откатить» назад, поскольку ситуация, как правило, непрерывно меняется;

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

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

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

Возможность перехода предприятий к экономике реального время, где каждое решение стоит денег;

Повышение качества обслуживания, снижение затрат денег и времени, уменьшение рисков и штрафов;

Решают сложные задачи планирования в производственных и транспортных сетях за счет перехода от перебора - к выявлению конфликтов и поиску компромиссов;

Поддерживают непрерывное перепланирование в реальном времени с быстрой реакцией на события;

Обеспечивают индивидуальный подход к планированию для каждого заказа и ресурса;

Поддерживают двустороннее взаимодействие с пользователями;

Помогают снизить зависимость от персоналий в принятии решений (человеческий фактор);

Снижают затраты на разработку за счет повторного использование кода при переходе к новым сферам применений;

Дают возможность моделирования «если-то» сценарии для оптимизации бизнеса;

Создают масштабируемую платформу для роста бизнеса.

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

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

В ходе проведенных исследований и разработок был получен первый опыт промышленных применений мультиагентных технологий и выработаны новые направления развития платформы для промышленных мультиагентных систем в области управления мобильными ресурсами (табл.1).

В этой связи в НПК «Генезис знаний», реорганизуемой в настоящее время в Группу компаний, совместно с ИПУСС РАН, СПИИРАН, ИМАШ РАН и ИПУ РАН в 2009-2010 году начата разработка мультиагентной платформы нового поколения, реализуемой в среде .Net.

Ожидаемые научные результаты от разработки новой платформы:

Развитие мультиагентного подхода для ситуативного управления мобильными ресурсами в реальном времени;

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

Разработка и реализация мультиагентных программных систем управления ресурсами нового поколения, базирующих на фундаментальных принципах самоорганизации и эволюции (bio-inspired);

Построение нового класса интеллектуальных систем в области транспортной логистики, использующих концепцию эмерджентного («вспыхивающего») интеллекта - как автокаталитической реакции в самоорганизующейся системе, возникающей спонтанно в произвольный момент времени и распространяющейся как «волна» изменений в расписании;

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

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

Табл. 1.

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

Заключение

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

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

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

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

[Андреев и др., 2003] Андреев В., Виттих В., Батищев С., Ивкушкин К., Минаков И., Ржевский Г., Сафронов А., Скобелев П. Методы и средства создания открытых мультиагентных систем для поддержки процессов принятия решений // Известия Академии наук. Теория и системы управления. 2003. № 1.

[Андреев и др., 2006] Андреев В.В., Глащенко А.В., Иващенко А.В., Иноземцев С.В., Скобелев П.О., Швейкин П.К. Мультиагентные системы адаптивного планирования мобильных ресурсов. // В трудах IV Международной конференции по проблемам управления (МКПУ-IV) - ИПУ РАН, 2009.

[Виттих и др., 2003] Виттих В.А., Скобелев П.О. Мультиагентные модели взаимодействия для построения сетей потребностей и возможностей в открытых системах. // Автоматика и телемеханика. 2003. №1.

[Виттих и др., 2009] В.А. Виттих, П.О. Скобелев. Метод сопряженных взаимодействий для управления распределением ресурсов в реальном времени // Автометрия. 2009. №2.

[Скобелев, 2002] Скобелев П.О. Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений. // Автометрия. 2002. №6 .

[Glashenko и др., 2009] A.Glashenko, A.Ivashenko, G Rzevski, P Skobelev. Multi-Agent Real Time Scheduling System for Taxi Companies - Proceedings of 8-th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2009). Hungary, Budapest, May 2009.

[Himoff и др., 2005] Himoff J., Skobelev P., Wooldridge M. Magenta Technology: Multi-Agent Systems for Ocean Logistics. // Proceedings of 4-th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2005). - Holland, July 2005.

[Himoff и др., 2006] Himoff J., Rzevski G., Skobelev P. Multi-Agent Logistics i-Scheduler for Road Transportation // Proceedings of 5-th International Conference on Autonomous Agents and Multi Agent Systems (AAMAS 2006). - Japan, May 2006.

[Rzevski и др., 2007] Rzevski G., Skobelev P., Andreev V. MagentaToolkit: A Set of Multi-Agent Tools for Developing Adaptive Real-Time Applications // Proceedings of 4-th International Conference on Holonic Approach and Multi Agent Systems (HoloMAS 2007). - Germany, June 2007.

[Rzevski и др., 2006] Rzevski G., Himoff J., Skobelev P. Magenta Technology: A Family of Multi-Agent Intelligent Schedulers. // Proceedings of Workshop on Software Agents in Information Systems and Industrial Applications 2(SAISIA). - Fraunhofer IITB, Germany, February 2006.

[Rzevski и др., 2009] Rzevski G., Skobelev P., Yankov I. Multi-Agent Scheduler for Rent-A-Car Business. - Proceedings of 6-th International Conference on Holonic Approach and Multi Agent Systems (HoloMAS 2009). - Germany, Springer, August 2009.

[Rzevski и др., 2007] Rzevski G., Skobelev P. Emergent Intelligence in Large Scale Multi-Agent Systemsю // International Journal Of Education And Information Technologies. 2007. Vol. 1. Issue 2.

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