=Paper=
{{Paper
|id=Vol-1787/561-566-paper-98
|storemode=property
|title=Распределенная программная система автоматического построения схемы городской транспортной сети (Distributed program system for automatic construction of the city traffic scheme)
|pdfUrl=https://ceur-ws.org/Vol-1787/561-566-paper-98.pdf
|volume=Vol-1787
|authors=Natalia Puchkova,Nikolay Ershov
}}
==Распределенная программная система автоматического построения схемы городской транспортной сети (Distributed program system for automatic construction of the city traffic scheme)==
https://ceur-ws.org/Vol-1787/561-566-paper-98.pdf
Распределенная программная система
автоматического построения схемы городской
транспортной сети
Н.А. Пучкова1,a, Н.М. Ершов1,2,b
1
ГБОУ ВО Московской области "Университет "Дубна"
141980, Московская область, г. Дубна, ул. Университетская, 19
2
Московский государственный университет им. М. В. Ломоносова, факультет ВМК
119991, Москва, ГСП-1, Ленинские горы, д. 1, стр. 52, факультет ВМК
E-mail: a pu4kova.nata@ya.ru, b ershov@cs.msu.ru
В работе рассматриваются вопросы, связанные с построением цифрового описания схем движе-
ния городского транспорта на основе геолокационных данных, получаемых с мобильных устройств (те-
лефоны, планшеты). Такое описание может в дальнейшем использоваться либо для компьютерного мо-
делирования движения транспорта, например, с целью оптимизации той или иной дорожной развязки,
либо для разработки алгоритмов и программ управления автономными транспортными средствами. Од-
ной из проблем, связанных с использованием геолокационной информации, является ее сильная зашум-
ленность. Поэтому на предварительном этапе исследования был разработан ряд алгоритмов, позволяю-
щих по нескольким трекам, соответствующим одному и тому же участку дороги, провести процедуру
удаления шума и выделить так называемые «чистые» траектории движения транспорта по данному уча-
стку дороги. Серьезным недостатком такого подхода оказалась необходимость в существенной ручной
предобработке входных данных, например, в пространственной синхронизации отдельных треков.
В настоящей работе предлагается следующая схема решения исходной задачи. Разрабатывается
программа-геотрекер для мобильных устройств, служащая для сбора ими первичной геолокационной
информации в непрерывном режиме. Эта информация автоматически пересылается на некоторое облач-
ное хранилище данных, откуда забирается сервером, выполняющим всю статистическую обработку дан-
ных. На первом этапе с использованием методов машинного обучения из треков выделяются части, соот-
ветствующие движению на транспортных средствах (автомобилях). На втором этапе производится про-
странственная синхронизация треков, т.е. разбиение их на фрагменты, относящиеся к одинаковым
участкам дорог. На третьем этапе выполняется выделение «чистых» траекторий движения транспорта и
связывание их в общую систему. Данная работа посвящена разработке алгоритмов решения задач, воз-
никающих на первом и третьем этапах описанной схемы. Приводятся результаты численных исследова-
ний, основанных на анализе реальных данных движения транспорта в городе Дубна Московской области.
Ключевые слова: транспортные модели, распределенные системы, геолокация.
Работа выполнена при финансовой поддержке РФФИ (грант № 14-07-00628 А).
© 2016 Наталья Александровна Пучкова, Николай Михайлович Ершов
561
Введение
В работе рассматриваютсся вопросы, связанные с построением цифроввого описания схем
движения городского транспор рта на основе геолокационных данных. Такоее описание может в
дальнейшем использоваться либо для компьютерного моделирования дви ижения транспорта,
например, с целью оптимизацции той или иной дорожной развязки, либо длля разработки алго-
ритмов и программ управленияя автономными транспортными средствами.
Одной из проблем при исспользовании геолокационной информации является ее сильная
зашумленность. Поэтому на первом этапе исследования были разработаны ы алгоритмы, позво-
ляющие по нескольким трекам м, соответствующим одному и тому же участкки дороги, провести
процедуру удаления шума и выделить «чистые» траектории движения тран нспорта по данному
участку дороги. Серьезным неедостатком такого подхода оказалась необхоодимость в сущест-
венной ручной предобработке входных данных.
Предлагается следующаяя схема решения исходной задачи. Разрабаты ывается программа-
геотрекер для мобильных устр ройств, служащая для сбора ими первичной геолокационной ин-
формации в непрерывном реж жиме. Эта информация автоматически пересыллается на некоторое
облачное хранилище данных, откуда забирается сервером, выполняющим всю статистическую
обработку данных. На первом этапе с использованием методов машинного обучения из треков
выделяются части, соответствуующие движению на транспортных средствахх (автомобилях). Да-
лее производится разбиение этих треков на фрагменты, относящиеся к оддинаковым участкам
дорог. На третьем этапе выполлняется выделение «чистых» траекторий движжения транспорта и
связывание их в общую системму.
Настоящая работа посвящ
щена разработке алгоритмов решения задач, воозникающих на пер-
вом и третьем этапах вышеопи исанной схемы. Приводятся результаты числеенных исследований
на основе реальных данных дввижения транспорта в городе Дубна.
Тестирование сущесттвующих решений
Для создания схемы сети
и дорог нам необходимы координаты этих доорог. В связи с этим
было решено использовать мо
обильный телефон (под управлением ОС Anddroid) с поддержкой
GPS и установленным приложеением для записи трека.
Рис. 1. Примеры зашумленных треков Рис. 2. Трек с разрывами в записи
Для тестирования существующих решений на Google Play Market было выбрано семь пр
при-
ложений,
ний, из которых четыре было отброшено сразу в силу низкого качества выдаваемых ими
данных. Оставшиеся три приложения были протестированы на записи реальных траекторий
562
(треков) движения легкового и общественного транспорта в городе Дубна Московской области.
Результаты тестирования выяввили две основные проблемы, связанные с поллученными геолока-
ционными данными: сильная зашумленность этих данных (рисунок 1) и раззрывы в записи (на-
пример, из-за потери связи со спутниками, рисунок 2). Поэтому первая посставленная нами за-
дача была связана с решениемм этих двух указанных проблем – имея сериюю зашумленных тре-
ков с возможными разрывами в записи выделить из них ту реальную траеккторию, по которой
происходит движение транспор рта.
Автоматическое усрееднение треков
Предполагается, что имеюются записи нескольких треков, соответствующ щих одной и той же
траектории движения транспор рта, в частности, все треки начинаются в одн ной точке и в одной
точке заканчиваются. Требуетсся выделить из этих данных «чистую», т.е. нее зашумленную тра-
екторию, по которой реально движется транспорт. Было предложено и реаализовано два алго-
ритма решения поставленной задачи.
Первый алгоритм (Forces)) основан на моделировании сил упругости и ггравитации. Для по-
лучения усредненного трека выполняются следующие шаги: 1) выбираетсся вспомогательный
трек без разрывов; 2) на этом треке равномерно расставляются узлы; 3) к узлам применяются
силы: со стороны соседних узллов этого трека действует сила упругости, со стороны точек всех
остальных треков – сила приттяжения; 4) производится суммирование силл для каждого узла;
5) после нахождения действую ющих сил для всех узлов, производится перем мещение каждого уз-
ла на новое место. Все шаги вы
ыполняются до тех пор, пока система не придеет в равновесие.
Второй алгоритм (Median) n основан выполнении параметризации кооординат всех треков
относительно (нормированного о) времени t. Затем по времени t строится новвая равномерная сет-
ка и во всех узлах этой сетки вычисляется средняя точка среди всех траектторий, причем, в ка-
честве средней берется медианна, что позволяет эффективно бороться с отдеельными значитель-
ными «выбросами».
Рис. 3. Пример работы алгоритма Median Рис. 4. Пример работы алгоритма Forces
Данные методы усреднения треков были численно протестированы на трех разных иску искус-
ственных траекториях: гладкая кривая (парабола),
( ломаная линия без самопересечений ((траек-
тория типа «П») и ломаная линия с самопересечениями («Бабочка»).
( Были созданы по 10 зза-
шумленных вариантов каждой из этих кривых, по которым и выполнялось усреднение. Н На ри-
сунках 3 и 4 показаны результаты тестирования
тестирова для траектории «Бабочка».
Помимо этого на тех же искусственных примерах была рассчитана погрешность работы
данных методов (рисунок 5).. Было выяснено, что 1) при увеличении числа точек трека умень-
шается размер ошибки;; 2) погрешность обоих методовов примерно одинаковая
одинаковая. Но т.к. алгоритм
Median работает намного быстрее, чем алгоритма Forces, было решено использовать именно
алгоритм Median для дальнейшего тестировании уже на реальных данных.
563
Рис. 5. Зависимость погрешности алгоритмов усреднения треков
от числа точек измерения
На рисунке 6 показаны
аны два примера применения алгоритма Median к анализу реальных
треков, записанных при движении на общественном транспорте (автобусы и маршрутные та
так-
си) в городе Дубна Московской области.
Рис. 6. Примеры усреднения реальных треков
564
Архитектура системы
Серьезным недостатком описанного выше подхода оказалась необходимость в существен-
ной ручной предобработке входных данных, например, в пространственной синхронизации
различных треков. Поэтому была предложена следующая архитектура программной системы
автоматической генерации схем дорожного движения (рисунок 7).
Рис. 7. Архитектура разрабатываемой программной системы
1) Разрабатывается программа-геотрекер для мобильных устройств, служащая для сбора
ими первичной геолокационной информации в непрерывном режиме. Эта информация
автоматически пересылается на некоторое облачное хранилище данных, откуда заби-
рается сервером, выполняющим всю статистическую обработку данных.
2) На следующем этапе с использованием методов машинного обучения выполняется
классификация треков, из них выделяются части, соответствующие движению на
транспортных средствах (автомобилях).
3) На третьем этапе производится пространственная синхронизация треков, т.е. разбие-
ние их на фрагменты, относящиеся к одинаковым участкам дорог.
4) На четвертом этапе с использованием вышеописанных алгоритмов усреднения выпол-
няется выделение «чистых» траекторий движения транспорта.
5) Наконец, на последнем этапе все выделенные траектории связывают в общую систему.
В настоящее время разработан пилотный вариант алгоритма для автоматической класси-
фикации треков по типу используемого транспорта, основанный на методе логистической рег-
рессии. Ведется работа по решению остальных задач.
Список литературы
Haunert J.-H., Budig B. An algorithm for map matching given incomplete road data // Proceedings of
the 20th International Conference on Advances in Geographic Information Systems
(SIGSPATIAL '12). ACM, New York, NY, USA, 2012, Pages 510-513.
Петров М.А., Ершов Н.М. Модель сети дорожного движения на основе расширенной сети Пет-
ри // Современные проблемы прикладной математики и информатики: Тезисы докладов
международной конференции (Дубна, 25-29 августа 2014 г.). — Дубна: ОИЯИ, 2014. —
С. 103–106.
Petrov M., Ershov N. Model seti dorozhnogo dvizheniya na osnove rasshirennoy seti Petri [Simulation of the city traf-
fic by using extended Petri networks] // Modern problems of applied mathematics and computer science, International
conference for young scientists, Dubna, August 25 – 29, 2014. — Dubna: JINR, 2014. — P. 103-106 (in Russian).
565
Distributed program system for automatic
construction of the city traffic scheme
N. A. Puchkova1,a, N. M. Ershov1,2,b
1
Moscow Region State Educational Institution for higher professional education University “Dubna”
19, Universitetskaya str., Dubna, Moscow region, 141980, Russia
2
Lomonosov Moscow State University, the Faculty of Computational Mathematics and Cybernetics
MSU, Faculty of Computational Mathematics and Cybernetics,
1-52, Leninskiye Gory, GSP-1, Moscow, 119991, Russia
E-mail: a pu4kova.nata@ya.ru, b ershov@cs.msu.ru
The paper discusses issues related to the construction of a digital description of the city traffic schemes on
the basis of geo-location data, obtained from mobile devices (phones, tablets and so on). This description may
later be used for computer modeling of traffic, for example, to optimize a particular junction. Or it can be used to
the development of algorithms for autonomous vehicle control programs. One of the problems associated with
the use of geolocation information that it is very noisy. Therefore, on the preliminary phase of the study we de-
veloped a number of algorithms that allow us to extract «pure» tracks from the set of noisy records correspond-
ing to the same section of road. A serious drawback of this approach was the need for significant manual pre-
processing of the input data, for example, for spatial synchronization of individual records.
In this paper, we propose the following scheme for solving the original problem. Special software (geo-
tracker) for mobile devices is written, which serves to collect in continuous mode primary geolocation infor-
mation. This information is sent to a cloud data storage, where is taken from by the server, which performs all
the statistical data processing. In the first stage we extract from the given records their parts corresponding to the
movement by use of vehicles. We do it by using machine learning methods. At the second stage the spatial syn-
chronization of tracks (i.e. splitting them into fragments referring to the same road sections) should be per-
formed. In the third final phase, the extraction of «pure» traffic paths and tying them into the overall system
should be done. This work is devoted to the development of algorithms for solving problems arising in the first
and third stages of this scheme described above. The results of numerical studies based on the analysis of real
data traffic in the city of Dubna (Moscow Region) are presented.
Keywords: traffic modeling, distributed systems, geolocation
The work was supported by Russian Foundation for Basic Research (RFBR Project 14-07-00628).
© 2016 Natalia A. Puchkova, Nikolay M. Ershov
566