基于DFS的二指双臂魔方机器人

崔俊文 刘自红 邓明洋 乐玉

摘要：本文提出一种二指双臂的解魔方自动化系统，其可以自主完成魔方颜色提取、求解和还原过程。首先利用双摄像头对魔方面进行色彩信息提取，编码后利用kociemba算法求解魔方，解码后依据自定义空间坐标，利用DFS-回溯算法规划机械执行步，并设置相应权重，全局优化双手臂求解步骤及时间。在该算法下，该套系统可以快速求解魔方，并可以得到适应硬件执行的最优结果。

关键词：魔方复原;视觉识别;坐标系构建与仿真;深度优先搜索

中图分类号：TP249    文献标识码：A

文章编号：1009-3044（2019）24-0194-05

开放科学（资源服务）标识码（OSID）：

Two-finger Arm Cube Robot Based on DFS

CUI Jun-wen， LIU Zi-hong*， DENG Ming-yang， LE Yu

（Southwest University of Science and Technology， Mianyang 621010， China）

Abstract： This paper proposes a two-finger double-armed magic cube automation system， which can independently complete the Rubik's cube color extraction， solution and restoration process. Firstly， the dual-camera is used to extract the color information from the magic aspect. After encoding， the kociemba algorithm is used to solve the puzzle. After decoding， according to the custom space coordinates， the DFS-backtracking algorithm is used to plan the mechanical execution steps， and the corresponding weights are set， and the double-arm solution steps are optimized globally. time. Under the algorithm， the system can quickly solve the Rubik's cube and get the optimal result that is adapted to the hardware execution.

Key words： rubik's cube restoration; visual recognition; coordinate system construction and simulation; depth-first search

隨着工业发展的逐步推进，机器人产业如雨后春笋在全国范围内遍地开花，自动化成了新时代的潮流，“机器换人”的概念逐渐成为现实，智能化的局面已经大势所趋。“机器人的革命”，有望成为第三次工业革命的一个重要切入点和增长点，将影响全球制造业格局，其市场前景也是可期的。

魔方（Rubik's Cube）发展了30多年，最短破解时间记录每年都在翻新，除了玩家的练习与心得之外，最主要靠的就是将公式改进。第一届世界冠军的成绩为22s，近年来由于公式的不断改进，加上网络发达促成魔方达人之间的相互交流，在2013年3月的比赛中Mats Valk以5.55s刷新了世界纪录。随着机器人技术的逐步发展，将魔方与机器人技术相融合在科普领域取得了突破性的进展，在计算速度方面，不再依赖于个人的灵巧、和对公式的熟练运用，更多的是将计算机、机械制造、和电子信息的结合，解魔方机器人的整体架构和多种变型模式也成了近几年的热点。

1 魔方机器人设计

1.1 机械结构

双手臂采用步进电机模拟手臂旋转，行程手指气缸实现二指夹取魔方中心外延，如图1所示。双手臂成90°卧式垂直布局，该种方式有利于保持魔方在空间内保持稳定不倾斜。分别在气缸和电机的驱动下模拟人手的手指和腕部的运动。通过电磁阀控制气缸的开闭即手的张合，电机与手部气缸通过联轴器连接，电机旋转带动手臂机械旋转，手臂回旋机械范围为正负360°。

1.2 工作流程

采用双摄像头对射魔方棱边，单次可提取四个魔方面的色彩信息。在图像上构建魔方浮动框选区域，该区域可进行调整位置和尺寸对魔方棱边视角进行框选，单个子区域经仿射变换实现对魔方面矫正，经高斯滤波后，对每个色块区域进行颜色提取，提取后采用K-mean算法进行识别分类。通过计算机端进行颜色采集和编码生成，利用DFS算法全局优化机械执行步编码，再通过串口通信发送给STM32下位机控制单元。下位机解析机械执行步编码执行双手臂机构进行魔方还原。流程图见图2

2 视觉识别

为快速获取魔方色彩面信息，采用双摄像头对棱边进行提取色彩信息。单个相机可获得魔方两面四边形色彩区域。分割为左右两区域，并进行定轮廓框选。针对四边区域进行仿射变换获得正视魔方面图像，校正后对各颜色块顶坐标色彩区域进行提取，如图3所示。在色彩空间HSV中进行颜色识别，该方法有利于削弱光线强弱对色彩识别的影响。

仿射变换后的面已经被旋转矫正，只需按特定坐标顺序读取魔方面信息。全部魔方面信息仿射变换后效果为图4。采用K-mean算法进行识别，该方法自动实现识别过程，且具有很强的抗干扰能力。

3 魔方编码执行及坐标系构建

3.1 编码转化执行

利用kociemba算法求解魔方，可获得执行编码，规定执行编码格式为XN，X表示魔方面坐标描述，有F，U，R，D，L，B。N表示对应面得执行方法，规定1为顺时针旋转90°，2表示顺时针旋转180°，3表示逆时针旋转90°。如F2则表示对F面进行180°旋转。该执行编码是对魔方面操作的标识，机器人无法直接执行，还需转化为机械执行步。

机械执行步主要是机器人在求解魔方过程中具体动作的执行，该转换过程依据图5中定义得魔方坐标系。机械执行步主要有左手张开（LO），右手张开（RO），左手闭合（LC），右手闭合（RC），左手顺时针旋转90°（L1）， 左手逆时针旋转90°（L3），左手旋转180°（L2），右手顺时针旋转90°（R1）， 右手逆时针旋转90°（R3）和右手旋转180°（R2）。示例机械执行步对应转换过程参考表1。

3.2 坐标系构建

构建魔方相对坐标系，在双手臂执行求解魔方过程中，需要对执行的魔方面在相对坐标系中进行搜索，再执行面切换和旋转操作。

将三维空间魔方坐标系转化为一维矩阵，前后顺序按照绝对空间坐标固定的读取方式，读取顺序按图6中ID序列。该种方法有利于程序检索。在每次魔方面执行操作结束后，需要对该记录魔方坐标信息的一维矩阵进行刷新纪录。对F，U，R，D，L，B每个执行面切换至左手或右手旋转时，一维坐标矩阵则是按一定规律进行变换。以初始化魔方坐标系变换为例（图6）。该过程表明该一维矩阵简单有效表明魔方相对坐标信息。其中操作R（2）和L（4）坐标面是旋转朝向至左手臂时的坐标变换。

魔方旋转面时，可以选择左手转面或者是右手转面。例如，2和4坐标面在相同的执行操作下可选择左手或者右手进行求解。1和5坐标面最短的执行方式是分别选择右手臂和左手臂去执行旋转面操作，然而也可以分别选择左手臂和右手臂去执行。不同执行选择将直接影响后续的求解执行步数。这里我们只考虑近期的执行效益，即1和5两面分别选择左手臂和右手臂产生多余执行步的方式直接不纳入考虑范围。对此，采用深度优先搜索的算法，对2和4坐标面左手转面还是右手转面进行全局规划，已达到执行时间最短的结果。当2和4坐标面为右手转面时，坐标变换存在如图7变换。

4 深度优先搜索优化模型建立

4.1 问题阐述

DFS算法是一种用于遍历或搜索树或图的算法，当一个问题的实现方式有许多种的时候可以实现选择方式的最优。采用了计算机递归的思想。单独采用DFS采用了暴力枚举的方式，回溯算法是类似枚举的搜索的尝试过程，当发现已经不满足求解条件就“回溯返回”，回溯带有剪枝算法，减去一些已经不满足要求的状态节点，从而在更少的状态节点中生成目标。考虑本文中的问题已经两种算法的优点，模型把问题转化为一个带权重的二叉树，寻找最短路径的问题。运动DFS+回溯算法在搜索最优模型中去除已经不满足条件的路径，以最短的时间，最少的计算量输出最优的结果。

算法步骤优化是对全局机械执行步所消耗时间的优化。前期的执行过程将影响后期是否要进行换面步骤，对所有面考虑“左撇子”和“右撇子”时，该问题则是极其复杂的，且由于实际过程中魔方执行编码基本在20步左右，对后续执行的长期影响不是特别明显。简化优化问题，除去在近期没有明显效益的执行，如1和5两坐标面分别选择左手臂和右手臂转面，3和0坐标面分别选择左手臂和右手臂转面产生多余执行步的方式直接不纳入考虑范围。只考虑对执行机械效益相同的进行DFS优化，如2和4坐标面可以左手转面或者右手转面，所以则是对二叉树模型进行深度优先搜索。

机械执行步分为手部旋转和气缸手指张合两部分组成，他们在不同硬件及算法条件下所占的执行时间有极大的差异。因此导致可能机械执行步最少的解法相对于机械执行步相对较多的，在硬件执行上时间更长。对具体机械执行设置权重，具体参数依据硬件设施决定。该问题进一步为机械执行步综合获取最优效益。

4.2 优化模型

建立一个带权重的二叉树模型。每一个分叉代表执行2和4坐标选择左手转面或者是右手转面。解决问題的标志为已经全部遍历完所有满足要求的节点，并且输出最优的执行效益。

动作分配：1）手指张开和闭合;2）手转90度;3）手转180度）。编码对应的执行过程都是2和4坐标左手转面或右手转面的编列组合。动作权重设定与实际硬件时间成正比，依据手指张合及手臂旋转时间占优状况设定权重如表2。

得到魔方执行编码，初始化最优权重和无穷大。进行算法搜索，遇分岔点1）先标志分叉点，保存当前状态，2）在从左手转面开始3）回到最近的保存点，消除标记4）从右边开始走。每走完一条路径更新最优的路径权重和，走完一步后进行权重累加，如果当前权重和已经大于保存的最优的权重和那么直接回到最近分叉点的右边继续搜索。直到没有保存的分叉点为止。模型阐述如图8。（这里接触面或对面是对于执行面为左手或者右手的接触面或对面）。

4.4 优化模型伪代码实现

输入： 魔方编码 cube_code = {（x1，y1），（x2，y2），...，（xm，ym）};

魔方编码的索引 index;

上一个分叉点指令长度 length.

过程： 函数CubeCodeOptimal（cube_code，index，length）递归方法

1：初始化add_weight_optimal无穷大，add_weight_current为0，初始化各个动作对应的权重

2：调用函数CubeCodeOptimal（cube_code，0，0）;

3：if index >= length_of（cube_code） 一条路径已经不能继续走了 then

4：    if add_weight_current < add_weight_optimal then

5：        add_weight_optimal = add_weight_current

6：        更新optimal_instruction为当前新的指令

7： return 回到上一个分叉点

8：    end if

9：end if

10：if add_weight_current >= add_weight_optimal 如果当前路径已经大于最优路径 then

11：    return 回到上一个分叉点

12：end if

13：if 当前面是左右手接触面或者对面 then

14：    current_instruction追加相应指令

15： add_weight_current进行加权

16： index += 1

17： 坐标进行相应变换

18： return CubeCodeOptimal（cube_code，index，length）

19：end if

20：else 当前面是两只手的非接触面和非对面 then

21： 暂存参数，先左手进行转面

22：    current_instruction追加相应指令

23： add_weight_current进行加权

24： index += 1

25： 坐标进行相应变换

26： return CubeCodeOptimal（cube_code，index，length）

27： 恢复相关参数进行右手转面

28：    current_instruction追加相应指令

29： add_weight_current进行加权

30： index += 1

31： 坐标进行相应变换

32： return CubeCodeOptimal（cube_code，index，length）

33：end if

输出： 最优解码指令 optimal_instruction.

4.4 实例验证

由于魔方求解问题复杂，每次获得的求解编码没有任何规律可言。此处，使用kociemba算法求解魔方，并选举了四组有代表性的执行编码进行分析具体如表3。

对以上执行编码进行机械执行步转换。转换的基本条件是优先当前的最短执行路径，其次针对2和4坐标面左手转面或右转面问题进行全局执行效益优化。未优化状况则是2和4坐标面全部为右手转面。同时，也求解出最多机械执行步进行对比。优化状况是DFS算法优化出的最短机械执行步结果。设置权重1-1-1，求解表3中编码获得机械执行步对比图9。从图中可以看出该DFS算法具有明显的优化效果。对比最长执行步和最短执行步，可知在双手臂求解魔方过程中，全局执行路径优化空间是极大的。

由于全局路径优化空间巨大，机械步执行时间效益不同，可能导致的最终执行效益存在差别。同样对表3中执行编码进行DFS优化并转换机械执行步。权重参数设定依据为表2，其表达三组不同机械执行步占优状况。其中权重1-1-1对应的权重和直接为其机械执行步数。对机械执行步数优化结果取前5，并求取权重和。图10中分析手指张合在时间上占优的权重和。可以发现最少的机械执行步在趋势上代表较优的执行效益，但不一定代表最优的执行效益。图10中分析手臂旋转时间占优的权重和。分析可得在手臂旋转时间占优时，则未表现出机械执行步数较多而执行效益较优的结果。综合分析可得，对于全局优化问题，还需要依据具体硬件执行不同机械步的时间效益来确定最优的执行方案。

5 结束语

该魔方机器人利用视觉提取魔方信息，采用一维坐标转换及检索方式描述魔方坐标变换，将魔方执行编码转化为相应机械执行步，并利用DFS搜索最短机械执行步。依据不同硬件条件下，不同机械执行步所占的时间优势不同，设定机械步权重，寻找一种最优的执行效益组合。最终充分优化了系统求解魔方的时间。

参考文献：

[1] Rathi G ， Goel S . Applications of Depth First Search： A Survey[J]. Paris， 2013.

[2] Bruce J ， Balch T ， Veloso M . Fast and Cheap Color Image Segmentation for Interactive Robots[C]// Proceedings. 2000 IEEE/RSJ International Conference on Intelligent Robots and Systems （IROS 2000） （Cat. No.00CH37113）. IEEE， 2002.

[3] C. Zieliński， Szynkiewicz W， Winiarski T， et al. Rubik's cube as a benchmark validating MRROC++ as an implementation tool for service robot control systems[J]. Industrial Robot， 2007， 34（5）：368-375（8）.

[4]魏金麗， 范鑫贺， 刘莲莲， 等. 基于深度优先遍历算法-回溯算法的公交网络限时免费换乘优化模型求解[J]. 科学技术与工程， 2017（10）：309-312.

[5] 李萍. 迪杰斯特拉算法的改进与实现[J].信息化建设，2016（2）.

[6] 贲可荣， 陈火旺. 计算机求解魔方算法[J].计算技术与自动化，1992（3）：31-37.

[7] 梁小龙. 解魔方算法的研究和系统实现[D].东北大学，2013.

[8] 李泽萱， 滕旭阳， 郑艺彬，等. 基于Arduino的两臂解魔方机器人——算法设计[J].电脑知识与技术， 2018，14（17）：248-250.

[9] 唐日成， 宋伟， 李泽萱，等.基于ARDUNO单片机的魔方机器人解决方案——机械变换控制[J]. 电脑知识与技术， 2018，14（17）：267-268.

[10]刘远法，周屹.基于Arduino单片机的解魔方机器人——控制部分[J].电脑知识与技术， 2016， 12（7）：171-173.

[11]熊晓松， 李朝朝. 基于Arduino的机器手臂控制[J]. 数字技术与应用， 2017（2）：3-3.

[12]高达. 基于STM32双臂魔方机器人的设计[J]. 电子产品世界， 2018， 25（11）：61-63.

[13]盛庆华， 杜永均， 罗飞， 等. 基于STM32机械臂解魔方算法研究[J]. 实验室研究与探索， 2017（4）.

【通联编辑：梁书】