今日頭條
官方微信
官方抖音
案例頻道1.
引言自主機器人的路徑規劃是指:有一臺機器人及其環境描述,要規劃出一條從已知的起始位置出發、繞過障礙物、到達預先規定的終止位置、并滿足某些優化條件的路徑。仿真系統對于移動機器人路徑規劃的研究具有重要的作用，一般用來驗證算法的最優性、安全性、可達性。很多學者對路徑規劃仿真做了大量的研究并提出一些方法，常用的有柵格法和人工勢場法等，但這些算法都存在著一些算法本身的局限性。柵格法當空間增大時所需存儲空間劇增，決策速度慢。人工勢場法結構簡單、便于底層實時控制，但它在障礙物前震蕩，在狹窄通道中擺動，經常陷入陷阱區域，可使機器人在到達目標前就停車。而遺傳算法是一種多點搜索算法，相對柵格法和人工勢場法，更有可能搜索到全局最優解。
但傳統的遺傳算法也存在著早熟收斂和收斂速度慢這兩個難題。早熟收斂導致產生局部最優值，而收斂速度慢是影響遺傳算法應用在實時性要求比較高的環境中的一個瓶頸因素[1]。本文針對上面提到的兩個問題，將改進遺傳算法和簡單圖搜索方法相結合，減少了搜索的盲目性，并且對遺傳算法從改進選擇方式和動態確定變異概率兩個方面考慮，選擇操作采用最優保存策略，局部出現相似個體之后實施災變操作，并且根據個體適應度函數值的大小動態
確定變異概率，這樣既不增加群體規模，避免運算時間過長，還能保證收斂到全局最優解，有效地克服了傳統遺傳算法的缺點。
2. 環境建模
首先根據任務和基本地圖建立環境模型，即將現實世界的問題進行抽象后建立相關的模型。本文采用鏈接圖法[2]
(MAKLINK Graph)建模，它在構造規劃空間時假設移動機器人在二維平面環境中運動；規劃環境的邊界及障礙物可用凸多邊形描述；機器人用點來表示[3]。在圖1所示的環境中，黑色多邊形表示環境中的障礙物。
圖1 有障礙物的環境 
圖2 對環境的鏈接圖表示
鏈接圖法對自由空間進行建模的過程為：取各障礙物頂點連線的中點為可能路徑點，相互連接各可能路徑點，并將機器人移動時的起點和終點分別連接到各個可能的路徑點上。對圖1所示含有障礙物的環境，經過上述算法處理后，可得到圖2的鏈接圖，其中P1為起點，P19為終點。所有可能路徑點和之間連線形成的網絡圖即為機器人可自由行走的路線，即得到一個帶權無向圖，機器人的全局路徑規劃即轉化為在網絡圖2中尋找從P1點到P19點的最短路徑，采用E．W．Dijkstra(狄克斯特拉)算法可以在一個給定的帶權無向圖中去求連接起點和終點的最短路徑和最短路徑的長度，得到最短路徑規劃結果。
3. 應用于路徑規劃中的改進的遺傳算法[3,5,6]
3.1 路徑編碼方法
如圖2 所示, 通過EW.Dijkstra(迪克斯特拉)算法得到了鏈接圖中的最短路徑為：P1,P2……Pn,P19,其中P1為路徑的起點,P19 為路徑的終點, 由于鏈接圖法連接的是凸多邊形的中點，基于上述方法通常得不到最短的規劃路徑，需要對P1,P2……Pn,P19 的位置進行調整, 從而得到機器人在工作空間的最優或近似最優的行走路徑。用遺傳算法優化時，我們讓各路徑點在相應障礙物端點連線上滑動。
北京市公安局海淀分局備案號：11010802023656號