亚洲免费av电影一区二区三区,日韩爱爱视频,51精品视频一区二区三区,91视频爱爱,日韩欧美在线播放视频,中文字幕少妇AV,亚洲电影中文字幕,久久久久亚洲av成人网址,久久综合视频网站,国产在线不卡免费播放

        ?

        基于時(shí)間窗模型的雙向機(jī)器人路徑規(guī)劃方法

        2021-12-12 02:52:36琛,茅
        關(guān)鍵詞:柵格遺傳算法沖突

        王 琛,茅 健

        上海工程技術(shù)大學(xué) 機(jī)械與汽車工程學(xué)院,上海 201620

        提起搬運(yùn)設(shè)備,一般人首先想到的無非是叉車、卡車等傳統(tǒng)的搬運(yùn)設(shè)備。隨著智能化與自動化的發(fā)展,制造業(yè)對自動化智能化的需求漸增,對提高制造系統(tǒng)的物流效率,進(jìn)而提高整個(gè)生產(chǎn)系統(tǒng)的生產(chǎn)效率需求更為強(qiáng)烈,機(jī)器人搬運(yùn)車應(yīng)運(yùn)而生[1]。雙驅(qū)雙向機(jī)器人不僅速度快、精度高、可靠性高、操作維護(hù)方便,并且沿預(yù)定軌跡行駛,因而被廣泛使用[2]。物流配送系統(tǒng)優(yōu)化主要是進(jìn)行配送車輛的合理調(diào)度[3]。優(yōu)化后的配送路徑不僅大大提高了企業(yè)倉儲的運(yùn)行效率,而且將人們從繁重的體力勞動中解放出來,同時(shí)也避免了安全事故的發(fā)生[4]。

        宋宇、王志明[5]將RRT算法用于柵格環(huán)境下產(chǎn)生初始路徑,其次提出一種新的插入算子,最后進(jìn)行路徑優(yōu)化。黨宏社、孫心妍[6]采用遺傳算法進(jìn)行機(jī)器人路徑規(guī)劃,并加入物料類型選擇的循環(huán)套,通過多次實(shí)驗(yàn)確定最合理的控制參數(shù),從而產(chǎn)生機(jī)器人運(yùn)輸多種類型物料的最優(yōu)路徑結(jié)果。李天童、寧平凡等[7]在傳統(tǒng)的障礙物柵格地圖中疊加了環(huán)境安全信息,構(gòu)建了融合信息柵格地圖,提出了一種改進(jìn)的遺傳路徑規(guī)劃算法。以上算法都是針對單機(jī)器人路徑規(guī)劃。

        通常在實(shí)際生產(chǎn)時(shí),需要多臺機(jī)器人同時(shí)進(jìn)行貨物運(yùn)輸[8]。因?yàn)槭艿娇臻g和場地的影響,多機(jī)器人不能自由的穿越障礙物,所以多機(jī)器人路徑規(guī)劃就成為眾多挑戰(zhàn)中的一個(gè)[9]。通常所遇到的算法主要有A*算法[10-11]、遺傳算法[12-13]、模擬退火算法[14]、Dijkstra算法[15]等。孟祥忠、劉健等[16]將時(shí)間窗算法和Dijkstra算法相結(jié)合,依次規(guī)劃各機(jī)器人的路徑,并采用實(shí)時(shí)更新位置信息和時(shí)間窗排布的方法對沖突路段進(jìn)行路徑動態(tài)規(guī)劃。雖然能得出最短路徑的最優(yōu)解,但由于它遍歷計(jì)算的節(jié)點(diǎn)很多,所以效率低。袁洋、葉峰等[17]摒棄了傳統(tǒng)A*算法只考慮單一運(yùn)行路程的評價(jià)函數(shù),引入了運(yùn)行路程結(jié)合區(qū)域負(fù)載作為新評價(jià)函數(shù)的方式。在幾乎不增大運(yùn)行路程的前提下,實(shí)現(xiàn)了機(jī)器人運(yùn)行路網(wǎng)的區(qū)域負(fù)載均衡。齊權(quán)、張新敏[18]在分析影響柔性生產(chǎn)車間內(nèi)機(jī)器人運(yùn)行效率因素的基礎(chǔ)上,建立了多機(jī)器人路徑優(yōu)化數(shù)學(xué)模型,并提出一種兩階段的路徑規(guī)劃方法。孫煒等[19]以路徑分割成節(jié)點(diǎn)的方法對A*算法進(jìn)行改進(jìn),雖然可以獲得比遺傳算法更快的解決方案,但很容易陷入一些局部極小值,而遺傳算法總是可以達(dá)到全局最優(yōu)或近似全局最優(yōu)。

        對于多臺機(jī)器人同時(shí)行駛,不僅要使每臺機(jī)器人行駛路徑最短,用時(shí)最少,還要能夠保證機(jī)器人之間的協(xié)作問題[20]。針對以上問題,提出了一種改進(jìn)的遺傳算法。在初始化總?cè)簳r(shí),盡可能使隨機(jī)生成的路徑較短,通過選擇中點(diǎn)的相鄰點(diǎn)擴(kuò)大選擇范圍確保線路連續(xù)。種群適應(yīng)度函數(shù)保證機(jī)器人路徑最短和改進(jìn)路徑平滑度防止轉(zhuǎn)向次數(shù)過多。為了防止遺傳算法陷入局部最優(yōu)解,通過輪盤賭的方法確保一部分非最優(yōu)個(gè)體。在改進(jìn)后的遺傳算法基礎(chǔ)上,對車輛沖突類型進(jìn)行分類處理,明確辨別方法。根據(jù)優(yōu)先級順序,并結(jié)合提出的時(shí)間窗模型,制定對應(yīng)的協(xié)調(diào)方案,以實(shí)現(xiàn)多機(jī)器人物流系統(tǒng)總時(shí)間最少為目標(biāo)的多機(jī)器人路徑規(guī)劃系統(tǒng)。

        1 時(shí)間窗模型說明

        為防止單車道雙向機(jī)器人系統(tǒng)中的沖突,有必要確定每個(gè)正在運(yùn)行的機(jī)器人占據(jù)路段的時(shí)間段,即機(jī)器人系統(tǒng)路徑規(guī)劃的時(shí)間窗口。它的真正含義是從進(jìn)入某個(gè)路徑到離開該路徑的時(shí)間段,在此期間,機(jī)器人有權(quán)延特定方向使用該路徑。在機(jī)器人路徑規(guī)劃中,時(shí)間窗算法由于其簡單性和實(shí)用性而被廣泛使用。

        建立模型的前提條件:

        (1)機(jī)器人可以在每個(gè)路線上沿兩個(gè)方向行駛;

        (2)在路徑的特定狀態(tài)下,機(jī)器人以恒定速度行駛;

        (3)為避免碰撞,沿同一方向行駛的機(jī)器人通過一定的安全措施確定機(jī)器人之間的間隔距離;

        (4)忽略通過交叉點(diǎn)后的減速時(shí)間和加速時(shí)間;

        (5)忽略機(jī)器人從等候站返回路徑的時(shí)間;

        (6)任務(wù)期間忽略機(jī)器人的裝卸時(shí)間;

        (7)任務(wù)的優(yōu)先級可以預(yù)先設(shè)置,通常情況下優(yōu)先級設(shè)置順序?yàn)槿蝿?wù)調(diào)度順序。

        基于以上假設(shè),多機(jī)器人路徑規(guī)劃系統(tǒng)的時(shí)間窗口公式:

        時(shí)間窗口代表一段時(shí)間段及機(jī)器人從進(jìn)入路段到離開路段這段時(shí)間。根據(jù)市面上一些常見的設(shè)備如圖1,確定下列相關(guān)參數(shù):r為彎曲路段上的轉(zhuǎn)彎半徑,取2 m;vz1為空載機(jī)器人在直線路段的速度,通常取3 m/s;vz2為空載機(jī)器人在彎曲路段的速度,通常取1.5 m/s;vl1為運(yùn)貨機(jī)器人在直線路段的速度,通常取2 m/s;vl2為運(yùn)貨機(jī)器人在彎曲路段的速度,通常取1 m/s;ljk表示jk路段的直線距離;表示jk路段的第m個(gè)時(shí)間窗口;表示jk路段的第m個(gè)時(shí)間窗口的開始時(shí)間;表示jk路段的第m個(gè)時(shí)間窗口的結(jié)束時(shí)間。

        圖1 機(jī)器人Fig.1 Robot

        2 基于時(shí)間窗的算法流程

        2.1 建立模型

        根據(jù)上述的條件,定義機(jī)器人物流規(guī)劃系統(tǒng)不能只依據(jù)最短路徑。機(jī)器人物流規(guī)劃系統(tǒng)的最終目標(biāo)是系統(tǒng)所有機(jī)器人完成規(guī)定任務(wù)的時(shí)間最少。它的目標(biāo)函數(shù)是:

        它的約束函數(shù)是:

        參數(shù)說明:n表示倉儲系統(tǒng)中存在的機(jī)器人數(shù);tti表示第i臺機(jī)器人執(zhí)行系統(tǒng)任務(wù)所需的時(shí)間;tci表示第i臺向系統(tǒng)輸入任務(wù)到開始執(zhí)行規(guī)定任務(wù)所花費(fèi)的最少時(shí)間;表示在時(shí)間窗內(nèi)在路段jk上的機(jī)器人數(shù);表示在時(shí)間窗內(nèi)在路段kj上的機(jī)器人數(shù)。

        公式的含義:式(3)表示執(zhí)行任務(wù)的機(jī)器人不大于物流系統(tǒng)中的機(jī)器人數(shù);式(4)和(5)表示在時(shí)間窗內(nèi)在路段jk上的機(jī)器人數(shù);式(6)表示路徑總數(shù)大于物流系統(tǒng)中機(jī)器人數(shù);式(7)表示在時(shí)間窗內(nèi)在路段jk上不存在沿相反方向行駛的機(jī)器人。

        2.2 優(yōu)化后的遺傳算法

        遺傳算法是一種智能優(yōu)化算法,主要用來解決優(yōu)化問題,其主要步驟為種群初始化、適應(yīng)度函數(shù)計(jì)算、選擇、交叉和變異。應(yīng)用于移動機(jī)器人路徑規(guī)劃時(shí)其主要步驟,流程圖如圖2所示。下面將對每步的方法做詳細(xì)介紹。

        圖2 遺傳算法流程圖Fig.2 Flow chart of genetic algorithm

        2.2.1 建立柵格地圖

        在對機(jī)器人進(jìn)行路徑規(guī)劃時(shí),需要先建立地圖。本文通過柵格法建立空間地圖模型,柵格越密集,空間中各種環(huán)境信息表示越精確。

        2.2.2 初始化種群

        初始化種群要求隨機(jī)產(chǎn)生多條可行路徑,可行路徑表示不與障礙物柵格相碰撞的路徑??尚新窂降漠a(chǎn)生分為兩個(gè)主要步驟。

        首先產(chǎn)生一條間斷路徑。機(jī)器人每次行走一個(gè)柵格,因此每一行或者每一列至少有一個(gè)柵格在可行路徑中。所以初始化時(shí)先按順序在每一行或每一列隨機(jī)取出一個(gè)無障礙柵格,形成一條間斷的路徑。

        第二步是將間斷的路徑連接為連續(xù)路徑。在這一步中首先從第一個(gè)柵格開始判斷相鄰的兩個(gè)柵格是否為連續(xù)柵格,柵格是否連續(xù)的判斷方法為:S=max{abs(xi+1-xi),abs(yi+1-yi)}。若S等于1則說明兩個(gè)相鄰柵格連續(xù),反之不連續(xù)。

        對于不連續(xù)的柵格取兩個(gè)柵格的中點(diǎn)柵格,中點(diǎn)柵格的坐標(biāo)計(jì)算為:

        若中點(diǎn)柵格為障礙物柵格,則取相鄰柵格。如果相鄰柵格是障礙物柵格,則刪除這條路徑。如果中點(diǎn)柵格或者相鄰柵格為無障礙柵格且不在路徑中則插入路徑中,繼續(xù)判斷新插入的柵格和新插入的柵格的前一個(gè)柵格是否連續(xù),若不連續(xù)則循環(huán)以上步驟,直到兩個(gè)柵格連續(xù)。當(dāng)兩個(gè)柵格連續(xù)后取下一個(gè)柵格,循環(huán)以上步驟,直到整條路徑連續(xù)。初始化一條路徑的流程圖如圖3所示。

        圖3 初始化種群Fig.3 Initialized population

        2.2.3 種群適應(yīng)度

        適應(yīng)度函數(shù)分成兩部分,分別用來判斷路徑的長短和平滑程度。路徑長度的計(jì)算相對簡單,公式如下:

        要求的是機(jī)器人的路徑最短,而選擇方式采用的是輪盤賭的方式,所以適應(yīng)度函數(shù)的第一部分為:

        機(jī)器人由于運(yùn)動學(xué)和動力學(xué)的約束,行進(jìn)時(shí)拐彎不宜過大,并且相對平滑的路徑有利于機(jī)器人的行駛,因此產(chǎn)生的路徑有平滑度的要求。路徑之間的夾角越大,用來表示路徑夾角的三個(gè)點(diǎn)之間的距離就越大,路徑也就越平滑,計(jì)算公式如下:

        d2的值可對應(yīng)路徑中連續(xù)三點(diǎn)的夾角的情況分別為180°和直角,其中180°的三點(diǎn)成一直線,平滑度最好,直角次之。對除直線外情況給予懲罰30,可以根據(jù)實(shí)際情況改動懲罰的大小。懲罰之和的倒數(shù)即為適應(yīng)度函數(shù)的第二部分fit2。

        適應(yīng)度函數(shù)的兩部分需要取一個(gè)權(quán)重,權(quán)重公式如下:

        根據(jù)路徑長度和平滑度之間的權(quán)重選擇參數(shù)a和b。

        2.2.4 選擇方法

        選擇方法采用簡單的基于概率的輪盤賭方法。首先計(jì)算出所有個(gè)體的適應(yīng)度函數(shù)的和,再計(jì)算每一個(gè)個(gè)體所占的比率,計(jì)算公式如下:

        然后根據(jù)每個(gè)個(gè)體的概率,以輪盤賭的方式選擇出下一代個(gè)體。為了防止遺傳算法陷入局部最優(yōu)解,通過輪盤賭的方法確保一部分非最優(yōu)個(gè)體。

        2.2.5 交叉

        首先需要確定一個(gè)交叉概率Pc,產(chǎn)生一個(gè)0到1的隨機(jī)數(shù),并和交叉概率Pc比較,若小于Pc則進(jìn)行交叉操作。交叉方式采用的是單點(diǎn)交叉的方式,具體的交叉操作是找出兩條路徑中所有相同的點(diǎn),然后隨機(jī)選擇其中的一個(gè)點(diǎn),將之后的路徑進(jìn)行交叉操作。具體的流程圖如圖4所示。

        2.2.6 變異

        首先需要確定一個(gè)變異概率Pm,產(chǎn)生一個(gè)0到1的隨機(jī)數(shù),并和變異概率Pm比較,若小于Pm則進(jìn)行變異操作。變異方法是隨機(jī)選取路徑中除起點(diǎn)和終點(diǎn)以外的兩個(gè)柵格,將這兩個(gè)點(diǎn)進(jìn)行連續(xù)操作。此時(shí)有可能無法產(chǎn)生連續(xù)的路徑,則需要重新選擇兩個(gè)柵格執(zhí)行以上操作,直到完成變異操作。具體的流程圖如圖5所示。

        圖4 交叉操作流程圖Fig.4 Crossover operation flow chart

        圖5 變異操作流程圖Fig.5 Mutation operation flow chart

        2.2.7 算法說明

        在Matlab 2018a,i7-9700KF的CPU環(huán)境下進(jìn)行仿真。改進(jìn)遺傳算法的平均計(jì)算時(shí)間與路徑長度之間的關(guān)系,如表1所示。

        2.3 基于時(shí)間窗的算法流程

        當(dāng)系統(tǒng)中輸入任務(wù)時(shí),機(jī)器人路徑規(guī)劃系統(tǒng)都會根據(jù)任務(wù)設(shè)定的優(yōu)先級對整體任務(wù)進(jìn)行規(guī)劃。該算法流程是:

        表1 時(shí)間與路徑長度之間的關(guān)系Table 1 Relationship between time and path length

        (1)向系統(tǒng)中導(dǎo)入任務(wù)列表。

        (2)找出優(yōu)先級順序與時(shí)間順序相符的任務(wù)和優(yōu)先級順序與時(shí)間順序不相符的任務(wù)。

        (3)優(yōu)先級較高的任務(wù)在執(zhí)行完當(dāng)前任務(wù)是否能參與次一級任務(wù)從當(dāng)前??奎c(diǎn)到達(dá)任務(wù)出發(fā)點(diǎn)的運(yùn)行。時(shí)間順序較早的任務(wù)在執(zhí)行完當(dāng)前任務(wù)是否能參與優(yōu)先級較高任務(wù)從當(dāng)前??奎c(diǎn)到達(dá)任務(wù)出發(fā)點(diǎn)的運(yùn)行。

        (4)明確各個(gè)機(jī)器人的任務(wù)分配,根據(jù)優(yōu)化后的遺傳算法確定運(yùn)輸線路。

        (5)在步驟(4)的基礎(chǔ)上,判斷各個(gè)任務(wù)從開始到結(jié)束的運(yùn)輸線路是否存在重合的節(jié)點(diǎn)。如果存在,根據(jù)重合節(jié)點(diǎn)數(shù)判斷沖突的類型,如果不存在,跳轉(zhuǎn)到步驟(8)。

        (6)如果機(jī)器人在同一條線路上重合的節(jié)點(diǎn)數(shù)等于1表明可能存在交叉沖突。交叉沖突如圖6所示。通過機(jī)器人通過交叉節(jié)點(diǎn)的時(shí)間判斷是否存在交叉沖突。如果存在交叉沖突,次優(yōu)先級任務(wù)選擇等待和重新規(guī)劃路徑,通過比較選擇較好的方案。

        圖6 交叉沖突Fig.6 Cross conflict

        (7)如果機(jī)器人在同一條線路上重合的節(jié)點(diǎn)數(shù)大于等于2且順序相同表明可能存在同向沖突,同向沖突如圖7所示。判斷所容納的數(shù)量是否小于道路承受能力,來確定是否存在同向沖突。任務(wù),時(shí)間成本太高,對優(yōu)先級高的任務(wù)進(jìn)行線路規(guī)劃,路徑增加則放棄當(dāng)前新路徑。以上情況都不滿足,再次對優(yōu)先級低的任務(wù)選擇等待和重新進(jìn)行路徑規(guī)劃,選擇出最優(yōu)路徑。

        圖7 同向沖突Fig.7 Co-direction conflict

        (8)如果機(jī)器人在同一條線路上重合的節(jié)點(diǎn)數(shù)大于等于2且順序相反表明可能存在相向沖突,相向沖突如圖8所示。通過機(jī)器人通過相向沖突節(jié)點(diǎn)的時(shí)間判斷是否存在交叉沖突。如果存在交叉沖突,依照任務(wù)的優(yōu)先級從低到高的順序,選擇等待和重新規(guī)劃優(yōu)先級低的

        圖8 相向沖突Fig.8 Opposing conflict

        (9)得出最優(yōu)路徑。

        3 對基于時(shí)間窗的算法進(jìn)行驗(yàn)證計(jì)算

        3.1 情景說明

        隨著貨物數(shù)量的爆炸性增長和用工成本的不斷增加,更高效的倉儲和物流系統(tǒng)就成為越來越多企業(yè)的首選?,F(xiàn)在簡化了一個(gè)大型倉庫,如圖9所示。

        圖9 倉庫作業(yè)的路網(wǎng)結(jié)構(gòu)和作業(yè)站點(diǎn)Fig.9 Road network structure and operation sites

        任務(wù)1、任務(wù)2、任務(wù)3和任務(wù)4是4個(gè)即將輸入系統(tǒng)任務(wù),具體任務(wù)為見表2,優(yōu)先級數(shù)字越小優(yōu)先級越高。物流系統(tǒng)中有4臺機(jī)器人分別是機(jī)器人1、機(jī)器人2、機(jī)器人3和機(jī)器人4。當(dāng)前處于空載空閑狀態(tài),??奎c(diǎn)分別是在9、4、15和55號站點(diǎn)等待系統(tǒng)調(diào)用。

        表2 機(jī)器人系統(tǒng)作業(yè)任務(wù)表Table 2 Task list of robot system

        3.2 最優(yōu)路徑計(jì)算

        3.2.1 最優(yōu)任務(wù)分配和確定運(yùn)輸線路

        根據(jù)遺傳算法,可以計(jì)算出機(jī)器人到起點(diǎn)的相應(yīng)最短路徑以及最短的行駛時(shí)間。通過比較確定任務(wù)分配的機(jī)器人,在此基礎(chǔ)上計(jì)算完成任務(wù)所需的時(shí)間。

        分別計(jì)算任務(wù)1、任務(wù)2、任務(wù)3和任務(wù)4調(diào)用機(jī)器人到達(dá)各自任務(wù)起點(diǎn)的路徑,如表3~6所示。

        表3 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)11的優(yōu)化路徑Table 3 Optimized path of robots 1,2,3,4 to point 11

        表4 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)13的優(yōu)化路徑Table 4 Optimized path of robots 1,2,3,4 to point 13

        表5 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)19的優(yōu)化路徑Table 5 Optimized path of robots 1,2,3,4 to point 19

        表6 機(jī)器人1、2、3、4到達(dá)起始點(diǎn)54的優(yōu)化路徑Table 6 Optimized path of robots 1,2,3,4 to point 54

        執(zhí)行任務(wù)1時(shí),分別計(jì)算機(jī)器人1、機(jī)器人2、機(jī)器人3、機(jī)器人4到達(dá)起點(diǎn)11的時(shí)間。因?yàn)闄C(jī)器人1執(zhí)行任務(wù)1任務(wù)所花費(fèi)的時(shí)間最少,所以選擇機(jī)器人1執(zhí)行任務(wù)1。

        使用機(jī)器人1計(jì)算任務(wù)2時(shí),機(jī)器人1已經(jīng)完成任務(wù)1,因此需要從308.04 s開始計(jì)算。通過對比發(fā)現(xiàn)機(jī)器人2到達(dá)起始點(diǎn)13的時(shí)間所花費(fèi)的時(shí)間最少,因此選擇機(jī)器人2執(zhí)行Task2任務(wù)。

        機(jī)器人1和機(jī)器人2必須先完成任務(wù)1和任務(wù)2,才能夠執(zhí)行任務(wù)3。任務(wù)3的優(yōu)先級高于任務(wù)4,任務(wù)4的開始執(zhí)行時(shí)間早于任務(wù)3。分別計(jì)算機(jī)器人1、機(jī)器人2、機(jī)器人3、機(jī)器人4到達(dá)任務(wù)3起始點(diǎn)19的時(shí)間,機(jī)器人3所花費(fèi)的時(shí)間最少。在上述基礎(chǔ)上,執(zhí)行任務(wù)4。當(dāng)執(zhí)行完任務(wù)4,機(jī)器人4到達(dá)起始點(diǎn)19的時(shí)間大于機(jī)器人3到達(dá)任務(wù)3起始點(diǎn)19所花費(fèi)的時(shí)間。選擇機(jī)器人3執(zhí)行任務(wù)3。

        最優(yōu)任務(wù)分配:任務(wù)1選擇機(jī)器人1;任務(wù)2選擇機(jī)器人2;任務(wù)3選擇機(jī)器人3;任務(wù)4選擇機(jī)器人4。它們到達(dá)起始點(diǎn)的路徑分別是9-10-11、4-14-13、15-14-19和55-54。運(yùn)輸線路:任務(wù)1的運(yùn)輸線路:9-10-11-12-13-14-19-24-25-26-27-28;任務(wù)2的運(yùn)輸線路:4-14-13-12-18-22-33-38;任務(wù)3的運(yùn)輸線路:15-14-19-24-25-35-34;任務(wù)4的運(yùn)輸線路:55-54-53-46-40-36-27-26。

        3.2.2 當(dāng)前線路時(shí)間窗

        系統(tǒng)當(dāng)前線路時(shí)間窗結(jié)果如表7~10所示。

        表7 機(jī)器人1執(zhí)行任務(wù)1的優(yōu)化路徑Table 7 Optimized path of robot 1 to perform task 1

        表8 機(jī)器人2執(zhí)行任務(wù)2的優(yōu)化路徑Table 8 Optimized path of robot 2 to perform task 2

        表9 機(jī)器人3執(zhí)行任務(wù)3的優(yōu)化路徑Table 9 Optimized path of robot 3 to perform task 3

        表10 機(jī)器人4執(zhí)行任務(wù)4的優(yōu)化路徑Table 10 Optimized path of robot 4 to perform task 4

        3.2.3 優(yōu)化當(dāng)前線路時(shí)間窗沖突

        分析任務(wù)發(fā)生沖突的時(shí)間窗詳細(xì)情況如下:

        (1)任務(wù)1

        機(jī)器人1與機(jī)器人2:

        機(jī)器人1與機(jī)器人3:

        機(jī)器人1與機(jī)器人4:

        (2)任務(wù)2

        機(jī)器人2與機(jī)器人1:

        (3)任務(wù)3

        機(jī)器人3與機(jī)器人1:

        (4)任務(wù)4:

        機(jī)器人4與機(jī)器人1:

        在路徑12-13和13-14上,機(jī)器人1和機(jī)器人2某一時(shí)間段內(nèi)沿相反方向行駛。機(jī)器人1和機(jī)器人3在路徑14-19、19-24和24-25上沿相同方向行駛。機(jī)器人1和機(jī)器人4沿相反方向行駛。

        解決線路沖突的方法主要有以下兩種:避讓和嘗試新的線路,通過嘗試兩種可能方案,選擇花費(fèi)時(shí)間較短的作為最優(yōu)方案。

        (1)避讓

        當(dāng)機(jī)器人1按照任務(wù)1規(guī)劃的線路行駛和機(jī)器人2按照任務(wù)2規(guī)劃的線路行駛時(shí),在節(jié)點(diǎn)12-13-14處產(chǎn)生碰撞。為避免該碰撞,將如任務(wù)2的時(shí)間節(jié)點(diǎn)后移動,至少需要推遲的時(shí)間是100 s。

        (2)嘗試新的線路

        路徑的發(fā)生沖突時(shí),依照任務(wù)的優(yōu)先級從低到高的順序,重新規(guī)劃優(yōu)先級低的任務(wù),路徑增加則放棄當(dāng)前新路徑,對優(yōu)先級高的任務(wù)進(jìn)行線路規(guī)劃,路徑增加則放棄當(dāng)前新路徑。以上情況都不滿足,再次對優(yōu)先級低的任務(wù)重新進(jìn)行路徑規(guī)劃。對比新路徑和在當(dāng)前路徑基礎(chǔ)上進(jìn)行避讓,選擇出最優(yōu)路徑。

        任務(wù)2的優(yōu)先級低于任務(wù)1,因此重新對任務(wù)2進(jìn)行線路規(guī)劃。新路徑大于原路徑,轉(zhuǎn)而尋找任務(wù)1的新路徑。結(jié)果如下:任務(wù)1的路徑是9-10-11-12-18-22-23-24-25-26-27-28;任務(wù)2的路徑是4-14-13-12-18-22-33-38。機(jī)器人1和機(jī)器人2在執(zhí)行任務(wù)1和任務(wù)2時(shí),避免了在線路12-13-14沖突。

        對于26-27路徑的沖突,因任務(wù)4優(yōu)先級更低,對任務(wù)4重新進(jìn)行路徑規(guī)劃,見表11。運(yùn)輸路徑是55-54-53-52-45-39-35-25-26,所花費(fèi)時(shí)間310.61 s。在原路徑基礎(chǔ)上進(jìn)行等待,生成的路徑是55-54-53-46-40-36(等待)-27-26,所花費(fèi)時(shí)間260.61 s。在解決了沖突后,任務(wù)1和4的時(shí)間窗口如表12和13所示。

        表11 機(jī)器人4執(zhí)行任務(wù)4重新進(jìn)行路徑規(guī)劃Table 11 Robot 4 performing task 4 and re-planning path

        表12 任務(wù)1最優(yōu)路徑(優(yōu)化后)Table 12 Optimal path of task 1(Optimized)

        表13 任務(wù)4最優(yōu)路徑(優(yōu)化后)Table 13 Optimal path of task 4(Optimized)

        機(jī)器人4的等待時(shí)間:280.32-246.61+2=35.71 s。

        新路徑的可能沖突的時(shí)間窗詳細(xì)分析:

        (1)任務(wù)1

        機(jī)器人1與機(jī)器人2:

        機(jī)器人1與機(jī)器人3:

        機(jī)器人1與機(jī)器人4:

        (2)任務(wù)2

        機(jī)器人2與機(jī)器人1:

        (3)任務(wù)3

        機(jī)器人3與機(jī)器人1:

        (4)任務(wù)4

        機(jī)器人4與機(jī)器人1:

        任務(wù)1和任務(wù)4的新路徑所花費(fèi)的時(shí)間增多,分別是310.32-308.04=2.28 s,320.61-306.32=14.29 s。

        任務(wù)1重新規(guī)劃路徑增加的2.28 s在可接受范圍內(nèi),如果任務(wù)1不重新規(guī)劃,任務(wù)2將會推遲100 s。任務(wù)4重新規(guī)劃路徑增加的15.9 s大于推遲時(shí)間窗的11.5 s,故對任務(wù)4使用等待的方法來避免沖突。

        4 結(jié)束語

        通過對單車道雙向多機(jī)器人路徑規(guī)劃問題進(jìn)行研究,提出了一種基于時(shí)間窗的算法流程,同時(shí)通過一個(gè)模型進(jìn)行驗(yàn)證證明了算法流程的有效性。為多機(jī)器人協(xié)同作業(yè),提供了新的選擇。未來將進(jìn)一步對多機(jī)器人協(xié)同作業(yè)進(jìn)行研究,為了進(jìn)一步提高效率可以讓各機(jī)器人預(yù)先出發(fā),從而為執(zhí)行任務(wù)進(jìn)一步節(jié)約時(shí)間。以及不同性能的雙車道雙向機(jī)器人以及機(jī)器人在交叉路口相遇,在保證安全的前提下如何避障。

        猜你喜歡
        柵格遺傳算法沖突
        耶路撒冷爆發(fā)大規(guī)模沖突
        基于鄰域柵格篩選的點(diǎn)云邊緣點(diǎn)提取方法*
        “三宜”“三不宜”化解師生沖突
        井岡教育(2020年6期)2020-12-14 03:04:32
        基于自適應(yīng)遺傳算法的CSAMT一維反演
        一種基于遺傳算法的聚類分析方法在DNA序列比較中的應(yīng)用
        基于遺傳算法和LS-SVM的財(cái)務(wù)危機(jī)預(yù)測
        基于改進(jìn)的遺傳算法的模糊聚類算法
        不同剖面形狀的柵格壁對柵格翼氣動特性的影響
        基于CVT排布的非周期柵格密度加權(quán)陣設(shè)計(jì)
        “鄰避沖突”的破解路徑
        浙江人大(2014年6期)2014-03-20 16:20:40
        正在播放一区| 亚洲日本一区二区三区四区| 久久精品国产亚洲av麻豆床戏 | 亚洲偷自拍国综合第一页| 中出人妻中文字幕无码| 国产亚洲一本大道中文在线| 久久婷婷免费综合色啪| 日韩精品乱码中文字幕| 国产一精品一av一免费| 久久99精品久久久久久野外| 国产西西裸体一级黄色大片| 五月婷婷开心五月激情| 中文字幕一精品亚洲无线一区| 精品久久久久久久中文字幕| 99在线无码精品秘 人口| av在线免费观看男人天堂| 中文字幕网伦射乱中文| 亚洲中文字幕无码中字| 国产精品一区二区日韩精品| 一本久道竹内纱里奈中文字幕| 亚洲中文字幕在线第二页| 亚洲一区二区在线| av一区二区三区高清在线看| 亚洲中文无码av永久| 国产美女久久精品香蕉69| 日本a在线免费观看| 黄片免费观看视频播放| 中文字幕日韩欧美一区二区三区| 处破痛哭a√18成年片免费| 国产自精品在线| 国产精品国产自产拍高清| 69一区二三区好的精华| 久久中文字幕无码一区二区| 亚洲一区二区三区最新视频| 久久精品国产字幕高潮| 亚洲欧美国产双大乳头| 黄色三级视频中文字幕| 91色老久久偷偷精品蜜臀懂色| 曰韩无码二三区中文字幕| 国产乱人伦真实精品视频| 国产免费人成视频在线观看|