ѧ
JOURNAL OF SOFTWARE
1999 10 8 Vol.10 No.8 1999



ֲʽ⻷лʵʱԤ
赫 ʷ ʯӢ
ժҪڷֲʽ⻷,ܵƿΪάʵΪһԶеͨ.ⳡеԤ״̬ģ,ʹ˻ںӵΪʵʱԤ.Ƚ˺ӵԭص;,ڶԴͳDR㷨˻ԤӦDR㷨;Ȼ˻ڸ㷨ṹ;һʵ,ʵ㷨Ժܺõع.
ؼʡֲʽ⻷,,Dead Reckoning (DR㷨),,.
ͼšTP
Real-time Prediction Based on Neural-networks in Distributed Virtual Environment
SHOU Li-dan SHI Lie SHI Jiao-ying
(State Key Laboratory of CAD&CG Zhejiang University Hangzhou 310027)
(Department of Computer Science and Engineering Zhejiang University Hangzhou 310027)
Abstract In a distributed virtual environment (DVE), the bottleneck of performance is the communication among hosts which keeps the consistency of virtual entities. The neural-network models of state vectors for unpredictable entities in a virtual scene are build in this paper, and the functional-link net to real-time prediction of their behavior is applied. Firstly, the principles and characters of functional-link net are introduced in this paper; secondly, after description of the traditional dead reckoning (DR) algorithm, an adaptive version of the algorithm based on functional-link net is presented; the network software architecture based on the algorithm is also given; finally, an example of the algorithm is given with experimental data, which shows the good performance of it.
Key wordsDistributed virtual environment, computer networks, dead reckoning, neural-network, functional-link net.
ֲʽ⻷(distributed virtual environment)ָ,һ绥ļͬʱ⻷(VE)ϵͳļ.⻷缼ѧƽĲ,ʹɵ⻷ʵֽʵʵλõԼ,ӶкӦʹ,Զѧϰ֧µЭͬ(CSCW)ֲʽģ(distributed simulation)ȸӦ.ֲʽ⻷ۺ͸µ,Զ̻(telerobotics)Զ(telemedicine).ֲʽ⻷Ŀǰŵо֮һ,ڿѧоģѵս෽йӦǰ.
ڷֲʽ⻷,Ҫÿʱÿ̶Ҫֲַʽϵͳ䳡ͳиʵΪһ,άϵͳͳһ.Ҫ֮ʵʱؽ״̬Ϣ,ɴ˶ͨռֲʽ⻷ʵͨĴ󲿷.һͨǳΪһͨ.һͨݵķ߳Ϊοϵͳ׼ϵͳ,߳Ϊϵͳ.ڳӶȽϸߣʮʵ壩ϵͳģϴ١ǧ̨£1,һͨᵼ绷ӵ.,һͨǷֲʽ⻷еһҪо.
оڸ÷չ2ݣ3,гõķǲԶеDR㷨,ⳡеʵΪԤ,һͨŵĴ,ӶﵽĿ.ǵĻ˼ڲοϵͳʹϵͳϲȫһµԤ㷨,ʵ״̬ʷ,һʱ̵״̬Ԥ.Ԥʵ״̬Զ,ڲοϵͳ˲һʱ̵һ,ϵͳһʱ̵״̬Ԥý;֮,ʵԶ,ʵ״̬,һͨ.ԤĶһһͬ,״̬һ򵥵ʱ亯ʾ.ʵʵⳡʵ,״̬޷һ򵥵ĺʾ.һܻ,ֱܵ˵Ŀ,,Ժܴ.ʵ,ͳDR㷨Ϊ,Ҫ;о.ڱ,ʹûںӵʵʵʱԤ,õ˽ϺõЧ,󽵵һͨڱ,Ϊ˱,һʱʾ̨֮ļ,һʱʾ˹磩.
1 Ӽ
ںģ,һһڵ,,ڵk,ͻ฽ӺҲ,ܵõڵkok,һܵõf0(ok),f1(ok),...,fn(ok)4.ԺӵĲͬҪͬЧ.ڱ,ǿǺչģͺģ.
ںչģ,ӵÿڵ ģʽеÿڵ,ͬĸӺ.,xԼ򵥵չݺ,չnάռһӼ,:sinx,cosx,sin2x,cos2xȵ.ǽģʽӳ䵽һģʽռ.ǽչϵ,.û뱾ԵϢ,ģʽԵõǿ.
ģ,ģʽÿģʽʸ.,ԭɷ{xi}ģʽ{xi,xixj}(ji){xi,xixj,xixjxk}(ji,kji)ȵ.ûµϢ,ʹõϼ.
ģʹǿʵػ.ͨ任õǿ,ʹ(͵ͿʹѧϰѸ5.ڵ5,٣10ڣСģѧϰ,ֻ費100μʹϵͳС10-6.,һ3루x1,x2,x3),(y)ѧϰ,7ѧϰ1.
1 뵥ѧϰ

x1x2x3y
10.2160.10.10.90
20.3470.160.10.85
30.4630.240.10.80
40.4870.320.30.75
50.5130.400.30.7
60.5470.460.60.65
70.7800.90.60.6


Բûͺչx1,x2,x3,x1.x2,x1.x3,x2.x3,cos(3.x2),cos(3.x3),cos(18.x3.x2),cos(13.x1.x3),cos(13.x1.x2),cos(24.x1.x3),cos(24.x2.x3),cos(24.x1.x3)14,õ˽ṹʹѸ,ͼ1ʾ.

ͼ1غѧϰٶ
ͼ1пԿ,ڶ²չ,ʹѧϰٶȴ,ͬʱ,˵Ľṹ,Ƽ,̷,ѧϰʱ伫̣Pentium 200MHzϲ1ms,,ʵʱԤ.
2 ںӵԤ㷨
ڷֲʽ⻷,Ѿйʵ״̬Ԥ㷨о.㷨ͳΪDR㷨.һ͵DRԤ㷨ڲοϵͳʹϵͳ˶ʹKalmanԤ6,˶״̬ÿһʱʱԤʵ״̬,һԼֵ,һͨ,ʡȥôʱڵһͨ.
ڶ̬ⳡ,˶ʵ峣ѭһĹ˶.ҲһЩʵ˶ûԵĹɿѭ,޷״̬̱ʾ˶.һЩ򵥵,ƶ׵Ķ.Щ˶ܵûֱӿ,״̬ıԽϴ.仰˵,״̬Ԥ.еĳһһϵͳ,ҵһȷ״̬.ʱ,ǿ.
ڵ1Ѽ򵥵ؽ˻ںӵ.ԽʹʤʵʱԤ.㷨Ļԭ:Ԥ,ڳʱ˶״̬ԵýϻҶ޹,Ϊ㷨ʵҲȷʵһ㣩һζʱ,˶ѭĳȷĹ,ֹʱı,״̬ʱı仯,,޵ԱΧ,޸ܿɸȷԱʾƽ5.ҲǺӵۻ.ЩǺеĺչ.,ṩk{(Xm,Xm+1,...,Xm+r-1,ym+r),(Xm+1,Xm+2,...,Xm+r,ym+r+1),(Xm+k-1,Xm+k,...,Xm+k+r-2,ym+k+r-1)},ym+iǡþXm+i(i=r,...,k+r-1),ѡȡʵ,ѧϰʹym+iеym+iһ.˿Կ,ÿʵǸǰr״̬,Ԥr+1״̬.ɸѵɵԤym+k+rֵ.
ڶ״̬ͣظı,ҪʵʱضԤе,޸ѧϰѧϰ.ǿڴͳDR㷨ϵõһ㷨,㷨ԳΪѧϰӦDR㷨.ӦDR㷨ܶ˶̲ȷĶԤ,رԤ.
ڸ㷨֮ǰȶԷűʾһЩԼ:kάX=(x1,x2,...,xk)Tʾ״̬;Xnʾtnʱ̶״̬.iѧϰúr+1״̬ľS(i)=(Xmi,Xmi+1,...,Xmi+r-1,Y(i))ʾ,京ǰr״̬Ԥӵ״̬y(i).ѧϰ:{S(i)|i=1,2,...,N}.
ϵͳΪοˣ׼ˣʹ.ο˵Ԥ㷨.
㷨1. ο˵Ԥ㷨
Step1. α={S(i)|i=1,2,...,N}.
Step2. ø϶ѵѧϰ.
Step3. ȥrʱ״̬ʷXn-r+1,Xn-r+2,...,XnΪr,(Ԥn+1.
Step4. յһʱͬźţtn+1ʱ̣,Xn+1-n+1,״̬Xn+1ͨ绷͵Ԥ,״̬Xn+1ʷ,ͬʱ
S=(Xn-r+1,Xn-r+2,...,Xn,Xn+1)
ϵ;,,Ԥn+1tn+1ʱ̵״̬״̬ʷ,ͬʱ
S=(Xn-r+1,Xn-r+2,...,Xn)
.
Step5. תStep2,ѭִStep24.
㷨֪,ÿյһʱź,㷨ѭһ.㷨Step3Ҫrѭ,ΪrѭʱڳΪrʷ.,ÿѭҪıӦе±.Щ˵ͬҲڴ˵㷨.˵㷨Աʾ.
㷨2. ˵Ԥ㷨
Step1. 㷨1ͬα={S(i)i=1,2,...,N}.
Step2. ø϶ѵѧϰ.
Step3. ȥrʱ״̬ʷXn-r+1,Xn-r+2,...,XnΪr,(Ԥn+1.
Step4. յһʱͬźţtn+1ʱ̣,ڴ֮ǰյο˵ݰ,յ״̬Xn+1ʷ,ͬʱ
S=(Xn-r+1,Xn-r+2,...,Xn,Xn+1)
ϵ;,δյݰ,Ԥn+1tn+1ʱ̵״̬״̬ʷ,ͬʱ
S=(Xn-r+1,Xn-r+2,...,Xn)
.
Step5. תStep2,ѭִStep24.
3 ϵͳṹ
Ͻ㷨,ǿƳӦṹ.ͼ2ʾ.

ͼ2
Ӧһʵi,οһԤ,ڲ㷨1;ӦϱȻһӦĴʵiԤ,Ԥִ㷨2(ͼF-LNNǻںӵд).ڷֲʽ⻷Ҫƿ,ӸṹͼԿ,ԤʵļԴķͶԴ.ںӵмߵٶȣ1ms,˵ʵϴʱ,ԤĵĵԴȻ.ɼ,Ԥ㷨ṩõĿչ,ĿǰںŵĴģֲʽ⻷3ݣLarge-Scale Distributed Virtual Environmentвοֵ.
4 ʵ
ĵʵΪǡԤ⡱,ʵΪĺ۱ֽϻ,Ҫܳ״̬ʷ,һֻ費10.,ʵռкӵѧϰ̷ǳѸ,10,ֻҪ100200ѭѧϰʹ.״̬5ʱ,ļĿǰĸߵPCֻ費1msʱ,˸㷨ȫʵʱԤ.
ǶԿռɶΪ2ʵ,Ӳƽ̨10Mbps̫20̨Pentium 200MhzPC,ƽ̨MS Windows95,ʵ4û.,ǶͬʹöζʽֵԤΪ.ڸʵԤ㷨,rֵȡΪ2,NΪ4.,ǿԽж,һĺ.ֱΪ(xn-1,yn-1)(xn,yn),Ը19άĻͺչ:xn-1,yn-1,xn,yn,xn-1.yn-1,xn-1.xn,yn-1.xn,xn.yn,xn.yn-1,xn-1.yn,xn.yn,cos(3.xn-1),cos(3.yn-1),cos(3.xn),cos(3.yn),cos(8.xn-1.yn-1),cos(8.xn-1.yn),cos(13.xn.yn),cos(13.xn.yn-1),ʵʱԤµ״̬(xn+1,yn+1),ͼ3ʾ.

ͼ3Ԥ㷨4ûʹõĽ
ʵ,㷨ûݵ궼ܺܺõؽԤ,Ҹ㷨Ԥ⾫ڶʽֵԤ㷨.ֽԭԤܹʵʱ޸Ȩֵ,ʹ֮ڲͬʱ̽Ӧ.ģʵĿϴ£,103,㷨Խʡ50%70%һͨ,ʵһԤCPUʱ2.43.0s.Ƕڴģϵͳ(ʵ105),ģԱ,Ԥ㷨ϵļر޴,Ҫǿĵ֧.,ڴͳDR㷨Ԥ,״̬ɱʾΪʽʱ亯ʵ,㷨ҲɺܺõؽԤ,Ĳ׸.
5  
1 һֲúмƵ,صǲõ˽ṹͦѧϰ,ٶȷǳ.ĸһںӵԤ㷨ڶԷֲʽ⻷еʵ״̬ʵʱԤ,˷˴ͳDR㷨Ԥ޷ģ͵ȱ.ʵ,ɶΪ,㷨Ժܺõع.
2ڷֲʽ⻷,Ҫƿ.ĻںӵԤ㷨,ϵͳܺͿչ.
ͨѶϵ:赫, 310027,㽭ѧ CAD&CG صʵ
߼飺赫,1974,˶ʿ,ҪоΪCSCW,ý,ģֲʽ⻷.ʷ,1964,ʦ,ҪоΪý,ʵ.ʯӢ,1937,,ʿʦ,ҪоΪͼѧ,ϵṹ,ʵ.
ߵλ赫㽭ѧ CAD&CG صʵ  310027
ʷ ʯӢ㽭ѧѧ빤ѧϵ  310027
ο
1 Pentland A P. Computational complexity versus simulated environments. Computer Graphics, 1990,24(2):185192
2 Pratt D R. A software architecture for the construction and management of real time virtual environments Ph.D. Thesis. Monterey, California: Naval Postgraduate School, 1993
3 Macedonia M R. A network software architecture for large scale virtual environments Ph.D Thesis. Monterey, California: Naval Postgraduate School, 1995
4 ()Լ.Ӧģʽʶ.:ѧ,1992
(Pao Yoh-han. Adaptive Pattern Recognition and Neural-networks. Massachusetts, Menlo Park: Addison-Wesley Publishing Company Inc., 1989. 192215)
5 Pao Yoh-han, Yoshiyasu Takefuji. Functional-link net computing: theory, system architecture, and functionalities. Computer, 1992,25(5):7679
6 Baumgartner, Eric T, Skaar, Steven B. An autonomous vision-based mobile robot. IEEE Transactions on Automatic Control, 1994,39(3):493502
1998-06-02յԭ,1998-09-16յ޸ĸ
