日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

1. 引言

    自主機器人的路徑規(guī)劃是指:有一臺機器人及其環(huán)境描述,要規(guī)劃出一條從已知的起始位置出發(fā)、繞過障礙物、到達(dá)預(yù)先規(guī)定的終止位置、并滿足某些優(yōu)化條件的路徑。仿真系統(tǒng)對于移動機器人路徑規(guī)劃的研究具有重要的作用，一般用來驗證算法的最優(yōu)性、安全性、可達(dá)性。很多學(xué)者對路徑規(guī)劃仿真做了大量的研究并提出一些方法，常用的有柵格法和人工勢場法等，但這些算法都存在著一些算法本身的局限性。柵格法當(dāng)空間增大時所需存儲空間劇增，決策速度慢。人工勢場法結(jié)構(gòu)簡單、便于底層實時控制，但它在障礙物前震蕩，在狹窄通道中擺動，經(jīng)常陷入陷阱區(qū)域，可使機器人在到達(dá)目標(biāo)前就停車。而遺傳算法是一種多點搜索算法，相對柵格法和人工勢場法，更有可能搜索到全局最優(yōu)解。

但傳統(tǒng)的遺傳算法也存在著早熟收斂和收斂速度慢這兩個難題。早熟收斂導(dǎo)致產(chǎn)生局部最優(yōu)值，而收斂速度慢是影響遺傳算法應(yīng)用在實時性要求比較高的環(huán)境中的一個瓶頸因素^[1]。本文針對上面提到的兩個問題，將改進(jìn)遺傳算法和簡單圖搜索方法相結(jié)合，減少了搜索的盲目性，并且對遺傳算法從改進(jìn)選擇方式和動態(tài)確定變異概率兩個方面考慮，選擇操作采用最優(yōu)保存策略，局部出現(xiàn)相似個體之后實施災(zāi)變操作，并且根據(jù)個體適應(yīng)度函數(shù)值的大小動態(tài)

確定變異概率，這樣既不增加群體規(guī)模，避免運算時間過長，還能保證收斂到全局最優(yōu)解，有效地克服了傳統(tǒng)遺傳算法的缺點。

2. 環(huán)境建模                                                       

首先根據(jù)任務(wù)和基本地圖建立環(huán)境模型，即將現(xiàn)實世界的問題進(jìn)行抽象后建立相關(guān)的模型。本文采用鏈接圖法^[2]

(MAKLINK Graph)建模，它在構(gòu)造規(guī)劃空間時假設(shè)移動機器人在二維平面環(huán)境中運動；規(guī)劃環(huán)境的邊界及障礙物可用凸多邊形描述；機器人用點來表示^[3]。在圖1所示的環(huán)境中，黑色多邊形表示環(huán)境中的障礙物。

                        圖1  有障礙物的環(huán)境                       





圖2  對環(huán)境的鏈接圖表示

    鏈接圖法對自由空間進(jìn)行建模的過程為：取各障礙物頂點連線的中點為可能路徑點，相互連接各可能路徑點，并將機器人移動時的起點和終點分別連接到各個可能的路徑點上。對圖1所示含有障礙物的環(huán)境，經(jīng)過上述算法處理后，可得到圖2的鏈接圖，其中P₁為起點，P₁₉為終點。所有可能路徑點和之間連線形成的網(wǎng)絡(luò)圖即為機器人可自由行走的路線，即得到一個帶權(quán)無向圖，機器人的全局路徑規(guī)劃即轉(zhuǎn)化為在網(wǎng)絡(luò)圖2中尋找從P₁點到P₁₉點的最短路徑，采用E．W．Dijkstra(狄克斯特拉)算法可以在一個給定的帶權(quán)無向圖中去求連接起點和終點的最短路徑和最短路徑的長度，得到最短路徑規(guī)劃結(jié)果。

3. 應(yīng)用于路徑規(guī)劃中的改進(jìn)的遺傳算法^[3,5,6]

3.1 路徑編碼方法

如圖2 所示, 通過EW.Dijkstra(迪克斯特拉)算法得到了鏈接圖中的最短路徑為：P₁,P₂……P_n,P₁₉,其中P₁為路徑的起點,P₁₉ 為路徑的終點, 由于鏈接圖法連接的是凸多邊形的中點，基于上述方法通常得不到最短的規(guī)劃路徑，需要對P₁,P₂……P_n,P₁₉ 的位置進(jìn)行調(diào)整, 從而得到機器人在工作空間的最優(yōu)或近似最優(yōu)的行走路徑。用遺傳算法優(yōu)化時，我們讓各路徑點在相應(yīng)障礙物端點連線上滑動。