基于改進(jìn)蟻群算法的人機(jī)象棋平面路徑規(guī)劃

朱晨曦，高軍偉，房國(guó)棟，孔德帥

（青島大學(xué) 自動(dòng)化學(xué)院，青島266071）

作為娛樂(lè)機(jī)器人的分支，人機(jī)象棋正逐漸成為研究的熱點(diǎn)。棋盤中，棋子僅存在2 種移動(dòng)，一種按走法，另一種被吃掉后放于指定位置。目前，人機(jī)象棋執(zhí)行多為機(jī)械臂實(shí)現(xiàn)的棋子空間移動(dòng)，無(wú)需考慮障礙。為提高設(shè)備環(huán)境適用性，因此研究人機(jī)象棋

平面避障路徑問(wèn)題具有重要意義。

蟻群算法作為一種尋優(yōu)算法，廣泛應(yīng)用于解決實(shí)際路徑問(wèn)題。針對(duì)算法局部解及收斂等問(wèn)題，文獻(xiàn)[1]將信息素分布限制在固定區(qū)間內(nèi)，算法性能不受信息素下界的影響；文獻(xiàn)[2]建立α 與β 的互鎖關(guān)系，使其動(dòng)態(tài)自適應(yīng)調(diào)整；文獻(xiàn)[3]引入最大最小螞蟻系統(tǒng)，避免蟻群算法早熟停滯；文獻(xiàn)[4]引入動(dòng)態(tài)局部?jī)?yōu)化搜索策略，針對(duì)蟻群不同路徑使用不同信息素，提高了路徑質(zhì)量；文獻(xiàn)[5]提出禁忌搜索的蟻群改進(jìn)算法，優(yōu)化了初始信息濃度，避免局部最優(yōu)解。

在此結(jié)合人機(jī)象棋與蟻群算法，針對(duì)蟻群算法局部解及收斂問(wèn)題，改進(jìn)啟發(fā)因子；針對(duì)棋子和障礙同尺寸問(wèn)題，對(duì)所得最優(yōu)路徑進(jìn)行控制點(diǎn)精簡(jiǎn)，減少拐角次數(shù)，縮短棋子移動(dòng)距離。

1 算法描述

1.1 環(huán)境建模

為使棋子平面移動(dòng)時(shí)避開(kāi)障礙棋子，計(jì)算機(jī)處理棋盤圖像得到10×9 棋盤數(shù)字矩陣后，調(diào)用博弈算法獲得棋局下一步走法，再經(jīng)蟻群算法規(guī)劃路徑，由機(jī)械臂實(shí)現(xiàn)棋子平面避障移動(dòng)。

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

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

式中：i 為柵格編號(hào)；M 為單行柵格個(gè)數(shù)；mod（）為取余；fix（）為向零方向取整作商；Xi和Yi為柵格中心的坐標(biāo)位置。

棋盤柵格建立后，相鄰柵格中心距離dij為1 或1.414，故移動(dòng)棋子被當(dāng)做二維平面中質(zhì)點(diǎn)時(shí)，為避免與障礙棋子發(fā)生碰撞，質(zhì)點(diǎn)只能在上下左右4 個(gè)方向移動(dòng)。移動(dòng)前后柵格應(yīng)滿足：

式中：i 為質(zhì)點(diǎn)當(dāng)前柵格；j 為質(zhì)點(diǎn)下一柵格；map（j）為非障礙柵格；dij為柵格i 與柵格j 之間距離。棋盤擴(kuò)充后的柵格坐標(biāo)系如圖1 所示。

圖1 棋盤擴(kuò)充后柵格坐標(biāo)系Fig.1 Grid coordinate system after checkerboard expansion

1.2 常規(guī)蟻群算法

常規(guī)蟻群算法概率選擇方式主要根據(jù)節(jié)點(diǎn)之間的信息素濃度和啟發(fā)信息來(lái)確定。環(huán)境建模后，初始化數(shù)據(jù)進(jìn)行迭代，螞蟻根據(jù)信息素隨機(jī)尋找路徑直到終點(diǎn)，找到最優(yōu)路線后更新信息素，直至迭代完成。

棋盤柵格化后，由蟻群算法得出的轉(zhuǎn)移概率即為相鄰柵格中心節(jié)點(diǎn)間的選擇概率[8]。在t 時(shí)刻，螞蟻k 從yi轉(zhuǎn)移到y(tǒng)j的概率為

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

2 改進(jìn)蟻群算法

2.1 啟發(fā)矩陣改進(jìn)

常規(guī)啟發(fā)式信息矩陣為節(jié)點(diǎn)i 到下一節(jié)點(diǎn)j 實(shí)際距離倒數(shù)，未考慮終點(diǎn)柵格E 的影響。柵格中，棋子從i 到j(luò) 水平或豎直移動(dòng)時(shí)路徑等長(zhǎng)，因此ηij＝1/dij在棋盤環(huán)境中沒(méi)有效果。為增加算法收斂能力，需要對(duì)其進(jìn)行改進(jìn)，在此引入常量a 和b 對(duì)djE進(jìn)行初等變換，即

式中：djE為下一節(jié)點(diǎn)j 與目標(biāo)節(jié)點(diǎn)E 之間的實(shí)際距離。然后通過(guò)棋盤試驗(yàn)結(jié)果，選擇同時(shí)滿足路徑最短和收斂代次最少的a，b 值。

2.2 信息素的更新策略

馬和象類棋子按走法移動(dòng)時(shí)，障礙棋子不能出現(xiàn)在絆馬腳和塞象眼的位置。為配合djE，棋子向?qū)强繑n，引入“熱區(qū)”概念，熱區(qū)是指當(dāng)前節(jié)點(diǎn)與目標(biāo)節(jié)點(diǎn)為對(duì)角線的矩形區(qū)域。當(dāng)前節(jié)點(diǎn)i 向下一節(jié)點(diǎn)j 隨機(jī)搜索時(shí)，選擇熱區(qū)節(jié)點(diǎn)的概率會(huì)比非熱區(qū)節(jié)點(diǎn)大，可減少不必要方向的搜索[9]。

式中：λ 為常量參數(shù)；i 為每次更新的當(dāng)前節(jié)點(diǎn)；j 為下一節(jié)點(diǎn)。

2.3 最優(yōu)路徑保留

蟻群算法在隨機(jī)搜索路徑過(guò)程，可能會(huì)丟失曾搜索到的最優(yōu)路徑，即本次最短路徑在下次迭代中未出現(xiàn)。棋盤常規(guī)蟻群的仿真收斂曲線如圖2 所示，收斂過(guò)程中最優(yōu)路徑丟失。

圖2 最優(yōu)路徑長(zhǎng)度Fig.2 Length of the optimal path

路徑中，信息素遵循新增和揮發(fā)規(guī)則，最優(yōu)路徑的丟失會(huì)降低該路徑信息素濃度[10]。為提高算法性能，在每次迭代得到最優(yōu)路徑后，都與前次迭代最優(yōu)路徑進(jìn)行比較。若長(zhǎng)度大于前代最優(yōu)路徑，則將前代最優(yōu)路徑加入在本次迭代路徑，在前代最優(yōu)路徑得以保留的同時(shí)，增加算法向已得最優(yōu)路徑的收斂。

2.4 已得路徑的平滑處理

在棋盤柵格中設(shè)定棋子僅水平或豎直移動(dòng)，會(huì)導(dǎo)致拐角次數(shù)的增多。為減少不必要控制點(diǎn)，縮短棋子移動(dòng)距離，需對(duì)已得路徑進(jìn)行控制點(diǎn)精簡(jiǎn)，優(yōu)化已有路徑的整體走向[11]?？刂泣c(diǎn)精簡(jiǎn)如圖3 所示，在此僅為圖1 所示坐標(biāo)系的局部示意圖。

圖3 控制點(diǎn)精簡(jiǎn)示意圖Fig.3 Diagrammatic sketch of reduced control pointn

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

式中：d 為障礙物中心點(diǎn)距離直連虛線路徑最短距離；a 為柵格邊長(zhǎng)。

2.5 蟻群算法改進(jìn)流程

步驟1對(duì)實(shí)時(shí)棋盤10×9 數(shù)字矩陣進(jìn)行擴(kuò)充，并采用柵格法對(duì)結(jié)果柵格化。

步驟2將實(shí)時(shí)棋子始末移動(dòng)位置換算成柵格號(hào)，初始化算法參數(shù)。

ⅰ.螞蟻開(kāi)始路徑選擇，按熱區(qū)尋找下一可行節(jié)點(diǎn)j，僅水平或豎直方向移動(dòng)，得出本次迭代的最優(yōu)路徑；

ⅱ.若本次迭代的最優(yōu)路徑長(zhǎng)于上次迭代最優(yōu)路徑，則上代最優(yōu)路徑加入本次路徑，共同進(jìn)行信息素更新。

步驟3全部迭代完成后得出最優(yōu)路徑。

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

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

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

ⅲ.返回步驟4，循環(huán)完成每段新生成路徑。

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

3 試驗(yàn)結(jié)果仿真

為驗(yàn)證改進(jìn)蟻群算法對(duì)棋盤柵格中棋子路徑規(guī)劃的有效性，以棋子被吃掉后從當(dāng)前位置移至棋局外指定位置為例，通過(guò)MatLab 2014a 對(duì)其仿真?？紤]到參數(shù)取值對(duì)算法性能的影響[12]，設(shè)置α=1.5，β=4.1，ρ=0.64，m=30，Q=14。

3.1 算法改進(jìn)仿真

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

圖4 仿真結(jié)果Fig.4 Simulation results

MatLab 運(yùn)行20 次后的統(tǒng)計(jì)路徑結(jié)果見(jiàn)表1。

表1 算法改進(jìn)前后運(yùn)行20 次的路徑結(jié)果統(tǒng)計(jì)Tab.1 Path result statistics of 20 runs before and after algorithm improvement

由表可知，相較于常規(guī)蟻群算法，信息素更新策略改進(jìn)后的蟻群算法平均路徑長(zhǎng)度降低5.9%，平均收斂次數(shù)降低36.1%，最短路徑長(zhǎng)度雖無(wú)變化，但最小收斂次數(shù)降低34.8%，改進(jìn)后的蟻群算法在平均路徑長(zhǎng)度和收斂速度上比常規(guī)蟻群算法更有優(yōu)勢(shì)。a，b 取不同值后，對(duì)改進(jìn)蟻群算法循環(huán)20 次，路徑結(jié)果統(tǒng)計(jì)見(jiàn)表2。

表2 a，b 取值不同時(shí)改進(jìn)蟻群算法路徑結(jié)果統(tǒng)計(jì)Tab.2 Path result statistics after improving ant colony algorithm with different values of a and b

由表可知，a=1，b=1 時(shí)平均收斂次數(shù)最??；a=2，b=1 時(shí)平均路徑最短，且最少收斂次數(shù)最小。與常規(guī)蟻群算法相比，a=2，b=1 時(shí)改進(jìn)蟻群算法具有更好性能，平均路徑長(zhǎng)度減少6.0%，平均收斂次數(shù)降低35.6%。

3.2 已得路徑的平滑仿真

在棋盤柵格20×20 環(huán)境中，路徑控制點(diǎn)精簡(jiǎn)后路徑長(zhǎng)度23.9，比精簡(jiǎn)前最短路徑長(zhǎng)度35.0，減少31.7%；中間控制點(diǎn)從15 精簡(jiǎn)到5 個(gè)，減少66.7%。棋子運(yùn)動(dòng)軌跡的仿真如圖5 所示。

4 結(jié)語(yǔ)

利用改進(jìn)的蟻群算法求解棋子移動(dòng)路徑，改進(jìn)包括對(duì)啟發(fā)矩陣及信息素更新策略的改進(jìn)，對(duì)棋子多拐角多控制點(diǎn)問(wèn)題的改進(jìn)。改進(jìn)后進(jìn)一步提高了收斂速度，縮短了移動(dòng)距離，能讓棋子在平面移動(dòng)中實(shí)現(xiàn)良好的人機(jī)對(duì)弈過(guò)程，增加適用性。

圖5 路徑控制點(diǎn)精簡(jiǎn)Fig.5 Path control point reduction