基于改進A＊算法的三維智能布線技術研究＊

朱永輝 張勝文 支辰羽 羅瑞旭 李 坤

（江蘇科技大學機械工程學院，江蘇 鎮(zhèn)江 212003）

線路設計是機電類產品設計制造過程中不可缺少的關鍵環(huán)節(jié)，線纜作為機電類產品的神經，擔負著聯(lián)系控制系統(tǒng)、配電箱、照明燈、空調和通風扇等電子設備的重任。隨著機電類產品向大規(guī)模定制的方向不斷發(fā)展，其布線結構與布線路徑也越發(fā)復雜多樣，線纜設計對產品性能和可靠性的影響也越來越大[1]，線纜的布設質量直接關系著機電類產品的安全性和功能性。

傳統(tǒng)的布線設計過程主要通過二維CAD 圖紙完成電路設計以及規(guī)劃出線路的進出口，線纜路徑由工藝人員在實際布線時根據產品的裝配結構以及個人經驗進行設計，并根據布線的實際情況對結構設計問題進行反饋，反推設計人員優(yōu)化結構設計，屬于邊生產邊修改的設計方法[2]。這種線路設計方法嚴重滯后被動，布線操作難度大，缺乏指導性，同時會增加產品研發(fā)周期，不適用于大規(guī)模定制趨勢下的產品線路設計。因此，研究三維環(huán)境下的智能布線方法尤為重要。

隨著計算機輔助設計技術與軟件的不斷發(fā)展，國內外專家對線路設計技術的研究也愈發(fā)深入。Conru A B 等[3]通過遺傳算法對線纜的最優(yōu)路徑進行求解，同時采用并行工程的方法進行布線設計。Ilknur K 等[4]提出了使用隨機路徑圖法計算布線路徑的路徑規(guī)劃算法以應對針對復雜環(huán)境下的布線問題。蔡毅等[5]通過綜合“迷宮法”“線搜索法”等搜索算法和路徑干涉理論，提出了“按面自動布線”和“貼壁干涉自動調整”的方法，但對于布線環(huán)境復雜，布線路徑多的產品適用性差。吳保勝等[6]提出了一種基于改進蟻群算法的線纜路徑規(guī)劃方法，通過分段式空間劃分和柵格化處理獲取三維布線路徑的規(guī)劃空間，但線纜路徑基于自由空間生成，不適用于規(guī)定了走線通道的復雜產品的布線。李春泉等[7]提出了基于輪廓擴展法和改進RRT 算法實現(xiàn)了回轉空間內電氣線纜的自動布線。綜上可知，三維布線技術的核心在于線纜路徑的智能規(guī)劃，而現(xiàn)有研究成果主要適用于自由空間的線路規(guī)劃，不適用于具有特定走線空間的大規(guī)模復雜機電類產品的線路規(guī)劃。

本文針對上述問題，在上述學者研究的基礎上提出了一種基于SolidWorks 平臺的三維智能布線方法，通過改進A*算法進行線纜的路徑規(guī)劃，并提出了一種基于通道網絡的布線空間構建方法，約束布線路徑的生成，保證布線路徑的正確性。同時通過SolidWorks 二次開發(fā)，開發(fā)出了相對應的布線系統(tǒng)，實現(xiàn)了特定走線空間條件下的三維線纜智能布路，驗證了該三維智能布線方法的可行性。

1 方法介紹

為實現(xiàn)三維設計環(huán)境下電氣線纜的智能布線，本文基于SolidWorks 平臺進行三維智能布線技術研究，提出了一種三維智能布線方法，其布線流程如圖1 所示。

圖1 SolidWorks 智能布線流程

本文提出的布線方法主要包括前期準備、線纜智能敷設和報表輸出3 個環(huán)節(jié)。

（1）在前期準備環(huán)節(jié)中，要對產品三維模型和電氣零部件庫的進行創(chuàng)建與裝配，并將線槽，PVC 管等走線通道以及錨定線路起點和終點的電器元件裝配到需要布線的三維實體模型中，搭建出三維布線的基礎環(huán)境。

（2）線纜智能敷設主要包括走線空間定義、走線路徑智能規(guī)劃、三維線纜敷設3 個部分。通過路徑搜索算法智能規(guī)劃出最優(yōu)的走線路徑，并通過定義走線空間約束路徑搜索的范圍，保證走線路徑規(guī)劃的正確性，同時在SolidWorks 平臺基于走線路徑生成線纜的三維實體模型，完成三維線纜敷設。

（3）報表輸出環(huán)節(jié)主要是將線路的起點與終點、線纜型號、線纜長度以報表的形式輸出，用于指導生產。

2 關鍵技術

2.1 布線空間定義

在三維布線設計過程中，產品三維實體模型與其內外部空間構成了基礎的布線環(huán)境，同時產品三維實體模型也作為線纜布路的空間障礙物，為了防止生成的線纜路徑與產品實體模型產生干涉，首先需要對線纜的可布線空間進行定義，即確定可進行路徑搜索的范圍。

現(xiàn)有研究對于布線空間的定義方法普遍采用包圍盒技術（bounding box, BB），是三維物體干涉檢測中常用的一種檢測方法，其主要策略是用體積較大的簡單形體近似地表達外形較為復雜的集合對象形體，然后對包圍盒進行相交檢測，求解出自由空間和障礙物空間，將自由空間作為布線空間[8]。但在大型復雜機電類產品中，在結構設計階段已經布置了線槽、PVC 管和走線矩管等型材用于布線，即產品的布線通道是確定的，通過包圍盒技術求解出的布線空間過于寬泛，因此該方法定義的布線空間與實際的布線空間很大程度上不相符，導致路徑搜索算法規(guī)劃出的走線路徑不符合要求。

針對上述問題本文提出了基于通道網絡的布線空間定義方法，保證了布線空間定義的正確性，其流程如圖2 所示，具體步驟如下。

圖2 布線空間定義流程

步驟1：在布線環(huán)境中通過3D 草圖沿線槽、PVC 管等走線通道的中心繪制出如圖3 所示布線通道網絡，定義出通道走向。

圖3 布線空間定義示意圖

步驟2：以走線通道網絡為中心軸線，將其一定范圍內的空間定義為布線空間，如圖3 所示。

步驟3：將定義出的布線空間劃分成一個三維空間點集合，便于后續(xù)路徑搜索使用。

在空間劃分的方法中，柵格法是目前最簡單、常用、便捷的一種方法，其采用空間等分的方法將立方體空間柵格化，將三維空間離散化成路徑搜索所需的一個三維空間點集合，如圖4 所示。

圖4 布線空間柵格化示意圖

2.2 布線路徑規(guī)劃

路徑規(guī)劃是指在有障礙物的工作環(huán)境中尋一條從起點到終點、無碰撞地繞過所有障礙物的運動路徑的過程[9]。布線路徑的智能規(guī)劃是研究三維智能布線技術的核心問題，研究布線路徑路規(guī)劃最重要的就是要保證布線路徑的正確性與合理性，同時要考慮線纜與布線空間內其他障礙物以及與其他線纜之間的干涉問題。

本文提出的三維智能布線方法中布線路徑的智能規(guī)劃通過路徑搜索算法自動完成。

在現(xiàn)有路徑搜索算法中，A*算法是最有效的直接搜索算法之一，其具有可納性和最優(yōu)性[10]。但是在實際的線路設計過程中，對線纜的折彎長度以及折彎次數(shù)都有著一定的要求，使得A*算法難以被直接應用，因此本文針對這一問題對原始A*算法進行了改進和拓展，使其獲得了更高的適用性。

2.2.1 A*算法估價函數(shù)改進

A*算法結合了Dijkstra 算法和BFS 算法的優(yōu)點，將Dijkstra 算法靠近終點的節(jié)點和 BFS 算法靠近目標點的節(jié)點的信息結合起來，并引入了估價函數(shù)對搜索的位置節(jié)點進行評估[11]，該估價函數(shù)一般為

式中：f(n)為節(jié)點n的估價函數(shù)，表示從初始節(jié)點經過節(jié)點n到目標節(jié)點的最佳路徑的代價；g(n)表示在狀態(tài)空間中從初始節(jié)點到節(jié)點n的代價；h(n)為從節(jié)點n到目標節(jié)點的最短路徑的估計代價[12]。

通常設定h(n)計算常用的啟發(fā)式估價函數(shù)為歐幾里得距離函數(shù)（ELDF），ELDF 是指在m維空間中兩個位置節(jié)點之間的真實距離，二維平面中ELDF 的計算公式為可表示為

結合實際電氣布線經驗，在布線路徑規(guī)劃時要考慮到線纜折彎所帶來的損耗問題，因此通過對A*算法的估價函數(shù)進行改進，引入第3 個評估因子q(n)，用來表示從起始節(jié)點到達當前節(jié)點n的折彎損耗[13]，改進后估價函數(shù)為

式中：k為每次折彎損耗轉換成的距離；N為從初始節(jié)點到節(jié)點n的折彎次數(shù)。

A*算法作為1 種二維平面上的路徑搜索算法而被廣泛應用于AGV 小車線路規(guī)劃、游戲地圖等問題上。而本文研究的三維智能布線技術，布線路徑規(guī)劃都是基于三維實體空間進行可行路徑的搜索工作，因此需要將A*算法的適用范圍由二維向三維拓展，拓展后的h(n)計算方式為

2.2.2 A*算法求解流程改進

改進A*算法對最優(yōu)路徑進行求解需要通過3 個基本空間點集：Open 表、Close 表和Lattice 表。其中Open 表用于存放當前節(jié)點可用的相鄰節(jié)點，Close表用于存放求解出的符合要求的路徑節(jié)點，Lattice表儲存本文章節(jié)2.1 中定義的走線空間經過柵格化后劃分出的所有可用空間節(jié)點。改進A*算法在原A*算法求解流程上新增Lattice 表，約束路徑點的搜索范圍，保證了路徑搜索的正確性與效率。改進A*算法流程如圖5 所示，其具體求解步驟如下：

圖5 改進A＊算法流程圖

步驟1：將起始節(jié)點S設置為當前節(jié)點M。

步驟2：判定當前節(jié)點M是否為目標節(jié)點O，若當前節(jié)點M是目標節(jié)點O，則將前節(jié)點M放入Close 表中并輸出Close 表中所有節(jié)點，組成布線路徑。若當前節(jié)點M不是目標節(jié)點O，則轉至步驟3。

步驟3：從Lattice 表循環(huán)搜索當前節(jié)點M的所有鄰居點并計算各個鄰居點的f(n)值，同時將搜索出的所有近鄰節(jié)點加入Open 表中。

步驟4：將當前節(jié)點M從Open 表中刪除，放入Close 表。

步驟5：將Open 表F值最小的鄰居點設置為當前節(jié)點M，并刪除其他鄰居點，轉至步驟2。

步驟6：循環(huán)步驟2 至步驟5，直至求解出的當前節(jié)點M為目標節(jié)點O，則將Close 表中所有節(jié)點按搜索的順序排列即可得到最優(yōu)路徑。

2.3 三維實體線纜敷設

三維實體線纜敷設是指在虛擬環(huán)境下通過建立線纜實體模型的方法來實現(xiàn)對三維空間中線纜姿態(tài)和屬性的表達和可視化的一種方法。三維環(huán)境空間下的線纜實體模型包含幾何特征和信息屬性[14]。

2.3.1 幾何特征

線纜幾何特征包括線纜的幾何形態(tài)、顏色、粗細等信息，線纜幾何模型的建立主要是通過數(shù)字化手段完成對線纜幾何特征的可視化描述和表達。

在SolidWorks 二次開發(fā)中，三維模型驅動方法有編程法和尺寸驅動法。本文線纜幾何模型的構建采用編程法，通過VB.net 編程語言對SolidWorks進行二次開發(fā)來實現(xiàn)。

編程法是將三維模型的所有建模操作和特征的參數(shù)關系都按照固定的順序的編寫成相應的程序，平臺按照程序規(guī)定的建模過程逐步執(zhí)行相應的操作，完成三維模型的生成。這種方法每生成或更新一次模型都需要從頭至尾執(zhí)行一次應用程序代碼[15]。

2.3.2 信息屬性

在實際的產品設計過程中，線纜都有著不同的線纜信息用于線纜間的彼此區(qū)分，線纜信息屬性包括線纜的名稱、編號、型號和材質等，為方便對線纜信息進行統(tǒng)一的儲存、組織和管理，本文通過數(shù)據庫構建相應的線纜信息庫，用于線纜信息的管理，便于將數(shù)據庫表中的線纜信息賦予對應的線纜的幾何模型。

2.3.3 線纜模型構建

通過對線纜幾何特征的創(chuàng)建和信息屬性的填寫，能夠構建出符合需求的線纜三維實體模型用于指導生產。通過對SolidWorks 模型驅動與屬性賦值等API 函數(shù)的應用，結合本文2.2 節(jié)中所述的改進A*算法的求解結果提出了如圖6 所示的三維實體線纜敷設流程，具體步驟如下：

圖6 三維實體線纜敷設流程

步驟1：根據求解出的Close 表中的路徑點，通過SolidWorks 二次開發(fā)，在布線空間中生成中心軸線。

步驟2：根據線纜信息庫中線纜相對應的直徑和顏色，沿線纜三維中心軸線生成線纜幾何特征模型。

步驟3：按照線纜信息庫中線路編號和線纜型號給線纜幾何模型添加相對應的線纜屬性。

3 實例驗證

本文基于上述三維布線關鍵技術的研究，通過Visual Studio2019、SolidWorks2020、SQL Server2008協(xié)同開發(fā)，基于SolidWorks 平臺開發(fā)了相對應的三維智能布線系統(tǒng)，用于驗證本文提出的三維智能布線方法可行性與實用性。

本文以機柜布線為例對該布線系統(tǒng)及方法進行了驗證，首先根據機柜內部線槽的擺放，通過3D草圖繪制出如圖7 所示的機柜的布線通道網絡。

圖7 布線通道草圖網絡繪制

布線通道網絡草圖繪制完成后，打開三維智能布線系統(tǒng)，進入如圖7 所示的布線空間定義界面，在該界面選擇布線通道網絡并根據輸入的通道直徑，定義相對應的布線空間，通過柵格法根據人工定義的劃分密度對該布線空間進行空間劃分，獲取如圖8 所示的布線空間路徑點集，并放入Lattice 表中供后續(xù)路徑搜索使用。

圖8 布線空間定義與劃分

布線空間定義完成后，選擇如圖9 所示的線路設計界面，根據需求定義線路的編號、起始點、終點和線纜型號。布線系統(tǒng)后臺程序根據定義的線路起始點，驅動改進A*算法在圖8 所示的Lattice 表中進行路徑點的搜索，求解出每條線路的最優(yōu)路徑，并將路徑點放入相對應Close 表中。通過選擇圖9中線路列表中定義的線路，可在最優(yōu)路徑點集區(qū)域顯示求解出的相對應最優(yōu)路徑點集。

圖9 線路設計

線纜路徑規(guī)劃完成后，點擊軸線創(chuàng)建按鈕，系統(tǒng)根據求解出的每條線路對應Close 表中的路徑點生成如圖10 所示的線路中心軸線，點擊線纜創(chuàng)建按鈕，根據線路所用線纜的直徑和顏色沿線路中心軸線生成如圖11 所示的線纜三維實體模型。

圖10 線路中心軸線生成

圖11 線纜三維實體生成

線纜敷設完成后，在如圖12 所示的報表輸出界面，可查看線路相對應的線纜信息報表，包含線路的連接關系、線纜長度的信息。線纜信息報表見表1。

表1 線纜信息報表

圖12 改進A＊算法流程圖

4 結語

本文針對三維環(huán)境下的智能布線技術展開了研究，提出了一種基于SolidWorks 的三維智能布線方法，并通過對A*算法的改進和布線空間定義新方法的應用，結合SolidWorks 二次開發(fā)技術開發(fā)了相應的三維智能布線系統(tǒng)，并通過實例驗證了該方法的可行性。結果表明，基于此三維智能布線方法開發(fā)的布線系統(tǒng)能實現(xiàn)布線路徑的快速智能規(guī)劃以及三維實體線纜的快速敷設，極大地提高設計效率、降低成本，具有很高的現(xiàn)實使用價值。