速解魔方機器人(中)

接上篇
4.3 系統(tǒng)軟件設(shè)計
4.3.1   魔方還原算法流程
     本算法是一個可以給出將魔方任何可能的混亂狀態(tài)還 原回六面同色狀態(tài)的算法。目前常用的CFOP法是一種4階段 算法，一共分有4個還原階段，平均步數(shù)在50-70步。而任意 狀態(tài)的魔方的還原方法已經(jīng)被證明可以在20步之內(nèi)，可見這 種方法有很大的冗余，還有提升空間。本算法能在短時間里 提供出一組平均步數(shù)在 25步左右的解決方案。
魔方有6個面，每個面存在3種操作(正對該面，順時針 旋轉(zhuǎn)，逆時針旋轉(zhuǎn)，180度旋轉(zhuǎn))，一共18種操作。首先介紹 一下各個旋轉(zhuǎn)操作的簡稱：

前面順時針旋轉(zhuǎn)為【 F 】逆時針旋轉(zhuǎn)為【 F’ 】，180 度旋轉(zhuǎn)為【F2】。后面相應為【B】【B’】【B2】。接下 來介紹算法中的編碼。算法有兩個階段，每個階段有不同的 編碼方式，如下表，第一階段：

通過攝像頭或者手動輸入采集魔方狀態(tài)之后，我們需 要用一種方式保存初始魔方狀態(tài)。魔方有8個角塊，12個棱 塊，魔方的擺放為：U藍色，F(xiàn)紅色，R黃色，L白色，B橙 色，D綠色。首先對它們分類進行編碼，角塊：

然后，對于每一個角塊，還需要一個參數(shù)來確定：順 時針扭轉(zhuǎn)次數(shù)。如圖14（166頁），藍橙黃5號角塊處在正確的位置， 但是處在不同的扭轉(zhuǎn)狀態(tài)，第一個是順時針扭轉(zhuǎn)0次，第二 個是順時針扭轉(zhuǎn)1次，第三個是順時針扭轉(zhuǎn)2次(在后文中也 稱作逆時針扭轉(zhuǎn)1次)。
而對于棱塊，只有兩種可能，翻轉(zhuǎn)或者正常。如藍紅11號棱塊，第一個是 正 常 0 ， 第 二 個 是 翻 轉(zhuǎn) 1 。 扭 轉(zhuǎn) 、 翻 轉(zhuǎn) 是 一個局部相對
于整體 的操作。在圖14中， 藍色是參考色，扭轉(zhuǎn) 是角塊與棱塊中藍色 的位置，相對于頂面 中心藍色來說的。不 同的參考會導致不同 的結(jié)果，如果以黃色 為參考色，那么角塊 中 ， 分 別 扭 轉(zhuǎn) 1 ， 2，0。
如圖15，被噴涂 的顏色為參考色，當

圖16　魔方還原算法流程圖

圖17　控制端算法流程圖
處在頂面和底面時，藍色和綠色是同等參考色。當處在UD 夾層中的時候，優(yōu)先參考藍色和綠色，當棱塊是紅黃等非 藍、綠色的時候，則參考紅色和橙色相對于中心紅色和橙色 的翻轉(zhuǎn)狀態(tài)。這樣，定義一個魔方的數(shù)組int MF[3][3][3][2][b][c];([n行][n列][n層][編號或扭轉(zhuǎn)數(shù)][第b步][第c次循環(huán)])就可以保 存下初始魔方的狀態(tài)。

圖18　QSYS系統(tǒng)設(shè)計
對于一個未打亂的魔方，如果你使用除 R，R’，L，L’，F(xiàn)，F(xiàn)’，B 和 B’以外的轉(zhuǎn)法來轉(zhuǎn)動它，你能生成的 狀態(tài)僅是魔方所有可能狀態(tài)群中的一個子群。這個子群表示 為 G1群。而本二階段搜索算法的思想，就是基于這個G1群，在 第一階段中，我們用所有的18種可能的操
作去作用初始狀 態(tài)，當所有塊的翻轉(zhuǎn)、扭轉(zhuǎn)為0，且中間棱塊都在中間的時 候，則到達G1群狀態(tài)，第一階段完成。第二階段，我們用 群的10種可能操作去作用此時狀態(tài)，直到所有塊的位置都正 確。則魔方還原。具體流程如下圖16所示。
4.3.2 控制端算法流程
具體流程圖如下圖17所示。
HPS端控制開始顏色識別，將控制信號發(fā)送給舵機轉(zhuǎn)動模塊，舵機轉(zhuǎn)動模塊控制機械手臂轉(zhuǎn)動魔方達到指定位置， 轉(zhuǎn)動結(jié)束后，舵機模塊向顏色識別模塊發(fā)送轉(zhuǎn)動結(jié)束信號， 顏色識別模塊開始識別9個色塊的顏色，識別結(jié)束后，將識 別到的顏色以及結(jié)束信號發(fā)送到HPS控制端。
如此循環(huán)6次，獲取到54個色塊的顏色，HPS控制端對
54個顏色進行整合，是否符合各個顏色的面數(shù)，如果符合，
則進行求解魔方，如果不符合，則進行重新識別。
5  設(shè)計方法
5.1 Qsys系統(tǒng)設(shè)計
5.2 CCD攝像頭使用原理
CCD攝像頭是指使用CCD傳感器的攝像頭。CCD圖像 傳感器可直接將光學信號轉(zhuǎn)換為模擬電流信號，電流信號經(jīng) 過放大和模數(shù)轉(zhuǎn)換,實現(xiàn)圖像的獲取、存儲、傳輸、處理和復 現(xiàn)。其顯著特點是：1.體積小、重量輕；2.功耗小，工作電 壓低，抗沖擊與震動，性能穩(wěn)定，壽命長；3.靈敏度高，噪聲低，動態(tài)范圍大；4.響應速度快，有自掃描功能，圖像畸 變小，無殘像；5.應用超大規(guī)模集成電路工藝技術(shù)生產(chǎn)，像 素集成度高，尺寸精確，商品化生產(chǎn)成本低。因此，許多采 用光學方法測量外徑的儀器，把CCD器件作為光電接收器。 CCD 從功能上可分為線陣CCD 和面陣CCD 兩大類。 線陣CCD通常將CCD內(nèi)部電極分成數(shù)組，每組稱為一相， 并施加同樣的時鐘脈沖。所需相數(shù)由CCD芯片內(nèi)部結(jié)構(gòu)決 定 ， 結(jié) 構(gòu) 相 異 的 C C D 可 滿 足 不 同 場 合 的 使 用 要 求 。 線 陣 CCD有單溝道和雙溝道之分，其光敏區(qū)是MOS電容或光敏 二極管結(jié)構(gòu)，生產(chǎn)工藝相對較簡單。它由光敏區(qū)陣列與移位 寄存器掃描電路組成，特點是處理信息速度快，外圍電路簡 單，易實現(xiàn)實時控制但獲取信息量小，不能處理復雜的圖像(線陣CCD如右圖所示)。面陣CCD的結(jié)構(gòu)要復雜得多，它由很多光敏區(qū)排列成一個方陣，并以一定的形式連接成一個 器件，獲取信息量大，能處理復雜的圖像。我們所使用的 CCD攝像頭實物如圖18。
5.3  舵機控制原理
舵 機 接 出 來 三 根 線 ， 紅 色 的 是 電 源 線 ， 棕 色 的 是 地 線，橘黃色的是信號線。舵機的工作電壓在4.8V到6V之間， 供電電壓不同，會影響舵機轉(zhuǎn)動的速率以及舵機的輸出力 矩。我們的板子上面的供電是5V電壓。舵機里面是一個步進電機、一個基準電路以 及其它部 件，信號線輸入不同的信號時會和基準電路進行比較，從 而決定舵機的轉(zhuǎn)動方向。舵機旋轉(zhuǎn)的角度由脈沖的高電平時 間決定，在一個周
期為20ms的脈沖里面高電平持續(xù)的時間 決定了舵機轉(zhuǎn)動的角度，180度舵機對應關(guān)系如下：
0.5ms--0 度，1ms--45度，1.5ms--90度，2ms--135度，2.5ms--180度。我 們所使用的舵機實物
如圖19（170頁）所示。
5.4  顏色識別原理
5.4.1   BP神經(jīng)網(wǎng)絡(luò)
神經(jīng)網(wǎng)絡(luò)是一種運算模型，由大量的節(jié)點(或稱“神經(jīng) 元”或“單元”)相互連接構(gòu)成。每個節(jié)點代表一種特定的 輸出函數(shù)，稱為激勵函數(shù)(activation function)。每兩個節(jié)點之 間的連接都代表對于通過該連接信號的加權(quán)值，稱為權(quán)重 (weight)，這相當于人工神經(jīng)網(wǎng)絡(luò)的記憶。網(wǎng)絡(luò)的輸出則依 網(wǎng)絡(luò)的連接方式、權(quán)重值和激勵函數(shù)的不同而不同。網(wǎng)絡(luò)本 身通常是自然界的某種算法或者函數(shù)逼近，也可以是一種邏 輯策略的表達。如圖20（170頁），是一個BP神經(jīng)網(wǎng)絡(luò)圖。
其中包含3個層次：
輸入層：輸入層各神經(jīng)元負責接收外接的輸入信息，并傳遞給中間層各神經(jīng)元 隱藏層：中間是內(nèi)部信息處理層，負責信息變換，根據(jù)信息變化能力的需求，中間層可以設(shè)計為單隱層或者多隱 層結(jié)構(gòu)；最后一個隱層傳遞到輸出層各神經(jīng)元的信息，經(jīng)進 一步處理后，完成一次正向傳播處理過程；輸出層：顧名思義，輸出層向外界輸出信息的處理結(jié)果；當上層的神經(jīng)元輸出經(jīng)過連接加權(quán)求和后，傳遞到下
一個神經(jīng)元時，經(jīng)過激勵函數(shù)處理后，才作為本層輸出，激 勵函數(shù)一般有以下幾種形式：

線性函數(shù)

閾值函數(shù)

Rectified linear函數(shù)

Sigmoid函數(shù)
本次顏色識別采用的激勵函數(shù)為Retified linear函數(shù)。采 用54*3個神經(jīng)元作為輸入層，輸入54個待分辨色塊的R ,G,B 值，兩個隱藏層，神經(jīng)元數(shù)分別為300與100，輸出層為54個 神經(jīng)元，輸出每個色塊的顏色分類結(jié)果。0表示白色，100表 示紅色，200表示藍色，300表示綠色，400表示黃色，500表 示橙色，輸出取在標準值附近，取最靠近的數(shù)為輸出。(未 完待續(xù))