ISSN 1000-0054
CN
11-2223/N
清华大学学报 (自然科学版)
J T singhua U niv (Sci& T ech),
2005 年 第 45 卷 第 10 期
2005, V ol.45, N o.10
30/36
1413-1416
M
-
POMDP
模型及其划分求解算法
张新良, 石纯一
(清华大学 计算机科学与技术系, 北京 100084)
收稿日期: 2004-09-24
基金项目: 国家自然科学基金资助项目 (60496323, 60373079)
作者简介: 张新良 (1978-), 男( 汉), 山 东, 博士 研 究生。
通讯联系人: 石纯一, 教授, E -m ail: scy@ tsinghua.edu.cn
摘 要: 针对多
M
-
PO M DP
问题(多
A gent
部分可观察
M arkov 决策问题)中存在的动作空间搜索量随 A gent个数
呈指数倍增长的问题,该文给出了一种基于
Agent
依赖关系
的划分算法,在满足收益可分解的条件下,将
A gent
集合按
动作依赖关系分为几组。在固定了一些 A gent的策略后,剩
下的 A gent只依赖于自己组内的 A gent的动作,从而变为一
个比较独立的决策问题,降低求解问题的复杂度。通过实验,
证明了这种方法可以减少
A gent
搜索空间,从而提高求解
效率。
关键词: 多
A gent
系统; 可观察决策问题; 划分算法
中图分类号:TP181 文献标识码:A
文章编号: 1000-0054(2005)10-1413-04
Div iding alg orithm for M -POMDP mode l
ZHANG Xinliang
,
S HI Chunyi
(
Department of Compute r S c i enc e and Tec h nol ogy
,
Tsinghua University
,
Beijing 100084
,
China
)
Abstract
: In the M -PO M D P (m ulti-agentpartialobservable M arkov
decision process) of a m u lti-agent system , the search space grow s
exponentially as the num ber of agents increases. T his p aper gives a
m ethod based on th e in ter dependence of actions that divides the
m ulti-agen t system into several g roups. A fter som e of the agent
strategies are fixed, the rem aining agent strategies only depend on
the agents in their ow n group. Experim ents show that the m ethod
can reduce the search space size, w hich im p ro ves the solving
efficiency.
Key words
: m ulti-agent system (M A S ); partial observation
decision process; d ividing algorithm
Markov
决策过程(
MDP
)是用来描 述
A gent
决
策的常见模型。多 A gent M arkov 决策过程可看作
多个
Agent
决策的
Markov
模型。在通常情况下,
A gent 用来决策的信息是不完全的,而不完全信息
情况下的
Agent
决策过程模型是
PO M D P
。在 决 策
模型中,需要定义 A gent 收益函数
V
(
s
)。在文[1
3]中提出,
V
(
s
)分为有限
T
步收益和无穷折扣收
益类型,相应的有动态规划、值迭代或者策略迭代的
办法等。对于信息不完全问题,定义状态信息函数或
者信念函数
b
(
s
)(文[4]),
b
(
s
)是 A gent 对当前所
处状态的一种概率分布,
PO M DP
可看作是状态空
间为
b
(
s
)(而不是
s
)的完全信息 M D P 问题,但其状
态空间是连续分布的,而不是离散分布的。相应的动
态规划方法也不能直接应用。在文[3]等文献中提出
了
Witness
算法,
Vector
剪枝算法,基于
Q
-学 习 的
逼近算法等。但在多 A gent 环境下,随着 A gent 数
目的增加,
Agent
联合动作空间也呈指数倍增长。
文[4]采用固定其他
n
- 1个Agent的策略,则M -
POM DP
问题变为针对
Agent
i
的
POM DP
问题,
然后循环调整
n
个 A gent的策略。但调整次数很难
保证,不能保证求解的效果。文[5]基于以下原理,对
于
n
个 A gent决策问题
M
, 如果 A gent
m
≤
i
≤
n
选
择的策略是最优的,那么求解其他
A gent
M
′问题的
策略所得的策略加上
m
≤
i
≤
n
的策略就是针对
M
的最优策略。
Agent
之间采用通信的办法,
Agent
i
可以知道其他 A gent的
b
j
(
s
), 从而推断其他 A gent
可能采取的动作。然后将
n
个
Agent
分为两组各
n
/2 个 A gent, 固定其中一组 A gent, 来求得另外一
组
Agent
的策略。这样循环下去,可证明这种循环
迭代的算法是收敛的。如果仍采用文[1]或[3]的动
态规划或值迭代的方法,需要搜索所有的联合动作
空间,其效率比较低。
本文主要是针对多
Agent
情况下,联合动作空
间随着 A gent 数目增加而指数增加的问题,在收益
可分解的条件下,给出了一种基于
Agent
之间动作
划分的办法。通过划分将 A gent 划分为几个简单的
相对比较独立的决策问题。然后对固定策略的
A gent 的联合动作空间搜索,从而求得收益函数。并
资源评论
