基于改進蟻群算法的人機象棋平面路徑規劃

朱晨曦，高軍偉，房國棟，孔德帥

（青島大學 自動化學院，青島266071）

作為娛樂機器人的分支，人機象棋正逐漸成為研究的熱點。棋盤中，棋子僅存在2 種移動，一種按走法，另一種被吃掉后放于指定位置。目前，人機象棋執行多為機械臂實現的棋子空間移動，無需考慮障礙。為提高設備環境適用性，因此研究人機象棋

平面避障路徑問題具有重要意義。

蟻群算法作為一種尋優算法，廣泛應用于解決實際路徑問題。針對算法局部解及收斂等問題，文獻[1]將信息素分布限制在固定區間內，算法性能不受信息素下界的影響；文獻[2]建立α 與β 的互鎖關系，使其動態自適應調整；文獻[3]引入最大最小螞蟻系統，避免蟻群算法早熟停滯；文獻[4]引入動態局部優化搜索策略，針對蟻群不同路徑使用不同信息素，提高了路徑質量；文獻[5]提出禁忌搜索的蟻群改進算法，優化了初始信息濃度，避免局部最優解。

在此結合人機象棋與蟻群算法，針對蟻群算法局部解及收斂問題，改進啟發因子；針對棋子和障礙同尺寸問題，對所得最優路徑進行控制點精簡，減少拐角次數，縮短棋子移動距離。

1 算法描述

1.1 環境建模

為使棋子平面移動時避開障礙棋子，計算機處理棋盤圖像得到10×9 棋盤數字矩陣后，調用博弈算法獲得棋局下一步走法，再經蟻群算法規劃路徑，由機械臂實現棋子平面避障移動。

人機象棋平面博弈系統，由機器視覺、博弈算法、路徑規劃、機械臂執行4 個部分組成。在此，路徑規劃采用了柵格法對棋局進行離散化處理。對博弈算法當前調用的10×9 棋盤數字矩陣實時擴充，有棋子的位置置1，其余位置均以0 填充，最終得到一個20×20 的0 1 矩陣并柵格化，以避免極端情況下，除90 個棋盤橫縱線交叉點[6]所在柵格本身外，相鄰兩交叉點各自所在柵格間仍有柵格可供路徑移動。

考慮象棋外觀尺寸，粒子和障礙物面積應該都按照象棋大小膨脹[7]。設置柵格邊長a＝1，柵格建立時，可將整個棋盤空間劃分成400 個大小相同的柵格，各柵格從左至右、自上而下依次編有序號。序號與坐標系的關系為

式中：i 為柵格編號；M 為單行柵格個數；mod（）為取余；fix（）為向零方向取整作商；Xi和Yi為柵格中心的坐標位置。

棋盤柵格建立后，相鄰柵格中心距離dij為1 或1.414，故移動棋子被當做二維平面中質點時，為避免與障礙棋子發生碰撞，質點只能在上下左右4 個方向移動。移動前后柵格應滿足：

式中：i 為質點當前柵格；j 為質點下一柵格；map（j）為非障礙柵格；dij為柵格i 與柵格j 之間距離。棋盤擴充后的柵格坐標系如圖1 所示。

圖1 棋盤擴充后柵格坐標系Fig.1 Grid coordinate system after checkerboard expansion

1.2 常規蟻群算法

常規蟻群算法概率選擇方式主要根據節點之間的信息素濃度和啟發信息來確定。環境建模后，初始化數據進行迭代，螞蟻根據信息素隨機尋找路徑直到終點，找到最優路線后更新信息素，直至迭代完成。

棋盤柵格化后，由蟻群算法得出的轉移概率即為相鄰柵格中心節點間的選擇概率[8]。在t 時刻，螞蟻k 從yi轉移到yj的概率為

式中：α 為信息素濃度相對重要程度；τij（t）為信息素濃度；β 為啟發性因子相對重要程度；ηij（t）為實際距離的倒數。

2 改進蟻群算法

2.1 啟發矩陣改進

常規啟發式信息矩陣為節點i 到下一節點j 實際距離倒數，未考慮終點柵格E 的影響。柵格中，棋子從i 到j 水平或豎直移動時路徑等長，因此ηij＝1/dij在棋盤環境中沒有效果。為增加算法收斂能力，需要對其進行改進，在此引入常量a 和b 對djE進行初等變換，即

式中：djE為下一節點j 與目標節點E 之間的實際距離。然后通過棋盤試驗結果，選擇同時滿足路徑最短和收斂代次最少的a，b 值。

2.2 信息素的更新策略

馬和象類棋子按走法移動時，障礙棋子不能出現在絆馬腳和塞象眼的位置。為配合djE，棋子向對角靠攏，引入“熱區”概念，熱區是指當前節點與目標節點為對角線的矩形區域。當前節點i 向下一節點j 隨機搜索時，選擇熱區節點的概率會比非熱區節點大，可減少不必要方向的搜索[9]。

式中：λ 為常量參數；i 為每次更新的當前節點；j 為下一節點。

2.3 最優路徑保留

蟻群算法在隨機搜索路徑過程，可能會丟失曾搜索到的最優路徑，即本次最短路徑在下次迭代中未出現。棋盤常規蟻群的仿真收斂曲線如圖2 所示，收斂過程中最優路徑丟失。

圖2 最優路徑長度Fig.2 Length of the optimal path

路徑中，信息素遵循新增和揮發規則，最優路徑的丟失會降低該路徑信息素濃度[10]。為提高算法性能，在每次迭代得到最優路徑后，都與前次迭代最優路徑進行比較。若長度大于前代最優路徑，則將前代最優路徑加入在本次迭代路徑，在前代最優路徑得以保留的同時，增加算法向已得最優路徑的收斂。

2.4 已得路徑的平滑處理

在棋盤柵格中設定棋子僅水平或豎直移動，會導致拐角次數的增多。為減少不必要控制點，縮短棋子移動距離，需對已得路徑進行控制點精簡，優化已有路徑的整體走向[11]。控制點精簡如圖3 所示，在此僅為圖1 所示坐標系的局部示意圖。

圖3 控制點精簡示意圖Fig.3 Diagrammatic sketch of reduced control pointn

圖3 中，A，B，C 拐角位置皆可由虛線路徑代替。循環精簡從第1 個控制點1 開始，依次與其后面所有非相鄰柵格控制點（第3 個控制點22 到目標控制點E，圖中未標出點E）連接成虛線路徑，根據點到直線距離公式，計算當前虛線點1—點22 到全部障礙物中心最短距離d。若d 都不小于則點1—點22 成為新的可行路徑，此段原先控制點被抹除，并從尾點22 開始新層循環，否則不做修改，直至最后。為此，引入變量L，L 為是/否生成新路徑：L=1，生成；L=0，不生成。L 值為

式中：d 為障礙物中心點距離直連虛線路徑最短距離；a 為柵格邊長。

2.5 蟻群算法改進流程

步驟1對實時棋盤10×9 數字矩陣進行擴充，并采用柵格法對結果柵格化。

步驟2將實時棋子始末移動位置換算成柵格號，初始化算法參數。

ⅰ.螞蟻開始路徑選擇，按熱區尋找下一可行節點j，僅水平或豎直方向移動，得出本次迭代的最優路徑；

ⅱ.若本次迭代的最優路徑長于上次迭代最優路徑，則上代最優路徑加入本次路徑，共同進行信息素更新。

步驟3全部迭代完成后得出最優路徑。

步驟4柵格中心控制點精簡方法。將最優路徑中每個控制點依次與其非同一直線上的后面所有控制點都分別連接成待生成新路徑。

ⅰ.通過點到直線距離公式得出d 的大小，判斷所有待生成路徑是否符合新路徑生成條件。如果當前待生成路徑都不符合條件，返回步驟4，否則繼續步驟4ⅱ。

ⅱ.刪除此段之前中間控制點和路徑，由新生成路徑替代。

ⅲ.返回步驟4，循環完成每段新生成路徑。

步驟5輸出完整新生路徑。

3 試驗結果仿真

為驗證改進蟻群算法對棋盤柵格中棋子路徑規劃的有效性，以棋子被吃掉后從當前位置移至棋局外指定位置為例，通過MatLab 2014a 對其仿真。考慮到參數取值對算法性能的影響[12]，設置α=1.5，β=4.1，ρ=0.64，m=30，Q=14。

3.1 算法改進仿真

20×20 棋盤柵格環境中，對基本蟻群算法和對a=1，b=1 的啟發因子及信息素更新策略改進的蟻群算法進行路徑仿真，仿真結果如圖4 所示。

圖4 仿真結果Fig.4 Simulation results

MatLab 運行20 次后的統計路徑結果見表1。

表1 算法改進前后運行20 次的路徑結果統計Tab.1 Path result statistics of 20 runs before and after algorithm improvement

由表可知，相較于常規蟻群算法，信息素更新策略改進后的蟻群算法平均路徑長度降低5.9%，平均收斂次數降低36.1%，最短路徑長度雖無變化，但最小收斂次數降低34.8%，改進后的蟻群算法在平均路徑長度和收斂速度上比常規蟻群算法更有優勢。a，b 取不同值后，對改進蟻群算法循環20 次，路徑結果統計見表2。

表2 a，b 取值不同時改進蟻群算法路徑結果統計Tab.2 Path result statistics after improving ant colony algorithm with different values of a and b

由表可知，a=1，b=1 時平均收斂次數最小；a=2，b=1 時平均路徑最短，且最少收斂次數最小。與常規蟻群算法相比，a=2，b=1 時改進蟻群算法具有更好性能，平均路徑長度減少6.0%，平均收斂次數降低35.6%。

3.2 已得路徑的平滑仿真

在棋盤柵格20×20 環境中，路徑控制點精簡后路徑長度23.9，比精簡前最短路徑長度35.0，減少31.7%；中間控制點從15 精簡到5 個，減少66.7%。棋子運動軌跡的仿真如圖5 所示。

4 結語

利用改進的蟻群算法求解棋子移動路徑，改進包括對啟發矩陣及信息素更新策略的改進，對棋子多拐角多控制點問題的改進。改進后進一步提高了收斂速度，縮短了移動距離，能讓棋子在平面移動中實現良好的人機對弈過程，增加適用性。

圖5 路徑控制點精簡Fig.5 Path control point reduction