게임이론 기반 도시철도 자율주행 연구

Abstract

기존의 열차 재스케줄링 문제는 시스템 최적화 모형에 기반을 두어 해결되어왔다. 하지만 열차 재스케줄링 문제의 최적화 모형은 계산의 복잡도의 한계로 실제 열차의 운행에 사용되기에는 부적합하였다. 또한 최근 도시철도에서 기존 관제 방식의 한계로 열차 중심의 열차 제어 방식이 연구되고 있다. 이러한 배경 하에서 본 연구에서는 열차 중심의 의사결정 방식이 도입되었을 때, 승객의 불확실성에 대응하여 승객의 불편함을 최소화하는 열차의 재스케줄링 문제를 다룬다. 이를 위해 도시철도의 재스케줄링 문제를 도시철도의 운행방식을 결정하는 열차의 불완전정보 순차 게임으로 모형화 하였다. 이 때 도시철도의 재스케줄링 문제는 모든 열차가 하나의 시스템을 구성하므로 본 게임에서는 내쉬 균형에서의 전체 전략이 각 사용자의 전략의 곱으로 주어진다는 가정이 완화된 Coarse Correlated Equilibrium을 통해 도시철도의 운행방식을 결정할 수 있다. 그에 따라 게임에서의 Coarse Correlated Equilibrium을 구하기 위해 No External Regret 알고리즘에 기반한 알고리즘을 제시하였다. 마지막으로 구한 균형을 최적화 모형의 해와 비교하여 제안한 모형의 적용 가능성을 살펴보았다.

The train rescheduling problem has been modeled by system optimization model. However, the system optimization model of the train rescheduling problem is inadequate for real urban railway operation due to the limitations of computational complexity. In recent years, train based train control system has been studied due to limitations of existing control system in urban railways. This paper introduces a train-oriented train rescheduling problem. The train-oriented train rescheduling problem is modeled by imperfect information sequential game of trains. In the rescheduling problem of the urban railway, all trains constitute one system, so in this game, the overall strategy can be determined by Coarse Correleated Equlibrium(CCE), which is relaxed the assumption that the overall strategy in the Nash Equilibrium is given by the product of each user's strategy. Then, we obtain CCE by regret minimization based algorithm. Finally, we provide quality of obtained equilibrium by solving system optimization model.