崔俊文 劉自紅 鄧明洋 樂玉

摘要：本文提出一種二指雙臂的解魔方自動化系統(tǒng)，其可以自主完成魔方顏色提取、求解和還原過程。首先利用雙攝像頭對魔方面進(jìn)行色彩信息提取，編碼后利用kociemba算法求解魔方，解碼后依據(jù)自定義空間坐標(biāo)，利用DFS-回溯算法規(guī)劃機(jī)械執(zhí)行步，并設(shè)置相應(yīng)權(quán)重，全局優(yōu)化雙手臂求解步驟及時(shí)間。在該算法下，該套系統(tǒng)可以快速求解魔方，并可以得到適應(yīng)硬件執(zhí)行的最優(yōu)結(jié)果。

關(guān)鍵詞：魔方復(fù)原;視覺識別;坐標(biāo)系構(gòu)建與仿真;深度優(yōu)先搜索

中圖分類號：TP249? ? 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2019）24-0194-05

開放科學(xué)（資源服務(wù)）標(biāo)識碼（OSID）：

Two-finger Arm Cube Robot Based on DFS

CUI Jun-wen， LIU Zi-hong*， DENG Ming-yang， LE Yu

（Southwest University of Science and Technology， Mianyang 621010， China）

Abstract： This paper proposes a two-finger double-armed magic cube automation system， which can independently complete the Rubik's cube color extraction， solution and restoration process. Firstly， the dual-camera is used to extract the color information from the magic aspect. After encoding， the kociemba algorithm is used to solve the puzzle. After decoding， according to the custom space coordinates， the DFS-backtracking algorithm is used to plan the mechanical execution steps， and the corresponding weights are set， and the double-arm solution steps are optimized globally. time. Under the algorithm， the system can quickly solve the Rubik's cube and get the optimal result that is adapted to the hardware execution.

Key words： rubik's cube restoration; visual recognition; coordinate system construction and simulation; depth-first search

隨著工業(yè)發(fā)展的逐步推進(jìn)，機(jī)器人產(chǎn)業(yè)如雨后春筍在全國范圍內(nèi)遍地開花，自動化成了新時(shí)代的潮流，“機(jī)器換人”的概念逐漸成為現(xiàn)實(shí)，智能化的局面已經(jīng)大勢所趨?！皺C(jī)器人的革命”，有望成為第三次工業(yè)革命的一個(gè)重要切入點(diǎn)和增長點(diǎn)，將影響全球制造業(yè)格局，其市場前景也是可期的。

魔方（Rubik's Cube）發(fā)展了30多年，最短破解時(shí)間記錄每年都在翻新，除了玩家的練習(xí)與心得之外，最主要靠的就是將公式改進(jìn)。第一屆世界冠軍的成績?yōu)?2s，近年來由于公式的不斷改進(jìn)，加上網(wǎng)絡(luò)發(fā)達(dá)促成魔方達(dá)人之間的相互交流，在2013年3月的比賽中Mats Valk以5.55s刷新了世界紀(jì)錄。隨著機(jī)器人技術(shù)的逐步發(fā)展，將魔方與機(jī)器人技術(shù)相融合在科普領(lǐng)域取得了突破性的進(jìn)展，在計(jì)算速度方面，不再依賴于個(gè)人的靈巧、和對公式的熟練運(yùn)用，更多的是將計(jì)算機(jī)、機(jī)械制造、和電子信息的結(jié)合，解魔方機(jī)器人的整體架構(gòu)和多種變型模式也成了近幾年的熱點(diǎn)。

1 魔方機(jī)器人設(shè)計(jì)

1.1 機(jī)械結(jié)構(gòu)

雙手臂采用步進(jìn)電機(jī)模擬手臂旋轉(zhuǎn)，行程手指氣缸實(shí)現(xiàn)二指夾取魔方中心外延，如圖1所示。雙手臂成90°臥式垂直布局，該種方式有利于保持魔方在空間內(nèi)保持穩(wěn)定不傾斜。分別在氣缸和電機(jī)的驅(qū)動下模擬人手的手指和腕部的運(yùn)動。通過電磁閥控制氣缸的開閉即手的張合，電機(jī)與手部氣缸通過聯(lián)軸器連接，電機(jī)旋轉(zhuǎn)帶動手臂機(jī)械旋轉(zhuǎn)，手臂回旋機(jī)械范圍為正負(fù)360°。

1.2 工作流程

采用雙攝像頭對射魔方棱邊，單次可提取四個(gè)魔方面的色彩信息。在圖像上構(gòu)建魔方浮動框選區(qū)域，該區(qū)域可進(jìn)行調(diào)整位置和尺寸對魔方棱邊視角進(jìn)行框選，單個(gè)子區(qū)域經(jīng)仿射變換實(shí)現(xiàn)對魔方面矯正，經(jīng)高斯濾波后，對每個(gè)色塊區(qū)域進(jìn)行顏色提取，提取后采用K-mean算法進(jìn)行識別分類。通過計(jì)算機(jī)端進(jìn)行顏色采集和編碼生成，利用DFS算法全局優(yōu)化機(jī)械執(zhí)行步編碼，再通過串口通信發(fā)送給STM32下位機(jī)控制單元。下位機(jī)解析機(jī)械執(zhí)行步編碼執(zhí)行雙手臂機(jī)構(gòu)進(jìn)行魔方還原。流程圖見圖2

2 視覺識別

為快速獲取魔方色彩面信息，采用雙攝像頭對棱邊進(jìn)行提取色彩信息。單個(gè)相機(jī)可獲得魔方兩面四邊形色彩區(qū)域。分割為左右兩區(qū)域，并進(jìn)行定輪廓框選。針對四邊區(qū)域進(jìn)行仿射變換獲得正視魔方面圖像，校正后對各顏色塊頂坐標(biāo)色彩區(qū)域進(jìn)行提取，如圖3所示。在色彩空間HSV中進(jìn)行顏色識別，該方法有利于削弱光線強(qiáng)弱對色彩識別的影響。

仿射變換后的面已經(jīng)被旋轉(zhuǎn)矯正，只需按特定坐標(biāo)順序讀取魔方面信息。全部魔方面信息仿射變換后效果為圖4。采用K-mean算法進(jìn)行識別，該方法自動實(shí)現(xiàn)識別過程，且具有很強(qiáng)的抗干擾能力。

3 魔方編碼執(zhí)行及坐標(biāo)系構(gòu)建

3.1 編碼轉(zhuǎn)化執(zhí)行

利用kociemba算法求解魔方，可獲得執(zhí)行編碼，規(guī)定執(zhí)行編碼格式為XN，X表示魔方面坐標(biāo)描述，有F，U，R，D，L，B。N表示對應(yīng)面得執(zhí)行方法，規(guī)定1為順時(shí)針旋轉(zhuǎn)90°，2表示順時(shí)針旋轉(zhuǎn)180°，3表示逆時(shí)針旋轉(zhuǎn)90°。如F2則表示對F面進(jìn)行180°旋轉(zhuǎn)。該執(zhí)行編碼是對魔方面操作的標(biāo)識，機(jī)器人無法直接執(zhí)行，還需轉(zhuǎn)化為機(jī)械執(zhí)行步。

機(jī)械執(zhí)行步主要是機(jī)器人在求解魔方過程中具體動作的執(zhí)行，該轉(zhuǎn)換過程依據(jù)圖5中定義得魔方坐標(biāo)系。機(jī)械執(zhí)行步主要有左手張開（LO），右手張開（RO），左手閉合（LC），右手閉合（RC），左手順時(shí)針旋轉(zhuǎn)90°（L1）， 左手逆時(shí)針旋轉(zhuǎn)90°（L3），左手旋轉(zhuǎn)180°（L2），右手順時(shí)針旋轉(zhuǎn)90°（R1）， 右手逆時(shí)針旋轉(zhuǎn)90°（R3）和右手旋轉(zhuǎn)180°（R2）。示例機(jī)械執(zhí)行步對應(yīng)轉(zhuǎn)換過程參考表1。

3.2 坐標(biāo)系構(gòu)建

構(gòu)建魔方相對坐標(biāo)系，在雙手臂執(zhí)行求解魔方過程中，需要對執(zhí)行的魔方面在相對坐標(biāo)系中進(jìn)行搜索，再執(zhí)行面切換和旋轉(zhuǎn)操作。

將三維空間魔方坐標(biāo)系轉(zhuǎn)化為一維矩陣，前后順序按照絕對空間坐標(biāo)固定的讀取方式，讀取順序按圖6中ID序列。該種方法有利于程序檢索。在每次魔方面執(zhí)行操作結(jié)束后，需要對該記錄魔方坐標(biāo)信息的一維矩陣進(jìn)行刷新紀(jì)錄。對F，U，R，D，L，B每個(gè)執(zhí)行面切換至左手或右手旋轉(zhuǎn)時(shí)，一維坐標(biāo)矩陣則是按一定規(guī)律進(jìn)行變換。以初始化魔方坐標(biāo)系變換為例（圖6）。該過程表明該一維矩陣簡單有效表明魔方相對坐標(biāo)信息。其中操作R（2）和L（4）坐標(biāo)面是旋轉(zhuǎn)朝向至左手臂時(shí)的坐標(biāo)變換。

魔方旋轉(zhuǎn)面時(shí)，可以選擇左手轉(zhuǎn)面或者是右手轉(zhuǎn)面。例如，2和4坐標(biāo)面在相同的執(zhí)行操作下可選擇左手或者右手進(jìn)行求解。1和5坐標(biāo)面最短的執(zhí)行方式是分別選擇右手臂和左手臂去執(zhí)行旋轉(zhuǎn)面操作，然而也可以分別選擇左手臂和右手臂去執(zhí)行。不同執(zhí)行選擇將直接影響后續(xù)的求解執(zhí)行步數(shù)。這里我們只考慮近期的執(zhí)行效益，即1和5兩面分別選擇左手臂和右手臂產(chǎn)生多余執(zhí)行步的方式直接不納入考慮范圍。對此，采用深度優(yōu)先搜索的算法，對2和4坐標(biāo)面左手轉(zhuǎn)面還是右手轉(zhuǎn)面進(jìn)行全局規(guī)劃，已達(dá)到執(zhí)行時(shí)間最短的結(jié)果。當(dāng)2和4坐標(biāo)面為右手轉(zhuǎn)面時(shí)，坐標(biāo)變換存在如圖7變換。

4 深度優(yōu)先搜索優(yōu)化模型建立

4.1 問題闡述

DFS算法是一種用于遍歷或搜索樹或圖的算法，當(dāng)一個(gè)問題的實(shí)現(xiàn)方式有許多種的時(shí)候可以實(shí)現(xiàn)選擇方式的最優(yōu)。采用了計(jì)算機(jī)遞歸的思想。單獨(dú)采用DFS采用了暴力枚舉的方式，回溯算法是類似枚舉的搜索的嘗試過程，當(dāng)發(fā)現(xiàn)已經(jīng)不滿足求解條件就“回溯返回”，回溯帶有剪枝算法，減去一些已經(jīng)不滿足要求的狀態(tài)節(jié)點(diǎn)，從而在更少的狀態(tài)節(jié)點(diǎn)中生成目標(biāo)?？紤]本文中的問題已經(jīng)兩種算法的優(yōu)點(diǎn)，模型把問題轉(zhuǎn)化為一個(gè)帶權(quán)重的二叉樹，尋找最短路徑的問題。運(yùn)動DFS+回溯算法在搜索最優(yōu)模型中去除已經(jīng)不滿足條件的路徑，以最短的時(shí)間，最少的計(jì)算量輸出最優(yōu)的結(jié)果。

算法步驟優(yōu)化是對全局機(jī)械執(zhí)行步所消耗時(shí)間的優(yōu)化。前期的執(zhí)行過程將影響后期是否要進(jìn)行換面步驟，對所有面考慮“左撇子”和“右撇子”時(shí)，該問題則是極其復(fù)雜的，且由于實(shí)際過程中魔方執(zhí)行編碼基本在20步左右，對后續(xù)執(zhí)行的長期影響不是特別明顯。簡化優(yōu)化問題，除去在近期沒有明顯效益的執(zhí)行，如1和5兩坐標(biāo)面分別選擇左手臂和右手臂轉(zhuǎn)面，3和0坐標(biāo)面分別選擇左手臂和右手臂轉(zhuǎn)面產(chǎn)生多余執(zhí)行步的方式直接不納入考慮范圍。只考慮對執(zhí)行機(jī)械效益相同的進(jìn)行DFS優(yōu)化，如2和4坐標(biāo)面可以左手轉(zhuǎn)面或者右手轉(zhuǎn)面，所以則是對二叉樹模型進(jìn)行深度優(yōu)先搜索。

機(jī)械執(zhí)行步分為手部旋轉(zhuǎn)和氣缸手指張合兩部分組成，他們在不同硬件及算法條件下所占的執(zhí)行時(shí)間有極大的差異。因此導(dǎo)致可能機(jī)械執(zhí)行步最少的解法相對于機(jī)械執(zhí)行步相對較多的，在硬件執(zhí)行上時(shí)間更長。對具體機(jī)械執(zhí)行設(shè)置權(quán)重，具體參數(shù)依據(jù)硬件設(shè)施決定。該問題進(jìn)一步為機(jī)械執(zhí)行步綜合獲取最優(yōu)效益。

4.2 優(yōu)化模型

建立一個(gè)帶權(quán)重的二叉樹模型。每一個(gè)分叉代表執(zhí)行2和4坐標(biāo)選擇左手轉(zhuǎn)面或者是右手轉(zhuǎn)面。解決問題的標(biāo)志為已經(jīng)全部遍歷完所有滿足要求的節(jié)點(diǎn)，并且輸出最優(yōu)的執(zhí)行效益。

動作分配：1）手指張開和閉合;2）手轉(zhuǎn)90度;3）手轉(zhuǎn)180度）。編碼對應(yīng)的執(zhí)行過程都是2和4坐標(biāo)左手轉(zhuǎn)面或右手轉(zhuǎn)面的編列組合。動作權(quán)重設(shè)定與實(shí)際硬件時(shí)間成正比，依據(jù)手指張合及手臂旋轉(zhuǎn)時(shí)間占優(yōu)狀況設(shè)定權(quán)重如表2。

得到魔方執(zhí)行編碼，初始化最優(yōu)權(quán)重和無窮大。進(jìn)行算法搜索，遇分岔點(diǎn)1）先標(biāo)志分叉點(diǎn)，保存當(dāng)前狀態(tài)，2）在從左手轉(zhuǎn)面開始3）回到最近的保存點(diǎn)，消除標(biāo)記4）從右邊開始走。每走完一條路徑更新最優(yōu)的路徑權(quán)重和，走完一步后進(jìn)行權(quán)重累加，如果當(dāng)前權(quán)重和已經(jīng)大于保存的最優(yōu)的權(quán)重和那么直接回到最近分叉點(diǎn)的右邊繼續(xù)搜索。直到?jīng)]有保存的分叉點(diǎn)為止。模型闡述如圖8。（這里接觸面或?qū)γ媸菍τ趫?zhí)行面為左手或者右手的接觸面或?qū)γ妫?/p>

4.4 優(yōu)化模型偽代碼實(shí)現(xiàn)

輸入： 魔方編碼 cube_code = {（x1，y1），（x2，y2），...，（xm，ym）};

魔方編碼的索引 index;

上一個(gè)分叉點(diǎn)指令長度 length.

過程： 函數(shù)CubeCodeOptimal（cube_code，index，length）遞歸方法

1：初始化add_weight_optimal無窮大，add_weight_current為0，初始化各個(gè)動作對應(yīng)的權(quán)重

2：調(diào)用函數(shù)CubeCodeOptimal（cube_code，0，0）;

3：if index >= length_of（cube_code） 一條路徑已經(jīng)不能繼續(xù)走了 then

4：? ? if add_weight_current < add_weight_optimal then

5：? ? ? ? add_weight_optimal = add_weight_current

6：? ? ? ? 更新optimal_instruction為當(dāng)前新的指令

7： return 回到上一個(gè)分叉點(diǎn)

8： ? ?end if

9：end if

10：if add_weight_current >= add_weight_optimal 如果當(dāng)前路徑已經(jīng)大于最優(yōu)路徑 then

11：? ? return 回到上一個(gè)分叉點(diǎn)

12：end if

13：if 當(dāng)前面是左右手接觸面或者對面 then

14：? ? current_instruction追加相應(yīng)指令

15： add_weight_current進(jìn)行加權(quán)

16： index += 1

17： 坐標(biāo)進(jìn)行相應(yīng)變換

18： return CubeCodeOptimal（cube_code，index，length）

19：end if

20：else 當(dāng)前面是兩只手的非接觸面和非對面 then

21： 暫存參數(shù)，先左手進(jìn)行轉(zhuǎn)面

22：? ? current_instruction追加相應(yīng)指令

23： add_weight_current進(jìn)行加權(quán)

24： index += 1

25： 坐標(biāo)進(jìn)行相應(yīng)變換

26： return CubeCodeOptimal（cube_code，index，length）

27： 恢復(fù)相關(guān)參數(shù)進(jìn)行右手轉(zhuǎn)面

28：? ? current_instruction追加相應(yīng)指令

29： add_weight_current進(jìn)行加權(quán)

30： index += 1

31： 坐標(biāo)進(jìn)行相應(yīng)變換

32： return CubeCodeOptimal（cube_code，index，length）

33：end if

輸出： 最優(yōu)解碼指令 optimal_instruction.

4.4 實(shí)例驗(yàn)證

由于魔方求解問題復(fù)雜，每次獲得的求解編碼沒有任何規(guī)律可言。此處，使用kociemba算法求解魔方，并選舉了四組有代表性的執(zhí)行編碼進(jìn)行分析具體如表3。

對以上執(zhí)行編碼進(jìn)行機(jī)械執(zhí)行步轉(zhuǎn)換。轉(zhuǎn)換的基本條件是優(yōu)先當(dāng)前的最短執(zhí)行路徑，其次針對2和4坐標(biāo)面左手轉(zhuǎn)面或右轉(zhuǎn)面問題進(jìn)行全局執(zhí)行效益優(yōu)化。未優(yōu)化狀況則是2和4坐標(biāo)面全部為右手轉(zhuǎn)面。同時(shí)，也求解出最多機(jī)械執(zhí)行步進(jìn)行對比。優(yōu)化狀況是DFS算法優(yōu)化出的最短機(jī)械執(zhí)行步結(jié)果。設(shè)置權(quán)重1-1-1，求解表3中編碼獲得機(jī)械執(zhí)行步對比圖9。從圖中可以看出該DFS算法具有明顯的優(yōu)化效果。對比最長執(zhí)行步和最短執(zhí)行步，可知在雙手臂求解魔方過程中，全局執(zhí)行路徑優(yōu)化空間是極大的。

由于全局路徑優(yōu)化空間巨大，機(jī)械步執(zhí)行時(shí)間效益不同，可能導(dǎo)致的最終執(zhí)行效益存在差別。同樣對表3中執(zhí)行編碼進(jìn)行DFS優(yōu)化并轉(zhuǎn)換機(jī)械執(zhí)行步。權(quán)重參數(shù)設(shè)定依據(jù)為表2，其表達(dá)三組不同機(jī)械執(zhí)行步占優(yōu)狀況。其中權(quán)重1-1-1對應(yīng)的權(quán)重和直接為其機(jī)械執(zhí)行步數(shù)。對機(jī)械執(zhí)行步數(shù)優(yōu)化結(jié)果取前5，并求取權(quán)重和。圖10中分析手指張合在時(shí)間上占優(yōu)的權(quán)重和?？梢园l(fā)現(xiàn)最少的機(jī)械執(zhí)行步在趨勢上代表較優(yōu)的執(zhí)行效益，但不一定代表最優(yōu)的執(zhí)行效益。圖10中分析手臂旋轉(zhuǎn)時(shí)間占優(yōu)的權(quán)重和。分析可得在手臂旋轉(zhuǎn)時(shí)間占優(yōu)時(shí)，則未表現(xiàn)出機(jī)械執(zhí)行步數(shù)較多而執(zhí)行效益較優(yōu)的結(jié)果。綜合分析可得，對于全局優(yōu)化問題，還需要依據(jù)具體硬件執(zhí)行不同機(jī)械步的時(shí)間效益來確定最優(yōu)的執(zhí)行方案。

5 結(jié)束語

該魔方機(jī)器人利用視覺提取魔方信息，采用一維坐標(biāo)轉(zhuǎn)換及檢索方式描述魔方坐標(biāo)變換，將魔方執(zhí)行編碼轉(zhuǎn)化為相應(yīng)機(jī)械執(zhí)行步，并利用DFS搜索最短機(jī)械執(zhí)行步。依據(jù)不同硬件條件下，不同機(jī)械執(zhí)行步所占的時(shí)間優(yōu)勢不同，設(shè)定機(jī)械步權(quán)重，尋找一種最優(yōu)的執(zhí)行效益組合。最終充分優(yōu)化了系統(tǒng)求解魔方的時(shí)間。

參考文獻(xiàn)：

[1] Rathi G ， Goel S . Applications of Depth First Search： A Survey[J]. Paris， 2013.

[2] Bruce J ， Balch T ， Veloso M . Fast and Cheap Color Image Segmentation for Interactive Robots[C]// Proceedings. 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS 2000） （Cat. No.00CH37113）. IEEE， 2002.

[3] C. Zieliński， Szynkiewicz W， Winiarski T， et al. Rubik's cube as a benchmark validating MRROC++ as an implementation tool for service robot control systems[J]. Industrial Robot， 2007， 34（5）：368-375（8）.

[4]魏金麗， 范鑫賀， 劉蓮蓮， 等. 基于深度優(yōu)先遍歷算法-回溯算法的公交網(wǎng)絡(luò)限時(shí)免費(fèi)換乘優(yōu)化模型求解[J]. 科學(xué)技術(shù)與工程， 2017（10）：309-312.

[5] 李萍. 迪杰斯特拉算法的改進(jìn)與實(shí)現(xiàn)[J].信息化建設(shè)，2016（2）.

[6] 賁可榮， 陳火旺. 計(jì)算機(jī)求解魔方算法[J].計(jì)算技術(shù)與自動化，1992（3）：31-37.

[7] 梁小龍. 解魔方算法的研究和系統(tǒng)實(shí)現(xiàn)[D].東北大學(xué)，2013.

[8] 李澤萱， 滕旭陽， 鄭藝彬，等. 基于Arduino的兩臂解魔方機(jī)器人——算法設(shè)計(jì)[J].電腦知識與技術(shù)， 2018，14（17）：248-250.

[9] 唐日成， 宋偉， 李澤萱，等.基于ARDUNO單片機(jī)的魔方機(jī)器人解決方案——機(jī)械變換控制[J]. 電腦知識與技術(shù)， 2018，14（17）：267-268.

[10]劉遠(yuǎn)法，周屹.基于Arduino單片機(jī)的解魔方機(jī)器人——控制部分[J].電腦知識與技術(shù)， 2016， 12（7）：171-173.

[11]熊曉松， 李朝朝. 基于Arduino的機(jī)器手臂控制[J]. 數(shù)字技術(shù)與應(yīng)用， 2017（2）：3-3.

[12]高達(dá). 基于STM32雙臂魔方機(jī)器人的設(shè)計(jì)[J]. 電子產(chǎn)品世界， 2018， 25（11）：61-63.

[13]盛慶華， 杜永均， 羅飛， 等. 基于STM32機(jī)械臂解魔方算法研究[J]. 實(shí)驗(yàn)室研究與探索， 2017（4）.

【通聯(lián)編輯：梁書】