Résolvez votre propre labyrinthe avec DQN

J'ai essayé de résoudre mon propre labyrinthe avec Deep Q Network (soi-disant DQN).

Le programme est ici. https://github.com/shibuiwilliam/maze_solver

Aperçu

Le DQN est un type d'apprentissage par renforcement qui utilise un réseau de neurones pour sélectionner la stratégie optimale. Ce qui suit est une référence pour l'explication de l'apprentissage par renforcement et du réseau neuronal.

Renforcer l'apprentissage Renforcer l'apprentissage de zéro à profond - Qiita
réseau neuronal Découvrez les principes de l'intelligence artificielle grâce au didacticiel TensorFlow-Qiita

L'apprentissage par renforcement est une technologie utilisée dans les jeux et le contrôle des robots, mais lorsqu'un joueur (également un agent) entreprend une action contre une situation (État), la situation change et la récompense pour cette action (récompense). ) Est un modèle à obtenir. Répéter les actions pour les situations Les joueurs visent à maximiser les récompenses.

Cette fois, je vais utiliser mon propre labyrinthe pour la situation. Le labyrinthe est automatiquement généré par le programme, mais il ressemble à ceci.

À 10x10, S est le point de départ et 50 est le but. Il est entouré d'un mur (#), et seules les tuiles (-1, 0) avec des numéros internes peuvent passer. Même à l'intérieur du mur, les carreaux marqués d'un # ne peuvent pas passer. Les chiffres sur les tuiles sont des points (récompenses en termes d'apprentissage amélioré). -1 est 1 point moins, 0 point est inchangé et l'objectif est de 50 points. Les joueurs visent à maximiser les points et à atteindre l'objectif.

Cette fois, nous avons implémenté les trois logiques suivantes pour que le joueur atteigne l'objectif.

Algorithme A-star
Q-Learning
Deep Q-network（DQN）

Le contour de chacun est le suivant.

Algorithme A-star

L'explication ici de l'algorithme A-star est très facile à comprendre. Recherche dans le labyrinthe avec python <Explication de la réponse> - Légèrement mystérieux. A* - Wikipedia

Pour faire simple, la distance entre le point de départ et l'emplacement actuel et entre l'emplacement actuel et l'objectif est mesurée, et l'itinéraire avec la distance la plus courte est sélectionné. Dans le labyrinthe, chaque distance est calculée comme la distance euclidienne.

Distance ^ 2 = (objectif [x] - état [x]) ^ 2 + (objectif [y] - état [y]) ^ 2

C'est une équation qui apparaît dans le théorème de Pitagolas (théorème des trois carrés).

En utilisant l'algorithme A-star, la distance la plus courte est priorisée pour résoudre le labyrinthe. Il n'y a aucun concept de points ou de récompenses. Par conséquent, dans le labyrinthe de cette règle, la récompense a tendance à être faible tout en résolvant le labyrinthe rapidement.

Voici le chemin du début au but lorsque vous le résolvez avec A-star. La route que j'ai empruntée est bleue.

J'irai la distance la plus courte dans le labyrinthe que j'ai utilisé cette fois, mais la récompense est faible à 44 points. -1 ou autre, visez la distance la plus courte.

Q-learning Vient ensuite l'apprentissage Q. [Q learning-Wikipedia](https://ja.wikipedia.org/wiki/Q learning) Renforcer l'apprentissage à partir de Python --Qiita

L'apprentissage Q est une méthode à usage général qui peut être utilisée en plus de la recherche de labyrinthe. C'est une sorte d'apprentissage automatique, et un modèle est créé en utilisant la situation et son comportement comme données d'apprentissage et en utilisant la récompense comme variable cible. Créez un modèle prédictif des récompenses pour les actions entreprises en fonction de la situation. La prévision de récompense est calculée par la formule suivante.

$ Q (s, a) $ est la valeur attendue de la récompense pour l'exécution de l'action $ a $ dans la situation $ s $. $ α $ est le taux d'apprentissage et $ γ $ est le taux d'actualisation des récompenses. $ Q (s ', a') $ est la valeur attendue de la récompense pour l'exécution de l'action $ a '$ dans la situation suivante $ s' $ de la situation $ s $. Prenez la valeur maximale attendue de $ Q (s ', a') $ avec $ max $ et multipliez par le taux d'actualisation de $ γ $. $ r $ est la récompense pour avoir fait l'action $ a $ dans la situation $ s $.

La caractéristique de l'apprentissage Q est qu'en calculant à plusieurs reprises cette formule, la valeur de récompense estimée $ Q (s, a) $ et la valeur attendue $ r + γmaxQ (s ', a') $ sont rapprochées (par conséquent, $ Q). (s, a) ← Q (s, a) + 0 $ convergeront). Dans l'apprentissage Q, vous allez d'abord acquérir une combinaison d'état, d'action et de récompense en la répétant un nombre suffisamment grand de fois. Avec cela comme entrée, la formule ci-dessus est calculée à plusieurs reprises pour dériver la valeur attendue de la récompense $ Q (s, a) $ qui correspond à la situation réelle.

Q-learning vise à maximiser les récompenses. Dans ce labyrinthe, le but est la récompense maximale, donc si vous résolvez le labyrinthe avec Q learning, vous irez rapidement au but en évitant la tuile -1. Voici à quoi ça ressemble.

Traversez les 0 tuiles autant que possible et atteignez l'objectif dans la distance la plus courte. La récompense est 48,0, ce qui est supérieur à A-star.

DQN DQN est une combinaison d'apprentissage Q et d'apprentissage profond. Nous allons construire un réseau de neurones avec la situation $ s $ et l'action $ a $ comme variables d'entrée et $ r + γmaxQ (s ', a') $ qui apparaît dans l'apprentissage Q comme variables cibles. Action $ a qui maximise la récompense $ r $ pour l'état $ s $ en approximant $ r + γmaxQ (s ', a') $ à partir de $ s $, $ a $ et en minimisant l'erreur Ce sera celui qui dérivera $.

DQN diffère d'un réseau neuronal normal en ce que le programme génère des données d'enseignant pour un apprentissage supervisé. Les données de l'enseignant sont nécessaires pour apprendre le réseau neuronal, mais dans DQN, l'action $ a $ pour l'état $ s $ et sa récompense $ r $ sont accumulées en agissant réellement. Les variables d'entrée et les variables cibles enregistrent des combinaisons de $ s $, $ a $ et $ r $ en répétant des actions, et l'apprentissage est effectué en fonction de la mémoire accumulée au-dessus d'un certain niveau. Cela s'appelle Experience Replay, mais il apprend de la combinaison de $ s $, $ a $, $ r $ enregistré par lui-même, crée un modèle de prédiction et répète l'action à $ s $, $ a $, $ Le flux consiste à obtenir la combinaison de r $ et à modifier le modèle de prédiction. Il s'agit d'un article préconisant la relecture d'expérience. https://pdfs.semanticscholar.org/9cd8/193a66cf53143cbba6ccb0c7b9c2ebf2452b.pdf Cette explication est facile à comprendre en japonais. Histoire de DQN + Deep Q-Network écrite en Chainer --Qiita Je vais citer une partie:

input: Données $ D $ constituées de nombreux échantillons ($ s $, $ a $, $ r $, $ s '$) sortie: fonction Q après l'entraînement $ Q_ {\ theta_N} (s, a) $

k=0
Initialisez le paramètre de réseau neuronal $ \ theta_0 $
Répéter: Répéter N-1 $ fois
Extraire des échantillons $ M $ des données $ D $
Sur la base d'échantillons de M $ Signal de l'enseignant $ {\ rm {cible}} ^ t = r_t + \ gamma \ max_ {a '} Q_ {\ theta_k} (s_t', a ') $ Créer une entrée $ (s_t, a_t) $ ($ t = 1,2, ..., M $)
Basé sur le signal de l'enseignant créé $ {\ rm {target}} ^ t $ et saisissez $ (s_t, a_t) $ Minimisez l'erreur $ L_ \ theta $ entre $ Q_ \ theta (s, a) $ et le signal de l'enseignant par une méthode de gradient Faire. Lorsque l'apprentissage converge et que certaines conditions sont remplies, le résultat est $ \ theta_ {k + 1} $
$ k \ leftarrow k + 1 $
Renvoie $ Q_ {\ theta_N} (s, a) $

Le réseau de neurones est écrit en Keras. Le modèle ressemble à ceci.

Seul DQN diffusera le programme. Le programme complet est ici. https://github.com/shibuiwilliam/maze_solver

Voici les agents. Il se compose d'un modèle de réseau neuronal, d'une mémoire pour stocker les états / actions / récompenses, la sélection d'actions et la relecture d'expérience. La variable de classe ʻepsilon est la probabilité d'effectuer des actions aléatoires. Cette valeur diminuera avec ʻe_decay à mesure que l'entraînement progresse. ʻE_min est la valeur minimale de ʻepsilon. Finalement, vous vous comporterez de manière optimale selon le modèle prédictif, mais au départ vous vous comporterez de manière aléatoire et échantillonnerez.

class DQN_Solver:
    def __init__(self, state_size, action_size):
        self.state_size = state_size # list size of state
        self.action_size = action_size # list size of action
        self.memory = deque(maxlen=100000) # memory space
        self.gamma = 0.9 # discount rate
        self.epsilon = 1.0 # randomness of choosing random action or the best one
        self.e_decay = 0.9999 # epsilon decay rate
        self.e_min = 0.01 # minimum rate of epsilon
        self.learning_rate = 0.0001 # learning rate of neural network
        self.model = self.build_model() # model
        self.model.summary() # model summary

    # model for neural network
    def build_model(self):
        model = Sequential()
        model.add(Dense(128, input_shape=(2,2), activation='tanh'))
        model.add(Flatten())
        model.add(Dense(128, activation='tanh'))
        model.add(Dense(128, activation='tanh'))
        model.add(Dense(1, activation='linear'))
        model.compile(loss="mse", optimizer=RMSprop(lr=self.learning_rate))
        return model

    # remember state, action, its reward, next state and next possible action. done means boolean for goal
    def remember_memory(self, state, action, reward, next_state, next_movables, done):
        self.memory.append((state, action, reward, next_state, next_movables, done))

    # choosing action depending on epsilon
    def choose_action(self, state, movables):
        if self.epsilon >= random.random():
            # randomly choosing action
            return random.choice(movables)
        else:
            # choosing the best action from model.predict()
            return self.choose_best_action(state, movables)

	# choose the best action to maximize reward expectation
    def choose_best_action(self, state, movables):
        best_actions = []
        max_act_value = -100
        for a in movables:
            np_action = np.array([[state, a]])
            act_value = self.model.predict(np_action)
            if act_value > max_act_value:
                best_actions = [a,]
                max_act_value = act_value
            elif act_value == max_act_value:
                best_actions.append(a)
        return random.choice(best_actions)

    # this experience replay is going to train the model from memorized states, actions and rewards
    def replay_experience(self, batch_size):
        batch_size = min(batch_size, len(self.memory))
        minibatch = random.sample(self.memory, batch_size)
        X = []
        Y = []
        for i in range(batch_size):
            state, action, reward, next_state, next_movables, done = minibatch[i]
            input_action = [state, action]
            if done:
                target_f = reward
            else:
                next_rewards = []
                for i in next_movables:
                    np_next_s_a = np.array([[next_state, i]])
                    next_rewards.append(self.model.predict(np_next_s_a))
                np_n_r_max = np.amax(np.array(next_rewards))
                target_f = reward + self.gamma * np_n_r_max
            X.append(input_action)
            Y.append(target_f)
        np_X = np.array(X)
        np_Y = np.array([Y]).T
        self.model.fit(np_X, np_Y, epochs=1, verbose=0)
        if self.epsilon > self.e_min:
            self.epsilon *= self.e_decay

Dans Experience Replay, l'état actuel, le comportement, la récompense et l'état suivant, le comportement optimal et la récompense sont transmis au réseau neuronal pour l'apprentissage. Correspond à la valeur attendue du comportement actuel.

C'est une formation modèle. ʻEpisodesest le nombre d'entraînements ettimes` est le nombre d'échantillonnages (recherches) dans un épisode. Échantillonnage → l'entraînement est répété 1000 x 20000 fois. Cependant, si vous atteignez l'objectif au milieu de l'échantillonnage, l'échantillonnage sera interrompu.

Ajustez le nombre d'échantillons et de formations pour correspondre aux valeurs de ʻepsilon et ʻe_decay. Si l'échantillonnage («temps») est faible, il n'y a pas assez de données d'échantillon qui peuvent être rejouées, et si le nombre de formations («épisodes») est faible, le réseau neuronal n'entraîne pas le modèle. La valeur ʻepsilon décroît avec chaque ʻépisodes, donc à moins que cette valeur ne soit suffisamment petite selon ʻe_decay`, quelle que soit la qualité du modèle, elle continuera à se comporter de manière aléatoire pendant l'échantillonnage et le modèle Ne peut pas être évalué.

La valeur de ce côté est ajustée en fonction de la taille du labyrinthe. S'il est 10x10, un modèle pourrait être généré avec cette valeur numérique, mais si la taille est grande, la formation se terminera avant que le nombre d'échantillonnages ne soit suffisant et un modèle biaisé sera créé.

# train the model
state_size = 2
action_size = 2
dql_solver = DQN_Solver(state_size, action_size)

# number of episodes to run training
episodes = 20000

# number of times to sample the combination of state, action and reward
times = 1000

for e in range(episodes):
    state = start_point
    score = 0
    for time in range(times):
        movables = maze_field.get_actions(state)
        action = dql_solver.choose_action(state, movables)
        reward, done = maze_field.get_val(action)
        score = score + reward
        next_state = action
        next_movables = maze_field.get_actions(next_state)
        dql_solver.remember_memory(state, action, reward, next_state, next_movables, done)
        if done or time == (times - 1):
            if e % 500 == 0:
                print("episode: {}/{}, score: {}, e: {:.2} \t @ {}"
                        .format(e, episodes, score, dql_solver.epsilon, time))
            break
        state = next_state
    # run experience replay after sampling the state, action and reward for defined times
    dql_solver.replay_experience(32)

Voici les résultats de la formation. Il est diffusé tous les 500 épisodes. score est la récompense de l'épisode, e est epsilon et @ est le nombre d'échantillons. Un petit nombre de @ signifie que vous notez au milieu de l'échantillonnage.


episode: 0/20000, score: 5.0, e: 1.0 	 @ 100
episode: 500/20000, score: 19.0, e: 0.95 	 @ 86
episode: 1000/20000, score: 14.0, e: 0.9 	 @ 82
episode: 1500/20000, score: 24.0, e: 0.86 	 @ 56
episode: 2000/20000, score: -9.0, e: 0.82 	 @ 138
episode: 2500/20000, score: 26.0, e: 0.78 	 @ 76
episode: 3000/20000, score: 20.0, e: 0.74 	 @ 84
episode: 3500/20000, score: 42.0, e: 0.7 	 @ 24
episode: 4000/20000, score: 44.0, e: 0.67 	 @ 22
episode: 4500/20000, score: 45.0, e: 0.64 	 @ 24
episode: 5000/20000, score: 46.0, e: 0.61 	 @ 36
episode: 5500/20000, score: 33.0, e: 0.58 	 @ 32
episode: 6000/20000, score: 43.0, e: 0.55 	 @ 32
episode: 6500/20000, score: 48.0, e: 0.52 	 @ 24
episode: 7000/20000, score: 38.0, e: 0.5 	 @ 34
episode: 7500/20000, score: 45.0, e: 0.47 	 @ 28
episode: 8000/20000, score: 43.0, e: 0.45 	 @ 42
episode: 8500/20000, score: 43.0, e: 0.43 	 @ 24
episode: 9000/20000, score: 45.0, e: 0.41 	 @ 28
episode: 9500/20000, score: 45.0, e: 0.39 	 @ 28
episode: 10000/20000, score: 48.0, e: 0.37 	 @ 20
episode: 10500/20000, score: 44.0, e: 0.35 	 @ 22
episode: 11000/20000, score: 46.0, e: 0.33 	 @ 24
episode: 11500/20000, score: 45.0, e: 0.32 	 @ 22
episode: 12000/20000, score: 48.0, e: 0.3 	 @ 26
episode: 12500/20000, score: 45.0, e: 0.29 	 @ 18
episode: 13000/20000, score: 47.0, e: 0.27 	 @ 18
episode: 13500/20000, score: 41.0, e: 0.26 	 @ 24
episode: 14000/20000, score: 47.0, e: 0.25 	 @ 16
episode: 14500/20000, score: 47.0, e: 0.23 	 @ 14
episode: 15000/20000, score: 47.0, e: 0.22 	 @ 14
episode: 15500/20000, score: 48.0, e: 0.21 	 @ 14
episode: 16000/20000, score: 46.0, e: 0.2 	 @ 18
episode: 16500/20000, score: 44.0, e: 0.19 	 @ 20
episode: 17000/20000, score: 48.0, e: 0.18 	 @ 14
episode: 17500/20000, score: 45.0, e: 0.17 	 @ 20
episode: 18000/20000, score: 48.0, e: 0.17 	 @ 18
episode: 18500/20000, score: 48.0, e: 0.16 	 @ 20
episode: 19000/20000, score: 46.0, e: 0.15 	 @ 18
episode: 19500/20000, score: 48.0, e: 0.14 	 @ 16

Au fur et à mesure que l'épisode se répète, le score augmente, l'epsilon se désintègre et le nombre d'échantillons diminue. Vous pouvez voir qu'il est agrégé dans un bon modèle.

Je vais essayer de résoudre le labyrinthe avec le modèle que j'ai réalisé.

# try the model
state = start_point
score = 0
steps = 0
while True:
    steps += 1
    movables = maze_field.get_actions(state)
    action = dql_solver.choose_best_action(state, movables)
    print("current state: {0} -> action: {1} ".format(state, action))
    reward, done = maze_field.get_val(action)
    maze_field.display(state)
    score = score + reward
    state = action
    print("current step: {0} \t score: {1}\n".format(steps, score))
    if done:
        maze_field.display(action)
        print("goal!")
        break

Le résultat est le même que l'apprentissage Q. Ce qu'ils recherchent est le même, et je me demande s'il existe un labyrinthe de cette taille.

en conclusion

Je voulais toucher DQN, puis j'ai comparé les algorithmes de recherche de labyrinthe. C'était bien que DQN fonctionne et c'était amusant. Le plus dur a été d'écrire un programme de labyrinthe qui peut être utilisé avec l'un ou l'autre algorithme, mais j'ai encore parfois des labyrinthes insolubles (les objectifs sont bloqués par des murs), mais je suis fatigué donc je reporte la correction. fait. En outre, il faut du temps pour ajuster les paramètres DQN. Je le vérifie dans un labyrinthe 20x20 en ce moment, donc je le téléchargerai à nouveau une fois terminé.

[PYTHON] Résolvez votre propre labyrinthe avec DQN

Résolvez votre propre labyrinthe avec DQN

Aperçu

Algorithme A-star

en conclusion