[Renforcer l'apprentissage] Rechercher le meilleur itinéraire

introduction

J'ai essayé de résoudre le meilleur problème de recherche d'itinéraire avec un programme python. En tant que manuel ["Strengthening learning"](http://www.amazon.co.jp/ Strengthening learning-Richard-S-Sutton / dp / 4627826613 / ref = sr_1_1? Ie = UTF8 & qid = 1463965873 & sr = 8-1 & keywords = Renforcement de l'apprentissage % E3% 80% 80 Mikami) a été utilisé.

Structure de cet article

Meilleure recherche d'itinéraire

règle

Considérez le problème de recherche dans le labyrinthe comme indiqué sur la figure. Le cercle blanc est l'agent, le rouge est la zone négative et le bleu est le but. Le problème de recherche ici se réfère à la recherche d'un itinéraire qui maximise la récompense pour atteindre l'objectif. Les règles sont présentées ci-dessous.

  1. Taille du labyrinthe: 6 $ \ times6 $
  2. Récompenses dans chaque zone: zone noire 0 $, zone rouge -1 $, zone bleue $ + 3 $
  3. Lorsque vous atteignez l'objectif bleu, recommencez à partir du point de départ en haut à gauche

Mettre à jour la valeur Q

Mettez à jour la valeur $ Q $ avec la formule suivante.

Q_{new}(s_t, a) = Q_{old}(s_t, a) + \alpha\bigl[r_{t+1} + \gamma max_{a'}Q(s_{t+1}, a') - Q_{old}(s_t, a)\bigr]

$ Q (s_t, a) $ représente la valeur de l'action $ a $ dans un état $ s_t $. L'action dans l'état $ s_t $ $ a $ donne la récompense $ r_ {t + 1} $. Lors de la mise à jour de la valeur $ Q $, la récompense la plus récente $ r_ {t + 1} $ est ajoutée à la valeur maximale obtenue par l'action $ a '$ dans l'état suivant $ s_ {t + 1} $. Ajoutez le produit multiplié par gamma $. Cela signifie que l'action dans un certain état est sélectionnée en considérant non seulement la dernière récompense mais également la valeur dans l'état suivant. $ \ Gamma $ est appelé le taux d'actualisation, et $ \ alpha $ est appelé le taux d'apprentissage.

la mise en oeuvre

Je l'ai implémenté en python. La probabilité d'effectuer des actions aléatoires est $ \ varepsilon = 0,1 $, le taux d'apprentissage est $ \ alpha = 0,2 $ et le taux d'actualisation est $ \ gamma = 0,9 $. L'apprentissage se termine lorsque vous atteignez l'objectif de 300 $.

.
|- agent.classe d'agent py
|- mazeimage.py Afficher / enregistrer la classe
|- main.py
|- resources
      |- maze.csv

agent.py


import numpy
import cv2
import random
import copy

class Agent:

	# constructor
	def __init__(self, maze_shape):
		self.state = numpy.array([0, 0])
		self.actions = self.__create_actions(maze_shape)
		self.moves = {0: numpy.array([0, -1]), 1: numpy.array([1, 0]), 2: numpy.array([0, 1]), 3: numpy.array([-1, 0])}
		self.q = numpy.zeros((4, ) + maze_shape)


# public method
	def act(self, maze, epsilon, alpha, gamma):
		act_index = self.__select_action(epsilon)
		move = self.moves.get(act_index)
		reward = maze[tuple(self.state + move)]
		self.update_q(act_index, move, reward, alpha, gamma)
		self.state += move


	def update_q(self, act_index, move, reward, alpha, gamma):
		y, x = self.state
		_q = self.q[act_index, y, x]
		self.q[act_index, y, x] = _q + alpha * (reward + gamma * self.__get_max_q(move) - _q)


	def goal(self, maze_shape):
		return numpy.array_equal(self.state, numpy.array(maze_shape) - 1)


	def reset(self):
		self.state = numpy.array([0, 0])


# private method
	def __create_actions(self, maze_shape):
		actions = []
		maze_h, maze_w = maze_shape
		for j in range(maze_h):
			actions.append([])
			for i in range(maze_w):
				action = [0, 1, 2, 3]
				self.__remove_actions(action, maze_h, maze_w, j, i)
				actions[j].append(action)

		return numpy.array(actions)


	def __remove_actions(self, action, maze_h, maze_w, j, i):
		if i == 0:
			action.remove(0)
		if i == maze_w - 1:
			action.remove(2)
		if j == 0:
			action.remove(3)
		if j == maze_h - 1:
			action.remove(1)

	
	def __select_action(self, epsilon):
		y, x = self.state
		action = copy.deepcopy(self.actions[y, x])
		if numpy.random.rand() > epsilon:
			mode = '!!!greedy!!!'
			act_index = self.__select_greedy_action(action)
		else:
			mode = '!!!random!!!'
			act_index = self.__select_random_action(action)

		print u'%s  state: (%d, %d), action: %d' % (mode, y, x, act_index)

		return act_index


	def __select_greedy_action(self, action):
		y, x = self.state
		_max = self.q[action, y, x].max()
		_indexes = list(numpy.argwhere(self.q[action, y, x] == _max))
		random.shuffle(_indexes)
		return action[_indexes[0]]


	def __select_random_action(self, action):
		random.shuffle(action)
		return action[0]


	def __get_max_q(self, move):
		y, x = self.state + move
		move = self.actions[y, x]
		return self.q[move, y, x].max()

mazeimage.py


import numpy
import cv2

class MazeImage:

	# constructor
	def __init__(self, maze, height, width):
		self.height, self.width = (height, width)
		self.maze_h, self.maze_w = maze.shape
		self.ystride = height / self.maze_h
		self.xstride = width / self.maze_w
		self.map_org = self.__create_image(maze)
		self.map_now = self.map_org
		self.writer = cv2.VideoWriter('q_learning.mv4', cv2.cv.CV_FOURCC('m', 'p', '4', 'v'), 30, (self.map_org.shape[1], self.map_org.shape[0]))


# public method
	def show(self, agent):
		self.map_now = self.map_org.copy()
		_y, _x = agent.state
		center = (int((_x + 0.5) * self.xstride), int((_y + 0.5) * self.ystride))
		cv2.circle(self.map_now, center, 11, (255, 255, 255), -1, cv2.cv.CV_AA)
		cv2.imshow('', self.map_now)
		return cv2.waitKey(10)


	def save_movie(self):
		self.writer.write(self.map_now)


	def shortest_path(self, q):
		shortest_map = self.map_org.copy()
		q_arrow = numpy.vectorize(lambda x: {0: '<', 1: 'V', 2: '>', 3: '^'}.get(x))(q.argmax(axis = 0))

		for j in range(self.maze_h):
			for i in range(self.maze_w):
				pt = (int(self.xstride * (i + 0.35)), int(self.ystride * (j + 0.6)))
				cv2.putText(shortest_map, q_arrow[j, i], pt, cv2.FONT_HERSHEY_PLAIN, 1, [255, 255, 255])

		return shortest_map


# private method
	def __create_image(self, maze):
		image = numpy.zeros((self.height, self.width, 3)).astype('uint8')

		for j in range(self.maze_h):
			for i in range(self.maze_w):
				tl = (self.xstride * i, self.ystride * j)
				br = (self.xstride * (i + 1) - 1, self.ystride * (j + 1) - 1)
				cv2.rectangle(image, tl, br, self.__color(maze[j, i]), -1)

		return image


	def __color(self, score):
		if score == 0.0:
			return [0, 0, 0]
		elif score == -1.0:
			return [0, 0, 127]
		else:
			return [127, 0, 0]

main.py


from agent import *
from mazeimage import *

if __name__ == '__main__':

	# init
	epsilon = 0.1
	alpha = 0.2
	gamma = 0.9
	maze = numpy.loadtxt('./resources/maze.csv', delimiter = ',')
	agent = Agent(maze.shape)
	maze_image = MazeImage(maze, 300, 300)

	trial = 0
	while True:
		if maze_image.show(agent) == 27:
			print '!!!escape!!!'
			break

		agent.act(maze, epsilon, alpha, gamma)
		maze_image.save_movie()
		
		if agent.goal(maze.shape):
			print '\033[32m' + '!!!goal!!!' + '\033[0m'
			trial += 1
			print 'next trial: %d' % trial
			agent.reset()

		if trial == 300:
			break

	maze_image.save_movie()
	cv2.imwrite('shortest.png', maze_image.shortest_path(agent.q))
	cv2.destroyAllWindows()

maze.csv

0 -1 0 0 0 0
0 -1 0 -1 -1 0
0 -1 0 -1 0 0
0 -1 0 -1 0 -1
0 -1 0 -1 0 0
0 0 0 -1 -1 3

résultat

Le chiffre du meilleur itinéraire obtenu par apprentissage est affiché. Vous pouvez apprendre l'itinéraire pour atteindre l'objectif sans passer par la zone négative. Je l'ai implémenté pour que l'état d'apprentissage soit enregistré sous forme de vidéo, donc si vous êtes intéressé, veuillez le déplacer.


en conclusion

J'ai pu résoudre le meilleur problème de recherche d'itinéraire. Comme le montre la formule de mise à jour de $ Q (s_t, a) $, il était entendu que la valeur exsude du côté objectif en considérant la valeur dans l'état de 1 $ à venir.

Recommended Posts

[Renforcer l'apprentissage] Rechercher le meilleur itinéraire
Renforcer l'apprentissage de la troisième ligne
[Apprentissage de renforcement d'introduction] Renforcement de l'apprentissage pour bouger pour le moment
TF2RL: bibliothèque d'apprentissage améliorée pour TensorFlow2.x
Mettre en œuvre la recherche de chemin le plus court pour le labyrinthe
Rechercher des fichiers avec l'extension spécifiée
[Introduction] Renforcer l'apprentissage
L'histoire selon laquelle le coût d'apprentissage de Python est faible
Wagtail est le meilleur CMS pour Python! (Peut-être)
Apprentissage par renforcement futur_2
Apprentissage par renforcement futur_1
Collecter des images pour l'apprentissage automatique (API Bing Search)
Notes d'apprentissage pour la fonction migrations dans le framework Django (2)
À la recherche du meilleur stéréogramme à points aléatoires (RDS).
[Boto3] Rechercher des utilisateurs Cognito avec l'API List Users
Electron est la meilleure solution pour le développement multi-plateforme de Python
Notes d'apprentissage pour la fonction migrations dans le framework Django (3)
Notes d'apprentissage pour la fonction migrations dans le framework Django (1)
J'ai étudié l'algorithme d'apprentissage de renforcement du trading d'algorithmes
Apprentissage amélioré 1 installation de Python
Renforcer l'apprentissage 3 Installation d'OpenAI
[Renforcer l'apprentissage] Tâche de bandit
Renforcer l'apprentissage 1 édition introductive
Apprentissage par renforcement dans les plus brefs délais avec Keras avec OpenAI Gym
Rechercher des fichiers volumineux sous Linux à partir de la ligne de commande
Essayez une recherche similaire de recherche d'images à l'aide du SDK Python [Recherche]
Recherchez le pandas.DataFrame avec une variable et obtenez la ligne correspondante.
Google recherche la chaîne sur la dernière ligne du fichier en Python
Si vous apprenez Linux pour la première fois, faites-le!