다중 에이전트 시스템을 이용한 실시간 도시철도 스케줄링

Abstract

열차 운행 중 예상치 못한 상황이 발생하여 더 이상 기존의 운행 계획대로 운영하 지 못할 때, 열차들은 경합이 없는 새로운 운행 계획을 필요로 한다. 열차 재스케줄링 문제는 이와 같은 상황에서 조정된 운행 계획과 기존 운행 계획의 오차가 최소화 되는 스케줄을 찾는 것을 말한다. 한편 열차 재스케줄링에 관한 많은 기존 연구들은 일반 철도의 상황에서 고려되었으며 일반 철도와는 다른 도시 철도의 특징 때문에 이를 도시 철도에 그대로 적용하는 것은 어렵다. 본 연구에서는 열차 재스케줄링 문제를 마르코프 게임(Markov game)으로 모형화 하여 확률적이면서도 동적인 도시 철도의 특성을 반영한다. 또한, 모형화된 마르코프 게임의 균형을 찾기위해 리그렛 매칭(regret matching) 알고리즘을 심층 학습(deep learning)으로 근사하여 적용하는 방법을 제안한다. 더 나아가 리그렛 매칭 알고리즘과 동일하게 균형을 찾음을 보장하면서 실제 적용 상황에서 더 빠른 수렴 속도를 가질 수 있는 멱리그렛 매칭(power-regret matching) 알고리즘을 제안한다. 심층 학습으로 근 사한 멱리그렛 매칭 알고리즘은 기존의 리그렛 매칭이 적용 불가능한 대규모 마르코프 게임에서도 적용할 수 있으며 리그렛 매칭 알고리즘보다 더 빠른 학습 속도를 가질 수 있음을 실험적으로 보였다.

When an unexpected situation arises during the train operation and the train can no longer operate according to the existing schedule, train system needs a new operation plan with no confliction. The problem of train rescheduling refers to finding a schedule that minimizes the error of the adjusted operation plan and the existing operation plan in such a situation. On the other hand, many previous studies on train rescheduling have been considered in the context of general railway and it is difficult to apply it to urban railway because feature of urban railway is different from general railway. In this study, urban train rescheduling problem is modeled as a Markov game, which reflects the features of urban railway which is both stochastic and dynamic. Also, we propose a method to approximate the regret matching algorithm with deep learning to find the equilibria of the modeled Markov game. In addition, we pro- pose a power-regret matching algorithm that guarantees the same equilibria as the regret-matching algorithm, but may have faster convergence speed in actual appli- cations. It has been experimentally shown that the power-regret matching algorithm approximated by deep learning can be applied to a large-scale Markov game in which conventional regret matching is not applicable and can have a learning speed faster than the regret matching algorithm.