о뷢չ
JOURNAL OF COMPUTER RESEARCH
AND DEVELOPMENT
1999 36 12 Vol.36 No.12 1999



Q-ѧϰܻ˾ֲ·
滮еӦо
겨˹Źӡ
ժҪǿѧϰһΪѧѧưΪѧϰɷḶ́Ӷѻ״̬ӳӦĶ.ܻ˹УʵΪ˼롢뻷ĽѧϰΪаѻδ֪ΪϰȡĶһΪǿѧϰʵܻ˱Ϊѧϰ.Q-ѧϰ㷨ڶ̬滮һǿѧϰڽQ-ѧϰĻ㷨֮˾о˼֯ƵQ-ѧϰѧϰ㷨Ȼо˸㷨ܻ˾ֲ·滮еӦãеϸķ.
ؼʡQ-ѧϰ磬ܻˣֲ·滮
ͼšTP242.6
Q-LEARNING AND ITS APPLICATION IN LOCAL PATH
PLANNING OF INTELLIGENT ROBOTS
ZHANG Ru-Bo, YANG Guang-Ming, GU Guo-Chang, and ZHANG Guo-Yin
(Department of Computer and Information Science,
Harbin Engineering University, Harbin 150001)
AbstractThe concept of reinforcement learning comes from behavior psychology that takes behavior learning as trial and error, by which the states of environment are mapped into corresponding actions. There's a question of how the behaviorism can be used to learn the actions in interaction with the environment in designing intelligent robots. In this paper, the actions that a robot takes to avoid obstacles are taken as one class of behaviors and the reinforcement learning is used to realize behavior learning of obstacle avoidance. Q-learning is one kind of reinforcement learning method that is similar to dynamic programming. After basic ideas of Q-learning are introduced, a neural network learning algorithm of Q-learning with concepts of competition and self-organization is presented. Its application in local path planning of intelligent robots is also introduced. Finally, the detailed simulation results are presented.
Key wordsQ-learning, neural network, intelligent robot, local path plan
1
ѧϰУѧϰ㷨ϿԷΪ3ͣǼලѧϰ(unsupervised learning)ලѧϰ(supervised learning)ǿѧϰ(reinforcement learning).
ǼලѧϰѧϾPavlovԭһĴ̼źţͬʱһ̼źţʳӸʱ򣬾һʱѵ󣬶ͻὨһ.ٽ̼ܵźʱͻ.͵ѧϰȫǿģѧϰУ֮Ϊع򣬼еHebbѧϰ.
ලѧϰһַѧϰ򣬵źϵͳ󣬹۲ɽʦṩźţźŷϵͳָѧϰѧϰУ֮ΪСѧϰ֮ΪĹ1.
۲رˣΪӦѧϰ̿Էص㣬һ˴ǾֹرȴԻ̽Ǵӻ̽ͨķźſԣ򷣣ģලѧϰȷ.ж۵Ļл֪ʶĽжӦﵽԤĿ.صѧϰǿѧϰѧϰѧϰΪRL2.
Q-ѧϰ㷨Watkins1989ڶ̬滮㷨һǿѧϰ.ṩϵͳƷ򻷾þĶѡŶһѧϰҲҪģ.Q-ѧϰ㷨ʵMDPMarkov decision processesһֱ仯ʽ.Watkinslookupʾ״̬֤Q-ѧϰԣ3.Szepesvriһ֤Q-ѧϰٶȣ4.Williams˲Q-ѧϰ㷨ԵϵͳʵоAnderson˲AHC˱ȽϷ5.ԣǿѧϰ㷺Ӧܿѧ߶ȡĳɹ.Beomģ߼ǿѧϰʵ½ƶ˵ϵͳͨѧϰܹδ֪Ļ˶ɱ͵ָĿΪ6. Winfriedǿѧϰʹѧ6ȵЭ7.Carnegie MellonѧSebastianǿѧϰʽʹͨѧϰܹڻеĿ1.
ڽQ-ѧϰĻ㷨֮˾о˼֯ƵQ-ѧϰѧϰ㷨Ȼо˸㷨ܻ˾ֲ·滮еӦѻδ֪ΪϰȡĶһΪQ-ѧϰƽл˵ıΪѧϰеϸķ.
2Q-ѧϰĻ㷨3
軷һ״̬ɢƷ̣ϵͳÿ޶ѡȡĳһܸö״̬תƣͬʱr.磬ʱtѡat״̬stתƵst+1rtrtst+1ĸʷֲȡatst.״̬¸ʱ仯st+1
probs=ss+1/st,at=Pst,at,st+1
(1)
ϵͳٵǾһŲԣʹܵۿ۽źֵ.ڲԦе£״̬sֵΪ

(2)
ϵͳϣյǿźr((x))ȻԸƶһֵΪV(st+1)һ״̬.̬滮۱֤һԦЪʹ

(3)
Q-ѧϰٵڳʼδ֪.WatkinsQ-ѧϰһʽ̬滮һʽ.ϣҵһԣУʹܺ͵õ.ģͣ״̬תƸʼģ֪ͣɹ۲Ƴö̬滮DPQ-ѧϰ˼ǲȥƻģֱͣŻһɵQWatkinsQΪ״̬stʱִжatҴ˺Ŷִʱۿۼǿֵ

(4)
Q-ѧϰУϵͳľһϵвͬĽ׶Σÿ׶Σѧϰ£
(1)۲ڵ״̬st;
(2)ѡִһat;
(3)۲һ״̬st+1;
(4)յһǿźrt;
(5)Qֵ

(5)
:

(6)
ڳʼ׶ѧϰУQǲ׼ȷطӳĲԣʼֵQ0(s,a)е״̬ͶٶǸ.Watkins֤Q-ѧϰһµ.ǣ
(1)Ʒ̣
(2)lookupʾQ
(3)ÿ״̬-ԣ޴εظ飻
(4)ѧϰʵȷѡ.
1.нǿź|rt|Rѧϰ0ܦt1

(7)
򣺵tʱQt(s,a)Ը1Q(s,a).
QʵַҪַʽһǲ緽һǲlookup񷽷lookup񷽷ҲñʾQQs,asSaAΪһlookupSAΪ޼.Q(s,a)s״ִ̬жaQֵ.ĴСSAĵѿ˻Ԫصĸ.״̬SϵͳܵĶAϴʱQ(s,a)Ҫռôڴռ䣬Ҳз.
ʵQ-ѧϰʱӦÿQֵӦ״̬.ʵQ-ѧϰ󣬿Կ˷ڵ.
3Q-ѧϰʵ
3.1Q-ѧϰϵͳĽṹ
Q-ѧϰϵͳṹͬAHC㷨ĽṹQ-ѧϰϵͳֻһߵԪͬʱ𵽶ۼѡãṹͼ1ʾ.

ͼ1Q-ѧϰϵͳṹ

һϵͳҪȡϸߵǿֵÿ״̬ϵͳòѡQֵĶرѧϰĳʼ׶Σ״̬ľ˽ıȽ٣Qֵ׼ȷرʾȷǿֵ.ͨѡQֵĶϵͳͬ·̽Ϻֵ.ˣϵͳѡݵǰQֵҲѡĶŵ.෽ѡ.Boltzmannֲ

(8)
TΪ¶ֵTĴСԵĴС.TԽԽ.ѧϰĳԽ׶ΣTȡϸߵֵΪʱѧϰľСҪѧϰĹУ𽥽¶ȣ֤ǰѧϰЧƻ.
Q-ѧϰøʵ֣ÿһӦһQֵQ(s,ai).ʵQ-ѧϰĹؼѧϰ㷨ȷ.QĶ壺

(9)
ֻڵõŲԵǰʽų.ѧϰ׶ʽ߲źΪ

(10)
УQ(st+1,at)ʾһ״̬ӦQֵЦQͨȨֵʹСһЩ.
3.2ۺQ-ѧϰ㷨
ǽϾ֯ӳ˼ʵQ-ѧϰ㷨.Ľṹͼ2ʾ

ͼ2ۺ
3ɣ㡢м㡢(֯).صҪھ֯.ڵӦһϵеĶ״ֵ̬Q(S,aj).Զһ˳Уaiai-1Ķ.乤ԭģ״̬St={s1,s2,,sn}ʱ򴫲ӦQ(S,aj)ѡԪQ(S,aj)ֵѡȡ.趯aiѡУQ-ѧϰУ

(11)
Уݾ˼Qmax=1.
⣬aiѡкڵĶҲһȨֵĵ.֯ӳ˼룬ͬһӦжӦֻӦĳ̶Ȳͬѣǲֲ̬ʽȷڶķӦǿȣ

(12)
ڵӦһϵе෴a1ama2am-1ȶ໥ĶԪѡȡһaiΪQmax෴Ķam-iΪ-Qmax.am-iڵĶӦʽ޸ģ

(13)
ÿѧϰʱͲڵֵ.Ŀ꺯

(14)
򴫲㷨Ȩֵ.
4Q-ѧϰܻ˾ֲ·滮еӦо
4.1ǿֵȷ
ǿźŵǶѧϰϵͳܵһۣҪڸϵͳ.ǿźŸݿĲͬʽͬ.ڻ˱ΪѧϰУĿʹϰԽԶԽ.ϰʱӦõõͷ.оĻУ6ڱͼ3ʾ.ӦۺϿ6ɵľϢе̽Զе̽Ͻ.

ͼ3ϰĹϵ
ǲƳȷⲿǿֵ.ȼܳĺ

(15)
kiΪϵiΪiɵ̽룻0Ϊȫ룬miΪɵ̽룻iΪi뻷ϵļн.˻˾ϰۺλùϵ.ϴϰϽ֮Զ.ʱ̵֮Ϊ

(16)
˶.F(t)0ԶϰӦõõF(t)0ʾ߽ϰõõͷ.ǿźr(t)Ϊ
r(t)=gۦF(t)
(17)
g(x)ȡΪ

(18)
ʵУki={2,2,2,2,1,1};0i={1.5,1.5,1.5,1.5,1.0,1.0};mi={4.5,4.5,4.5,4.5,1.5,1.5}
⣬ϰʱr(t)=-1.
4.2롢ıʾʽ
оĻϵͳУҪǱ.ˣΪǿѧϰϵͳźž6ɴľϢϢǻ4ȼDangerNearMiddleFarǰɻ£

(19)
ڲɣ

(20)
ѻ˵תǶȻΪ7ɢ0,10,20,30.˸ݴϢѧϰѡʶ.
a1=-30,a2=-20,a3=-10,a4=0,a5=10,a6=20,a7=30
Уa1a7a2a6a3a5Ϊ.Ϊʹ˾ѧϰûڱȽϸӵĻηʽ˶ϰʱص¿ʼѧϰϴѧϰĻ½Ȩֵĵ.û·ѧϰЧĺûߵ·Խ˱Խǿ.
4.3Q-ѧϰĻ˱ʵ
Q-ѧϰĻ˱ѧϰϵͳ3ʵ.Ϊ6ڵ㣬Ϊ7ڵ㣬мѡ16ڵ.УתǶΪģΪԳƵĶ.ÿѧϰʱѡBorlzmannֲѡȡһ.Ϊ˷Ĺ۲˵ѧϰЧǲ˶ԶͳƷߣʵͼ4ʾ.

ͼ4ʵ
ۺQ-ѧϰ㷨ʵߣѧϰٶߣƽ·ԶԶڱ׼Q-ѧϰ㷨ߣ.ϿԿñ׼Q-ѧϰѧϰʱȽϳûдﵽȶЧ.ͼ5Ϊ㷨ѧϰԵѧϰ켣.켣ȽңƽͷӬײ.ͼ6ΪһʱѧϰĹ켣켣Ƚƽ.

ͼ5ѧϰʼ׶ε˶켣

ͼ6˾һʱѧϰ˶켣
Ϊ˽һѧϰЧѵõĻһΣѧϰͼ7ΪεĽ.ǵֲ·滮⣬ûҵĻеָĿ㣬Ľͼ8ʾ.

ͼ7Թ˶ķ

ͼ8Q-ѧϰľֲ·滮
ӷԿQ-ѧϰƵĻ˾ѧϰڱȽϸӵĻ˶ͬʱʵ־ֲ·滮.
5ᡡ
˾о˼֯ƵQ-ѧϰѧϰ㷨׼Q-ѧϰȣѧϰٶȴ.ø㷨ĻͨѧϰнǿıӶ˻˶ԻӦ.㷨ͬӦõܿϵͳ.
߼飺겨У19633ڣʿҪоΪѧϰܿƼ
ܻ.
У19743˶ʿоҪоΪѧϰܻ.
˹У19464ʿʦҪоΪܻˡϵ
ṹжߺͿƼ.
ŹӡУ19629ʿڣҪоΪܿƼܻ.
ߵλ̴ѧϵ150001
ο
1Sebastian T, Mitchell T M. Lifelong robot learning. Robotics and Autonomous System, 1995, 15: 2546
2ƽ. ѧϰԭ㷨ܿеӦ. Ϣ, 1996, 25(1): 2834
Yan Pingfan. Reinforcement learningprinciple, algorithm and its application in intelligent control. Information and Control(in Chinese), 1996, 25(1): 2834
3Watkins J C H, Dayan P. Q-learning. Machine Learning1992, 8: 279292
4Szepesvri C. The asymptotic convergence-rate of Q-learning. In: Proceedings of Neural Information Processing Systems. Cambridge, MA: MIT Press, 1997. 10641070
5Williams R J. Simple statistical gradient-following algorithms for connectionist. Machine Learning, 1992, 8 229256
6Beom H B. A sensor-based navigation for a mobile robot using fuzzy logic and reinforcement learning. IEEE Trans on SMC, 1995, 25(3): 464477
7Winfried I, Karsten B. A learning architecture based on adaptive control of the walking machine LAURON. Robotics and Autonomous System1995, 15 323334
ԭյڣ1999-03-10޸ĸյڣ1999-08-26
