《智能機(jī)器人創(chuàng)新設(shè)計(jì)》 課件 實(shí)踐：多機(jī)器人協(xié)同調(diào)度-粒子群算法

智慧物流系統(tǒng)：從設(shè)計(jì)到實(shí)現(xiàn)多機(jī)器人協(xié)同調(diào)度——粒子群算法實(shí)踐教學(xué)內(nèi)容CONTENTS4實(shí)踐準(zhǔn)備3任務(wù)要求1項(xiàng)目目標(biāo)5程序框圖6操作步驟7實(shí)操效果2項(xiàng)目原理8修改參數(shù)-唯一變量9拓展思考31項(xiàng)目目標(biāo)了解粒子群算法對(duì)多段路徑規(guī)劃的設(shè)計(jì)思路，通過分析算法邏輯，學(xué)習(xí)使用Python編程語言進(jìn)行函數(shù)模塊設(shè)計(jì)。函數(shù)模塊設(shè)計(jì)與算法原理相結(jié)合，將有助于同學(xué)們理解粒子群算法本身。學(xué)習(xí)掌握算法調(diào)試，最終在應(yīng)用軟件Flex-PF實(shí)現(xiàn)基于粒子群算法為多個(gè)物流機(jī)器人規(guī)劃路徑，使物流機(jī)器人根據(jù)最優(yōu)的路徑完成從起點(diǎn)位置移動(dòng)到貨架位置，再從貨架位置移動(dòng)到取貨區(qū)，最終把貨架運(yùn)送回貨架區(qū)的任務(wù)。42項(xiàng)目原理粒子群算法是通過群體中粒子間的合作與競(jìng)爭(zhēng)而產(chǎn)生的群體智能進(jìn)行指導(dǎo)優(yōu)化搜索。算法采用簡(jiǎn)單的速度位移模型，避免了復(fù)雜的遺傳，同時(shí)它特有的記憶功能使其可以動(dòng)態(tài)地跟蹤當(dāng)前的搜索情況并調(diào)整搜索策略，具有較強(qiáng)的全局搜索能力和魯棒性，且不需要借助問題的特征信息。5(1)粒子群算法主要步驟：①設(shè)定粒子的長(zhǎng)度（即“位置”屬性的維數(shù)）、粒子群的粒子數(shù)，初始化粒子群中粒子的位置和速度屬性；②確定適應(yīng)度/評(píng)價(jià)函數(shù)表達(dá)式，計(jì)算粒子群中每個(gè)粒子的適應(yīng)度，更新每個(gè)粒子與整個(gè)粒子群的最優(yōu)位置及適應(yīng)度。2項(xiàng)目原理6(1)粒子群算法主要步驟：③根據(jù)個(gè)體最優(yōu)和群體最優(yōu)的位置依據(jù)下式更新個(gè)體速度和位置：

更新粒子速度：慣性因子當(dāng)前粒子速度粒子加速因子粒子群加速因子[0,1]之間的隨機(jī)數(shù)粒子歷史最優(yōu)位置粒子當(dāng)前位置粒子群歷史最優(yōu)位置2項(xiàng)目原理7(1)粒子群算法主要步驟：③根據(jù)個(gè)體最優(yōu)和群體最優(yōu)的位置依據(jù)下式更新個(gè)體速度和位置：

更新粒子速度：更新粒子位置：④設(shè)定迭代停止條件，不斷重復(fù)②③步直至達(dá)到迭代停止條件，迭代結(jié)束時(shí)的粒子群最優(yōu)位置即為所求的最優(yōu)解；2項(xiàng)目原理8(2)粒子群算法的隨機(jī)性分析:粒子群初始化時(shí)，每個(gè)粒子的初始位置和初始速度是隨機(jī)的。粒子初始位置的隨機(jī)性使得粒子群可以從各個(gè)方向靠近最優(yōu)解，一定程度上保證了粒子群算法的搜索范圍；粒子初始速度的差異使得其向群體最優(yōu)解靠近的同時(shí)自身仍保留一定的尋優(yōu)能力，不至于使得群體迅速收斂至局部最優(yōu)解，造成自鎖。2項(xiàng)目原理9(3)對(duì)協(xié)同調(diào)度問題的分析:針對(duì)多機(jī)器人物流系統(tǒng)協(xié)同調(diào)度這個(gè)實(shí)際問題，需要對(duì)粒子群算法中的一些抽象概念賦予實(shí)際的含義和相關(guān)規(guī)定。假設(shè)物流系統(tǒng)中有3個(gè)物流機(jī)器人、4個(gè)待搬運(yùn)貨架、2個(gè)可復(fù)用取貨點(diǎn)，分別對(duì)物流機(jī)器人、待搬運(yùn)貨架、取貨點(diǎn)進(jìn)行編號(hào)：物流機(jī)器人編號(hào)：0、1、2貨架編號(hào)：0、1、2、3取貨點(diǎn)編號(hào)：0、12項(xiàng)目原理10在多機(jī)器人物流系統(tǒng)協(xié)同調(diào)度問題中，將“一個(gè)物流機(jī)器人搬運(yùn)一個(gè)貨架到一個(gè)取貨點(diǎn)”視為1個(gè)任務(wù)。因此，則在物流機(jī)器人的搬運(yùn)能力內(nèi)，只需考慮3個(gè)任務(wù)分配問題，每個(gè)物流機(jī)器人將分到1個(gè)任務(wù)。注意：當(dāng)機(jī)器人數(shù)量大于貨架數(shù)量時(shí)，多余的機(jī)器人不需要被分配任務(wù)；當(dāng)貨架數(shù)量大于機(jī)器人數(shù)量時(shí)，多余的貨架不需要被考慮。①協(xié)同調(diào)度問題中對(duì)“粒子位置”的定義：粒子群算法中，迭代結(jié)束后得到的“最優(yōu)粒子位置”即為我們想要的最優(yōu)解，它是一個(gè)定義在高維空間中的“位置”，通常用一串實(shí)數(shù)表示。2項(xiàng)目原理11①實(shí)際問題中，將解（即“粒子位置”）的結(jié)構(gòu)形式定義成二維數(shù)組的形式：機(jī)器人的數(shù)量小于貨架的數(shù)量，每個(gè)機(jī)器人都會(huì)被分配貨架：1）將機(jī)器人的編號(hào)作為數(shù)組的下標(biāo)；2）將貨架的編號(hào)作為數(shù)組的第0行，本次任務(wù)只有3個(gè)機(jī)器人，只能同時(shí)搬運(yùn)3個(gè)貨架，因此貨架的編號(hào)4選3，不可重復(fù)；3）將取貨點(diǎn)的編號(hào)作為數(shù)組的第1行，2個(gè)取貨點(diǎn)的編號(hào)2選1，可重復(fù)使用；數(shù)組下標(biāo)(物流機(jī)器人)012第0行(貨架)XXX第1行(取貨點(diǎn))XXX2項(xiàng)目原理12①實(shí)際問題中，將解（即“粒子位置”）的結(jié)構(gòu)形式定義成二維數(shù)組的形式機(jī)器人的數(shù)量小于貨架的數(shù)量，每個(gè)機(jī)器人都會(huì)被分配貨架：數(shù)組下標(biāo)(物流機(jī)器人)012第0行(貨架)201第1行(取貨點(diǎn))110二維數(shù)組結(jié)構(gòu)定義粒子位置：數(shù)組下標(biāo)(物流機(jī)器人)012第0行(貨架)XXX第1行(取貨點(diǎn))XXX2項(xiàng)目原理13①實(shí)際問題中，將解（即“粒子位置”）的結(jié)構(gòu)形式定義成二維數(shù)組的形式數(shù)組下標(biāo)(物流機(jī)器人)012第0行(貨架)201第1行(取貨點(diǎn))110二維數(shù)組結(jié)構(gòu)定義粒子位置：二維數(shù)組結(jié)構(gòu)表示的含義：編號(hào)為0的機(jī)器人搬運(yùn)編號(hào)為2的貨架到編號(hào)為1的取貨點(diǎn)編號(hào)為1的機(jī)器人搬運(yùn)編號(hào)為0的貨架到編號(hào)為1的取貨點(diǎn)編號(hào)為2的機(jī)器人搬運(yùn)編號(hào)為1的貨架到編號(hào)為0的取貨點(diǎn)2項(xiàng)目原理14②“粒子位置”的數(shù)據(jù)類型與取值范圍：數(shù)組下標(biāo)(物流機(jī)器人)012第0行(貨架)201第1行(取貨點(diǎn))110二維數(shù)組結(jié)構(gòu)定義粒子位置：由左圖可知，表示“粒子位置”的二維數(shù)組中每位的取值含義為機(jī)器人、貨架、取貨點(diǎn)的編號(hào)，因此，需要將編號(hào)定義為非負(fù)整數(shù)，但在粒子群算法的迭代過程中涉及粒子位置和速度的更新，更新公式中包含浮點(diǎn)數(shù)運(yùn)算，如隨機(jī)數(shù)、給定的學(xué)習(xí)因子也可能是小數(shù)等。因此“粒子位置”的數(shù)據(jù)類型將不可避免的變?yōu)樾?shù)，所以要注意對(duì)其進(jìn)行取整運(yùn)算，當(dāng)計(jì)算結(jié)果超過編號(hào)上、下限時(shí)，可進(jìn)行強(qiáng)制取值以限定范圍。2項(xiàng)目原理15②“粒子位置”的數(shù)據(jù)類型與取值范圍：數(shù)組下標(biāo)(物流機(jī)器人)012第0行(貨架)201第1行(取貨點(diǎn))110二維數(shù)組結(jié)構(gòu)定義粒子位置：數(shù)組下標(biāo)012第0行-0.50.30.43第1行0.5-0.1-0.25定義同樣結(jié)構(gòu)的粒子速度：

新的粒子速度新的粒子位置(取整數(shù))向最優(yōu)粒子靠近2項(xiàng)目原理16(4)迭代結(jié)束條件：粒子群算法的迭代結(jié)束條件可以有以下幾種設(shè)定方式：①設(shè)定固定的最大迭代次數(shù)，當(dāng)?shù)螖?shù)超過迭代限制就停止迭代；②當(dāng)全局最優(yōu)粒子位置經(jīng)過若干代不再更新時(shí)，則停止迭代；③當(dāng)粒子群中所有粒子的速度都為零時(shí)，即粒子都位于相同位置不會(huì)再計(jì)算出新的位置了，則停止迭代；④將上述停止條件相結(jié)合，設(shè)定最大迭代次數(shù)，在迭代過程中若滿足條件②或③，就提前結(jié)束迭代。2項(xiàng)目原理173任務(wù)要求使用Python編程語言實(shí)現(xiàn)粒子群算法功能函數(shù)模塊；通過粒子群算法功能模塊實(shí)現(xiàn)物流機(jī)器人從等待區(qū)到貨架區(qū)，再從貨架區(qū)移動(dòng)到取貨區(qū)，最后再從取貨區(qū)返回貨架區(qū)的路徑規(guī)劃任務(wù)。18使用python語言編寫一個(gè)PSO類(或函數(shù))，該類(或函數(shù))根據(jù)粒子群算法給物流機(jī)器人編隊(duì)進(jìn)行任務(wù)分配，以坐標(biāo)組合形式輸出分配方案：起點(diǎn)到貨架將機(jī)器人分配到貨架將貨架分配到取貨點(diǎn)貨架到取貨點(diǎn)3任務(wù)要求19使用python語言編寫一個(gè)PSO類(或函數(shù))，該類(或函數(shù))根據(jù)遺傳算法給物流機(jī)器人編隊(duì)進(jìn)行任務(wù)分配，以坐標(biāo)組合形式輸出分配方案：將機(jī)器人分配到貨架將貨架分配到取貨點(diǎn)注意：只需要考慮機(jī)器人單次搬運(yùn)能力將貨架搬運(yùn)至取貨點(diǎn)的最短距離總和。即只需考慮兩段移動(dòng)距離，機(jī)器人到貨架的距離加上貨架到取貨點(diǎn)的距離既可。當(dāng)機(jī)器人數(shù)量大于貨架數(shù)量時(shí)，多余的機(jī)器人不需要被分配任務(wù)；當(dāng)貨架數(shù)量大于機(jī)器人數(shù)量時(shí)，多余的貨架不需要被考慮。3任務(wù)要求20序號(hào)教學(xué)環(huán)境數(shù)量要求1電腦1Windows102物流機(jī)器人≥2無問題、滿電3貨架≥2貨架緊固無松散4路由器1品牌：TP-Link型號(hào)：TL-WAR452L5場(chǎng)地18x74實(shí)踐準(zhǔn)備215程序框圖22(1)引用庫：本例程中自定義的PSO類需要依賴numpy庫，載入相關(guān)庫；numpy

是一個(gè)運(yùn)算速度非?？斓臄?shù)學(xué)函數(shù)庫6操作步驟23(2)創(chuàng)建PSO類，包含20個(gè)屬性，6個(gè)方法。在初始化方法中定義20個(gè)屬性6操作步驟24(2)創(chuàng)建PSO類，包含20個(gè)屬性，6個(gè)方法。在類中定義6個(gè)方法：給機(jī)器人、貨架、取貨點(diǎn)排序計(jì)算機(jī)器人、貨架、取貨點(diǎn)距離生成初始粒子群計(jì)算適應(yīng)度、更新最優(yōu)值更新粒子群的位置和速度迭代控制6操作步驟25①確定粒子長(zhǎng)度n：比較物流機(jī)器人的數(shù)量和待搬運(yùn)貨架的數(shù)量，取二者中較小值賦值給n，同時(shí)將機(jī)器人、貨架、取貨點(diǎn)的數(shù)量進(jìn)行排序(取貨點(diǎn)數(shù)量將視為無窮大)。分別獲取機(jī)器人、貨架、取貨點(diǎn)的數(shù)量如果貨架少，將貨架數(shù)量作為粒子長(zhǎng)度，輸出各自的數(shù)量否則，將機(jī)器人數(shù)量作為粒子長(zhǎng)度，輸出各自數(shù)量6操作步驟26②計(jì)算機(jī)器人、貨架、取貨點(diǎn)之間的距離，這里使用曼哈頓距離：生成存儲(chǔ)曼哈頓距離的格式，小車的數(shù)量作為行，貨架數(shù)量作為列分別計(jì)算小車到貨架間的距離和貨架到目標(biāo)點(diǎn)間的距離6操作步驟27③生成初始粒子群：粒子的位置用貨架編號(hào)作為下標(biāo)，用機(jī)器人編號(hào)作為第0行，用取貨點(diǎn)編號(hào)作為第1行；粒子的速度為同樣格式的二維數(shù)組，數(shù)據(jù)范圍[-0.5,0.5]；粒子的位置：生成等差數(shù)列，作為第0行(物流機(jī)器人)，亂序處理；再生成第1行(取貨點(diǎn))等差數(shù)列n位；粒子速度：同樣格式的二維數(shù)組每位數(shù)據(jù)都是[-0.5,0.5]范圍內(nèi)的隨機(jī)浮點(diǎn)數(shù)；6操作步驟28④計(jì)算適應(yīng)度：將機(jī)器人走過的總距離(機(jī)器人->貨架->取貨點(diǎn))作為適應(yīng)度，并更新粒子最優(yōu)適應(yīng)度、更新并記錄自身最優(yōu)位置和粒子群全局最優(yōu)位置；計(jì)算機(jī)器人->貨架->取貨點(diǎn)總距離如果適應(yīng)度小于最優(yōu)適應(yīng)度，更新粒子的最優(yōu)適應(yīng)度并記錄自身的最優(yōu)位置；否則記錄自身歷史最優(yōu)位置；如果適應(yīng)度小于粒子群歷史最優(yōu)位置，更新全局最優(yōu)適應(yīng)度，更新全局最佳位置；6操作步驟29⑤粒子群的速度、位置更新：計(jì)算粒子的速度和位置，對(duì)計(jì)算出的位置進(jìn)行取整，保證粒子位置中的編號(hào)是正數(shù)；獲取全局的最優(yōu)位置、機(jī)器人和貨架的最大值、取貨點(diǎn)的數(shù)量、粒子的當(dāng)前速度、粒子的當(dāng)前位置、粒子的歷史最優(yōu)位置計(jì)算更新的粒子速度、計(jì)算更新的粒子位置設(shè)置close表，將走過的位置存入到close表中，以確保第0行(貨架)的編號(hào)不重復(fù)出現(xiàn)6操作步驟30⑥迭代控制：先給機(jī)器人、貨架、取貨點(diǎn)排序，然后生成初代粒子，在最大迭代次數(shù)中循環(huán)計(jì)算曼哈頓距離，計(jì)算適應(yīng)度，更新粒子位置和速度，當(dāng)粒子不再更新，停止迭代；生成粒子群并迭代，粒子不再更新就結(jié)束迭代，跳出循環(huán)將編號(hào)對(duì)應(yīng)到機(jī)器人的坐標(biāo)，輸出最優(yōu)組合6操作步驟31(1)通過命令行方式或PyCharm集成開發(fā)環(huán)境運(yùn)行（run）例程：在主函數(shù)中設(shè)置參數(shù)，調(diào)用算法，實(shí)例化算法：設(shè)置參數(shù)，無障礙物時(shí)設(shè)為空，無其他機(jī)器人路徑時(shí)設(shè)為空實(shí)例化算法7實(shí)操效果32(1)通過命令行方式或PyCharm集成開發(fā)環(huán)境運(yùn)行（run）例程：調(diào)用迭代控制函數(shù)，輸出分配結(jié)果：調(diào)用迭代控制函數(shù)，輸出分配結(jié)果輸出每個(gè)任務(wù)分配7實(shí)操效果33(1)通過命令行方式或PyCharm集成開發(fā)環(huán)境運(yùn)行（run）例程：控制臺(tái)輸出結(jié)果：最優(yōu)適應(yīng)度：這里為曼哈頓距離最短最優(yōu)粒子位置：曼哈頓距離最短的分配組合最優(yōu)分配方案：曼哈頓距離最短的坐標(biāo)組合7實(shí)操效果34(2)打開應(yīng)用軟件Flex-PF，在應(yīng)用軟件Flex-PF中實(shí)物運(yùn)行算法文件：導(dǎo)入連接應(yīng)用軟件Flex-PF需要的庫，將通信接口類CI()添加到算法文件中，修改PSO算法類中屬性和計(jì)算方法，完成和路徑規(guī)劃算法的通信：7實(shí)操效果35(2)打開應(yīng)用軟件Flex-PF，在應(yīng)用軟件Flex-PF中實(shí)物運(yùn)行算法文件：①在初始化方法中增加10個(gè)屬性：記錄路徑規(guī)劃算法傳來的數(shù)據(jù)輸入任務(wù)分配所需要的相關(guān)信息7實(shí)操效果36(2)打開應(yīng)用軟件Flex-PF，在應(yīng)用軟件Flex-PF中實(shí)物運(yùn)行算法文件：②修改計(jì)算距離的函數(shù)中的內(nèi)容：將分配結(jié)果對(duì)應(yīng)到機(jī)器人、貨架、取貨點(diǎn)的坐標(biāo)，獲取需要的數(shù)據(jù)，整理數(shù)據(jù)格式將數(shù)據(jù)發(fā)送給路徑規(guī)劃算法接收路徑規(guī)劃算法回傳的數(shù)據(jù)，將數(shù)據(jù)存儲(chǔ)到對(duì)應(yīng)的列表中7實(shí)操效果37(2)打開應(yīng)用軟件Flex-PF，在應(yīng)用軟件Flex-PF中實(shí)物運(yùn)行算法文件：③修改計(jì)算適應(yīng)度、更新粒子最優(yōu)位置的函數(shù)中的內(nèi)容：根據(jù)路徑規(guī)劃的返回的結(jié)果，判斷粒子自身最優(yōu)適應(yīng)度、最優(yōu)位置、全局最優(yōu)適應(yīng)度、全局最優(yōu)位置、最優(yōu)路徑、最優(yōu)分配組合7實(shí)操效果38(2)打開應(yīng)用軟件Flex-PF，在應(yīng)用軟件Flex-PF中實(shí)物運(yùn)行算法文件：④在主函數(shù)中調(diào)用通信接口類，根據(jù)應(yīng)用軟件Flex-PF傳輸來的數(shù)據(jù)，調(diào)用PSO算法，再將分配的結(jié)果發(fā)送給應(yīng)用軟件Flex-PF：接收應(yīng)用軟件Flex-PF傳來的數(shù)據(jù)，并判斷數(shù)據(jù)是否異常將分配結(jié)果回傳給應(yīng)用軟件Flex-PF實(shí)例化任務(wù)分配算法類，并執(zhí)行算法7實(shí)操效果39(2)打開應(yīng)用軟件Flex-PF，在應(yīng)用軟件Flex-PF中實(shí)物運(yùn)行算法文件：將算法文件添加到應(yīng)用軟件Flex-PF中，搭配路徑規(guī)劃算法，在應(yīng)用軟件Flex-PF連接機(jī)器人的仿真運(yùn)行圖和實(shí)物運(yùn)行圖對(duì)比：7實(shí)現(xiàn)效果40可調(diào)參數(shù)分析：在實(shí)例化算法時(shí)，需要傳入的參數(shù)：機(jī)器人坐標(biāo)列表機(jī)器人初始朝向機(jī)器人的狀態(tài)貨架坐標(biāo)列表取貨點(diǎn)坐標(biāo)列表障礙物坐標(biāo)列表其他機(jī)器人坐標(biāo)列表地圖大小種群數(shù)量慣性因子自學(xué)因子全局因子最大迭代次數(shù)需要向應(yīng)用軟件Flex-PF獲取的數(shù)據(jù)固定的場(chǎng)地(8*7or4*7)可以自行設(shè)置的常用變量(在可修改范圍內(nèi))8修改參數(shù)-唯一變量41可調(diào)參數(shù)分析：通過修改唯一的參數(shù)，分析對(duì)分配結(jié)果的影響：粒子群算法中的可調(diào)節(jié)參數(shù)：粒子的數(shù)量m、