[PYTHON] Möglichkeit der Anwendung auf die Evakuierungsroutengestaltung des Labyrinthproblems beim Lernen der Verstärkung

Vorwort

Während der Frühlingsferien habe ich durch erweitertes Lernen über Sicherheitstechnik geforscht, aber es scheint, dass es nicht möglich sein wird, es in eine konkrete Form zu sublimieren, deshalb werde ich hier den Teil bis zu diesem Zeitpunkt zusammen mit dem Hintergrund zeigen.

Intensivierter Lern- und Forschungshintergrund

Labyrinthproblem

Das Labyrinthproblem ist ein Beispiel für ein Problem, das häufig beim intensiven Lernen behandelt wird. Als Beispiel für die Implementierung habe ich auf [hier] verwiesen (https://qiita.com/kyogoku_meta/items/a7bb70a787baa9b4c39e).

Erläuterung: Der Zweck besteht darin, die Route von S (Start) nach G (Ziel) im Labyrinth zu lernen, wie in der Abbildung gezeigt. Dieses Mal werden wir die ε-gierige Methode beim Q-Lernen verwenden.

Beim Q-Learning werden die Bewegungsoptionen (Maßnahmen) definiert, die für jedes Quadrat ergriffen werden können, und der Aktionswert wird für jede Maßnahme bestimmt. Wenn eine Kennzahl in einem bestimmten Quadrat erstellt wird, wird die Differenz vom Maximalwert des Aktionswerts des Ziels um einen bestimmten Prozentsatz erhöht und der Aktionswert der Kennzahl in diesem Quadrat aktualisiert. Eine andere Sache ist, dass das Ziel einen bestimmten Aktionswert hat und die Richtlinie, um zum Ziel zu gelangen, darin besteht, den Aktionswert mit der Belohnung zu aktualisieren und einen Satz zu beenden, um das Labyrinth zu lösen.

Die Grundform der Aktualisierungsformel für den Aktionswert Q lautet wie folgt. $Q(s,a)\leftarrow Q(s,a) + \alpha[r+\gamma*max_{a'}Q(s',a')-Q(s,a)]$

$ Q $: Aktionswert $ s $: Status (Agentenposition, Quadrat) $ a $: Aktion $ \ Alpha $: Lernrate $ \ Gamma $: Zeitabzinsungssatz $ r $: Belohnung Ist gegeben als. $ s ', a' $ repräsentieren den Status einen Schritt voraus (dh den Aktionswert des bestimmten Aktionsziels).

Wie Sie der obigen Formel entnehmen können, verwendet die Aktualisierung beim Q-Lernen die Differenz vom Aktionswert Q des nächsten Quadrats als treibende Kraft für die Aktualisierung. Wenn also der Wert von Q in jedem zuerst angegebenen Quadrat einheitlich ist. Wenn es 0 ist, bewegt sich der Agent von Anfang an zufällig um jedes Feld, und der Aktionswert dieses Feldes wird nur aktualisiert, wenn eine Strategie zum zufälligen Erreichen des Ziels erworben wurde. Dies ist tatsächlich der Fall, und zuerst führen wir eine zufällige Suche durch und erhalten eine Belohnung. Allmählich breitet sich der Aktionswert vom Ziel und den umliegenden Feldern zum Start aus.

Andererseits hat die obige Formel den Nachteil, dass der Aktionswert, sobald er von Start bis Ziel bestimmt wurde, definitiv nur diese Route durchläuft (da die anderen Quadrate 0 sind, ist die Richtlinie zum Verschieben nicht ausgewählt). Daher wird ein Berechnungsverfahren angewendet, bei dem der Wert von & egr; allmählich verringert wird, indem bei der Entscheidung über eine Richtlinie zufällig Maßnahmen mit einer bestimmten Wahrscheinlichkeit & egr; ergriffen werden. Dies ist eine kurze Erklärung der ε-gierigen Methode.

Forschungshintergrund

In der Sicherheitstechnik ist die Brandkatastrophe eines der wichtigsten Forschungsthemen. Verschiedene Experimente zur Evakuierung im Brandfall wurden aus Experimenten und Berechnungen in früheren Studien erstellt. Ein Beispiel ist die Simulation des Brandevakuierungsverhaltens mithilfe eines Labyrinths. In der Berechnung

• Ein Modell, das menschliches Verhalten als Teilchenbewegung interpretiert und die Bewegungsgleichung löst
• Modell der Zellautomatisierung

Usw. werden häufig diskutiert, aber in beiden Fällen werden bei der Berechnung Informationen über die Umwelt und wichtige Regeln der Umweltabhängigkeit verwendet. Infolgedessen wurden viele Studien zusammen mit der Überprüfung der tatsächlichen Brandfälle diskutiert, was Fragen zur Vorhersage des Evakuierungsverhaltens aufwirft.

Daher denken wir hier an eine Studie, die auf der Idee basiert, das Labyrinthproblem durch Q-Lernen anzuwenden, um den optimalen Weg vom Auftreten eines Feuers bis zur Evakuierung zu berechnen und quantitativ zu betrachten. Einer der Vorteile dieser Methode besteht darin, dass die voreingestellten Parameter weniger von der Umgebung abhängig sind. Darüber hinaus wird eine große Erweiterbarkeit erwartet, ohne die Regeleinstellung des Algorithmus in Abhängigkeit von der Einstellung der Belohnungen und Maßnahmen zu erhöhen.

Labyrinthproblem durch Q-Lernen

Der Code kann schnell eingefügt werden.

import numpy as np
import matplotlib.pyplot as plt


#decide the direction to move by Q table and random probability epsilon
#and convert it as movement on the map.
def decide_action(status, maze_row, q_table, maze_map, epsilon):
    
    direction=["up", "right", "down", "left"]
    if(np.random.rand() < epsilon):
        #at random choice
        direction_to=np.random.choice(direction, p=maze_map[status])
    else:
        #direction is selected at max Q value direction
        direction_to=direction[np.nanargmax(q_table[status])]
        
        
    #convert direction to map information at matrix
    if(direction_to=="up"):
        status=status-maze_row
        action=0
    elif(direction_to=="right"):
        status=status+1
        action=1
    elif(direction_to=="down"):
        status=status+maze_row
        action=2
    elif(direction_to=="left"):
        status=status-1
        action=3
        
    return status, action


#q_learning function to update the Q_value
def q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward):
    
    #setting of reward
    if(next_status==goal):
        r=reward
    else:
        r=0
        
    #update fomula of Q_value
    q_table[status][action]+=alfa*(r+gamma*(np.nanmax(q_table[next_status])-q_table[status][action]))
    
    return q_table


#solve and update the maze at once
def goal_once(start, goal, maze_row, maze_map, q_table, alfa, gamma, reward, epsilon):
    
    flag=True
    history_move=[]
    
    #initialize
    status=start
    
    #solve maze until it gets the goal
    while(flag):
        
        next_status, action=decide_action(status, maze_row, q_table, maze_map, epsilon)
        q_table=q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward)
        
        #record the history of action
        history_move.append([status, action])
        
        #flag of goal
        if(next_status==goal):flag=False
        
        #status update
        status=next_status
    
    return q_table, history_move



move_0=np.array([0, 0, 0, 0])
move_w=np.array([1, 0, 0, 0])
move_d=np.array([0, 1, 0, 0])
move_s=np.array([0, 0, 1, 0])
move_a=np.array([1, 0, 0, 1])
move_wd=np.array([1, 1, 0, 0])/2
move_ws=np.array([1, 0, 1, 0])/2
move_wa=np.array([1, 0, 0, 1])/2
move_ds=np.array([0, 1, 1, 0])/2
move_da=np.array([0, 1, 0, 1])/2
move_sa=np.array([0, 0, 1, 1])/2
move_wds=np.array([1, 1, 1, 0])/3
move_wda=np.array([1, 1, 0, 1])/3
move_wsa=np.array([1, 0, 1, 1])/3
move_dsa=np.array([0, 1, 1, 1])/3
move_wdsa=np.array([1, 1, 1, 1])/4


###input form###

maze_map=np.array([move_ds, move_dsa, move_dsa, move_dsa, move_sa, \
                   move_wds, move_wdsa, move_wdsa, move_wdsa, move_wsa,\
                   move_wds, move_wdsa, move_wdsa, move_wdsa, move_wsa,\
                   move_wd, move_wda, move_wda, move_wda, move_wa])

q_table=np.where(maze_map==0.0, np.nan, 0)

maze_row=5
maze_columns=4

start=0
goal=19
reward=1
time_of_episode=100
alfa = 0.10  #Lernrate
gamma = 0.92 #Zeitabzinsungssatz
epsilon = 0.99  # ε-Anfangswert der gierigen Methode
probability_reduce_rate=1.04

###input form end###



history_move=[]
size_of_epi=[]
episode = 1



flag=True
while(flag):
    q_table, history_move=goal_once(start, goal, maze_row, maze_map, q_table, alfa, gamma, reward, epsilon)
    print("this is episode: {0:5d}, steps to goal are {1:5d}".format(episode, len(history_move)))
    size_of_epi.append(len(history_move))
    if(time_of_episode==episode):
        flag=False
        episode=episode-1
    episode+=1
    epsilon=epsilon/probability_reduce_rate
    q_table=q_table/np.nanmax(q_table)
    
direcion=["↑", "→", "↓", "←"]
for i in range(len(history_move)):
    print(direcion[history_move[i][1]])
    
plt.plot(size_of_epi)
plt.show()



q_table[goal]=1.0

np.set_printoptions(suppress=True, precision=4, floatmode='maxprec')
#print(maze_map)
print(q_table)


q_table_max=np.zeros(goal+1)
for i in range(len(q_table)):
    q_table_max[i]=np.nanmax(q_table[i])
        
print(q_table_max.reshape(maze_columns, maze_row))

q_table_max=q_table_max.reshape(maze_columns, maze_row)

plt.figure(figsize=(10, 5))
plt.imshow(q_table_max, interpolation='nearest', vmin=0 ,cmap='YlOrRd')
plt.colorbar()
plt.show()

Die Berechnungsergebnisse sind unten gezeigt, und es ist ersichtlich, dass der Aktionswert in dem Labyrinth, das von links oben nach rechts unten endet, sehr deutlich übertragen wird und der Weg zum Ziel festgelegt wird.

Simuliertes Feuer

Erweitern wir dies, um das Lernen des Evakuierungsverhaltens im Brandfall zu simulieren. Hier setzt das Modell nur eine Belohnung für das Ziel, aber als einfache Erweiterung bereiten wir eine Masse vor, die wie ein Feuer aussieht, und geben eine negative Belohnung, wenn wir dort ankommen. Wenn Sie ein Feld mit einer negativen Belohnung erreichen, beendet das Spiel einen Satz. Mit anderen Worten, der Agent startet ohne Wissen von Anfang an und strebt das Ziel an, während er viele Male in den Tod zurückkehrt.

Ergebnis

Das Obige ist das Berechnungsergebnis, aber es wurden ziemlich interessante Ergebnisse erhalten. Schauen wir uns noch einmal die Q-Learning-Update-Formel an.

Der Aktionswert jeder Kennzahl wird basierend auf der obigen Formel aktualisiert. In der obigen Formel spiegeln alle Aktualisierungen den Maximalwert des Aktionsziels wider. Selbst wenn eine negative Belohnung vergeben wird, wird die Umgebung berücksichtigt Mit Ausnahme von 1 Zelle wird diese von der Max-Funktion ignoriert. Die Aktualisierungsformel über Q-Learning ist eine optimistische Verhaltenswertformel. Einfach ausgedrückt, sie nimmt den besten Weg, selbst wenn eine große negative Belohnung daneben steht. Selbst wenn die Flamme daneben brennt, besteht das Problem, dass der kürzeste Weg berechnet wird, um dorthin zu gelangen.

Pessimistisches Update

Betrachten Sie nun einen leicht pessimistischen Agenten. Bei einem Parameter namens Pessimismus,

Ändern Sie die obige Gleichung wie folgt. Mit anderen Worten, es wird so modifiziert, dass der Mindestwert des Aktionswerts des Aktionsziels auf eine bestimmte Rate geschätzt wird. Wenn Pessimismus = 0 ist, entspricht dies der ursprünglichen Aktualisierungsformel, und wenn Pessimismus → ∞ ist, handelt es sich um ein Programm, das nur den niedrigsten Wert des Aktionswerts jedes Quadrats auswertet und lernt. Speziell,

q_learning

#q_learning function to update the Q_value
def q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward, pesimism):
    
    r=0
    
    #setting of reward
    for i in range(len(goal)):
        if(next_status==goal[i]):
            r=reward[i]
        
    #update fomula of Q_value
    q_table[status][action]+=alfa*(r+gamma*(np.nanmax(q_table[next_status])-q_table[status][action]))
    
    
    return q_table

Die Funktion des entsprechenden Teils

q_learning

#q_learning function to update the Q_value
def q_learning(status, action, next_status, goal, q_table, alfa, gamma, reward, pesimism):
    
    r=0
    
    #setting of reward
    for i in range(len(goal)):
        if(next_status==goal[i]):
            r=reward[i]
        
    #update fomula of Q_value
    q_table[status][action]+=alfa*(r+gamma*(np.nanmax(q_table[next_status])/(1+pesimism)\
           +np.nanmin(q_table[next_status])*pesimism/(1+pesimism)-q_table[status][action]))
    
    
    return q_table

Umschreiben als. Wenn ich versuche damit zu rechnen.

Es ist ersichtlich, dass die Route so gewählt ist, dass der Ort des Feuers richtig vermieden wird.

Aktionswertkarte (Potenzial) eines mittelgroßen Labyrinths

Basierend auf den obigen Befunden wird mit weiter vergrößertem Maßstab des Labyrinths die Route von jedem Quadrat des Labyrinths zum Ziel gelernt, und der daraus erhaltene Aktionswert wird gemittelt, um vom gesamten Labyrinth zum Ziel zu erwärmen. Ich habe eine Karte gemacht. Obwohl die Wärmekarte selbst keine wesentliche Bedeutung hat, wird sie als nützlich angesehen, um klar darzustellen, wie viel Risiko im Brandfall auftritt und welche Art von Änderung bei der Routenauswahl auftritt.

Das Ziel ist die Mitte des oberen Teils.

Kein Feuer:

Da ist ein Feuer:

Es ist zu erkennen, dass bei einem Brand auf der rechten Seite des Bodens der Aktionswert des Raums auf der rechten Seite erheblich sinkt. Andererseits ist zu sehen, dass der Durchgang auf der linken Seite der beiden Routen in der unteren Mitte höher bewertet und bevorzugt wird. Selbst wenn das Feuer als eine einzige negative Belohnungsmasse angesehen wurde, waren die Ergebnisse ziemlich interessant.

Problem

Obwohl es zu Beginn als eigenständige Forschung deklariert wurde, gibt es die folgenden Probleme, dass dies noch keine konkrete Form geworden ist.

Multi-Agent

Es ist notwendig, Multi-Agent-Aufgaben zu lösen, ganz zu schweigen vom Personenfluss im Brandfall. Auch als Merkmal des tatsächlichen Evakuierungsverhaltens

1. Evakuierte folgen Führungskräften (sachkundiges Personal). (Dies kann als gemeinsame Nutzung der Aktionswertfunktion angesehen werden.)
2. Informationstafeln und Evakuierungsanweisungen haben einen bestimmten Effekt. (Es ist notwendig, Belohnungen und Maße für bestimmte Quadrate festzulegen.)
3. In der Nähe des Ausgangs tritt eine Überlastung auf, und die Mobilität der Menschen nimmt ab. (Natürlich wird sich die Flucht verzögern, daher muss die Belohnung für diejenigen, die später fliehen, schrittweise reduziert werden.)

Es ist notwendig, unter Berücksichtigung der Merkmale eines solchen tatsächlichen Evakuierungsverhaltens zu untersuchen. Im Vergleich dazu endet dieses Programm mit einer Verbesserung des Q-Lernens.

Einbau von Brandmerkmalen

Beim Evakuierungsverhalten während eines Brandes ändert sich das Feuer selbst im Laufe der Zeit erheblich. Der größte Faktor für das Evakuierungsverhalten ist Rauch. Die seitliche Bewegungsgeschwindigkeit von Rauch soll ungefähr der Gehgeschwindigkeit des Menschen entsprechen, es ist jedoch notwendig, die Eigenschaften von Diffusion, Bewegungsgeschwindigkeit und Richtung weiter zu untersuchen. Es wird als effektiver Algorithmus angesehen, den negativen Belohnungsbereich mit der Zeit für jede Runde zu entwickeln, aber im tatsächlichen Experiment zum Evakuierungsverhalten des Feuers behindert der Rauch des Feuers die menschliche Sicht, verlangsamt die Gehgeschwindigkeit usw. Es wurde darauf hingewiesen, und es ist unklar, ob der Effekt nur durch negative Belohnungen ausgedrückt werden kann.

Das Dilemma des menschlichen Evakuierungsverhaltens

Wie bereits erwähnt, umfasst das Evakuierungsverhalten des Menschen charakteristisches Verhalten, das aus Experimenten beobachtet wurde. Es ist auch bekannt, mit einflussreichen Führungskräften und dem Verhalten der Menge Schritt zu halten, um vorerst mit den Menschen Schritt zu halten. Ein solches Verhalten kann auftreten, selbst wenn der Ausgang eng ist und es effizienter ist, zu einem anderen Ausgang zu gelangen. Das Problem ist, dass der optimale Weg, der durch verstärkendes Lernen gelernt wird, nicht immer optimal ist, wenn man die Irrationalität und den Instinkt des Menschen berücksichtigt. Während manche Menschen in Panik geraten, ist die größte Frage, wie viel irrationales Verhalten als Belohnung verwendet werden kann, um festzustellen, ob es für menschliches Verhalten optimal ist.

Ausblick

Schließlich halte ich es für interessant, wenn die Berechnung auf der Serverseite mit hoher Geschwindigkeit verarbeitet und jedem Evakuierten der optimale Evakuierungsweg präsentiert werden könnte. Im Vergleich zur bestehenden Zellautomatenmethode gibt es nur wenige umgebungsabhängige Algorithmen, die für die Erweiterbarkeit hier effektiv zu sein scheinen. Wurde es bereits in Gebieten in der Umgebung wie dem städtischen Verkehr und dem Bahnhofstransfer in die Praxis umgesetzt?

Ich würde mich freuen, wenn Sie mich wissen lassen könnten, ob Sie nützliche Literatur haben.

Fazit

• Da es viele Referenzen gibt, werde ich sie weglassen. Bitte lassen Sie mich wissen, wenn Sie an den Referenzen interessiert sind