基于DFS的二指双臂魔方机器人 崔俊文 刘自红 邓明洋 乐玉Summary：本文提出一种二指双臂的解魔方自动化系统，其可以自主完成魔方颜色提取、求解和还原过程首先利用双摄像头对魔方面进行色彩信息提取，编码后利用kociemba算法求解魔方，解码后依据自定义空间坐标，利用DFS-回溯算法规划机械执行步，并设置相应权重，全局优化双手臂求解步骤及时间在该算法下，该套系统可以快速求解魔方，并可以得到适应硬件执行的最优结果Key：魔方复原;视觉识别;坐标系构建与仿真;深度优先搜索：TP249 ：A：1009-3044（2019）24-0194-05开放科学（资源服务）标识码（OSID）：Two-finger Arm Cube Robot Based on DFSCUI 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下位机控制单元下位机解析机械执行步编码执行双手臂机构进行魔方还原流程图见图22 视觉识别为快速获取魔方色彩面信息，采用双摄像头对棱边进行提取色彩信息单个相机可获得魔方两面四边形色彩区域分割为左右两区域，并进行定轮廓框选针对四边区域进行仿射变换获得正视魔方面图像，校正后对各颜色块顶坐标色彩区域进行提取，如图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）示例机械执行步对应转换过程参考表13.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） 一条路径已经不能继续走了 then4： if add_weight_current < add_weight_optimal then5： add_weight_optimal = add_weight_current6： 更新optimal_instruction为当前新的指令7： return 回到上一个分叉点8： end if9：end if10：if add_weight_current >= add_w。