Известия РАН. Теория и системы управления, 2022, № 1, стр. 76-82

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

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

1. Постановка задачи и основная модель. Для построения расписания необходимо в первую очередь реализовать модель движения агентов. В статье для этой цели используется дополненная модель, описанная в [1, 5].

Для тестирования интеллектуальной системы был выбран линейный участок на графе железнодорожной сети Монголии, включающий в себя шесть станций и пять перегонов между ними. Каждая станция состоит из трех или более станционных путей. Инфраструктурным сегментом считается станционный путь или перегон между станциями. Для каждого сегмента известны его название, длина и смежные с ним инфраструктурные сегменты. Каждый инфраструктурный сегмент может находиться в одном из трех возможных состояний: “normal”, “locked”, “reduced speed”. Состояние сегмента “normal” означает, что он доступен для движения и на нем нет никаких ограничений. Состояние сегмента “locked” означает, что на нем произошел аншлаг. Аншлагом называется любой запрет движения агентов по данному сегменту. Для каждого аншлага задается номер сегмента и его продолжительность, т.е. время начала и время окончания запрета. Состояние сегмента “reduced speed” означает, что движение по данному сегменту разрешено, однако максимально допустимая скорость агентов ограничена. Максимальное значение скорости в данном случае задается отдельно.

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

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

Каждый агент может находиться в одном из следующих состояний. Состояние “stay” соответствует движению агента по перегону либо остановке на станции, согласно плановому графику движения. Состояние “move” является командой и означает, что агент, который простоял на станционном пути необходимое по плану количество времени, может начать движение к следующей станции по смежному перегону. Агент находится в этом состоянии один момент времени, после чего состояние агента становится “stay”. Состояние “wait” служит командой и означает, что агент, который простоял на станционном пути необходимое по плану количество времени, может продолжать стоянку на этом станционном пути. Данное состояние реализуется только в течение пребывания поезда на станции. Эта команда отдается агенту в том случае, если начинать дальнейшее движение неоптимально в данный момент времени. Состояние “skip” устанавливается для агента, который достиг конечную точку своего маршрута. Такие агенты игнорируются при дальнейшей работе алгоритма.

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

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

Отклонение от планового графика движения является целевой функцией, который минимизируется в рассматриваемой оптимизационной задаче и рассчитывается по формуле из [1]:

где $i$ – индекс агента, $j$ – индекс сегмента из множества W_i, обязательных для посещения, согласно маршруту агента $i$, ${{\omega }_{i}}$ – весовой коэффициент агента $i$ на основе его типа – задается вручную для каждого агента, ${{T}_{{ij}}}$ – изменение времени прибытия агента $i$ на станцию  j по сравнению с нормативным графиком, $\theta $ – тензор весовых коэффициентов нейронной сети.

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

Для маршрутов введем термин нитки. В рамках данной терминологии будут рассматриваться исходные, плановые, исполненные и прогнозные нитки. Каждая нитка задается следующим набором параметров: время начала нитки, приоритет и тип агента движения, массив составляющих ее фрагментов. Фрагментом обозначается совокупность инфраструктурного сегмента, через который проходит нитка, и времени пребывания агента в состоянии “stay” на этом сегменте.

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

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

На рис. 2 представлен алгоритм построения дерева возможных вариантов развития графика движения.

Узлом дерева является вариация состояния всех сегментов и агентов движения в данный момент времени, т.е. массивы агентов и сегментов в некоторых состояниях. В каждом узле содержится информация о смежных узлах дерева – родителе и потомках, текущем отклонении от исходного планового графика, а также флаг события, показывающий, произошло ли какое-либо событие в момент времени, соответствующий данному узлу. Листьями дерева выступают последние рассчитанные варианты. Корень дерева – состояние сегментов и агентов в начальный момент времени. Он устанавливается при инициализации системы. Узлы следуют друг за другом, количество потомков для одного узла может быть больше одного. Несколько потомков создаются за счет вариативности предпринимаемых мер управления, т.е. наборов команд, отдаваемых агентам при возникновении событий. Работа алгоритма заключается в построении данного дерева оптимальным образом и поиску ветви дерева, соответствующей наилучшей стратегии управления движением. При построении дерева используются вариация алгоритма метода Монте-Карло поиска по дереву [6], алгоритм Дейкстры [7], а также отдельные алгоритмы теории графов, такие, как BFS [8], DFS [7]. Результатом работы алгоритма является набор ниток по самой оптимальной ветви дерева стратегий, которые в свою очередь и представляют оптимальное расписание движения, передаваемое пользователю.

Алгоритм построения нового узла дерева стратегий заключается в следующем.

Шаг 1. Новые узлы строятся как продолжение одного из имеющихся листов дерева. Изначально лист только один – корень дерева. В структуру узла в первую очередь вносятся агенты, которые уже сформированы и готовы начать свое движение. Для этих агентов устанавливается состояние “stay”. В том случае, если стартовый сегмент маршрута агента занят, его появление откладывается до освобождения данного сегмента.

Шаг 2. На втором шаге осуществляется обновление состояния инфраструктурных сегментов участка. Меняется их статус или, например, появляются новые аншлаги.

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

Шаг 4. Выполнение команд управления движением агентов, унаследованных от предыдущего узла. Так, например, исполнение команды “move” для некоторого агента приводит к его перемещению со станционного пути на смежный перегон и установке состояния “stay”. В процессе выполнения команд осуществляется проверка на то, что исполнение команды не приведет к возникновению deadlock (deadlock или взаимоблокировка – ситуация, при которой несколько агентов находятся в состоянии ожидания сегментов, занятых друг другом, и ни один из них не может продолжать свое движение). Например, не допускается загруженность агентами локальной области участка графа так, чтобы не оставалось ни одного свободного станционного пути.

Шаг 5. В соответствии с формулой (1.1) обновляется текущее суммарное временное отклонение от планового графика движения всех агентов.

Шаг 6. Создаются варианты наборов допустимых команд для агентов в данном узле, которые затем передаются в узлы-потомки для исполнения их на следующей итерации цикла в шаге 4. Углубление веток происходит с вероятностью, линейно пропорциональной оценке отклонения от планового графика движения. Данный подход является разновидностью метода Монте-Карло поиска по дереву.

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

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

На рис. 3 представлен пример deadlock на случайно сгенерированных нитках исполненного движения.

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

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

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

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

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

Дальнейшее развитие предложенного метода заключается в следующем: отладка существующего решения в соответствии с замечаниями, выявленными в процессах блочного и интеграционного тестирований; реализация возможности пакетного пропуска агентов (возможность пропускать несколько агентов на перегон в одном направлении); оптимизация основного алгоритма игровых стратегий с использованием алгоритмов на графах (BFS, DFS, Dijkstra) для поиска допустимых маршрутов движения и ускорения построения дерева стратегий, а также отсеивание лишних ветвей на основе анализа плотности потока агентов через участок; внедрение оптимизации для прогнозирования циклического движения (пригородное движение, Московское центральное кольцо, Московские центральные диаметры, метро), а именно замена текущей целевой функции, показывающей отклонение от нормативного графика движения, на целевую функцию, работающую с интервальным движением.