新浪博客

控制系统设计：魔方还原机器人解析

2017-08-27 17:26阅读：

http://blog.sina.cn/dpool/blog/u/2793933290

【前言】

目前世界上最快的魔方复原机器人，是2018年麻省理工两名学生Ben Katz和Jared Di Carlo研发的，还原3阶魔方只用了0.38秒，采用了六个电机+3枚摄像头+定制的控制器，只需15毫秒内就可以完成魔方的单圈旋转。而之前的最好战绩，是德国工程师AlbertBeer发明的升级版Sub1，战绩：0.637秒，于2016年11月9日，该款机器人外观与运转动图如下所示。

控制系统设计：魔方还原机器人解析
控制系统设计：魔方还原机器人解析

控制系统设计：魔方还原机器人解析

【Sub1 Reloaded 还原魔方的工作原理与特点】

该款机器人内部嵌入了许多微芯片，只要按下按钮就会自动进入复原魔方模式。1、打开百叶窗，电脑通过机器视觉扫描图像，检测魔方是如何被打乱的。2、通过算法在不到0.15毫秒的时间内得出最快的复原方式。3、通过微处理器将指令传输给六个电驱动机器臂，并由机器臂快速转动魔方，完成对魔方的复原。为了使转动时间保持最小，设计者制造了一个“速度立方体”，用以减少移动部件产生的摩擦力。该款机器人运用了英飞凌的微控制器，与无人车辅助驾驶系统中的控制器200MHz高速运算避障刹车的算法很相似，都能使机器能做出“最少反应” （minimal reaction times）。

【研究魔方还原算法的意义】

匈牙利教授厄尔诺·鲁比克发明魔方时，仅仅是作为一种帮助学生增强空间思维能力的教学工具。但要使那些小方块可以随意转动而不散开，不仅是个机械难题，还牵涉到木制的轴心，座和榫头等。将魔方转了几下后，教授才发现如何把混乱的颜色方块复原竟是个有趣而且困难的问题。因此，鲁比克决心大量生产这种玩具。魔方在发明后不久就风靡世界。除了对教育行业带来深远影响，魔方也对科学研究产生了巨大推动力。截至目前，晶体学、晶体电子衍射、夸克以及基因学等多个领域的模型构建都曾借鉴过三阶魔方。如今人工智能技术的很多应用场景中也有了“魔方”的身影。

【人工还原魔方的一些方法与算法】

一个普通的三阶魔方的组合变化总数约为 4.3 X10^19 个，若将这个数量的标准大小魔方铺满地球表面，可以累积 275 层，每层厚度约 20 米。三阶魔方的变化不可谓不多，对于新手来说，如果你不知道方法，你可能穷其一生的时间也无法将其复原。以下是一些三阶魔方的公式介绍：

初级和高级：1、层先法/LBL（Layer By Layer）：指逐层还原魔方的方法。由于所需要背的公式很少，只需要七个步骤，所以层先法一般都是初学者先学的解法。2、角先（Corner First）：角先方法是先将魔方的八个角归位定色，然后再填补棱色，最后完成复原。这种方法记忆的公式比较多，所以速度会较层先快。最快的角先魔方高手可以在30秒之内复原魔方。3、棱先：棱先方法是先将棱块归位定色，然后填补底层和上层的角块的方法。4、8355法：强调以理解的方法去解出魔术方块。将方块分成单层8个角、第二层3个边、第三层5个边归位后再将剩下5个角归位并转正。其后面两段'五边'和'五角'的解法，可以用在Megaminx正十二面体魔术方块的最后一层解法上，不需要做调整改变，依然适用。4、SCAF：SCAF (Six Cross And Finger shortcut) 玩家只需要记忆一个口诀 (右上左下)，利用这个口诀就能完成六面魔方，与8355法不同的是SCAF跳过第一层角块这项大难关，这大大降低了初学者学习难度，这也是SCAF被整理出来的目的。SCAF在解法中被归类为棱先法，先完成所有边块的位置与方向再借由 FSC(U’RUR’) 完成剩余的角块；精通整个解法过程可以达到 Sub25，尤其是对于背公式感到反感的玩家来说SCAF 是非常适合的解法。5、LARS：这是一种解魔术方块的方法，发明人为Lars Petrus，号称步骤比CFOP少的解法。1）构造一个 2x2x2块；2）扩展成2x2x3块；3）修正朝向错误的棱块；4）F2L-3rd & 4th（还原剩下的两对F2L，步骤3使顶层的Cross强制完成)；5）顶层角块位置；6）顶层角块方向；7）最后4个棱块的位置。6、桥式解法 (Roux Method)：先在两个侧面下方各形成正确的2X3两块，使顶面的四个角块归位，调整中间四个棱块和侧面两个棱块的朝向，左右侧面顶部的棱块归位，中间棱块和中心快归位。7、Fridrich Method：Fridrich Method (简称CFOP) 其实是层先的变种，但是由于其归纳出了可能出现的各种情况，所以在记忆量上面要增大许多倍（119个公式），但同时也能有效的增加速度。其步骤分为以下几个：将底层转出一个符合色块分布的十字（Cross），同时将底层角块和相对应棱块归位（F2L，First 2Layers） 41个公式，最上层利用公式将颜色统一（OLL，Orientationof Last Layer）57个公式，将最上层侧面的颜色统一 （PLL，Permutationof Last Layer）21个公式，现在绝大多数魔方高手都使用Fridrich Method，因为相对于它能达到的速度来说，119个公式的记忆量就显得不多了。

大神级别：1、X-Cross＋ZBF2L＋ZBLL；2、X-Cross＋VHF2L＋ZBLL；3、X-Cross＋ZBF2L＋COLL＋PLL；4、X-Cross＋VHF2L＋COLL＋PLL。其中，X-Cross 其实是指Extended Cross，即完成Cross的同时完成F2L步骤的第一组F2L。VHF2L 是 Vandenbergh-Harris F2L的略称。一共32个公式 (左右对称，各有16个)，可以一次性对好基本型下的最后一组F2L以及同时对好顶层十字，这样使得CFOP里的OLL情况从57种降至7种。ZBF2L：完成最后一组F2L的同时完成顶层十字。和VHF2L十分相似、最大的不同是判断的时机：VHF2l是在最后一组的基本型完成之后判断；而ZBF2L是在最后一组F2L的基本型形成之前就开始判断，所以ZBF2L包含了VHF2L。公式一共有302个。COLL：由CLL和OLL组合而来，可以说是OLL的加强版，相当于[OLL + PLL的换角]，一共40个公式。前提是顶层已经形成十字状态，从该状态开始，通过COLL公式，一次性对好顶面4个角块的方向和顺序，但尚未做好棱换的状态。做完COLL之后，大部分情况下魔方已还原(即不必做最后一步PLL)，另外还会有出现4种情况棱块还没有还原，这时还得用PLL解决，但这四种情况下的PLL非常简单。ZBLL是COLL的加强版。从顶层十字状态开始，一次性做好OLL和PLL，即=COLL+棱换。一共493个公式。此外还有两个高难度解法：1、ALL/1LLL：All Last Layer的略称，也称1LLL(1-Look Last Layer)，从F2L完成后的状态开始，一步完成OLL和PLL，共近4000个公式(镜像和逆公式算作一个公式的话，则有一千多个)。2、Double Extended Cross：完成Cross的同时完成F2L步骤的前两组F2L。

【机器还原魔方的一些方法与算法】

步骤1、魔方的数组表示、数据结构设计

魔方有6个面，每面含9个色块，要让计算机知道每块魔方具体的方位和朝向，我们就必须将魔方用数字信号代替并输入电脑中。这一步骤主要是将魔方各块的各个方位在空间坐标系里表示出来，来具体确定魔方各个模块的具体方位，从而才能够给出具体的魔方解决算法。魔方的点主要分为：三面相接的角点，面相接的边点，面中心的基本点。其中，基本点是固定的，魔方在变形过程中，基本点是没有办法进行改变的，图中1-1，2-2，3-3的相对位置是固定的，改变的只能是角点和边点，基于此，基本位置衡量必须基于基本点。

（自动还原魔方算法数据结构，参考案例 http://blog.csdn.net/cun_chen/article/details/50261787）

控制系统设计：魔方还原机器人解析

根据基本点，设置边点编号，相同编号表示为同一边块；再设置角点编号，相同编号表示为同一角块，如下图。

控制系统设计：魔方还原机器人解析
控制系统设计：魔方还原机器人解析

根据上图，不论边块还是角块，只需要四面就可以确定全部边块及角块位置，因此设置最小确定点如下图。

控制系统设计：魔方还原机器人解析

由此可见，魔方不论如何变换，其角块对于基本点相对位置是对应的，不可能出点所以基本点按照正确位置排列，但具体色块颜色位置出现问题，基于此设置魔方基本变换方法两种，边点变换和角点变换。角点变换不存在什么问题，但是边点变换存在基本点变换的问题，由于我们设置基本数据结构基于基本点，因此基本点不能进行变换，故：边点变换=左角变换+右角变换，根据最小确定点，可以设置数据结构为一维数组或二维数组。

控制系统设计：魔方还原机器人解析

基本变换方法（不涉及基本点变换）

　Method turnRightClockwise()
　Method turnRightAnit()
　Method turnLeftClockwise()
　Method turnLeftAnit()
　Method turnTopClockwise()
　Method turnTopAnit()
　Method turnTBottomClockwise()
　Method turnTBottomAnit()
　Method turnOutsideClockwise()
　Method turnInsideClockwise()

扩展方法（涉及基本点变换，转化为基本方法）
　Method turnTransverseClockwise() 中心横向顺时针
　Method turnTransverseAnit() 中心横向逆时针
　Method turnLongitudinalClockwise() 中心纵向顺时针
　Method turnLongitudinalAnit() 中心纵向逆时针

设置值栈进行路径探索，终点是可以确定的，只要保证相对位置符合，那最终位置就是确定的。用栈来存储变换路径其实就是防止无限递归问题，如果发生变换到之前发生过的情况，则后退重新变化。

步骤2、扫描魔方、识别色彩

机器人的视觉识别多使用摄像头，经过图像分割、聚类算法，在HSV（Hue，Saturation,Value）颜色空间下实验分析。机器人通过颜色传感器经过伺服电机转动实现识别色彩，事实上这个数值受环境光线强度影响非常大，即使相同的环境下，读数也会有波动，何况必须扫54个点，为此我们还需要定义分辨颜色的判断规则，来提高魔方颜色识别的准确率。

步骤3、魔方求解算法

机器人解三阶魔方算法的实质是将人解三阶魔方的思维转化为机器人的“思维”，具体的做法是：首先魔方由上、下、左、右、前、后六个面构成,表面共有蓝、红、黄、绿、白、橙六种颜色，分别用1、2、3、4、5、6六个数字表示，魔方每个面由9个色块构成，对于每个面我们采用一个3X3的数组表示这个面上9小块的颜色分布。然后将对魔方进行旋转后各表面色块分布的变化转换为相应位置数组元素值的改变，即魔方表面的旋转对应着数组元素的变化，魔方表面色块的归位对应着相应数组中元素值的同一化。若要提高解魔方的速度,除了依靠硬件系统的性能外，选择最佳解魔方算法也是关键一步。目前，可以应用的解三阶魔方的方法比较多，有初级层先法、CFOP法等。其中最有利于机器人执行的是初级层先法。常见算法一：最优转发算法。百度百科里边有，已经证明了，不论在什么情况下，魔方20步之内可以还原，但由于要保证相对位置，所以中心点不可以改变，涉及到中心点的变动可以转换为两边转动，所以直接设置栈深50，这样进行完全遍历时间复杂度还是太高，所以需要根据一些基本魔方原理进行时间效率优化。常见算法二： 可以采用魔方公式进行模拟，层旋发，桥式这些都是相对简单的转法。

（三阶魔方CFOP复原C语言算法，参考案例 http://blog.csdn.net/u010650845/article/details/62420526）

步骤4、机械自动还原

魔方作为一个正立方体，有6面需要行动，要实现对魔方的某个面进行旋转要求魔方机器人的机构有两个基本功能：固定功能和旋转功能。固定功能是能够承载魔方，使得魔方整体固定在某一位置；旋转功能是对魔方的某个面进行动旋转。魔方机器人的手臂控制通常采用舵机控制器进行机械手动作组控制，舵机控制器可实现多路伺服电机单独控制或同时控制。控制中心可以通过串口发送指令控制舵机控制器，控制指令精简，控制转角精度高，波特率可以实时更改，体积小，重量轻，其可作为类人型机器人、仿生机器人、多自由度机械手的控制器。

因此，从上面机器人还原魔方的步骤上来看，魔方机器人的还原速度主要取决于魔方的扫描速度、魔方算法程序、控制中心的数据处理速度以及机械运动还原速度。

【END】

我的更多文章

下载客户端阅读体验更佳

APP专享