工業(yè)大數(shù)據(jù)與人工智能HFUT12第六章

工業(yè)中的智能優(yōu)化方法

路徑規(guī)劃問題的分類6.3路徑規(guī)劃問題路徑規(guī)劃的一般步驟常用的路徑規(guī)劃算法路徑規(guī)劃不同應(yīng)用場景遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用3路徑規(guī)劃問題路徑規(guī)劃技術(shù)廣泛應(yīng)用于工業(yè)領(lǐng)域，構(gòu)成了生產(chǎn)線自動化與智能化建設(shè)的基石。諸如機(jī)器人獨(dú)立無碰撞行走、無人機(jī)避開障礙物執(zhí)行高難度飛行任務(wù)、巡航導(dǎo)彈在復(fù)雜環(huán)境中巧妙規(guī)避雷達(dá)探測、實(shí)施突破式打擊等，均依賴于精密的路徑規(guī)劃。。4路徑規(guī)劃問題的分類根據(jù)對環(huán)境認(rèn)知的詳盡程度，路徑規(guī)劃可分為兩個類別：（1）基于完整預(yù)知信息的全局路徑規(guī)劃（2）依賴實(shí)時傳感信息的局部路徑規(guī)劃。從障礙物信息獲取方式來看，全局路徑規(guī)劃通常屬于靜態(tài)規(guī)劃范疇，相反，局部路徑規(guī)劃則歸屬動態(tài)規(guī)劃領(lǐng)域，通常被稱為在線規(guī)劃。5路徑規(guī)劃問題的分類根據(jù)環(huán)境信息的特性，路徑規(guī)劃可劃分為（1）離散空間路徑規(guī)劃問題離散空間路徑規(guī)劃問題主要涉及在已知、簡化的一維環(huán)境中進(jìn)行靜態(tài)優(yōu)化，相當(dāng)于是對環(huán)境信息高度抽象后的路徑優(yōu)化問題。（2）連續(xù)空間路徑規(guī)劃問題。連續(xù)空間路徑規(guī)劃問題則涉及到在多維連續(xù)變化環(huán)境中的動態(tài)規(guī)劃，它要求在連續(xù)變化的空間中實(shí)時規(guī)劃并調(diào)整路徑，以應(yīng)對復(fù)雜且實(shí)時變化的環(huán)境條件。6路徑規(guī)劃的一般步驟在連續(xù)環(huán)境空間內(nèi)的路徑規(guī)劃問題，如機(jī)器人和飛行器等的動態(tài)路徑規(guī)劃，其典型處理流程通常由三個關(guān)鍵步驟構(gòu)成：環(huán)境模型構(gòu)建、路徑探索和路徑優(yōu)化平滑。7路徑規(guī)劃的一般步驟（1）環(huán)境建模：這是路徑規(guī)劃過程的基石，旨在建立一個能夠被計(jì)算機(jī)算法有效解析和操作的環(huán)境模型，即將復(fù)雜的實(shí)際物理空間轉(zhuǎn)化成算法可處理的抽象空間結(jié)構(gòu)，實(shí)現(xiàn)兩者之間的合理映射。（2）路徑搜索：在此階段，基于已經(jīng)建立的環(huán)境模型，采用適宜的算法探尋一條連接起始點(diǎn)和目標(biāo)點(diǎn)的路徑，以期在滿足預(yù)設(shè)性能指標(biāo)的前提下，找到全局或局部最優(yōu)路徑。8路徑規(guī)劃的一般步驟（3）路徑平滑：初步搜索得出的路徑可能并非運(yùn)動實(shí)體能夠?qū)嶋H通行的平滑路徑，因此需要進(jìn)一步運(yùn)用相關(guān)算法對其進(jìn)行細(xì)化處理和優(yōu)化平滑，確保最終生成的路徑切實(shí)可行且滿足運(yùn)動體的實(shí)際行駛需求。9常用的路徑規(guī)劃算法路徑規(guī)劃算法多樣，依據(jù)不同算法的特點(diǎn)和局限性，其適用場景有所差異。根據(jù)算法的歷史發(fā)展脈絡(luò)及其核心工作原理，將它們概括地劃分為四個主要類別：傳統(tǒng)算法、圖形學(xué)方法、智能算法以及其他算高效算法。10路徑規(guī)劃不同應(yīng)用場景離散域路徑規(guī)劃：離散域路徑規(guī)劃主要聚焦于那些能夠被簡化的環(huán)境，其中空間被劃分成有限數(shù)量的不連續(xù)狀態(tài)或節(jié)點(diǎn)。在此框架下，路徑被視為一系列離散節(jié)點(diǎn)間的轉(zhuǎn)移過程，每一步轉(zhuǎn)移代表一種可能的狀態(tài)變換。倉儲物流，網(wǎng)格化游戲地形導(dǎo)航，網(wǎng)絡(luò)通信路由場景都會用到離散域路徑規(guī)劃。11路徑規(guī)劃不同應(yīng)用場景連續(xù)域路徑規(guī)劃：與之相對，連續(xù)域路徑規(guī)劃則關(guān)注于環(huán)境狀態(tài)可連續(xù)變化的情況，處理對象是無界、無縫隙的物理空間。此類路徑規(guī)劃不僅要求精確的數(shù)學(xué)模型支撐，還需運(yùn)用高級優(yōu)化算法，在無限可能性中篩選出最優(yōu)解。自動駕駛，無人機(jī)航跡規(guī)劃，機(jī)器人臂運(yùn)動規(guī)劃場景都會用到連續(xù)域路徑規(guī)劃。12遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用在機(jī)器人路徑規(guī)劃領(lǐng)域，核心挑戰(zhàn)聚焦于兩個關(guān)鍵方面：（1）選取合適的環(huán)境模型，（2）確定高效的路徑規(guī)劃算法。環(huán)境模型的選項(xiàng)繁多，其中包括但不限于柵格地圖、幾何地圖和拓?fù)鋱D等。其中，柵格地圖因其實(shí)現(xiàn)的直觀性、構(gòu)造的便捷性而被廣為采納。13遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用環(huán)境建模：柵格地圖通過柵格的占有率來表示環(huán)境中的障礙物，通過“0”和“1”的數(shù)字矩陣區(qū)分無障礙空間與障礙區(qū)域，其中“0”代表可通過區(qū)域，“1”則代表障礙物所在。下圖展示了這一概念，圖中中的柵格地圖矩陣可表達(dá)為[[0,0,0],[0,1,1],[0,1,0]]。14遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用障礙物處理：鑒于障礙物形態(tài)的不規(guī)則特性，為了模型的簡易性和實(shí)用性，將涉及障礙的所有相鄰柵格均標(biāo)記為不可通行區(qū)域，使得柵格地圖模型貼近真實(shí)場景。下左圖為障礙物的膨脹化處理，右圖為柵格的填充處理。15遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用柵格地圖信息編碼：直角坐標(biāo)法在平面中，以以柵格地圖的左下角落為坐標(biāo)系的原點(diǎn)，定義水平方向?yàn)閄軸，垂直向上為Y軸，從而建立起一個直角坐標(biāo)系統(tǒng)。以圖下圖為例，展示的是一個10行10列的柵格地圖，采用直角坐標(biāo)表示法，其中某一點(diǎn)A的具體坐標(biāo)為（4.5，1.5）16遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用遺傳算法路徑規(guī)劃方法設(shè)計(jì)：個體編碼方式選擇了路徑點(diǎn)的柵格序號編碼方式。在這種編碼方式下，機(jī)器人從起始柵格出發(fā)，穿越一系列連貫的可行路徑點(diǎn)，直至抵達(dá)目標(biāo)柵格，整個路徑構(gòu)成了遺傳學(xué)概念中的染色體，其中每個路徑點(diǎn)如同染色體上的基因單元。以下圖為例：用序號法可表示為1-2-3-4-5-15-25-35-45-55-66-77-88-89-90-100。17遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用種群初始化：使用中點(diǎn)法產(chǎn)生初始路徑的具體步驟如下：Step1：首先，在起點(diǎn)S和終點(diǎn)E之間繪制一條直線段。Step2：接著，找到直線段SE的中點(diǎn)柵格M。若M點(diǎn)位于障礙物柵格上，則隨機(jī)選擇M點(diǎn)附近的非障礙物柵格點(diǎn)M'，并將M'取代M。若M點(diǎn)是自由柵格點(diǎn)，則無需做任何處理。18遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用種群初始化：使用中點(diǎn)法產(chǎn)生初始路徑的具體步驟如下：Step3：然后，將線段SM（或SM’）視為起點(diǎn)到終點(diǎn)的路徑段。接著，將M（或M’）點(diǎn)作為新的起點(diǎn)S，E點(diǎn)保持不變；或者將M（或M’）點(diǎn)作為新的終點(diǎn)E，S點(diǎn)保持不變。Step4：重復(fù)執(zhí)行Step1至Step3，直到所有生成的路徑段都是連續(xù)的路徑段。Step5：最后，將從起點(diǎn)S到終點(diǎn)E的每一條路徑經(jīng)過的柵格編號連接起來，形成一條初始路徑。通過這樣的方式，生成與種群數(shù)量N相等的路徑群體。19遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用使用中點(diǎn)法生成初始路徑如下：20遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用適應(yīng)度函數(shù)確立：在機(jī)器人路徑規(guī)劃中，核心優(yōu)化目標(biāo)通常是確定最短的可行路徑?，F(xiàn)在生成的所有初始路徑均滿足可行性條件，故無需額外添加懲罰項(xiàng)來規(guī)避不可行解。適應(yīng)度函數(shù)如下：21遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用1.選擇算子：采用了傳統(tǒng)遺傳算法常用的比例法，也稱為輪盤賭法。2：交叉算子：具體操作步驟如下：(1）在種群中隨機(jī)選擇兩個個體。（2）如果這兩個個體中存在一個或多個相同的柵格點(diǎn)，則隨機(jī)選擇其中一個相同的柵格點(diǎn)作為交叉點(diǎn)。（3）如果兩個個體沒有相同的柵格點(diǎn)，則放棄本次交叉，重新選擇兩個個體進(jìn)行交叉。22遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用遺傳算子：3.變異算子：具體步驟概括為：（1）從現(xiàn)有路徑中隨機(jī)抽取一條作為變異對象；（2）在這條路徑中隨機(jī)挑選兩個節(jié)點(diǎn)，移除這兩節(jié)點(diǎn)間的全部路徑片段；（3）直接連接這兩個節(jié)點(diǎn)，形成新的直線段；（4）檢驗(yàn)新形成的線段是否穿越障礙區(qū)域，若發(fā)生碰撞，則進(jìn)入（5）；否則依次進(jìn)入(1)-(4)；(5)：應(yīng)用中點(diǎn)法填補(bǔ)這兩個節(jié)點(diǎn)間的空白路徑段，完成變異步驟。23遺傳算法在機(jī)器人路徑規(guī)劃中的應(yīng)用遺傳算子：4.修復(fù)算子：盡管交叉和變異操作可以增加種群的多樣性，但可能會導(dǎo)致生成的路徑包含冗余路徑段。為了確保獲得最優(yōu)