速解魔方機器人(中)

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

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

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

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

圖16　魔方還原算法流程圖

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

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

線性函數

閾值函數

Rectified linear函數

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