ѧ
JOURNAL OF SOFTWARE
1999 2 No.2 1999



ʵʱ
¡š
ժҪʵʱµǽ滮оȤĻ.ʵʱ滮㷨ͬͳ߹滮㷨֮Ĳ֮ͬ,һʵʵʱ滮ͳһ,ͬʱ˿еĸģ.ܹͨĵϵͳӦʵʻҪ,ڹ涨ʱڽϵͳҪ,ܽϺõؽȷ.,ڿģָ¹װʵʱϵͳ,ʵ.,,Ҽ򵥵ʵʱ滮㷨ĲԼķչ.
ؼʡ滮,ʱ㷨,ʵʱ,ȷ,鼼,ʵʱ.
ͼšTP18
Real-time Problem Solving Framework
CHEN Zheng ZHANG Bo
Abstract Real-time problem solving is an interesting topic in planning in the recent years. Besides discussing the differences between real-time scheduling and off-line scheduling, a real-time scheduling framework is proposed and some pivotal technologies are discussed in this paper. This framework can deal with uncertainty in real-time environment and output approximate solution in given time. Based on this framework, an intelligent assembly robot system is built, and through some experiments this framework is proved to do well in real-time environment. After all, the conclusion is given out, and the policy of real-time planning problem solving algorithm simply and the possible developments in the future are discussed in this paper.
Key wordsPlanning, anytime algorithm, real-time scheduling, uncertainty, group technology, real-time monitoring. 
1 ʵʱ滮߹滮
滮ʱ䡢ռ临ӶȶȽϴ,,ͳ滮㷨Թ滮һϵеļ,ΪؼһΪ绷ǲ,ʹǵ绷ı仯,ҲΪ仯ǿԤ֪.,滮㷨ڸ绷¶Թ滮ռ,õϵͳ.,һʵ,ǾͻֵᷢĴͳ滮㷨ܺܺõؽʵʻеĹ滮,ΪʵʻһױĻ,һԤ֪;ͳĹ滮㷨Ϊ绷һԤ֪ģ,ϴ´ͳĹ滮㷨ױĻоԵ޷ת.,һʵʱµĹ滮㷨ͳΪҹע.κøԴ,Чеʵʱ㷨ΪоĹؼ.
򵥵˵,ʵʱ滮㷨봫ͳ滮㷨뷽:
(1) ޵Դ;
(2) ȷ: Դȷ; ȷ:(a) Դı,(b) Լı,(c) ִй̸ı; ȷ:(a) ,(b) ȸı.
˹,ȷԡǸȤĻ.ȷԷΪ͹۲ȷԺ۲ȷ.͹۲ȷǶ¼ƵȽͳƼó,˵˼Ӱ;۲ȷǶ¼Ƶȵһ,Ʊʹںܴ.,߽ײȷֵ,p(p(A)=xK)=y.
ʵʱ㷨㷨ԴںܴĲ,Ҳõ㷨صҲںܴĲ,ҪΪ¼1: 㷨ϵ𡪡ȫȷ()¾ȷ(); жԵ𡪡ж()ж(); ʱϵܲ()ʱ().
2 ʵʱ
ʵʱ,ͳ߹滮㷨ѾӦҪ.ҪһµĽӦʵʱҪ.,ǷֱԸӦĽ.
ΪʵʱµĹ滮ܵԴ,Բԭϵͳȫֽй滮,ڹ滮㷨ǽӦĸı,ɷΪ¼ַ.
(1) ԴԼ
ٲ߹滮㷨Ȼǿȵ㷨,ȡ֮ǡʵʱµĹ滮㷨ʱ㷨ȣ.ʵʱµĹ滮㷨ص: ʱжϲʱĽŽ; ܹ޵Դй滮,ҿԴڸ; Դ,ϵͳ𽥸Ľ; ֲܹȷ,֤ϵͳת.
(2) ȷ
ʵʱ滮,һϴڡȷԡ.ϵͳҪױ绷,Ҫϵͳܹͻ¼.ͳĹ滮Ϊ绷ǿԤ֪,Ⲣʵʱ滮ʵҪ,ҪϵͳӦı: ʵʱϵͳ; ֲ滮ϵͳ:(a) ϵͳл,ϵͳͼ,(b) ֲ滮:ӽϴֵȿռϽй滮,ϸȿռϽٴι滮,(c) Ե:ϵͳпòֵʹ.
ʵʱ滮ǽʹ¼.
2.1 鼼Group Technology
鼼Ļڹ滮аѹ滮ϵͳֽΪɸϵͳ.ǿԿ,ʹ÷鼼,Զÿϵͳֱáʱ㷨й滮,ʹϵͳʵʱ.Сռ,ҿԼٲҪظٹ滮,ͬʱʹ滮ϵͳ.
2.2 ֯
ʵʱеĹ滮ϵͳɶϵͳ,ҳڶʱ䡢ռԴĿ,Ƕÿϵͳʱ㷨й滮,ʹÿϵͳܶԴӶ.,һ֮,κڸϵͳ֮Դ,ϵͳ,ǳ֮Ϊʱ㷨֯.ᵽĺܶNP,ͬѿ,ʱ㷨֯ͬҲһNP,κطϵͳԴ,õŵܳΪһ.߻¿ôͳķ֯,һӦʵʱ,¾ȷ⡱ռҪλ.
2.3 ʱ㷨ļ
ó鼼ϵͳͬ໮,ͬʱԸֺϵͳԴ,Щ߻,ȻҪ߹滮ĽӦʵʻ,ʵʻдĲȷ,Ҫϵͳִнм,ϵͳִн.
ϵͳ,ξصƵԼξǷüصȲף2ϸ,˴׸.
2.4 ʵʱ
ĸʵʱķ,һʵʱһ,ڸʵʱ,ܿԱȽ׵عʵʱ㷨,ԽϺõؽ.ʵ,滮/ⶼԿһʵʱµ,,ǿԲ/߹ϵͳ,.ͼ1пԿҪΪ4ģ:߹滮ģ顢ߵģ顢ģ͹ϻָģ.ϵԴͼ1еõ.

ͼ1ʵʱ
ڲͬĹ滮/,ǽʵʱܽйʵʱ㷨,ͬʱʵʱ㷨ݿԼ滮/ȵľ֪ʶ,ʵʱ㷨м,ֲȷ,ϵͳ.
ʵʱܹװϵͳ,ϵͳ.
3 
ᵽġʵʱĿܡ,װ̵,Ʋʵһװϵͳ,ͬʱһЩװӽӦĲ.
ڻװ,Ǹװص,˿ٵ㷨,ֲȷķ.װҪ:m̨õĻM={M1,...,Mm},ͬʱҪȵnT={T1,...,Tn},ͬʱn֮ԼϵDAGͼ߹ʾ,ҪԽٵʱm̨ϵִn.
װҪľڸʱڸϵͳŵĹ滮,ͬʱܹʵʱִзĸֲȷ.ǶװпֵܳĲȷԽй,Ҫ¼:(1) ӹʱı仯:Ҫָǰִеļӹʱӻǰ;(2) λ:ָԭӦÿԾھʱ;(3) :ĳʱ̻,Ҫִ.
ʵʵ,Ǹװȵ,µȲ:(1) ִʱԽȱִеĿԽ;(2) ȳȽϴִеĿԽϴ;(3) ֱӺ̻Ǻ̶ִеĿԴ.
3ǵĿٵȵĻ,ǻԵ÷Χŵȹ̶ı.ڵ,Ǹʵʱıÿȼ,ЩѾ͸ȼĸ,ڽ϶̵ʱڶе.֮Բö̬ȼȣ3,ΪԲϵȼӦױ绷.ı,ȼҲ֮ı,ԴﵽѵĵȽ.ͬʱ,ڵлδĵһԤ,Ա֤ȵľ.ڽܵ㷨ǰ,ȸ¼.
(1) :tʱiǰԼѾȽ,ô,iΪ,ֻҪпеĻпܱ.ΪRT(t)3;
(2) л:tʱ̻jڵκ,ǳƻjΪл;ڵȹӦٻĿг̶,ϣʱڵȽ.ΪRM(t)3;
(3) ִʱ:ExecTi;
(4) ִҪĿ:UMi;
(5) ȳ:Depth(Taski);
(6) ĺȳ:Depth(Taski).
Ϊ˽͵ȹ״̬ռĴС,ǰѹ滮ʱ仮ֳɸɢʱƬ,ÿռ1ʱƬ.,ڵȹ̶ÿʱƬ̬ؼȼ,ȼߵȷִ;ȼ㰴ĲԶȳԼִʱӦȨõ.
ĲǿԵótʱiȼΪ

ᵽ㷨ڶԽԤ,Զ㷨Ӧĸı,tʱ̼ȼʱǰԤһʱ䦤t,ͬʱڦtʱڲڵ,t+itʱ֮ȼ,Щȼ.ͬʱ,ʱ㷨ϸı䦤t,ҵʱѵĵ.
3.1 ܻ㷨
t=0;
LeftTask=n;
while (LeftTask0) {
tʱ̵ľ񼯺
t=0
BestAlloc=
while (tMax PredictTime {
if񼯺Ϊ,һȴ
else {
t+tʱ̵ľ񼯺ϡл,ھ񼯺еӦĶ̬ȼPrior(Taski)
ѡֵߵִ
ѷ뵽BestAlloc
LeftTask--;
}
ŵBestAlloc(tʱ̼伯)
t=t+step // Ż
}
BestAllocϵе
t++;
}
3.2 Ӷȷ
㷨µķ,ڵֻҪһ̨,ͬʱڹл,Ľ㷨ľȷ.
Խ㷨:㷨ʱΪTn,ŵʱΪT*n;㷨ľƫ=Tn-T*n,ƫ.
֤,㷨֮κԼ,ƫ㣨lΪĿ4.Ҵ㷨ϿԿ,̨˹ʱ,㷨ϵͳŵ,Johnson̨˵ȵõͬϵͳ.
3.3 ȷԴ
ȼȷ,ͨʵ鷢,ܽϺõضװе.Ӧʵʱ,Ĳȷ԰ļ,ԷֵȷԷ,ϵͳԸݵʱ״Եʱľ¼ͷ,ͬʱԸݸʱ䲻϶Ż,õŵϵͳ;ҴȷϵͳҲ,pʱ.
3.4 ʵ
ԼΪ㷨.㷨P133+Win95+Vc4.2¿.
ϵͳԼϵͼ24ʾ.ϵͳGanttͼ512ʾ.

ͼ2ͼ3ͼ4

ͼͼ1Ȳԣ̬ȼExecTime(T8)=2
ͼ5ʵ1ͼͼ2ԼԼԼÿʹһߣлʱΪ1߸Ϊ5ͼ*ڵȴʱҪйл
ͼ6ʵ2


ͼԼԼԼĿΪ3ִʱҪ13̨ͬʱ
ͼ7ʵ3ͼͼ3ͣװǰԼϵͼзװ䲿ԲȦװӴͬһεĽڵ㣬ͬϵĹϵȷֲ滮
ͼ8ʵ4


ͼͼ2ûκβȷ
ͼ9ʵ5ͼ2ȷԣt=4ʱ̻2ϣϵt=5ʱ̽
ͼ10ʵ6


ͼͼ2ȷt=6ʱp5ִʱҪӳһʱ
ͼ11ʵ7ͼͼ2ȷԣp5ĵλʱӳt=9ܵλ
ͼ12ʵ8

ߵȷ,˲ᵽġ¾ȷ⡱ķ,ֲ滮ҲǽϺõһֽ,԰Ѹ򵥻,ͬʱҲܵõϺõĽ.
3.5 ֲ滮
ΪװмٹлϵͳװĲ,ֲ滮ķ,ʵַ£װеÿе滮:
(1) Ϳл;
(2) ڵ,ԭеĲԷִ.ڲڵ,ȹִʱԼҪִлĿ,Ȼִ;
(3) ڲڵϸ,㷨.
ᵽ㷨,ֲ滮㷨Ҫ¼ı:
(1) ڼÿִʱʱ㷨Ҫı,ִʱֱӵõ;ڲִʱҪй.һҪtiʱ,ȻִҪĻĿn,ڲִͬлĿ,ڲͬʱExecT=
(2) Ĺ,񼯺Լл.
(3) ȼ.ȼʱҪǵԲִлĿвͬĹƶӰ.
(4) ȼϸߵִ.
(5) ҪϵضԲĵȽϸ.
ֲ滮㷨ڴȷԷŵ: ԭеһϵͳֳԶСϵͳ. ڲͬ϶Ƚд. ʱ,Զÿֲ;㷨ĸӶ. ȷ,ԶԲȷԷԡλ,ع滮ȷԷĲ,ӰεĹ滮;ͬʱ,ʹù滮õļֵ.
,ᵽװ̲ϵͳзֲ,ǻװгõһЩ֪ʶϵͳзֲ滮,ڵ,ǿ԰һЩϲһ,ȻڽϸߵĲνе,ȵʱ,ٵȽϵͲεĵȽй滮.
4  
ִҵķչ,ʵʱ滮ʵеӦҲԽԽ㷺,ͳ߹滮ѽӦʵʵ,µĹ滮ģʽռλ.ʵʱ滮㷨ԻϵͳԴ֮Ķ̬ƽ.Ӧõƹ,عʵʱ滮㷨,Чù滮ÿõĽ,Żϵͳ,ŵؼϵͳִ,ЩΪоʵʱ滮Ĺؼ.
оõ863߿ƼĿ.
߽ܣ,1972,ʿ,ҪоΪ˹,Ӧ.
,1935,,ʿʦ,ҪоΪ˹,Ӧ.
ͨѶϵ:, 100084,廪ѧѧ뼼ϵ
ߵλ¡廪ѧѧ뼼ϵ  100084
šࡡ廪ѧܼϵͳصʵ  100084
ο
1Joshua Grass, Shlomo Zilberstein. Anytime algorithm development tools. Department of Computer Science, University of Masschusetts. URL: httpanytime.cs.umass.edu/sclomo
2Hansen E A, Zilberstein Shlomo. Monitoring the progress of anytime problem-solving. Department of Computer Science, University of Massachusetts. URL: http: anytime.cs.umass.edu/sclomo
3ݻƱ.װϵͳо۲ʿѧλģ.廪ѧ,1994(Huang Bi-qing. Research on task scheduling in intelligent assembly robot systemsPh.D. Thesis. Tsinghua University, 1994)
4¬.㷨Ӷȷ.:廪ѧ,1983(Lu Kai-cheng. Analysis of Algorithm Complexity. Beijing: Tsinghua University Press, 1983)
1997-12-11յԭ,1998-03-02յ޸ĸ
