裝配路徑規(guī)劃中基于動(dòng)態(tài)坐標(biāo)的A_搜索算法

1、第8卷第4期2002年4月計(jì)算機(jī)集成制造系統(tǒng)CIMSComputerIntegratedManufacturingSystemsVol.8No.4Apr.2002文章編號(hào):1006-5911(2002)04-0316-04裝配路徑規(guī)劃中基于動(dòng)態(tài)坐標(biāo)的A3搜索算法田立中,付宜利,馬玉林,謝龍(哈爾濱工業(yè)大學(xué)機(jī)電學(xué)院,黑龍江哈爾濱150001)摘要:在裝配路徑規(guī)劃中,最常用的方法是A3搜索算法。通過(guò)兩個(gè)實(shí)例說(shuō)明在實(shí)體模型空間中,由于節(jié)點(diǎn)的擴(kuò)展方向和運(yùn)動(dòng)方向不一致,導(dǎo)致A3算法失敗和算法復(fù)雜性的增加。在總結(jié)傳統(tǒng)的A3搜索算法的基礎(chǔ)上,本文提出了動(dòng)態(tài)坐標(biāo)的A3搜索算法。通過(guò)變換坐標(biāo),使節(jié)點(diǎn)擴(kuò)展方向和運(yùn)

2、動(dòng)方向始終保持一致,從而解決了由于節(jié)點(diǎn)擴(kuò)展方向和被規(guī)劃物體運(yùn)動(dòng)方向不一致所導(dǎo)致的算法失敗。最后給出了變換坐標(biāo)的原則,證明了動(dòng)態(tài)坐標(biāo)的A3搜索算法的收斂性,并進(jìn)行了復(fù)雜性分析。關(guān)鍵詞:A3搜索算法;動(dòng)態(tài)坐標(biāo);裝配路徑規(guī)劃中圖分類號(hào):TP305;O18文獻(xiàn)標(biāo)識(shí)碼:A0引言術(shù),為此,、J函數(shù)法、拓?fù)浣稻S法等。隨著計(jì)算機(jī)軟硬件技術(shù)的發(fā)展,使快速進(jìn)行干涉計(jì)算已成為可能。這為在三維實(shí)體模型環(huán)境下直接使用A搜索算法和干涉檢查進(jìn)行路徑規(guī)劃創(chuàng)造了條件。在路徑規(guī)劃中,A3搜索算法一般過(guò)程可概述為1,2;open表排序;(9)轉(zhuǎn)到步驟(1)。對(duì)于三維路徑規(guī)劃,擴(kuò)展節(jié)點(diǎn)的代價(jià)可用式(1)做估價(jià)函數(shù)計(jì)算3。h(n)=(

3、tx-nx)2+(ty-ny)2+(tz-nz)2(1)3式中:n表示當(dāng)前節(jié)點(diǎn);tx,ty和tz分別是目標(biāo)T的x,y和z的坐標(biāo);nx,ny和nz分別是要計(jì)算點(diǎn)的x,y和z的坐標(biāo)。:(1)將起始點(diǎn)放入到open表中;(2)在open表中取出第一個(gè)搜索節(jié)點(diǎn);(3)判斷open表是否為空,如果為空,算法失在三維實(shí)體模型環(huán)境下使用A3搜索算法,擴(kuò)展節(jié)點(diǎn)的方法非常重要,在特定條件下可決定算法成功與否。敗;(4)判斷當(dāng)前點(diǎn)是否是目標(biāo),如果是目標(biāo),算法1擴(kuò)展節(jié)點(diǎn)的一般方法在三維幾何空間中,對(duì)于沒(méi)有旋轉(zhuǎn)的運(yùn)動(dòng)規(guī)劃,節(jié)點(diǎn)的擴(kuò)展方法如圖1所示3-5。設(shè)圖1中擴(kuò)展的起點(diǎn)為O,以O(shè)為中心向四周擴(kuò)展出26個(gè)點(diǎn)。設(shè)每個(gè)節(jié)

4、點(diǎn)為vi(i=1,2,26),稱vi為O的子節(jié)點(diǎn)。向量OViO-vi(i=1,2,26)形成了一個(gè)擴(kuò)展方向集合D=OVii=1,2,26,稱D中的任何一個(gè)元素為成功結(jié)束;(5)將運(yùn)動(dòng)體移動(dòng)到這個(gè)節(jié)點(diǎn)上,判斷是否與障礙體干涉。如果干涉,運(yùn)動(dòng)體回退,放棄當(dāng)前點(diǎn),并將其從open表中刪除,轉(zhuǎn)到步驟(2);(6)將當(dāng)前節(jié)點(diǎn)放入到closed表中;(7)擴(kuò)展當(dāng)前節(jié)點(diǎn),并將新產(chǎn)生的節(jié)點(diǎn)放入到收稿日期:2001-04-26;修訂日期:2001-07-16。作者簡(jiǎn)介:田立中(1973-),男,河南三門峽人,哈爾濱工業(yè)大學(xué)機(jī)電學(xué)院博士研究生,主要從事裝配規(guī)劃和計(jì)算機(jī)輔助公差等研究。E-mail:fms。第4期田

5、立中等:裝配路徑規(guī)劃中基于動(dòng)態(tài)坐標(biāo)的A3搜索算法317節(jié)點(diǎn)O的一個(gè)擴(kuò)展方向。連接O和vi的線段是路徑的微觀表現(xiàn)。2問(wèn)題的提出利用上述的節(jié)點(diǎn)擴(kuò)展方法,在三維實(shí)體造型的環(huán)境下應(yīng)用A3搜索算法進(jìn)行路徑規(guī)劃,會(huì)遇到以下兩個(gè)問(wèn)題。211孔軸配合的路徑規(guī)劃對(duì)于圖2中的螺栓和螺孔的配合,螺栓要從與之配合的螺孔中運(yùn)動(dòng)出來(lái),如果節(jié)點(diǎn)的擴(kuò)展不正確,就會(huì)導(dǎo)致路徑規(guī)劃的失敗。值也不為零。當(dāng)軸孔配合的間隙小于時(shí),螺栓就和螺孔發(fā)生干涉。在這種情況下,任何一個(gè)擴(kuò)展點(diǎn)都不是可用的節(jié)點(diǎn),也就是說(shuō)不存在可行路徑。這顯然是錯(cuò)誤的,使本來(lái)可搜索路徑的方法變成不收斂的方法。只有當(dāng)步長(zhǎng)小于求解干涉的誤差時(shí),在運(yùn)動(dòng)一個(gè)步長(zhǎng)后,不會(huì)發(fā)生干涉

6、。但在實(shí)踐中,將步長(zhǎng)減少到非常小是不現(xiàn)實(shí)的。而在軸孔之間沒(méi)有間隙時(shí),則必須要求式(2)的值為零,即節(jié)點(diǎn)的一個(gè)擴(kuò)展方向必須和孔軸的軸線平行。212路徑規(guī)劃中的直線運(yùn)動(dòng)在路徑規(guī)劃過(guò)程中,當(dāng)運(yùn)動(dòng)方向和節(jié)點(diǎn)擴(kuò)展的方向不一致時(shí),即使是在直線運(yùn)動(dòng)情況下,也會(huì)增加規(guī)劃的節(jié)點(diǎn)數(shù),從而導(dǎo)致搜索算法效率降低。下面以一個(gè)二維空間的例子加以闡述(如圖4)。螺栓要從與之配合的螺孔中運(yùn)動(dòng)出來(lái)時(shí),螺栓必須沿著孔(軸)的軸線運(yùn)動(dòng)。但是,如果利用傳統(tǒng)的節(jié)點(diǎn)擴(kuò)展方法(如圖1),當(dāng)擴(kuò)展方向和運(yùn)動(dòng)方向不一致時(shí),就會(huì)導(dǎo)致規(guī)劃失敗。圖3為螺栓從與之配合的螺孔中運(yùn)動(dòng)出來(lái)的示意圖。圖3中,螺栓和螺孔的配合方向表示單位向量 K,也即 K為螺栓

7、的軸線方向。W表示軸運(yùn)動(dòng)一個(gè)步長(zhǎng)后,運(yùn)動(dòng)前后軸的幾何中心的距離。由圖4可見(jiàn),運(yùn)動(dòng)體從A點(diǎn)運(yùn)動(dòng)到B點(diǎn)。當(dāng)運(yùn),也即:OVi K0( K為運(yùn)動(dòng)方向)(3)那么,規(guī)劃出的路徑將是一條曲折路徑(如圖4a)。在路徑規(guī)劃完畢后,還要對(duì)這條曲折的路徑進(jìn)行修剪,使之盡量減少轉(zhuǎn)折次數(shù)。利用動(dòng)態(tài)坐標(biāo)的3搜索算法,在擴(kuò)展節(jié)點(diǎn)前進(jìn)行坐標(biāo)變換,使OVi K=0就可以消除這種現(xiàn)象(如圖4b)。3動(dòng)態(tài)坐標(biāo)的A3搜索算法根據(jù)上面的分析,產(chǎn)生問(wèn)題的原因是由于運(yùn)動(dòng)體運(yùn)動(dòng)方向和節(jié)點(diǎn)擴(kuò)展方向不一致的結(jié)果。針對(duì)這一原因,在擴(kuò)展時(shí)檢查節(jié)點(diǎn)擴(kuò)展方向和運(yùn)動(dòng)方向是否一致。如果不一致,通過(guò)變換坐標(biāo)系,使擴(kuò)展節(jié)點(diǎn)的方向和運(yùn)動(dòng)方向相同,即式(2)中的

8、為零。圖5為基于動(dòng)態(tài)坐標(biāo)的A3搜索算法的流程圖。動(dòng)態(tài)坐標(biāo)的A3搜索算法的優(yōu)點(diǎn)在于:33(4)f(ni)f(ni)表示從初始節(jié)點(diǎn)S出發(fā),約束通過(guò)節(jié)式中:f3(點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)T上的最小耗散值;ni表示坐對(duì)于OViD(i=1,2,26),當(dāng)OVi K0。當(dāng)K螺栓被按照擴(kuò)展方向移動(dòng)一個(gè)步長(zhǎng)時(shí),螺栓的軸線和螺孔的軸線偏離的距離為:=W(2)sinOVi0時(shí),也即存在夾角=cos-1OVi K318計(jì)算機(jī)集成制造系統(tǒng)CIMS第8卷地解決本文提出的問(wèn)題。對(duì)于孔軸的路徑規(guī)劃問(wèn)題,由于節(jié)點(diǎn)擴(kuò)展方向和孔(軸)的軸線方向一致,從根本上解決了由于節(jié)點(diǎn)擴(kuò)展所導(dǎo)致的搜索不收斂。對(duì)于路徑規(guī)劃中的直線運(yùn)動(dòng)問(wèn)題,可將節(jié)點(diǎn)擴(kuò)展

9、的方向變換到物體的運(yùn)動(dòng)方向,如圖4b所示,則規(guī)劃出來(lái)的路徑將比較平直,從而避免了路徑修剪過(guò)程。4動(dòng)態(tài)坐標(biāo)的A3搜索算法性能分析411動(dòng)態(tài)坐標(biāo)的A3搜索算法性能分析當(dāng)在算法A的估價(jià)函數(shù)中,使用的啟發(fā)函數(shù)h(n)是處在h3(n)的下界范圍,即滿足h(n)h3(n)時(shí),這個(gè)算法稱為算法A3。標(biāo)變換前的節(jié)點(diǎn);ni事實(shí)上,ni和ni,在的坐標(biāo)系不同(A3A3算法短。因?yàn)閺闹庇^上看,動(dòng)態(tài)坐標(biāo)的A3搜索算法產(chǎn)生的路徑是傳統(tǒng)算法經(jīng)過(guò)修剪過(guò)的結(jié)果。動(dòng)態(tài)坐標(biāo)的A3搜索算法和傳統(tǒng)的A3搜索算法的主要不同是擴(kuò)展節(jié)點(diǎn)的方法。在動(dòng)態(tài)坐標(biāo)方法中,變換坐標(biāo)的策略很重要,它決定了算法效率。坐標(biāo)變換的原則是:1)設(shè)D 為被規(guī)劃對(duì)

10、象的運(yùn)動(dòng)方向,OViD(其中D為擴(kuò)展方向集合),如果OViD 0,。D,使得OViD,OViD =0。D 表示坐標(biāo)變命題1采用式(1)為估價(jià)函數(shù)動(dòng)態(tài)坐標(biāo)的A3搜索算法,是一種A3搜索算法。證明:因?yàn)槭?1)計(jì)算的是兩點(diǎn)間的直線距離,所以必有(5)nn),所以動(dòng)態(tài)坐標(biāo)的3。命題2采用式(1)為估價(jià)函數(shù)的動(dòng)態(tài)坐標(biāo)的A3搜索算法滿足單調(diào)限制條件。證明:對(duì)于一個(gè)估價(jià)函數(shù)h,如果對(duì)所有的節(jié)點(diǎn)ni和nj(nj是ni的子節(jié)點(diǎn)),都有:h(ni)-h(nj)C(ni,nj)(6)則稱估價(jià)函數(shù)h滿足單調(diào)限制條件。其中C(ni,nj)表示ni到nj的弧線耗散值。將式(1)代入式(6)的左邊,并根據(jù)三角形的性質(zhì),可

11、以得到式(7):(tx-nix)2+(ty-niy)2+(tz-niz)2-(tx-njx)2+(ty-njy)2+(tz-njz)2<(nix-njx)2+(nix-njy)2+(nix-njz)2(7)換之后的運(yùn)動(dòng)方向。(2) T,則對(duì)于OViD,如果OVi T0,得到新的擴(kuò)展方向集合D,使得OViD,OVi T=0。 T表示坐標(biāo)變換之后的指向目標(biāo)位置的方向。(3)當(dāng)D 和 T相互垂直時(shí),取D 和 T為新擴(kuò)展方向集合D的坐標(biāo)架。當(dāng)D 和 T相互不垂直時(shí),以D 的方向?yàn)樽鴺?biāo)方向,參照規(guī)則(2)進(jìn)行坐標(biāo)變換。因?yàn)镈 方向是根據(jù)零件之間的接觸關(guān)系計(jì)算出來(lái)的局部拆卸方向。利用上述原則,動(dòng)態(tài)啟

12、發(fā)式搜索算法可以很好式(7)的右邊是C(ni,nj)的估計(jì),故有(nix-njx)2+(nix-njy)2+(nix-njz)2C(ni,nj)(8)(9)聯(lián)合式(7)和式(8),有h(ni)-h(nj)C(ni,nj)故命題得證。動(dòng)態(tài)坐標(biāo)的A3搜索算法由于具有式(4)的性質(zhì),這是動(dòng)態(tài)坐標(biāo)的A3搜索算法比A3搜索算法性能好的地方。在證明式(4)之前,先闡述如下定理。定理:若估價(jià)函數(shù)h(n)滿足單調(diào)限制條件,則算法擴(kuò)展了節(jié)點(diǎn)h之后,就找到了到達(dá)節(jié)點(diǎn)n的最第4期田立中等:裝配路徑規(guī)劃中基于動(dòng)態(tài)坐標(biāo)的A3搜索算法319佳路徑。即若A3選n來(lái)擴(kuò)展,在單調(diào)限制條件下,有g(shù)(n)=g3(n)2。命題3坐標(biāo)

13、變換后,節(jié)點(diǎn)最短路徑耗散值的估計(jì)不大于原來(lái)節(jié)點(diǎn)的最短路徑耗散值的估計(jì),即33f(ni)f(ni)。當(dāng)在搜索過(guò)程中僅有一次坐標(biāo)變換,不妨設(shè)在ni進(jìn)行了坐標(biāo)變換,變換后為ni。則f3(ni)=g3(ni)+h3(ni)(10)(11)(12)33f3(ni)=g(ni)+h(ni)根據(jù)前面的定理,有g(shù)(n)=g3(ni)=g3(ni)次擴(kuò)展節(jié)點(diǎn)之前都要進(jìn)行坐標(biāo)變換,那么,動(dòng)態(tài)坐標(biāo)的A3搜索算法的時(shí)間復(fù)雜性是O(2N)+O(N)。雖然動(dòng)態(tài)坐標(biāo)的A3搜索算法的時(shí)間復(fù)雜性比A3搜索算法高,但是動(dòng)態(tài)坐標(biāo)的A3搜索算法產(chǎn)生的路徑比A3搜索算法平直,基本不需要進(jìn)行路徑剪裁計(jì)算。如果按照文獻(xiàn)2所述的方法進(jìn)行路徑

14、剪裁計(jì)算,則其計(jì)算的時(shí)間復(fù)雜性是O(N2+N)。從總體性能上看,動(dòng)態(tài)坐標(biāo)的A3搜索算法是有較高效率的。5結(jié)論在總結(jié)傳統(tǒng)的A3搜索算法的基礎(chǔ)上,本文提出了基于動(dòng)態(tài)坐標(biāo)的A3搜索算法,用于解決由于節(jié)點(diǎn)擴(kuò)展方向和被規(guī)劃物體運(yùn)動(dòng)方向不一致所導(dǎo)致的算法失敗問(wèn)題。在搜索過(guò)程中判斷運(yùn)動(dòng)方向和目標(biāo)之間的偏差,雖然,提:1蔡自興,徐光.人工智能及其應(yīng)用(第二版)M.北京:清華因?yàn)橹挥幸淮巫鴺?biāo)變換,所以變換后h3(ni)由有限段長(zhǎng)度大于步長(zhǎng)的直線段組成。即h3(ni)=abjjj=1,2,m(13)對(duì)于不做變換的搜索,由于hihi+1D,所以,對(duì)于任意的ajbjj=1,2,m),:3h(nj,nk)ajbj(14

15、)式中:nj表示aj所代表的節(jié)點(diǎn);nk表示b節(jié)點(diǎn)。由式(14)得:h3(ni)大學(xué)出版社,1996.2林堯瑞,馬少平.人工智能導(dǎo)論M.北京:清華大學(xué)出版社,1989.3王偉.障礙環(huán)境下機(jī)器人無(wú)碰自主路徑規(guī)劃的研究D.哈n3j,nk)=h3(ni)(15)當(dāng)在動(dòng)態(tài)坐標(biāo)的A搜索算法中有k(km)次坐標(biāo)變換也是成立的。412動(dòng)態(tài)坐標(biāo)的A3搜索算法時(shí)間復(fù)雜性分析A3搜索算法的時(shí)間復(fù)雜性是O(2N)6,其中N是擴(kuò)展節(jié)點(diǎn)的數(shù)目。因?yàn)樽鴺?biāo)變換的時(shí)間復(fù)雜性是固定的,假設(shè)在動(dòng)態(tài)坐標(biāo)的A3搜索算法中有n坐標(biāo)變換,則動(dòng)態(tài)坐標(biāo)的A3搜索算法的時(shí)間復(fù)雜性為O(2N)+O(n)。按照最壞性能分析,在每爾濱:哈爾濱工業(yè)大學(xué)

16、,1998.4儲(chǔ)林波.面向虛擬裝配的裝配工藝規(guī)劃技術(shù)的研究D.哈爾濱:哈爾濱工業(yè)大學(xué),2000.5熊有倫,丁漢.機(jī)器人無(wú)碰撞運(yùn)動(dòng)的規(guī)劃J.模式識(shí)別與人工智能,1989,(6):15-21.6邢文訓(xùn),謝金星.現(xiàn)代優(yōu)化計(jì)算方法M.北京:清華大學(xué)出版社,2000.A3SearchArithmeticBasedonDynamicCoordinateinAssemblyPathPlanTIANLi-zhong,FUYi-li,MAYu-lin,XIELong(CollegeofMechatronicEngineering,HarbinInstituteofTechnology,Harbin150001,

17、China)Abstract:Theheuristicallysearcharithmeticisoftenusedinassemblypathplanning.Butthearithmeticwillbefailedbecauseofthenon-consistentbetweenthedirectionofmovementandtheexplanddirectionofnode.Weproposedaheuristicallysearcharithmeticbasedondynamiccoordinate.Thearithmeticcankeeptheconsistentbetweenthedirectionofmovementandth