본문 바로가기
Paper Review

[논문리뷰] (MPLight) Toward a thousand lights:Decentralized deep reinforcement learning for large-scale traffic signal control

by 3neutronstar 2021. 7. 17.

이번에 리뷰할 논문은 교통공학 논문으로 AAAI 2020에 게재된 Toward a thousand lights:Decentralized deep reinforcement learning for large-scale traffic signal control 입니다. 자세한 내용은 원본 paper인 링크를 참조해주세요.

 

Motivation

 

Traffic congestion은 급격한 도시화로 인한 사회적 문제로 대두되고 있고, 이로 인해서 발생하는 이산화탄소와 같은 가스 발생량은 23%를 차지하고 있으며, 그 중 교통신호 시스템으로 인해 발생하는 배기가스는 40%에 달한다고 합니다. 이에 최근에는 효율적으로 제어하기 위해 Reinforcement Learning method를 적용하려는 시도들이 계속되고 있습니다. 

 

기존의 approach들에는 교통공학 적인 지식으로 접근하고자 하였으며, 다음과 같이 4가지 종류가 존재합니다.

-1. Pre-timed control

과거 real-time data를 기반으로 signal plan을 직접 연산한 다음 실행하는 제어 방식입니다.

-2. Actuated control

Pre-defined rule들과 real-time data(현재)를 기반으로 다음 신호를 제어하는 방식으로 보통 차량의 queue length에 기반하여 이동합니다.

-3. Adaptive control

현재 교통 신호제어에 많이 사용하며, 스마트 신호하면 사용하는 많은 방식입니다. 현재 상황을 센서로 인지하여 최고의 신호 제어를 사용합니다.

-4. Optimization-based control

사람의 지식에 적게 의존하는 대신(교통공학적 지식) 관찰 데이터를 기반으로 신호계획을 결정합니다. (물론 pre-defined rule이 필요하고, dynamic traffic에 대해서는 적응하기 어렵다고 합니다. 평시의 데이터에 최대한 최적화가 되기 때문이라고 하네요!)

 

그래서 이 논문에서는 다음과 같이 우리가 해결해야할 문제가 있다고 제시하고 있습니다.

-1. traffic 신호는 highly correlated되어 있으므로, 각 신호 제어에서 유연성을 가져야하며, 신호군(신호등 구역)에 대해서 협력적으로 제어해야 한다고 합니다.

-2. 출퇴근 시간대를 제외하고서라도 dynamic traffic에 대응할 수 있도록 설계되어야 한다고 합니다.

 

이러한 문제를 3가지 키워드를 중점으로 제시하며, 저 또한 이 글에서 최대한 이 3가지 키워드 중심으로 설명하고자 합니다.

-1. Scalability

 Large scale traffic signal에 대해서 학습할 수 있어야하고 동시에 global optimization goal을 달성할 수 있어야합니다.

-2. Coordination

근접한 신호들에 대해서는 traffic light들 끼리 서로 optimization이 되어 signal timing이 correlated되게 제어할 수 있어야 합니다.

-3. Data feasibility

강화학습으로 데이터를 학습시키는 데에 있어서 말도안되는 상황을 가정하고 학습시키지 말아야 합니다.

 

Related Work

- 기존의 method for multi-intersection control 1

다른 신호에 대해서 거리가 짧다면 동일 cycle length를 사용하여 correlation을 무시한 multi-intersection control이 있어서 다음 그림과 같은 상황에 대처하기 어려웠습니다.

또한, 거리가 멀면 selected movement에 대해서 offset을 조정하여 맞추었습니다. (위 그림과 같은 상황을 맞추었습니다.)

이러한 방법들의 문제점은 few network(적은 교차로)끼리만 correlation이 좋고, dynamic traffic에 대해서 global optimization이 되기 어렵다는 것입니다.

 

- 기존의 method for multi-intersection control 2

과거에 Global optimization을 진행하여 coordination을 달성하기 위한 시도로, max pressure 기법을 적용하였습니다. pressure# of inflow vehicles - # of outflow vehicles라고 할 때, max pressure를 골라 phase를 선정해주는 control방식입니다. Max pressure를 통해 intersection 모두에서 vehicle travel time throughput global하게 optimization을 진행할 수 있었습니다. 하지만, simple traffic condition에만 의존하였고, 실제에 적용하지는 못했습니다.

최근에 들어서야 사람들이 신호 제어에 RL을 사용하기 시작했고, 기존의 전통적인 방법보다 나은 성능을 발휘하는 것을 확인하였습니다. RL의 가장 큰 장점은 이전의 행동에 대한 환경의 피드백을 관찰함으로서 다음 행동을 하기 때문에 dynamic하게 반응할 수 있다는 장점이 있습니다. 과거에 Single-intersection에서 RL을 적용한 것을 확인해보니 전통적인 transportation method보다 더 나은 성능을 보이는 것을 확인하였고, 여기서 scalability를 만족시키기 위해 multi-intersection에 적용하려고 이 논문을 작성하게 되었다고 합니다.

MaxPressure (Varaiya 2013; Kouvelas et al. 2014)

- multi-intersection control method로서의 강화학습

Multi intersection에 적용하기 위한 시도가 2가지가 있었는데. 1개의 traffic 신호를 1개의 agent라고 할 때, 단순히 agent의 수만 늘려서 single agent rl알고리즘을 사용할 수 있었습니다. Scaling은 간단하고 쉽지만 서로 coordination이 안된다는 단점이 있습니다.

Intellilight, Wei H, et al. 2018., (이미지 출처: https://docs.ray.io/en/master/index.html)

다른 방법으로는 Multi agent를 사용하여 적용하는 방법이 있을 수 있습니다. 이를 통해서 intersection 끼리 coordinate 될 수 있다는 장점이 있으나 scale이 커지면 action space의 차원이 커져서 curse of dimensionality에 빠질 가능성이 존재합니다.

Colight, Wei H, et al. 2019b.

이러한 점들 때문에 RLlarge network에 적용하기 어려웠습니다. RL을 적용하기 위한 방법으로 Decentralized Approach를 실행해왔습니다. Scalabilitycoordination을 동시에 고려한다는 점에서 각광받았습니다. 하지만, 이전의 연구들에서는 기존에 transportation system에서 사용하던 최적화 방식을 그대로 사용하여 각각의 traffic light에 대해서 관찰 할 때, individual reward를 증가시키는 reward function이 아니었습니다. 또한, 협업의 결과로 나오는 global reward function design도 아니었습니다.

 

Proposed Method

이러한 문제들을 해결하는 방안으로 언급했던 Scalability, Coordination, Data feasibility를 극복하기 위한 실험을 진행하였습니다. Synthetic data real-data를 이용하여 infeasibility를 극복하고자 하였습니다. 또한, Decentralized agents의 특징인 parameter를 공유하고, action을 분리하여 scalable하게 만들려고 하였습니다. 기존 연구에서 사용하던 FRAP 모델을 사용하여 학습 속도를 올리고, exploration space를 줄이고자 구성하였습니다. Max Pressure 개념을 reward에 도입하여 해당 global throughput을 최대화 시키고 pressure를 줄여 차량의 분포를 균일하게 만드는 것을 목표로 하였습니다

- FRAP architecture(base model, 제가 제 발표자료에서 사용한 내용을 복사하여 가져왔습니다.)

사실 이 부분은 다른 논문에서 제시된 방법의 전체를 다룹니다. 나중에 분리될 수도 있음을 알려드립니다.

Learning Phase Competition for Traffic Signal Control, Guanjie Zheng, et al. (CIKM 2019)

 

1. Flipping and Rotation and considers All phase Configuration

2. Focus on the relation between different traffic movement

   1) Reduction of exploration space by rotating and flipping

   2) Current model need 8phases experience to learn in the same state
       - By rotating and flipping, Reduces needed experience in 1/8 scale

3. Adapting different intersection structure easily by two principles

   1) Principles of competition: Larger traffic indicates higher demand for ‘green’

   2) Principles of invariance: signal control should be invariant to symmetries such as rotating and flipping

4. Prediction of phase score into tree stages(for i traffic movement)

   1) Phase demand modeling: features from both current phase and # of vehicles through 2 fc-layers

   2) Phase pair representation: the score of a phase depends on its competition with the other phase

   3) Phase pair competition: predicted score of a phase p over all its opponents

Learning Phase Competition for Traffic Signal Control, Guanjie Zheng, et al. (CIKM 2019)

개념은 위와 같고, 딥러닝 모델로 구현한 것은 아래와 같습니다.

Learning Phase Competition for Traffic Signal Control, Guanjie Zheng, et al. (CIKM 2019)

각 도로에서 inflow하는 차량들의 수를 # of vehicles로 하고, heading방향(다가오는 intersection에서 이동할 방향)을 추론하여 input으로 저장합니다. 각 phase demand는 두가지의 movement demand로 구성됩니다. (저희가 도로에서 직진하면 마주오는 차량이 직진할 수 있는, 즉 동시에 켜져도 충돌하지 않는 조합이 phase입니다. 각 구성요소가 traffic movement 입니다) 이를 이용하여 competing phase demand들 끼리의 점수를 낼 수 있도록 embedding을 합니다. 이를 통해서 convolution neural network를 통과하여 phase competition representation을 결정합니다. 그리고 난 pairwise(동일 phase demand)에 대해서 묶어서(1행 끼리 묶음) phase score를 결정하여 딥러닝 모델의 output, 즉 심층강화학습의 input(state)로서 사용하게 됩니다. 이렇게 되면 각 phase에 대해서 rotate, flip한 demand를 가져올 수 있게 됩니다.

 

강화학습 모델로는 Deep Q Network를 사용하였고 가장 간단하게 사용하였습니다. DQN은 value-based learning(Q-learning)을 사용하여 최적의 action을 찾아가며 epsilon-greedy하게 exploration과 exploitation을 진행합니다. Loss function의 경우 target network의 approximated Q를 통해 최적화를 진행합니다. Experience replay를 사용하여 highly-correlated되어 있다고 평가받는 on-policy method보다 과거의 데이터 학습이 현재에 도움이 되게 한다고 합니다.

 

Toward a thousand lights:Decentralized deep reinforcement learning for large-scale traffic signal control

본 논문에서 얘기하는 decentralized framework입니다. Agents로 표시되어 헷갈릴 수 있는데 inference는 decentralized agent가 진행하며, agent라고 표시한 부분은 신호등들을 의미합니다.

MDP는 다음과 같이 사용합니다.

Observation

- Current phase

- Pressure of the 12 traffic movements 

Action

- 8 candidate phases(가능한 신호에서) action으로서 phase를 선택함

- Max Pressure Control Law를 기반으로 선택

Reward

- Max Pressure기반이므로, inflow vehicles와 outflow vehicles의 queue length difference를 reward로 갖는다

 $r_i=-P_i$,  $P_i$ is the pressure of intersection $i$

Decentralized Agent에 대한 Parameter Sharing

- Decentralized RL에 대해서는 많은 방식이 존재합니다. (ex: Reward공유, State를 agent별로 공유, Parameter 공유 등등) 본 논문에서는 parameter sharing을 통해서 decentralized를 달성하는 방식을 사용하였습니다.

- 본 방식을 통해 다른 교차로 신호로부터 경험을 가져와서 학습에 사용할 수 있다는 장점이 있습니다.

 

Experiment Setting

- Synthetic data on a 4x4 Network

실험에서는 4x4와 실제 network를 사용하였으며, synthetic data에서는 phase가 실행되고 all yellow signal 3초와 all red 2초를 연속적으로 무조건 동작하게 사용하였습니다. Bi-directional and dynamic flows를 사용하여 차량의 흐름을 지정하였고, Peak는 rho를 0.3 flat은 rho를 0.6으로 사용하여 교통량을 부여하였습니다. 각 vehicle은 taxi 데이터로부터 turning ratio를 사용하여 60% straight 30% right 10% left를 각 교차로에서 하도록 부여하였습니다. 총 2가지의 pattern과 arrival rate로 4가지 실험을 진행하였습니다.

- Real-world data

Manhattan의 taxi data volumn을 배수로 취하여 사용하였고, 총 2510개(!!)의 많은 신호를 동시에 제어하였습니다.

Result

다른 방법기반 신호들(강화학습 포함)에 대해서 20% 정도 높은 성능을 보였습니다. (Travel Time) 이전 연구였던 FRAP모델에 대해서도 높은 성능향상을 나타냄으로서 Decentralized method가 효과가 있음을 확인할 수 있었습니다.

New York도로 구조에 대해서는 다음과 같이 진행하였고, 현재 사용중인 fixed time control보다 두배 높은 travel time 감소와 3배 높은 throughput을 나타내었습니다. 신기한 점은 컴퓨터로 5x5 network를 학습하더라도 1일넘게 걸리는데 2510개는 얼마나 걸렸을지 궁금한 부분이 있었습니다. 아래 실험을 통해서 동시에 large-scale을 학습한 결과로 scalability를 만족함을 알 수 있었습니다.

아래 실험은 Decentralized Method에서 parameter sharing이 학습의 완성에 얼마나 영향력이 있는지 확인할 수 있는 결과입니다. Converge속도가 parameter sharing이 없는 것 보다 빠른 것을 확인할 수 있었습니다.

Conclusion

여전히 2510개의 신호를 동시에 제어하는 것을 통해서 한것이 어렵다는 생각은 들지만 Decentralized method가 scalability에서 강력한 모습을 보여줄 수 있음을 확인한 논문이었습니다. 

 

자세한 내용은 full paper를 참고하거나 댓글로 남겨주세요.

댓글