算法

强化学习的目标是学习一个行为策略π：S→A，使系统选择的动作能够获得环境奖赏的累计值最大，也使得外部环境对学习系统在某种意义下的评价(或整个系统的运行性能)最佳。
Q学习算法可从有延迟的回报中获取最优控制策略。
伪码如下
1.Set parameter, and environment reward matrixR
2.Initialize matrixQ as zero matrix
3.For each episode:

• Select random initial state
• Do while not reach goal state

  • Select one among all possible actions for the current state

  • Using this possible action, consider to go to the next state

  • Get maximum Q value of this next state based on all possible actions

  • Compute

    
    

  • Set the next state as the current state

• End Do
  End For
  学习系数取值范围是[0,1)，如果值接近0，那么表示的是Agent更趋向于注重即时的环境反馈值。反之，则Agent更加考虑的是未来状态的可能奖励值。

思路

状态转换图如下

初始化矩阵为

每一episode的过程为

1. 随机选择初始初始状态A_F(05)
2. 循环直到到达目标状态

• 将当前状态可做的动作存为一个临时列表
• 从中随机选择一个动作，作为下一状态
• 根据公式计算新Q值
• 更新Q矩阵

最终学习结果为

得到最优路径 C->D->E->F

脚本使用方法

创造prim，将脚本附在上面。
迭代次数固定为10次，经测试可以学习出6*6矩阵的结果。
打印出最优路径。

代码及注释

list Q;
list R = [-1,-1,-1,-1,0,-1,-1,-1,-1,0,-1,100,-1,-1,-1,0,-1,-1,-1,0,0,-1,0,-1,0,-1,-1,0,-1,100,-1,0,-1,-1,0,100];
float alpha = 0.8;

// 初始化Q矩阵全零
initQ() {
integer s;
integer a;
Q = [];
for (s = 0; s < 6; s++) {
for (a = 0; a < 6; a++) {
Q = Q + [0];
}
}
}

// 打印Q矩阵
reportQ() {
integer s;
for (s = 0; s < 6; s++)
{
llOwnerSay("State " + (string)s + ": " + llDumpList2String(llList2List(Q, s * 6, s * 6 + 5), ", "));
}
}

// 获取特定状态-动作对的Q值，即Q[s,a]
integer getQ(integer s, integer a) {
return llList2Integer(Q, s * 6 + a);
}

// 获取特定状态-动作对的R值，即R[s,a]
integer getR(integer s, integer a) {
return llList2Integer(R, s * 6 + a);
}

// 获取MaxQ值
integer getMaxQ(integer s) {
integer a;
integer max = 0;
for (a = 0; a < 6; a++)
{
if(llList2Integer(Q, s * 6 + a)>max)
{
max = llList2Integer(Q, s * 6 + a);
}
}
return max;
}

// 更新特定状态-动作对的Q值
setQ(integer s, integer a, integer newQ) {
integer index = s * 6 + a;
Q = llListReplaceList(Q, [newQ], index, index);
}

// 打印结果路径
reportResult(integer s) {
integer currentS = s;
llOwnerSay((string)currentS + " -> ") ;
while(currentS!=5)
{
integer a;
integer max = 0;
integer nextS;
for (a = 0; a < 6; a++)
{
if(llList2Integer(Q, currentS * 6 + a)>max)
{
max = llList2Integer(Q, s * 6 + a);
nextS = a;
}
}
llOwnerSay((string)nextS + " -> " );
currentS = nextS;
}

}

default
{
state_entry()
{
initQ();
integer episodeCount = 10;
while(episodeCount--)
{
// 随机选择初始初始状态0~5
integer currentS = (integer)llFrand(6);
integer nextS;
integer newQ;
// 循环直到到达目标
while(currentS!=5)
{
// 随机选择当前状态可做的动作
integer a;
list actions = [];
for (a = 0; a < 6; a++)
{
if(getR(currentS,a)!=-1)
{
actions = actions + [a];
}
}
integer index = (integer)llFrand(llGetListLength(actions));
nextS = llList2Integer(actions,index);
// 根据公式
newQ = (integer)((float)getR(currentS,nextS) + alpha * (float)getMaxQ(nextS));
setQ(currentS,nextS,newQ);
currentS = nextS;
}

reportQ();
}
reportResult(2);
}
}