基于DFS的二指雙臂魔方機器人

崔俊文 劉自紅 鄧明洋 樂玉

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

關鍵詞：魔方復原;視覺識別;坐標系構建與仿真;深度優先搜索

中圖分類號：TP249? ? 文獻標識碼：A

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

開放科學（資源服務）標識碼（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

隨著工業發展的逐步推進，機器人產業如雨后春筍在全國范圍內遍地開花，自動化成了新時代的潮流，“機器換人”的概念逐漸成為現實，智能化的局面已經大勢所趨。“機器人的革命”，有望成為第三次工業革命的一個重要切入點和增長點，將影響全球制造業格局，其市場前景也是可期的。

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

1 魔方機器人設計

1.1 機械結構

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

1.2 工作流程

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

2 視覺識別

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

仿射變換后的面已經被旋轉矯正，只需按特定坐標順序讀取魔方面信息。全部魔方面信息仿射變換后效果為圖4。采用K-mean算法進行識別，該方法自動實現識別過程，且具有很強的抗干擾能力。

3 魔方編碼執行及坐標系構建

3.1 編碼轉化執行

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

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

3.2 坐標系構建

構建魔方相對坐標系，在雙手臂執行求解魔方過程中，需要對執行的魔方面在相對坐標系中進行搜索，再執行面切換和旋轉操作。

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

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

4 深度優先搜索優化模型建立

4.1 問題闡述

DFS算法是一種用于遍歷或搜索樹或圖的算法，當一個問題的實現方式有許多種的時候可以實現選擇方式的最優。采用了計算機遞歸的思想。單獨采用DFS采用了暴力枚舉的方式，回溯算法是類似枚舉的搜索的嘗試過程，當發現已經不滿足求解條件就“回溯返回”，回溯帶有剪枝算法，減去一些已經不滿足要求的狀態節點，從而在更少的狀態節點中生成目標。考慮本文中的問題已經兩種算法的優點，模型把問題轉化為一個帶權重的二叉樹，尋找最短路徑的問題。運動DFS+回溯算法在搜索最優模型中去除已經不滿足條件的路徑，以最短的時間，最少的計算量輸出最優的結果。

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

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

4.2 優化模型

建立一個帶權重的二叉樹模型。每一個分叉代表執行2和4坐標選擇左手轉面或者是右手轉面。解決問題的標志為已經全部遍歷完所有滿足要求的節點，并且輸出最優的執行效益。

動作分配：1）手指張開和閉合;2）手轉90度;3）手轉180度）。編碼對應的執行過程都是2和4坐標左手轉面或右手轉面的編列組合。動作權重設定與實際硬件時間成正比，依據手指張合及手臂旋轉時間占優狀況設定權重如表2。

得到魔方執行編碼，初始化最優權重和無窮大。進行算法搜索，遇分岔點1）先標志分叉點，保存當前狀態，2）在從左手轉面開始3）回到最近的保存點，消除標記4）從右邊開始走。每走完一條路徑更新最優的路徑權重和，走完一步后進行權重累加，如果當前權重和已經大于保存的最優的權重和那么直接回到最近分叉點的右邊繼續搜索。直到沒有保存的分叉點為止。模型闡述如圖8。（這里接觸面或對面是對于執行面為左手或者右手的接觸面或對面）。

4.4 優化模型偽代碼實現

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

魔方編碼的索引 index;

上一個分叉點指令長度 length.

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

1：初始化add_weight_optimal無窮大，add_weight_current為0，初始化各個動作對應的權重

2：調用函數CubeCodeOptimal（cube_code，0，0）;

3：if index >= length_of（cube_code） 一條路徑已經不能繼續走了 then

4：? ? if add_weight_current < add_weight_optimal then

5：? ? ? ? add_weight_optimal = add_weight_current

6：? ? ? ? 更新optimal_instruction為當前新的指令

7： return 回到上一個分叉點

8： ? ?end if

9：end if

10：if add_weight_current >= add_weight_optimal 如果當前路徑已經大于最優路徑 then

11：? ? return 回到上一個分叉點

12：end if

13：if 當前面是左右手接觸面或者對面 then

14：? ? current_instruction追加相應指令

15： add_weight_current進行加權

16： index += 1

17： 坐標進行相應變換

18： return CubeCodeOptimal（cube_code，index，length）

19：end if

20：else 當前面是兩只手的非接觸面和非對面 then

21： 暫存參數，先左手進行轉面

22：? ? current_instruction追加相應指令

23： add_weight_current進行加權

24： index += 1

25： 坐標進行相應變換

26： return CubeCodeOptimal（cube_code，index，length）

27： 恢復相關參數進行右手轉面

28：? ? current_instruction追加相應指令

29： add_weight_current進行加權

30： index += 1

31： 坐標進行相應變換

32： return CubeCodeOptimal（cube_code，index，length）

33：end if

輸出： 最優解碼指令 optimal_instruction.

4.4 實例驗證

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

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

由于全局路徑優化空間巨大，機械步執行時間效益不同，可能導致的最終執行效益存在差別。同樣對表3中執行編碼進行DFS優化并轉換機械執行步。權重參數設定依據為表2，其表達三組不同機械執行步占優狀況。其中權重1-1-1對應的權重和直接為其機械執行步數。對機械執行步數優化結果取前5，并求取權重和。圖10中分析手指張合在時間上占優的權重和。可以發現最少的機械執行步在趨勢上代表較優的執行效益，但不一定代表最優的執行效益。圖10中分析手臂旋轉時間占優的權重和。分析可得在手臂旋轉時間占優時，則未表現出機械執行步數較多而執行效益較優的結果。綜合分析可得，對于全局優化問題，還需要依據具體硬件執行不同機械步的時間效益來確定最優的執行方案。

5 結束語

該魔方機器人利用視覺提取魔方信息，采用一維坐標轉換及檢索方式描述魔方坐標變換，將魔方執行編碼轉化為相應機械執行步，并利用DFS搜索最短機械執行步。依據不同硬件條件下，不同機械執行步所占的時間優勢不同，設定機械步權重，尋找一種最優的執行效益組合。最終充分優化了系統求解魔方的時間。

參考文獻：

[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]魏金麗， 范鑫賀， 劉蓮蓮， 等. 基于深度優先遍歷算法-回溯算法的公交網絡限時免費換乘優化模型求解[J]. 科學技術與工程， 2017（10）：309-312.

[5] 李萍. 迪杰斯特拉算法的改進與實現[J].信息化建設，2016（2）.

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

[7] 梁小龍. 解魔方算法的研究和系統實現[D].東北大學，2013.

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

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

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

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

[12]高達. 基于STM32雙臂魔方機器人的設計[J]. 電子產品世界， 2018， 25（11）：61-63.

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

【通聯編輯：梁書】