0. 前言
当我还是一名学生时，我建造了一个解魔方机器人。速度并没有那么快。颜色识别过程耗时约15秒，求解时间约40秒。造成时间过长的主要限制因素有两个。首先是使用的舵机，电机转速无法提高。二是机械结构的限制。使用左、右、前、后四个舵机。没有上下自由度导致求解步骤数被拉长。下面主要从结构、软件、算法等方面来说明整个系统的组成。
1. 结构
由两个舵机组成的曲柄滑块的机械结构主要用作回收魔方的机械手。八个舵组成四组机械手。
魔方解题机器人整体结构
2、软件框架
魔方机器人恢复的完整流程如下： 首先是获取魔方的颜色状态。此阶段需要STM32和APP的协调配合。 STM32控制舵机旋转待拍照的魔方面，并通过蓝牙通知相机拍照。相机拍照。拍照完成后，通过蓝牙向STM32发送指令，通知STM32控制舵机旋转下一个要拍照的面kaiyun.ccm，直到相机拍摄完魔方六个面的六张照片。接下来，通过读取照片信息得到魔方的颜色分布，经过魔方复原算法处理后得到复原公式。为了缩短魔方恢复时间，让STM32更容易分析魔方，需要对恢复指令进行优化和优化。处理后的指令然后通过蓝牙发送到STM32。 STM32将指令解析为舵机执行的动作，完成魔方的复原。
魔方解谜机器人软件框图
3. 算法
3.1 Kociemba算法
该求解算法是著名的Kociemba算法的移植版本。最大恢复步数为21，求解时间为ms级别。传统的层优先方法虽然思路简单，但平均需要150步左右，而步数稍少的CFOP算法也需要100步左右。
下图是本文移植的Kociemba算法Java测试软件。打乱按钮可以随机打乱魔方并显示在界面中。移动限制设置恢复魔方公式的最大步数，时间限制设置恢复魔方的最长时间。 Solve Cube 按钮运行 Kociemba 算法并生成恢复公式。当设定的时间没有解决或者设定的步数太短时，软件会提示。
Kociemba算法Java测试软件
魔方中心块上的字母代表该面的方位：F（前）代表前，B（后）代表后，L（左）代表左，R（右）代表右，U (up)代表顶部，D(down)代表下方。魔方有 6 种颜色。某种颜色的颜色标签由该颜色的中心块的方向（F、B、L、R、U、D）表示。 Kociemba算法的输入参数是魔方54个色块的标签排列。颜色标签按一定顺序排列。六个面的顺序是上、右、前、下、左、后。每个面的标签排列是按照从上到下、从左到右的顺序。
3.2 一个优化问题
3.2.1 恢复魔方命令系统
魔方机器人有两套指令系统。第一个指令系统是世界各地魔方解题教程中使用的恢复指令系统。也是Kociemba算法得到的恢复指令所使用的指令系统。第二个指令系统就是我们魔方机器人在进行魔方恢复时使用的指令系统。事实上，对于恢复命令优化方案来说，一方面是通过优化命令来缩短魔方的恢复时间，另一方面也将第一套命令系统改造为第二套命令系统，以便STM32收到命令后进行分析。找回魔方。因此，第一套命令系统称为未优化命令系统，第二套命令系统称为优化命令系统。
指令系统未优化，单指令共18条。表中字母L（左）代表左侧，R（右）代表右侧，F（前）代表前云开·全站体育app登录，B（后）代表后，U（上）代表上，D（ downm) 代表底部。字母后面加 ' 表示逆时针旋转 90 度。例如，F'表示将魔方正面逆时针旋转90度。单个字母表示顺时针旋转 90 度。字母后面的数字2表示对应的面旋转180度。由于逆时针旋转180度和顺时针旋转180度效果是一样的，所以不做区分。
优化后，命令系统共有16条单命令。指令系统中所有与未优化指令系统中相同的指令也具有相同的含义。优化指令系统中^后面的字母与未优化指令系统中单个字母的含义相同。两个相同的字母代表翻转指令，例如：LL表示向左翻转魔法90度。
优化前后指挥系统
3.2.2 恢复指令优化的来源
从上面介绍的两套指令系统可以看出，优化后指令系统中去掉了字母U、D的指令，增加了翻转指令。这种差异是由魔方机器人的机械结构决定的。为了提高整个机械结构的稳定性并节省成本，本文设计的魔方机器人的机械手只有四个自由度。下图展示了魔方机器人机械结构形成的四个自由度。一个普通人正在修复魔方。在此过程中使用了手的六个自由度。与人手相比，魔方机器人缺少垂直方向的直线运动和旋转两个自由度。
魔方机器人机械结构（俯视图）
优化后，指令系统中每个单指令对应的舵机执行步数是一定的。当舵机匀速运行时，恢复时间与舵机执行步数成正比。优化后的指令系统中每条指令对应的伺服执行步数如下表所示。从表中可以看出，旋转90度指令对应的舵机执行步数为4步，因为旋转180度指令是执行两次90度旋转，所以对应的舵机执行步数为4步。执行步数为8步，翻转指令对应的舵机执行步数为6步。
之所以需要对Kociemba算法得到的魔方恢复指令进行优化，最本质的原因是优化后可以缩短恢复指令对应的伺服执行步数，从而缩短魔方恢复时间。我们知道，机器人旋转魔方的前后左右都是非常简单直接的。通过两个舵机的配合，只需4步即可完成前后左右四个方向中的任意一个。然而，在旋转魔方顶部和底部时，由于次要方向缺乏自由度，需要翻转魔方。翻转后，恢复魔方的说明会发生变化。四个不同方向的翻转对应四种不同的命令变化，如下表所示。例如：向左翻转后，指令U'变为L'。
从上表可以看出，执行U、D指令时，需要先翻转，然后旋转L、R、F或B面的魔方，才能完成这条指令的执行。但随之而来的问题是：翻转后还需要翻转回去吗？返回到原始位置需要相应的翻转动作，但舵机必须执行额外的 6 步而不翻转回原始位置。所有后续指令都将因翻转而改变。我们不知道更改后的命令对应的伺服执行步数是否小于未更改的命令对应的伺服执行步数。
从上面的分析可以看出，在指令解析过程中，存在一个优化问题，即执行字母U或D的指令时向哪个方向翻转，以及翻转后是否需要翻转回来。
从Kociemba算法的求解指令到机器的执行指令可以看作是一个优化问题，即最小化求解步骤数。为了解决最优解问题，我们构建了二叉树算法模型，参考贪心算法的思想，将指令解析优化问题转化为树的最短路径问题。
3.2.3 优化效果
为了比较二叉树模型对恢复指令优化的效果，我们制作了一个测试程序，即恢复指令优化的基本模型。当基本模型解析带有U或D字母的指令时，它会将它们翻转回来，并将第一组指令系统更改为第二组指令系统。也就是说，基础模型只是还原了Kociemba算法。指令转换为STM32单片机可以识别的第二套指令系统，并没有进行优化。流程图如下图所示。
对于Kociemba算法得到的魔方恢复指令，通过比较通过基本模型和二叉树模型得到的恢复指令对应的伺服执行步数，可以得出二叉树模型对恢复指令优化的效果比较的。
下图测试了15组数据。横轴上的15个实验数字代表15个魔方恢复指令。如图4-2所示，Kociemba算法测试软件可以随机打乱魔方，并通过算法生成打乱魔方的恢复公式。 ，与手动打乱魔方相比，更加科学合理。
与图中的基本模型相比，二叉树模型中舵机步数对应的最大优化步数为90，最小优化步数为16，平均优化步数为51.6，最大优化率为38.8%，最小优化率为7.4%开yun体育app官网网页登录入口，平均优化率为23.6%。从以上数据可以看出，二叉树模型的优化效果非常显着。
二叉树算法模型优化结果
3.3 自动颜色识别方案
自动颜色识别方案是备用方案，因为稳定性需要提高，主要使用聚类算法K-means。主要目的是对幻方盒子进行聚类，然后计算9个中心点。
事实上，最后我们发现一切都是数学。
