网友提问：
联通机器人路径规划有哪些算法？
优秀答案：
联通机器人的应用有很多。 目前扫地机器人、家庭服务机器人、AGV搬运车都需要用到机器人路径规划算法。 虽然在众多服务机器人中，还有另一套路径规划平台软件SLAM。
这个原因以主要和次要的方式陈述：
1、先说说扫地机器人的路径规划。
联通机器人路径规划一般需要解决三个问题：
1）使机器人从初始位置移动到目标位置；
2）利用一定的算法使机器人避开障碍物，但通过某些必须经过的点来完成相应的任务；
3）在完成上述任务的前提下人工智能最短路径，尝试优化机器人的运动轨迹。
联通机器人的路径规划根据用途的不同分为两种，一种是传统的点对点路径规划，另一种是完全遍历的路径规划。
点对点路径规划是一种从起点到终点的运动策略。 要求从起点到终点寻找一条最优（如成本最低、路径最短、时间最短）合理的路径，使联通机器人能够顺利地在工作空间中导航，不会遇到任何障碍。 完全遍历路径规划是二维工作空间中的一种特殊路径规划。 是指在满足最优或准最优性能指标的前提下，在设定区域内寻找一条从起点到终点的路径，并通过所有可达路径。 点的连续路径。
对于扫地机器人来说，它的工作任务是打扫房子，它的路径规划是一次完整的遍历路径规划，需要满足遍历性和不重复性两个指标。 所谓遍历性是指扫地机器人的运动轨迹需要最大程度地覆盖所有的大空间，这反映了机器人的工作质量。 所谓不重复，就是扫地机器人的行走路线要尽量避免重复，体现了机器人的工作效率。
扫地机器人的自主寻路可分为随机覆盖法和路径规划法两种。
随机覆盖
随机覆盖方式统称为随机碰撞导航，但这并不意味着机器人真的与环境中的物体发生碰撞，也不是在地板上无规则地随机交流。 为满足要求，随机覆盖方式是指机器人按照一定的联通算法对工作区域进行试探性覆盖，如三角形或五边形轨迹。 如果遇到障碍物，它会执行相应的转向功能。 这些方法都是一种以时间换空间的低成本策略，比如100%的覆盖率不考虑时间。 随机覆盖方式不需要定位，没有环境地图，无法规划路径，所以它的联通路径基本上依赖于外部算法，算法的好坏也决定了它清扫的质量和效率。
开发的iRobotRoomba3-8系列是随机碰撞寻路系统的典型代表。
据悉，它采用了iAdapt智能清洁技术的专利技术，是一款软硬件结合的智能AI清洁系统。 硬件由Roomba前面的几个白色探测器、底部灰尘探测器和跌落传感器、刷子、橡胶刷、边刷测速系统等组成，通过Roomba硬件传回的信息，iRobot自身的软件可以分析返回的信息，根据红外回传信息的硬度、范围、高度、速度、电流、阻力等参数，估算出前方障碍物的大致形状，再通过软件的处理计算，得到的结果就是Roomba的下一步清洁方法。 Roomba以每秒60次的速度预估周围障碍物，同时对周围环境做出环绕、回头、螺旋、贴边、转弯等40多种清扫动作。
其次，iRobot采用区域模糊判别算法，根据房间面积手动设置清扫时间。 不同于路径规划，Roomba 开始收集算法计算所需的两个重要参数：单次行驶距离和单位时间内的碰撞频率。 单程距离越长，间接意味着卧室面积越大人工智能最短路径，走几步后掉头间接意味着卧室面积越小。 每次与 Roomba 发生碰撞时，您都可以收集相关信息。 单位时间内碰撞频率越高，卧室面积越小，碰撞频率越低，需要清扫的面积越大。
虽然市面上的扫地机器人大多采用随机碰撞寻路，但清扫效率参差不齐。 归根结底还是软件算法的问题。 这就是为什么你也买随机碰撞寻路的扫地机器人。 覆盖范围和效率存在天壤之别。
路径规划
计划导航需要构建环境地图和定位。 路径规划的研究已经进行了多年，提出了多种技术。 不同的方法各有异同，适用范围也不同。 没有一种路径规划方法可以适用于所有的环境信息。 其中，人工势场法、网格法、模板模型法和人工智能法是路径规划中的典型方法，但也越来越受到重视。 下面分别介绍上述典型的路径规划方法。
1、人工势场法
人工势场法是机器人导航中提出的一种虚拟力法。 其基本方法是将机器人在周围环境中的运动设计为势场中的运动，势场是机器人运动环境的具体描述。 机器人在场中具有一定的具体势能，势能有力极和引力极两种。
机器人不想进入的区域和障碍物是力极：目标和机器人系统建议的区域是引力极。 两极周围形成相应的电势，任一点的电势是该点形成的电势之和。 这种势能的负梯度称为力。 势场的完善主要用于动态跟踪。 此时，引力极是局部环境中的中间目标，力极是局部环境中的障碍物。 重力与力的合力作为机器人的加速力，控制机器人的运动方向，估计机器人的位置。 该方法结构简单，易于实现低级实时控制，在实时跟踪和平滑轨迹控制中得到广泛应用。 但对于局部最优解的问题，很容易形成死锁现象，因此机器人可能在到达目标点之前停留在局部最优点。
2.网格法
联通机器人的实际几何形状可以用一个矩形区域来表示。 在飞行规划过程中，机器人被缩小为一个点，环境中障碍物的边界也随之扩大和模糊。 工作空间用网格表示，即工作空间定义为大小相同的正方形，正方形的大小与机器人的几何形状相同。
用网格法表示环境：用相同大小的网格定义机器人的工作空间，用网格链表表示环境。 每个网格都是两种状态之一，要么在自由空间中，要么在空间障碍物中。 这些方法的特点是简单易实现，因此给路径规划的实现带来了很多方便，并且具有表示不规则障碍物的能力； 它们的缺点是表示效率不高，时空开销与精度存在矛盾。 网格的大小直接影响环境信息存储的大小和规划时间的长短。 网格定义大，环境信息存储量小，规划时间短，帧率增加，密集环境下路径检测能力下降； 道的能力强，但环境的储量大。 所以网格的大小直接影响控制算法的性能。
3、模板模型法
另一种常见的方法是模板模型。 DeCaravalh 提出了一个具有 2D 干净环境的地图和一个基于全遍历路径规划的模板。 为了完成完整的遍历路径规划，DeCaravalh定义了五个模板，分别是：前向模型（TowardsModel）、边到边转向模型（SideShift）、回溯模型（Backtracker）、掉头模型和掉头交替模型. 模板模型法是根据先验知识和先前环境地图遍历机器人获得的环境信息来匹配预先定义的模板。 为此，整个路径由一系列模板组成。 在这种方法中，为了简化路径规划过程，预先扩大了环境，使这些精致灵活的机器人可以被视为一个粒子。 基于模板的模型完全遍历路径规划，需要环境模型的记忆和预先定义的模板，难以应对不断变化的环境，例如工作过程中突然出现的障碍物穿越机器人。
4.人工智能方法
近年来，许多学者采用模糊逻辑、人工神经网络、遗传算法等现代估计智能技术来解决机器人路径规划问题，并取得了一些可喜的成果。
1）模糊控制算法
模糊控制和路径规划的应用是一种非常有特色的方式，是在线规划中普遍使用的一种规划方法，包括建模和全局规划。 它利用多个传感器检测前方道路和障碍物的状况，并根据驾驶员的驾驶经验制定模糊控制规则，用于对传感器信息进行处理，输出速度、加速度、转弯等控制量，以达到引导卡车前进。 这种方法最大的优点是参与者的驾驶经验少，可以实现实时规划，克服了势场法容易形成的局部极值问题，疗效显着是理想的。
模糊控制的路径规划方法非常适用于局部防撞规划，具有设计简单、直观、速度快、效果好等特点。
2）神经网络路径规划
神经网络早已被应用到许多工程领域，机器人领域也不例外。 神经网络在路径规划方面也有很多应用。 Tse 提出了一种 BP 神经网络，用于清洁联通机器人从一个地方到另一个地方的运输。 该模型可以通过自学习进行自主导航的路径规划。 跟踪的完整遍历路径规划只能通过离线学习来实现，分为运动行为、路径规划和全局路径规划三个步骤。 在运动行为阶段，机器人通过各种传感器采集三维环境信息，然后将这些信息输入到BP神经网络中。 机器人可以清洁周围区域，直到周围没有未清洁区域为止。 在路径规划阶段，清扫机器人需要确定通向工作空间内其他未清扫区域的最短路径。 在全局路径规划中形成全局环境地图，然后机器人从起点开始清扫整个工作空间。
3）遗传算法
遗传算法是 John Holand 于 20 世纪 70 年代初开发的一种针对自然选择和种群遗传机制的搜索算法。 它模拟自然选择和自然遗传过程中发生的繁殖、交配和变异现象。 它将每一个可能的解看成群体中的一个个体（所有可能的解），并将每个个体编码成一个字符串，根据预定的目标函数对每个个体进行评价，并给出一个合适的值。 一开始总是随机形成一些个体（即候选解），根据这些个体的适应性，利用遗传算法（选择、交叉、变异）对这些个体进行交叉组合，得到新的个体. 因为这群新个体继承了上一代的一些优秀特性，明显优于上一代，并逐渐朝着更好的解进化。 遗传算法不需要对复杂的优化问题进行建模和复杂计算。 遗传算法只有三个算子才能找到最优解，因此在各个领域得到了广泛的应用。 在机器人研究领域，遗传算法已被应用于机械臂轨迹生成、多机器人路径规划、冗余机械臂避障等方面。
另一方面，当遗传算法与模糊逻辑、人工神经网络等技术相结合，形成智能学习和进化系统时，就显示出其强大的威力。 许多学者综合运用上述智能方法进行了路径规划尝试。 如 ToshioFukuda 等人。 提出了具有“结构化智能”的机器人导航系统。 它以模糊控制器为核心。 一种用于路径规划的分层决策机制，但根据从反馈中获得的奖励和惩罚信息进行学习和进化。 它的优点是系统的自学习能力，这也是其研究的长处和短处，但都使系统更加复杂，效率较低。