авторефераты диссертаций БЕСПЛАТНАЯ БИБЛИОТЕКА РОССИИ

КОНФЕРЕНЦИИ, КНИГИ, ПОСОБИЯ, НАУЧНЫЕ ИЗДАНИЯ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ


Pages:   || 2 | 3 | 4 |
-- [ Страница 1 ] --

Федеральное агентство связи

Государственное образовательное учреждение

высшего профессионального образования

ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ

ЭЛЕКТРОННАЯ

БИБЛИОТЕЧНАЯ СИСТЕМА

Самара

1

ФЕДЕРАЛЬНОЕ АГЕНТСТВО СВЯЗИ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

ПОВОЛЖСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ И ИНФОРМАТИКИ КАФЕДРА ИНЖЕНЕРИИ ЗНАНИЙ А.В.Иващенко, А.Н.Лада, Е.В.Симонова, П.О.Скобелев МУЛЬТИАГЕНТНАЯ ТЕХНОЛОГИЯ УПРАВЛЕНИЯ МОБИЛЬНЫМИ РЕСУРСАМИ В РЕЖИМЕ РЕАЛЬНОГО ВРЕМЕНИ Учебное пособие САМАРА ПГУТИ 2011 УДК 004.9 (075) ББК 32. Мультиагентная технология управления мобильными ресур сами в режиме реального времени / А.В.Иващенко, А.Н.Лада, Е.В.Симонова, П.О.Скобелев. Поволжский государственный уни верситет телекоммуникаций и информатики. Самара, 2011 – 177 с.

Учебное пособие предназначено для студентов, обучающихся по специальности 230105 – «Программное обеспечение вычис лительной техники и автоматизированных систем». Рекомендует ся использовать учебное пособие при изучении курсов «Системы искусственного интеллекта», «Мультиагентные системы» и «Мультиагентный подход в управлении распределенными систе мами». Включает разделы, которые подробно описывают совре менное состояние и методы адаптивного планирования, мультиа гентный подход к решению задач динамического планирования ресурсов в реальном времени, архитектуру и реализацию муль тиагентной системы управления транспортными ресурсами. Тео ретический материал иллюстрируется большим количеством примеров динамического планирования. Учебное пособие содер жит контрольные вопросы и упражнения по всем разделам.

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

Табл. 25. Ил. 124. Библиогр.: 88 назв.

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

д.т.н., проф. Смирнов С.В.

© Поволжский государственный университет телекоммуникаций и информатики, СОДЕРЖАНИЕ Введение................................................................................................................. 1 МЕТОДЫ И АЛГОРИТМЫ ПЛАНИРОВАНИЯ РЕСУРСОВ...................... 1.1 Современная постановка задачи управления мобильными ресурсами в режиме реального времени.......................................................... 1.2 Особенности планирования ресурсов в транспортно логистической компании................................................................................... 1.3 Обзор алгоритмов распределения ресурсов.............................................. 1.3.1 Списочные алгоритмы........................................................................... 1.3.2 Алгоритм имитации отжига............................................................... 1.3.3 Генетические алгоритмы...................................................................... 1.3.4 Мультиагентный подход....................................................................... 1.3.5 Сравнительный анализ алгоритмов распределения ресурсов.......... 2 МУЛЬТИАГЕНТНАЯ МОДЕЛЬ АДАПТИВНОГО ПЛАНИРОВАНИЯ МОБИЛЬНЫХ РЕСУРСОВ.............................................. 2.1 Метод адаптивного планирования............................................................. 2.1.1 Сеть потребностей и возможностей................................................. 2.1.2 Метод компенсаций............................................................................... 2.2 Обзор архитектуры мультиагентных систем............................................. 2.3 Мультиагентная платформа планирования............................................... 2.3.1 Онтология – модель знаний предметной области............................. 2.3.2 Агенты мира транспортной логистики........................

...................... 2.3.3 Алгоритм переговоров агентов............................................................ 2.3.4 Реализация мультиагентной платформы планирования ресурсов............................................................................................................ 2.4 Примеры адаптивного планирования заказов в реальном времени........ 3 МУЛЬТИАГЕНТНАЯ СИСТЕМА УПРАВЛЕНИЯ ТРАНСПОРТНЫМИ РЕСУРСАМИ (МАС УТР).............................................. 3.1 Назначение системы..................................................................................... 3.2 Установка и запуск системы....................................................................... 3.3 Начало работы с системой........................................................................... 3.3.1 Интерфейс и главное окно системы.................................................... 3.3.2 Ввод новой заявки................................................................................... 3.3.3 Последовательность действий менеджера по обработке заявки................................................................................................................ 3.4 Управление.................................................................................................... 3.4.1 Управление ресурсами............................................................................ 3.4.2 Управление заявками.............................................................................. 3.4.3 Справочники............................................................................................ 3.4.4 Мониторинг............................................................................................ 3.4.5 Отчеты................................................................................................... 3.4.6 Редактор правил..................................................................................... 3.4.7 Шаблоны печатных форм..................................................................... 4 Цели, задачи и содержание лабораторного практикума................................ 5 Лабораторный практикум.................................................................................. 5.1 Исходная информация для планирования................................................. 5.2 Рассчитываемые показатели планирования ресурсов.............................. 5.3 Лабораторная работа №1. Создание заявок, построение начального плана и последовательное планирование заявок........................ 5.3.1 Создание заявок и построение начального плана............................... 5.3.2 Сценарий последовательного планирования заявок........................... 5.3.3 Индивидуальные задания....................................................................... 5.4 Лабораторная работа №2. Подбор ресурса с минимальным холостым ходом.................................................................................................. 5.4.1 Сценарий планирования заявок на ресурсы с минимальным холостым ходом.............................................................................................. 5.4.2 Индивидуальные задания....................................................................... 5.5 Лабораторная работа №3. Перепланирование заявок по ресурсам в случае появления более выгодной заявки..................................................... 5.5.1 Сценарий перепланирования ресурсов с вытеснением заявок........... 5.5.2 Индивидуальные задания....................................................................... 5.6 Лабораторная работа №4. Планирование заявок по ресурсам в случае недоступности ресурса.......................................................................... 5.6.1 Сценарий перепланирования ресурсов при недоступности ресурса.............................................................................................................. 5.6.2 Индивидуальные задания....................................................................... 5.7 Лабораторная работа №5. Планирование заявок на предпочитаемые ресурсы................................................................................. 5.7.1 Сценарий планирования заявок на предпочитаемые ресурсы........... 5.7.2 Индивидуальные задания....................................................................... 5.8 Лабораторная работа №6. Планирование неприбыльной заявки............ 5.8.1 Сценарий раздельного планирования неприбыльной и прибыльной заявок........................................................................................... 5.8.2 Сценарий совместного планирования неприбыльной и прибыльной заявок........................................................................................... 5.8.3 Индивидуальные задания....................................................................... 5.9 Контрольные вопросы.................................................................................. Заключение............................................................................................................ Библиографический список................................................................................. ВВЕДЕНИЕ Широкое распространение мобильных телефонов и других «наладонных»

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

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

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

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

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

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

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

­ планирование в реальном времени;

­ большие объемы ( 1000 заказов ежедневно, 100 пунктов назначения, транспортных средств);

­ «плавающие» и «стягивающиеся» временные окна;

­ заказы меньшего объема, чем один грузовик, требующие эффективной кон солидации;

необходимость поиска нетрадиционных решений;

­ интенсивные перегрузки товара на складах;

­ обмен прицепами;

­ множественные ограничения по типам, доступности, габаритам, совмести ­ мости грузов и транспортных средств;

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

­ собственные и арендованные транспортные средства;

­ жсткие и гибкие графики доставки грузов;

­ зависимые расписания (прицепов, водителей и др.);

­ экономическая оценка вариантов в реальном времени;

­ постоянная эволюция транспортной сети.

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

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

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

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

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

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

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

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

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

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

При проведении лабораторного практикума рекомендуется использовать учебную версию мультиагентной системы управления транспортными ресур сами (краткое название – МАС УТР). Использование описываемой в данном пособии мультиагентной технологии на примерах транспортной логистики пользоволяет наглядно представить современные возможности по управлению мобильными ресурсами в режиме реального времени.

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

1 МЕТОДЫ И АЛГОРИТМЫ ПЛАНИРОВАНИЯ РЕСУРСОВ 1.1 Современная постановка задачи управления мобильными ресурсами в режиме реального времени Задача управления мобильными ресурсами может быть сформулирована следующим образом и проиллюстрирована Рисунок 1 [1-8]:

­ Имеется флотилия грузовиков (или других мобильных ресурсов), которые могут иметь GPS / ГЛОНАСС датчики на борту;

­ В реальном времени поступают заказы (и другие события), которые необхо димо распределять на ресурсы, учитывая текущие планы, индивидуальные предпочтения и ограничения заказов и ресурсов;

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

­ Должен быть реализован полный цикл управления:

­ реакция на события, ­ динамическое планирование, ­ исполнение планов;

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

­ Необходимо вести мониторинг и контроль исполнения согласованных пла нов;

­ В случае расхождения плана и факта требуется перепланирование.

Система планирования и управления мобильными ресурсами должна обеспечивать перечисленные ниже основные функциональные возможности:

Прим нового заказа. Может осуществляться как в ручном, так и в авто матическом режиме с использованием функции импорта из корпоративной CRM системы. В сфере логистики все новые заказы обычно имеют стандарт ный набор полей, такие как: грузоотправитель и грузополучатель, тип и вес груза, тип транспортного средства, грузоподъмность, адреса и время отгрузки и доставки и другие. Заказы обычно принимаются оператором по телефону, че рез Интернет-портал или по электронной почте (например, от корпоративных клиентов). В связи с этим для регистрации поступающих заказов вручную не обходимо, чтобы у системы был дружественный интерфейс. Кроме того, в про цессе прима заказов должны также учитываться различные категории и типы клиентов. Например, у VIP клиентов могут быть дополнительные требования, которые система должна обязательно принимать во внимание.

Автоматическое планирование новых заказов. Система старается по добрать наилучшее размещение заказа с учтом имеющихся в наличии ресур сов. При этом учитываются различные виды критериев, такие как: протяжн ность маршрута, статус водителя (свободен, с заказом, скоро освободится и др.), объективное распределение выгодных заказов между водителями и другие.

Если невозможно запланировать заказ автоматически, система позволяет сде лать это в ручном режиме.

Рис. Рисунок 1 – Схема функционирования автоматизированной системы управления мобильными ресурсами Обратная связь с водителями. Водители используют специальные уст ройства, чтобы информировать систему о свом актуальном статусе и взаимо действовать с диспетчером при распределении новых заказов.

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

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

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

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

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

Задачи транспортной логистики заключаются в сокращении сроков транспортировки грузов и оптимизации затрат компании на всем пути движе ния грузов при максимально высоком уровне обслуживания посредников и ко нечных потребителей. В коммерческих транспортных организациях, где имеет ся распределенная структура с развитой филиальной сетью и используется большое количество подвижного грузового транспорта, задача по автоматиза ции планирования поездок, управлению подвижными ресурсами, оптимизации материальных и временных затрат на перевозку, контролю и учету операций бизнес-процесса приема и исполнения заявок, а также повышению качества оказываемых услуг в целом становится особенно актуальной с ростом числа клиентов и заказов. Анализ технического оснащения современных транспорт но-экспедиционных компаний показывает, что такие компании представляют собой сложные объекты управления, которые характеризуются значительным числом взаимозависимых ограничений и факторов, обусловленных технологи ческим регламентом и определяющих эффективность работы объекта управле ния, что вызывает определенные трудности при решении задачи планирования выполнения заявки на транспортировку [1-8].

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

Рисунок 2 – Схема взаимодействия по обработке заявки Можно выделить следующие задачи управления, решение которых имеет определяющий характер для компаний, занимающихся оказанием транспортно логистических услуг:

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

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

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

­ Утилизация – отношение времени, потраченного на перемещение до места загрузки и выполнение заявки, к общему рабочему времени в месяц. Необ ходимо, чтобы грузовики не простаивали и постоянно ездили по заявкам (утилизацию надо постоянно повышать);

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

­ Удельная выручка – выручка на километр. Система должна оценивать заяв ки по удельной выручке и сравнивать значение удельной выручки с некото рой граничной величиной. Среди заявок, с удельной выручкой, больше за данной границы, будет выбрана заявка с большей абсолютной выручкой Среди заявок, приблизительно равных по абсолютной выручке необходи мо выбирать те, у которых удельная выручка больше. Из двух заявок, удельная выручка которых больше заданной границы, следует выбирать ту, которая вы годнее по абсолютной выручке. Если, согласно данным, указанным в заявке, один грузовик вынужден будет совершить более протяженный переезд до точ ки погрузки, чем другой, следует выбрать грузовик, находящийся ближе с це лью уменьшения количества «порожних» переездов.

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

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

1.3 Обзор алгоритмов распределения ресурсов Существует множество алгоритмов, на основе которых строятся системы распределения ресурсов. Рассмотрим наиболее известные из алгоритмов рас пределения ресурсов с учетом требований к системам распределения ресурсов как к сложным системам.

1.3.1 Списочные алгоритмы Среди всех алгоритмов распределения ресурсов можно выделить доста точно простые для реализации алгоритмы, которые позволяют запланировать заказ на необходимые ресурсы. К такому типу относятся списочные (приори тетные) алгоритмы [9]. Предположим, что несколько заказов ожидают плани рования. В этом случае заказы выбираются из общего списка и поочередно от правляются на планирование. При планировании заказы выбирают ресурсы и время выполнения либо по критерию наиболее раннего исполнения, либо в со ответствии с другими критериями. Например, выбор рабочего делается на ос нове близости его разряда к необходимому, заданному в технологической опе рации. Заполняя постепенно свободное место операциями, списочный алгоритм строит производственный план до достижения локального оптимума. Критерии выбора из списка могут быть различные [9]. Например, задачи выбираются по принципу очередности прихода в систему (First Come First Served – FCFS). Дру гим критерием может служить приоритет. Вначале планируются те заказы, приоритет которых максимален в очереди (Highest Priority First – HPF).

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

Наконец, может учитываться сложность планирования заказа: сложный заказ, состоящий из множества подзаказов, связанных различными ограниче ниями, необходимо планировать раньше, так как более простые заказы имеют большую степень свободы при планировании. Необходимо также упомянуть и метод Монте-Карло, в соответствии с которым заказы выбираются из очереди в случайном порядке. После планирования осуществляется оценка результирую щего плана. Затем заново повторяются фазы планирования и оценки. Данные операции повторяются до тех пор, пока качество плана не будет удовлетвори тельно, либо выполнится необходимое количество итераций, либо скорость роста качества «лучшего» плана уменьшится до некоторой величины.

Некоторые из вышеприведенных алгоритмов используются также в сис темах реального времени при распределении задач по выполняющим их про цессорам. Примеры использования данных алгоритмов можно найти в [10].

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

1.3.2 Алгоритм имитации отжига Алгоритм имитации отжига основывается на аналогии с термодинамиче ским процессом, который происходит при кристаллизации вещества из жидкого состояния в тврдое. Изначально делается допущение, что атомы предвари тельно выстроились в кристаллическую рештку. В то же время часть атомов может переходить из одной ячейки в другую. Данный переход осуществляется с некоторой вероятностью. Температура постепенно понижается. Вероятность, в свою очередь, также уменьшается с понижением температуры. Стабильная кристаллическая рештка соответствует минимуму энергии атомов – «охлаж денному состоянию». Изначально метод был предложен в 1982 году и описан в [11]. В общем виде описание алгоритма можно найти в [17].

Данный подход нашел свое применение в системах распределения ресур сов. Для этого над планом определяются несколько операций, которые приво дят к его изменению:

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

­ обмен временем выполнения двух заказов;

­ замена ресурса у заказа на другой ресурс.

Случайно выбирается и осуществляется одна из указанных операций. В зависимости от того, улучшился план или нет, данный шаг принимается сразу или с некоторой вероятностью P(t) соответственно. Изначально вероятность P(t) равна 1. С течением времени вероятность снижается, и переход к худшему плану осуществляется все реже и реже. Таким образом, план все сильнее и сильнее кристаллизуется.

К сожалению, у алгоритма имитации отжига существует следующий не достаток. Вследствие того, что он похож на метод наискорейшего спуска [14], ему свойственно попадать в локальные минимумы и не выбираться оттуда [15].

1.3.3 Генетические алгоритмы В настоящее время одними из самых популярных алгоритмов многоэкс тремальной оптимизации являются генетические алгоритмы (ГА). Данные ал горитмы основываются на принципах теории эволюции и опыта селекции рас тений и животных [18]. Идея поиска оптимального решения в генетических ал горитмах заключается в следующей гипотезе: чем выше приспособленность особи, тем выше вероятность того, что у потомков, полученных с е участием, признаки, определяющие приспособленность, будут выражены ещ сильнее [19]. Генетические алгоритмы являются подмножеством эвристических алго ритмов поиска.

В n-мерном пространстве задается функция f x1, x2,..., xn, которая называ ется функцией качества, а также приспособляемостью особи. В процессе рабо ты алгоритма выполняется поиск максимума данной функции. Выбираются не сколько точек из рассматриваемого n-мерного пространства:

X1 x11, x12,..., x1n, X 2 x21, x22,..., x2n, …, X m xm1, xm2,..., xmn.

Данные точки называются особями или хромосомами. Координаты самих точек ( x1, x2,..., xn ) – генами в хромосоме. Выбранные особи составляют началь ную популяцию. При работе генетического алгоритма используются две опера ции, с помощью которых получают популяцию следующей итерации: скрещи вание и мутация.

С помощью данных операций из предыдущей популяции появляется но вая временная популяция Pn, причем количество особей в полученной популя ции больше, чем в исходной. Из полученной популяции удаляются те особи, у которых значение функции приспособленности наименьшее. Однако решение о том, какие особи удалять, не является жестко детерминированным. Удаление происходит с учетом некоторой вероятности, которая зависит от значения са мой функции приспособленности. Таким образом, в полученной популяции окажутся не только особи с наибольшей функцией приспособленности.

Рассмотрим более подробно операцию скрещивания. Данная операция обеспечивает обмен генетическим материалом. Новый потомок, появляющийся с помощью указанной операции, может получить лучшие положительные каче ства своих родителей. В результате значение функции приспособленности для новой особи будет лучше, чем у исходных родителей. Операция скрещивания заключается в следующем. Берутся две произвольные особи. Случайно выбира ется целое число k, значение которого удовлетворяет неравенству 1 k n. У обеих особей первые k генов остаются на месте, затем особи обмениваются ме жду собой оставшимися частями хромосом. С помощью данного механизма по лучаются две новые особи. Необходимо отметить, что родители также остаются в новой популяции. Так как операция скрещивания рождает новые особи обме ном группами генов, принципиально новых особей не рождается. В этом случае алгоритм может легко скатиться в локальный экстремум. Для того чтобы избе жать этого, вводится операция мутации.

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

В системах распределения ресурсов каждому гену ставится в соответст вие пара (ресурс, время), которая соответствует состоянию заказа в плане.

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

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

1.3.4 Мультиагентный подход Агентом считается все, что действует (слово агент произошло от латин ского слова agere – действовать) [33,34]. Но предполагается, что компьютерные агенты обладают некоторыми другими атрибутами, которые отличают их от обычных «программ», такими как способность функционировать под автоном ным управлением, воспринимать свою среду, существовать в течение продол жительного периода времени, адаптироваться к изменениям и обладать способ ностью взять на себя достижение целей, поставленных другими. У агента зада ются предпочтения, которые соответствуют предпочтениям пользователя.

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

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

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

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

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

В [33] приводятся определения агента в «слабом» и «сильном» смыслах.

Под интеллектуальным агентом (ИА) в слабом смысле понимается программно или аппаратно реализованная система, которая обладает такими свойствами:

­ автономность – способность ИА функционировать без вмешательства чело века и при этом осуществлять самоконтроль над своими действиями и внут ренним состоянием;

­ общественное поведение (social ability) – способность функционировать в сообществе с другими агентами, обмениваясь с ними сообщениями с помо щью некоторого общепонятного языка коммуникаций;

­ реактивность (reactivity) – способность воспринимать состояние среды и своевременно отвечать (реагировать) на те изменения, которые в ней проис ходят;

­ про-активность (pro-activity) - способность агента брать на себя инициативу, т.е. способность генерировать цели и действовать рационально для их дос тижения, а не только реагировать на внешние события.

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

­ знания (knowledge) – это постоянная часть знаний агента о себе, среде и дру гих агентах, т.е. та часть, которая не изменяется в процессе его функциони рования;

­ убеждения (beliefs) – знания агента о среде, в частности, о других агентах;

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

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

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

­ цели (goals) – конкретное множество конечных и промежуточных состояний, достижение которые агент принял в качестве текущей стратегии поведения;

­ обязательства по отношению к другим агентам (commitments) – задачи, ко торые агент берет на себя по просьбе (поручению) других агентов в рамках кооперативных целей или целей отдельных агентов в рамках сотрудничест ва.

Применительно к планированию для каждой задачи и ресурсов, на кото рые должны быть запланированы задачи, назначаются агенты. И для агентов задач, и для агентов ресурсов задаются предпочтения. Целью агентов заказов и ресурсов является построение плана в соответствии с определенными крите риями. При запуске мультиагентной системы планирования агенты, основыва ясь на своих целях и предпочтениях, строят план, находя различные компро миссы. Описание различных мультиагентных систем можно найти в работах [33-34, 67].

1.3.5 Сравнительный анализ алгоритмов распределения ресурсов В Таблица 1 представлены результаты сравнительного анализа известных алгоритмов распределения ресурсов.

Таблица 1 – Сравнительный анализ алгоритмов распределения ресурсов Алго- Гене- Муль Спи- Ней ритм тиче- Сим- тиа сочные CPM и рон Критерии ими- ские плекс гент алго- ные PERT тации алго- метод ный ритмы сети отжига ритмы подход – – Посто- – С обратной + + + янная связью оценка гене рируе мых особей Оператив- Практи Воз- – Про- – Реко- + чески можно, стой менда ное плани неосу- однако пере- ции рование (приход со- щест- требует счет вимо допол- сроков бытий не нитель- выпол доступно ных со- нения сти ресур гласо глав са, нового ной за заказа, от ваний дачи мена зака планов за) Алго- Гене- Муль Спи- Ней ритм тиче- Сим- тиа сочные CPM и рон Критерии ими- ские плекс гент алго- ные PERT тации алго- метод ный ритмы сети отжига ритмы подход Мало- Мало- – Толь- – Возмож- + + эффек- эффек- коне в ность тивно тивно батч планиро режиме вания не в батч режиме Только Спон- Гло- Локаль – Неоп Локальные + не в танные баль ные реде изменения батч- измене ные ляемо плана режиме ния в произ воль ных участ ках плана Такти- Направ Направ Направ – Направ- + + чески ленный лен- ленный ленный направ- стохас- ность крити поиск ленный тиче- обес- ческим ский печи- путем.

вается Скорее (+) отбо- –, чем ром + особей (+/–) Слож- Слож- Очень Изме- – Легко Легко Адаптив но но сложно нения ность к из на ос менениям нове предмет пере ной облас счета ти вероят ностей.

Доста точно просто – – – Пере Возмож- + + + Алго- Гене- Муль Спи- Ней ритм тиче- Сим- тиа сочные CPM и рон Критерии ими- ские плекс гент алго- ные PERT тации алго- метод ный ритмы сети отжига ритмы подход обуче ность под ние се хвата из ти менений в предмет ной облас ти в со стоянии уже со ставленно го плана Полно- Детер- Эво- Детер- Детер- Детер Квази Детерми стью мини- люци- мини- ми мини- детер нирован детер- рован- онный, рован- ниро- рован- мини ный/ сто мини- ное по- осно- ный ван ный рован хастиче рован- строе- ван ный ный, ский/ са ный ние с ный на эволю мооргани неболь итера- ционн зация шим тив ность, учетом ном осно стохаст улучше ванная ики нии на ите особей ратив ном улуч шении – – – – – Возмож- + + ность про активного выхода на пользова теля с предложе ниями по улучше нию не больших участков плана Ориен- Ориен- Ис- – Ориен Направ- + + тация тация пользу- тация ленность Алго- Гене- Муль Спи- Ней ритм тиче- Сим- тиа сочные CPM и рон Критерии ими- ские плекс гент алго- ные PERT тации алго- метод ный ритмы сети отжига ритмы подход на ши- на ши- ется на по на решение рокий рокий для ма- строе задач пла спектр спектр ло- ние нирования задач задач крите- связей ресурсов риаль- за (+/–) (+/–) ных за- каз/рес дач урс – – – – – – Поиск гло- + бального экстрему ма Ниже приведены краткие описания известных эвристик и метаэвристик [47-51]:

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

­ Simple Local Search Based Meta-heuristics (SLSBM) – мета-эвристики локаль ной оптимизации со случайным выбором кандидата из списка лучших, с прогнозированием и случайным выбором критериев.

­ Simulated Annealing (моделирование процесса остывания) – расширение ме тодов локальной оптимизации, в котором формируются зависимые решения, причем на каждом шаге решения могут не только улучшаться, но и ухуд шаться с вероятностью, вычисляемой как функция от некоторого управляю щего параметра, аналога температуры.

­ Tabu Search – метод, использующий историю методов локальной оптимиза ции, когда некоторые уже исследованные варианты запрещается использо вать на следующих шагах (табу).


­ Ant Search – метод, моделирующий поведение муравьев, добывающих пищу.

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

­ Adaptive Memory Programming – использование общей памяти решений.

­ смешанные мета-эвристики Miscellaneous – использование нескольких па раллельных алгоритмов, каждый из которых формирует свое решение.

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

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

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

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

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

2 МУЛЬТИАГЕНТНАЯ МОДЕЛЬ АДАПТИВНОГО ПЛАНИРОВАНИЯ МОБИЛЬНЫХ РЕСУРСОВ 2.1 Метод адаптивного планирования С учетом описанных бизнес-процессов управления мобильными ресурса ми (Рисунок 3) целесообразно использование метода адаптивного планиро вания, который позволит добиться следующих преимуществ [37, 42]:

­ обеспечение индивидуального подхода к выполнению каждого заказа;

­ автоматизация основных операций операторов по планированию ресурсов;

­ накопление знаний о специфике бизнеса, позволяющих уточнять и совер шенствовать правила принятия решений при планировании;

­ повышение оперативности принятия решений и сокращение времени плани рования;

­ осуществление эффективного наглядного оперативного управления имею щимися заказами, повышение операционной эффективности;

­ своевременное извещение операторов о возможных проблемах (отсутствие заказов на будущее, расхождение между «планом» и «фактом», неэффектив ное использование транспортных средств и т.д.);

­ получение соответствующей комплексной систематизированной отчетности, снижение издержек по составлению и систематизации отчетной документа ции.

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

2.1.1 Сеть потребностей и возможностей При этом в качестве базовых классов мира агентов для распределения ре сурсов были выбраны агенты потребностей и возможностей, по определе нию представляющих собой сущности с противоположными интересами, по стоянно конкурирующих и кооперирующих на виртуальном рынке. На Рисунок 4 показана сцена виртуального рынка: поиск агентов потребностей (белые) и возможностей (серые), показан различный уровень удовлетворенности связями и разные виды связей (предварительное бронирование и т.д.).

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

Рисунок 3 – Бизнес-процессы управления мобильными ресурсами Сеть потребностей и возможностей (ПВ-сеть) [54] формируется про граммными агентами потребностей и возможностей ее элементов, в частности, заказов и ресурсов, постоянно стремящихся найти друг друга и установить свя зи. Например, для компании грузовых перевозок модель ПВ-сети может вклю чать агентов клиента и заказа, грузовика и груза, маршрута поездки, магазина и склада, водителя и т.д. При этом заказ постоянно ищет себе лучший грузовик, а грузовик встречно – заказ, но также маршрут и водителя и т.п. Сложность мо дели ПВ-сети и точность моделирования реальной транспортной сети могут на ращиваться как с ростом числа программных агентов, представляющих интере сы различных физических и абстрактных сущностей, необходимых для работы каждой сети, так и с ростом типов и вариантов взаимодействий между агентами разных классов.

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

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

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

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

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

Таким образом, обеспечивается автоматическое гибкое планирование ресурсов ТЛК в реальном времени, как в автоматическом режиме, так и в диалоге с чело веком.

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


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

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

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

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

Таким образом, суть метода сопряженных взаимодействий заключает ся в следующем [52, 53].

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

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

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

4. С помощью специальных инструментальных средств программирования разрабатывается программа моделирования сопряженных взаимодействий.

5. С помощью этой программы строится первоначальная ПВ-сеть, определяю щая соответствующее распределение ресурсов.

6. Если состояние ресурсов или потребности в них изменяются с приходом но вых событий, то ПВ-сеть перестраивается с целью разрешения конфликтов, причем в той части, которая непосредственно связана с изменениями (в пре дельном случае – вся сеть).

7. Решение задачи распределения ресурсов считается найденным, когда ни один элемент ПВ-сети не может улучшить свое состояние в сети.

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

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

Конкретная ситуация, складывающаяся с ресурсами, описывается в виде сцены, связывающей конкретные экземпляры объектов (название компании клиента, имя водителя грузовика, номер транспортного средства и т.п.).

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

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

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

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

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

2.1.2 Метод компенсаций Для реализации рассмотренного подхода предлагаются специально раз работанные методы и средства, реализующие различные варианты ПВ-сетей.

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

Заказ 1 Ресурс 1, Ресурс 3,4, Рисунок 6 – Обнаружение заказом двух ресурсов и бронирование второго ресурса для реализации заказа: 1 – запрос к первому ресурсу, 2 – ответ и предложение от первого ресурса, 3 – запрос второму ресурсу, 4 – ответ и предложение от второго ресурса, 5 – выбор варианта второго ресурса и его бронирование Заказ 1 Ресурс 8, Ресурс 7, Заказ 2 6, Рисунок 7 – Приход второго заказа и перебронирование второго ресурса для второго заказа с выплатой компенсации: 6 – запрос ко второму ресур су, 7 – переадресация предложения первому заказу от второго ресурса, 8 – запрос к первому ресурсу, 9 – положительный ответ и предложение, 10 разрешение на перебронирование второго ресурса, 11 – согласие и пред ложение с суммой компенсации первому заказу Заказ 1 Ресурс Ресурс 12,13, Рисунок 8 – Освобождение ресурса также вызывает пересмотр ситуации и перепланирование ресурсов даже «на лету», в ходе исполнения заказа: 12 – освободившийся ресурс инициирует выполняющийся заказ, 13 – выясня ется, что перегрузка на второй ресурс выгодна для первого заказа, 14 – да ется подтверждение и бронирование второго ресурса, 15 – первому ресурсу дается извещение об изменении маршрута и необходимости перегрузки груза на второй ресурс Здесь в примере из транспортной логистики для упрощения намеренно опущены все детали и дана лишь самая общая схема (модель) взаимодействия некоторых заказов и ресурсов как примеров потребностей и возможностей, но данная схема применима к заказам и маршрутам, грузовикам и водителям, по ездкам и заправкам топливом и т.д.

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

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

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

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

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

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

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

В работах [38, 67] рассмотрена классификация агентов, в которой выде лены три основных типа агентов:

­ Реактивные агенты. Термин реактивные агенты впервые возник в работах Брукса [39]. Реактивные агенты не имеют какой-либо символьной внутрен ней модели мира и работают по правилам типа ситуация-действие, выбирая из них действия, наиболее подходящие к конкретной ситуации. Эти агенты просты по конструкции и сравнительно неплохо приспособлены к работе в оперативном режиме (режиме, близком к режиму реального времени).

­ Мыслящие агенты (делиберативные). Агенты данного типа обладают внут ренним представлением о мире, которое меняется в процессе размышления агента. Как правило, строится модель размышлений (поведения) агента (на пример, BDI модель).

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

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

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

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

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

Разработаны принципы построения и функционирования агентов, а также про токолы их взаимодействий для коллективного управления подвижными объек тами, спроектированы средства для поддержки жизненного цикла агентов как в части реакции на события и построения планов, так и их исполнения и коррек тировки в реальном времени, спроектированы средства для поддержки жизнен ного цикла агентов (Рисунок 9 – Рисунок 10).

Жизненный цикл агента состоит из следующих фаз [46]:

­ восприятие окружающего мира – percept;

­ определение цели (задачи) – goal;

­ построение плана – plan;

­ принятие плана к исполнению – commit;

­ исполнение плана – execute;

­ сравнение полученных результатов и ожидавшихся – plan vs. fact;

­ изменение поведения» – learn.

Этот цикл называется PCX-циклом (по наименованию фаз: plan – commit – execute). PCX-цикл каждого агента независим, т.е. фазы работы агента не за висят от того, в какой фазе своего жизненного цикла находятся другие агенты.

Таким образом, часть агентов в системе могут заниматься, например, планиро ванием, а другие исполнением своих планов.

Каждый раз, когда агент получает управление от системы, личность аген та – Agent Personality – решает, как себя вести в данной ситуации: продолжить исполнение ранее начатой задачи, инициировать обработку новой задачи на ос новании изменений во внешнем мире или внутреннем состоянии, вернуться к ранее отложенной задаче и пр. Т.е. агент оценивает имеющуюся у него инфор мацию с точки зрения своей цели и выбирает наиболее адекватный с его точки зрения вариант действий.

Конструкция агента представлена на Рисунок 9.

От Диспетчера аген- Базовая часть тов Библиотека ролей Жизненный цикл агента агента Очередь событий Отложенная роль с Личность агента сохраненным кон (Принятие решений) текстом данных Выполнить шаг роли Роль агента и перейти к следую- Инициализировать процесс щему состоянию Ожидать событие от другого агента и перейти к следующему Сенсоры Исполните ли Диаграмма Ожидать событие, ко состояний торое придет первым, и перейти к следующему Уничтожить процесс Предметная область Рисунок 9 – Конструкция агента Новая информация может поступать в индивидуальную сцену агента, т.е., индивидуальное представление о внешнем мире и о себе. Сенсоры создают объекты – события, которые помещаются в очереди. Очереди обрабатываются в Agent Personality, которая работает согласно PCX-циклу. События создаются в фазе восприятия (perception).

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

Выбранный план принимается к исполнению на фазе commit.

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

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

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

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

­ задачи, соответствующие его классу;



Pages:   || 2 | 3 | 4 |
 





 
© 2013 www.libed.ru - «Бесплатная библиотека научно-практических конференций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.