基于Kociemba算法的雙臂解魔方機器人還原算法研究*

盧桂萍，程 開，羅澤奇，吳榮鑫，陳永鍵，康詩鑠

（北京理工大學(xué)珠海學(xué)院工業(yè)自動化學(xué)院，廣東珠海519088）

0 引言

魔方作為極其具有人類智慧的玩具，在日常最為常見的玩法為競速，解魔方機器人（Rubik′s Cube-Solving Robot,RCSR）的目的是讓機器人穩(wěn)定、快速地還原標(biāo)準三階魔方。標(biāo)準三階魔方作為經(jīng)典的人類智力玩具，其還原過程代表著人類邏輯推理運算，三維空間想象等智力行為。雙臂協(xié)作機器人作為機械模仿人類的一個里程碑，通過設(shè)計雙臂解魔方機器人，能進一步讓機器去模仿人類智慧的行為動作，對于制造更具有人類特征的機器人有著重要意義[1-2]。

機械臂作為應(yīng)用最為廣泛的高精度機器人，由于其可以代替人手執(zhí)行大部分人工操作，被廣泛用于工業(yè)自動化生產(chǎn)線等場合。通過設(shè)計開發(fā)解魔方機器人，實現(xiàn)對高精度機械臂的控制，并向工業(yè)領(lǐng)域應(yīng)用拓展[3]。國內(nèi)外的解魔方機器人結(jié)構(gòu)多為六軸電機旋轉(zhuǎn)，本文的研究對象采用雙臂結(jié)構(gòu)，同時在程序算法上，采用高效的Kociemba解魔方算法得出魔方還原步驟能逼近“上帝之?dāng)?shù)”（God′s number）——20，即魔方最少需要多少次的轉(zhuǎn)動，才能確保無論什么樣的顏色組合都能被復(fù)原。從而不斷提高機器臂控制的精度、速度和可靠性[4]。

目前比較成熟的魔方機器人多為六軸中心式（如德國的Sub1Reloaded）以及底面翻滾式（如LEGO的EV3），然而前者需要對標(biāo)準三階魔方的中心塊進行改造，后者由于機械結(jié)構(gòu)設(shè)計上的不穩(wěn)定因素解算成功率并不高。基于Kociemba算法的雙臂解魔方機器人，更為貼合人類標(biāo)準三階魔方時的手部動作與結(jié)算策略，采用手指夾持的方式無需對標(biāo)準三階魔方的中心塊進行改造，在正常運行情況下，在極具觀賞性的同時，保證還原速度。機器人想要快速尋找到最優(yōu)的還原步驟需要進行復(fù)雜的計算與推理，建立還原步驟簡化規(guī)律，避免多余、重復(fù)的還原步驟；同時精準地還原，需要準確而快速的顏色識別、快速而穩(wěn)定的轉(zhuǎn)動操作和高效可靠的通訊模塊。

1 基于Kociemba算法的雙臂魔方機器人

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

本文針對圖1所示的雙臂魔方機器人展開研究。如圖2所示，在夾具上，采用薄型平行開閉型氣動手爪，將兩個氣動手爪嚴格處于統(tǒng)一平面且保持相互之間成90°，采用碳纖維高壓氣瓶作為本雙臂解魔方機器人的高壓空氣源。同時，由于顯著改善速度提高后力矩會導(dǎo)致缺失和開環(huán)步進電機丟失步數(shù)的問題控制脈沖頻率，將脈沖電信號轉(zhuǎn)換為角位移，選擇STM32 MCU與兩相混合式步進電機。利用Altium Designer電路設(shè)計軟件，繪制出所使用的控制主板的原理圖與PCB板布線樣圖。

圖1 雙臂魔方機器人整體結(jié)構(gòu)

圖2 雙臂魔方機器人手臂結(jié)構(gòu)

1.2 機械臂運動模式

用戶可通過解魔方機器人操作界面來手動控制該解魔方機器人手臂的動作。通過按鈕“L順”（左側(cè)電機順時針旋轉(zhuǎn)）、“L逆”（左側(cè)電機逆時針旋轉(zhuǎn)）、“D順”（右側(cè)電機順時針旋轉(zhuǎn)）和“D逆”（右側(cè)電機逆時針旋轉(zhuǎn)）來進行電機旋轉(zhuǎn)角度的微調(diào)，以及控制兩個氣缸夾爪的松開和夾緊[5]。

用戶也可在該操作界面串口通信區(qū)的下方信息發(fā)送區(qū)寫上指令，點擊發(fā)送即可控制機器人。指令列表如圖3所示。

圖3 機器人控制指令列表

1.3 硬件調(diào)試與整機運行測試

通過上電運行測試后，還原標(biāo)準三階魔方的平均時間依據(jù)魔方打亂程度的不同為12～17 s。檢驗電機運動控制算法，使得電機能夠保持足夠力矩，快速達到高速，快速精準地止動，并且能使運動過程平滑，不產(chǎn)生大量突變，以減少運動慣性帶來的魔方層與層之間的錯位，使得機械臂能夠進行短促平滑地高速轉(zhuǎn)動。可以得出結(jié)論，該結(jié)構(gòu)嚴格符合雙臂魔方機器人的運動條件和運動方式，同時解決了顯著改善速度提高后力矩會導(dǎo)致缺失和開環(huán)步進電機丟失步數(shù)的問題。

2 基于Kociemba算法的雙臂解魔方機器人算法分析

2.1 Koeicmba算法

Kociemba算法的輸出形式如下：首先，將魔方的6個面分別定義為U面、D面、L面、R面、F面和B面，分別對應(yīng)上面（Up）、下面（Down）、左面（Left）、右面（Right）、前面（Front）和后面（Back）。U代表順時針旋轉(zhuǎn)上面90°，U2代表順時針（或逆時針）旋轉(zhuǎn)上面180°，U′代表逆時針旋轉(zhuǎn)上面90°，其余5面同理。一段像“U D R′D2”這樣的表示魔方旋轉(zhuǎn)的序列，稱之為一個策略（maneuver）。Kociemba算法將對魔方顏色信息的輸入進行計算，然后計算輸出一個還原策略。

需要注意，Kociemba算法的運算量較大，因此計算解法通常需要花費較長時間。為了提高解魔方機器人的效率，一般會在算法運算一定時間后得到較優(yōu)解后就停止運算[6-8]。另外，為了統(tǒng)一表示解法，本文將順時針旋轉(zhuǎn)90°的操作用“+”表示，逆時針旋轉(zhuǎn)90°的操作用“-”表示，旋轉(zhuǎn)180°的操作用“2”表示，如有一段來自于Kociemba算法輸出的策略“UDR′D2”，在本文，將會被表示為“U+D+R-D2”。

2.2 Kociemba算法的轉(zhuǎn)換算法

由于本設(shè)計是基于雙臂解魔方機器人的算法，所以需要進一步將六面旋轉(zhuǎn)信息轉(zhuǎn)換成兩面旋轉(zhuǎn)信息的算法稱為“6-2轉(zhuǎn)換算法”。該轉(zhuǎn)換能將所有的操作轉(zhuǎn)變?yōu)殡p臂電機的旋轉(zhuǎn)操作和氣動夾具的夾持和松開動作。本文所研究設(shè)計的雙臂解魔方機器人的雙臂分別對應(yīng)了魔方的左面和下面，即L面和D面。因此，轉(zhuǎn)換算法的輸出將只包含了L面和D面的操作，不能包含其他面的操作。如圖4所示。

圖4 適用于雙臂解魔方機器人的Kociemba算法的轉(zhuǎn)換算法

2.3 坐標(biāo)轉(zhuǎn)換算法——A算法與A步驟

假設(shè)原坐標(biāo)系順序是Coord[6]={U,D,L,R,F,B}，在進行了AL+操作后，即解魔方機器人夾持魔方L面整體順時針旋轉(zhuǎn)90°，將會變成AL+（Coord[6]）={B,F,L,R,U,D}，觀察可以發(fā)現(xiàn)，原坐標(biāo)系的U面變?yōu)锽面，B面變?yōu)镈面，D面變?yōu)镕面，F(xiàn)面變?yōu)閁面，這個轉(zhuǎn)換的過程在本文稱為“坐標(biāo)系轉(zhuǎn)換算法”。

圖5 所示為轉(zhuǎn)換算法表。Ux、Dx、Lx、Rx、Fx和Bx分別代表了所截取的已完成坐標(biāo)系轉(zhuǎn)換的兩步驟中的第一步，而Uy、Dy、Ly、Ry、Fy和By分別代表了第二步。以“A”字符開頭的操作代表著魔方的整體旋轉(zhuǎn)，而不是面旋轉(zhuǎn)，“”字符意味著該操作是空。需要注意的是，表格中“->（??）”表達式意味需要額外往后多截取一個操作，這種特殊情況通常出現(xiàn)在需要旋轉(zhuǎn)的面恰好已經(jīng)被雙臂所夾持，被夾持的一面不需要做額外的坐標(biāo)轉(zhuǎn)換，因此需要再多往后讀取一個步驟?？梢园l(fā)現(xiàn)，圖中，同一對操作有多種轉(zhuǎn)換方法，例如“Ux Fy”，可以被轉(zhuǎn)換成“AL2AD+DxLy”、“AL+AD-LxDy”和“AD-AL2DxLy”中的一種，通常為了盡可能簡化步驟，如果上一對操作轉(zhuǎn)換后的最后一個操作是L面旋轉(zhuǎn)（或D面旋轉(zhuǎn)）的，那么，下一對操作在轉(zhuǎn)換時優(yōu)先選擇AL旋轉(zhuǎn)（或者DL旋轉(zhuǎn)）的。

圖5 Kociemba算法轉(zhuǎn)換算法表

為了進一步說明圖5的操作，下面將給出示例：假設(shè)截取到的原算法的輸出策略為“U+L-”，那么第一個步驟可表示為“Ux”，其中的“x”等于“+”，第二個步驟可表示為“Ly”，其中的“y”等于“-”。通過查表可得，在進行了轉(zhuǎn)換后，原策略將變?yōu)椤癆L2DxLy”，代入x和y的值，即為“AL2D+L-”，這表示了“L側(cè)手臂先夾住整個魔方整體旋轉(zhuǎn)180°，然后再順時針旋轉(zhuǎn)魔方的當(dāng)前坐標(biāo)系的D面90°，最后再逆時針旋轉(zhuǎn)魔方的當(dāng)前坐標(biāo)系的L面90°”。旋轉(zhuǎn)過程如圖6所示。

圖6 “AL2D+L-”旋轉(zhuǎn)過程（從左往右）

A步驟：在將Kociemba算法的原始輸出策了統(tǒng)略通過A算法的轉(zhuǎn)換后，其輸出將只包含以下幾個操作，分別為：L+、L2、L-、D+、D2、D-、AL+、AL2、AL-、AD+、AD2和AD-。不是A開頭的操作和原Kociemba算法輸出策略的含義一致，代表了旋轉(zhuǎn)某一面某個角度的操作。

2.4 轉(zhuǎn)換為機械臂動作——M-C算法與M-C步驟

C算法：M-C算法所做的事情是將A步驟，即L+、L2、L-、D+、D2、D-、AL+、AL2、AL-、AD+、AD2和AD-這些代表魔方本身被旋轉(zhuǎn)的動作步驟轉(zhuǎn)換為電機和夾爪的動作，這些動作分別為：LM+、LM2、LM-、DM+、DM2、DM-、LC+、LC-、DC+和DC-。

帶“M”字符的操作表示了電機動作，例如“LM+”，其意義為“L側(cè)電機順時針旋轉(zhuǎn)90°”。而帶“C”字符的操作表示了夾爪動作，例如“LC+”，其意義為“L側(cè)夾爪夾緊”；而“LC-”，表示“L側(cè)夾爪松開”。在一串的M-C步驟中，若X代表了D側(cè)，則Y將代表L側(cè)，反之亦然。為了盡可能簡化步驟，如果上一對操作轉(zhuǎn)換后的最后一個操作是L面旋轉(zhuǎn)（或D面旋轉(zhuǎn)）的，那么下一對操作在轉(zhuǎn)換時優(yōu)先選擇AL旋轉(zhuǎn)（或者DL旋轉(zhuǎn)）。如圖7所示。圖中，表達式中的“X”和“Y”的含義和轉(zhuǎn)化為機械臂動作——M-C算法和M-C步驟中的含義一致，“1”代表A步驟中的“+”或“-”操作，“…”僅表示A步驟中未被截取的地方，“!”表示A步驟中此處不允許出現(xiàn)的操作。如SP3“…AX2 Y1!AY1…”中的“Y1!AY1”表示A步驟中“Y1”后面不能是“AY1”，否則構(gòu)不成SP3特殊情況。又如SP4“…!X1 AX1 Y1!AY1…”中的“!X1 AX1”表示A步驟中“AX1”前面不能是“X1”，否則構(gòu)不成SP4特殊情況。在圖中，對于每一種特殊情況，枚舉出了其輸入、原始輸出（直接查圖7的輸出結(jié)果）和簡化后的輸出。最終再將整張表的輸入、輸出進行抽象，得到了圖中右側(cè)三列的表達式，即輸入表達式、輸出表達式以及備注。為了方便討論，在這張表中，用“i”和“j”字符來代替輸入表達式中的旋轉(zhuǎn)動作，即“+”、“-”或“2”。相反地，用“I”和“J”字符來代替輸入表達式中與之相反的旋轉(zhuǎn)動作，即若“i”表示“+”，則“I”表示“-”。

圖7 Kociemba算法轉(zhuǎn)換算法M-C步簡化表

3 結(jié)束語

本文將使用C++接口的OpenCV庫來獲取攝像頭獲取的圖像信息，并對圖像進行處理，提煉出所需的魔方顏色信息。處理圖像時所需要使用到的算法為高斯濾波算法、白平衡算法、RGB和HSV轉(zhuǎn)換等。

經(jīng)過運算后，目前機器人能在20 s內(nèi)解開一個被任意打亂的魔方，定時運行1 s后的Kociemba算法的平均步數(shù)大約為21步，Kociemba算法的轉(zhuǎn)換算法效果令人滿意，轉(zhuǎn)換后的指令步數(shù)大約在85步左右，實現(xiàn)了設(shè)計目標(biāo)。