速解魔方机器人(中)

接上篇
4.3 系统软件设计
4.3.1   魔方还原算法流程
     本算法是一个可以给出将魔方任何可能的混乱状态还 原回六面同色状态的算法。目前常用的CFOP法是一种4阶段 算法，一共分有4个还原阶段，平均步数在50-70步。而任意 状态的魔方的还原方法已经被证明可以在20步之内，可见这 种方法有很大的冗余，还有提升空间。本算法能在短时间里 提供出一组平均步数在 25步左右的解决方案。
魔方有6个面，每个面存在3种操作(正对该面，顺时针 旋转，逆时针旋转，180度旋转)，一共18种操作。首先介绍 一下各个旋转操作的简称：

前面顺时针旋转为逆时针旋转为，180 度旋转为。后面相应为。接下 来介绍算法中的编码。算法有两个阶段，每个阶段有不同的 编码方式，如下表，第一阶段：

通过摄像头或者手动输入采集魔方状态之后，我们需 要用一种方式保存初始魔方状态。魔方有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个层次：
输入层：输入层各神经元负责接收外接的输入信息，并传递给中间层各神经元 隐藏层：中间是内部信息处理层，负责信息变换，根据信息变化能力的需求，中间层可以设计为单隐层或者多隐 层结构；最后一个隐层传递到输出层各神经元的信息，经进 一步处理后，完成一次正向传播处理过程；输出层：顾名思义，输出层向外界输出信息的处理结果；当上层的神经元输出经过连接加权求和后，传递到下
一个神经元时，经过激励函数处理后，才作为本层输出，激 励函数一般有以下几种形式：