Данный подход был разработан бельгийскими учеными для решения задачи управления дорожным движением города с целью минимизации количества заторов и повышения скорости передвижения автомобилей. Чтобы распределить трафик и избежать «пробок» при движении большого числа автомобилей современные системы управления транспортом используют информацию о ситуации на дорогах, поступающую в режиме реального времени, что позволяет реагировать только на уже существующие скопления автомобилей, но не препятствовать формированию новых. Предлагаемый подход основан на многоагентных системах, использующих агентов-посланников, и на сконцентрированном на восприятии среды механизме координации. Подход агентов-посланников использует аналогию с поведением муравьев. Подобно муравьям одни агенты-посланники исследуют окружающую среду автомобилей, то есть определяют транспортную ситуацию и делают прогнозы заторов. Благодаря этим прогнозам автомобили могут менять свой маршрут. Другие агенты-посланники по выбранным маршрутам коллективно формируют карту транспортной ситуации во всем городе. Эта карта определяет окружающую среду автомобилей.
Таким образом, целью предложенного механизма координации движения автомобилей является сокращение длительности и дальности поездки. Выбор маршрута остается на усмотрение водителя автомобиля. Этот механизм децентрализованный, то есть с одной стороны, автомобили самостоятельно делают прогнозы характеристик движения по тому или иному маршруту и на основе этих прогнозов выбирают оптимальный текущий маршрут, а с другой стороны, автомобили, зная выбранные маршруты, формируют общую карту транспортной ситуации в городе. Этот механизм самосогласованный: автомобили одновременно 1) формируют и 2) используют общую карту транспортной ситуации, и динамичный: как выбираемые автомобилями маршруты, так и карта ситуации динамически меняется.
С целью демонстрации работоспособности предложенного механизма была построена и исследована компьютерная модель многоагентной системы.
Модель многоагентной системы основана на следующих трех основных типах агентов: 1) агент автомобиля; 2) агент инфраструктуры; и 3) виртуальная среда.
Агент автомобиля размещен внутри смарт-устройства на автомобиле. Этот агент может получать информацию о пунктах назначения и состоянии автомобиля, включая его местоположение и скорость. Агент автомобиля предоставляет водителю информацию о маршрутах к пункту назначения.
Основные элементы дорожной инфраструктуры, такие как дороги и перекрестки, снабжены агентами инфраструктуры. Агенты инфраструктуры установлены на вычислительных и коммуникационных устройствах в дорожной инфраструктуре. Агенты инфраструктуры отслеживают текущее состояние подответственных им элементов дороги, а также получают от агентов автомобилей информацию об ожидаемых приездах автомобилей. Если информация о приездах не обновляется агентами автомобилей, то с течением времени она исчезает.
Виртуальной средой является программный аналог окружающей среды, в которой физическая сеть дорог отображается путем графического представления. Узлы графика представляют собой дорожные элементы, такие как линии и перекрестки. Эта виртуальная среда задается программными элементами, установленными на электронные устройства, предоставляемые дорожной инфраструктурой.
Агенты автомобилей и агенты инфраструктуры отвечают за координацию трафика. У агентов автомобилей есть две важные задачи. Во-первых, агенты автомобилей ищут наиболее подходящие маршруты к заданным пунктам назначения. Агент автомобиля оценивает качество каждого из возможных маршрутов по времени достижения пункта назначения. Из набора альтернативных маршрутов агент выбирает один предпочтительный маршрут, которому он намерен следовать. Во-вторых, агент автомобиля должен информировать агентов других автомобилей о предполагаемом маршруте своего автомобиля, чтобы позволить другим агентам использовать эту информацию для выбора их маршрутов. Для осуществления этого агент автомобиля информирует всех агентов инфраструктуры, соответствующих элементам маршрута, выбранного данным агентом. Поступая таким образом, все агенты автомобилей совместно формируют информацию о своих намерениях, предоставляя информацию о намеченном пути и намеченном времени своего прибытия на тот или иной элемент маршрута агенту инфраструктуры, соответствующему этому элементу. Агенты инфраструктуры в свою очередь предоставляют данную информацию обратно агентам автомобилей, чтобы они использовали ее при составлении маршрутов.
При выборе маршрутов и при информировании агентов инфраструктуры агенты автомобилей используют так называемых легких агентов или агентов-посланников. Эти легкие агенты аналогичны муравьям и прямо называются авторами муравьями. Используется два вида этих агентов-муравьев: 1) муравьи-разведчики и 2) муравьи намерений.
Агенты-посланники функционируют подобно реальным муравьям, которые при нахождении пищи метят проходимые ими маршруты пахучим веществом феромоном. Другие муравьи воспринимают запах феромона и используют его при выборе своего пути движения к пище. Если пища в каком-то месте закончилась, то откладывание феромона на пути к этому месту прекращается, оставшийся феромон испаряется и, таким образом, прокладываемые пути к источникам пищи динамически меняются.
Принципы функционирования агентов-посланников для автомобилей, прокладывающих маршруты в динамически меняющейся транспортной ситуации, отображены на рис. 1.
Рис. 1. Муравьи-разведчики (Exploration ants) и муравьи намерений (Intention ants). Муравьи-разведчики исследуют возможные маршруты (выделены темно-синим цветом) и возвращают автомобилю оценки качества маршрутов. На основе этих оценок агент автомобиля выбирает наиболее подходящий маршрут (выделено красным) и посылает муравья намерения уведомить агентов инфраструктуры о своем запланированном перемещении.
1) Функционирование муравьев-разведчиков. Агент автомобиля посылает муравьев-разведчиков через регулярные интервалы времени. Муравьи-разведчики исследуют различные пути между текущим местоположением агента и местом его назначения, используя карту виртуальной среды. На каждом участке (элементе) дороги своего маршрута муравей-разведчик запрашивает у агента инфраструктуры, какое может быть прогнозируемое время выезда из этого участка, если автомобиль прибудет к этому элементу в определенное время. Затем он переходит к следующему участку на своем пути и задает такой же вопрос, получает ответ, оценивает время перемещения по участку, а затем движется дальше. В конце концов, муравей-разведчик достигает пункта назначения автомобиля с оценкой того, сколько всего времени понадобится автомобилю попасть туда, принимая во внимание прогнозируемые задержки по этому маршруту. Таким образом, муравей разведчик оценивает качество определенного маршрута. Затем муравей-разведчик сообщает оценку ожидаемого полного времени движения по данному маршруту обратно агенту автомобиля. Другие муравьи-разведчики оценивают качество других возможных маршрутов. В результате, агент автомобиля постоянно получает оценки качеств (то есть полное время достижения пункта назначения) альтернативных маршрутов к пункту назначения.
2) Функционирование муравьев намерений. После того, как агент автомобиля выбирает один из исследованных маршрутов для своего движения, он должен сделать информацию о своем намерении двигаться по определенному маршруту доступной для других агентов автомобилей. Это обеспечивается тем, что агент автомобиля посылает своих муравьев намерений по выбранному маршруту через регулярные интервалы времени, а эти муравьи сообщают информацию о запланированном данным автомобилем времени прибытия на определенный элемента дороги и времени убытия с этого элемента дороги агенту инфраструктуры данного элемента. Таким образом, муравьи намерений представляют информацию агентам инфраструктуры об ожидаемой загрузке элементов дороги.
Агенты автомобилей могут менять свои намерения движения по тем или иным маршрутам. Например, агент автомобиля может изменить какой-либо маршрут на новый, если время полного движения к пункту назначения для нового маршрута меньше, чем для старого. Для того, чтобы учесть это, вводится аналог испарения феромона у муравьев: у агентов инфраструктуры информация о намерениях движения автомобилей с течением времени стирается.
Итак, происходит динамическое формирование маршрутов автомобилями на основе информации у агентов инфраструктуры об ожидаемом трафике во всей виртуальной среде, а данные агентов инфраструктуры, в свою очередь, определяются информацией о выбранных автомобилями маршрутах, получаемой от агентов-муравьев намерений.
Рис. 2. Карта моделируемой области. (а) Общий вид города и дорог. (б) График дорог, используемый при компьютерном моделировании.
Работоспособность и эффективность предложенной схемы многоагентной системы, включающей в себя агентов-посланников, была продемонстрирована путем компьютерного моделирования. Компьютерные эксперименты выполнены при моделировании в реальных условиях дорожного движения на дорожной сети города Лёвен (Leuven), Бельгия (рис. 2.) Эта дорожная сеть включает более 1600 дорог, в основном, двунаправленных, и 1250 развязок и перекрестков. В качестве данных для эксперимента были подробно описаны не только местоположение большинства городских дорог и развязок, но и их характеристики, такие, как их тип, допустимая максимальная скорость и мощность. Исследовалось движение 28800 автомобилей, которые имели различные (выбираемые случайно) пункты отправления и назначения. При моделировании проводилось сопоставление с ранее известными близкими подходами, в которые либо не вводились все компоненты предложенной схемы маршрутизации (децентрализация, динамичность, прогнозирование маршрутов, использование агентов-посланников), либо некоторые компоненты были модифицированными.
Результаты моделирования показали, что предложенная авторами схема децентрализованной маршрутизации на основе прогнозов и нетривиального использования агентов-посланников позволят обеспечить достижение автомобилями их пунктов назначения на 35% быстрее, чем для ранее разработанных аналогичных схем.
Более подробно статья представлена здесь.
© Редько Ольга
Таким образом, целью предложенного механизма координации движения автомобилей является сокращение длительности и дальности поездки. Выбор маршрута остается на усмотрение водителя автомобиля. Этот механизм децентрализованный, то есть с одной стороны, автомобили самостоятельно делают прогнозы характеристик движения по тому или иному маршруту и на основе этих прогнозов выбирают оптимальный текущий маршрут, а с другой стороны, автомобили, зная выбранные маршруты, формируют общую карту транспортной ситуации в городе. Этот механизм самосогласованный: автомобили одновременно 1) формируют и 2) используют общую карту транспортной ситуации, и динамичный: как выбираемые автомобилями маршруты, так и карта ситуации динамически меняется.
С целью демонстрации работоспособности предложенного механизма была построена и исследована компьютерная модель многоагентной системы.
Модель многоагентной системы основана на следующих трех основных типах агентов: 1) агент автомобиля; 2) агент инфраструктуры; и 3) виртуальная среда.
Агент автомобиля размещен внутри смарт-устройства на автомобиле. Этот агент может получать информацию о пунктах назначения и состоянии автомобиля, включая его местоположение и скорость. Агент автомобиля предоставляет водителю информацию о маршрутах к пункту назначения.
Основные элементы дорожной инфраструктуры, такие как дороги и перекрестки, снабжены агентами инфраструктуры. Агенты инфраструктуры установлены на вычислительных и коммуникационных устройствах в дорожной инфраструктуре. Агенты инфраструктуры отслеживают текущее состояние подответственных им элементов дороги, а также получают от агентов автомобилей информацию об ожидаемых приездах автомобилей. Если информация о приездах не обновляется агентами автомобилей, то с течением времени она исчезает.
Виртуальной средой является программный аналог окружающей среды, в которой физическая сеть дорог отображается путем графического представления. Узлы графика представляют собой дорожные элементы, такие как линии и перекрестки. Эта виртуальная среда задается программными элементами, установленными на электронные устройства, предоставляемые дорожной инфраструктурой.
Агенты автомобилей и агенты инфраструктуры отвечают за координацию трафика. У агентов автомобилей есть две важные задачи. Во-первых, агенты автомобилей ищут наиболее подходящие маршруты к заданным пунктам назначения. Агент автомобиля оценивает качество каждого из возможных маршрутов по времени достижения пункта назначения. Из набора альтернативных маршрутов агент выбирает один предпочтительный маршрут, которому он намерен следовать. Во-вторых, агент автомобиля должен информировать агентов других автомобилей о предполагаемом маршруте своего автомобиля, чтобы позволить другим агентам использовать эту информацию для выбора их маршрутов. Для осуществления этого агент автомобиля информирует всех агентов инфраструктуры, соответствующих элементам маршрута, выбранного данным агентом. Поступая таким образом, все агенты автомобилей совместно формируют информацию о своих намерениях, предоставляя информацию о намеченном пути и намеченном времени своего прибытия на тот или иной элемент маршрута агенту инфраструктуры, соответствующему этому элементу. Агенты инфраструктуры в свою очередь предоставляют данную информацию обратно агентам автомобилей, чтобы они использовали ее при составлении маршрутов.
При выборе маршрутов и при информировании агентов инфраструктуры агенты автомобилей используют так называемых легких агентов или агентов-посланников. Эти легкие агенты аналогичны муравьям и прямо называются авторами муравьями. Используется два вида этих агентов-муравьев: 1) муравьи-разведчики и 2) муравьи намерений.
Агенты-посланники функционируют подобно реальным муравьям, которые при нахождении пищи метят проходимые ими маршруты пахучим веществом феромоном. Другие муравьи воспринимают запах феромона и используют его при выборе своего пути движения к пище. Если пища в каком-то месте закончилась, то откладывание феромона на пути к этому месту прекращается, оставшийся феромон испаряется и, таким образом, прокладываемые пути к источникам пищи динамически меняются.
Принципы функционирования агентов-посланников для автомобилей, прокладывающих маршруты в динамически меняющейся транспортной ситуации, отображены на рис. 1.
Рис. 1. Муравьи-разведчики (Exploration ants) и муравьи намерений (Intention ants). Муравьи-разведчики исследуют возможные маршруты (выделены темно-синим цветом) и возвращают автомобилю оценки качества маршрутов. На основе этих оценок агент автомобиля выбирает наиболее подходящий маршрут (выделено красным) и посылает муравья намерения уведомить агентов инфраструктуры о своем запланированном перемещении.
1) Функционирование муравьев-разведчиков. Агент автомобиля посылает муравьев-разведчиков через регулярные интервалы времени. Муравьи-разведчики исследуют различные пути между текущим местоположением агента и местом его назначения, используя карту виртуальной среды. На каждом участке (элементе) дороги своего маршрута муравей-разведчик запрашивает у агента инфраструктуры, какое может быть прогнозируемое время выезда из этого участка, если автомобиль прибудет к этому элементу в определенное время. Затем он переходит к следующему участку на своем пути и задает такой же вопрос, получает ответ, оценивает время перемещения по участку, а затем движется дальше. В конце концов, муравей-разведчик достигает пункта назначения автомобиля с оценкой того, сколько всего времени понадобится автомобилю попасть туда, принимая во внимание прогнозируемые задержки по этому маршруту. Таким образом, муравей разведчик оценивает качество определенного маршрута. Затем муравей-разведчик сообщает оценку ожидаемого полного времени движения по данному маршруту обратно агенту автомобиля. Другие муравьи-разведчики оценивают качество других возможных маршрутов. В результате, агент автомобиля постоянно получает оценки качеств (то есть полное время достижения пункта назначения) альтернативных маршрутов к пункту назначения.
2) Функционирование муравьев намерений. После того, как агент автомобиля выбирает один из исследованных маршрутов для своего движения, он должен сделать информацию о своем намерении двигаться по определенному маршруту доступной для других агентов автомобилей. Это обеспечивается тем, что агент автомобиля посылает своих муравьев намерений по выбранному маршруту через регулярные интервалы времени, а эти муравьи сообщают информацию о запланированном данным автомобилем времени прибытия на определенный элемента дороги и времени убытия с этого элемента дороги агенту инфраструктуры данного элемента. Таким образом, муравьи намерений представляют информацию агентам инфраструктуры об ожидаемой загрузке элементов дороги.
Агенты автомобилей могут менять свои намерения движения по тем или иным маршрутам. Например, агент автомобиля может изменить какой-либо маршрут на новый, если время полного движения к пункту назначения для нового маршрута меньше, чем для старого. Для того, чтобы учесть это, вводится аналог испарения феромона у муравьев: у агентов инфраструктуры информация о намерениях движения автомобилей с течением времени стирается.
Итак, происходит динамическое формирование маршрутов автомобилями на основе информации у агентов инфраструктуры об ожидаемом трафике во всей виртуальной среде, а данные агентов инфраструктуры, в свою очередь, определяются информацией о выбранных автомобилями маршрутах, получаемой от агентов-муравьев намерений.
Рис. 2. Карта моделируемой области. (а) Общий вид города и дорог. (б) График дорог, используемый при компьютерном моделировании.
Работоспособность и эффективность предложенной схемы многоагентной системы, включающей в себя агентов-посланников, была продемонстрирована путем компьютерного моделирования. Компьютерные эксперименты выполнены при моделировании в реальных условиях дорожного движения на дорожной сети города Лёвен (Leuven), Бельгия (рис. 2.) Эта дорожная сеть включает более 1600 дорог, в основном, двунаправленных, и 1250 развязок и перекрестков. В качестве данных для эксперимента были подробно описаны не только местоположение большинства городских дорог и развязок, но и их характеристики, такие, как их тип, допустимая максимальная скорость и мощность. Исследовалось движение 28800 автомобилей, которые имели различные (выбираемые случайно) пункты отправления и назначения. При моделировании проводилось сопоставление с ранее известными близкими подходами, в которые либо не вводились все компоненты предложенной схемы маршрутизации (децентрализация, динамичность, прогнозирование маршрутов, использование агентов-посланников), либо некоторые компоненты были модифицированными.
Результаты моделирования показали, что предложенная авторами схема децентрализованной маршрутизации на основе прогнозов и нетривиального использования агентов-посланников позволят обеспечить достижение автомобилями их пунктов назначения на 35% быстрее, чем для ранее разработанных аналогичных схем.
Более подробно статья представлена здесь.
© Редько Ольга