# qlearning_robot

**Repository Path**: xiaojie0532/qlearning_robot

## Basic Information

- **Project Name**: qlearning_robot
- **Description**: No description available
- **Primary Language**: Python
- **License**: Not specified
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2020-08-12
- **Last Updated**: 2020-12-19

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

### 概述
在这个项目中，你会需要实现一个 Q-learning算法来解决一个增强学习问题 -- 走迷宫。

 
### Github Repo
- 更新你的 `qlearning_robot` 目录
 ```
 git clone https://github.com/nd009/qlearning_robot.git
 ```
- `Qlearner.py` 提供了实现 `QLearner` 类的模版。
- `maze.py` 提供了实现`Maze` 类的模版。
- `mazeqlearning.py` 利用 `QLearner` 类和 `Maze`类解决走迷宫问题
- `testworlds` 目录下提供了一些迷宫可以用来测试。

## 定义迷宫问题

#### 地图
我们用一个二位数组定义了整个迷宫。迷宫的纬度是 10 * 10， 每一个迷宫都存储在csv文件中，用 integer 表示每个位置的属性，具体含义如下

- 0: 空地.
- 1: 障碍物.
- 2: 机器人的起始点.
- 3: 目标终点.
- 5: 陷阱.

一个迷宫 (world01.csv) 如下图所示 

```
3,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,1,1,1,1,1,0,0,0
0,5,1,0,0,0,1,0,0,0
0,5,1,0,0,0,1,0,0,0
0,0,1,0,0,0,1,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0,0
0,0,0,0,2,0,0,0,0,0
```

在这个例子中，机器人从最后一行的中间位置开始，目标为第0行第0列，中间连续的障碍物组成一面墙阻挡路线，同时左边有很多陷阱。

#### 机器人行走
有四个可能的行为： 向上走, 向右走, 向下走, 向左走。如果机器人尝试走入陷阱，则会真的走入陷阱。如果机器人尝试走入障碍物或走出地图，则会停留在原地，但依旧算作一步。

#### 随机行为
机器人有 0.2 的概率不执行指令，而是在四种行为中随机选择。
例如，如果机器人收到指令 “向上走”，会有一定的概率不往上走，而走其他方向。因此，一个 “聪明的” 机器人应该尽可能得远离陷阱。

#### 目标

我们的目标是让机器人在不走入陷阱的情况下，用最少的步数从起点到达终点。

## 定义迷宫问题为 Markov 决策过程 (MDP)
在使用 QLearning 解决走迷宫问题之前，我们首先要重新定义走迷宫问题为一个 Markov 决策过程， 因为 QLearning 是用来解决 Markov 决策过程的。 

Markov 决策过程包含四个元素，状态，行为，模型和奖励。
#### 状态
`S`: 10*10 地图上的每个位置，都对应一个状态，共 100 个状态。我们可以用 0 ~ 99 来代表所有状态。
#### 行为
`A`: 向上走，向下走，向左走，向右走，共 4 个行为。我们可以用 0 ~ 3 来代表所有行为。
#### 模型
`T(s, a, s') = P(s|s, a)`:   在状态 `s`, 执行行为 `a`, 进入状态 `s'` 的概率。模型可以被地图完全定义。例如从一个格子向上走，如果四周都没有障碍物，那么进入上下左右四个格子的概率分别为 0.85, 0.05, 0.05, 0.05, 进入其他各自的概率为0 。

#### 奖励
`R(s)`: 进入状态 `s` 的奖励。根据我们的目标:
>让机器人在不走入陷阱的情况下，用最少的步数从起点到达终点。

我们可以选择了最直接的奖励／惩罚。

- **reward = -1** 如果机器人走进了一个空地。
- **reward = -1** 如果机器人尝试走进障碍物，或走出地图。
- **reward = -100** 如果机器人走进了陷阱。
- **reward = 1** 如果机器人走到了终点。

如果你觉得选择其他的奖励函数更好得达到目标（更快收敛，更好收敛），也可以使用其他奖励函数。

## 定义迷宫问题为增强学习问题

在强化学习的问题中，我们并不知道完整的模型 `T(s, a, s')` 和奖励 `R(s)`。我们只知道四元组 `<s, a, s', r>`, 既在状态`s`下， 执行行为 `a`, 会进入`s'`, 获得奖励 `r`。

![](model-based.png)

我们的 Qlearner 会不断和世界互动，在状态 `s` 下， 执行行为 `a`，观察新的状态 `s'` 和获得的奖励 `r`。不断收集四元组，来学习这个世界的规则，找到最优策略。这也就是增强学习的学习过程。

## 实现 QLearner
你不可以导入任何额外的库，你需要按照下面定义的 API，在 `QLearner.py` 中实现 QLearner 类。 注意你的 QLearner 不应该知道任何有关走迷宫的信息。

#### QLearner()

QLearner 的构造函数，应该预留空间存放 所有状态和行为的 Q-table Q[s, a], 并将整个矩阵初始化为 0. 构造函数的每一个参数如下定义：

- `num_states` integer, 所有状态个数。
- `num_actions` integer, 所有行为个数。
- `alpha` float, 更新Q-table时的学习率，范围 0.0 ~ 1.0, 常用值 0.2。
- `gamma` float, 更新Q-table时的衰减率，范围 0.0 ~ 1.0, 常用值 0.9。
- `rar` float, 随机行为比例, 每一步随机选择行为的概率。范围 0.0（从不随机） ~ 1.0（永远随机）, 常用值 0.5。
- `radr` float, 随机行为比例衰减率, 每一步都更新 rar = rar * radr. 0.0（直接衰减到0） ~ 1.0（从不衰减）, 常用值 0.99。
- `verbose` boolean, 如果为真，你的类可以打印调试语句，否则，禁止所有打印语句。

#### query(s_prime, r) 

QLearner 的核心方法。他应该记录最后的状态 s 和最后的行为 a，然后使用新的信息 s_prime 和 r 来更新 Q-Table。 学习实例是四元组 `<s, a, s_prime, r>`. query() 应该返回一个 integer, 代表下一个行为。注意这里应该以 rar 的概率随机选择一个行为，并根据 radr 来更新 rar的值。

参数定义：

- `s_prime` integer, 新的状态
- `r` float, 即时奖励／惩罚，可以为正，可以为负。
 
#### querysetstate(s)
query() 方法的特殊版本。设置状态为 s，并且返回下一个行为 a （和 query() 方法规则一致，例如包括以一定概率随机选择行为）。但是这个方法不更新 Q-table，不更新 rar。我们主要会在两个地方用到它： 1）设置初始状态 2) 使用学习后的策略，但不更新它

这里是一个使用 API 的例子

```
import QLearner as ql

learner = ql.QLearner(num_states = 100, \ 
    num_actions = 4, \
    alpha = 0.2, \
    gamma = 0.9, \
    rar = 0.98, \
    radr = 0.999, \
    verbose = False)

s = 99 # 初始状态

a = learner.querysetstate(s) # 状态s下的执行行为 a

s_prime = 5 # 在状态 s，执行行为 a 之后，进入新状态 s_prime

r = 0 # 在状态 s，执行行为 a 之后，获得即使奖励／惩罚 r

next_action = learner.query(s_prime, r)
```

重声一次，QLearner 不应该知道任何有关迷宫的信息。

## 实现 Maze
Maze 类定义了迷宫的世界，起点，终点，障碍物和陷阱。
#### Maze()
Maze 的构造函数，定义了地图，随机行走概率，以及每一步的奖励／惩罚。你也可以在构造函数中定义自己的成员变量。例如起始地点，目标地点等。

#### get\_start\_pos()
返回机器人的起始地点。即地图中，数值为2的位置。

#### get\_goal\_pos()
返回机器人的目标地点。即地图中，数值为3的位置。

#### move()
根据地图信息，现在位置和行为指令来移动机器人。机器人有 0.2 的概率不执行指令，而是在4个行为中随机选择。如果机器人尝试走入障碍物或走出地图，则会停留在原地。

返回新的位置和得到的奖励。

#### print\_map()
工具函数，打印地图，无需修改。

#### print\_trail()
工具函数，打印地图和路径，无需修改。参数 `trail` 是一个坐标的数组。例如 `[(0,0), (0,1), (0,2), (1,2)]`


## 实现 mazeqlearning

#### to_state()
将位置用 0～99 的数字来表达，每个数字代表一个状态。

返回位置所对应的状态

#### train()
在给定的地图中进行多次行走，每次行走都会让机器人从起点走到终点，或者超时（超过100,000步）。

返回所有行走的奖励。

每一次尝试的伪代码:

```
total_reward = 0
robopos = startpos
action = learner.querysetstate(to_state(robopos))
while not at goal and not timeout:
	newpos, reward = maze.move(robopos, action)
	robopos = newpos
	action = learner.query(to_state(robopos), reward)
	totol_reward += reward		
```

#### maze_qlearning()
定义 QLearner 和 Maze，你可以使用默认参数，或使用自己的参数。调用 train() 进行训练，

返回所有行走的奖励的中位数。