基于强化学习马尔科夫决策过程(MDP)的吃豆人

正文索引 [隐藏]

Pacman MDPAgent

项目开源 Pacman_MDP
基于马尔科夫决策过程的自动运行智能体,控制吃豆人自动完成游戏,(没有考虑吃掉胶囊之后的鬼魂可食用状态)

视频上传在YouTube(需要梯子)
中等地图运行100次胜率

小地图运行100次胜率

1. 简介

Markov Decision Process (MDP)马尔科夫决策过程 是基于马尔可夫理论的随机动力系统的最优决策过程。马尔可夫决策过程是马尔可夫的(没有后果,相关系统的下一个状态只是当前的状态信息,并与之前的状态无关),但不同之处在于,MDP认为动作不仅与当前状态相关,而且也与下一步的动作有关。

一个MDP由五个元组组成 (S, A, P(:,:), R(:,:), \gamma)S 是状态的有限集, A 是动作的有限集, P 是状态转移的可行性 P_{ss’}^a=\vec{P}[S_{t+1} = s’ | S_t = s,A_t =a], R 是奖励方程 R_s^a = \vec{E}[R_{t+1}|S_t=s,A_t=a]\gamma 是折扣因子 \gamma \in [0,1]. A policy \pi 当然状态的可能动作分布 \pi(a|s)=\vec{P}[A_t=a|S_t=s], 哪个表示在给定状态下动作的概率分布. 也就是说, \pi 表示agent在下一状态中可能采取的任何操作的概率分布 s.

2. 描述

本课程要求我们创建一个mdp解决方案工作在吃豆人的环境。吃豆人可以知道世界上所有物体的位置(墙壁、食物、胶囊、鬼魂)。(walls, food, capsules, ghosts).

2.1 流程图

2.2 Value Map 初始化

在每一步操作之后,我们需要使用pacman状态来初始化值映射,以获取所有对象的位置并为每个状态(位置)提供奖励。

S_t = [food, capsule, wall(not \ used \ for \ calculate), ghost, visited] = [5, 5, -5(not\ used\ for\ calculate), -100, 0]

例如, value map 看起来像:

2.3 使用贝尔曼方程迭代 Bellman Equation

i. 判断地图大小

函数 api.corners() 我们可以得到row和col.的最大索引,从而知道布局是samllGrid还是mediumClassic。因为samllGrid是一张7\times7 的图s,而mediumClassic是一张20\times11大小的地图。

ii. 临近鬼混区域填写负值

让吃豆人更怕鬼我使用了一个for循环来设置一个负向值到靠近幽灵的位置。该值为-15 (3-distance\ with \ ghost\ in\ row \ or col) smallGrid和-10 (6-distance\ with \ ghostt\ in\ row \ or col) mediumClassic。如果幽灵和附近的幽灵位置之间有一堵墙,这个值将不会被重置。

iii. 选取需要更新值的位置

让吃豆人更怕鬼我使用了一个’ ‘ ‘ for ‘ ‘ ‘循环来设置一个负向值到靠近幽灵的位置。为了提高运行代码的速度,我只使用Bellman方程来更新