机器人吸尘器环境建模与路径规划研究综述

李昊 汪超 王进 孟濬 由林麟

1.加拿大新不伦瑞克大学 新不伦瑞克 E3B；2.北京航空航天大学航空科学与工程学院 北京 100191；3.中国家用电器研究院 北京 100037；4.浙江大学机器人研究院 浙江杭州 310027；5.中山大学智能工程学院 广东广州 510006

1 引言

家用机器人自90年代以来就已经被广泛应用。一些主要的家用机器人包括应用于清洁的吸尘器、自动擦地机、割草机、游泳池清洁器和窗户清洁器等；用于家庭娱乐的有玩具、业余兴趣机器人；还有一些家用机器人主要负责家庭安全和监视，如机器视觉、运动检测机器人等。

预计未来几年家用机器人的应用将更加广泛，有更多创新的人工智能（AI）技术将得到应用。国际机器人联合会（International Federation of Robotics）指出美国服务机器人产业的市场规模为52亿美元。估计2020年服务机器人或家用机器人将贡献110亿美元的收入。企业也在加大投资进行清洁机器人的AI研究与开发。2017年2月，戴森公司投资5.87亿美元在新加坡建立了研发技术中心，进行互联技术和机器人研究。人工智能非盈利组织OpenAI将“家用机器人”列为重要技术目标之一。

在过去的十年中，清洁机器人的功能有了重大改进[1]。该市场制造商越来越多的希望采用AI技术，特别是在吸尘、擦地板和割草等方面。市场上一些流行的清洁机器人包括：

iRobot Roomba：当iRobot于2002年推出其第一台机器人真空吸尘器Roomba时，产品只具有基本的AI功能，例如识别墙壁和使用内置传感器避开楼梯。最新的980型Roomba具有由AI驱动的高级决策功能。该机器人能够扫描房间大小、识别障碍物并记住最有效的路线和方法。

博世Roxxter：博世机器人吸尘器Roxxter系列利用AI绘制环境的交互式地图。机器人能够通过Amazon兼容Alexa的设备处理语音命令。用户可以通过命令Alexa来激活Roxxter机器人。

夏普RX-V100：夏普RX-V100内置有语音识别AI引擎，可通过闪烁的指示灯和语音消息组合来执行诸如报告机器人当前状态之类的任务。当用户向机器人发出语音命令“清洁”时，RX-V100使用AI语音回答“好”并“摇摆”以确认命令。然后开始在自动模式下清洁。该产品还提供了一组预定义的消息和响应功能，以进行简单的对话。

此外，戴森、三星、Neato等品牌的机器人产品也都在市场中得到了较好的反响。

机器人吸尘器的设计和开发通常基于市场上的低成本组件，其吸尘结构图如图1所示。吸尘器底座带有电机及控制电路、驱动轮、编码器、脚轮等；底座可以移动并携带电池、吸尘装置、控制系统等其它组件。传感器系统通常包括超声波测距仪传感器、相机、激光雷达、陀螺仪、IMU等。通讯系统有无线通讯、I/O总线、RS-232串行端口等。嵌入控制系统从传感器接收测量信息，再依次处理传感器信息、环境建模、导航、控制、执行车轮速度命令并将这些命令发送到电动机，以控制电机执行任务。机器人控制器在主机中创建、开发，然后下载到嵌入控制系统。本文主要介绍用于机器人吸尘器的环境建模和导航的人工智能技术。

图1 机器人吸尘器结构图

在吸尘器机器人开始任务前，必须完成环境建模。环境建模是基于工作空间地图而实现的，而工作空间的地图则是通过摄像头、红外传感器或超声波传感器等不同传感装置获得的传感数据构建。由于室内扫地机器人缺少诸如GPS之类的绝对定位系统，因此机器人位置逐渐漂移，姿态的不确定性也越来越大。同步定位和映射（SLAM）技术的发展极大地改善了机器人的定位精度，该技术通过统计数据的方式来估计机器人的姿态（位置和方向）并对其进行纠正。在智能机器人吸尘器顶部，配置一个摄像头或激光雷达，利用SLAM技术对传感器数据进行处理。而SLAM算法是一种动态构建地图同时跟踪自己位置的方法，该算法可以处理相机图片或雷达数据，从中挑选出例如室内物体的边角等诸多环境特征。机器人记住这些特征的形状并在移动时对其进行跟踪。在工作过程中，机器人将连续采集数据，检测和跟踪新特征，并逐步建立环境地图。在自身定位方面，在机器人底部通常安装编码器、陀螺仪、IMU等传感器，机器人需要将该环境地图、里程表及其他传感器结合。一旦机器人吸尘器获取了自己的位置，便可以执行各种任务。机器人可以进行直线吸尘，以提高覆盖效率。如果充电电池电量不足，机器人可以在房间内直线返回充电器进行充电。即使清洁工作还未完成，机器人也能记住确切位置，充电完成后再返回该处继续完成剩余吸尘任务。环境建模和定位功能解决了传统吸尘器没有定位和导航功能，无法清理多个房间，以及充电后无法回到暂停位置继续工作的问题。

机器人吸尘器的一项重要任务是扫除整个环境中的每个可及区域，并避开障碍物。当机器人通过某个区域的位置时，将对其进行清洁，如果尚未清洁，该区域则会保持不清洁状态。机器人吸尘器设置了室内地图后，就能够规划覆盖室内的路径。这种机制称为覆盖区域路径规划。覆盖路径规划（CPP）的任务是确定一条路径，该路径将经过感兴趣区域中的所有点，同时避开障碍物。路径规划是许多机器人应用的必须功能，例如吸尘机器人、喷漆机器人、自动水下机器人、割草机、自动收割机、窗户清洁器和复杂结构的检查器具等。要清洁一个房间，可以使用螺旋形或弓字形的运动轨迹。在该区域中，机器人应通过覆盖路径规划清扫每个可到达的自由区域，并以有效的轨迹避开障碍物。这种有效的轨迹应该是短距离的，并且包含最小数量的转弯角。

本文主要介绍了机器人吸尘器的定位及室内建模的技术，同时对路径规划问题及相关算法进行详细的描述，给出了路径规划算法的案例及结果。

2 机器人吸尘器的定位及室内建模技术

同步定位和映射（SLAM）技术通过机器人定位来建立环境地图，同时解决定位和地图的计算问题。该技术在构造或更新未知环境地图时同时跟踪机器人位置。主流的近似求解方法包括粒子滤波器、扩展卡尔曼滤波器、协方差交点和GraphSLAM。其中基于统计的卡尔曼滤波器和粒子滤波器也被称为蒙特卡洛法，它们为机器人的姿态和地图参数提供了后验概率函数的估计；使用协方差交集近似上述模型的方法能够避免依赖统计的独立性假设来降低算法复杂性；而GraphSLAM算法仍然是一个新的研究领域，是否应用通常是由对地图、传感器和模型类型的不同要求来决定。

SLAM算法广泛用于导航、机器人定位、自动驾驶汽车、无人驾驶飞机、水下自动驾驶、行星漫游车、家用机器人等。

2.1 滤波

室内环境的建模需要对传感器数据进行滤波，主要方法包括卡尔曼滤波、扩展卡尔曼滤波、粒子滤波等。这些方法都基于贝叶斯滤波。通过对吸尘器传感器滤波研究，可以对吸尘器定位，并建立室内环境地图。

2.1.1 贝叶斯定理

贝叶斯定理又称为贝叶斯定律或贝叶斯规则，该定理是基于对事件之条件相关的先验知识来描述事件的概率。比如已知发生健康问题的风险会随着年龄的增长而增加，贝叶斯定理则认为比仅假设某人是整个人口中的典型情况更准确地是评估已知年龄人的健康风险。贝叶斯推理是贝叶斯定理的一个扩展，是统计推理的一种特殊方法。贝叶斯定理中涉及的概率可能具有不同的概率解释。通过贝叶斯概率，该定理表达了应合理改变概率以说明相关证据的可用性。贝叶斯推理是贝叶斯统计的基础。贝叶斯定理已在机器人领域广泛应用，用于去除或降低传感器的噪音，以降低不确定性。通过使用贝叶斯定理，可以有效处理机器人吸尘器的传感器数据，实现定位、环境建模、检测障碍物等功能。贝叶斯定理中P(B)代表测量概率，(B│A)代表可能性，P(A)代表先验知识，公式如下：

贝叶斯定理解决了用吸尘器的低精度传感器计算室内环境模型的难题。

2.1.2 卡尔曼滤波（KF）

卡尔曼滤波（KF）可以用于处理吸尘器的传感器数据，进行定位及环境建模。卡尔曼滤波是一种统计和控制理论算法，该算法使用随时间推移观察到的一系列测量值（包含统计噪声和其他误差），并生成未知变量的估计值，该估计值通过估计每个时间范围内变量的概率分布得出，比仅基于单个测量的结果更准确。卡尔曼滤波是贝叶斯定理在存在高斯分布噪音的线性系统模型时的一个简单应用。该过滤器以其理论的主要开发者Rudolf Kalman命名。卡尔曼滤波器在技术上有许多应用，常见的应用是运动物体的导航和控制，尤其是飞机、航天器和动态定位的船舶。卡尔曼滤波器是机器人运动和控制领域的主要方法之一。

2.1.3 扩展卡尔曼滤波（EKF）

对于存在高斯分布噪声的线性系统模型，卡尔曼滤波器是最佳的线性估计器。然而在现实工程中，大多系统具有非线性，需要对卡尔曼滤波器进行改进以便应用于非线性系统。扩展卡尔曼滤波（EKF）使用了多元泰勒级数展开式及雅各布矩阵，以线性化工作点模型。通过线性近似，得以对具有高斯分布噪声的非线性系统模型进行估计。因此，通常先建立机器人吸尘器及其传感器的非线性模型，然后用泰勒级数对其线性化，最后使用扩展卡尔曼滤波进行数据处理。

2.1.4 粒子滤波器

如果系统模型是非线性的且噪音不是高斯分布，则采用蒙特卡洛方法如粒子滤波器进行数据处理并估计。这种蒙特卡洛技术最早用于火箭或太空技术，缺点是计算方面更加耗时。

2.2 地图及定位

机器人吸尘器需要解决室内定位、姿态估计和地图建模的问题。问题的难点在于需要地图才能进行定位，需要位置姿态的精确信息才能测量绘制室内地图。SLAM是同时解决这两个问题的技术[2]。定位即先给定一个地图，再进行定位；地图绘制则为先给定位置姿态，再测绘室内地图，如图2所示。

图2 地图绘制

地图主要有几种：

（1）拓扑图：拓扑图是一种环境地图表示的方法，它捕获环境的连通性（即拓扑），而不是创建几何上精确的图。

（2）特征地图：特征地图是使用环境中的主要特征点及其位置来绘制地图。

（3）网格地图：网格地图的基本思想是将环境图表示为均匀分布的二进制随机变量的字段，每个字段代表环境中该位置存在障碍物。网格地图算法计算近似后验估计随机变量。

基于特征的定位方法：

定位指使用传感器信息在环境中定位机器人，目的是找到给定的机器人位置。主要需要两个模型进行滤波定位：

（1）控制输入和运动模型；

（2）传感器测量和测量模型。

机器人吸尘器的运动模型如图3所示。

EKF SLAM利用扩展的卡尔曼滤波器（EKF）进行同步定位和映射（SLAM）。EKF SLAM算法基于特征，并使用最大近似算法进行数据关联。直到FastSLAM出现，EKF SLAM一直是SLAM的主流方法。假设机器人具有基于特征的地图，机器人可以将传感器读数与期望值进行比较（基于当前估计的机器人姿态）。传感器需要测量特征的方位、范围及相对位置，利用扩展卡尔曼滤波器（EKF），将不确定性测量结果与机器人姿态的当前估计值合并。通过运动学模型实现机器人姿态Xt的预测更新。控制信号Ut-1是运动学模型的输入。使用已知特征位置M和估计姿势Xt计算预测。然后，EKF用于融合距离和方位测量值Zt，以减少姿态不确定性。EKF SLAM的定位结果如图4所示。

图3 机器人运动模型

图4 机器人定位（Matlab运行结果）

机械人的状态是向量X=[x yθ]T，测量值是Z=[dα]T，其中d是距离，α是传感器测得的角度。运动命令是前进速度和角速度。机器人不能完美执行命令并运动。在运动中存在一些高斯噪声，并相应地改变了机器人的实际姿势。传感器测量机器人的实际运动，但也存在一些高斯噪声。需要根据上述信息，找到系统的运动模型和测量模型，然后线性化运动模型和测量模型，并进行滤波定位。这里使用EKF进行状态估计和校正。EKF是对非线性系统的线性卡尔曼滤波器的扩展，它使用关于当前均值和协方差值的泰勒线性化。类似于线性卡尔曼滤波器，EKF算法具有两个主要步骤，即“预测”和“更新”。非线性系统可以描述为状态函数f和观察函数h。X是n×1状态向量，Z是m×1状态向量，U是控制信号。R和Q分别是过程和观测高斯噪声，其中R和Q为协方差矩阵。EKF使用f的雅可比行列式Jx。在每个步骤中，EKF计算状态的估计值并更新不确定性，以及关联状态协方差矩阵。

3 路径规划

获取了室内环境地图及定位信息后，要进行机器人吸尘器的路径规划。覆盖路径规划（CPP）是扫地机器人的一个重要功能。通过检测灰尘、构建室内地面模型的方式，使扫地机器人在清扫时使用传感器和吸尘器有效覆盖所需清洁区域。以下简要介绍覆盖路径规划的一些研究。

利用精确的单元分解算法将自由空间（即没有障碍的空间）分解为简单的、不重叠的区域，并称之为单元。所有单元的并集恰好填充了自由空间。这些区域没有障碍物，可以“轻松”地遮盖起来，并且可以通过机器人简单的动作将其扫过。例如，每个单元都可以使用弓形的“割草”模式覆盖。通常，基于精确的单元分解算法会分两步生成覆盖路径：首先将自由空间分解为单元格，并将分解结果存储为邻接图，再计算覆盖邻接图的详尽序列，所获得的详尽行动路线是一系列节点，而不是实际的覆盖路径。

此后，一种基于摩尔斯功能临界点的新型单元分解方法被提出。基于摩尔斯的分解具有处理非多边形障碍的优势。通过选择不同的莫尔斯函数，可以获得不同的单元形状，例如圆形或尖刺。从理论上讲，莫尔斯分解可以应用于任何n维空间。通过使用一种感官距离信息检测临界点从而进行平面空间覆盖的方法，可确保遇到目标区域中的所有临界点。因此，这种方法可以实现完全覆盖。

后来，一种用于移动机器人的在线拓扑覆盖算法被提出。这种方法旨在用于简单的平面环境。虽然类似摩尔斯分解，但此处提出的拓扑算法是使用不同的事件来确定单元边界。摩尔斯分解法是将单元边界置于障碍物表面的关键点上，然而直线环境不能通过摩尔斯分解来处理，因为这种环境的临界点已经退化。另一方面，由于关键点只能在机器人执行沿着墙走动的指令时显示在机器人的侧面，因此需要一个矩形的覆盖图案，包括重新绘制轨迹。相比之下，拓扑方法可以使用更简单的界标来确定被称为“切片分解”的精确单元分解。由于使用了简单的地标，切片分解可以处理更多种环境，包括具有多边形、椭圆形和直线形障碍物的环境。此外，还可以从机器人的所有侧面检测障碍物，从而可以使用简单的弓形图案而无需使用轨迹，该方法生成的覆盖路径更短。

另一种方法是基于接触传感器的直线环境覆盖。这是一种精确的单元分解算法，用于接触感应机器人（即没有范围感应）在线覆盖未知的直线环境。在该系统中，平面线性电动机在类似桌子的表面上运行。实际上，这个方法构造的分解可以看作是摩尔斯分解，然而所有临界点都退化了。

还有一种方法是基于图形表示的环境覆盖算法，图形可以是街道或道路网络。这种方法解决了一些覆盖率方面的问题。首先，考虑到以图形提供的先前地图信息可能不完整；其次，考虑了环境约束，例如单行道；第三，当执行覆盖路径时，机器人的传感器检测到图形中的变化后，将提供在线重新计划的策略。图形搜索算法能够为图表的每个边界分配一个数值并寻找最佳解决方案，或者在时间限制下找到一种近似优化的解决方案。

3.1 覆盖路径规划的定义

为了正式定义路径规划问题，我们需要定义一些基本术语，如下：

配置空间（Q）：机器人可以实现的所有配置的集合。Q可以细分为自由配置空间Qfree和占用配置空间Qobs。Qobs中的任何配置都会导致与障碍物的接触，而Qfree中的任何配置都不会。

工作区或环境（W）：机器人所在的世界。

路径：通过Qfree的参数化曲线。

自由度：代表机器人配置所需的最少自变量。要完全描述移动机器人，需要六个自由度：{x，y，z，φ，θ，ψ}，其中x，y和z表示3D空间中的位置，而φ，θ和ψ是欧拉角。通过假设θ=φ=0在2D平面完成扫地机器人的路径规划，在这种情况下存在3个自由度：{x，y，ψ}。

我们可以将路径规划的任务定义为在自由配置空间Qfree中找到一条曲线，该曲线连接起始位置q=qs与目标位置q=qg。

路径规划任务通常属于以下四个应用：

（1）导航：在有障碍的环境中找到无碰撞的路径。

（2）环境覆盖：移动传感器覆盖环境中的每个点。

（3）定位：使用传感器数据来确定机器人在环境中的配置。

（4）建地图：使用传感器探索以前未知的环境。

本文介绍的大多数算法都适用于导航与环境覆盖。它们对机器人吸尘器的路径规划很重要。以下术语定义路径规划算法的属性，用作比较的基础。

（1）最优性：一种优化（最大化或最小化）目标的算法。

（2）完整性：如果路径规划算法始终能找到解决方案或在有限时间内确定不存在解决方案，那么该算法是完整的。如果路径完整且易于离散化，则也可以认为该路径已完成。或者，如果可以保证算法收敛到完整性，则称该算法是概率完整的。

（3）离线路径规划：在执行任务之前了解所有环境知识，并完成路径规划。

（4）在线路径规划：在执行任务过程中逐步构建路径。

（5）基于传感器的路径规划：在线处理传感器信息并用于规划。

（6）思考式：意识思考 → 规划 → 执行任务。

（7）反应式：使用感官信息来完成任务，而无需构建整个环境。

覆盖路径规划的目标是生成一条路径，该路径将使工作空间中的每个点都被传感器覆盖，而不是生成从起点到目标点的导航。该问题可以表述为：考虑一个带有嵌入传感器的移动机器人，其传感器带有一些二维覆盖区域A。在工作空间W内的轨迹将产生一组N个传感器读数：{A1，A2，...，AN}。覆盖路径规划的目标是生成一条穿过工作空间的路径，使覆盖W，这意味着一段时间后，传感器覆盖区已通过工作空间W中的每个点[3]。

3.2 路径规划算法

一旦扫地机器人建立了环境地图，并且机器人已经能够自我定位，就必须完成路径规划的高级任务，以完成其任务目标。通常，路径由一组要连续命中的航路点表示。这些航路点被用作外环参考，内环控制器将能够控制机器人跟踪参考路径。鉴于外环引用独立于电机控制，因此可以开发出与系统硬件无关的非常通用的路径规划算法。航路点可以根据当前的最新信息一次生成，也可以提前进行全面规划。例如，传统的覆盖路径规划使用一系列预先定义好的航路点来定义路径（通常是弓字或之字形路径）。航点定义的路径的替代方法是更基于反应行为的规划。例如，可以通过保持距离墙壁的距离，或避开障碍物，或遵循诸如室内家具结构来指定路径轨迹。在这种被动的方法中，没有建立环境模型来辅助决策过程，因此很难实现全局目标。路径规划的任务取决于许多因素，例如有关环境的信息，规划路径的期望质量及任务。如果事先可以获得详细的环境信息，则路径生成可能会很慢。如果需要即时规划路径，则需要一种可以接近实时运行的算法。本节将总结现有的主要路径规划算法。

路径规划的方法有许多种。一些覆盖路径规划的问题，可以视为确定性方法，不考虑不确定性，可以在理想状况下证明完整性。采用非确定性或概率性方法对传感器和执行器的噪声鲁棒性更好，但不能保证路径的完整性。简单的覆盖路径规划算法定义了预定形状（如弓字形或之字形）的结构化路径，以确保覆盖。一些复杂的方法则从搜索空间生成非结构化轨迹，以实现探索目标。

覆盖路径规划的方法有启发规则式、随机式、单元分解技术、基于网格的方法：

（1）启发规则式方法定义了要遵循的一组规则，这些规则最终导致覆盖整个环境。

（2）随机式方法通过随机移动，最终重复多次覆盖整个环境。

（3）单元分解技术用于将环境划分为可管理数量的单元或区域，可以采用图形或查询树等搜索方法进行路径规划。一旦所有单元都被覆盖，则整个工作区都被覆盖。分解可以是近似、半近似或精确分解。单元的形状和分解类型可能会对搜索算法的性能产生影响。覆盖路径规划算法的其他应用包括：无人驾驶飞机、3D地形覆盖，以及用于农业的机器等。

（4）基于网格的方法是使用分解为统一网格单元的集合来表示环境。这种网格表示环境的方法是使用安装在移动机器人上的传感器来绘制室内环境图。在此表示形式中，每个网格单元都存在一个关联的值，该值可以表示是否存在障碍物或是否为自由空间。该值可以是二进制值，也可以是概率值。通常，每个网格单元都是正方形，但是也可以使用不同的网格单元形状，例如三角形。这种近似表示的结果是，大多数基于网格的方法都是“分辨率完整的”，也就是说，其完整性取决于网格图的分辨率。

简单的启发式、反应性方法可以通过遵循简单的规则来覆盖整个工作空间。这种方法功能非常有限，无法处理计划之外的情况，但是这种方法无需对环境的认知或地图。如果有地图，那么计划的选择就会大大增加。一些算法依据障碍物的位置和目标点在整个工作空间上生成潜在函数，使机器人跟随每个位置的势函数负梯度的方向。

自由空间的维数也可以减小以形成类似于路线图的方案。路线图必须遵循的规则是可以以某种简单的方式从自由空间的任意点进入路线图，并且路线图本身已连接。单元分解法将环境分解为小块的集合，这些小块通常称为单元。路线图和单元分解的结果是将工作空间转换为抽象表达，可以将其视为带有节点的图形，并通过边连接。构建图形后，必须对其进行搜索。遍历或搜索图形的算法在文献中很常见。

由于基于网格的方法仅近似目标区域及其障碍物的形状，因此基于网格的方法也可归类为近似单元分解。另外，受仿生启发的生物算法和神经网络、深度学习等方法也可以解决包括搜索在内的各种问题。

以下使用简单2D环境比较各种算法。随机放置的红色方块表示障碍，起点和终点如图5所示。

图5 路径规划环境（Matlab运行结果）

3.2.1 启发式反应算法

虫子算法是一种简单的启发式方法，可以帮助机器人在充满障碍的环境中从起点导航到目标。

1代虫子算法假定机器人只有接触传感器和目标所在位置的信息。机器人开始向目标移动，如果遇到障碍，就会绕过障碍找到最接近目标的点，然后机器人会一直移动到那个点，直到达到目标为止。如果前进方向与已知障碍相交，则推断没有通往目标的路径。事实证明，这种方法是完整的，也意味着机器人可以在有限的时间内找到目标或报告没有可能通往目标的路径。

用1代虫子算法生成的路径如图6所示。

图6 1代虫子算法规划的路径（Matlab运行结果）

2代虫子算法则在起点和目标点之间绘制一条假想线，机器人遵循这条线移动，如果遇到障碍，将会绕过障碍，直到与线相交，然后继续前进。2代虫子算法通常比1代虫子算法快，但缺点是无法保证在有限的时间内找到目标，因为这种算法可能被某些奇形怪状的障碍难住。如果机器人在映射中遇到已访问的点，则算法失败。2代虫子算法生成的路径如图7所示。

还有一种类似虫子算法的方法叫做“相切虫”算法。“相切虫”算法假定机器人配备了范围传感器。机器人开始朝目标方向移动，如果测距传感器检测到障碍物，则机器人会将其轨迹改变到测距传感器上的点，以避开障碍物并将其推向目标。产生的路径与障碍物相切。这种方法的性能大大超过1代虫子算法和2代虫子算法，但需要使用额外的传感器。在所有虫子算法中，必须在搜索之前选择绕过障碍的方向。通常，此选择是随机进行的，但会对输出路径的长度产生显著影响。

3.2.2 势能场算法

现有的目标、障碍位置等环境知识可用来定义一个势能场。规划路径可以由势能函数的负渐变生成。此方法计算简单，因为不需要搜索确定路径，而是自动选择势能场负梯度的方向。势能场如图8所示。图中障碍物所在位置势能高，目标位置势能低。

图7 2代虫子算法规划的路径（Matlab运行结果）

图8 势能场（Matlab运行结果）

势能场方法通过将目标看作吸引力，将障碍物看作排斥力来生成势场函数，空间中的任何一点的势能函数是正负力的和：

势能场算法快速且能够处理多自由度的场景。在循环中，先计算吸引和排斥力矢量和梯度，然后计算梯度下降。在循环中的每一步，都会沿负梯度的方向移动一些距离。

势能场算法生成的路径如图9所示。

图9 势能场算法规划的路径（Matlab运行结果）

3.2.3 波浪边缘算法

波浪边缘算法与势能场算法相似，但在几个重要方面有所不同。波浪边缘算法对自由空间中的每一点的势能都是通过模拟从目标位置移动到起点的波产生。可用空间由网格表示，所有网格的初始化都为不可见。目标单元格初始标记为已访问并指定值2，然后，此算法迭代查找访问的单元格中未被查看的相邻单元，并为其分配一个大于访问的单元格的值。结果将是一个“波浪”从目标单元向外辐射，新单元则被分配到增加的值。

一旦波浪边缘到达起始单元，表示势能方程完成，然后通过梯度递减规划路径。通过从起始位置开始并迭代选择最小值的相邻单元来实现梯度下降。

由于波浪边缘算法不会出现局部最小值，比势能场方法具有优势。然而，它在计算上更复杂，并需要事先了解所有障碍的位置，是一种离线算法。

图10中显示了波浪边缘算法的结果。如图10所示，可用空间的较浅区域具有较高的势能。黑色显示的障碍物被认为是无限的负势能。起点以绿色显示，终点以红色显示。在这种情况下，自由空间被离散为单元格，在梯度下降步骤中只考虑四个邻域。

3.2.4 路线图算法

路线图可以通过环境空间的子集生成，它满足三个主要规则：

（1）可以从环境空间的任何一个起始点到达路线图。

（2）可以从路线图上的任何一点到达路线图上的任何其他点。

（3）可以从路线图到达环境空间中的任何目标点。

图10 波浪边缘算法规划的路径（Matlab运行结果）

常用路线图算法包括：

（1）沃罗尼图（Voronoi图）是与至少2个障碍物等距离的点的集合。

（2）可见性图是通过连接每一个可以用直线连接的障碍物顶点而生成的。

生成路线图后，就可以用边和节点的图来表示环境，然后可以用经典的搜索方法来搜索，如A*、广度优先搜索、深度优先搜索等。要生成路线图，需要事先知道所有障碍物的位置。在线路线图方法是在机器人所在环境中，基于采样的方法建立路线图。

广义Voronoi图（GVD）算法是地图自由空间中至少与最近的两个障碍物等距的所有点的集合。GVD是一个回缩，因为GVD上的所有点都会被映射到自己身上，自由空间中的所有点都会被映射到GVD上。因此，能将自由空间平滑映射到GVD上的函数是一个变形回缩。这种表述使我们对GVD的两个重要性质加以利用。

（1）GVD是连通的，因为自由空间的集合是连通的，在变形回缩下保持了连通性。

（2）一个地图的GVD是唯一的，并且对变换和轮回不变，因为它是一个回缩。

GVD可以解释为地图结构的拓扑表示，它包含了地图固有的关键信息，但以更紧凑的一维形式存在。生成GVD的一个简单方法是给地图的每个网格qi分配一个半径很小的圆，然后增加圆的半径，直到它接触到至少一个障碍物。如果只有一个接触点，那么qi不属于GVD，否则属于GVD。GVD如图11所示。

图11 GVD图算法规划的路径（Matlab运行结果）

可见度图算法是自由空间的另一种路线图表示。在可见度图中，所有障碍物顶点都是图中的节点。边缘线用来连接自由空间中彼此视线一致的节点。可见度图算法生成的图具有较高的连通性。该图可以通过以下两个定义来修剪。

（1）支撑线与2个障碍物相切，并且障碍物都在线的同一侧。

（2）分离线与2个障碍物相切，且障碍物各自在线的相对侧。

支撑线和分离线是最佳方案。因此其他边都可以去掉。可见度图规划的路径如图12所示。在现实中，可以在所有障碍物周围实现一个安全边距，使路径不紧密地接近障碍物，增强容错性。

图12 可见度图规划的路径（Matlab运行结果）

与GVD路线图相比，可见度图的优势在于它的生成非常简单。然而，生成的图一般有更多的边和节点，因此搜索更耗时。另外，按照可见度图生成的路径可以保证非常接近障碍物，而且该算法要求障碍物必须用多边形表示。

3.2.5 基于采样的算法

在某些情况下，使用GVD或可见度图生成路线图存在太难或是导致图中的节点和边太多，无法实现有效搜索。如果有很多障碍物，或者环境空间的维度很高，就会出现这种情况。为了解决这些问题，人们提出了基于采样的算法。虽然这些算法不完整且非最优，但其已经被证明能够有效地解决实际问题。

基于采样的算法很多，但本质上其目标都是通过在自由空间中随机生成样本来建立路线图。一种基于采样的算法是概率路线图（PRM）算法。根据这个算法，整个自由空间被随机样本覆盖，然后这些样本以某种方式连接起来，生成一个路线图。PRM算法的设计是这样的：路线图的构建和操作的查询阶段是分开的；在找到从起点到目标的路径之前，整个路线图就已经构建完成。这种类型算法的关键是：

（1）确定随机生成的样本是否位于自由空间中。

（2）确定两个节点之间的边缘是否仍在自由空间中。

用PRM算法规划的路径如图13所示。这种算法是概率完全的，也就是说其朝向最优解的方向收敛。

图13 概率路线图规划的路径（Matlab运行结果）

其他基于采样的方法可以在生成样本的同时就找到了一条通往目标的路径，例如快速探索随机树（RRT）算法。RRT算法在自由空间中随机生成新的样本，但偏向目标。如果没有障碍物，则向随机生成的点迈出一小步，这个过程一直持续到找到目标。如前所述，在空间维度非常高的情况下，这些方法很适合寻找可接受的解。

3.2.6 单元分解算法

单元分解算法是指任何将配置空间分割成一组较小单元格的方法。一旦完成了分解，就可以建立一个连接图，其中单元是节点，在图中有共同边缘的单元是连接的。这种方法对于规划实现完全覆盖的路径非常有效，因为一旦图中的每个节点都被访问过，整个空间就会被覆盖，但单元分解也可以用于起点到目标的路径规划。

单元分解的形状和样式对规划路径的效果有很大影响。单元分解可以分为精确、半近似或近似。比如可以采用近似矩形分解来规划从起点到目标的路径。这种方法的好处是内建了避障功能，而且可以利用信息增益指标搜索目标。但是，它的前提是事先知道障碍物和目标的信息。此外，连接图的搜索可能需要很长时间。

对于带有多边形障碍物的二维环境，可以通过检测临界点进行单元分解，这些临界点是多边形障碍物的顶点，它们会导致自由空间的连通性发生变化。在每个临界点，一个临界片被绘制，通过临界点，但不通过任何其他障碍或环境边界，由此产生的自由空间的分区就是单元分解。这种方法是对梯形分解进行改进，它从每个障碍物顶点延伸出线，适用于非多边形障碍物的环境，而且它产生的单元更少，使搜索更简便快速。一旦单元格分解完成，就会生成一个图，其中每个单元格表示图中的一个节点，相邻的单元格用一条边连接。如图14所示，每个单元由其中心点代表。图中小区的中心点用黑点表示。蓝线代表临界片。每个临界片都与障碍物相切，但不能穿透障碍物。障碍物用红色显示。通过连接中心点从而找到的路径显示为黄线。由于将单元缩减到只有其中心点，所以会产生一个次优路径。

图14 单元分解规划的路径（Matlab运行结果）

3.2.7 搜索算法

一旦自由空间用路线图或单元分解等技术转化为图形，就可以使用搜索算法来搜索图形。下面介绍一些流行的方法。

广度优先搜索（BFS）是在没有启发的情况下，详尽地搜索最接近的节点。最接近根节点的节点总是先被展开。算法维护了两个集合，一个开放集和一个封闭集。封闭集包含所有已经处理过的节点，开放集包含已经访问过的、等待扩展的节点。当一个节点被扩展时，会考虑所有还没有处于封闭集的邻近节点。如果邻近节点还没有在开放集中，则计算其成本，并将其加入到开放集。除了成本之外，我们还必须跟踪哪个节点是为了到达这个相邻节点而展开的。这被表示为父节点，在原程序中通过一个指针实现，它可以让我们恢复查到的路径。这种搜索可以保证找到最优解，但是一般来说，它的速度非常慢，而且只对小型查询问题可用。广度优先搜索的树状图如图15所示。BFS能找到最优搜索，但每个节点都会被扩展。

图15 广度优先算法规划的路径（Matlab运行结果）

A*算法是Dijkstra搜索算法的扩展。A*通过使用距离成本进行启发，因为具有较好的运算速度。A*搜索的一个基本要素是定义一些启发式成本，将每个节点与目标节点联系起来。通常情况下，使用曼哈顿或欧几里得距离来计算成本。每个节点都包含一个从开始通过图到达该节点的真实成本，用g表示，以及一个启发式成本，代表该节点离目标节点的距离，用h表示。所有展开节点的两个成本之和，用f=g+h表示。f值最小的节点被选为下一个展开的节点。如上所述，一旦达到目标，就可以按照父指针从目标节点向后倒推出到起始节点的路径。图16中所示是A*搜索树规划的路径。灰色的边缘和节点没有被展开。与BFS一样，A*也能够找到最优解，然而它无需进行穷尽搜索。

图16 A*算法规划的路径（Matlab运行结果）

3.2.8 遗传算法

遗传算法（GA）是受达尔文进化论启发衍生的算法。所有生物体都是由细胞组成的，在每个细胞中都有同一组染色体。染色体是一串DNA，是整个生物体的模型。一条染色体由基因组成，基因是DNA块。每个基因编码一种特定的蛋白质。在生殖过程中，首先发生交叉或重组。来自父母的基因以某种方式形成一条全新的染色体。一套完整的遗传物质（所有染色体）称为基因组。

进化是一种解决问题的有效方法。遗传算法于1975年首次被提出，是一种借鉴基因的计算方法，它通过计算机实现进化理论，以解决现实生活中的问题。遗传算法定义一组染色体，其中每个染色体代表搜索空间中的一个可能的解。在每次迭代过程中，根据染色体的“适合度”选择染色体，并重组以产生新的后代，直到产生全新的一代。新一代的每个成员也可以选择“突变”，以保持染色体的多样性。实现遗传算法的主要问题是如何对代表潜在解决方案的染色体进行编码，以及如何定义“适合度”函数。

3.2.9 人工神经网络

另一种受生物启发的路径规划算法是人工神经网络。受神经元分流模型的启发，可以构造一种神经网络结构，其动态神经活动图代表动态变化的工作空间。

如图17所示，这是一个拓扑组织的神经网络，它代表一个状态空间S。用矢量qi表示第i个神经元在S中网格的位置。qi代表机器人在状态空间中的一个状态，每个神经元都有与其邻近神经元的局部侧向连接，构成S中的一个子集，在神经生理学中称为第i个神经元的接受场。第i个神经元的动态由分流方程来描述。对于S中给定的当前状态，用qp表示，通过查找邻近神经元的最大值来确定下一个状态qn，这个过程重复执行最终规划起点至终点的路径。

图17 神经活动图（Matlab运行结果）

通过正确定义工作空间的外部输入和内部的神经连接，保证目标和障碍物分别停留在神经网络活动图的高峰和低谷。目标可以通过神经活动在全局范围内传播，吸引机器人在整个工作空间内活动，而障碍物只具有局部影响，从而避免局部碰撞。

4 路径规划案例及结果

本节简要介绍两种路径规划算法的结果。

4.1 信息增益法

下面介绍一种创新的运用信息论来量化机器人吸尘器的清洁效率，从而进行路径规划。这种方法结合吸尘器传感器的不确定性，比传统方法更加实用、有效。对于室内地图每个网格清洁状态离散随机变量X，熵定义为：

交互信息定义了一个标量，该标量表示Z中包含的有关X的信息量，或者换句话说，Z所提供的信息将减少X的熵。

对于吸尘器，X表示状态向量，Z代表传感器测量值。先验是尚未进行测量的状态，无法直接访问该量，因此无法直接评估相互信息。定义预期的熵减少量，通过进行测量Z将实现的预期的熵减少量，从而有效规划路径并清洁环境。

将增益信息表述为所需行驶方向ψd的函数，从而定义信息增益目标函数。定义一条从机器人当前位置（x，y）开始并在每个方向ψd上行驶固定距离r的轨迹进行路径规划并评估。可以预测将要进行的测量，然后可以使用评估从沿给定轨道行进中获得的预期信息，并最大化信息增益[4]。

本方法通过最大化对环境的置信度来最小化熵。最终确保了整个房间的清洁效率。图18中显示了通过信息增益的方法进行路径规划，环境中每个网格的清洁程度不断提高。

图18 信息增益路径规划案例及结果

4.2 单元分解法

通过将机器人自由空间细分为单元的较小区域来确定初始配置和目标配置之间的路径。分解之后，根据单元之间的相邻关系构造连接图，其中节点表示自由空间中的单元，节点之间的链接表明相应的单元彼此相邻 。根据此连通性图，可以通过简单地跟踪从初始点到目标点的相邻空闲单元来确定连续路径或信道。

以下是这种方法的结果。单元分解的第一步如图19（a）所示，通过简单地从配置空间中每个内部多边形的每个顶点绘制平行线段，将多边形在内部和外部都受到多边形限制的自由空间分解为梯形或三角形单元，如图19（b）所示。然后，对每个单元进行编号，并将其表示为连接图中的一个节点。配置空间中相邻的节点在连通性图中连接。该图中的路径对应于自由空间中的信道。然后，通过通道中相邻单元格将初始配置连接到目标配置，可以将此通道转换为自由路径。

图19 单元分解法

5 结束语

本文以吸尘器机器人为例综述了机器人的定位及室内建模技术，并详细介绍了路径规划的概念及算法。结合实例，根据吸尘器传感器不确定性的特点，提出了基于信息理论的路径规划方法，给出了相应结果。本文对机器人路径规划的算法及技术研究，将有助于家用机器人的科技发展。