李澤萱 滕旭陽(yáng) 鄭藝彬 唐日成 徐歡瀟

摘要：該設(shè)計(jì)以層先法作為基礎(chǔ)算法，將魔方以面、顏色、位置（二維數(shù)組）三個(gè)基本屬性進(jìn)行存儲(chǔ)，通過調(diào)用設(shè)計(jì)的六個(gè)基本動(dòng)作進(jìn)行“底部十字”“底角還原”“中棱還原”“頂面十字”“頂角面位”“頂角還原”“頂棱還原”七個(gè)還原步驟，輸出得到還原序列。最后該設(shè)計(jì)優(yōu)化了操作面的問題，調(diào)用了設(shè)計(jì)的四套基本動(dòng)作，最終完成魔方的還原。

關(guān)鍵詞：算法設(shè)計(jì)；單片機(jī)算法；解魔方算法；機(jī)器人算法

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2018）17-0248-03

Abstract： This design takes the first method as the basic algorithm， and stores the magic cube with three basic attributes of surface， color and position（two-dimensional array）.By calling the six basic movements of the design， the seven restoration steps of” bottom cross” ”bottom angle restoration” ”middle prism restoration” ”top cross” ”top angle surface”” top angle restoration” are carried out. Finally， this design optimizes the operation surface problem， calls the four basic actions of the design， and finally completes the restoration of the Rubiks cube.

Key words： algorithm design； single chip algorithm； magic square algorithm； robot algorithm

在市場(chǎng)和政策的雙重利好下，國(guó)內(nèi)機(jī)器人市場(chǎng)迅速升溫，機(jī)器人產(chǎn)業(yè)可謂迅猛發(fā)展。如今由一開始的多達(dá)95%的工業(yè)應(yīng)用擴(kuò)展到更多的非工業(yè)應(yīng)用。例如做手術(shù)，采摘水果，巷道掘進(jìn)，偵察，排雷，還有空間機(jī)器人等等，只要是能想到的，就可以去創(chuàng)造去實(shí)現(xiàn)。

機(jī)器人技術(shù)的發(fā)展，它應(yīng)該說是一個(gè)科學(xué)技術(shù)發(fā)展共同的一個(gè)綜合性的結(jié)果，也同時(shí)，為社會(huì)經(jīng)濟(jì)發(fā)展產(chǎn)生了一個(gè)重大影響的一門科學(xué)技術(shù)，它的發(fā)展歸功于在第二次世界大戰(zhàn)中，各國(guó)加強(qiáng)了經(jīng)濟(jì)的投入，就加強(qiáng)了本國(guó)的經(jīng)濟(jì)的發(fā)展。同時(shí)，科技的發(fā)展也是人類發(fā)展的一個(gè)必然結(jié)果，機(jī)器人技術(shù)當(dāng)然也就是科技發(fā)展的一項(xiàng)產(chǎn)物。另一方面，這些也是人類生產(chǎn)力需求下的必然結(jié)果，隨著社會(huì)的發(fā)展，對(duì)這個(gè)世界，對(duì)自然的更多的認(rèn)識(shí)，在人力不可達(dá)到不可完成的對(duì)自然改造的情況下，科技發(fā)展，機(jī)器人技術(shù)的發(fā)展就成為人類的一個(gè)客觀需要。該設(shè)計(jì)將完成既可以用于教育行業(yè)作為典型的機(jī)器人教學(xué)教具，也可用于娛樂業(yè)作為展示用和表演用的機(jī)器人，還能產(chǎn)生一定經(jīng)濟(jì)效益。該解魔方機(jī)器人運(yùn)用顏色識(shí)別和數(shù)字舵機(jī)精確控制等科學(xué)技術(shù)。對(duì)于解魔方機(jī)器人，控制系統(tǒng)就如同人的神經(jīng)中樞，它起著承接算法與機(jī)械結(jié)構(gòu)的作用。該文將從算法設(shè)計(jì)部分進(jìn)行論述。

1 前期設(shè)計(jì)分析

首先，該設(shè)計(jì)需要三個(gè)主要部分。第一：魔方信息的采集；第二：魔方還原序列的計(jì)算；第三：對(duì)舵機(jī)的調(diào)用。對(duì)于第一部分，使用攝像頭采集到魔方的二進(jìn)制顏色信息并將其轉(zhuǎn)換成詳細(xì)的RGB顏色信息，從而得到魔方的初始顏色狀態(tài)。第二部分，設(shè)計(jì)采用層先法計(jì)算輸出魔方的還原序列。第三部分來說，我們需要更換每一步完成后的操作面以更優(yōu)的方法步驟來實(shí)現(xiàn)對(duì)魔方的操作，最終調(diào)用四路舵機(jī)完成對(duì)魔方的還原。

2 層先法的描述以及選用層先法的原因

在還原魔方的算法方面我們選擇了層先法，與競(jìng)速還原法CFOP相比，CFOP有較少的還原步驟，但需要大量的函數(shù)，不便于編程，從可行性方面，最終選用層先法。

層先法，就是指將魔方分為三層：底層、中層、頂層分層復(fù)原。用層先法復(fù)原魔方一共分七步，分別為：做好底層十字、調(diào)整底面角塊、復(fù)原中層棱塊、做好頂面十字、頂角歸位、調(diào)整頂角位置、調(diào)整頂棱位置。做好這七步，魔方就可以成功復(fù)原了。

2.1 魔方特性

魔方共有6個(gè)中心方塊，它們顏色固定并且不會(huì)隨著旋轉(zhuǎn)而改變，同時(shí)擁有12個(gè)棱塊和8個(gè)角塊。魔方的展開圖如圖1：

在調(diào)用層先法算法時(shí)，遍歷所有方塊，然后調(diào)用以上函數(shù)，即可實(shí)現(xiàn)魔方的還原。

3 案例參考與對(duì)比

3.1 與四機(jī)械臂相比

我們?cè)谒臋C(jī)械臂的基礎(chǔ)上減去了兩個(gè)機(jī)械臂，讓還原魔方過程減少對(duì)于機(jī)械臂的要求，讓還原魔方這一過程在更為簡(jiǎn)易的環(huán)境下運(yùn)行。

3.2 調(diào)用舵機(jī)的代碼

3.2.1 轉(zhuǎn)換至操作面的代碼優(yōu)化

由于與四機(jī)械臂相比減少了兩個(gè)操作面，所以我們對(duì)于將目標(biāo)面旋轉(zhuǎn)至操作面的代碼進(jìn)行了優(yōu)化。我們對(duì)于除了兩個(gè)操作面以外的其余四個(gè)面都定義了將本面移動(dòng)至操作面的函數(shù)，在需要時(shí)調(diào)用該函數(shù)以達(dá)到將目標(biāo)面旋轉(zhuǎn)至操作面的目的。

3.2.2 對(duì)機(jī)械臂的動(dòng)作優(yōu)化

由于原本的算法給出的步驟是基于原始操作面進(jìn)行移動(dòng)旋轉(zhuǎn)，這就要求機(jī)械臂在每一次完成旋轉(zhuǎn)目標(biāo)面之后都要還原到原始面再進(jìn)行下一步操作，這種不必要的動(dòng)作大大加長(zhǎng)了魔方的還原時(shí)間。所以我們對(duì)于機(jī)械臂的動(dòng)作做了一定程度上的優(yōu)化，我們?cè)诿恳淮螜C(jī)械臂進(jìn)行當(dāng)前的操作之前計(jì)算在機(jī)械臂完成當(dāng)前操作之后下一個(gè)目標(biāo)面的位置以及所需旋轉(zhuǎn)的方向，并進(jìn)行修改替換機(jī)械臂的下一步操作。

4 攝像機(jī)-算法-舵機(jī)之間的連接

我們把還原魔方的過程粗略分為三個(gè)部分：

（1）通過攝像機(jī)獲取魔方的初始狀態(tài)數(shù)據(jù)；

（2）通過算法對(duì)魔方的初始狀態(tài)數(shù)據(jù)進(jìn)行處理獲得解魔方的相應(yīng)步驟；

（3）將解魔方步驟轉(zhuǎn)化成相應(yīng)的代碼操縱機(jī)械臂進(jìn)行活動(dòng)。

我們首先將三個(gè)步驟分開作為三個(gè)獨(dú)立的項(xiàng)目進(jìn)行，在三個(gè)項(xiàng)目都完成的情況下如何將三個(gè)項(xiàng)目串聯(lián)形成一個(gè)完整的解魔方機(jī)器人就成為一個(gè)新的問題。

對(duì)于（1）—>（2）的連接首先我們通過攝像機(jī)獲取對(duì)應(yīng)面的二進(jìn)制數(shù)組的數(shù)據(jù)，通過圖像解碼將對(duì)應(yīng)區(qū)域的二進(jìn)制碼求取并均值獲得魔方一面上相對(duì)應(yīng)的小方塊的RGB顏色數(shù)據(jù)，最后將每一面的數(shù)據(jù)集中存放在一個(gè)二維數(shù)組當(dāng)中。當(dāng)算法開始計(jì)算并需要獲得魔方的初始顏色狀態(tài)時(shí)調(diào)用上述相機(jī)操作存儲(chǔ)的二維數(shù)組進(jìn)行計(jì)算。

對(duì)于（2）—>（3）的連接中我們將算法中輸出的一連串的步驟放入一個(gè)二維數(shù)組當(dāng)中，并在操作舵機(jī)的程序中將動(dòng)作步驟部分的代碼修改成為調(diào)用上述二維數(shù)組的內(nèi)容進(jìn)行還原魔方的動(dòng)作，以完成算法與操作舵機(jī)程序的連接，來達(dá)到從代碼到機(jī)械臂活動(dòng)的目的。

5 總結(jié)

該文主要闡述了此次針對(duì)解三階魔方的機(jī)器人的算法研究。從前期的需求分析進(jìn)行算法的基該設(shè)計(jì)到最終選取采用了層先法為基礎(chǔ)方法，然后根據(jù)機(jī)械臂轉(zhuǎn)動(dòng)的需求對(duì)算法進(jìn)行了步驟優(yōu)化，從算法的詳細(xì)編輯再到算法的細(xì)節(jié)優(yōu)化，最終實(shí)現(xiàn)將本算法應(yīng)用于解魔方機(jī)器人。

參考文獻(xiàn)：

[1] Arduino案例實(shí)戰(zhàn)（卷Ⅰ）/清華開發(fā)者書庫(kù)[M]. 北京： 清華大學(xué)出版社， 2017： 42.

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