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

Л'

МОГОРАС АНДРЕЙ АЛЕКСАНДРОВИЧ ^

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

Специальность 05.13.01 - Системный анализ, управление и обработка

информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

0 3 033 2011

Москва 2010

4853700

Работа выполнена на кафедре: "Математическое обеспечение систем обработки информации и управления" (МОСОИиУ) Московского государственного института электроники и математики (технического университета)

Научный руководитель:

кандидат технических наук, доцент Тюхов Борис Петрович

Официальные оппоненты:

доктор технических наук, профессор Фоминых Игорь Борисович;

кандидат технических наук, доцент Тарасов Валерий Борисович.

Ведущая организация:

Учреждение Российской академии наук Институт проблем управления им. В. А. Трапезникова РАН

Защита состоится 22 февраля 2011 года в 14 часов на заседании диссертационного совета Д212.133.01 Московского государственного института электроники и математики (технического университета) по адресу 109028, Москва, Б. Трехсвятительский пер., 3.

С диссертацией можно ознакомиться в библиотеке МИЭМ (ТУ). Автореферат разослан года.

Ученый секретарь

диссертационного совета ДЙ2,133.01,

Общая характеристика работы

Актуальность работы

В настоящее время практически во всех мегаполисах темпы роста количества автомобилей значительно опережают темпы развития улично-дорожной сети. Это порождает ряд проблем дорожного движения: транспортные заторы, снижение безопасности, загрязнение окружающей среды, а также социально-экономических проблем. В Москве эти проблемы усугубляются из-за исторически сложившейся радиально-кольцевой планировки города, существенного роста и уплотнения городской среды, влияния пригородных транспортных потоков (ТП) и разобщенности мест работы и проживания. Начиная с 90-х годов в развитых странах (США, Зап. Европа, Япония, Сингапур и др.) получили определенное развитие полностью автоматизированные системы дистанционного централизованного оперативного управления дорожным движением, названные интеллектуальными транспортными системами (ИТС). Эксперты считают применение ИТС одним из наиболее перспективных способов решения перечисленных проблем дорожного движения.

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

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

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

Задачи исследования

1. Анализ моделей, методов и информационно-коммуникационных технологий, применяемых при управлении дорожным движением.

2. Разработка функциональной схемы управления ТП мегаполиса на основе многоагентной ИТС.

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

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

5. Разработка базы знаний и структуры многоагентной ИТС, реализующей данную методику.

6. Программная реализация многоагентной ИТС.

7. Экспериментальная проверка работоспособности и анализ свойств и особенностей многоагентной ИТС.

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

На защиту выносятся следующие научные результаты:

- функциональная схема управления ТП мегаполиса посредством ИТС;

- имитационная модель неоднородного ТП;

- методика анализа, прогнозирования динамических состояний и управления ТП для различных классов типовых и нештатных ситуаций;

- база знаний и структура многоагентной ИТС, реализующей разработанную методику.

Научная новизна содержится в следующих результатах работы:

функциональная схема управления ТП. мегаполиса в классе многоагентных ИТС;

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

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

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

Практическая полезность

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

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

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

Реализация результатов

Полученные в работе результаты были программно реализованы и используются в практической деятельности организации ООО «СМИЛИНК», работающей в области сбора, обработки и анализа информации о дорожном движении, а также в учебном процессе МИЭМ при обучении студентов на кафедре "Математическое обеспечение систем обработки информации и управления", что подтверждено соответствующими справками и актом.

Апробация работы

Результаты работы докладывались в 2008 г. на XVI-й Международной конференции «Проблемы управления безопасностью сложных систем» (ИПУ, Москва), в 2005-2009 гг. на Ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ, Москва; в 2005-2008 гг. на Международной студенческой школе-семинаре «Новые информационные технологии», (Судак, Украина), в 2005 г. на Шестом Всероссийском симпозиуме по прикладной и промышленной математике (Сочи, Россия).

Публикации

Основные результаты диссертации опубликованы в 12 научных работах, в том числе работы [1], [2], [3] - в журналах, включенных ВАК в Перечень ведущих рецензируемых научных изданий.

Структура работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложений. Основная часть работы изложена на 150 страницах, содержит 54 рисунка и 10 таблиц. Список литературы включает 105 наименований. Приложения содержат 10 рисунков и 16 таблиц.

Содержание работы

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

Глава 1 содержит анализ предметной области, проблем, подходов и существующих решений. Определены основные понятия и проанализированы различные классы ИТС и моделей ТП, рассмотренных в работах отечественных специалистов: В.В. Зырянова, В.Т. Капитанова, В.Г. Живоглядова, П.И. Поспелова, М.Я. Блинкина, В.В. Сильянова, и др. и зарубежных специалистов: Ф. Хейта, X. Иносэ и Т. Хамада, К. Даганзо и др.

Интеллектуальная транспортная система или ИТС — это

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

Транспортный поток (ТП) — совокупность автотранспортных средств (АТС), одновременно участвующих в движении на определенном участке улично-дорожной сети.

Агент - это сущность, обладающая следующими свойствами:

1) активностью - может осуществлять целенаправленное поведение, проявляя при этом инициативу;

2) реактивностью - воспринимает состояние окружающей среды и реагирует на ее изменения;

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

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

5) целенаправленностью - имеет собственные источники мотивации.

Интеллектуальными являются агенты, поведение которых

рационально, т.е. основано на рассуждениях.

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

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

- высокая сложность и многокритериальность решаемой задачи;

- ограниченная область применения ИТС;

- нестабильность, неоднородность и неполная наблюдаемость ТП;

- значительная непредсказуемость поведения участников дорожного движения;

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

- неточность реализации управляющих воздействий.

На основе проведенного анализа предметной области сформулирована следующая постановка задачи управления ТП посредством ИТС.

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

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

Объектом управления в разработанной системе является множество ТП Р={Рк}, к=1,..,К, которые распределены на улично-дорожной сети мегаполиса и представлены имитационной моделью.

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

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

Глава 2 содержит описание функциональной схемы, математического аппарата и методики управления ТП на основе применения нечеткой и модальной (временной) логики. Схема управления ТП имеет вид:

Имитационное моделирование

Анализ ТП:

уровень мегаполиса

-структурный,

-типовая ситуация:

применяется Правило

_ЩИИНр 1

- нештатная ситуация: применяется имитационное лгода'шр'Ьвание -

-классификация состояния ТП

Наблюдение за ТП в городе

-уровень микрорайонов

Рис. 1. Функциональная схема управления ТП

Разработанная имитационная модель ТП описывается так: дорога содержит 1ЧП полос по Мкл клеток;

в каждый момент времени I на каждой клетке может находиться не более одного АТС, ширина всех АТС равна 1 клетке; общее число АТС в потоке равно М. Состав ТП определяется Я классами участников дорожного движения, которые различаются следующими параметрами: габаритной длиной (от 1 до 3 клеток); типом транспорта (легковой, грузовой или пассажирский);

7

скоростью V в свободном ТП (усредненное значение скорости движения для данного класса АТС при отсутствии помех на дороге);

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

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

При оперативном управлении дорожным движением в масштабах мегаполиса возможно использовать только интегральные характеристики ТП. Кроме того, при решении задач моделирования, прогнозирования и управления ТП всегда присутствует значительная неопределенность, что делает малоэффективным применение точных количественных методов и подходов. В силу этих причин данные задачи в работе решаются на основе применения нечеткого вывода и аппарата лингвистических переменных. Лингвистическая переменная формально определяется так: ЬУ = (Ь,Т,Х,0,М) (1),

где Ь - название переменной;

Р=Р(Ь) - терм-множество (совокупность лингвистических значений); X - универсальное множество;

в - грамматика, позволяющая из простых, атомарных термов строить составные термы, 0:Т—>Т*, Т* есть расширенное терм-множество;

М - множество семантических правил, задающее отношение полиморфизма (соответствия типа "один-ко-многим") между Р и X.

Применяемые в работе нечеткие продукционные правила имеют вид: Ц: ЕСЛИ (х, есть аи)л...л(хй есть аы) ТО (у есть РО (2),

где хь...,хп- входные лингвистические переменные, л - конъюнкция (логическое И), у - выходная лингвистическая переменная,

ап,...,аП1, р, - лингвистические термы, определенные на универсальных множествах Хь..,Хп,У,

здесь и далее 1 - номер правила.

Нечеткий вывод на правилах данного вида осуществляется по известному алгоритму Мамдани.

Разработанная база знаний содержит три основных уровня правил, состоящих из нескольких подуровней.

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

Скорость АТС в свободном ТП определяется на основе правил вида: П|: ЕСЛИ «расстояние до перекрестка/светофора» есть а^ И <<условия видимости/погодные условия» есть а2| И «максимальная разрешенная скорость» есть а31 И «скорость АТС в предыдущий момент времени» есть а«, ТО «скорость АТС в свободном ТП» есть р| (3),

Ян.....адь р| - термы соответствующих лингвистических переменных,

Скорость АТС в согласованном ТП определяется правилами вида:

Ц: ЕСЛИ «скорость АТС в свободном ТП» есть ац И «скорость впереди идущего АТС» есть а21 И «дистанция до впереди идущего АТС» есть аз( И «дистанция до сзади идущего АТС» есть оц,, ТО «скорость АТС в согласованном ТП» есть Р; (4),

ам,.. .,ац\, Р; - термы соответствующих лингвистических переменных. Правила 2-го уровня определяют методику анализа и прогнозирования динамических состояний ТП. Анализ ТП включает 2 этапа.

а) Структурный анализ ТП, в результате которого для каждого ТП Рк (к=1,..,К), который движется на определенном участке улично-дорожной сети рь определяется вектор состояния Ук-

б) Определение класса состояния ТП Рк на основе анализа вектора состояния Ук посредством лингвистической переменной С - состояние ТП,

Р(С) = {«свободное движение», «почти свободное движение», «умеренное движение», «умеренно-затрудненное движение», «затрудненное движение», «плотное движение», «старт-стоп движение», «почти остановившееся движение», «остановившееся движение (затор)»}

или в символьном виде Р(С) = {С1, С2, СЗ, С4, С5, С6, С7, С8, С9} (5), X = [0,100] (баллов) - напряженность движения в ТП. Графики функций принадлежности представлены на рис. 2.

Рис. 2 Графики функций принадлежности для термов лингвистической переменной «Состояние ТП»

Правила классификации состояния ТП имеют вид: II¡: ЕСЛИ «плотность ТП» есть Оц И «изменение плотности» есть И «средняя скорость ТП» есть <X3¡ И «изменение средней скорости» есть ct4¡ И «затрудненность движения в ТП» есть as¡ И «изменение затрудненности движения» есть a6¡ ТО «состояние ТП» есть p¡ (6),

cti¡.....a«;, P¡ - термы соответствующих лингвистических переменных.

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

Состояние системы ТП {F¡, F2,..., FK} в момент времени t характеризуется вектором состояний y(t) = {Ci, С2,.-мСк}, где Ск -класс состояния ТП Fk в момент времени t.

Разработанная модель прогнозирования позволяет с некоторой вероятностью предсказывать будущие значения вектора y(th) в моменты

времени th = t+h ■ Atnp, h=l,2.....H, где Atnp=2 мин - шаг прогнозирования, a

весь интервал прогнозирования Т = 60 мин. При этом возможны 2 случая.

а) Типовая ситуация - известны классы состояний для всех ТП в данном районе мегаполиса. В этом случае ориентировочно-прогнозируемое состояние каждого ТП F в этом районе определяется по правилам вида:

ü¡: ЕСЛИ «состояние ТП F» есть Оц И «состояние ТП F/» есть a2¡

И «состояние ТП Fn.¡» есть a„¡,

ТО «ориентировочно-прогнозируемое состояние ТП F» есть p¡ (7), Fi,...,F„.i - входящие и исходящие из F потоки, ai¡,...,ctn¡, p¡ - термы соответствующих лингвистических переменных. Далее применяются правила уточненного прогнозирования вида:

II¡: ЕСЛИ «ориентировочно-прогнозируемое состояние ТП F » есть a¡¡ И «приток/отток АТС с прилегающих территорий» есть а^ И «последствия управляющих воздействий» есть oí3¡ И «погодные условия/условия видимости» есть а41 И «количество пешеходов» есть as¡ И «пропускная способность» есть a6¡,

ТО «уточненно-прогнозируемое состояние ТП F» есть p¡ (8),

d|¡,...,a6i, p¡ - термы соответствующих лингвистических переменных.

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

Правила 3-го уровня определяют выработку управления ТП мегаполиса для заданного временного интервала. В рамках принятой структурной и функциональной иерархии координирования ТП управление осуществляется:

- на уровне мегаполиса путем назначения приоритетов каждому району по степени напряженности в нем дорожного движения, а также коэффициентов, соответствующих критериям качества управления ТП;

- на уровне округов, путем определения величины перераспределения каждого ТП с учетом полученного прогноза по правилам, имеющим вид:

n¡: ЕСЛИ «текущее состояние ТП» есть ац

И «уточненно-прогнозируемое состояние ТП» есть a2¡ И «вес ТП» есть a3¡

И «текущий уровень транспортных заторов в районе» есть a4¡ И «прогнозируемый уровень транспортных заторов» есть as¡ И «текущий уровень свободного движения в районе» есть a6¡ ТО «перераспределение ТП» есть p¡ (9),

aii,...,a6¡, P¡ - термы соответствующих лингвистических переменных.

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

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

б) светофорное регулирование.

Для структурного анализа и светофорного регулирования ТП применяется аппарат временной (интервальной) логики Аллена. Это

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

В логике Аллена рассматриваются интервалы вида (А, В) и отношения между ними, где А и В - вещественные числа (А,ВеЯ) такие, что А <В.

Вводятся 2 типа интервалов:

- пространственные (соответствуют пути, проходимому одним или группой автотранспортных средств за такт моделирования);

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

Возможны следующие интервальные отношения (рис. 3):

Ь (before) предшествование s (starts) старт

-1 ,-, El-1

f (¡finishes) завершение m (meets) встреча

-ь=| -

о (overlaps) пересечение d (during) включение

Ш'-1 -1 -■-ч

e (is equal) синхронность

HI =1

Рис. 3. Основные интервальные отношения логики Аллена

Обратные отношения между интервалами, обозначаемые как !Ь, !с1 !£ !т, !о, ¡в, означают инверсию интервалов. Т. о. есть 13 возможных отношений (е и !е одно и то же), множество которых обозначается /:

/= {Ь, !Ь, й, !с1, е, {, !{,т, !т, о, !о, в, !я} (10)

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

Ка г,} -

Глава 3 содержит описание разработанной многоагентной ИТС (МАИТС) и ее программной реализации.

МАИТС = (Л, Е, О, ACT, F, St, Y) (11)

-4={А, П, К} - множество агентов; А = {Ааь...,Аам} - множество агентов-автомобилистов (АА), П = {Pa|,...,PaN} - множество прогнозирующих агентов (ПА), К = {Ка11, Ка2],..., Ka2L, Ка3 множество координирующих агентов (КА);

Е - множество сред, в которых функционируют агенты;

О - множество отношений между агентами;

ACT - множество возможных действий агентов;

СОМ - множество коммуникативных актов, используемых взаимодействии агентов;

ST - множество состояний многоагентной системы;

Y - множество законов функционирования многоагентной системы.

Структурная схема созданной МАИТС представлена на рис. 4:

при

Структура многоагентной системы И----- .. -.

Координатор 1 мегаполиса J L

Рис. 4. Структурная схема многоагентной ИТС

Агенты-автомобилисты делятся на подклассы, которые различаются физическими параметрами (габаритные размеры, скорость и т.д.) и правилами, которыми пользуется агент при выборе маршрута и вариантов поведения в ТП (в том числе правилами вида (4-5)). Часть АА обладает связью с КА и получает от него информацию о текущей и прогнозируемой ситуации на дорогах.

С целью понижения сложности задачи имитационного моделирования ТП, мегаполис разбивается на множество непересекающихся районов 3-го уровня {11а31,...Да3с}. Экспериментально была выбрана такая размерность этих районов, чтобы в каждом из них суммарное число одновременно движущихся АТС в часы пик не превышало 1ШАХ=2000 (по площади это

12

примерно соответствует району, включающему несколько улиц в центре Москвы). Отдельно по каждому району 3-го уровня движение ТП моделируется с помощью АА с учетом данных наблюдения о текущей ситуации на данном участке улично-дорожной сети, статистической информации и соблюдения граничных условий между смежными районами.

Схема действий АА приведена на рис. 5.

Осуи ¿ест'нлепие

дейстрий:

: *• •. •■• ~ - : равномерное дни же» I и с

дни же 11 ?! с с .у:с кор е и и е м

динжсние задним ходом

перестроенцс

на другу|&полосу

остановка

обгон (обьезд) разворот

о тправка сообщения КЛ ожидание сообщени я от К*Л

Выбор .маршрута

Планирован/ге

Выбор цели

Рис. 5 Схема действий агента-автомобилиста

Группы смежных районов 3-го уровня объединяются в более крупные районы 2-го уровня иерархии (округа). На этом уровне рассматриваются только интегральные характеристики ТП - классы состояний, определяемые на основе правил вида (6). Районы 2-го уровня объединяются в единственный район 1-го уровня, соответствующий всему мегаполису.

Прогнозирующие агенты определяют прогноз динамических состояний ТП для заданного временного интервала Т = (10Дк) согласно правилам (7-8). Каждый ПА прогнозирует состояния ТП, движущегося на определенном участке улично-дорожной сети, взаимодействуя при этом с координатором и другими ПА. Схема действий ПА дана на рис. 6.

Рис. 6 Схема действий прогнозирующего агента 13

Районы -го уровня

¥ -г- , «

рагч>, I м> ulxp:;unei) Щвvnp;;B\еп:гл III для кдМуДоГо района2-го )ровтц

.ВаавтеениеприаришговрайоиакЗгГо уровня« завиеимос от интенсивное!^ и напряженности дорожи») о движения.

Координирующие агенты обеспечивают согласованность действий и разрешение конфликтных ситуаций, реализуют управление ТП, а также взаимодействуют с другими агентами для совместного решения конкретных задач. Координирующие агенты делятся на 3 подкласса (согласно представленной на рис. 4 иерархической структуре) и обозначаются Каг,, где г=1,2,3 - уровень (подкласс) агента, } - его порядковый номер на г-ом уровне. Каждый агент КаГ] отвечает за определенный район мегаполиса Наг, (рис. 7).

- координирование Л А.; светофорное регулирование ТП; распределение дополнительныхресурсов.

Рис. 7. Структура взаимодействия КА на разных уровнях

КА 1-го уровня определяет управление ТП в рамках всего мегаполиса, назначая коэффициенты, соответствующие критериям качества управления.

КА 2-го уровня определяет величину управляющего воздействия на каждый ТП в пределах соответствующего района 2-го уровня (согласно правилам вида (9)).

КА 3-го уровня производит структурный анализ и классификацию состояний ТП в своем районе (согласно правилам вида (6)), ставит задачи для прогнозирующих агентов, взаимодействует с КА 2-го уровня и осуществляет непосредственную реализацию управляющих воздействий на ТП.

При программной реализации МАИТС использованы несколько видов программного обеспечения: пакеты AnyLogic 5.0 и Matlab, а также разработанный автором для поддержки применяемого в системе аппарата логики Аллена набор внешних приложений, написанных на языке Java. Структура программного обеспечения системы представлена на рис. 8.

AnyLogic

| Fuzzy Logic Toolbox | (система Matlab)

поддержка аппарата логики Аллена, реализация представления знаний и алгоритмов.

осуществление нечеткого вывода по алгоритму Мамдани.

Структура программного обеспечения МА И ТС

-Интерфейс и оболочка системы; -имитационное моделирование ТП и окружающее среды; ^управление и настройка системы;

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

ЩШШШВШЩ

информация о предметной области

Рис. 8. Структура программного обеспечения разработанной системы

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

Глава 4 описывает экспериментальную проверку адекватности МАИТС, анализ результатов эксперимента, а также свойств и особенностей разработанной системы.

Методика экспериментальной проверки МАИТС включает 4 этапа.

1. Имитационное моделирование дорожного движения в районах 1 -ой Тверской-Ямской улицы (Район 1), проспекта Мира (Район 2) и Рязанского проспекта (Район 3).

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

3. Прогнозирование динамических состояний ТП на временном интервале Т. Ошибка прогнозирования АР равна отношению количества N0UJ ошибочно определенных состояний к общему количеству No6.

4. Анализ эффективности управления и ее зависимости от величины схда (доли АА, обладающих обратной связью с КА), которая при разных экспериментах составляет 10%, 25%, 50% или 100% от общего числа АА. Эффективность управления характеризуется коэффициентом увеличения средней скорости pv и коэффициентом уменьшения заторов рз.

Были проведены 54 эксперимента (18 по каждому району) для разных дней недели и времени суток, что позволило испытать МАИТС на всем диапазоне возможных значений исходных данных.

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

Погрешность прогнозирования (3-ий этап эксперимента) согласно результатам экспериментальной проверки приведена в таблице 1:

Погрешность прогнозирования в МАИТС_Таблица 1

Д1 (мин) Погрешность прогнозирования (%)

Район 1 Район 2 Район 3

10 3.2-9.1 5.3-10.2 6.5-11.5

20 9.1-15.1 9.8-14.4 13.1-18.7

30 12.5-19.0 13.1-20.6 14.9-21.4

60 17.9-21.6 18.7-25.4 20.1-28.1

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

Результаты проведенных экспериментов показали, что перечисленные факторы увеличивают погрешность прогнозирования на 4-23%.

Наиболее важным критерием работоспособности МАИТС является эффективность управления ТП. В таблице 2 приведены экспериментальные данные об эффективности управления ТП в зависимости от величины ам.

Эффективность управления ТП в МАИТС _Таблица 2

<хаа(%) Р,(%)

10 4.9-8.2 6.1-10.3

25 12.4-18.4 12.6-23.1

50 10.9-24.6 12.3-19.0

100 4.2-12.0 7.1-14.3

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

В заключении сформулированы основные результаты работы.

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

16

Основные результаты работы

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

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

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

4. Разработана методика адаптивного управления ТП на основе нечеткого вывода и применения формализмов временной логики, которая:

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

- позволяет учитывать динамические и стохастические свойства ТП, а также координировать поведение участников дорожного движения в соответствии с полученным прогнозом;

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

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

6. Программно реализована многоагентная интеллектуальная транспортная система (МАИТС), соответствующая сформулированным принципам управления ТП мегаполиса.

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

Публикации по теме диссертации

1. Могорас A.A. Интеллектуальный мониторинг для мультиагентных систем управления с темпоральным представлением знаний. // Обозрение прикладной и промышленной математики; ISSN 08698325. - М.: ОПиПМ, 2005, том. 12 - с. 1040-1041.

2. Могорас A.A. Моделирование и прогнозирование транспортных потоков с помощью нечеткой временной логики. // Естественные и технические науки; ISSN 1684-2626. - М.: «Компания Спутник+», 2009, №1 - с. 283-289.

3. Тюхов Б.П., Могорас A.A. Прогнозирование и управление дорожным движением на основе интеллектуальных агентов. И Естественные и технические науки; ISSN 1684-2626. - М.: «Компания Спутник+», 2009, №2 - с. 372-379.

4. Могорас A.A. Исследование и программная реализация метода абдукции для интервальной логики Аллена // Тезисы докладов, Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. - М.: МИЭМ, 2005. - с. 389-390.

5. Могорас A.A. Логико-динамическая система управления транспортными потоками, на основе гетерогенных агентов. // Тезисы докладов, Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ - М.: МИЭМ, 2006- с. 154-155.

6. Могорас A.A. Логико-динамическая система управления транспортными потоками, на основе интеллектуальных агентов. // Тезисы докладов, XIV международная студенческая школа-семинар «Новые информационные технологии» - М.: МИЭМ, 2006 - с. 121-123.

7. Могорас A.A. Интеллектуальная система ситуационного управления транспортными потоками, на основе гетерогенных агентов. // Тезисы докладов, Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. - М.: МИЭМ, 2007. - с. 244-245.

8. Могорас A.A. Система ситуационного управления транспортными потоками, на основе интеллектуальных агентов. // Тезисы докладов, XV международная студенческая школа-семинар «Новые информационные технологии». - М.: МИЭМ, 2007. - с. 46-47.

9. Могорас A.A. Имитационное моделирование динамики транспортных потоков на основе аппарата нечеткой логики. // Тезисы докладов, Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. - М.: МИЭМ, 2008. - с. 346-348.

10. Могорас A.A. Моделирование, структурный анализ и прогнозирование динамических характеристик транспортных потоков на основе аппарата нечеткой логики. // Тезисы докладов, XVI международная студенческая школа-семинар «Новые информационные технологии». - М.: МИЭМ, 2008. - 192-193.

11. Тюхов Б.П., Могорас A.A. Прогнозирование и оптимизация транспортных потоков на основе интеллектуальных агентов с применением нечеткой логики. // Тезисы докладов, XVI Международная конференция «Проблемы управления безопасностью сложных систем» - М.: ИПУ, 2008. - с. 258-262.

12. Могорас A.A. Моделирование и прогнозирование транспортных потоков с помощью нечеткой модальной логики. // Тезисы докладов, Ежегодная научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ - М.: МИЭМ, 2009. - с. 192-194.

Отпечатано в ООО «Компания Спутник+» ПД № 1-00007 от 25.09.2000 г. Подписано в печать 27.12.2010 Тираж 100 экз. Усл. п.л. 1,0 Печать авторефератов (495)730-47-74,778-45-60

Список принятых сокращений.—.

Введение.

1. Аналитический обзор моделей, методов; и информационно-коммуникационных технологий^ применяемых при управлении транспортными потоками^.

1.1 .Интеллектуальные-' транспортные" системы (ИТС): определение, классификация, история развития^.—

1.2.Модельно-алгоритмическое обеспечение ИТС.

1.2.1. Основные параметры и классификации состояний транспортного потока.

1.2.2. Аналитическое моделирование транспортных потоков.

1.2.3: Имитационное моделирование транспортных потоков.;.

Г.З.Перспективные направления развития ИГС.V.

1.3.1. Применение в ИТС видеонаблюдения и телематики.

1.3 .2. Применение нечеткой логики в , ИТС.

1.3 .3 . Применение агентов в ИТС.

1.4. Анализ преимуществ и недостатков существующих ИТС.

1.5.Постановка задачи управления транспортными потоками мегаполиса посредством ИТС.

Выводы.„.

2. Моделирование, анализ, прогнозирование и управление транспортными потоками на основе нечеткого вывода и применения формализмов временной логики.

2.1 .Функциональная схема управления транспортными потоками.

2.2.Имитационная модель транспортного потока..:.;.

2.3.Спецификация и иерархия лингвистических переменных.

2.4.Моделирование поведения.участников дорожного движения.

2.5.Представление динамики транспортного потока с; помощью формализмов временной логики Аллена.

2.6-МЪдель агрегации/сегрегации потоков;—.

2.7.Алгоритмлранзитивного замыкания семантических сетей:.

2.8.Шространственно-временной анализ-транспортнь1Х. потоков:.

2.9:Вёктор состояния транспортного потока.

2.10: Классификация состояний транспортного потока.----------.

2.11. Прогнозирование динамики состояний транспортных потоков;

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

2.13. Светофорное регулирование транспортных потоков на системе; перекрестков.

Выводы.

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

3.1 .Постановка задачи многоагентного имитационного моделирования и ее решение в среде AnyLogic:.

3.2.Структура многоагентной системы МАИТС.

3.31Коммуникация агентов и^разрешение конфликтов:.

314. Агентгавтомобилист. 108;

3:4.1. Структура агента-автомобилиста.

3;4.2МТоведение агента-автомобилиста.

3.4.3; Классификация агентов-автомобилистов.

3.4.4. Поиск оптимальных маршрутов с помощью алгоритма« А*.

3; 5. Прогнозирующий агент.

3:5. Г. Структура прогнозирующего агента.

3.5.2. Построение прогноза в МАИТС.

3.6.Координирующий агент.:.

3.6.1. Структура координирующего агента;.

3.6.2. Управление транспортными потоками посредством координирующих агентов:.;.

3.7.Программное обеспечение системы МАИТС.

3.8.Программная реализация системы МАИТС.

Выводы.

4. Проверка эффективности разработанной системы и анализ ее преимуществ и недостатков.

4.1 .Методика экспериментальной проверки.

4.2.Результаты экспериментов и их анализ.

4.3.Графическая интерпретация состояний транспортного потока и их прогноза.

4.4.Сравнение с другими ИТС.

4.5. Анализ свойств, особенностей и возможностей дальнейшего совершенствования разработанной системы.

Выводы.

Актуальность работы

В4 настоящее время практически* во всех мегаполисах темпы роста автомобильного парка значительно опережают развитие улично-дорожной сети. Это порождает ряд проблем дорожного движения: транспортные заторы, снижение безопасности, загрязнение окружающей среды. В Москве эти проблемы усугубляются из-за исторически сложившейся радиально-кольцевой планировки города и разобщенности мест работы и проживания» [40]. В этих условиях начиная с 1990-х годах в развитых странах (США, Зап. Европа, Япония и др.) начали разрабатывать полностью автоматизированные системы дистанционного централизованного1 оперативного управления дорожным движением в режиме реального времени, получившие название интеллектуальных транспортных систем (ИТС). Эксперты считают применение ИТ€ одним из наиболее перспективных способов^ решения перечисленных задач дорожного движения ([71], [85], [89]).

Развитие ИТС сопровождается повышением уровня технической оснащенности транспортной инфраструктуры мегаполисов, разработкой более совершенных средств оперативного мониторинга, анализа и перераспределения транспортных потоков-(ТП), а также развитием систем искусственного интеллекта [44], [45]. Это дает достаточный потенциал для создания ИТС, обладающих принципиально новыми возможностями управления дорожным движением. Однако для создания- таких систем требуется проведение дополнительных теоретических исследований в области моделирования, анализа и прогнозирования транспортных потоков, выявления закономерностей* влияния различных факторов и формализации знаний о предметной области.

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

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

Задачи исследования

1. Анализ моделей, методов и> информационно-коммуникационных технологий, применяемых при управлении дорожным движением.

2. Разработка функциональной схемы управления? ТП мегаполиса посредством ИТС.

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

4: Выбор математического аппарата и разработка методики анализа, прогнозирования динамики состояний и оптимизирующего управления ТП.

5. Создание структуры и баз знаний многоагентной ИТС, реализующей данную методику.

6. Программная реализация многоагентной ИТС. .

7. Экспериментальная проверка работоспособности и анализ полученной многоагентной ИТС.

Методы исследования основаны на использовании принципов системного подхода и-искусственного; интеллекта, теории множеств, и теории графов, теории агентов и. многоагентных систем,. модальной и нечеткой логики, методов оптимизации и имитационного моделирования, а также теории ТП.

На защиту выносятся следующие научные результаты:

- функциональная схема управления ТП мегаполиса посредством ИТС;

- имитационная модель неоднородного ТП;

- методика анализа, прогнозирования динамики состояний и управления ТП;

- структура и БЗ многоагентной ИТС, реализующей данную методику.

Научная новизна содержится в следующих результатах работы: функциональная схема управления ТП мегаполиса посредством многоагентной ИТС; имитационная модель неоднородного ТП на основе гетерогенных агентов и применения формализмов нечеткой временной логики, что позволяет учитывать особенности структуры ТП и поведения участников дорожного движения; методика структурного анализа, прогнозирования динамики состояний и управления ТП на основе интеллектуальных агентов, что повышает эффективность ИТС и делает ее устойчивой к нештатным ситуациям и влиянию различных факторов;* структура и БЗ многоагентной ИТС, отличительными особенностями которой является наличие прогнозирующих агентов (ПА), иерархически организованная система координации, а также моделирование различных типов поведения водителей в ТП.

Практическая полезность

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

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

Реализация результатов

Полученные в диссертационной работе результаты были программно реализованы и использованы в учебном процессе МИЭМ при обучении студентов на кафедре "Математическое обеспечение систем обработки информации и управления" и в практической деятельности организации ООО «СМИЛИНК», работающей в области сбора, обработки и анализа информации о дорожном движении.

Апробация работы

Результаты работы докладывались в 2008 г. на XVI Международной конференции «Проблемы управления безопасностью сложных систем», ИПУ, Москва; в 2005, 2006, 2007, 2008 и 2009 гг. на Ежегодной научно-технической конференции студентов, аспирантов и молодых специалистов МИЭМ, Москва; в 2005, 2006, 2007, 2008 и 2009 гг. на Международной студенческой школе-семинаре, Судак.

Публикации

Основные результаты диссертации опубликованы в 12 научных работах, в том числе 3 публикации в журналах из Перечня ВАК.

Структура работы

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