论文部分内容阅读
摘要：近年来，基于DFL[1]的agent学习已经受到了不少研究者的关注。文献[2]给出了一种即时回报的DF环境下的多agent学习模型，文献[3]给出DF环境下的单agent学习算法，文献[4]介绍了DF环境中agent的心智模型。本文主要是在这些文献的基础上，具体构建了一个基于DFL的非即时回报的合作型多agent学习模型。主要内容包括该模型的结构、主要数据结构，以及相应的算法，最后还给出了一个验证实例。
关键词：DFL；agent学习；Q-learning
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)03-10802-03
1 引言
本文的主要工作是在文献[1-4]的基础之上，构建一个基于DFL的合作型多agent学习模型。由于Q-learning算法需要考虑到将来的动作对当前Q值的影响，因此这里构建的多agent系统就直接使用文献[2]使用的统筹多agent学习系统的拓扑结构。而每个单agent的学习采用文献[3]中所介绍的基于DFL的Q-learning学习算法。
这里所使用的agent的内部构造比文献[2]介绍的要复杂得多。每个agent除了具有心智模型所需要的各种意向库、能力库之外，还需要一个栈和一个队列。栈主要存放本agent待处理的Q值的信息，队列则用以更新各个agent自己负责处理的Q值信息。
2 基于DFL的非及时回报合作型多agent学习模型
2.1 模型结构
非即时回报的合作型多agent学习模型结构如图1所示。
图1 非即时回报的合作型多agent学习模型图
系统存在一个统筹agent和若干普通agent。其中，统筹agent和普通agent的拓扑结构为星型结构，即所有agent之间都可以进行通信。在该系统中，除了各个agent都存在与自己心智状态相关的数据库外（比如信念库、动作库等），整个系统还存在一个公共策略库。该库主要是用来存放系统对一些环境的学习策略，以便下次碰到相同状态时可以直接调用应对策略，不用再进行学习。
统筹agent除了担任系统统筹规划外，也是整个系统对外交互的一个接口。由它跟其他agent系统进行交互，决定是否要进行学习，或者将相应的学习策略提供给需要该学习策略的其他agent系统。普通agent主要是在统筹agent的规划之下，进行新策略的学习。同时，它也定期的将系统策略库的最新策略更新到自己的策略库，以便下次学习的时候能发挥最优性能。
2.2 Agent内部主要模块
统筹agent主要负责和外界的交互和内部的统筹管理，它一般是在接收到特定消息以后才做出相应的指示。因此，它除了agent的心智状态等基本功能模块之外，还需要一个消息中断模块，功能相对比较简单。消息中断模块的主要算法见算法1。
而普通agent除了接受统筹agent的指令作出相应的动作之外，在没有接受到消息的情况下，也需要进行一些学习行为。因此，它的内部结构相对比较复杂。见图2。
心智状态模块的算法详见文献[4]。
学习模块主要是处理agent待处理任务栈中的学习任务，算法详见算法2。
消息中断模块主要处理agent接收到的消息。Agent在处理学习任务的过程中，其他agent（包括统筹agent）会把一些任务指示、学习结果等发送给它，这就需要消息中断模块在接收到相应的消息之后，做出相应的响应。算法详见算法3。
图2 普通agent的内部结构图
2.3 算法描述：
下面给出agent Manager消息中断模块的算法描述：
算法1 Agent Manager消息中断模块算法
procedure listen_message_manage(message)
if(the Q of the message doesn’t exist in the queue)
//判断队列中是否已经存在这个待处理的Q值了，如果没有，把它放入队列，//并发送给某一个agent
put it and the agent id who sends it into the queue and send it to one of the agents
else
//否则，则將发送这个Q来的agent的ID加入到队列中该Q值结点字段中
add the agent id into the queue
endif
end listen_message_manage
普通agent学习处理模块算法描述：
算法2 普通agent学习处理算法
procedure immediate_multiagent_learning(n, ,A,)
for each agent i: pardo
if(the stack is empty)
//判断栈是否是空的，如果空，跳出
break;
else
//否则弹出栈顶节点，进行处理
exceed(stack);
put the Q into the queue;
if(the Q which should be calculated can’t be calculated)
//判断这个Q值能否马上进行计算，如果不能，发送给agent Manager
send the Qs to the manage agent;
else
//如果能马上进行计算，则计算之，并把它发送给需要这个Q值的//agent
calculate the Q and send it to the agent who sends the Q;
endif
endif
endfor
end immediate_multiagent_learning
普通agent消息中断模块的算法描述：
算法3 普通agent消息中断模块算法
procedure listen_message(message)
if (the message is the Q which should be calculated)
//判断信息是否是需要计算的Q值，如果是，放入栈中
put the information of the Q into the stack;
endif
if (the message is the result of the Q which has been calculated)
//判断信息是否是计算的Q值的结果，如果是，更新队列
update the queue;
if(the updated result of the Q is the needed result)
//判断该Q值是否最终的结果，如果是，把这个Q值发送给需要这个Q
//值的agent
send it to the agent who sends the Q;
endif
endif
end immediate_multiagent_learning
2.4 算法分析
从以上算法可以看出，Q-learning算法是一种递归算法。在计算Q(( ),a)的时候，需要计算其后续动作a'的Q值。因此，如果在得到结果的过程中需要进行m次Q值计算，每次计算时间为t，那么该算法总的时间为T=t*[m/n]。
2.5 重要数据结构的定义
(1)Agent Manager队列节点数据结构：
其中：“Q(state,*)”是节点的标识；
“agent ID”是需要计算Q(state,*)的agent的标识，比如有agent 1，agent 2，agent 3需要计算Q(state,*)，那么agent ID这个字段的值就是1，2，3。
(2)普通agent队列节点数据结构：
其中：“Q(state,*)”是节点的标识；
“Q值”用以存放更新的Q值；
“Action”用以存放取得“Q值”字段值的动作；
“agent ID”是需要计算Q(state,*)的agent的标识；
“计数器”用来统计“*”所对应的所有动作数是否都计算过了；
“是否是最新的”标识了“Q值”字段是否已经得到完全更新。如果是，则该字段为“T”，否则为“F”。
(3)普通agent栈节点数据结构：
其中：“Q(state,*)”是节点的标识；
“agent ID”是需要计算Q(state,*)的agent的标识，比如有agent 1，agent 2，agent 3需要计算Q(state,*)，那么agent ID这个字段的值就是1，2，3。
2.6 应用举例
例1 如图3所示的五段图：
图3 一个五段图
假设端点1为初始状态s，端点12为目标状态t。端点2~11为各个可能出现的状态。其中权值为环境奖赏值。从初始状态s出发，通过解题过程来具体说明算法1、2和3。假设在此题的多agent系统中，一共有四个agent，分别为agent 1，agent 2，agent 3和agent 4。
(1)Agent 1到agent 4初始化自己的栈，agent Manager将Q(1,*)发送给系统中的某个agent。
(2)随机的，四个agent中一个agent接收到需要计算的Q值Q(1,*)，不妨设为agent 1接收到了。放入agent 1的栈中。
(3)Agent 1到agent 4分别从栈里弹出待处理的节点。Agent 1需要处理Q(1,*)，把Q(1,*)放入相应的队列，并把Q(2,*)，Q(2,*)，Q(4,*)，Q(5,*)发送给agent Manager。Agent Manager判断这些Q值是否已经发送给特定agent处理了，如果没有再分别发送给系统中的agent（此处不妨agent i需要处理的Q值为Q(i+1,*)，1≤i≤4)；其他agent暂时没有需要处理的节点。此时，agent 1到agent 4的四个栈中分别有Q(2,*)，Q(2,*)，Q(4,*)，Q(5,*)。
(4)Agent 1到agent 4分别从栈里弹出待处理的节点。则agent i,1≤i≤4,把需要处理的Q(i+1,*)分别放入相应的队列，并将相应需要Q值发送给agent Manager，agent Manager再统筹处理发送给各个agent。此时各个agent的队列和栈如下表所示：
表1 各个agent的栈和队列
表2 Agent Manager的队列
(5)Agent 1到agent 4分别从栈里弹出待处理的节点，并将其放入相应队列中，相应需要处理的Q值发送给agent Manager，agent Manager再统筹处理发送给各个agent。此时各个agent的队列和栈如下表所示：
表3 各个agent的栈和队列
表4 Agent Manager的队列
(6)Agent 1到agent 4分别从栈里弹出待处理的节点，并将其放入相应队列中，相应需要处理的Q值发送给agent Manager，agent Manager再统筹处理发送给各个agent。此时各个agent的队列和栈如下表所示：
表5 各个agent的栈和队列
表6Agent Manager的隊列
(7)Agent 1到agent 4分别从栈里弹出待处理的节点，并将其放入相应队列中。此时发现Q(12,*)可以马上进行计算，计算结果，并将结果发送到需要Q(12,*)的agent 1到agent 3。
(8)有了Q(12,*)，agent 1，agent 2和agent 3可以分别计算Q(9,*)，Q(10,*)和Q(11,*)，并将计算结果发送到需要它们的agent。
(9)各个agent根据当前接收到的Q值，计算Q(6,*)，Q(7,*)和Q(8,*)，并将计算结果发送到需要它们的agent。
(10)各个agent根据当前接收到的Q值，计算Q(2,*)，Q(3,*)，Q(4,*)和Q(5,*)，并将计算结果发送到需要它们的agent。
(11)agent 1计算Q(1,*)，得到结果。
(12)结束。
3 结束语
本文在作者文献[1]-[4]的基础之上，进一步完善了DF环境下的多agent学习，给出了一个基于DFL的非即时回报的多agent合作型学习模型。该模型在Q-learning算法基础之上，充分考虑到了agent学习过程中的动态模糊性特点，更具有使用价值。
参考文献：
[1] 李凡长，刘贵全，佘玉梅. 动态模糊逻辑引论[M]. 云南科技出版社，2005.
[2] Li-ping Xie, Fan-zhang Li. A Multi-agent Learning Model Based on Dynamic Fuzzy Logic, 2005 IEEE International Conference on Granular Computing, Beijing, China, 2005.7, Vol 1:310-313.
[3] Li-ping Xie, Fan-zhang Li. The Multi-agent Learning Model Based on Dyanmic Fuzzy Logic, Journal of Communication and Computer, 2006.3, Vol 3(3):87-99.
[4] Li-ping Xie, Fan-zhang Li. Agent Intelligence Model Based on Dynamic Fuzzy Logic, Journal of Computational Information Systems 2:3(2006)965-972.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：DFL；agent学习；Q-learning
中图分类号：TP301文献标识码：A文章编号：1009-3044(2007)03-10802-03
1 引言
本文的主要工作是在文献[1-4]的基础之上，构建一个基于DFL的合作型多agent学习模型。由于Q-learning算法需要考虑到将来的动作对当前Q值的影响，因此这里构建的多agent系统就直接使用文献[2]使用的统筹多agent学习系统的拓扑结构。而每个单agent的学习采用文献[3]中所介绍的基于DFL的Q-learning学习算法。
这里所使用的agent的内部构造比文献[2]介绍的要复杂得多。每个agent除了具有心智模型所需要的各种意向库、能力库之外，还需要一个栈和一个队列。栈主要存放本agent待处理的Q值的信息，队列则用以更新各个agent自己负责处理的Q值信息。
2 基于DFL的非及时回报合作型多agent学习模型
2.1 模型结构
非即时回报的合作型多agent学习模型结构如图1所示。
图1 非即时回报的合作型多agent学习模型图
系统存在一个统筹agent和若干普通agent。其中，统筹agent和普通agent的拓扑结构为星型结构，即所有agent之间都可以进行通信。在该系统中，除了各个agent都存在与自己心智状态相关的数据库外（比如信念库、动作库等），整个系统还存在一个公共策略库。该库主要是用来存放系统对一些环境的学习策略，以便下次碰到相同状态时可以直接调用应对策略，不用再进行学习。
统筹agent除了担任系统统筹规划外，也是整个系统对外交互的一个接口。由它跟其他agent系统进行交互，决定是否要进行学习，或者将相应的学习策略提供给需要该学习策略的其他agent系统。普通agent主要是在统筹agent的规划之下，进行新策略的学习。同时，它也定期的将系统策略库的最新策略更新到自己的策略库，以便下次学习的时候能发挥最优性能。
2.2 Agent内部主要模块
统筹agent主要负责和外界的交互和内部的统筹管理，它一般是在接收到特定消息以后才做出相应的指示。因此，它除了agent的心智状态等基本功能模块之外，还需要一个消息中断模块，功能相对比较简单。消息中断模块的主要算法见算法1。
而普通agent除了接受统筹agent的指令作出相应的动作之外，在没有接受到消息的情况下，也需要进行一些学习行为。因此，它的内部结构相对比较复杂。见图2。
心智状态模块的算法详见文献[4]。
学习模块主要是处理agent待处理任务栈中的学习任务，算法详见算法2。
消息中断模块主要处理agent接收到的消息。Agent在处理学习任务的过程中，其他agent（包括统筹agent）会把一些任务指示、学习结果等发送给它，这就需要消息中断模块在接收到相应的消息之后，做出相应的响应。算法详见算法3。
图2 普通agent的内部结构图
2.3 算法描述：
下面给出agent Manager消息中断模块的算法描述：
算法1 Agent Manager消息中断模块算法
procedure listen_message_manage(message)
if(the Q of the message doesn’t exist in the queue)
//判断队列中是否已经存在这个待处理的Q值了，如果没有，把它放入队列，//并发送给某一个agent
put it and the agent id who sends it into the queue and send it to one of the agents
else
//否则，则將发送这个Q来的agent的ID加入到队列中该Q值结点字段中
add the agent id into the queue
endif
end listen_message_manage
普通agent学习处理模块算法描述：
算法2 普通agent学习处理算法
procedure immediate_multiagent_learning(n, ,A,)
for each agent i: pardo
if(the stack is empty)
//判断栈是否是空的，如果空，跳出
break;
else
//否则弹出栈顶节点，进行处理
exceed(stack);
put the Q into the queue;
if(the Q which should be calculated can’t be calculated)
//判断这个Q值能否马上进行计算，如果不能，发送给agent Manager
send the Qs to the manage agent;
else
//如果能马上进行计算，则计算之，并把它发送给需要这个Q值的//agent
calculate the Q and send it to the agent who sends the Q;
endif
endif
endfor
end immediate_multiagent_learning
普通agent消息中断模块的算法描述：
算法3 普通agent消息中断模块算法
procedure listen_message(message)
if (the message is the Q which should be calculated)
//判断信息是否是需要计算的Q值，如果是，放入栈中
put the information of the Q into the stack;
endif
if (the message is the result of the Q which has been calculated)
//判断信息是否是计算的Q值的结果，如果是，更新队列
update the queue;
if(the updated result of the Q is the needed result)
//判断该Q值是否最终的结果，如果是，把这个Q值发送给需要这个Q
//值的agent
send it to the agent who sends the Q;
endif
endif
end immediate_multiagent_learning
2.4 算法分析
从以上算法可以看出，Q-learning算法是一种递归算法。在计算Q(( ),a)的时候，需要计算其后续动作a'的Q值。因此，如果在得到结果的过程中需要进行m次Q值计算，每次计算时间为t，那么该算法总的时间为T=t*[m/n]。
2.5 重要数据结构的定义
(1)Agent Manager队列节点数据结构：
其中：“Q(state,*)”是节点的标识；
“agent ID”是需要计算Q(state,*)的agent的标识，比如有agent 1，agent 2，agent 3需要计算Q(state,*)，那么agent ID这个字段的值就是1，2，3。
(2)普通agent队列节点数据结构：
其中：“Q(state,*)”是节点的标识；
“Q值”用以存放更新的Q值；
“Action”用以存放取得“Q值”字段值的动作；
“agent ID”是需要计算Q(state,*)的agent的标识；
“计数器”用来统计“*”所对应的所有动作数是否都计算过了；
“是否是最新的”标识了“Q值”字段是否已经得到完全更新。如果是，则该字段为“T”，否则为“F”。
(3)普通agent栈节点数据结构：
其中：“Q(state,*)”是节点的标识；
“agent ID”是需要计算Q(state,*)的agent的标识，比如有agent 1，agent 2，agent 3需要计算Q(state,*)，那么agent ID这个字段的值就是1，2，3。
2.6 应用举例
例1 如图3所示的五段图：
图3 一个五段图
假设端点1为初始状态s，端点12为目标状态t。端点2~11为各个可能出现的状态。其中权值为环境奖赏值。从初始状态s出发，通过解题过程来具体说明算法1、2和3。假设在此题的多agent系统中，一共有四个agent，分别为agent 1，agent 2，agent 3和agent 4。
(1)Agent 1到agent 4初始化自己的栈，agent Manager将Q(1,*)发送给系统中的某个agent。
(2)随机的，四个agent中一个agent接收到需要计算的Q值Q(1,*)，不妨设为agent 1接收到了。放入agent 1的栈中。
(3)Agent 1到agent 4分别从栈里弹出待处理的节点。Agent 1需要处理Q(1,*)，把Q(1,*)放入相应的队列，并把Q(2,*)，Q(2,*)，Q(4,*)，Q(5,*)发送给agent Manager。Agent Manager判断这些Q值是否已经发送给特定agent处理了，如果没有再分别发送给系统中的agent（此处不妨agent i需要处理的Q值为Q(i+1,*)，1≤i≤4)；其他agent暂时没有需要处理的节点。此时，agent 1到agent 4的四个栈中分别有Q(2,*)，Q(2,*)，Q(4,*)，Q(5,*)。
(4)Agent 1到agent 4分别从栈里弹出待处理的节点。则agent i,1≤i≤4,把需要处理的Q(i+1,*)分别放入相应的队列，并将相应需要Q值发送给agent Manager，agent Manager再统筹处理发送给各个agent。此时各个agent的队列和栈如下表所示：
表1 各个agent的栈和队列
表2 Agent Manager的队列
(5)Agent 1到agent 4分别从栈里弹出待处理的节点，并将其放入相应队列中，相应需要处理的Q值发送给agent Manager，agent Manager再统筹处理发送给各个agent。此时各个agent的队列和栈如下表所示：
表3 各个agent的栈和队列
表4 Agent Manager的队列
(6)Agent 1到agent 4分别从栈里弹出待处理的节点，并将其放入相应队列中，相应需要处理的Q值发送给agent Manager，agent Manager再统筹处理发送给各个agent。此时各个agent的队列和栈如下表所示：
表5 各个agent的栈和队列
表6Agent Manager的隊列
(7)Agent 1到agent 4分别从栈里弹出待处理的节点，并将其放入相应队列中。此时发现Q(12,*)可以马上进行计算，计算结果，并将结果发送到需要Q(12,*)的agent 1到agent 3。
(8)有了Q(12,*)，agent 1，agent 2和agent 3可以分别计算Q(9,*)，Q(10,*)和Q(11,*)，并将计算结果发送到需要它们的agent。
(9)各个agent根据当前接收到的Q值，计算Q(6,*)，Q(7,*)和Q(8,*)，并将计算结果发送到需要它们的agent。
(10)各个agent根据当前接收到的Q值，计算Q(2,*)，Q(3,*)，Q(4,*)和Q(5,*)，并将计算结果发送到需要它们的agent。
(11)agent 1计算Q(1,*)，得到结果。
(12)结束。
3 结束语
本文在作者文献[1]-[4]的基础之上，进一步完善了DF环境下的多agent学习，给出了一个基于DFL的非即时回报的多agent合作型学习模型。该模型在Q-learning算法基础之上，充分考虑到了agent学习过程中的动态模糊性特点，更具有使用价值。
参考文献：
[1] 李凡长，刘贵全，佘玉梅. 动态模糊逻辑引论[M]. 云南科技出版社，2005.
[2] Li-ping Xie, Fan-zhang Li. A Multi-agent Learning Model Based on Dynamic Fuzzy Logic, 2005 IEEE International Conference on Granular Computing, Beijing, China, 2005.7, Vol 1:310-313.
[3] Li-ping Xie, Fan-zhang Li. The Multi-agent Learning Model Based on Dyanmic Fuzzy Logic, Journal of Communication and Computer, 2006.3, Vol 3(3):87-99.
[4] Li-ping Xie, Fan-zhang Li. Agent Intelligence Model Based on Dynamic Fuzzy Logic, Journal of Computational Information Systems 2:3(2006)965-972.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。