模擬退火算法.pdf

《模擬退火算法.pdf》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于柵格法-模擬退火法的機(jī)器人路徑規(guī)劃123鄭秀敏顧大鵬劉相術(shù)（1.北京航空材料研究院，北京100095；2.滄州師范?？茖W(xué)校，滄州061001；3.北京機(jī)械工業(yè)學(xué)院，北京，100085）摘要：路徑規(guī)劃是機(jī)器人技術(shù)中的重要組成部分，分全局路徑規(guī)劃和局部路徑規(guī)劃。本文將柵格法與模擬退火法結(jié)合，采用柵格法表示環(huán)境信息。局部路徑規(guī)劃主要基于模擬退火法，使路徑跳出局部極小點(diǎn)，到達(dá)目標(biāo)位置。關(guān)鍵詞：機(jī)器人路徑規(guī)劃模擬退火法柵格法中圖分類號(hào)：TP273文獻(xiàn)標(biāo)示碼：ARobotPathPlanningBasedonGridMethodwithSimulatedAnnealingAbs

2、tract：Pathplanningisoneofimportanttopicsinrobotics.Ithastwoessentialsorts.Oneisglobalpathplanning,andtheotherislocalpathplanning.Inthepaperthegrid,methodiscombinedwithsimulatedannealing.Weusegridmethodtodenotetheenvironments’informationThelocalpathplanningchieflybasedonsimulatedannealing

3、,inordertoescapethelocalminimumandarrivetargetposition.Keywords：RobotPathPlanningSimulatedAnnealingGridMethod1引言[1]機(jī)器人路徑規(guī)劃是按著一定的法則搜索一條從起點(diǎn)到終點(diǎn)的安全最優(yōu)行走路線，它是機(jī)器人導(dǎo)航技術(shù)中的重要組成部分。依據(jù)機(jī)器人對(duì)周圍工作環(huán)境信息的感知程度，機(jī)器人路徑規(guī)劃分為兩類：一類是基于環(huán)境信息完全知道的路徑規(guī)劃；一類是基于不確定環(huán)境下的路徑規(guī)劃。如果把機(jī)器人看作要研究的問題的某種狀態(tài)，把障礙物看作問題的約束條件，而無碰撞路徑則為滿足約束條件的解，那

4、么路徑規(guī)劃就是一種多約束的問題求解過程。目前用于路徑規(guī)劃的算法很多主要有人工勢(shì)場(chǎng)法、自由空間法、環(huán)境地圖法、可視圖法，此外近幾年遺傳算法、蟻群算法、人工智能也被用于機(jī)器人路徑規(guī)劃。這些算法存在一定的應(yīng)用局限性，規(guī)劃出來的結(jié)果也非全局最優(yōu)。本文將柵格法與模擬退火法結(jié)合，采用柵格法表示環(huán)境信息，利用模擬退火法進(jìn)行局部路徑規(guī)劃使路徑跳出局部極小點(diǎn)，到達(dá)目標(biāo)位置。2柵格法和模擬退火法的基本思想[2]柵格法是由W.E.Howden在1968年提出的.在進(jìn)行路徑規(guī)劃時(shí)采以柵格(grid)為單位表示環(huán)境信息,在處理障礙物的邊界時(shí),避免了復(fù)雜的計(jì)算?？梢钥闯鰱鸥竦拇笮≈苯佑绊懼?guī)劃時(shí)間

5、的長(zhǎng)短和精度,柵格劃分越小,障礙物的表示會(huì)越精確,但同時(shí)會(huì)占用大量的存儲(chǔ)空間,算法的搜索范圍將按指數(shù)增加。柵格的劃分太大,規(guī)劃的路徑會(huì)很不精確.[3]模擬退火算法是將退火思想引入組合優(yōu)化領(lǐng)域，提出的一種大規(guī)模組合優(yōu)化問題的有效近似算法，該算法模仿固體物質(zhì)的退火過程。眾所周知,高溫物體降溫時(shí)其內(nèi)能隨之下降,如果降溫過程充分緩慢,則在降溫過程中物質(zhì)體系始終處于平衡狀態(tài),從而降到某一低溫時(shí)其內(nèi)能為最??；反之降溫太快,則降到同一低溫時(shí)會(huì)保持內(nèi)能。模仿退火過程的尋優(yōu)方法稱為模擬退火算法。模擬退火法的基本步驟如下:(1)給定初始溫度T,及初始點(diǎn),計(jì)算該點(diǎn)的函數(shù)值f(x)。0'(2)

6、隨機(jī)產(chǎn)生擾動(dòng)?x，得到新點(diǎn)x'=+?xx，計(jì)算新點(diǎn)函數(shù)值f(x),及函數(shù)值差。?=ffxfx(')?()(3)若?≤f0，則接受新點(diǎn),作為下一次模擬的初始點(diǎn);???f(4)若?>f0，則計(jì)算新點(diǎn)接受概率:pf()?=exp???產(chǎn)生[0,1]區(qū)間上均勻分布的偽隨機(jī)數(shù)r，??KT?r∈[0,1],如果p()?≥fr,則接受新點(diǎn)作為下一次模擬的初始點(diǎn);否則放棄新點(diǎn),仍取原來的點(diǎn)作為下一次模擬的初始點(diǎn)，然后轉(zhuǎn)（2）步，重復(fù)此過程。收稿日期：基金項(xiàng)目：北京市教委科技發(fā)展計(jì)劃項(xiàng)目[KM200311232138]作者簡(jiǎn)介：鄭秀敏(1976－)，女，河北唐山人，碩士，主要從事機(jī)械設(shè)計(jì)

7、及理論方面的研究。1模擬退火法具有以下的優(yōu)點(diǎn)：（1）模擬退火法不依賴于初始解。盡管在開始計(jì)算時(shí)模擬退火法需要一個(gè)初始解，但它在求解過程中能接受壞解，因此它不會(huì)局限于初始解所在的收斂域內(nèi)。（2）模擬退火法得到的解雖然不一定是最優(yōu)解，但一定是全局的次優(yōu)解。原因是在計(jì)算過程中，壞解始終都有可能被接受，，因此算法能跳出局部極小值點(diǎn)。3算法的實(shí)現(xiàn)首先作如下假設(shè)。（1）把機(jī)器人簡(jiǎn)化成長(zhǎng)為L(zhǎng)，寬為B的矩形，如圖二所示。（2）機(jī)器人在二維空間內(nèi)運(yùn)動(dòng)，機(jī)器人通過其視覺系統(tǒng)能感知自己目前的位姿和障礙物的位置。（3）所有的障礙物為凸多邊形。（4）從起點(diǎn)到終點(diǎn)至