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

1. 引言

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

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

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

2. 環(huán)境建模                                                       

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

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

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





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

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

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

3.1 路徑編碼方法

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