Группа компаний «Генезис знаний»

& НПК «Разумные решения»

Д.т.н.. П.О.Скобелев

Мультиагентные технологии

для управления ресурсами предприятий

в реальном времени

Слабые, но множественные силы, творят чудеса. А.И. Коновалов

Таруса, 3 Марта 2011

Содержание

Немного истории

Современная постановка задачи управления ресурсами в

реальном времени

Мультиагентный подход к решению сложных задач управления ресурсами в реальном времени Примеры промышленных внедрений первого поколения Мультиагентная платформа нового поколения Текущие проекты Преимущества подхода Перспективы Немного истории 1990 г. – начало научного сотрудничества Самарских филиалов ИМАШ РАН и ФИАН с Открытым университетом (г. Лондон) в области мультиагентных систем 1991 – 1996 гг. – создание научно-производственной компании «АртЛог» для разработки и применения мультиагентных систем в образовании 1997 г. – создание научно-производственной компании «Генезис знаний» для разработки мультиагентных систем в сфере социальных сервисов е-Правительства для населения 2000 г. – создание на базе НПК «Генезис знаний» компании Magenta Technology (UK), получившей венчурное инвестирование со стороны Европейских фондов 2001 – 2008 гг. – создание в Magenta Technology (UK) промышленных мультиагентных систем на платформе первого поколения по управлению мобильными ресурсами:

танкерами, грузовиками, такси, сдачей машин в аренду и ряда других 2009 г. – образование группы компаний «Генезис знаний», создание научнопроизводственной компании «Разумные решения» (Smart Solutions), специализированной для задч управления ресурсами, и, совместно со СПИИРАН, развертывание работ по разработке отечественной платформы второго поколения для построения мультиагентных систем для управления ресурсами в реальном времени 2009 - формирование союза научных учреждений ИПУСС РАН, СПИИРАН, ИМАШ РАН, ИПУ РАН и НПК «Разумные решения» для совместных исследований и разработок на новой отечественной платформе для создания промышленных мультиагентных систем 2009 - 2010 г. – первые отечественные проекты по созданию промышленных мультиагентных систем в интересах отечественного аэрокосмического комплекса, производственных и транспортных предприятий 15 июня 1990 – в начале было слово … Проф. Г.А.Ржевский (Открытый университет, Лондон) Рост численности сотрудников в 2000- и проф. В.А.Виттих (ИПУСС РАН, Самара) N u m b e r o f p e o p le 100 20 1999 2000 2001 2002 2003 2004 2005 2006 В офисе компании Magenta Technology (Самара) Years Новые вызовы глобальной экономики Растет сложность принятия решений по управлению бизнесом Неопределенность: трудно предсказать изменения спроса и предложения Событийность: часто случаются события, которые меняют планы Ситуативность: решение надо принимать по ситуации Многофакторность: много разных критериев, предпочтений и ограничений Высокая связность: принятие одного решения вызывает изменение других Индивидуальность: потребители требуют все более индивидуального подхода Конфликты: все больше участников с противоречивыми интересами Трудоемкость: слишком много опций, чтобы просчитать последствия Усиливается динамика принятия решений в ходе управления Требуется высокая оперативность для принятия решений Идут постоянные изменения спроса и предложения Сокращается время на ответ - решения принимаются под прессом времени Необходимо постоянно балансировать между разными критериями Надо непрерывно считать экономику вариантов и менять цены динамически Нужны постоянные взаимодействия с клиентами и поставщиками … Эти особенности требуют новых методов и средств для принятия решений в реальном времени Современная постановка задачи управления мобильными ресурсами в реальном времени Пункт отправки Повышение эффективности ресурсов Усложнение задачи управления грузовиками для Европейской транспортной сети Объем: Срок: 2 дня Особенности задачи управления грузовиками Планирование в реальном времени Большие объемы (> 1000 заказов ежедневно, > 100 пунктов назначения, > 50 транспортных средств) «Плавающие» и «стягивающиеся» временные окна Заказы меньшего объема, чем один грузовик, требуют эффективной консолидации Необходимость поиска решений, сбалансированных по разным критериям Интенсивные перегрузки товара на складах Обмен прицепами Множественные ограничения по типам, доступности, габаритам, совместимости грузов и транспортных средств Необходимость индивидуального подхода к крупным клиентам Собственные и арендованные транспортные средства Жёсткие и гибкие графики Зависимые расписания (прицепов, водителей и др.) Экономическая оценка вариантов в реальном времени Постоянная эволюция сети Сложность задачи такова, что планирование работы большинства крупных транспортных Мультиагентный подход для решения сложных задач управления ресурсами Последовательное выполнение Параллельное выполнение Стремление уменьшать сложность Стремление наращивать сложность Одновременно активные программы (сопрограммы) Сети потребностей и возможностей для построения самоорганизующихся систем (ПВ-сети) Постоянный поиск соответствий между конкурирующими и кооперирующими агентами потребностей и возможностей на виртуальном рынке системы позволяет строить решение любой сложной задачи как динамическую сеть связей, Пример ситуативной модели выявления конфликта и поиска компромиссов Агент заказа из А в В через Z выбирает грузовик с минимальным объемом, чтобы более выполнить более экономичный маршрут, но едет обратно пустой Что будет, если далее приходит заказ из В в А, для которого требуется грузовик большего размера – ведь изменение размера грузовика может повлечь потерю прибыльности первого заказа Второй заказ обращается к агенту маршрута и тот должен решить:

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

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

Отказать новому заказу – тогда будет создан другой новый маршрут и по нему напрямую поедет пустой грузовик в В и потом в А Если потеря прибыли от первого заказа оказывается меньше, чем выигрыш от второго, то второй должен быть принят в маршрут с увеличением размера грузовика Если нет, то принимается вариант, когда надо послать второй грузовик в точку В для поездки в А Пример компромисса: один Пример без компромисса: для выполнения грузовик используется для двух второго заказа используется отдельный Принцип баланса интересов: решение принимается, если бонус за новое распределение одних ресурсов превышает сумму штрафов за нарушение предпочтений и ограничений других Логика мультиагентного планирования •Есть начальное расписание •Поступает новый заказ •Предварительный просмотр •Новый заказ «будит» агента Грузовика 3 и начинает с ним переговоры •Грузовик 3 оценивает возможность принятия заказа Грузовик •Грузовик 3 «будит» агента Заказа •Заказ 3 анализирует ситуацию и Сдвинешься сдвинуться вправо Заказа 3 и взять новый заказ •Заказ 3 начинает переговоры о новом перевозчике и затем размещается на Грузовике путем сдвига Заказа Расширенный список агентов ПВ-сети мира транспортной логистики Агент заказа Ищет лучшие варианты размещения на грузовиках (например, по цене) Агент грузовика Ищет заказы для увеличения эффективности своего использования Агент стороннего Ищет стороннего перевозчика с лучшим соотношением цены и качества перевозчика Агент маршрута Ищет лучший маршрут для поездки (минимальной длины) Агент водителя Ищет поездки, удовлетворяющие предпочтениям водителя (длинные Агент техосмотра Ищет возможности сделать профилактический осмотр грузовика Агент топлива Ищет лучшие возможности для заправки машины по маршруту следования Финансовый агент Выбирает варианты оплаты внешним перевозчикам (например, минимум Агент груза Проверяет условия транспортировки (наличие машины с холодильником) Агент диспетчер Выбирает политику активации агентов Агент компании Следит за интересами компании и переключает стратегии другим агентам Пример хода переговоров по подвижкам (1/3) Шаг Шаг Шаг 1 и 2. Проведение переговоров при поступлении нового заказа:

Заказ 4 меняет свое положение и смещается вправо Пример хода переговоров по подвижкам (2/3) Шаг Шаг Шаг 3. Дальнейшие переговоры: в результате переговоров внутри Пример хода переговоров по подвижкам (3/3) Шаг Шаги 4 и 5. Достижение итогового решения: в результате переговоров Заказ 1 смещается влево и Заказ 4 размещается без конфликтов с Логика мультиагентной маршрутизации через склады промежуточного хранения Рассмотрим логистическую сеть некоторой компании 1.Заказ1 следует из C в Z 2.Заказ2 следует из B в X 3. Появляется Заказ3, следует из A в Z 4.Заказ3 решает следовать в B и затем присоединиться к Заказу2 на Базе 5.Появляется Заказ4, следует из A в Y 6.Заказ3 решает следовать по первому плечу совместно с Заказом4 и по второму плечу – с Заказом1, чтобы избежать одиночной перевозки из A в B Общее описание мультиагентного подхода к планированию в реальном времени Работа системы строится по событиям, приходящим в реальном времени Расписание самоорганизуется в ходе работы системы: агенты работают асинхронно и квазипараллельно, анализируя и перестраивая сцену путем установления или пересмотра связей Решения агентами принимаются эволюционно, при этом изменяются принятые ранее решения Реакция на событие в форме цепочка (волны) изменений решений может возникать и спонтанно, в заранее не предвиденные моменты времени, лавинообразно самоускоряясь (автокатализируясь);

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

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

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

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

Работа на исторических данных требует восстановления контекста ситуаций;

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

«Эффект бабочки»: малые изменения на входе системы приводят к неожиданным для наблюдателя большим изменениям на выходе;

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

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

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

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

Решение системы иногда трудно объяснить пользователю («интерференция»

влияний и потеря причинно-следственных связей) Перспективным представляется совместная работа пользователя и системы в интерактивной «доводке» решения;

Мультиагентная платформа для управления ресурсами в реальном времени • Основаны на семантическом Веб • Знания отделены от кода • Позволяют описать объекты и связи • Дают возможность описывать ситуации Первые крупные промышленные проекты Мультиагентная система для управления танкерами для компании Tankers International (UK);

Мультиагентная система для управления грузовиками для компании GIST (UK);

Мультиагентная система для управления такси для компании Addison Lee (UK);

Мультиагентная система для управления сдачи машин в аренду для компании Avis (UK);

Мультиагентная система для оптимизации Интернет компаний (UK).

Пример внедрения в GIST Параметры транспортной сети:

4500 заказов в день Сложная структура заказов Множество возможных консолидаций заказов Малое число заказов, дающих полную загрузку Малое число заказов, от которых можно отказаться Важность заказов требует комплексного планирования – цена ошибки велика 600 мест назначения Множество мелких заказов 3 перевалочные базы 9 пунктов обмена прицепов 140 собственных грузовиков различного типа 20 привлеченных транспортных средств Графики доступности привлеченного транспорта Различные схемы оплаты Проблемы, требующие решения:

Окна доступности пунктов назначения Обратные загрузки Консолидация Множество ограничений Непрерывный режим планирования Динамическая маршрутизация Перевалки грузов Смена водителей Интерфейс пользователя мультиагентной системы управления грузовиками Основные преимущества (До/После)

ДО ВНЕДРЕНИЯ ПОСЛЕ ВНЕДРЕНИЯ

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

скрытых в умах экспертов Легкость добавления новых знаний Трудность быстрого рассмотрения Выбор приемлемого варианта с вариантов с разных точек зрения Пример внедрения в Addison Lee Компания «Аддисон Ли» оснащена современной ERP системой и CALL центром, объединяющем более чем 130 операторов, получающих и обрабатывающих заказы одновременно Весьма большой флот в более чем 2,000 бортов (каждый оснащен системой GPS навигации).

В любой момент около 700 водителей работают одновременно, конкурируя и борясь за заказы.

Более 13 000 заказов в день; поток заказов периодически превышает уровень в 1500 заказов в час; время поступления заказа и место назначения непредсказуемо До 18% заказов с введением адаптивного планировщика поступают через Интернет сайт компании Компания гарантирует прибытие борта к клиенту в центре Лондона в течение 15 минут с момента размещения заказа Водители Freelance арендуют машину у компании и работают в удобное им время, которое в разные дни может быть разным Разнообразие типов клиентов (частные лица, корпоративные, VIP, с различными тарифами с специальными требованиями к водителям и бортам (кресла для детей, места для инвалидов, перевозка домашних животных, …) Учитывается множество параметров заказа: места посадки и высадки, срочные и предварительные заказы, разные виды сервиса, важность (приоритет от 0 до 100 в зависимости от заказчика), специальные требования (детское кресло им т.п.) Разные транспортные средства: «минивэны» и «кэбы», некоторые со специальным оборудованием Экран бронирования машины Экран мониторинга выполнения заказа Экран планирования машин Пример внедрения в Addison Lee В первые 3 месяца после внедрения были получены результаты:

Количество обработанных заказов увеличилось на 7% при том же флоте Автоматически стали планироваться 98,5% всех заказов;

Количество потерь заказов сократилось на 2% до 3,5%;

Пустой пробег сократился на 22,5%;

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

Прибыльность возросла на 4,8%, при этом доходы водителей выросли на 9%, а также появилась возможность расширить флот;

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

Полная окупаемость проекта - около 6 месяцев от внедрения в штатную эксплуатацию Сюжет о данном проекте показан Первым каналом в программе «Время» о необходимости скорейшего внедрения ГЛОНАСС с показом интервью Российских сотрудников Мадженты в офисе Аддисон Ли в Лондоне в 2008 году Компания Аддисон Ли выдвинула разработанное решение на Национальную премия «Оскар в бизнесе» в 2008 году и победила!

Пример внедрения в Avis Проблемы управления машинами и водителями • Высокая сложность планирования для менеджеров • Взаимозависимости расписаний • Много непредвиденных событий (задержки и т.д.) • Высокая динамика событий • Низкая эффективность использования ресурсов сочетается с большими переплатами за внеурочное время • Требуется опытные менеджеры • Локальная оптимизация работы станций • Неэффективное распределение флота по станциям • Нет прозрачности, дисциплины и контроля • Нет возможности расширения бизнеса Мультиагентная система сдачи машин в аренду 1. Клиент звонит в • Получают • Выполняют 6. Менеджер станции контролирует процесс и необходимости Примеры правил принятия решений агентами Матрица допустимых изменения классов машин Примеры критериев принятия решений Менеджеры центрального офиса могут изменять штрафы за нарушение критериев Штрафы помогают агентам сравнивать опции, преодолевать Интерфейс менеджера станции Показывает очередь событий и расписания всех водителей Карта с запланированными операциями сбора и поставки машин Маршруты поездок водителей Заказы и состояние их выполнения Число входных событий в обычный день (по часам) number of events per hour В среднем для 6 станций – более 150 событий в час (для 120 заказов в день и 150 машин на станции) Около 39% всех событий связаны с доступностью и недоступностью ресурсов Эффективность фазы проактивности Green – фазы, давшие результат по улучшению расписания Red – не успешные фазы Blue – фазы, прерванные новым внешним событием Среднее время по классам событий • Большинство событий обрабатываются менее 3 сек • Задержка водителя обрабатывается в среднем около 5 сек • 23% всех решений пересматриваются через 1 час после принятия • Только 10% всех решений живут более 3 часов Результаты измерений, показывающие динамику принятия решений (на 6 станциях) Число заказов в день на станцию 15- Среднее % опозданий Диапазон числа событий в час Время обработки события Среднее число задач, запланированных для одного заказа Drop фактор Объем переговоров (число сообщений) на обработку 1 заказа Число постоянно активных агентов Число опций на одно решение Полученные результаты Текущее состояние разработки: опытная эксплуатация в первых станциях в Великобритании • Увеличение объема выполненных заказов • Сокращение внеурочной работы водителей (переработки) • Сокращение трудоемкости Station Managers • Качество обслуживания клиентов (меньше ошибок с классами машин и опозданий) • Сокращение времени реакции на непредвиденные события • Полная прозрачность сети станций • Улучшение бизнеса за счет повышения эффективности использования флота станций;

• Сокращение человеческого фактора при принятии решений Ближайший план – доработки по уменьшению «нервности» системы и внедрение в других станциях (2010-2011) Новые проекты Новые проекты 2009- РКК «Энергия»

Динамическое планирование программы полетов и грузопотока МКС ЦСКБ-Прогресс, Тяжмаш, Ижевский мотозавод Внутрицеховое планирование станков и рабочих в реальном времени Транспортные компании «РусГлобал» и «Пролоджикс», EI Tech (USA) Динамическое планирование грузовых перевозок на основе средств GPS навигации Airbus/Университет г. Кёльна, Германии Моделирование процессов управления наземными сервисами аэропорта на основе RFID-чипов Минобрнауки России Динамический планировщик задач пользователей мобильных телефонов РФФИ Коллективное управление роем спутников Dynamic IT Управление рисками страховых компаний Мультиагентная платформа нового поколения Конструкция агента, поддер- Возможность индивидуального управления агентами Динамическая диспетчери-зации, планирования, исполнения Виртуальный рынок агентов, Повышение оперативности и гибкости, качества и Ускорение или торможение процессов основанный на нелинейной эффективности планирования в реальном времени, переговоров и саморегуляция других планировщиков реального производительность, _асштабируемость, надежность и поставок как распределенной р2р сетью времени, демонстрирующих живучесть системы управления предприятием адаптивных планировщиков отдельных Динамически формируемые Возможность обучать и наращивать базу знаний Система в диалоге с водителем узнает о пользователями («снизу-вверх») интеллекта» предприятия, в устойчивости и конкуренто-способности бизнеса сотового сообщать об скоплении активно участвует в управлении Интерактивное взаимодействие с Интеллектуализация диалога с пользователем, легкость Позволяет пользователю дорабатывать системой, в ходе которого и удобство перестройки любых фрагментов решения в диалоге с системой решение задачи ищется совместно расписания Поддержка работы в случае Недостаток данных или ошибки не являются Большая устойчивость и надежность неопределенности ситуации или препятствием для продолжения работы системы работы системы при некорректных Платформа для поддержки Повышение производительности создаваемых систем Планирование большого числа Мультиагентная система управления Десятки стартов, тысячи единиц грузов, сотни событий … Задержка по погодным условиям старта в США вызывает цепочку сдвигов полетов на Российском сегменте, пересчет дат стартов, состава грузопотока, снижение станции, увеличение запаса топлива на следующих ракетах и т.д.

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

Необходимо учитывать при автоматическом планировании взаимосвязи между всеми элементами плана (грузами, транспортными средствами, доставками топлива и воды, ограничениями по стыковке и отстыковке) Требуется создание 8 основных АРМов и целый набор АРМов поставщиков В дальнейшем возможна автоматизация управления ресурсами во всей цепочке поставок Экран конструктора онтологий Подход к построению МАС цеха Экраны построения программы полетов Экраны построения грузопотока Подход к построению МАС цеха Экраны баланса (на примере воды) Преимущества разработанного подхода Позволяет предприятиям переходить к экономике реального времени Повышает эффективность ресурсов, качество обслуживания, снижает затраты денег и времени, риски и штрафы Решает сложные задачи планирования в производственных и транспортных сетях за счет перехода от перебора - к поиску конфликтов и компромиссов Поддерживает непрерывное перепланирование в реальном времени с быстрой реакцией на событиям Обеспечивает индивидуальный подход для каждого заказа и ресурса Поддерживает двустороннее взаимодействие с пользователями Помогает снизить зависимость от персоналий в принятии решений Снижает затраты на разработку за счет повторного использование кода при переходе к новым сферам применений Дает возможность моделирования «если-то» для оптимизации решений Создает масштабируемую платформу для роста сложности решаемых задач и развития бизнеса Перспективы That Was Then This is Future Batch Optimizers Rules Engines Constraints Visualize Модели, методы и средства Скобелев П.О. Открытые мультиагентные системы для оперативной обработки информации в процессах принятия решений. // Автометрия. – 2002. - №6. - C. 45-61.

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

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

G.Rzevski, P. Skobelev, V.Andreev. 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.

G. Rzevski, J. Himoff, P. Skobelev. 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.

George Rzevski, Petr Skobelev. Emergent Intelligence in Large Scale Multi-Agent Systemsю - INTERNATIONAL JOURNAL OF EDUCATION AND INFORMATION TECHNOLOGIES. - Issue 2, Volume 1, 2007.

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

Практические приложения 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.

J. Himoff, G Rzevski, P Skobelev. 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.

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

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;

I.Yankov, G Rzevski, P Skobelev. 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.

Спасибо за внимание!

Для дополнительной информации:

www.smartsolutions-123.ru Скобелев Петр Олегович [email protected] Сотовый тел.: +7 929 702 22