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

鄭雨辰　王婷

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

關(guān)鍵詞：魔方；機(jī)器人；二階段雙向搜索

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

1 解魔方求解算法

1.1 求解搜索方法

本程序算法的本質(zhì)是窮舉法。

第1輪，設(shè)定公式步數(shù)為1，有6^1=6種公式，對(duì)給定的打亂狀態(tài)分別應(yīng)用這6個(gè)公式，可得6種新狀態(tài)，若這6種狀態(tài)中出現(xiàn)復(fù)原態(tài)，則輸出相應(yīng)公式并結(jié)束程序。否則進(jìn)入第2輪，公式步數(shù)為2，有6^2=36種公式，搜索是否存在復(fù)原態(tài)。以此類推，直至窮舉出復(fù)原態(tài)。

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

1.2 二階段搜索

定義三組狀態(tài)集合G0、G1、G：

集合G0中僅有一個(gè)元素，即魔方的復(fù)原狀態(tài)。

A={U，D，L，R，F(xiàn)，B}，如果魔方從復(fù)原態(tài)開始轉(zhuǎn)動(dòng)，每一步操作僅來自集合A，當(dāng)轉(zhuǎn)動(dòng)足夠多的步數(shù)后，所有得到的魔方狀態(tài)構(gòu)成了集合G。顯然，G是全集。

A1={U，D，LL，RR，F(xiàn)F，BB}，如果魔方從復(fù)原態(tài)開始轉(zhuǎn)動(dòng)，每一步操作僅來自集合A1，即對(duì)魔方的轉(zhuǎn)動(dòng)進(jìn)行限制，左、右、前、后四個(gè)面每次只能轉(zhuǎn)動(dòng)180°，當(dāng)轉(zhuǎn)動(dòng)足夠多的步數(shù)后，所有得到的狀態(tài)都屬于集合G1。

三個(gè)狀態(tài)集合的從屬關(guān)系為：G0？哿G1？哿G。

打亂狀態(tài)的魔方屬于集合G，復(fù)原態(tài)的魔方屬于G0。在上文介紹的窮舉法中，由于沒有對(duì)魔方的轉(zhuǎn)動(dòng)操作進(jìn)行限制，不存在G1，直接從G向著G0搜索。記為“G-G0”。

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

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

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

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

由于集合G1中的元素不止一個(gè)，所以在第一階段中，只要搜索到任意一個(gè)中間狀態(tài)即可。又由于產(chǎn)生集合G1的過程對(duì)轉(zhuǎn)動(dòng)操作進(jìn)行了限制，所以G1中元素的個(gè)數(shù)遠(yuǎn)小于G中元素的個(gè)數(shù)。二階段搜索法對(duì)減小計(jì)算量有很明顯的效果。但這在效率上仍達(dá)不到要求。為此，本文提出了雙向搜索法。

1.3 雙向搜索

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

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

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

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

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

實(shí)踐證明，這種算法大幅度減小了數(shù)據(jù)量，使計(jì)算機(jī)程序求解魔方更快捷。

2 解魔方機(jī)器人控制系統(tǒng)設(shè)計(jì)

步進(jìn)電機(jī)是一種將脈沖信號(hào)轉(zhuǎn)換為步距角的電動(dòng)機(jī)。例如：默認(rèn)狀態(tài)下，經(jīng)過一個(gè)脈沖周期，步進(jìn)電機(jī)的主軸旋轉(zhuǎn)1.8°。這種電動(dòng)機(jī)可以較為精確地控制旋轉(zhuǎn)角度，適合本項(xiàng)目。

本項(xiàng)目采用Arduino單片機(jī)作為信號(hào)源控制步進(jìn)電機(jī)，其數(shù)字I/O端口可輸出0V/5V兩種電壓，搭配延時(shí)函數(shù)，可產(chǎn)生脈沖信號(hào)。Arduino程序在接收到復(fù)原公式后，逐個(gè)解析公式中的字母，向?qū)?yīng)的電機(jī)發(fā)送信號(hào)，即可按照預(yù)期的動(dòng)作順序控制六臺(tái)電機(jī)。

3 機(jī)器人框架設(shè)計(jì)與實(shí)驗(yàn)調(diào)試

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

框架采用歐標(biāo)4040號(hào)鋁合金；固定板為鋁合金板；傳動(dòng)桿采為亞克力板。最終構(gòu)建出解魔方機(jī)器人平臺(tái)。

參考文獻(xiàn)：

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

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

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

作者簡(jiǎn)介：

鄭雨辰（1996-），男，漢族，江蘇常州人，蘇州大學(xué)應(yīng)用技術(shù)學(xué)院2014級(jí)機(jī)械電子工程，研究方向：機(jī)電一體化。