速解魔方機器人(中)

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

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

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

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

圖16　魔方還原算法流程圖

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

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

線(xiàn)性函數

閾值函數

Rectified linear函數

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