摘 要：針對城市軌道交通車輛吹掃機(jī)器人路徑規(guī)劃問題，提出一種基于CHNN神經(jīng)網(wǎng)絡(luò)的全覆蓋路徑規(guī)劃算法，綜合機(jī)器人運(yùn)行方向上障礙物信息與吹掃信息建立柵格地圖，采用矩形分解法將整個工作空間劃分為不同矩形子區(qū)域，在各子區(qū)域內(nèi)基于柵格信息分別得到全覆蓋路徑，各子區(qū)域之間則采用CHNN神經(jīng)網(wǎng)絡(luò)進(jìn)行遍歷尋優(yōu)。仿真結(jié)果表明：所提出的算法可以有效解決吹掃機(jī)器人全覆蓋路徑規(guī)劃過程中的路徑纏繞和清潔死區(qū)問題，降低了路徑重復(fù)率，提高機(jī)器人吹掃效率，具有較好的工程應(yīng)用前景。

關(guān)鍵詞：吹掃機(jī)器人；CHNN神經(jīng)網(wǎng)絡(luò)；全覆蓋； 路徑規(guī)劃

中圖分類號：TP242.3 文獻(xiàn)標(biāo)志碼：B 文章編號：1671-5276（2024）04-0245-05

Research on Intelligent Path Planning of Purging Robot for Rail Vehicles

LIU Jin

（Suzhou Rail Transit Group Co.， Ltd.，Suzhou 215101， China）

Abstract：With regard to the path-planning of urban rail transit vehicle purging robot， a full-coverage path-planning algorithm based on CHNN neural network was proposed. The raster map was established by integrating obstacle information and purging information in the robot's moving direction. The whole workspace was divided into different rectangular sub-regions by rectangular decomposition method， and in each sub-region， the full coverage path was obtained based on grid information， and CHNN neural network was used for traversal optimization between sub-regions. The simulation results show that the proposed algorithm can effectively solve the problems of path winding and cleaning dead zone in the process of full coverage path planning of the robot， reduce the path repetition rate and improve the efficiency of the robot， which has a good prospect of engineering application.

Keywords：purging robot; CHNN neural network; full coverage; path planning

0 引言

城市軌道交通列車吹掃作業(yè)為車輛檢修前的必要工序，目前主要采用人工吹掃，作業(yè)效率低、強(qiáng)度大、環(huán)境差。研究吹掃機(jī)器人代替人工作業(yè)，可有效解決現(xiàn)有人工吹掃作業(yè)存在的問題^[1]。因列車車底零部件多，作業(yè)空間有限，吹掃機(jī)器人需要根據(jù)車底零部件布置以及空間限制合理規(guī)劃吹掃路徑，提高車底吹掃作業(yè)效率。現(xiàn)有全覆蓋路徑規(guī)劃算法多采用將全局路徑規(guī)劃轉(zhuǎn)化為相鄰柵格間局部運(yùn)動決策的思想，可以得到局部最優(yōu)全覆蓋路經(jīng)，但無法保證所得路徑達(dá)到全局最優(yōu)^[2]。因此，針對軌道交通車輛吹掃機(jī)器人路徑規(guī)劃問題，本文提出了一種基于CHNN神經(jīng)網(wǎng)絡(luò)的全覆蓋路徑規(guī)劃算法，通過將柵格地圖劃分為多個形狀規(guī)則的區(qū)域，各子區(qū)域間采用CHNN神經(jīng)網(wǎng)絡(luò)求解最優(yōu)連通路徑，從而高效完成各工作區(qū)域的全覆蓋。仿真結(jié)果表明，該方法可有效降低路徑重復(fù)率，避免機(jī)器人陷入死區(qū)，提高工作效率。

1 基于柵格法的子區(qū)域覆蓋方法

結(jié)合軌道交通車輛吹掃環(huán)境特點(diǎn)，本文采用簡單可靠且易于實現(xiàn)的柵格法進(jìn)行環(huán)境地圖建模^[3]，采用沿邊學(xué)習(xí)法使機(jī)器人沿著邊界或鄰近邊界的障礙物運(yùn)動，通過傳感器實現(xiàn)機(jī)器人對工作環(huán)境整體輪廓的感知^[4]。具體流程為在笛卡兒坐標(biāo)系中將工作地圖按統(tǒng)一規(guī)格劃分為若干個柵格，根據(jù)柵格的位置性質(zhì)信息賦予不同的置信度，從而確定機(jī)器人下一步運(yùn)動方向。柵格大小的選取一般根據(jù)地圖大小、障礙物尺寸形狀、機(jī)器人工作范圍以及算法復(fù)雜度確定。每個柵格需要對實際位置信息、相對位置信息、滯留信息等進(jìn)行描述。

1.1 柵格覆蓋信息與障礙信息的表達(dá)

為避免機(jī)器人與障礙物發(fā)生碰撞，防止機(jī)器人對于非重點(diǎn)區(qū)域的多次重復(fù)遍歷，需要對各柵格的覆蓋信息與障礙物信息進(jìn)行賦值。為了避免對非滯留柵格的重復(fù)覆蓋，對于未覆蓋柵格，設(shè)定其初始柵格信息為1，每覆蓋一次其綜合屬性值會遞減0.5，覆蓋次數(shù)越多屬性值越小，在重復(fù)覆蓋過程中該柵格被選中的可能性越?。煌瑫r為了區(qū)分障礙物柵格，將其柵格信息賦值為-∞。假設(shè)機(jī)器人的工作空間柵格地圖如圖1（a）所示，其中p_p表示機(jī)器人當(dāng)前所處柵格，p_b表示機(jī)器人上一覆蓋柵格，黑色柵格表示障礙物柵格，p_p周圍柵格表示機(jī)器人下一步可能的運(yùn)動方向，根據(jù)柵格地圖計算出的柵格屬性信息如圖1（b）所示。

1.2 柵格相對位置信息的表達(dá)

為了減少吹掃機(jī)器人運(yùn)動過程中頻繁轉(zhuǎn)向引起的能量損耗以及機(jī)器人反向運(yùn)動導(dǎo)致規(guī)劃路徑過于復(fù)雜，引入描述各柵格與機(jī)器人相對位置信息的轉(zhuǎn)向置信函數(shù)，如式（1）所示。

式中：Δθ表示預(yù)選柵格與機(jī)器人當(dāng)前位置夾角；Δφ表示機(jī)器人陷入死區(qū)后最近未覆蓋柵格與機(jī)器人當(dāng)前位置以及預(yù)選柵格之間的夾角，Δθ、Δφ∈[0，π]，均可根據(jù)機(jī)器人柵格坐標(biāo)求出。 當(dāng)機(jī)器人未陷入死區(qū)時，隨著機(jī)器人轉(zhuǎn)向角度增大，轉(zhuǎn)向置信度值不斷減小，機(jī)器人總是趨向于朝著偏航角度小的方向運(yùn)動，遠(yuǎn)離已覆蓋區(qū)域的方向，且機(jī)器人更偏向于直行；當(dāng)機(jī)器人陷入死區(qū)后，轉(zhuǎn)向置信度隨機(jī)器人下一步運(yùn)動方向與最近未覆蓋柵格之間角度的減小而增大，因此機(jī)器人會朝著最近未覆蓋柵格的方向運(yùn)動，可使機(jī)器人迅速逃離死區(qū)。

當(dāng)機(jī)器人陷入死區(qū)后，需要先確定最近未覆蓋柵格位置，然后根據(jù)轉(zhuǎn)向置信度函數(shù)確定機(jī)器人逃離死區(qū)的路線^[5]。最近未覆蓋柵格采用環(huán)形搜索法確定。以當(dāng)前死點(diǎn)位置為中心，以當(dāng)前柵格與未覆蓋柵格之間的歐式距離為半徑進(jìn)行搜索，直至找到最近未覆蓋柵格位置。吹掃機(jī)器人工作時除無障礙遍歷工作空間外，還需對車底重點(diǎn)零部件位置進(jìn)行集中吹掃。因此，將機(jī)器人工作空間中重點(diǎn)零部件所在位置設(shè)為滯留柵格，機(jī)器人途經(jīng)滯留柵格時，需要停留在當(dāng)前柵格，更改吹掃速度等參數(shù)。柵格i的滯留屬性根據(jù)參數(shù)γ_i確定。利用柵格法建立二維仿真地圖的柵格地圖如圖2（a）所示，采用（x_i，y_i，α_i，β_i，γ_i）的坐標(biāo)形式對其各柵格屬性進(jìn)行賦值，如圖2（b）所示。其中紅色柵格表示起點(diǎn)位置，紫色柵格表示終點(diǎn)位置，綠色柵格表示已覆蓋路徑，青色柵格表示機(jī)器人當(dāng)前位置（本刊黑白印刷，相關(guān)疑問咨詢作者）。

1.3 機(jī)器人工作空間子區(qū)域覆蓋方法

子區(qū)域分割采用“矩形分解法”，通過豎直與水平兩條直線從左到右、從下往上將工作空間分兩次劃分為獨(dú)立的子區(qū)域。子區(qū)域的面積越大，則機(jī)器人直線行走可覆蓋區(qū)域面積越大，需要轉(zhuǎn)彎的次數(shù)越少，可間接提高機(jī)器人工作效率。對于如圖2（a）、圖2（b）所示工作空間，采用矩形分解法得到S1—S11共11個子區(qū)域，如圖2（c）所示。

2 基于CHNN神經(jīng)網(wǎng)絡(luò)的路徑規(guī)劃算法

2.1 CHNN網(wǎng)絡(luò)基本原理

CHNN是一種單層互相全連接的反饋型神經(jīng)網(wǎng)絡(luò)，網(wǎng)絡(luò)中的每個神經(jīng)元將自己的輸出傳遞進(jìn)其他神經(jīng)元，同時接收其他神經(jīng)元的輸入，可模擬神經(jīng)系統(tǒng)中的神經(jīng)回路現(xiàn)象^[6]。其神經(jīng)元輸入與輸出之間的關(guān)系：

式中：X_i表示第i個神經(jīng)元輸入；I_i表示第i個神經(jīng)元的外部輸入；ω_ji表示i、 j神經(jīng)元之間的權(quán)值系數(shù)。

由上式可得，每個神經(jīng)元的輸入隨時間動態(tài)變化，輸入大小與網(wǎng)絡(luò)內(nèi)部輸入以及其他神經(jīng)元的輸出有關(guān)。因此整個網(wǎng)絡(luò)狀態(tài)隨時間動態(tài)變化。通常采用能量函數(shù)對神經(jīng)網(wǎng)絡(luò)的動態(tài)穩(wěn)定性進(jìn)行觀測：

通過設(shè)定各神經(jīng)元間的權(quán)值矩陣與神經(jīng)元的外部輸入，將傳統(tǒng)優(yōu)化問題中的約束條件以及目標(biāo)函數(shù)與CHNN能量函數(shù)聯(lián)系起來，保證網(wǎng)絡(luò)達(dá)到穩(wěn)定時的極值點(diǎn)為待優(yōu)化問題中的最優(yōu)解。

基于各神經(jīng)元之間的全連接關(guān)系，將網(wǎng)絡(luò)結(jié)構(gòu)圖進(jìn)一步展開為環(huán)狀的全連通圖。由此可見，CHNN網(wǎng)絡(luò)可用于求解全連通圖最優(yōu)路徑問題。

2.2 基于CHNN子區(qū)域遍歷路徑優(yōu)化

本文所述全覆蓋路徑規(guī)劃，在對工作空間采用柵格法進(jìn)行子區(qū)域分割后，需對各子區(qū)域之間進(jìn)行遍歷。各子區(qū)域可視為全連通圖，因此可將CHNN網(wǎng)絡(luò)應(yīng)用于子區(qū)域遍歷路徑優(yōu)化，求解步驟如下。

1）建立全連通模型，求解權(quán)值矩陣

將矩形分解法得到的子區(qū)域采用環(huán)形全連接圖表示，同時求出各子區(qū)域間的距離。吹掃機(jī)器人子區(qū)域間的距離除柵格距離外，還應(yīng)考慮機(jī)器人轉(zhuǎn)向等問題，因此，建立如式（4）所示子區(qū)域間距離求解方法。

式中：S_i表示子區(qū)域柵格距離；β_i表示根據(jù)式（1）計算得到的路徑中由轉(zhuǎn)向引起的總置信值；ω₁、ω₂分別表示對應(yīng)的權(quán)重系數(shù)，且二者和為1；T表示覆蓋次數(shù)。得到各子區(qū)域間的相對距離后，需要求解起點(diǎn)區(qū)域與終點(diǎn)區(qū)域間經(jīng)過每個區(qū)域僅一次的最短路徑。采用關(guān)聯(lián)矩陣來標(biāo)志不同區(qū)域的遍歷順序。

2）設(shè)置目標(biāo)函數(shù)與約束條件

得到關(guān)聯(lián)矩陣后，需要對關(guān)聯(lián)矩陣元素進(jìn)行約束，保證每個子區(qū)域只覆蓋一次，同時為保證對所有區(qū)域的完全遍歷，矩陣中所有元素之和需為區(qū)域數(shù)目。設(shè)定如下的約束函數(shù)：

式中：α、β、γ均為非負(fù)系數(shù)；m、n分別表示不同的區(qū)域；k、t分別表示不同遍歷次序；V_xk、V_yt均為關(guān)聯(lián)矩陣元素，取值為0與1，表示是否經(jīng)過該區(qū)域。當(dāng)滿足每次僅訪問一個區(qū)域、每個區(qū)域僅遍歷一次、總遍歷區(qū)域數(shù)目為N時，該函數(shù)取最小值。對求解遍歷子區(qū)域最短路徑問題，目標(biāo)函數(shù)與完成全覆蓋遍歷總距離相關(guān)，如式（6）所示。

式中η為非負(fù)系數(shù)。目標(biāo)函數(shù)取得最小值時，表示路徑代價最小。

3）求解神經(jīng)網(wǎng)絡(luò)狀態(tài)方程

根據(jù)約束條件與目標(biāo)函數(shù)，將二者疊加可得到網(wǎng)絡(luò)能量函數(shù)。根據(jù)以下方程對神經(jīng)網(wǎng)絡(luò)進(jìn)行迭代求解。

式中f（U_mi）為激活函數(shù)，根據(jù)實際需要進(jìn)行選取。

2.3 軌道交通車輛吹掃機(jī)器人路徑規(guī)劃流程

綜上所述，本文采用基于柵格法與CHNN網(wǎng)絡(luò)優(yōu)化方法實現(xiàn)吹掃機(jī)器人全覆蓋路徑規(guī)劃，具體步驟如下：

步驟1，采用沿邊學(xué)習(xí)法獲取機(jī)器人工作空間輪廓信息，在直角坐標(biāo)系下建立二維地圖；

步驟2，對工作空間地圖進(jìn)行柵格分解，確定各柵格坐標(biāo)以及機(jī)器人運(yùn)動起點(diǎn)、終點(diǎn)位置；

步驟3，計算各柵格障礙物信息、相對位置信息等，對各柵格賦值；

步驟4，用矩形分解法對工作地圖進(jìn)行分割，建立子工作區(qū)域全連通模型，計算各子區(qū)域之間的距離D；

步驟5，基于機(jī)器人運(yùn)動優(yōu)先級和柵格信息對各子區(qū)域內(nèi)柵格進(jìn)行完全覆蓋；

步驟6，采用CHNN對各子區(qū)域間的全連通圖進(jìn)行最優(yōu)遍歷路徑求解；

步驟7，結(jié)合各子區(qū)域內(nèi)柵格全覆蓋路徑以及子區(qū)域之間的遍歷路線，確定機(jī)器人全覆蓋路徑規(guī)劃。

3 仿真試驗分析

為了驗證本文算法在吹掃機(jī)器人全覆蓋路徑規(guī)劃中的優(yōu)越性，設(shè)定機(jī)器人工作空間為40×20，如圖3（a）所示。根據(jù)機(jī)器人以及障礙物的實際尺寸設(shè)定每個柵格大小為2×2，因此整個工作空間被劃分為20×10的柵格地圖。為了研究路徑規(guī)劃算法的效果，將機(jī)器人視為質(zhì)點(diǎn)，可以向四周任意方向運(yùn)動，所有障礙物都占據(jù)至少一個柵格并經(jīng)規(guī)則化處理，通過設(shè)定不同障礙物占比模擬不同復(fù)雜度的環(huán)境。處理后的柵格地圖如圖3（b）所示。所有仿真試驗中，參數(shù)K=1，ω₁=0.8，ω₂=0.2。

將本文算法與僅采用柵格法進(jìn)行全覆蓋路徑規(guī)劃的算法對比，對比指標(biāo)包括路徑質(zhì)量、區(qū)域覆蓋率、路徑重復(fù)率等。其中路徑質(zhì)量通過轉(zhuǎn)彎次數(shù)描述，區(qū)域覆蓋率與路徑重復(fù)率分別用完成覆蓋柵格個數(shù)以及重復(fù)覆蓋柵格個數(shù)與工作空間總柵格次數(shù)比值確定。區(qū)域覆蓋率越高，路徑重復(fù)率越低，算法性能越好。

對圖3（a）所示的仿真工作環(huán)境，僅采用柵格法進(jìn)行路徑規(guī)劃，結(jié)果如圖3（c）所示，機(jī)器人對工作空間可達(dá)到100%覆蓋，同時路徑中存在3個死點(diǎn)（圖中黑點(diǎn)標(biāo)注位置），由死點(diǎn)引起的重復(fù)柵格數(shù)目為5個（圖中小方框位置），即路徑重復(fù)率只有2.87%，路徑整體質(zhì)量較好，不存在路徑纏繞問題。

基于CHNN的全覆蓋路徑規(guī)劃根據(jù)矩形分解法劃分得到的子區(qū)域建立的全連通圖如圖4（a）所示，所得路徑如圖4（b）所示。對比柵格法路徑規(guī)劃結(jié)果，CHNN算法得到的路徑可達(dá)到工作空間100%覆蓋，且路徑重復(fù)率降低為1.72%。同時，基于CHNN規(guī)劃的路徑將機(jī)器人的死區(qū)逃離問題轉(zhuǎn)化為子區(qū)域聯(lián)通問題，避免了死區(qū)逃離過程，提高了工作效率。

為進(jìn)一步對比兩種算法的性能，通過增大工作空間中的障礙物占比，得到如圖4（c）所示柵格地圖，在此環(huán)境下兩種算法對比結(jié)果如表1所示。由表1可得，工作環(huán)境越復(fù)雜，基于柵格法的路徑規(guī)劃出現(xiàn)陷入死區(qū)次數(shù)與路徑長度顯著增加，機(jī)器人行走工作效率大幅降低；融入CHNN進(jìn)行路徑規(guī)劃在保證同樣完全覆蓋的前提下，可降低死區(qū)次數(shù)和路徑重復(fù)率，間接提高了吹掃機(jī)器人的工作效率。

4 結(jié)語

本文針對軌道交通車輛吹掃機(jī)器人路徑規(guī)劃問題，提出了一種基于CHNN的全覆蓋路徑規(guī)劃算法，可以在機(jī)器人工作空間內(nèi)無障礙地實現(xiàn)高效覆蓋。通過仿真試驗，對比傳統(tǒng)路徑規(guī)劃方法，得出以下結(jié)論：

1）傳統(tǒng)全覆蓋路徑規(guī)劃方法與本文所述的CHNN路徑規(guī)劃方法的基本思想均為將全局路徑轉(zhuǎn)化為對工作空間各子區(qū)域內(nèi)的完全覆蓋以及子區(qū)域之間的遍歷問題；

2）在障礙物比例高的復(fù)雜環(huán)境中，本文所述方法相對于僅采用柵格法的路徑規(guī)劃方法，可有效降低路徑重復(fù)率，同時可消除機(jī)器人陷入死區(qū)的現(xiàn)象，節(jié)省了死區(qū)逃離路徑選擇的時間，間接提高機(jī)器人工作效率。

本文研究了軌道交通車輛吹掃機(jī)器人全覆蓋路徑規(guī)劃算法，并在仿真實驗環(huán)境下取得了良好的效果，提高了路徑規(guī)劃的效率，后續(xù)需通過改變試驗參數(shù)、微調(diào)算法方案等對規(guī)劃出的路徑進(jìn)行優(yōu)化，以減少機(jī)器人轉(zhuǎn)彎次數(shù)，降低能量損耗，進(jìn)一步提高CHNN全覆蓋路經(jīng)規(guī)劃算法的適用性。

參考文獻(xiàn)：

[1] 趙文濤，朱丹，周小斌，等. 一種集成車底車側(cè)吹掃除塵設(shè)備的吹掃裝置，中國：CN213892447U[P]. 2021-08-06.

[2] 林韓熙，向丹，歐陽劍，等.移動機(jī)器人路徑規(guī)劃算法的研究綜述[J].計算機(jī)工程與應(yīng)用，2021，57（18）：38-48.

[3] 簡毅，高斌，張月.一種室內(nèi)掃地機(jī)器人全遍歷路徑規(guī)劃方法研究[J].傳感器與微系統(tǒng)，2018，37（1）：32-34.

[4] LE A V，NHAN N H K，ELARA MOHAN R. Evolutionary algorithm-based complete coverage path planning for tetriamond tiling robots[J]. Sensors，2020，20（2）：445.

[5] 李少雄，張黎明，曹筱歐，等. 面向電動公交車的充電機(jī)器人感知與控制[J]. 機(jī)械制造與自動化，2021，50（6）： 190-194，198.

[6] 田春穎，劉瑜，馮申珅，等. 基于柵格地圖的移動機(jī)器人完全遍歷算法：矩形分解法[J]. 機(jī)械工程學(xué)報，2004，40（10）：56-61.

收稿日期：2022-12-15