新闻中心

EEPW首页 > 嵌入式系统 > 设计应用 > 速解魔方机器人(中)

速解魔方机器人(中)

作者:孙磊 张洋洋 吴坷时间:2017-03-07来源:电子产品世界收藏

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

本文引用地址:http://www.eepw.com.cn/article/201703/344897.htm

前面顺时针旋转为【 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表 示橙色,输出取在标准值附近,取最靠近的数为输出。(未 完待续)



关键词: 魔方 机器人

评论


相关推荐

技术专区

关闭