智能体路径规划
C++实现:
代码如下:
#include <iostream>
#include <time.h>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iterator>
#include <fstream>
using namespace std;
ofstream out_explore("d:\\explore.txt");
ofstream out_use("d:\\use.txt");
void access(int state, int q[6][6], int r[6][6])
{
vector<int> q_action;
q_action.push_back(state+1);
out_use<<"Start from : "<<state+1<<endl; //
while(state != 5)
{
int act = 0;
int max_state = q[state][0];
for(int action = 1; action < 6; ++action)
{
if(q[state][action] > max_state)
{
max_state = q[state][action];
act = action;
}
}
q_action.push_back(act+1);
state = act;
out_use<<"The most reward is from action "<<act+1 <<" ,and it is "<<max_state<<"."<<endl;
}
if(state == 5)
out_use<<"Reach the goal room!"<<endl;
copy(q_action.begin(), q_action.end(), ostream_iterator<int>(cout," -> "));
cout<<"ok"<<endl;
}
int special(int in_state, float gamma, int q[6][6], int r[6][6])
{
vector<int> r_action;
for(int action=0; action<6; ++action)
{
if(r[in_state][action] >=0 )
r_action.push_back(action);
}
int m = rand() % (r_action.size());
int next_state = r_action[m];
int max = q[next_state][0];
for(int i = 1; i < 6; ++i)
{
if(max < q[next_state][i])
max = q[next_state][i];
}
q[in_state][next_state] = r[in_state][next_state] + gamma * max;
return next_state;
}
void qlearning(float gamma, int r[6][6], int q[6][6])
{
//获得随机进入的门
int in_state = (rand() % 5); //产生0-5的随机数
out_explore<<"★ "<<in_state+1;
while (in_state != 5)
{
in_state = special(in_state, gamma, q, r);
out_explore<<"->"<<in_state+1;
if(in_state == 5)
{
special(in_state, gamma, q, r);
}
}
out_explore<<endl;
}
int main()
{
int q[6][6]= {0};
int r[6][6]=
{
{-1, 0, 0, 0,-1, -1},
{0, -1, -1, 0, -1, -1},
{0, -1, -1, -1, -1, -1},
{0, 0, -1, -1, 0, 100},
{-1, -1, -1, 0, -1, 100},
{-1, -1, -1, 0, 0, 100}
};
for(int i=0; i<100; i++) //执行多次qleaning函数 , 更新 q 数组
qlearning(0.8, r, q);
int max=0;
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++)
{
if(q[i][j] > max)
max = q[i][j];
}
}
cout<<"The convergence matrix: Q "<<endl;
for(int i=0; i<6; i++)
{
for(int j=0; j<6; j++)
{
q[i][j] = (int)(100*((float)(q[i][j]))/max);
cout<<q[i][j]<<"\t";
}
cout<<endl;
}
cout<<endl;
cout<<endl<<"智能体序列:"<<endl;
for(int i=0; i<6; ++i)
{
access(i, q, r);
out_use<<endl;
}
cout<<endl<<"input the number of room(1-6):";
int state ;
cin>>state;
if(state>6 || state <1)
cout<<"the number of room is error!"<<endl;
else
access(state-1, q, r);
out_explore.close();
out_use.close();
return 0;
}
Python实现:
代码如下:
# -*- coding:UTF-8 -*-
import numpy as np
import random
def acorss(state):
q_action = [state+1]
max_state = -1
while state != 5:
for action in range(6):
if q[state][action] > max_state:
max_state = q[state][action]
act = action
q_action.append(act+1)
state = act
print(q_action)
def qlearning(gamma, r, q):
in_state = random.randint(0, 5)
while in_state != 5:
in_state = special(gamma, in_state,r, q)
if in_state == 5:
special(gamma, in_state,r, q)
def special(gamma, in_state, r, q):
r_action = []
for action in range(6):
if r[in_state][action] >= 0:
r_action.append(action)
next_state = r_action[random.randint(0, len(r_action) - 1)]
max = -1
for i in range(6):
if r[next_state][i] >= 0:
if q[next_state][i] > max:
max = q[next_state][i]
q[in_state][next_state] = r[in_state][next_state] + gamma* max
return next_state;
if __name__ == '__main__':
q = np.zeros([6, 6])
r = np.array([
[-1, 0, 0, 0,-1, -1],
[0, -1, -1, 0, -1, -1],
[0, -1, -1, -1, -1, -1],
[0, 0, -1, -1, 0, 100],
[-1, -1, -1, 0, -1, 100],
[-1, -1, -1, 0, 0, 100]
])
for i in range(0, 100):
qlearning(0.8, r, q)
max = q.max()
for i in range(6):
for j in range(6):
if(q[i][j] != 0):
q[i][j] = (int)(100*(q[i][j]/max))
state = input('Input the number of room(1-6):')
state = int(state)
if state > 6 or state < 1:
print('Error!!')
else:
acorss(state-1)
探索的过程:
★ 2->1->3->1->3->1->2->1->3->1->2->4->1->2->1->4->6
★ 1->3->1->2->4->6
★ 3->1->4->1->3->1->4->2->4->1->2->1->2->4->6
★ 4->1->2->4->1->2->1->3->1->3->1->2->1->3->1->2->1->4->2->4->5->6
★ 2->4->1->4->5->6
★ 2->1->2->1->2->4->6
★ 4->5->4->6
★ 4->6
★ 4->6
★ 3->1->2->4->5->6
★ 5->4->2->1->3->1->3->1->3->1->2->1->4->6
★ 4->2->4->6
★ 1->4->6
★ 4->6
★ 4->6
★ 5->6
★ 2->1->4->1->4->2->1->4->1->3->1->4->6
★ 1->3->1->2->4->6
★ 1->2->4->2->1->3->1->4->2->1->2->4->5->4->6
★ 1->4->2->1->4->6
★ 3->1->2->1->4->1->3->1->4->2->4->1->2->1->3->1->2->4->1->2->4->5->4->1->3->1->3->1->4->6
★ 1->2->4->6
★ 2->1->2->1->3->1->2->1->2->1->4->2->1->3->1->4->1->3->1->4->2->4->1->3->1->2->1->4->6
★ 5->6
★ 4->2->1->2->4->1->3->1->4->1->4->6
★ 5->4->6
★ 5->6
★ 1->3->1->4->2->4->5->6
★ 4->2->1->2->1->3->1->4->2->4->2->4->2->1->2->4->1->2->4->6
★ 1->2->1->4->5->4->2->1->3->1->3->1->3->1->3->1->3->1->2->1->3->1->3->1->3->1->4->5->6
★ 4->1->3->1->3->1->4->6
★ 3->1->2->1->4->1->4->5->4->2->4->5->4->1->2->4->1->2->1->2->4->5->4->1->2->1->4->2->1->4->5->6
★ 2->1->4->6
★ 4->1->3->1->3->1->2->1->3->1->3->1->3->1->3->1->4->5->6
★ 2->1->4->1->3->1->3->1->4->6
★ 2->1->4->5->4->1->4->1->2->4->5->6
★ 2->4->5->4->1->3->1->4->5->4->1->4->2->4->5->4->6
★ 1->2->1->2->4->1->2->1->2->4->6
利用的过程:
Start from : 1
The most reward is from action 4 ,and it is 79.
The most reward is from action 6 ,and it is 100.
Reach the goal room!
Start from : 2
The most reward is from action 4 ,and it is 79.
The most reward is from action 6 ,and it is 100.
Reach the goal room!
Start from : 3
The most reward is from action 1 ,and it is 63.
The most reward is from action 4 ,and it is 79.
The most reward is from action 6 ,and it is 100.
Reach the goal room!
Start from : 4
The most reward is from action 6 ,and it is 100.
Reach the goal room!
Start from : 5
The most reward is from action 6 ,and it is 100.
Reach the goal room!
Start from : 6
Reach the goal room!
Start from : 3
The most reward is from action 1 ,and it is 63.
The most reward is from action 4 ,and it is 79.
The most reward is from action 6 ,and it is 100.
Reach the goal room!
智能体路径规划报告
如下:
智能体路径规划
姓名:×××
时间:2017年8月14日
目 录
1. Q-learning的公式推导...................................................... 3
2. 马尔可夫决策过程............................................................ 3
3. 问题的建模分析及抽象.................................................... 5
4. RL的探索和利用过程的仿真.......................................... 10
5. 探索和利用过程的可视化.............................................. 11
6. 总结.................................................................................. 12
7. 参考文献.......................................................................... 12
1.Q-learning的公式推导
在确定策略h(x)下,一个状态x,采取一个给定动作u的Q-值函数:X*U→ℝ,记为。
(为奖赏函数)
式中,,对于k >= 0,,且对于k >= 1,,那么有<1>式可以推出Bellman等式为:
(为奖赏函数,为迁移函数)
Bellman最优等式,就是一个状态x,采取一个给定动作u后,最优的Q值,记为,它等于立即奖赏与下一个状态最优动作的折扣最有Q-值函数之和,即
(为奖赏函数,为迁移函数)
∈[0,1]为折合因子,表明未来的回报相对于当前奖赏的重要程度。当时,相当于只考虑立即奖赏而不考虑长期回报,当时,将立即奖赏和长期回报看得同等重要。
2.马尔可夫决策过程
马尔可夫决策过程和强化学习有着密切的关系,强化学习是马尔可夫决策过程应用的一个领域。
在马尔可夫决策过程中,做出下一个动作与之前所走过的状态和动作都没有关系,而只和当前状态有关。这类似于数学中概率的一个问题,同一个种类的东西,不管它们之前经历了什么,在此之后,它们发生一些事情的概率是相等的,例如,同一时间,一个50岁的成年人和一个刚出生的婴儿,他们的寿命再增加60岁的概率是相等的。
马尔可夫决策过程,可以对一个未知的环境进行探测,它不断探索的过程就是它学习的过程。在这个过程中,它会根据奖赏值来做判断,参考γ参数,来综合考虑立即奖赏和之后的未知的奖赏,即延长奖赏。通过不断的探索,最后在它的大脑中绘制出一个成熟的、很完善的结构。在得到一个收敛的结果后,之后便可以直接利用这个收敛的结果中的回报值来选择动作。
马尔可夫决策过程可以很好地处理机器人规划路径、走出房间的问题。马尔可夫决策过程和我们人类面对未知的东西时所做的事情很像,我们总是从尝试开始,再到后面的熟悉。所以马尔可夫决策过程在人工智能领域发挥着重要的作用。
强化学习(Reinforcement Learning)问题可以利用马尔可夫决策过程(MDP)框架来形式化地描述。
在马尔可夫决策过程中,有四个重要的因素,即(状态、动作、奖赏、迁移)。
1.是环境的状态集
2.为动作的集合,动作用来控制系统的状态
3.和。在离散的时间步k,对状态采取动作,迁移状态到下一状态,并得到奖赏。根据迁移情况,可以分为确定环境迁移和随机环境迁移。
马尔可夫决策过程应用策略的方法:
(1)从初始状态集中选择一个初始状态;
(2)根据策略h,选出所要采取的动作,并执行该动作;
(3)根据迁移函数和奖赏函数得到下一个状态和执行这个动作的奖赏,即和。
(4)不断重复上面3个步骤,最后产生:。
Robot的任务是在利用马尔可夫决策过程和环境交互的过程中,学习一个策略h:X→U,从X状态到达U状态,并使得产生的累计奖赏最大。回报是robot所做动作的奖赏之和。
另外,根据过程是否可以分成带有终止时间步的片段,可分为情节式任务和连续式任务,即无限期地进行下去。
总之,马尔可夫决策过程的特别之处是有动作和回报的部分,是一个具有无后效性的决策方式。它是马尔可夫链的发展,并且在信息处理、数字计算方法、经济、管理科学等领域都有重要的应用,而不仅仅只在计算机领域运用到。
3.问题的建模分析及抽象
根据题目当中的房间图,每个房间/空间视为一个节点,它们之间的门是连接两个房间的通道。在这里,我们把一个节点称为一个状态state,从一个房间去往相连的房间称为动作action。由房间及房间之间的连通状态,得出一个模型图:
图中的箭头表示从键尾的房间可以直接通往箭头的房间。
在这个案例中,我用到了马尔可夫决策过程,因此在分析解决这个问题的时候,用到了奖赏等度量值。将直接通往目标空间6的动作的奖赏设为100,而其它不能直接通往目标空间的动作的奖励值视为0。由此得到一个新的模型:
箭头上的数字表示相应动作的奖励值。
根据以上信息,我们可以得出一个表示奖励值的6×6的矩阵R:
行代表状态,列是行表示的状态去往相应房间的动作。-1表示两个状态之间不相连,100表示相应的动作直接去往目标状态,0表示两状态之间相通,但不是去往目标空间。
在Q学习中,我们让robot自主学习,在这个未知的环境中不断探索,通过学习对环境熟悉,并在之后可以利用探索的结果直接从特定房间/空间按最优路径到达目标空间。因此,我们初始化一个全零的6×6矩阵Q,表示robot最初对环境的认识,可以将其视为robot的大脑。
初始化Q矩阵为0:
在Q学习中有一个十分重要的公式:
转换成中文即:
在这里我们取折合因子γ的值为0.8。
举一个例子来模拟robot探索环境和更新自己大脑(即Q矩阵)的过程:
假如robot随机选了一个出发点:4号房间,从R矩阵中,我们发现第4行的第1、2、5、6列均非负,因此这些均是可以进行的动作,而robot此时并不清楚选哪一个动作最优,它从这四个房间里随机选择一个。
假如它选择了去6号空间的动作,我们观察R矩阵的第6行,发现通往4、5、6房间的动作都是可以进行的,我们在Q矩阵里,比较第六行的第4、5、6列的值,并取出其中的最大值。
应用上述的Q学习的公式:
Q(4,6) = R(4, 6) + 0.8 * max ( Q(6, 4), Q(6, 5), Q(6, 6)) = 100 + 0.8 * 0 = 100。
更新Q矩阵:
因为到达了目标空间6,因此,这次探索完成,继续下一次学习。
经过多次探索,最终得到一个收敛的Q矩阵:
归一化后的Q矩阵:
此时,robot学习到了到达目标空间的最优路径。
由以上收敛后的Q矩阵,得出新的模型:
根据该模型,可以很明确地得出最优路经。
从房间2出发,回报值最大的是去房间4的动作,之后回报值最大的是去往空间6的动作,即序列2 - 4 - 6。
最后可以得出所有的智能体序列:
1 - 4 - 6
2 - 4 - 6
3 - 1 - 4 - 6
4 - 6
5 - 6
6
4.RL的探索和利用过程的仿真
通过强化学习得到的智能体序列:
程序执行情况:
程序中设置的探索次数是100次,通过实验观察,探索57次左右就可以得到一个收敛情况很好的矩阵,而对于能够找到最优的路径来说,进行5次探索就可以达到效果。
在程序代码中,qlearning()和special()两个函数实现了探索的功能,access()函数实现了利用的功能。
程序代码见robot文件夹。
5.探索和利用过程的可视化
探索和利用的过程分别在“explore.txt”和“use.txt”文件中呈现。此外,在程序运行后,D盘下将自动产生这两个文件。
探索的过程:
利用的过程:
6.总结
通过完成这次题目,我对强化学习、Q学习、马尔可夫决策过程等知识进行了学习和了解。这些知识在机器学习中是十分重要的部分,为人工智能奠定了基础。我运用C++语言完成了相关的代码编写工作,其中也运用到了部分C++ STL的知识。同时我认识到Python语言的重要性,之前对Python有过一些了解,因此也用Python语言编了一份代码。可视化的相关知识是我在以后的学习生活中应该关注的方面。在本次考核题目当中,我通过两个文本文件展示了RL探索与利用的过程。我的深刻体会是,在完成这个题目的过程中,通过查阅一些资料,在短时间内学习了以前从未接触甚至没有听说过的学科,这让我发现这种学习方式的高效的优势,这也是一个一通百通的学习方法,面对新的知识的时候能够很快地学习和掌握。
7.参考文献
[1]刘全,傅启明,钟珊,黄蔚.大规模强化学习[M].北京:科学出版社,2017.3:1-22,99
[2]霍华德 M.施瓦兹(Howard M.Schwartz).多智能体机器学习:强化学习方法[M].北京:机械工业出版社,2017.6,14-21
[3]张汝波,杨广铭,顾国昌,张国印.Q—学习及其在智能机器人局部路径规划中的应用研究[J].计算机研究与发展,1999,36(12):1-7
[4]梁泉.未知环境中基于强化学习的移动机器人路径规划[J].机电工程,2012,29(4):1-5