Optymalizacja sygnałów ruchu: adaptacyjne sterowanie

Zawsze ustalony czas versus uczenie się z kolejki

Konwencjonalny semafor działa na cyklu o ustalonej długości: 30 sekund zielonego światła północ-south południe, a następnie całe czerwone światło do czystki, potem 30 sekund zielonego światła wschód-west, powtarzać wiecznie, niezależnie od tego, czy na żadnym z tych kierunków jest choć jedno samochod. Jest proste i przewidywalne, ale zuważy ogromne ilości czasu zielonego na pustych kierunkach o godzinie 2 a.m., a jednocześnie starzeje się intensywnie używany kierunek podczas szczytu ruchu. Tym symulacją treningiem jest agent uczenia Q w czasie rzeczywistym, bezpośrednio w Twojej przeglądarce, do kontroli tej samej przecznicy poprzez czytanie długości kolejek i wybieranie kierunku otrzymującego zielone światło — a następnie konkuruje go z bazowym cyklem o ustalonej długości, aby pokazać różnicę, nie tylko podać ją.

Rozważanie przekroju jako proces decyzyjny Markowa

Nauczanie poprzez zwielokrotnianie wymaga stanu, zbioru działań i nagrody. Tutaj stan to dyskretna opis przekroju — zazwyczaj długość kolejki na każdym podejściu, podzielona na kilka poziomów, oraz który teren jest obecnie zielony i jak długo był zielony. Działanie jest małe: utrzymać bieżący teren lub przejść do następnego. Nagroda przekazana po każdej akcji jest ujemna, proporcjonalna do czegoś, co miasto rzeczywiście dba — całkowitą liczbę pojazdów czekających, lub łączną czas oczekiwania — dlatego agent jasno próbuje minimalizować łączny opóźnienie, a nie maksymalizować przepustowości jako abstrakcyjnej liczby.

state  = (queue_N, queue_S, queue_E, queue_W, current_phase, phase_duration)
action = { keep_phase, switch_phase }
reward = - (total vehicles waiting this step)

Q-learning: zasada aktualizacji

Q-learning utrzymuje tabelę Q(s, a), która szacuje długoterminowy przypadek discountowany powrotu wynikający z podjęcia działania a w stanie s i następnie działania optymalnie do końca. Na każdym kroku obserwuje przejście (s, a, r, s') i poprawia tabelę na podstawie obserwowanych dowodów:

Q(s, a) Term w nawiasach to błąd różnicowy czasu: różnica między tym, co agent oczekiwał (starej wartości Q), a tym, co teraz uważa za bliższe prawdy (wygrana niedawno odebrane plus najlepsza szacunkowa ocena wszystkiego co nastąpi potem). Powtarzane tysiące cykli przecięć, tabela zbiega się ku rzeczywistej funkcji optymalnej wartości działania bez kiedykolwiek otrzymywania informacji na temat podstawowych dynamicznych kolejek — uczy się jedynie na podstawie prób, błędu i sygnału nagrody.

Q(s, a) <- Q(s, a) + alpha * [ r + gamma * max_a' Q(s', a') - Q(s, a) ]

alpha = learning rate   (how much to trust the newest sample)
gamma = discount factor  (how much future reward matters vs. immediate)

Eksploracja wobec wykorzystania

Agencja, która zawsze wybiera działanie o najwyższej obecnej wartości Q, może się zatrzymać i wykorzystywać słabo skuteczną politykę, którą odnalazła wczesno, nigdy nie odkrywając lepszej. Epsilon-greedy eksploracja naprawia to prosto: z prawdopodobieństwem epsilon agencja wybiera losowe działanie zamiast greedy, a epsilon maleje podczas treningu, aby agencja intensywnie eksplorowała wczesno (kiedy tabela Q nadal jest niezawodna) i wykorzystywała pewnie późno (po tym, jak tabela się zbiegła). Ta harmonograma maleńkości jest jedynym najwyraźniej widocznym przyciskiem w szybkości, z jaką krzywa treningu w demo wzrasta — za mało eksploracji i agencja wcześnie zobowiązuje się do słabej polityki; za dużo i straci czasy, nie osiągając konsystencji.

action = random(actions)         with probability epsilon(t)
       = argmax_a Q(state, a)     with probability 1 - epsilon(t)
epsilon(t) decays from ~1.0 toward ~0.05 over training

Dlaczego ustalony czas straci

Ustalony czas jest optymalny tylko dla exact traffic pattern, dla którego został dostosowany, a rzeczywisty ruch nie jest taki pattern — fluctuuje w zależności od godziny dnia, dnia tygodnia i niewy:animated events. Stan wielkości kolejki agenta Q-uczenia mu daje coś, czego ustalony czas strukturalnie nie może mieć: widzi teraz ile rzeczywistego ruchu jest warte na każdym podejściu, a może utrzymać zielonego kilka dodatkowych sekund dla podburzonego podejścia lub skrócić zielony dla pustego. W praktyce, przy dowolnej rzeczywistej różnorodności stopni przybywań, ten reaktowny zalety kompensują się w materialnie niższym średnim czasie oczekiwania — co dokładnie jest przepaścią, której dwie krzywe uczenia się na bieżąco w demo pokazują, a nie stwierdzają.

Zmiany są rzeczywiste, a nie szczegóły implementacji do zignorowania. Tabela stanu-działania skaluje się źle — każda dodatkowa ścieżka lub każdy finansowy bufor kolejki mnoży rozmiar tabeli — co jest powodem dla którego coraz więcej wdrożeń miast używają aproksymacji funkcji zamiast prostej tablicy po przekroczeniu kilku przecięć rozmiaru przestrzeni stanu. A agent Q-uczenia treningu na jednym układzie ruchu nie automatycznie generalizuje się do innej geometrii lub wzoru przybywań innego układu; musi być ponownie treningowany, a co najmniej dostosowany.

Często zadawane pytania

Wypróbuj na żywo

Wszystko powyżej działa bezpośrednio w Twojej przeglądarce — otwórz Traffic Signal Optimization: Adaptive Control i zmieniaj parametry podczas działania. Nic nie jest instalowane ani przesyłane na serwer, cały model działa w jednej karcie.