路徑規(guī)劃算法的研究.pdf

1、路徑規(guī)劃就是指按照先驗(yàn)知識(shí)，在滿足一定約束條件下，從有障礙物的環(huán)境中規(guī)劃出一條從起點(diǎn)到終點(diǎn)的無碰撞路徑。它在機(jī)器人學(xué)，地理信息系統(tǒng)，G IS等眾多領(lǐng)域有廣泛的運(yùn)用，對(duì)它的研究有重要的意義。路徑規(guī)劃問題包括環(huán)境表達(dá)、規(guī)劃方法、路徑搜索策略三個(gè)方面，環(huán)境表達(dá)研究如何有效表示環(huán)境信息；規(guī)劃方法研究如何把環(huán)境模型抽象為數(shù)學(xué)模型；路徑搜索策略研究求解滿足約束條件的路徑的技術(shù)。本文從這三個(gè)角度對(duì)路徑規(guī)劃問題進(jìn)行研究，主要工作包括：
　　 1

2、深入研究了基于可視圖法的全局路徑規(guī)劃。將路徑規(guī)劃問題轉(zhuǎn)換為用枚舉類型搜索算法搜尋從起點(diǎn)到終點(diǎn)的最短路徑問題。并且對(duì)搜索算法做出了基于數(shù)據(jù)儲(chǔ)存結(jié)構(gòu)、存儲(chǔ)空間和搜索方向三個(gè)方面的改進(jìn)，以達(dá)到降低時(shí)間復(fù)雜度，提高搜索效率的目的。
　　 2環(huán)境表達(dá)是路徑規(guī)劃的核心問題之一，在保證環(huán)境信息不丟失的情況下盡可能簡(jiǎn)化環(huán)境模型是提高規(guī)劃效率的重要手段。環(huán)境模型的復(fù)雜程度是與環(huán)境中障礙物頂點(diǎn)數(shù)目密切相關(guān)的。因此，在環(huán)境表達(dá)的過程中，減少障礙物頂點(diǎn)

3、數(shù)目是提高規(guī)劃效率的一個(gè)重要環(huán)節(jié)。本文提出一種基于導(dǎo)數(shù)方法的最小外接矩形法。該方法可以有效將環(huán)境中任意障礙物多邊形的頂點(diǎn)數(shù)目下降為四個(gè)，這樣就大大降低了環(huán)境模型的復(fù)雜程度。
　　 3遺傳算法是近年來智能算法的研究熱點(diǎn)，也是目前路徑規(guī)劃研究中應(yīng)用較多的一種搜索策略。但在環(huán)境復(fù)雜，障礙物數(shù)目較多的情況下，會(huì)出現(xiàn)初始種群規(guī)模龐大，適應(yīng)度函數(shù)區(qū)分度不高，遺傳算子設(shè)計(jì)不合理的缺陷，本文設(shè)計(jì)了具備明確物理意義的適應(yīng)度函數(shù)和遺傳算子，通過仿真

4、實(shí)驗(yàn)表明，該方法能夠切實(shí)有效搜索出最短路徑。
　　 4粗糙集理論是波蘭學(xué)者Z.Pawlak在1982年提出的，它是一種刻劃不完整性和不確定性的數(shù)學(xué)工具，能有效地分析不精確，不一致(ineon sistent)，不完整(incomplete)等各種不完備的信息，還可以對(duì)數(shù)據(jù)進(jìn)行分析和推理，從中發(fā)現(xiàn)隱含的知識(shí)，揭示潛在的規(guī)律。遺傳算法在規(guī)劃多障礙物復(fù)雜環(huán)境中的路徑時(shí)最容易出現(xiàn)的問題就是產(chǎn)生規(guī)模龐大的初始種群。本文引入粗糙集軟計(jì)算方法