Размещено на http://www.allbest.ru/

УДК 658.012:681.3

Маршрутизация и контроль движения технологических транспортных средств

В.М Левыкин, доктор технических наук, Харьковский национальный университет электроники.

И.В. Шевченко, Институт экономики и новых технологий

Анотація

Розглядається задача автоматизованого управління рухом технологічних транспортних засобів на технологічних площадках. Пропонована графова модель площадки, та на іі основі розроблено метод адаптивної маршрутизації та контролю руху транспортних засобів.

Ключові слова: технологічний транспорт; граф маршрутів; алгоритми управління; гнучка перенастройка маршрутів; безпека обраних шляхів.

1.1 Общие свойства модели

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

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

ТС использует для выезда не те же самые точки, что для въезда;

проезжая по площадке ТС не должно разворачиваться.

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

Для исключения циклических маршрутов, введём дополнительные условия:

1. Корректный маршрут должен содержать один и только один въезд, точку разворота, точку назначения и выезд, и именно в такой последовательности.

2. Участки корректных маршрутов между особыми точками не должны содержать повторяющихся вершин и ребер.

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

1.2 Способ построения корректных маршрутов

Обозначим через {xy}, xy, множество всех возможных путей на графе из вершины x в вершину y, таких, что каждый путь в этом множестве включает любое ребро и любую вершину не более одного раза. Для данных вершин x и y множество {xy} однозначно определяется методом поиска «в глубину» на графе маршрутов.

Если имеются множества путей {xy} и {yz}, где x, y, z - вершины графа, такие, что xy и yz, то декартово произведение этих двух множеств {xy}{yz} будет представлять собой новое множество путей, которые ведут из вершины x в вершину z через вершину y, и участки xy и yz не содержат самопересечений.

Пусть А - множество вершин-въездов, В - множество точек разворота, и С - множество точек назначения, и эти множества не пересекаются. Тогда:

множество корректных путей от точек въезда к точкам разворота задается выражением:

{ab}, aA, bB(1)

множество корректных путей от точек разворота к точкам назначения задается выражением:

{bc}, bB, cC(2)

множество корректных путей от точек назначения к точкам выезда задается выражением:

{ca}, aA, cC(3)

все корректные маршруты на графе задаются выражением:

{ab}{bc}{ca}, aA, bB, cC (4)

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

1.3 Транспортное средство на маршруте

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

TC = (C(C_x, C_y), d), C_xR, C_yR, dR, d > 0(5)

Будем говорить, что объект O (вершина или ребро) занят данным ТС=(C, d), если расстояние от объекта до центральной точки ТС меньше или равно радиусу ТС:

D(O, C) d(6)

Если О является вершиной графа, то расстояние D(O,C) от этой вершины до точки центра ТС определяется как длина отрезка, соединяющего O и C. В случае, если О представляет собой ребро графа (т.е. отрезок, соединяющий некие две вершины V₁ и V₂), расстояние от центральной точки ТС до О определяется следующим образом:

если точка пересечения перпендикуляра, опущенного из центральной точки ТС на ребро О, принадлежит этому ребру, то расстояние D(O,C) берется равным длине данного перпендикуляра;

в противном случае принимается, что:

D(O, C) = min (D(O, V₁), D(O, V₂)) (7)

1.4 Постановка задачи

Используя данные выше определения, задачу маршрутизации можно поставить следующим образом:

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

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

2 Общий подход к решению

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

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

Проанализировать текущее положение ТС на площадке, и определить, какой объект графа маршрутов занимает каждое ТС (см. п. 1.3).

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

Перейти к шагу 1.

Очевидно, что чем быстрее будет выполняться одна итерация данного цикла, тем чаще маршруты будут пересчитываться, и тем надежнее будет алгоритм. Поскольку алгоритм поиска «в ширину», используемый на шаге 2, имеет сложность Q(n²), где n - количество вершин графа, и поскольку шаг 2 выполняется для каждого ТС, то сложность одной итерации цикла для данного алгоритма составляет не менее

Q(n²_*m) ,(8)

где m - количество ТС на площадке.

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

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

Оценка сложности одной итерации цикла для такого алгоритма составляет Q(m), поскольку динамически рассчитывать маршруты ТС не нужно. Однако, выигрывая в скорости, такой подход проигрывает в гибкости, по двум причинам:

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

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

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

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

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

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

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

3. Алгоритм планирования и контроля движения

3.1 Общая схема алгоритма

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

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

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

Шаги 2 и 5 реализуются подсистемами локации ТС на площадке и пилотажного уровня соответственно. Детальное рассмотрение этих шагов выходит за рамки данной статьи.

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

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

3.2 Алгоритм расчета направления движения ТС

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

На рис.2 используются следующие обозначения:

TC = (C(C_x, C_y), d) - ТС, для которого производятся расчеты;

R(V_p, V_n) - ребро графа, по которому в данный момент времени следует ТС, из вершины V_p в вершину V_n;

W - текущий путь данного ТС.

Размещено на http://www.allbest.ru/

3.3 Алгоритм обработки непредвиденных ситуаций

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

Размещено на http://www.allbest.ru/

3.4 Обработка въезда нового ТС на площадку

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

Если такой возможности не предусмотрено, то для обработки въезда ТС на площадку используются алгоритмы, описанные в п.п. 3.2 и 3.3. Если на одном из въездов появляется новое ТС, маршрутизатор на шаге 3 схемы рис.1 отработает возможные коллизии, и если таковых нет, то на шаге 4 присвоит новому ТС определенный маршрут.

Размещено на http://www.allbest.ru/

Выводы

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

Математическое обоснование безопасности выбираемых путей.

Адаптивный выбор путей, при котором ТС может изменить маршрут в процессе следования.

Расширяемость модели и независимость алгоритма работы маршрутизатора от физической модели ТС.

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

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

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

Литература

1 Транспортные роботы для автоматизированного производства / В.П. Драгаев - Киев: Лыбидь, 1991.-240 с.

2. Шевченко И.В. Сравнительный анализ применения дальномерных и угломерных систем для автоматического управления маневрированием карьерных автосамосвалов.?сб. «Проблемы создания новых машин и технологий» - научные труды Кременчугского государственного политехнического института. 1999. Вып.2., с.92-95.

3 Шевченко И.В., Гура А.В. Навигационные радиосредства для автоматического маневрирования тяжелых автосамосвалов. Проблемы создания новых машин и технологий. Научные труды КГПИ. Вып.12000(8) Кременчуг: КГПИ, 2000 - с.247-250

Размещено на Allbest.ru