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