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

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

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

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

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