怎样做出能在 5 秒内解开魔方的机器人？ 第1页

第二版解魔方机器人（有点晃） https://www.zhihu.com/video/1205597785783107584

有小伙伴反应上面的视频太晃，所以这里放出另外一个视频，我们制作的第一个版本，如下所示：

0. 前言

学生时代做过一个解魔方机器人，速度没有那么快，颜色识别过程大约15S，解算时间大约40S。造成时间长的限制因素主要有两点，第一是用的舵机，电机转速上不去，第二是机械结构的限制，使用的是左、右、前，后的四个舵机，没有上下的自由度，造成解算步数的拉长。下面主要从结构，软件，算法等方面说下整个系统的构成。

1. 结构

主要采用了舵机两两一组构成曲柄滑块的机械结构作为复原魔方的机械手，8个舵机构成四组机械手。

2. 软件框架

魔方机器人复原的完整过程如下：首先是魔方颜色状态的获取，这一阶段需要STM32和APP协调配合，STM32控制舵机把要拍照的魔方的面旋转到上面，通过蓝牙通知摄像头来照片，摄像头拍完照片之后通过蓝牙给STM32发送指令，通知STM32控制舵机把下一个要拍照的面旋转到上面，直到摄像头拍照完魔方六个面的六张照片。接下来通过读取照片的信息获取魔方的颜色分布，经过魔方复原算法的处理之后得到复原公式，为了缩短魔方复原的时间同时使STM32在解析魔方时更加容易，需要对复原指令进行优化处理，优化处理后的指令再通过蓝牙发送给STM32，STM32把指令解析为舵机执行的动作，完成魔方的复原。

3. 算法

3.1 Kociemba算法

解算算法方面是移植的大名鼎鼎的Kociemba算法，最大复原步数为21步，并且其解算时间为ms级。传统的层先法虽然思想简单，但是平均需要大约150步，步数稍微短一点的CFOP算法也要在100步左右。

下图本文移植的Kociemba算法Java测试软件。按钮Scramble可以随机打乱一个魔方，并在界面中显示出来，Move Limit设定复原魔方公式的最大步数，Time Limit设定复原的最大时间。按钮Solve Cube运行Kociemba算法并生成复原公式，当超过设定的时间还没有解算出来或者设定的步数过短时，软件会有提示。

魔方中心块上的字母代表这个面所处的方位：F(front)代表前面，B(back)代表后面，L(left)代表左面，R(right)代表右面，U(up)代表上面，D(down)代表下面。一个魔方共有6种颜色，某种颜色的颜色标号用中心块为该颜色的面所处的方位(F、B、L、R、U、D)来表示。Kociemba算法的输入参数即为魔方54个颜色块的标号排列，颜色标号的排列按照一定的顺序，六个面的顺序依次为上、右、前、下、左、后，每个面的标号排列按照从上到下，从左到右的顺序。

3.2 一个最优化问题

3.2.1 复原魔方指令系统

魔方机器人有两套指令系统，第一套指令系统是现在世界各地的解魔方教程中所使用的一套复原指令系统，也就是Kociemba算法得到的复原指令中使用的指令系统，第二套指令系统是我们的魔方机器人在执行魔方复原时用到的指令系统。其实对于复原指令优化程序来说，一方面是通过优化指令缩短魔方复原的时间，另一方面也是把第一套指令系统转变为第二套指令系统，这样STM32才能在接收到指令后进行解析，复原魔方。所以第一套指令系统我们称为未优化指令系统，第二套指令系统我们称为优化后指令系统。

未优化指令系统，共有18种单指令。表中字母L(left)代表左面，R(right)代表右面，F(front)代表前面，B(back)代表后面，U(up)代表上面，D(dowm)代表下面。字母后面加’代表逆时针旋转90度，例如F’表示将魔方的前面逆时针旋转90度，单独一个字母表示顺时针旋转90度，字母后面有数字2表示将相应的面旋转180度，由于逆时针旋转180度和顺时针旋转180度的效果是一样的，所以不做区分。

优化后指令系统，共有16种单指令。指令系统中所有和未优化指令系统相同的指令表示的含义也相同，优化后指令系统中字母后面加^和未优化指令系统中单字母表示的含义相同。两个字母相同的代表翻转指令，例如：LL代表把魔方向左翻转90度。

3.2.2 复原指令优化的来源

从上面介绍的两套指令系统可以看出，优化后指令系统去掉了带有字母U和D的指令，并且加入了翻转指令。这种差异是由魔方机器人的机械结构所决定的。为了提高整个机械结构的稳定性同时为了节省成本，本文设计的魔方机器人的机械手只有四个自由度，下图表示的是魔方机器人机械结构形成的四个自由度，而一个普通人在复原魔方的过程中用到了手的六个自由度，和人手相比，魔方机器人缺少了竖直方向的直线运动和旋转两个自由度。

优化后指令系统中每个单指令所对应的舵机执行步数是一定的，当舵机运行的速度一定时，复原时间和舵机执行步数成正比例关系。优化后指令系统中每一个单指令所对应的舵机执行步数如下表所示，从表中可以看出，旋转90度的指令对应的舵机执行步数为4步，因为旋转180度的指令是执行两次旋转90度的指令，所以其对应的舵机执行步数为8步，翻转指令对应的舵机执行步数为6步。

为什么需要对Kociemba算法得到的魔方复原指令进行优化处理，最本质的原因是经过优化处理后可以缩短复原指令所对应的舵机执行步数，进而缩短魔方复原时间。我么知道，机器人旋转魔方的前、后、左，右面时是很容易且直接的，两个舵机之间通过配合只需要4步就可以完成前、后、左，右面四个面任意一个面90度的旋转，但是在旋转魔方的上、下面时，由于缺少次方向的自由度，就需要通过翻转魔方，翻转之后魔方复原指令会发生变化，四种不同方向的翻转对应四种不同的指令变化,如下表所示。例如：经过向左翻转，指令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%，平均优化比例为23.6%。从上述数据中可以看出，二叉树模型的优化效果非常显著。

3.3 颜色自动识别方案

颜色自动识别方案是备用方案，因为稳定性有待提高，主要使用了一种聚类算法K-means。主要是对魔方框做聚类，再计算9个中心点。

项目已经开源，包含源代码、教程、视频，工程设计图纸等，地址如下：

其它视频如下：