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

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

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

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

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