速解魔方機(jī)器人(中)

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

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

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

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

圖16　魔方還原算法流程圖

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

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

線性函數(shù)

閾值函數(shù)

Rectified linear函數(shù)

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