迷宫解算机器人，使用人工智能

应用和在线服务

	Arduino IDE
	MIT App Inventor 2

关于这个项目

简介

本教程是根据我的上一个项目开发的：Line Follower Robot - PID Control - Android Setup。一旦你拥有一个具有跟随能力的机器人，下一个自然的步骤就是给他一定程度的智能。所以，我们亲爱的“机器人雷克斯”现在将尝试寻找如何以最短和最快的方式逃离“迷宫”（顺便说一下，他讨厌牛头怪。

首先，Maze 和有什么区别？ 和迷宫 ?据http://www.labyrinthos.net介绍，在英语世界里，通常认为一个设计要成为一个迷宫，必须在路径上有选择。显然，这将包括娱乐公园和旅游景点中的许多现代设施，包括我们这里的 2D 迷宫。普遍的共识还表明，迷宫有一个途径，可以无情地从入口通向目标，尽管通常是最复杂和曲折的路线。

大多数迷宫，无论它们的设计看起来多么复杂，基本上都是由一堵连续的墙和许多交叉点和分支形成的。如果迷宫目标周围的墙壁在入口处与迷宫的周边相连，则始终可以通过保持一只手与墙壁接触来解决迷宫，无论可能涉及多少弯路。那些“简单”的迷宫被正确地称为“Simply-connected " 或 "完美迷宫 " 或者换句话说，包含没有循环 .

回到我们的项目，它将被分成两部分（或“passes "):

• （第一次通过） :机器人从“未知的完美迷宫 ”。不管你把它放在迷宫里面的什么地方，它都会找到一个“solution ".

• （第二次通过） :一旦机器人找到一个可能的迷宫解决方案，它应该优化它的解决方案，找到“从开始到结束的最短路径 ".

下面的视频将展示雷克斯寻找出路的例子。机器人第一次探索迷宫，当然会浪费很多时间“thinking ”关于在任何路口做什么。测试无数的可能性，会走几条错误的道路和死胡同，迫使他走更长的路并执行不必要的“U-Turns ”。在这个“第一次通过” ，机器人会积累经验，“做笔记 “关于不同的交叉点和消除坏分支。在它的“2nd Pass ”，机器人直接快速地走到最后，没有任何错误或疑问。在本教程中，我们将详细探讨如何做到这一点：

第 1 步： 物料清单

材料清单与 Line Follower Robot 使用的材料清单基本相同，除了我添加了 2 个额外的传感器以提高检测左和右交叉点的准确性：

最终的机器人还是很便宜的（大约 85.00 美元）：

正文（您可以根据自己的需要或可用材料进行调整）：

• 2 X 木方格 (80X80mm)

• 3 X Binder 剪辑

• 2 X 木轮（直径：50mm）

• 1 个球型脚轮

• 9 X 弹力带

• 3M 命令框条

• 用于传感器固定的塑料接头

• 面包板和接线

• 2 X 4X 镍氢电池组（每组 5V）

• 2 X SM-S4303R 连续旋转 360 度塑料伺服

• Arduino Nano

• HC-06 蓝牙模块

• 5 个 X 线传感器（TCRT5000 4CH 红外线轨跟随器传感器模块 + 1 个独立的轨道传感器）

• 2 X ZX03（基于 TCRT5000）反射式红外传感器（模拟输出）

• 1 个 LED

• 1 个按钮

注意 ：我将上面的第 7 项与模拟输出一起使用，因为我没有像第 6 项那样具有数字输出的手头传感器。如果可能，理想的情况是让所有传感器都相同。我还测试了仅保留原始 5 个传感器的项目。它会起作用，但需要在发现交叉点时进行更敏感的调整。

第二步：身体的变化

移除原来的 5 个线性跟随传感器并修复新的“Far LEFT” 和“最右边 " 在支撑塑料条的每个极端都有反射传感器。建议尽可能排列 7 个传感器。

第 3 步：安装和测试新传感器

现在 7 个传感器的新阵列 ，安装方式是原来的5个专用于PID控制（和检测“全线”，稍后解释）和2个新的，专用于LEFT和RIGHT交叉点检测。

快速回顾一下，让我们记住 5 个原始“数字”传感器的工作原理：

如果一个传感器相对于黑线居中，则只有该特定传感器会产生 HIGH。另一方面，应计算传感器之间的间距，以允许 2 个传感器同时覆盖黑线的整个宽度，同时在两个传感器上产生 HIGH 信号。

2 个新的“模拟”传感器的工作原理：

如果其中一个传感器相对于黑线居中，则输出将是一个模拟值，通常在 Arduino ADC 处产生低于“100”的输出（请记住，ADC 产生的输出范围为 0 到 1023）。对于较浅的表面，输出值会更高（例如，我在白纸上测试了 500 到 600）。该值必须在不同的光线和表面材料情况下进行测试，以定义要在您的情况下使用的正确 THRESHOLD 常数（请参见此处的图片）。

查看 Arduino 代码，每个传感器都将定义一个特定的名称（考虑到更靠左的原始 Line Follow Sensor 必须分配标签“0 "):

const int lineFollowSensor0 =12; //使用数字输入const int lineFollowSensor1 =18; //使用模拟引脚A4作为数字输入const int lineFollowSensor2 =17; //使用模拟引脚A3作为数字输入const int lineFollowSensor3 =16; //使用模拟引脚A2作为数字输入const int lineFollowSensor4 =19; //使用模拟引脚A5作为数字输入const int farRightSensorPin =0; //模拟引脚A0const int farLeftSensorPin =1; //模拟引脚A1 

请记住，跟随一行时可能的 5 个原始传感器阵列输出是：

1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 1 1 0 0 0 1 0 0 0 0 

加上 2 个新的，它们可能的输出是：

• 远左传感器：模拟输出大于或小于阈值

• 远右传感器：模拟输出大于或小于阈值

为了存储每个传感器的值，为原始 5 个数字传感器创建了一个数组变量：

int LFSensor[5]={0, 0, 0, 0, 0}; 

以及 2 个新模拟传感器的两个整数变量：

int farRightSensor =0;int farLeftSensor =0; 

数组和变量的每个位置都会随着每个传感器的输出而不断更新：

LFSensor[0] =digitalRead(lineFollowSensor0);LFSensor[1] =digitalRead(lineFollowSensor1);LFSensor[2] =digitalRead(lineFollowSensor2);LFSensor[3] =digitalRead(lineFollowSensor3);LFSensor[4] =digitalRead(lineFollowSensor4);farRightSensor =analogRead(farRightSensorPin);farLeftSensor =analogRead(farLeftSensorPin); 

拥有 5 个传感器，如 Follower Line Robot 项目中所见，允许生成“误差变量”，这将有助于控制机器人在线路上的位置。此外，如果机器人跟随一条线，一个名为“mode”的变量将用于定义 , 在连续线上 , 一个交叉路口 或无线 根本。

这个变量“mode " 也将与 "Far LEFT/RIGHT 一起使用 " 传感器。为了表示，让我们考虑具有 3 种可能状态的最左侧和最右侧传感器：

• H（高于阈值），

• L（小于阈值）和

• X（无关）。

对于数字输出，通常是 0、1，我们还将引入 X:

• H 0 X X X X L ==> 模式 =RIGHT_TURN;错误 =0; （参见上图中的示例）

• L X X X X 0 H ==> 模式 =LEFT_TURN;错误 =0;

• X 0 0 0 0 0 X ==> 模式 =NO_LINE；错误 =0;

• H 0 0 0 0 1 H ==> 模式 =FOLLOWING_LINE;错误 =4;

• H 0 0 0 1 1 H ==> 模式 =FOLLOWING_LINE;错误 =3;

• H 0 0 0 1 0 H ==> 模式 =FOLLOWING_LINE;错误 =2;

• H 0 0 1 1 0 H ==> 模式 =FOLLOWING_LINE;错误 =1;

• H 0 0 1 0 0 H ==> 模式 =FOLLOWING_LINE;错误 =0;

• H 0 1 1 0 0 H ==> 模式 =FOLLOWING_LINE;错误 =-1;

• H 0 1 0 0 0 H ==> 模式 =FOLLOWING_LINE;错误 =-2

• H 1 1 0 0 0 H ==> 模式 =FOLLOWING_LINE;错误 =-3;

• H 1 0 0 0 0 H ==> 模式 =FOLLOWING_LINE;错误 =-4;

• X 1 1 1 1 1 X ==> 模式 =CONT_LINE;错误 =0;

所以，在函数中实现上述逻辑：

void readLFSsensors() 

将返回变量“mode " 和 "错误 " 将在程序逻辑中使用。在进行项目之前测试传感器的逻辑很重要。代码中包含波纹管函数，可用于测试目的：

void testSensorLogic(void) { Serial.print (farLeftSensor); Serial.print (" <==左右==> "); Serial.print (farRightSensor); Serial.print("模式："); Serial.print（模式）； Serial.print（“错误：”）； Serial.println(错误);} 

第 4 步：解决迷宫 - 左手法则

正如介绍中所讨论的，大多数迷宫无论其设计看起来多么复杂，基本上都是由一堵连续的墙和许多连接点和分支形成的。如果迷宫目标周围的墙壁在入口处与迷宫的周边相连，则始终可以通过保持一只手与墙壁接触来解决迷宫，无论可能涉及多少弯路。这些“简单”的迷宫被正确地称为“Simply-connected .”

在维基百科上搜索，我们了解到：

简而言之，左手法则 可以这样描述：

在每个十字路口和整个迷宫中，让你的左手接触你左边的墙壁。

• 将左手放在墙上。

• 开始往前走

• 最终，您将到达迷宫的尽头。你可能不会走最短、最直接的路，但你会到达那里。

所以，这里的关键是识别交叉点 ，根据上述规则定义要采取的课程。具体在我们这种2D迷宫中，我们可以找到8种不同类型的交叉点（见上图）：

看图，我们可以知道在路口可能的动作是：

1. 在“十字架 ":

• 向左走，或

• 向右转，或

• 直截了当

2. 在“T ”：

• 向左走，或

• 向右转

3. 在“只有权利 ”：

• 向右转

4. 在“仅左 ”：

• 向左走

5. 在“直行或向左 ”：

• 向左走，或

• 直截了当

6. 在“直或右 ”：

• 向右转，或

• 直截了当

7. 在“死胡同 ”：

• 回去（“掉头”）

8. 在“迷宫尽头 ”：

• 停止

但是，应用“左手规则”，每个动作将减少到一个选项：

• 在“十字路口”：向左走

• 在“T”处：向左转

• 在“只靠右边”：向右移动

• 在“仅左”处：向左转

• 在“直行或向左”处：向左走

• 在“直或右”：直行

• 在“死胡同”：回去（“掉头”）

• 在“迷宫尽头”：停止

我们就快到了！ “冷静点！”

当机器人到达“死胡同”或“迷宫尽头”时，很容易识别它们，因为不存在模棱两可的情况（我们已经在 Line Follower Robot 上实现了这些动作，还记得吗？）。例如，问题是当机器人找到“LINE”时，因为一条线可以是“Cross”（1）或“T”（2）。此外，当它到达“左转或右转”时，可以是简单的转弯（选项 3 或 4）或直行的选项（5 或 6）。为了准确地发现机器人是什么类型的交叉路口，必须采取额外的步骤：机器人必须“多跑一英寸”，然后看看接下来会发生什么（例如，请参见上面的第二张图片）。

因此，就流程而言，可能的操作现在可以描述为：

1. 在“死胡同”：

• 回去（“掉头”）

2. 在“LINE”处：多跑一英寸

• 如果有一条线：它是一个“十字”==>转到左边

• 如果没有线：它是一个“T” ==>转到左边

• 如果还有另一行：它是“迷宫尽头”==>停止

3. 在“右转”处：多跑一英寸

• 如果有一条线：它是直的或右的==>直行

• 如果没有线：它是一个 Right Only ==> Go to RIGHT

4. 在“左转”处：多跑一英寸

• 如果有一条线：它是直线或左==>转到左

• 如果没有一行：它是一个LEFT Only ==> Go to LEFT

请注意，实际上，如果是“LEFT TURN”，您可以跳过测试，因为无论如何您都会向左走。只是为了清楚起见，我让解释变得更通用。在实际代码中，我将跳过此测试。上面的第三张图是我实验室地板上的一个非常简单的迷宫，用于测试目的。

第 5 步：在 Arduino 代码中实现“左手上墙”算法

一旦我们有了 readLFSsensors() 函数修改为包括额外的 2 个传感器，我们可以重写循环函数来运行算法，如上一步所述：

void loop(){ readLFSsensors(); switch (mode) { case NO_LINE:motorStop(); goAndTurn (左, 180);休息;案例 CONT_LINE:runExtraInch(); readLFSsensors(); if (mode ==CONT_LINE) mazeEnd();否则 goAndTurn (LEFT, 90); // 或者它是一个“T”或“Cross”）。在这两种情况下，转到 LEFT 休息； case RIGHT_TURN:runExtraInch(); readLFSsensors(); if (mode ==NO_LINE) goAndTurn (RIGHT, 90);休息; case LEFT_TURN:goAndTurn (LEFT, 90);休息;案例FOLLOWING_LINE：followLine();休息; }} 

一些新功能出现在这里：

• followingLine() 与跟随线机器人相同，如果它只跟随一条线，它必须calculatePID() <代码>; 并根据 PID 值控制电机：motorPIDcontrol();

• runExtraInch(): 将机器人向前推一点。在您命令电机停止之前，机器人将运行多少将取决于您在延迟功能中使用的时间。

void runExtraInch(void){ motorPIDcontrol();延迟（额外英寸）； motorStop();} 

• goAndTurn（方向、角度）： 这个特殊功能很重要，因为一旦你意识到你所在的交叉路口类型，你就无法转动机器人。请记住，我们设计了一个差分机器人，在转弯时，它“绕着它的轴转动”，因此，要移动 90o 并连续沿线移动，轮子的中心必须与相交中心对齐。一旦传感器线位于其斧头之前，您必须向前运行机器人以对齐它们。时间常数adjGoAndTurn 必须根据 ax 和传感器线之间的距离进行调整 ("d ")、轮子的速度和尺寸（参见上图说明）。

void goAndTurn(int direction, int degree){ motorPIDcontrol();延迟（adjGoAndTurn）； motorTurn（方向，度数）；} 

此时，机器人其实是在“解迷宫”！你刚刚完成了“第一次通过”。不管你在迷宫中从哪里开始，你总会到达终点。

波纹管，项目这一阶段的测试：

第 6 步：存储路径

让我们考虑上图所示的示例。在选定的起点，机器人会在到达迷宫尽头前找到 15 个路口：

• 左 (L)

• 返回 (B)

• 左 (L)

• 左 (L)

• 左 (L)

• 返回 (B)

• 直（S）

• 返回 (B)

• 左 (L)

• 左 (L)

• 返回 (B)

• 直（S）

• 左 (L)

• 左 (L)

• 结束

在这些交叉点中的任何一个中必须做的是保存每个动作完全按照它发生的顺序完成。为此，让我们创建一个新变量（数组）来存储机器人所走的路径：

char path[100] =" "; 

我们还必须创建 2 个与数组一起使用的索引变量：

unsigned char pathLength =0; // pathint pathIndex =0 的长度； // 用于到达特定的数组元素。 

所以，如果我们运行图中所示的例子，我们将以：

path =[LBLLLBSBLLBSLL]and pathLengh =14 

第七步：简化（优化）路径

让我们回到我们的例子。查看第一组路口，我们意识到第一个左分支实际上是一个“死胡同”，因此，如果机器人而不是“左后左”只在第一个路口直行，需要很多能量时间会被节省！换句话说，序列“LBL”实际上与“S”相同。这正是优化完整路径的方式。如果您分析使用“U 形转弯”的所有可能性，则可以将出现此“U 形转弯”（“B”）（“xBx”）的 3 个交叉点的集合减少到只有一个。

上面只是一个例子，下面你可以找到完整的可能性列表（试试看）：

• LBR =B

• LBS =R

• RBL =B

• SBL =R

• SBS =B

• LBL =S

以完整路径或我们的示例，我们可以减少它：

path =[LBLLLBSBLLBSLL] ==> LBL =Spath =[SLLBSBLLBSLL] ==> LBS =Rpath =[SLRBLLB​​SLL] ==> RBL =Bpath =[SLBLBSLL] ==> LBL =Spath =[SSBSLL ] ==> SBS =Bpath =[SBLL] ==> SBL =Rpath =[RL] 

惊人！看这个例子很明显，如果机器人在第一个路口向右走，然后向左走，它将以最短的路径到达迷宫尽头！

迷宫求解器的第一条路径总代码将合并在函数mazeSolve()中 .该函数实际上是之前使用的 loop() 函数，但结合了所有存储和路径优化的步骤。当第一条路径结束时，path[] 数组将具有优化的路径。引入了一个新变量：

unsigned int status =0; // 求解 =0;到达迷宫尽头 =1 

在 First Path 函数下方：

void mazeSolve(void){ while (!status) { readLFSsensors(); switch (mode) { case NO_LINE:motorStop(); goAndTurn (左, 180); recIntersection('B');休息;案例 CONT_LINE:runExtraInch(); readLFSsensors();如果（模式！=CONT_LINE）{goAndTurn（左，90）； recIntersection('L');} // 或者它是一个“T”或“Cross”）。在这两种情况下，转到 LEFT else mazeEnd();休息; case RIGHT_TURN:runExtraInch(); readLFSsensors(); if (mode ==NO_LINE) {goAndTurn (RIGHT, 90); recIntersection('R');} else recIntersection('S');休息; case LEFT_TURN:goAndTurn (LEFT, 90); recIntersection('L');休息;案例FOLLOWING_LINE：followLine();休息; } }}  

这里引入了一个新函数：recIntersection（方向）。 此函数将用于存储交集并调用另一个函数 simplifyPath() , 这将减少我们之前看到的涉及“掉头”的 3 个交叉路口组。

void recIntersection(char direction){ path[pathLength] =direction; // 将交集存储在路径变量中。路径长度++；简化路径(); // 简化学习路径。} 

simplifyPath( ) 功能是给 Patrick McCabe 的路径 Solving Code（详情请访问 https://patrickmccabemakes.com）！ Path simplification 的策略是每当我们遇到一个序列 xBx 时，我们可以通过切掉死胡同来简化它。例如，LBL ==> S 正如我们在示例中看到的那样。

void simplePath(){ // 仅当倒数第二个转弯是“B”时才简化路径 if(pathLength <3 || path[pathLength-2] !='B') return;整数总角度 =0;国际我; for(i=1;i<=3;i++) { switch(path[pathLength-i]) { case 'R':totalAngle +=90;休息; case 'L':totalAngle +=270;休息;案例'B'：总角度+=180；休息; } } // 获取角度为 0 到 360 度之间的数字。总角度 =总角度 % 360; // 用一个回合替换所有这些回合。 switch(totalAngle) { case 0:path[pathLength - 3] ='S';休息;案例 90：路径[路径长度 - 3] ='R';休息; case 180:path[pathLength - 3] ='B';休息;案例270：路径[路径长度 - 3] ='L';休息; } // 路径现在缩短了两步。路径长度 -=2; }  

第 8 步：第二关：尽快解决迷宫！

主程序：loop() 就是这么简单：

void loop() { ledBlink(1); readLFSsensors();迷宫解决（）； // 第一遍解迷宫 ledBlink(2); while (digitalRead(buttonPin) { } pathIndex =0; status =0; mazeOptimization(); // 第二遍：尽可能快地运行迷宫 ledBlink(3); while (digitalRead(buttonPin) { } mode =STOPPED; status =0; // 第一次通过 pathIndex =0; pathLength =0;} 

因此，当 First Pass 结束时，我们必须做的只是将优化的路径阵列喂给机器人。它将开始运行，当找到交叉点时，它现在将根据 path[] 中存储的内容定义要执行的操作 .

void mazeOptimization (void){ while (!status) { readLFSsensors();开关（模式）{ case FOLLOWING_LINE:followLine();休息; case CONT_LINE:if (pathIndex>=pathLength) mazeEnd();否则{迷宫转弯（路径[路径索引]）；路径索引++；}中断； case LEFT_TURN:if (pathIndex>=pathLength) mazeEnd();否则{迷宫转弯（路径[路径索引]）；路径索引++；}中断； case RIGHT_TURN:if (pathIndex>=pathLength) mazeEnd();否则{迷宫转弯（路径[路径索引]）；路径索引++；}中断； } } } 

要命令做什么，一个新函数 mazeTurn(path[]) 被创建。函数 mazeTurn(path[]) 将是：

void mazeTurn (char dir) { switch(dir) { case 'L':// 向左转 goAndTurn (LEFT, 90);休息; case 'R':// 右转 goAndTurn (RIGHT, 90);休息; case 'B':// 返回 goAndTurn (RIGHT, 800);休息; case 'S':// 直接运行 runExtraInch();休息; }} 

第二关完成！下面的视频显示了在这里工作的完整示例，第一遍和第二遍。在本教程中使用的 Arduino 代码下方：

FV6XNJWINJ45XWM.ino F2FXS8MINJ45XX6.h FX5MHFMINJ45XX7.ino FT2S1WXINJ45XXA.ino F9IC3HQINJ45XXB.ino FU2HRXJINJ45XXV.ino

第 9 步：使用 Android 进行调优

也可以在此处使用为以下项目开发的 Android 应用程序（如果您需要，Android 应用程序及其代码可在以下位置获得：Line Follower Robot - PID Control - Android Setup。上一步提供的 Arduino 代码已包含与Android 设备。如果您不想使用 Android 应用程序，没问题，因为代码是“transparent ”.

我在项目中使用了很多 Android，使用“Message Received”将测试数据从机器人发送到设备 " 字段，必须定义好几个变量，才能保证机器人转动正确的角度。最重要的如下（粗体标记的我改过几次）：

const int adj =0; float adjTurn =8;int adjGoAndTurn =800;THRESHOLD =150const int power =250; const int iniMotorPower =250; int extraInch =200;  

第 10 步：结论

这是一个复杂项目的第二部分也是最后一部分，探索线路跟随机器人的潜力，其中人工智能 (AI) 简单的概念被用来解决迷宫。

我不是人工智能 专家，根据我从网上得到的一些信息，我明白我们的小雷克斯机器人所做的，解决迷宫可以被认为是人工智能的应用。让我们来看看下面的 2 个来源：

来自维基百科：

或者来自这篇大学论文：《使用Freeduino和LSRB算法的迷宫求解机器人国际现代工程研究杂志（IJMER）》

这个项目的更新文件可以在 GITHUB 找到。希望我可以为其他人贡献更多关于电子、机器人、Arduino 等的知识。更多教程请访问我的博客：MJRoBot.org

来自世界南部的Saludos！

谢谢

马塞洛