基于二階段雙向搜索的解魔方機器人研究

鄭雨辰　王婷

摘 要：設計了能自動復原三階魔方的解魔方機器人。提出了“二階段雙向搜索法”，對機器人的研究主要包括以下幾個方面：計算機程序求解魔方、單片機程序控制步進電機、攝像頭掃描魔方并識別顏色、設計制造金屬實物框架和機械手。本文重點討論了計算機程序求解魔方的思路，即利用大幅度縮短求解時間。該機器人與現有的魔方機器人相比，有機械結構簡單、效率高、造價低等優點。

關鍵詞：魔方；機器人；二階段雙向搜索

自1972年魯比克教授發明魔方以來，人們探索魔方解法的腳步從未停止。目前國內外魔方愛好者已經研究出一系列的魔方求解算法。本設計在前人的基礎上，衍生創新出一種新的求解算法，旨在為求解魔方提供新的突破點，其結構主要包括以下四個模塊：①求解魔方的計算機程序；②攝像頭識別魔方顏色的計算機程序；③機器人的框架結構及機械手的傳動結構；④控制步進電機的單片機程序。

1 解魔方求解算法

1.1 求解搜索方法

本程序算法的本質是窮舉法。

第1輪，設定公式步數為1，有6^1=6種公式，對給定的打亂狀態分別應用這6個公式，可得6種新狀態，若這6種狀態中出現復原態，則輸出相應公式并結束程序。否則進入第2輪，公式步數為2，有6^2=36種公式，搜索是否存在復原態。以此類推，直至窮舉出復原態。

這種解法理論上可以解出任意打亂的魔方。但以常見的計算機性能來看，不論是計算時間，還是所需的存儲空間，都十分龐大。所以本文提出了“二階段搜索”這個概念。

1.2 二階段搜索

定義三組狀態集合G0、G1、G：

集合G0中僅有一個元素，即魔方的復原狀態。

A={U，D，L，R，F，B}，如果魔方從復原態開始轉動，每一步操作僅來自集合A，當轉動足夠多的步數后，所有得到的魔方狀態構成了集合G。顯然，G是全集。

A1={U，D，LL，RR，FF，BB}，如果魔方從復原態開始轉動，每一步操作僅來自集合A1，即對魔方的轉動進行限制，左、右、前、后四個面每次只能轉動180°，當轉動足夠多的步數后，所有得到的狀態都屬于集合G1。

三個狀態集合的從屬關系為：G0？哿G1？哿G。

打亂狀態的魔方屬于集合G，復原態的魔方屬于G0。在上文介紹的窮舉法中，由于沒有對魔方的轉動操作進行限制，不存在G1，直接從G向著G0搜索。記為“G-G0”。

在“二階段搜索”算法中，“G-G0”的過程被分為了兩個階段：“G-G1”和“G1-G0”，記為“G-G1-G0”。G1中的每個狀態稱為“中間狀態”。

第一階段G-G1：從打亂狀態開始搜索，類似上文提到的窮舉法。但是，這里不再是判斷新狀態是否是G0，而是判斷新狀態是否屬于G1，若發現新狀態屬于G1，則第一階段完成。此時可得到兩條信息：一個屬于G1的中間狀態{a1}，以及一個從打亂狀態{a}到中間狀態{a1}的復原公式。

第二階段G1-G0：類似第一階段。將{a1}作為打亂狀態，在搜索的過程中判斷新狀態是否屬于G0。該搜索完成后，可得到一個從狀態{a1}到復原態的公式。

兩階段都完成后，將兩階段中各自得到的公式合并，得到從打亂狀態{a}到復原態的公式。

由于集合G1中的元素不止一個，所以在第一階段中，只要搜索到任意一個中間狀態即可。又由于產生集合G1的過程對轉動操作進行了限制，所以G1中元素的個數遠小于G中元素的個數。二階段搜索法對減小計算量有很明顯的效果。但這在效率上仍達不到要求。為此，本文提出了雙向搜索法。

1.3 雙向搜索

假設G-G1階段最多需要搜索2n（n=1，2，3……）步即可完成，我們可以先從打亂狀態{a}開始搜索n輪，即，從步數為1的公式開始搜索，直到步數為n的公式全部搜索完畢，若此時還未搜索到第一階段的復原公式，則暫停搜索，并將這n輪搜索過程中產生的所有魔方狀態都記為集合Ga。并保存每種狀態所對應的復原公式。同理，本文將G1中的狀態{a1}開始搜索n步，將這n步搜索過程中產生的所有魔方狀態都記為集合Ga1。

對集合Ga和集合Ga1取交集，再從交集中任取出一個元素，記為{at}。

通過查表得到由狀態{a}到{at}的公式，和狀態{a1}到{at}的公式。將{a1}到{at}的公式逆推，可得{at}到{a1}的公式。

將{a}到{at}的公式和{at}到{a1}的公式拼接，得到第一階段的復原公式。

以上是第一階段的雙向搜索法，第二階段類似，不再贅述。

實踐證明，這種算法大幅度減小了數據量，使計算機程序求解魔方更快捷。

2 解魔方機器人控制系統設計

步進電機是一種將脈沖信號轉換為步距角的電動機。例如：默認狀態下，經過一個脈沖周期，步進電機的主軸旋轉1.8°。這種電動機可以較為精確地控制旋轉角度，適合本項目。

本項目采用Arduino單片機作為信號源控制步進電機，其數字I/O端口可輸出0V/5V兩種電壓，搭配延時函數，可產生脈沖信號。Arduino程序在接收到復原公式后，逐個解析公式中的字母，向對應的電機發送信號，即可按照預期的動作順序控制六臺電機。

3 機器人框架設計與實驗調試

整機結構并不復雜。框架由若干豎直、水平的鋁合金桿構成，直角處用螺栓連接，方便拆卸。魔方使用空心結構，簡化了傳動過程。避免了機械卡爪帶來的控制部件繁多、結構復雜等缺點。

框架采用歐標4040號鋁合金；固定板為鋁合金板；傳動桿采為亞克力板。最終構建出解魔方機器人平臺。

參考文獻：

[1] （美）Michael Margolis著，楊昆云譯.Arduino權威指南.2版.北京：人民郵電出版社，2015.

[2] 毛星云，冷雪飛著. OpenCV3編程入門.北京：電子工業出版社，2015.

[3] 濮良貴，紀名剛著.機械設計.9版.北京：高等教育出版社，2013.

作者簡介：

鄭雨辰（1996-），男，漢族，江蘇常州人，蘇州大學應用技術學院2014級機械電子工程，研究方向：機電一體化。