基于模型的值迭代算法

发表于 | 分类于

MDP模型

一个扫地机械人的模型如下

确定情况的清洁机械人MDP

状态空间：X={0,1,2,3,4,5}，其中：状态0和5为终止状态。

动作空间：U={-1,1}。

迁移函数：

奖赏函数：

确定情况下基于模型的值迭代算法

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
# -*- coding: UTF-8 -*-

import operator

xs = [0,1,2,3,4,5]
us = [-1,+1]
r = 0.5  #折扣因子
Q = []   #使用列表，字典的嵌套来存储数据
hs = []  #使用列表存储值迭代的 h*
vs = []  #使用列表存储值迭代的 V*

#状态转移函数
def f(x,u):
	if x >= 1 and x <= 4:
		return x + u
	elif x == 0 or x == 5:
		return x

#奖赏函数
def reward(x,u):
	if x == 4 and u == 1:
		return 5
	elif x == 1 and u == -1:
		return 1
	else:
		return 0


# #确定性情况下值迭代算法（同步算法）
# def value_Interation():
# 	#初始化Q[0]
# 	Q.append({})
# 	for x in xs:
# 		for u in us:
# 			Q[0][(x,u)] = 0.0
# 	n = 0

# 	while True:
# 		Q.append({})
# 		n += 1
# 		for x in xs:
# 			for u in us:
# 				Q[n][(x,u)] = reward(x,u) + r * max(Q[n-1][(f(x,u),-1)],Q[n-1][(f(x,u),1)])
# 		if operator.eq(Q[n],Q[n-1]):
# 			break


#确定性情况下值迭代算法（异步算法）
def value_Interation():
	#初始化Q[0]
	Q.append({})
	for x in xs:
		for u in us:
			Q[0][(x,u)] = 0.0
	n = 0

	while True:
		Q.append({})
		n += 1
		for x in xs:
			for u in us:
				if x == 0 or x == 5:
					# 由状态转移函数得x==0与x==5时下一状态仍是x，使用的值是Q[n-1]的
					temp = max(Q[n-1][(f(x,u),-1)],Q[n-1][(f(x,u),1)])
				#异步算法需要区分u==-1与u==1的情况，u==-1时使用Q[n]的值，u==1是使用Q[n-1]的值
				elif u == 1:
					temp = max(Q[n-1][(f(x,u),-1)],Q[n-1][(f(x,u),1)])
				elif u == -1:
					temp = max(Q[n][(f(x,u),-1)],Q[n][(f(x,u),1)])
				Q[n][(x,u)] = reward(x,u) + r * temp
		if operator.eq(Q[n],Q[n-1]):
			break

	for x in xs:
		d = Q[n][(x,-1)]-Q[n][(x,1)]
		if d < 0:
			hs.append(1)
			vs.append(Q[n][(x,1)])
		elif d > 0:
			hs.append(-1)
			vs.append(Q[n][(x,-1)])
		else:
			hs.append('*')
			vs.append(Q[n][(x,-1)])


value_Interation()
n = 0
for q in Q:
	print('Q' + str(n))
	print(q)
	n += 1
print('------------------------------------------------------------------------------------')
print('路径选择：',hs)
print('值：',vs)

随机情况的清洁机械人MDP

随机情况下状态空间和动作空间与确定情况下的一样，主要是迁移函数和奖赏函数的不同，这里不在给出，在代码实现中体现。

随机情况下基于模型的值迭代算法

代码实现（异步版本）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
# -*- coding: UTF-8 -*-

import operator

xs = [0,1,2,3,4,5]
us = [-1,1]
r = 0.5  #折扣因子
Q = []   #使用列表，字典的嵌套来存储数据
hs = []  #使用列表存储值迭代的 h*
vs = []  #使用列表存储值迭代的 V*

#随机情况下转移的概率函数
def p(x,u,y):  # x是开始的状态，u是采取的动作，y是最后到达的状态
	#先检查初始状态是0和5的情况
	if x == 0:
		if y == 0:
			return 1
		else:
			return 0
	elif x == 5:
		if y == 5:
			return 1
		else:
			return 0
	t = y - x
	if t == 0:
		return 0.15  #停在原地的机率是0.15
	elif t == u:
		return 0.8  #按预期方向行动的机率是0.8
	elif t == -u:
		return 0.05  #按与预期方向相反的方向行动的机率是0.05
	else:
		return 0

#随机情况的奖赏函数
def reward(x,u,y):  # x是开始的状态，u是采取的动作，y是最后到达的状态
	if x == 4 and y == 5:
		return 5
	elif x == 1 and y == 0:
		return 1
	else:
		return 0

#随机情况下值迭代算法（异步算法）
def value_Interation():
	#初始化Q[0]
	Q.append({})
	for x in xs:
		for u in us:
			Q[0][(x,u)] = 0.0
	n = 0

	while True:
		Q.append({})
		n += 1
		for x in xs:
			for u in us:
				Q[n][(x,u)] = 0
				for y in xs:
					if y > x:
						# y > x 时使用Q[n-1]的值
						Q[n][(x,u)] += p(x,u,y)*(reward(x,u,y) + r * max(Q[n-1][(y,-1)],Q[n-1][(y,1)]))
					elif y < x:
						# y < x 时异步算法使用的是Q[n]的值
						Q[n][(x,u)] += p(x,u,y)*(reward(x,u,y) + r * max(Q[n][(y,-1)],Q[n][(y,1)]))
					elif y == x:
						# 若 y == x 需区分 u 的情况
						if u == -1:
							Q[n][(x,u)] += p(x,u,y)*(reward(x,u,y) + r * max(Q[n-1][(y,-1)],Q[n-1][(y,1)]))
						elif u == 1:
							Q[n][(x,u)] += p(x,u,y)*(reward(x,u,y) + r * max(Q[n][(y,-1)],Q[n-1][(y,1)]))
				Q[n][(x,u)] = round(Q[n][(x,u)],3)
		if operator.eq(Q[n],Q[n-1]):
			break

	for x in xs:
		d = Q[n][(x,-1)]-Q[n][(x,1)]
		if d < 0:
			hs.append(1)
			vs.append(Q[n][(x,1)])
		elif d > 0:
			hs.append(-1)
			vs.append(Q[n][(x,-1)])
		else:
			hs.append('*')
			vs.append(Q[n][(x,-1)])


value_Interation()
n = 0
for q in Q:
	print('Q' + str(n))
	print(q)
	n += 1
print('------------------------------------------------------------------------------------')
print('路径选择：',end='')
print(hs)
print('值：',end='')
print(vs)

note

  • python 3.x 的版本已经没有 cmp() 函数，在进行列表、字典的比较时引入operator模块。operator模块使用与任何对象。

  • python中实现一个do-while循环：

    1
    2
    3
    4
    while True:
        stuff()
        if fail_condition:
            break

    or

    1
    2
    3
    stuff()
    while not fail_condition:
        stuff()

  • 一个小tip：编写for循环时，对于用于存储列表中每个值的临时变量，可指定任何名称。然而，选择描述单个列表元素的有意义的名称大有帮助。例如，对于小猫列表、小狗列表和一般性列表，像下面这样编写for循环的第一行代码是不错的选择:

    1
    2
    3
    for cat in cats:
    for dog in dogs:
    for item in list_of_items:

    这些命名约定有助于你明白for循环中将对每个元素执行的操作。使用单数和复数式名称，可帮助你判断代码段处理的是单个列表元素还是整个列表。

​
​
​

​
​
​