🎇 🙀 👖 基于FAC的魔方机器 🥗 ⁉️ 🌓

不久前，我们与Wilbert Swinkels一起完成了一台收集魔方的机器。他们在Raspberry Pi官方博客上写了关于我们的信息，我们收到了很多好评。然而，在俄罗斯网络中，该项目以某种方式没有引起注意。因此，我决定通过在此处发布原始帖子的翻译版和增强版来纠正此遗漏。

在削减之后，我们将主要讨论该机器的软件部分，而机械部分可以在项目的官方页面上找到（是的，我们知道这有点“老派”了）

TL; DR

对于不耐烦的人，有几个链接：

介绍

一切始于今年5月，我偶然遇到了Wilbert Swinkels。当我看到他的作品时，我感到非常震惊：从小到大，每种机制都可以安全地称为艺术品。而且，您越仔细看他们的设备，就越会被他们的美丽所吸引。

当然，当威尔伯特邀请我帮助他使用魔方组装机时，我毫不犹豫地动了一下，尤其是因为那时我已经发现了对彩色立方体的热情。那时，他已经在机器上工作了4（！）年以上，但是软件部分仍需编写。

我没有为Raspberry Pi和Arduino进行编程的经验，但是总的来说，这项任务对我来说似乎很简单。当然，我错了:)

硬件

机器本身是使用模块化FAC系统构建的。这有点像苏联设计师，但其创建目的是为原型建立严肃而复杂的机制。在上世纪下半叶，它在飞利浦以及其他公司和大学的实验室中得到了非常积极的使用。

当我遇到威尔伯特时，他已经尝试过两次“复兴”汽车。两次，阿姆斯特丹大学的学生都处理了这个案件，不幸的是，两次尝试都失败了，这两次他们都对该项目失去了兴趣。尽管其中一个结果是机器无法收集立方体（将您的手举到此处认识自己的人），但其中一位甚至为该主题的学士学位辩护。

微控制器

首先，我们决定使用Raspberry Pi代替Arduino。这主要是由于用于解决Rubik's Cube的“智能”算法需要大量的内存和处理器功能。在先前的尝试中，使用了原始的三层算法，但是这次我们决定使用Kotsemba算法。另外，我并不是真的想用C编写所有内容（尽管部分必须这样做）。

在Raspberry Pi的标准版本中，我们没有足够的引脚来连接所有可用的电机，因此我们订购了开发套件。顺便说一句，我强烈建议：不仅更多的引脚，而且在我看来，它们之间的逻辑距离更大。此外，该板有两个用于相机的连接器，而不是一个。

扫描仪的第一个版本

要读取多维数据集的初始配置，需要使用扫描设备。这个想法很简单：我们依次用三个LED照明立方体的表面：红色，绿色和蓝色。每次我们使用光敏电阻测量反射光。从理论上讲，我们应该获得可用于识别正方形颜色的RGB值。从以前的程序员那里，我们仍然有Arduino的概念验证代码，看起来甚至可以在某些条件下使用。

我们遇到的第一个问题是电压不匹配。如您所知，Arduino引脚上的逻辑单元为5V，而Raspberry Pi为3.3V。幸运的是，尽管更改了脉冲幅度，但我们使用的步进电机驱动器控制器仍继续工作。

事实证明，Raspberry Pi没有模拟输入更为重要。因此，Raspberry无法简单地获取并读取光敏电阻上的电压。这对于至少一次遇到此问题的人来说可能是显而易见的，但是起初我什至没有考虑过。在网上寻找解决方案时，我们偶然发现了这篇文章。简而言之，我们在电路中添加一个电容器，并测量其从零充电到逻辑单元的时间（我们可以使用数字引脚进行检测）。充电时间将与光敏电阻的电阻成正比，因此我们可以判断光量。

这种方法不仅非常不可靠（在带有大量后台进程的Linux上的Python Python脚本中花费时间是一件令人不快的事情），而且它也不会长久。为了消除读数中的随机偏差，我们必须阅读几次，排除异常值，然后对剩余值取平均值。但是，我们仍然设法使该扫描仪正常工作：

扫描仪的第二个（最终）版本

电容扫描仪工作得很好，但是非常慢。扫描整个Rubik's Cube大约花了两分钟，到扫描完成时，观众已经失去了所有兴趣。因此，我们决定返回Arduino，并购买了一个专门用于控制扫描仪的小型Arduino Mini。

事实证明，使用Raspberry Pi与Arduino成为朋友非常简单：两条线，它们之间的电压转换器和voila-我们有一个串行接口。而且，如果您将最简单的Min协议放在首位，那么对该业务进行编程是一种乐趣。

我将所有扫描仪控制逻辑转移到了Arduino。扫描速度大大提高。得益于模拟输入，我们可以直接从光敏电阻读取电压，这些值非常准确。另外，由于Arduino直接安装在扫描仪上，因此从扫描仪到Raspberry Pi的接线要少得多！

生成算法

从数学的角度组装魔方是一项相当艰巨的任务。当然，我们在谈论寻找最佳解决方案，而不是“一些”。当我发现神的数目（解决任意立方体所需的移动数的确切下限）仅在2010年发现时，我感到惊讶。

在这个项目中，我们希望减少计算解决方案和组装所需的总时间，因此既没有一种简单的三层算法（可以快速运行，但可以使解决方案长出一百步），也没有一种最佳算法（解决方案很短，但是在Raspberry上进行渲染的过程） Pi会永远拿走）。结果，我们选择了宏伟的“两阶段”算法德国数学家Herbert Kociemba。他能够做出次优的决定（平均20步），同时保持在合理的时间内。

在作者的网站上，您可以找到Java算法的实现。我要做的第一件事就是将这段代码翻译成Python。这一点都不困难，因为大多数程序都是数学运算和选项枚举。但是，我没有考虑到该算法确实需要大量资源。在我的笔记本电脑上，在首次启动时找到解决方案花费了超过一分钟（！）。

在pypy下在启用JIT的情况下，该解决方案在笔记本电脑上花费了1秒钟，但是在Raspberry Pi上仍然花费了大约一分钟。经过几次尝试以加快Python程序的工作速度（numpy，多处理），我决定将算法重写为C。尽管如此，该解决方案现在需要1-2秒，甚至是Raspberry。

我在GitHub上发布了算法的两种实现。

机器控制

下一步是编写一个程序来控制机械部分：考虑齿轮比和机构限制来移动电动机（例如，仅当底部处于某个位置时才可以旋转侧支架，否则会产生干扰）。

除了主程序外，我还制作了一个交互式外壳程序，在调试时为我节省了很多时间。通常，这部分在编程方面并不罕见。为了调试扫描，我将结果生成为图片。

扫描和色彩识别

到目前为止，一切都很有趣，但并不困难。工作开始两周后，机器已经可以从给定状态收集多维数据集。剩下的只是学习如何使用扫描仪读取多维数据集的初始配置。我们已经有一个针对Arduino的“有效”程序，因此我们并不感到意外。但是，该项目的这一部分最困难，又花了我们两个月的时间。

光敏电阻指示

就像我在上面写的，我们从带电容器的扫描器电路开始。这种方法的错误非常可怕，因此要获得可用的值，我必须进行几次测量，然后再消除排放。之后，我们得到了类似的结果（这是在黑暗的房间中扫描组装好的立方体的结果）：

如您所见，结果远非理想。首先，同一颜色的值在不同位置不同，因为光敏电阻和LED沿不同的方向``看''。其次，某些颜色在颜色空间中彼此非常接近，有时值的范围重叠（例如，橙色和红色有时给出相同的值）。最后，读数非常依赖于外部照明。

从视觉上看，电容器扫描仪的误差可以在下图中看到（一般来说，这里有一个交互式版本）：

回头看，我想知道我们如何设法使扫描得到这样的结果，尽管这需要仔细，棘手地校准有问题的值会降低一点。

正如我所说，电容器扫描仪可以工作，但是速度很慢。当我们用内置的Arduino将它替换为另一个时，读数变得更加“拥挤”（交互式版本在此处）：

读数的校准和聚类

现在我们有了来自光敏电阻的原始RGB读数，我们必须自己识别颜色，以便将立方体配置输入到构建算法中。此处立即提出了两种不同的方法：颜色间隔的使用和聚类算法。

第一种方法是``正面''解决方案：可以通过实验确定立方体每一侧的值的间隔（实际上是将颜色空间划分为不相交的区域），然后根据属于某个间隔的值简单地组合这些值。在这种情况下，应分别考虑立方体边缘上9个可能的位置中的每个位置。这种方法很容易编程，但是有两个明显的缺点。首先，它将我们绑定到特定的颜色，这意味着我们只能收集严格定义的魔方。其次，可能值的间隔在很大程度上取决于外部照明。此外，我们发现，取决于环境光，相同的读数可能对应于不同的颜色。

第二种方法需要对值进行初步校准，以使相同的颜色在立方体边缘的所有9个位置给出相同的结果。在这种情况下，我们可以使用聚类算法将值组合成6组。同时，只要是不同的颜色，立方体所用的颜色就无关紧要。不幸的是，由于聚类算法的概率性质，该方法也必须被“拒绝”：它们可以产生“良好”的结果，但不能保证其准确性。

两种方法各有利弊，因此我们在两者之间使用了一些方法：

首先，我们对扫描仪读数进行人为校准，以将值归一化。系数是通过实验获得的。
将生成的RGB值转换为HSV
, S ()
, .

即使使用了良好的聚类算法，由于环境条件，扫描通常也会失败。在黑暗的房间中校准的算法无法在白天条件下完成任务，反之亦然。此外，如果外部照明非常明亮（直射阳光），则扫描仪通常会停止工作，因为LED的影响几乎不明显。威尔伯特做了非常艰苦的工作，将扫描仪与环境光隔离开。我必须经历3次迭代：每次我们认为就足够了，并且每次我们都发现另一个缺口，外部照明通过该缺口落在光敏电阻上。

结论

这个项目的工作非常令人兴奋。看着汽车栩栩如生，真是太好了，看到汽车如何运转，证明自己的一切努力特别酷。但是，这不能与我们在此过程中设法获得的知识存储相提并论。我无法想象，我将不得不学习大量有关电子学，力学，代数甚至是数学统计的材料，并一路走来找到十二个有用的实用程序和库。这就是为什么我很高兴有机会从事这个项目的原因。

尽管如此，这辆车只是一个原型。我们没有设定打破速度记录的目标，当然我们也没有意识到机械零件的全部潜力。但是我们一定会在已经开始工作的机器的下一版本中尝试这样做。在那里，我们将使用相机进行扫描，并且操纵器的设计已经发生了重大变化。当然，如果您有任何疑问，建议或技巧，我会很高兴在评论中听到他们的声音。

基于FAC的魔方机器