ѧ
JOURNAL OF SOFTWARE
1999 1 No.1 1999



ʵʱµ* 
¡š 
ժҪʵʱµǽ滮оȤĻ.˴ͳ滮㷨Ĳ֮,ʵʱķʱ㷨.ʱ㷨ԺʱԴ,֤ϵͳѵܣͬʱ,ʱ㷨ʱж,ʱſн.Ŵ㷨ʱ㷨,ڽͬ㷨Ĳ֮ͬ,ͨʵó֪ʶָϵķ,ԽϺõشʵʱ滮.,Ҽ򵥵ʵʱ滮㷨Ĳ,ͬʱ˽ķչ.
ؼʡ滮,ʱ㷨,Ŵ㷨,.
ͼšTP18
Real-Time Problem Solving 
CHEN ZhengZHANG Bo 
AbstractReal-time problem solving is an interesting topic in planning in recent years. Besides discussing the deficiency of traditional planning algorithm, the authors imported the anytime algorithm, which can solve the real-time problems in this thesis. Anytime algorithm could allocate time resource reasonably to ensure the best system output performance. Anytime algorithm could be interrupted at any time and output the relatively best probable solution in that time. Genetic algorithm has the properties of the anytime algorithm. After introducing the differences between this and other search algorithms, through the experiments, the authors found that the method, which combines the random search technology and knowledge based method, could solve real-time planning problems relatively better that other methods. At last, the authors gave out the conclusion, discussed the policy of real-time planning problem solving algorithm simply, and discussed the possible developments in the future.
Key wordsPlanning, anytime algorithm, genetic algorithm, operator.
ͳĹ滮ǴӾΪ֮һӳ,Ϊ绷ı仯С,ͬʱ绷ڹ滮ϵͳ˵ȫԤ֪һϵͳ.GPSgeneral problem solve˵Ĺ滮ϵͳ,GPSԹ滮һЩ,滮ɶɵ,滮ΪǿԤԵ,ּǳΪͳ滮Classical Planning.Ȼв˶ּ,ȷʵܽ.1
ļȻܹһЩ滮,Ǵֻ߹滮˴ױġȫ֪Ļʱ,벻ϵظ֪Χ,ӦķӦ.,Ȼٰѻ˵ΪΪǿԤ֪Ķ.˳˲ٿǻϵͳӰ߹滮㷨,磺Agre  Chapman2,GeorgeffLansky3,Rosenscheinkaelbling4,SanbornHendler5,Schoppers6,Firby7ݵȵ.Щ򵥻,ͿΪڽĴ̼(Stimulus)ķӦ(Response).1
ͳ滮Ϊһ滮㹻ʱѰѽ.,ʱһʵ̫Ļ,Ӧѡҵѽǰ,õÿʱ̵ľֲŽ.Ҫʱֹ滮㷨,ҸʱŽ,ص㷨ǳΪʱ㷨(Anytime Algorithm).8
,ڹ滮оһ,ѴͳĹ滮ĳӦ(Ҳܹ̬ͻ¼),ˡֲ滮㷨,Խ˵Ĺ滮.
1 ʱ㷨
ʱ㷨ҪоڸʱζһЩ¼õӦ.ʵĹ滮,źܶԴ,ʱԴӲԴȵ,ڸԴڶϵͳѵĹ滮Ϊ滮оĹؼ.,ʵĹ滮⴦ױĻ,Ҫ㷨ܹӦı仯.
˺ܶʵʱķ,ʱ㷨нͻص.һ,ͬʱһʱԴ,ʱ㷨ܵ.ͨ͡ʱԼ,ԵõһԤԵ㷨ģ,ģ,԰㷨ֵҪʱԴ,̵ʱڸ.ʱ㷨ĽܹϺõӦⲿԼڲĲȷ,ʵʱ滮Ҫ.
ÿҪӦʱc,Ǽ˶cκӦһ,ÿǶһЩʱ,صӦõĽš.ǶǴCӳ,,ÿcCʵ,(c,)=űʾڸʱڶcõӦǦ,˶ԸʱĹ滮ʱ,ǸȤϵĹutility(c,(c,)),ǶԸʱһ.
,ǽ5ͺʱصĹ滮㷨.(x,y)=utilit
(x,(x,y)).8
(1) :cC,,šR+,(c,)ܦ(c,+);
(2) Ծ(ͼ1(a)ʾ):cC,r,kR+,;
(3) ޱ߽(ͼ1(b)ʾ):cC,ˡR+,(c,)=*;
(4) б߽(ͼ1(c)ʾ):cC,r,ˡR+,;
(5) ٶ(ͼ1(d)ʾ):cC,f,̡(c,t)=f(t),fǵ,x,yR+,f(x)f(y),xy(f(y)f(x)).
 
ͼ1 
滮ϵͳϵ2,ṩʱ,ЩϵͳҪ̶ʱͬ,ʱ϶,Ҳ滮ʲôҲ.ʱ䲻,ô,ϵͳִȱʡĶ.滮¼ԤĻ,߹滮Ҫʱܶ,ô,2ַԵõϺõĽ.34ַǵ5ַ,ʵӦнϺõ,ŸʱӶŵĹ滮.
ʱ㷨ص:(1) ǿʱж,Ҫӵĸ;(2) ǿʱж,һЩ;(3) صĽʱ,Ҳڸ. 
(2)(3)صʹͬͳĹ滮㷨,Ϊ,ǳ֮Ϊʱ㷨(Anytime Algorithms).8
2 Ŵ㷨GA
ͨѿ,ʱ㷨صṩԴ,ʹ㷨Ӧʵʻ,Ҫʱ̿ʱŽ.ʱ㷨ԲŻ㷨Ľ,ʹʱӶԶԸϵͳطԴ,ﵽϵͳ.,ʱ㷨ʵʱ㷨һ,ڸʵʱ,Ƕڲͬʵ,Ҫʱ㷨ָ²ӦĽ.ڹ滮ʵʱ㷨,Ƕѭʱ㷨Ŀ,СŴ㷨˵нͻص.
2.1 Ŵ㷨
Ŵ㷨һֻȻѡȻŴѧƵ.ͨȻѡеġʤ̭ĲÿһЩµĴṹ,̭ϲĽṹ,ʺϵĽṹԱ,ÿζнһ.,ʹŴ㷨ͬͳ,ֲ,ΪЧʷϢ,ʹÿжõķǰ.
ͳŴ㷨Ƚ,ǵġ³ԡ.ͳ㷨ֻĳЩضĻ,仯,㷨ͲܺܺõӦ仯Ž⣻Ŵ㷨,,ʹκθӻ,ܹͨŻĽƽŽ.ڽŴ㷨ǰ,ͳ㷨ص.
ͳ㷨ϿԷΪ3ࣺ9
(1) ΢ָ.̾Ƕռ΢,䵼Ϊ0ĵ,Hillɽֲֵ.ַ㷺ೡ,,ռдڶֵʱ,ͲܺܺõҳռŽ,ֻҵֲŽѰµʼ,ʼµ.
(2) öٷ.ַʺռ޵ɢݼ,ȱЧ,÷ΧҲȽС.ռӴʱ,ԵòӦʵʻ,Ҳʾϲġ³ԡ.
(3) .Ŵ㷨áѡΪһָ㷨һ봮ɵĿռн.ǵ,ѡΪֶ,ϵͳΪ,ʹϵͳܲ,Ž.
һ㷨׼,㷨ǷܹڸʱԴΧڸŵĽ.ŽⲢܱ㷨һõ,ʵʻ,ǸӵܹڸԴʱԴڸõӦ.Ŵ㷨Ǿⷽص.Ųͬ㷨,ҪΪ4棺
(1) ռǲϵı,ǲ.
(2) GAsռһȺ,һʵ.Աֲֵֻ,ʧȫ.
(3) GAsָ㷨ŵķǰ,һЩ֪ʶ.֤ϵͳ³,κλ.
(4) Ϊֶ.
4ʹŴ㷨бõ³,κʵʻ.
2.2 ͳGA㷨
Ŵ㷨ڱ봮ռ,ʹԴд,õµĴ.GA㷨Ѱһн,ȻннŻ,ķӣ˵3֣selectionѡ,Crossover棩,mutationͻ䣩.
GAsͨ3ڴռ,ϵͳĽܶԱ봮,Reproduction,ͬʱѡ񽻲,Ա봮н,õµһ봮,ͬʱͻڶԱ봮ͻ.
2.3 Ŵ㷨ص
(1) Ŵ㷨ʱ㷨ص,ʱж,ʱĻſн⣨ȻܶŴ㷨ĽⲢҪ,,ʵĽʵҪ.Ź滮ʱ,ϵͳ.
(2) Ŵ㷨,˿Ա⴫ͳľֲŵ,ҵȫŽ.
(3) ȡԼ֪ʶӦ,,ֻһЩͳϲܷЧ.
(4) ͳ㷨Ҫ϶֪ʶ֧,֪ʶԻȱʱ,޷𷽷Ŵ㷨ֻҪ۷,ͿԽй滮,ⲿƽ.
3ʵ
3.1 ʵӦмŴ㷨(SGA)ڵ
Ŵ㷨Ҫһصͬ滮㷨,кǿ³,ڸױĻ,ܹŻĽṹ,ȡýŵ.,SGAϵͳΪ,ϵͳһЩõľ֪ʶЧ֪ʶ,Ȼϵͳ³,ȴʹϵͳٶȱȽϻ,,һпҲ.,Ŵ㷨Ĺ۵ֵΪָ.ȻСʤ̭ԭ,ʵʱ㷨,ԲŻϵͳ,ܹʱжϲŽ,,ʵضŴ㷨и,ͿԵõһϺõʵʱ㷨.
3.2 ʵӦ
Ŵ㷨㷺Ӧ,ڡ·㷨ӦΪ,Ŵ㷨ʵӦдڵ.
ͳȻȱ,ױ绷,Ҳźܶŵ,Ժܺõ֪֪ʶΪָ,ϿصõϵͳĽ.,ԺضŴ㷨и,Ŵ㷨ĻһЩ֪ʶָķ,ӿٶ,ֲŴ㷨ȱ.
ڹ滮,Ŵ㷨嶼ͬ,Ϊ,ڼ֪ʶָ,ʹϵͳÿжŻķǰ.SGAвõķ϶Ѱһн,ȻннŻ.ͨѡӺ۷в.ķ˵3֣ơ桢ͻ.Ȼʵ,ڲͬõ֪ʶʾͬ,ӵʵӦҲڽϴĲ,۷Ҳͬ,Զڲͬ,3ҲҪӦĸıӦʵ.,ԡ·滮㷨еʵʽΪ,ʵ֪ʶӦŴ㷨е.
·滮ҪǣһϰĶάռ,յ,Ѱһϰ·.
.ݱʾ
·滮,ʵ·õıʾǲ·еһϵйؼʾʵ·,(s,d1,d2,...,dn,e)ʹһʵ·,sΪ,eΪյ,diΪ·еĹؼ.
.۷
(1) ϰཻĳȣԽԽã;
(2) ϰཻĴԽԽã;
(3) ·ȣԽԽã.
ȼ𽥽,ҳн,ȻѰ·.
.
(1) ӣõ·ѡһ,Ȼ·н,õµ·,ͼ2ʾѡ3Ϊ㣩.
 
ͼ2 
(2) ͻ䣺ͻ¼:ıؼλ,ڼӵ,ۼ,Ҳȡһ,λϸı䡢ɾһ.ı/ĵλҲɵ.ͼ3ʾ,ı//λѡ3.
 
ͼ3ͻӣı䣯ӣ㣩 
ѿ,ͳGAԽ·滮õľķ۲ϵķ.ַѡԵõŵĽ,ϰ϶,ôʵʱͻúܳ,Ҳ𷽰,ΪѰŽϾٶȱȽ,ҿ˵ƽŵٶȫȡ۲.ͬʱ,ȱʵ֪ʶָ,һ.
,ʵظĽ,ʵ֪ʶָ,.
.ϰĽ
·滮,ҪѰһϰ·.GA㷨һЩн,ȻЩнŻ,GA㷨ʼ,нǲķ,˲ɱشϰĽ,GAÿͼȥЩв,ͬʱﵽ·.·滮㷨ص,GA㷨нʵĸĽ,ʹÿβ·ܵرܿϰ,ϰĽ澡,ӶӿŽѰ.
õӲ£һʵʵ·(s,d1,d2,...,dn,e),di-djϰཻ,ôϰӡᴦβ,֮Ĺؼ.Ҫָ˼ƽʱѰ·ʱ,ϰȡܿԭ,ʹɵ·ϰཻ㾡,õķͼ4ʾ.¹ؼԷ,֣(1) Ѱһ¹ؼԭеĲؼ;(2) ѰҼ¹ؼԭеĲؼ.
 
ͼ4ϰ 
.
·滮гҪϰ֮,һҪҪ·.ڽпʹɵ·ĳȶ,,ʵѡ񽻲,ʹ·ĳȾ,ҲҪõһֲ.ǵ·ȵ,,ڽʱѡ϶̵ĵΪѡ.
·ֱΪ·1:(s,d1,d2,...,dn,e)·2:(s,d1,d2,...,dm,e)֮ľ,ҳ̵ĵ,Ϊi={jmin(d1,d2-d1,d2,d1,d2-d1,d2,...,dj,di+1-dj,dj+1-dj,di+1-dj,dj+1,...)},ѡdiΪ,·1·2,õµ·1:(s,d1,...,di,di+1,...,dm,e)·2:(s,d1,...,di,di+1,...,dn,e),ͼ5ʾ.
 
ͼ5 
.·Ż
Ŵ㷨ɵ·,ɱشźܶȦ·,ЩȦ,õʵʵ·ϵͳյҪ.Ҫǰɹؼɵ·תͼÿʵʵɵʵ·,һ(x1,y1)(x2,y2)·ͼ߱ʾ·תͼʵʱʾ·,ҲǰÿС񿴳һ,ͼ6ʾ.
 
ͼ6Ż· 
ʵ㷨£

x=x1
y=y1
i=0
while (ix2-x1+y2-y1{


(x,y)Ϊһ,Уxyx,yĽx=x+x
}
ξǶԽĽŽŻ,ŻķҲǶ·䡰ϸ·,ȥظ·,õ̵һ·,ͼ7ʾ.
 
ͼ7ȥظ· 
ᵽһЩ֪ʶ,ǻһЩصļ,Ŵ㷨ͬ.ڹ滮ռ,ڽϴϽ,õĿнٶԹ滮ռϸ,׼ȷĽſн.
ͬʱ,Ҳˡ滮ĸ,֪ʶԹ滮Ŀռ򻮷,Իֱֺй滮Ŵ㷨,Ȼϲ,õŵĿн.
·滮㷨,Ƚϴֵػֹ滮,ҳһЩн,Ȼл,õЩ·Ƚϼе,Щϰ϶ࡢ·е,Ȼϸ½й滮.÷ֲ滮ĸ,ʹϵͳٶȼӿ.
3.3֪ܽʶʵʱеӦ
ͨʵ鲻ѿ,Ŵ㷨ȴŵ,Ҳڲ֮.Ȼϵͳġ³ԡ,ȱ֪ʶָ,ʹϵͳķȽäĿ,ʹϵͳȶٶȴ󽵵.ʵ뾭֪ʶָ,Դӿϵͳٶ,ͬʱŴ㷨ѡΪ,˶ʧȫŽ,,ֲ滮ԽԽܵҵ.
Ҳݺӵ,֪ʶǷ,ϵͳܵӰǺܴ,ʵ֪ʶϵͳٶʲô,һпܰ;,ϵͳʧŽ.֪ʶ,ϵͳڴ֪ʶ治ɱҪͶʵĿ,,Ҫƽķ֪ʶ.ʵз,·滮ϵͳʱĲ־Ƕ·.벻֪ͬʶ۵ʱ䲻ͬ.ֻк֪ʶŴ㷨,ܸõȡĽ.
3.4 ʵ 
ᵽķ,IMBPC Pentium133ʵ·滮㷨,Microsoft VC++4.2,Windows95,µʵݾڴ˻µõ.
·滮,300*200pixelĵͼϽй滮,·ϰ˹,ʼ·Ϊ100,·йؼΪ10,ͻΪ5.۷á·ϰཻȡԼ·ʵʳȡΪ.ڹ滮ĳԡϰཻȡΪ,˹滮,·ں,ϰཻĳȽС,ԡ·̡Ϊ.Ƿֱͨ¼;Ŵ㷨вԣ
(1) û㷨,κζ֪ʶϢ;
(2) ıʼ·Լؼ;
(3) Ӧ֪ʶϢΪָ.
ʵвѿ,Ŵ㷨Ȼкǿ³,Ӧ绷,ȱӦ֪ʶΪָ,;,ҪϳʱҵŽ,ϵͳʼ˿ڹģ,ʹϵͳȶĳЩ,ЩⲢϵͳҪ.·滮㷨,ϰĿ˵,Ŵ㷨ԽϺõҳŽ,,ϰ,Ŵ㷨ѰٶȾʹ.Ӿȶһ˵Ľ,Ӵ˿ڹģ,ϵͳͿȶ,пѰҵſн.ϵͳ78,ȶ,ϰཻΪ37,ͼ8ʾ.
 
ͼ8Ŵ㷨 
Ӧ֪ʶָ,ϵͳܴ.֪ʶ۵:һǾϰཻ,Ҳᵽıײ,һҲӦ֪ʶʹ·Ⱦ,磺ʶѡ񽻲㡢ŻӦ·ȷ.ʵǿ,֪ʶϵͳЧ,ҾϵͳӰҲͬ.֪ͬʶõķҲͬ,ϵͳʼʱ,ײ,ϵͳеĺ,·϶ӿʼ.ͬʱ,ע⵽Ǽ֪ʶӺӴϵͳĸ,۴ʱ仹ǿռ临Ӷ˵ȻŴ㷨.˲äĿ֪ʶ,ֻѡʺϵͳ֪ʶ,ܷЧ.ʵѡ֪ʶ,֪ʶ븴Ӷ֮ƽϵҲҪһо.Ϸ,ǽӦʵ,ʵͼ9(a)(b)ʾ.ʵ1ݼ1.
 
ͼ9֪ʶӣ滮 
1 

n 
N
C1 
5
5992 
71
5623 
80
1094 
77
1075 
83
796 
46
817 
73
818 
19
819 
66
8510 
80
8511 
20
6412 
59
9313 
49
9414 
69
7415 
36
4916 
73
9717 
43
9618 
31
10119 
41
9920 
30
115
n 
N
C21 
28
10222 
18
11423 
32
11024 
40
11425 
55
11026 
80
6327 
60
9028 
75
9029 
34
10030 
86
8531 
25
7132 
29
5933 
44
7234 
23
7235 
86
6136 
0
7337 
44
7538 
16
5539 
57
5940 
61
59
n 
N
C41 
74
5942 
81
5943 
20
5944 
8
5945 
2
5046 
23
4147 
86
6248 
20
6249 
32
2650 
28
2651 
11
2552 
39
2553 
28
2554 
3
2455 
6
2756 
0
1957 
0
1358 
11
059 
31
060 
82
0

nڼ,Nnֵߵ·,Cnֵߵ·ϰཻĳ.
ʵ1,ϵͳ60Һȶ,Ѱҳſн.ʵ,Ƿ벻ͬı,ϵͳܵӰҲͬ,Ͳʵ.
ʵݿԿ,滮֪ʶ,˺ָܴ,ӿٶ.,Ҳע⵽,֪ʶ,ӴϵͳĸӶ,ÿΪ˶ϰҪѽ϶ʱ,ϰ,ϵͳӵĹؼҲ,ϵͳĿռʱ临ӶȶԼӴ.,֪ʶһԹ滮,ֻдﵽһ̶,ܷ.ȷϵһ,֪ʶ,ԼСʼ˿ڣ֪ʶ,ϰﵽһ̶ʱ,ϵͳȶһЩн,ʱֻмӴʼ˿ڲн,֪ʶ,ԽϺõؽ.,δϰʼ˿ڡ֪ʶԼ滮ʱ䡢ռ临Ӷ֮ĹϵΪоĹؼ. 
4ܡ
ʵʱ滮㷨ҪϵͳƶԴڸŵĽ,ͬʱ,ϵͳԴͻ¼,ʱֹ滮㷨,ʱΪŵĽʱԽ,ϵͳܾԽ.ʱ㷨ĿܷЩ,Ҳʵʱ滮.ʱ㷨,ԺϵͳԴ,ϵͳܣͬʱ,ʵӦʵ뾭֪ʶΪָ,ԴӿϵͳĹ滮ٶ,Ž.
оõȻѧ͹863߿ƼĿ
߽ܣ,1972,ʿ,ҪоΪ˹ܣʵʱ⣬滮.
,1935,,ʿʦ,йѧԺԺʿ,ҪоΪӦü˹.
ͨѶϵˣ, 100084,廪ѧѧ뼼ϵ
ߵλ¡廪ѧѧ뼼ϵ100084
šࡡ廪ѧܼϵͳصʵҡ100084
E-mail: snowchen@263.net
ο
1 McDermott D, Hendler J. Planning: what it is, what it could be, an introduction to the special issue on planning and scheduling. Artificial Intelligence, 1995,76:116
2 Agre P E, Chapman D. Pengi: an implement of a theory of activity. In: Proceedings of American Association for Artificial Intelligence'87. 1987. 268272. http: www.ncstrl.org
3 Georgeff M P, Lansky A. Procedural knowledge. IEEE Proceedings, Special Issue on Knowledge Representation, 1986,74(10):13831398
4 Kaelbling L P, Rosenschein S J. Action and planning in embedded agents. In: Patti Maes ed. New Architectures for Autonomous Agents: Task-level Decomposition and Emergent Functionality. Cambridge, MA: MIT Press, 1990. 3548
5 Sanborn J, Hendler J. A model of reaction for planning in dynamic domains. In: International Joint of AI Engineering. 1988. http: www.ncstrl.org
6 Schoppers M. Universal plans for reactive robots in unpredictable environments. In: Proceedings of the International Joint Conference'87 on Artificial Intelligence. 1987. 10391046. http: www.ncstrl.org
7 Firby R J. An investigation into reactive planning in complex domains. In: Proceedings of American Association for Artificial Intelligence'87. 1987. http: www.ncstrl.org
8 Dean T L, Boddy M. An analysis of time-dependent planning. In: Proceedings of American Association for Artificial Intelligence'88. 1988. 4954. http: www.ncstrl.org
9 Goldberg D E. Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, MA: Addison-Wesley Publishing Company, Inc., 1989. 36
1997-10-15յԭ,1998-01-09յ޸ĸ 
