🗊Группа компаний «Генезис знаний», ИПУСС РАН и НПК «Разумные решения» Мультиагентные технологии для управления ресурсами в практи

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

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

В офисе компании Magenta Technology (Самара)

Новые вызовы экономики реального времени Растет сложность принятия решений по управлению бизнесом Неопределенность: трудно предсказать изменения спроса и предложения Событийность: часто случаются события, которые меняют планы Ситуативность: решение надо принимать по ситуации Многофакторность: много разных критериев, предпочтений и ограничений Высокая связность: принятие одного решения вызывает изменение других Индивидуальность: потребители требуют все более индивидуального подхода Конфликты: все больше участников с противоречивыми интересами Трудоемкость: слишком много опций, чтобы просчитать последствия Усиливается динамика принятия решений в ходе управления Требуется высокая оперативность для принятия решений Идут постоянные изменения спроса и предложения Сокращается время на ответ - решения принимаются под прессом времени Необходимо постоянно балансировать между разными критериями Надо непрерывно считать экономику вариантов и менять цены динамически Нужны постоянные взаимодействия с клиентами и поставщиками …

Мультиагентная технология для управления ресурсами в реальном времени Иерархии больших программ Последовательное выполнение операций Инструкции сверху вниз Централизованные решения Управляются данными Предсказуемость Стабильность Стремление уменьшать сложность Тотальный контроль

Мультиагентный подход в военном деле

Развитие мультиагентного подхода Начало в 1970-ые годы… Объектно-ориентированное программирование, искусственный интеллект, параллельные вычисления, телекоммуникации Традиционно базировались на логике (Wooldridge, etc) Наш подход bio-inspired (Van Brussel, Paulo Letao, etc) но базирующийся на ключевых идеях: Ilya Prigozhin in Physics (auto-catalytic reactions), Marvin Minsky in Psychology (society of mind), Artur Kestler in Biology (holonic systems) Ключевые слова: self-organisation and evolution, synergy, non-linear thermodynamics, collective (emergent) intelligence Первые применения: Internet e-commerce Текущие применения: логистика, извлечение знаний, понимание текста и другие Будущее: Web-Intelligence

Классификации агентов

Примеры МАС компаний Weinestein Technologies – http://www.weinstein.com NuTech – http://www.nutech.com Living Systems – http://www.livingsystems.com AgentBuilder - http:// www.agentbuilder.com Quarterdeck - http:// arachnid.qdeck.com GeneralMagic - http://www.genmagic.com Intelligent Reasoning System - http://members.home.net:80/marcush/IRS BiosGroup – http: www.eurobios.com LostWax – http://www.lostwax.com Около 30 компаний на рынке. Более 100 университетских проектов.

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

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

Онтологический подход к описанию ситуаций

Интерактивное взаимодействие с пользователями через мобильное устройство

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

Метод сопряженных взаимодействий с компенсациям

Логика мультиагентного планирования

Модели организации перевозок Модель «С возвращением на базу». Для заказа бронируется грузовик, в расписании которого на момент заказа есть “окно”. Если погрузка осуществляется в другом городе, то грузовик должен прибыть туда ко времени погрузки. Отмена бронирования грузовика под заказ не допускается. После выполнения заказа грузовик возвращается в пункт базирования. Модель «Без возвращения». После выполнения заказа грузовик остается в конечном пункте заказа, не возвращаясь на базу, где ожидает следующий заказ. Модель «Опоздания со штрафами». Допускается планирование заказов с опозданиями, т.е. когда фактический момент начала заказа позже требуемого в заказе. При этом из прибыли вычитаются штрафы, пропорционально времени опоздания. Если величина штрафа превышает возможную прибыль от выполнения заказа, то такой заказ не планируется. После выполнения заказа грузовик остается в пункте назначения. Модель «Адаптивное планирование со штрафами». Совпадает с предыдущей, однако допускается адаптивное перебронирование грузовика под новый заказ в случае, если прибыль от нового заказа превышает прибыль от прежде запланированного. Таким образом, при поступлении заказа осуществляется перераспределение уже размещенных заказов и ищется новое, более выгодное по прибыли решение.

Пример из 4 городов и 5 заказов

Движение грузовика

Планирование 100 заказов

Расчетные оценки эффективности грузоперевозок за счет адаптивности

Оценка роста прибыли компании при переходе к реальному времени

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

Примеры промышленных применений

Первые промышленные проекты в транспортной логистике 2000-2008 Мультиагентная система для управления танкерами для компании Tankers International (UK); Мультиагентная система для управления грузовиками для компании GIST (UK); Мультиагентная система для управления такси для компании Addison Lee (UK); Мультиагентная система для управления сдачи машин в аренду для компании Avis (UK); Мультиагентная ситсема для управления курьерами CitySprint (UK)

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

Примеры промышленных применений

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

Основные преимущества (До/После)

Примеры промышленных применений

Примеры промышленных применений

Примеры промышленных применений

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

Текущие результаты Система начала работать в феврале 2011 и перераспределять ресурсы Введены 140 рабочих и мест оборудования с новым оборудованием для инструментального цеха Каждый день от 30 до 300 заказов приходит, каждый из 5 до 25 операций В целом 25 пользователей вводят информацию, планируют и подтверждают операции, делают отчеты и т.д. На момент 90% тех операций введены и используются в планировании В первые 3 месяца система показала что не менее 17 % работ имеют завышенную трудоемкость или некорректные исходные данные Полная прозрачность позволяет теперь формировать более обоснованно зарплаты и премии Примерно 50% всех заказов считаются автоматически Диспетчеры получили больше времени для улучшения решений Сократилось время для обучения диспетчеров

Примеры промышленных применений

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

Функции системы Ведение справочников бригад и смен База знаний для формализации и накопления особенностей заказов и ресурсов Интеллектуальная поддержка принятия решения диспетчера в выборе ресурсов для выполнения заявок Анализ ситуации в реальном времени Выбор бригады, наиболее подходящей для выполнения задания Построение маршрута движения бригады с учетом дорог, знаков ГИБДД, пробок и т.д. Построение расписание движения бригады и времени доезда Адаптация расписания при возникновении непредвиденных событий Минимизация времени доезда (как можно скорее на важных заявках) Сокращение общего пробега (на заявках низкой значимости) Мониторинг и контроль исполнения задания Оперативное адаптивное планирование работ бригад по событиям в реальном времени (с изменением планов ранее назначенных работ) Обеспечение индивидуального подхода к планированию каждого заказа Отображение маршрутов и расписаний на электронной карте Мониторинг и контроль исполнения бизнес процессов с использованием экономичных мобильных телефонов Перепланирование в случае расхождения плана и факта Интеграция с системой приема заявок (Call Center), учетными системами и другими Построение отчетов по работе бригад

Журнал заявок (цвет – статус)

Заявки и ресурсы показываются на карте

Карта удобно и легко масштабируется

Центральный район с заявками

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

Варианты решений по планированию

Изменения в расписании

Намеченный маршрут исполнения заявок

Изменения по новому событию

Запланированные заявки

Отчет по работе бригад

Динамика показателей консолидированного отчета

Отчет по отклонениям

Отчет по эффективности работ бригад

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

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

Теория сложных систем и «эмержентный» интеллект (вспыхивающий)интеллект» интеллекта»? Каждый агент может иметь степень удовлетворенности связью Когда все агенты удовлетворены и не ищут новых связей – состояние «порядка», когда не удовлетворены, и продолжают состоять в связи – близки к «хаосу», разрывают связи – в состояние «хаоса» (нет связей) В результате расписание формируется как набор неустойчивых равновесий (устойчивых неравновесий») Введение агента расписания, оценивающего состояние в целом, позволяет управлять точечными (адресными) «провокациями» например, разбивая уже сложившиеся фрагменты расписания и давая им возможность сложиться заново (при новых условиях), переключать стратегии агентам потребностей и возможностей и др. Локальные взаимодействия порождают «глобальные структуры» (расписания), которые влияют на поведение образовавших их локальных взаимодействий Новые события порождают, спонтанно, в заранее не известные моменты времени, автокаталитические реакции, самоускоряющие или самозамедляющие процесс реконструкции расписания Число возрастающих сообщений на единицу площади сети можно рассматривать как рост «температуры» самоорганизующейся системы в проблемном участке? Прирост значений показателей за единицу времени (или число тактов реакции) может характеризовать «сложность» и «умность» решения Путь к созданию принципиально нового «искусственного интеллекта» (интеллектуальный резонатор), образованного непростым взаимодействием очень простых агентов?

Общие проблемы разработки МАС Опыт разработки указанных приложений показал следующие важные особенности этого процесса: Продажа инновационных разработок требует участия разработчиков и занимает много времени (от 3 до 18 месяцев); Критически важные для бизнеса приложения требуют затрат времени примерно в 3 раза больше, чем ожидается в начале; Объем разработки мультиагентной системы управления («движка») занимает не более 25% общего времени, все остальное время тратиться на вопросы, связанные с базами данных, интерфейсом пользователя и т.д.; Разработка первой версии мультиагентной системы для управления ресурсами занимает от 3 до 6 месяцев; Внедрение разработки часто занимает больше времени, чем сама разработка; Примерное соотношение затрат труда (человеко-месяцев) по основным фазам проекта (на примере системы для аренды машин): проектирование - 10, разработка – 60, тестирование – 20, поставка и внедрение – 40 (на 6 станциях); Разработанная система должна «выжить» в условиях постоянных ошибок пользователей; Пользователи должны быть мотивированы на внедрение системы, в идеале, оплачиваться по результатам внедрения; Пользователи должны иметь возможность вручную дорабатывать расписания, поскольку всегда есть факторы, которые не представляется возможным учесть при принятии решений.

Преимущества технологии Позволяет создавать интеллектуальные системы нового класса для управления ресурсами в реальном времени Дают результаты, сопоставимые с результатами работы людей; Поддерживают полный цикл управления, присущий автономным живым организмам; Исповедуют новую концепцию «эмерджентного интеллекта», основанного на коллективных взаимодействиях Возможность предприятиям переходить к экономике реального времени Повышает эффективность использования ресурсов, качество обслуживания, снижает затраты денег и времени, риски и штрафы Решает сложные задачи производственного и транспортного планирования за счет перехода от перебора - к поиску конфликтов и компромиссов Поддерживает непрерывное перепланирование в реальном времени с быстрой и гибкой реакцией на событиям Обеспечивает индивидуальный подход для каждого заказа и ресурса Помогает снизить зависимость от персоналий в принятии решений Снижает затраты на разработку за счет повторного использование кода при переходе к новым сферам применений и усложнении решения Дает возможность моделирования «если-то» для оптимизации решений Создает надежную и масштабируемую платформу для роста сложности решаемых задач и развития бизнеса

Сетецентрический подход на основе р2р подхода

Лицензии и дипломы

Выводы

Спасибо за внимание! Для связи: Скобелев Петр Олегович petr.skobelev@gmail.com Сотовый тел.: +7 929 702 22 00