基于Kociemba算法的双臂解魔方机器人还原算法研究*

2021-10-25卢桂萍罗泽奇吴荣鑫陈永键康诗铄

机电工程技术 2021年9期

卢桂萍，程开，罗泽奇，吴荣鑫，陈永键，康诗铄

（北京理工大学珠海学院工业自动化学院，广东珠海519088）

0 引言

魔方作为极其具有人类智慧的玩具，在日常最为常见的玩法为竞速，解魔方机器人（Rubik′s Cube-Solving Robot,RCSR）的目的是让机器人稳定、快速地还原标准三阶魔方。标准三阶魔方作为经典的人类智力玩具，其还原过程代表着人类逻辑推理运算，三维空间想象等智力行为。双臂协作机器人作为机械模仿人类的一个里程碑，通过设计双臂解魔方机器人，能进一步让机器去模仿人类智慧的行为动作，对于制造更具有人类特征的机器人有着重要意义[1-2]。

机械臂作为应用最为广泛的高精度机器人，由于其可以代替人手执行大部分人工操作，被广泛用于工业自动化生产线等场合。通过设计开发解魔方机器人，实现对高精度机械臂的控制，并向工业领域应用拓展[3]。国内外的解魔方机器人结构多为六轴电机旋转，本文的研究对象采用双臂结构，同时在程序算法上，采用高效的Kociemba解魔方算法得出魔方还原步骤能逼近“上帝之数”（God′s number）——20，即魔方最少需要多少次的转动，才能确保无论什么样的颜色组合都能被复原。从而不断提高机器臂控制的精度、速度和可靠性[4]。

目前比较成熟的魔方机器人多为六轴中心式（如德国的Sub1Reloaded）以及底面翻滚式（如LEGO的EV3），然而前者需要对标准三阶魔方的中心块进行改造，后者由于机械结构设计上的不稳定因素解算成功率并不高。基于Kociemba算法的双臂解魔方机器人，更为贴合人类标准三阶魔方时的手部动作与结算策略，采用手指夹持的方式无需对标准三阶魔方的中心块进行改造，在正常运行情况下，在极具观赏性的同时，保证还原速度。机器人想要快速寻找到最优的还原步骤需要进行复杂的计算与推理，建立还原步骤简化规律，避免多余、重复的还原步骤；同时精准地还原，需要准确而快速的颜色识别、快速而稳定的转动操作和高效可靠的通讯模块。

1 基于Kociemba算法的双臂魔方机器人

1.1 机械结构

本文针对图1所示的双臂魔方机器人展开研究。如图2所示，在夹具上，采用薄型平行开闭型气动手爪，将两个气动手爪严格处于统一平面且保持相互之间成90°，采用碳纤维高压气瓶作为本双臂解魔方机器人的高压空气源。同时，由于显著改善速度提高后力矩会导致缺失和开环步进电机丢失步数的问题控制脉冲频率，将脉冲电信号转换为角位移，选择STM32 MCU与两相混合式步进电机。利用Altium Designer电路设计软件，绘制出所使用的控制主板的原理图与PCB板布线样图。

图1 双臂魔方机器人整体结构

图2 双臂魔方机器人手臂结构

1.2 机械臂运动模式

用户可通过解魔方机器人操作界面来手动控制该解魔方机器人手臂的动作。通过按钮“L顺”（左侧电机顺时针旋转）、“L逆”（左侧电机逆时针旋转）、“D顺”（右侧电机顺时针旋转）和“D逆”（右侧电机逆时针旋转）来进行电机旋转角度的微调，以及控制两个气缸夹爪的松开和夹紧[5]。

用户也可在该操作界面串口通信区的下方信息发送区写上指令，点击发送即可控制机器人。指令列表如图3所示。

图3 机器人控制指令列表

1.3 硬件调试与整机运行测试

通过上电运行测试后，还原标准三阶魔方的平均时间依据魔方打乱程度的不同为12～17 s。检验电机运动控制算法，使得电机能够保持足够力矩，快速达到高速，快速精准地止动，并且能使运动过程平滑，不产生大量突变，以减少运动惯性带来的魔方层与层之间的错位，使得机械臂能够进行短促平滑地高速转动。可以得出结论，该结构严格符合双臂魔方机器人的运动条件和运动方式，同时解决了显著改善速度提高后力矩会导致缺失和开环步进电机丢失步数的问题。

2 基于Kociemba算法的双臂解魔方机器人算法分析

2.1 Koeicmba算法

Kociemba算法的输出形式如下：首先，将魔方的6个面分别定义为U面、D面、L面、R面、F面和B面，分别对应上面（Up）、下面（Down）、左面（Left）、右面（Right）、前面（Front）和后面（Back）。U代表顺时针旋转上面90°，U2代表顺时针（或逆时针）旋转上面180°，U′代表逆时针旋转上面90°，其余5面同理。一段像“U D R′D2”这样的表示魔方旋转的序列，称之为一个策略（maneuver）。Kociemba算法将对魔方颜色信息的输入进行计算，然后计算输出一个还原策略。

需要注意，Kociemba算法的运算量较大，因此计算解法通常需要花费较长时间。为了提高解魔方机器人的效率，一般会在算法运算一定时间后得到较优解后就停止运算[6-8]。另外，为了统一表示解法，本文将顺时针旋转90°的操作用“+”表示，逆时针旋转90°的操作用“-”表示，旋转180°的操作用“2”表示，如有一段来自于Kociemba算法输出的策略“UDR′D2”，在本文，将会被表示为“U+D+R-D2”。

2.2 Kociemba算法的转换算法

由于本设计是基于双臂解魔方机器人的算法，所以需要进一步将六面旋转信息转换成两面旋转信息的算法称为“6-2转换算法”。该转换能将所有的操作转变为双臂电机的旋转操作和气动夹具的夹持和松开动作。本文所研究设计的双臂解魔方机器人的双臂分别对应了魔方的左面和下面，即L面和D面。因此，转换算法的输出将只包含了L面和D面的操作，不能包含其他面的操作。如图4所示。

图4 适用于双臂解魔方机器人的Kociemba算法的转换算法

2.3 坐标转换算法——A算法与A步骤

假设原坐标系顺序是Coord[6]={U,D,L,R,F,B}，在进行了AL+操作后，即解魔方机器人夹持魔方L面整体顺时针旋转90°，将会变成AL+（Coord[6]）={B,F,L,R,U,D}，观察可以发现，原坐标系的U面变为B面，B面变为D面，D面变为F面，F面变为U面，这个转换的过程在本文称为“坐标系转换算法”。

图5 所示为转换算法表。Ux、Dx、Lx、Rx、Fx和Bx分别代表了所截取的已完成坐标系转换的两步骤中的第一步，而Uy、Dy、Ly、Ry、Fy和By分别代表了第二步。以“A”字符开头的操作代表着魔方的整体旋转，而不是面旋转，“”字符意味着该操作是空。需要注意的是，表格中“->（??）”表达式意味需要额外往后多截取一个操作，这种特殊情况通常出现在需要旋转的面恰好已经被双臂所夹持，被夹持的一面不需要做额外的坐标转换，因此需要再多往后读取一个步骤。可以发现，图中，同一对操作有多种转换方法，例如“Ux Fy”，可以被转换成“AL2AD+DxLy”、“AL+AD-LxDy”和“AD-AL2DxLy”中的一种，通常为了尽可能简化步骤，如果上一对操作转换后的最后一个操作是L面旋转（或D面旋转）的，那么，下一对操作在转换时优先选择AL旋转（或者DL旋转）的。

图5 Kociemba算法转换算法表

为了进一步说明图5的操作，下面将给出示例：假设截取到的原算法的输出策略为“U+L-”，那么第一个步骤可表示为“Ux”，其中的“x”等于“+”，第二个步骤可表示为“Ly”，其中的“y”等于“-”。通过查表可得，在进行了转换后，原策略将变为“AL2DxLy”，代入x和y的值，即为“AL2D+L-”，这表示了“L侧手臂先夹住整个魔方整体旋转180°，然后再顺时针旋转魔方的当前坐标系的D面90°，最后再逆时针旋转魔方的当前坐标系的L面90°”。旋转过程如图6所示。

图6 “AL2D+L-”旋转过程（从左往右）

A步骤：在将Kociemba算法的原始输出策了统略通过A算法的转换后，其输出将只包含以下几个操作，分别为：L+、L2、L-、D+、D2、D-、AL+、AL2、AL-、AD+、AD2和AD-。不是A开头的操作和原Kociemba算法输出策略的含义一致，代表了旋转某一面某个角度的操作。

2.4 转换为机械臂动作——M-C算法与M-C步骤

C算法：M-C算法所做的事情是将A步骤，即L+、L2、L-、D+、D2、D-、AL+、AL2、AL-、AD+、AD2和AD-这些代表魔方本身被旋转的动作步骤转换为电机和夹爪的动作，这些动作分别为：LM+、LM2、LM-、DM+、DM2、DM-、LC+、LC-、DC+和DC-。

带“M”字符的操作表示了电机动作，例如“LM+”，其意义为“L侧电机顺时针旋转90°”。而带“C”字符的操作表示了夹爪动作，例如“LC+”，其意义为“L侧夹爪夹紧”；而“LC-”，表示“L侧夹爪松开”。在一串的M-C步骤中，若X代表了D侧，则Y将代表L侧，反之亦然。为了尽可能简化步骤，如果上一对操作转换后的最后一个操作是L面旋转（或D面旋转）的，那么下一对操作在转换时优先选择AL旋转（或者DL旋转）。如图7所示。图中，表达式中的“X”和“Y”的含义和转化为机械臂动作——M-C算法和M-C步骤中的含义一致，“1”代表A步骤中的“+”或“-”操作，“…”仅表示A步骤中未被截取的地方，“!”表示A步骤中此处不允许出现的操作。如SP3“…AX2 Y1!AY1…”中的“Y1!AY1”表示A步骤中“Y1”后面不能是“AY1”，否则构不成SP3特殊情况。又如SP4“…!X1 AX1 Y1!AY1…”中的“!X1 AX1”表示A步骤中“AX1”前面不能是“X1”，否则构不成SP4特殊情况。在图中，对于每一种特殊情况，枚举出了其输入、原始输出（直接查图7的输出结果）和简化后的输出。最终再将整张表的输入、输出进行抽象，得到了图中右侧三列的表达式，即输入表达式、输出表达式以及备注。为了方便讨论，在这张表中，用“i”和“j”字符来代替输入表达式中的旋转动作，即“+”、“-”或“2”。相反地，用“I”和“J”字符来代替输入表达式中与之相反的旋转动作，即若“i”表示“+”，则“I”表示“-”。