机器人笔记 - 自动导航

• 导航问题
• 定位 (localization)
• 基于行为的导航(Behavior-based Navigation)
• 基于模型的导航 (Model-based Navigation)
• 传感器噪声
• • 来源
  • 结果
  • 解决方案
• 传感器混叠 (Sensor Aliasing)
• • 是什么？
  • 结果
  • 解决方案
• 里程计Odometry (航位推算 Dead Reckoning)
• • 是什么？
  • 怎么使用
  • 优点
  • 改进
  • 里程碑误差
  • 集成误差的分类
• 地图表示 (Map Representation)
• • 基于行的连续表示 (continuous line-based representation)
  • 精确的单元表示 (exact cell representation)
  • 固定单元格表示 (fixed cell representation)
  • 自适应单元表示 (Adaptive Cell Representation)
  • 地图表示的挑战
  • 拓扑分解 (Topological Decomposition)
  • • 地标感知和连通 (landmark perception and connectivity)
    • 地标地图
    • 模糊地图 (Fuzzy Map)
  • 基于地图定位的步骤
• 规划 (planning)
• • 挑战
  • 机器人路径规划 (path planning)
  • • 从程序角度进行规划
    • 从交流角度进行规划
    • 规划语言 (planning language)
  • 路径规划算法
  • • 意义
    • 虫子算法 (Bug Algorithm)
    • • 虫子1算法 (Bug 1 Algorithm)
      • 虫子2算法 (Bug 2 Algorithm)
    • 最短路径算法
  • 势场算法 (potential field algorithm)
  • • 例子
    • 吸引势场 (Attractive Potential Field)
    • 排斥势场 (Repulsive Potential Field)
    • 两个场的向量和 (Vector Sum of Two Fields)
    • 作用到机器人的行动轨迹 (Trajectory)
    • 吸引或远离(Attractive and Avoidance)
    • 潜在问题
    • 旋转场和随机场 (Rotational and Random Fields)
    • 向量场直方图(Vector Field Histogram)：快速避障
    • • 占据栅格
      • 虚拟力场 (Virtual Force Field)
      • 极坐标直方图 (Polar Histogram)
      • 安全移动的方向 (Directions for safe travel)
      • 漫游过程
    • 波前算法 (Wavefront Algorithm)

导航问题

• 机器人定位 (我在哪？)
• 地图建立 (其他地点是如何和我联系的)
• 路径/动作规划 (我如何到达其他地点)
• 避开障碍物 (我要安全到达)

参照人类的导航方式：

• 全局(global)时：基于地图; 商议性的(deliberative); 慢的
• 本地(local)时: 基于传感器的; 反应式的(reactive); 快的

定位 (localization)

方法：

• 里程计(odometry)，航位推算 (dead reckoning)
• 基于外部传感器，信标 (beacons) 或者 地标 (landmarks) 的定位。
• 基于概率地图(probabilistic map)的定位。

挑战:
机器人要知道其绝对位置(absolute position). GPS并不总是足够的,因为其：
在室内环境中不可用，建筑物反射会导致错误。在水下，隧道，洞穴等中不可用。

路径规划需要的不仅仅是位置。
影响位置估算质量的因素有：传感器噪声，传感器错误，车轮打滑(wheel slippage)，里程表位置估计错误(漂移 drift)

导航的限制(constrains):
在导航的过程中不要碰撞到障碍物。检测目标的位置。

备选解决方案：
始终跟随左墙走，并检测是否到达目标。

基于行为的导航(Behavior-based Navigation)

该导航方法不使用地图或者本地定位。只是对感知到的作出反应。

基于模型的导航 (Model-based Navigation)

定位并且使用地图和地标。

传感器噪声

来源

环境：如表面，照明等…
测量原理：如超声波传感器之间的串扰(cross-talk)

结果

会导致接收的信息不佳。

解决方案

传感器融合 (sensor fusion) 与集成 (integration): 多个传感器，多个时间步骤，整合传感器模型。

传感器混叠 (Sensor Aliasing)

是什么？

传感器在多个可能的姿势或者状态中读数相同

结果

会导致信息不足

解决方案

整合多个传感器，随着时间推移整合数据。

里程计Odometry (航位推算 Dead Reckoning)

是什么？

基于本体感受传感器 (proprioceptive sensors) 而进行位置更新。
里程表：车轮传感器。(wheel sensors)
航位推算法: 航向传感器 (heading sensors)。(如陀螺仪 gyros，加速度计 accelerometers)

怎么使用

机器人的运动由车轮编码器(wheel encoders)感应，并用于跟踪机器人的位置。

优点

直截了当，容易实现

改进

添加额外的航向传感器(heading sensors)如陀螺仪。

里程碑误差

分为确定性误差 deterministic (系统的，例如漂移)和非确定性误差 non-deterministic (非系统的，例如表面不规则)。
校准(calibration)可以消除确定性误差。至于非确定性误差就先不用管。
错误来源： 集成时的解析度(resolution)不够。车轮未对准(确定性误差)。车轮直径不相等(确定性)。车轮接触点的变化。地板接触不均匀(打滑，不平坦…)。

集成误差的分类

范围误差 (range error): 机器人移动的集成路径长度(距离)。(车轮移动距离的总和)
转弯误差 (turn error): 和范围误差类似，但是是考虑转弯的情况。(车轮运动的差异 difference)
漂移误差 (drift): 车轮误差的差异会导致机器人角度方向的误差。

在很长一段时间内，转向和漂移误差远远超过范围误差！

地图表示 (Map Representation)

环境表示(environment representation)包括了: 连续度量 continuous metric (x, y, θ), 离散度量 discrete metric (metirc grid), 离散拓扑 discrete topological (topological grid)

特征的环境建模：

• 原始传感器数据，如激光范围数据(laser range data), 灰度图(grayscale images)。数据量大，个体价值水平的独特性低。利用所有获得的信息。
• 底层特征 (low level features), 如几何特征的轮廓。中等数据量，平均独特性。机器人能过滤出有用的信息，但是仍然含糊不清。
• 高级特征 (high level features)，如门，汽车或者埃菲尔铁塔等。数据量少，特色鲜明。能筛选出有用的信息，且很少或没有歧义。

基于行的连续表示 (continuous line-based representation)

用向量行集表示-假设环境是几何 (geometric) 的。

精确的单元表示 (exact cell representation)

对象的图形表示。将映射分区到基于对象的单元格中。

固定单元格表示 (fixed cell representation)

对象被映射到常规网格中的单元格。即：占据栅格(occupancy grid)。

自适应单元表示 (Adaptive Cell Representation)

用可变大小的单元格和值来表示对象。

地图表示的挑战

细颗粒度(finely granulated)的固定分解网格(fixed decomposition grids)会产生出一个巨大的表格。
这需要巨大的处理能力和大的内存需求。

应对挑战：
降低复杂性: 随机采样(randomized sampling) /粒子滤波 (Particle filter): 通过仅代表所有状态(可能的位置)的"代表"子集来估计近似的状态。例如，仅更新10%的所有可能位置。通常对采样过程进行加权(weighted)，例如，在概率密度函数 (probability density function) 中的局部峰(local peaks)周围放置更多样本。
但是，您必须确保仍能跟踪一些不太可能的位置(less likely locations)，否则机器人可能会迷路。

拓扑分解 (Topological Decomposition)

对地标(landmark)的感知和连通性。地标可以分解。
允许对地表进行组织：即从全局地标到本地地标。也可以按外观背景进行组织。

地标感知和连通 (landmark perception and connectivity)

地标地图

模糊地图 (Fuzzy Map)

基于描述性地图。且通过属性来描述特征。

基于地图定位的步骤

1. 根据先前的估计和里程表进行预测。
2. 内置传感器(on-board sensors)观察。
3. 基于预测和地图的测量预测(measurement prediction)。
4. 将观测和地图进行匹配(matching)。
5. 估算 -> 位置更新 (后验位置)
   

规划 (planning)

挑战

现实世界是动态的。感知仍然是一个巨大挑战，因为其容易出错且提取有用的信息较困难。而对于规划，在开放世界中进行遍历，建立拓扑 (结点边界 boundaries of nodes)，传感器融合 (sensor fusion) 这些都是挑战。

机器人路径规划 (path planning)

机器人路径规划涉及使机器人能够规划自己的动作。自动确定要执行哪些任务才能完成由 初始状态 和 目标状态 以及 物理对象空间布置 所指定的任务。
Agre 和 Chapman (1990) 认为我们的规划方式取决于我们如何使用这些规划。
有两种观点：

1. 从程序角度进行规划 (plan as program view): 计划的使用是有效程序的执行。
2. 从交流角度进行规划 (plan as a communication view): 计划的使用就像遵循自然语言说明一样。

从程序角度进行规划

在该规划方式中：

• 将导航理解为解决问题和控制问题。
  世界向机器人提出了一系列需要解决的正式定义的问题 (formally defined problems)。
  规划者(planner)可以解决由机器人执行的每个问题。
  这种方法类似于欧洲航海家如何估计他在地图上的位置并绘制到达目的地的路径。但是，当一个人指向地图上的某个位置时，导航员通常无法将其航行所经过的物理环境相关联。
• 传感器的输入仅用作监视相对于计划的进度，而不用于修改计划。
• 计划的执行旨在独立于领域(domain independent), 从而使地图的构建在很大程度上取决于领域。
• 计划和地图构造的计算复杂性会随着处理所有可能情况而必须包括的所有详细信息呈指数增长(grow exponentially)。

从交流角度进行规划

在该规划方式中：

• 计划仅在规划中扮演间接角色。
  计划的使用就像遵循自然语言说明一样。
  计划不会直接确定用户的行动方针，而是会就如何实现目标向其提供建议。
  计划是决定做什么的众多信息来源之一。
• 使用计划需要弄清楚如何将其于任务相关联，并且在导航的情况下，必须要具备感知环境的能力。需要特定领域知识(domain specific knowledge)。
• 日常生活世界中并不是一系列需要被解决的问题，而是一系列需要处理的突发事件(contingencies)和需要抓住的机会。

规划语言 (planning language)

许多实现的规划者使用规划语言来表达计划，并使用解释程序(interpreter)来执行计划。
规划语言就像具有一组参数化基元 (parametrized primitives) 和组合运算符 (composition operators) 的编程语言。如：室内服务机器人通常使用从地图得出的一系列走廊和门道来被进行编程。
此外，如果计划将由移动机器人(mobile robot)执行，则计划可以用几何方式 (geometrically) 表达。用精确的几何坐标 (geometric coordinates)，航向 (headings) 和速度 (velcocities) 来描述计划。这样的计划可以在图形显示器 (graphics display) 上查看，由模拟机器人(simulated robot)执行或用于控制实际机器人。

路径规划算法

意义

在结构性不强，复杂或部分未知的环境中，路径的可能数量可能非常多。在这种情况下，使用路径规划算法(path planning algorithm)存储世界地图并规划穿过地图的路径 可能比 搜索存储在内存中的大量已知路径 (known paths) 更为有效。
如果仅对环境有部分了解，或者身处不断改变的环境，则可能在很长一段时间路径的数量都会不够，因此必须使用算法路径规划器 (algorithm path planner)。

大多数路径规划者 (path planner) 将搜索空间(search space) 抽象为 可能的路径图。然后搜索该图以找到最短路径。这种方法在学习环境(learning environment)中自然而然地出现，在学习环境中机器人可能已经遍历了数条路径来绘制世界。

虫子算法 (Bug Algorithm)

虫子算法仅假设环境的本地知识(local knowledge)和全局目标(global goal)。

虫子的行为很简单：

• 虫子1：跟随墙壁 (左跟随或右跟随)
• 虫子2：随着直线移动到目标。

这些虫子实际上都是触觉感知的。
Tangent虫子设计有限距离感测(finite distance sensing)。

虫子1算法 (Bug 1 Algorithm)

步骤：

1. 朝着目标前进。
2. 如果遇到障碍，则绕过障碍并时刻感应并记住自身和目标之间的距离。
3. 在绕了一圈之后，机器人返回到与目标点最近的点(蓝色点) (通过墙跟随) 并往其方向移动直到遇到下一个障碍物(回到2)。
   
   

虫子2算法 (Bug 2 Algorithm)

假设起点到目标之间的直线是M。
步骤：

1. 机器人朝着M线上的目标前进。
2. 如果有障碍物，绕着障碍物走直到再次到达M线。
   
   
   
   为了解决上图的问题，算法的改进可以是：
   当q点再次被访问到了，虫子(机器人)继续跟随障碍物边界。

最短路径算法

1. A* 搜索
2. 广度优先搜索
3. 深度优先搜索
4. D* 算法
5. 等等

势场算法 (potential field algorithm)

例子

球门发出恒定的磁场(field)，吸引机器人。
障碍物会产生排斥力(repulsive field)来排斥机器人。
通过添加和减去势场来确定机器人的方向。

吸引势场 (Attractive Potential Field)

排斥势场 (Repulsive Potential Field)

两个场的向量和 (Vector Sum of Two Fields)

作用到机器人的行动轨迹 (Trajectory)

吸引或远离(Attractive and Avoidance)

目标：被吸引势场(attractive fields)包围。
障碍物：被排斥势场(repulsive fields)包围。
理想结果：在避免和障碍物碰撞的同时朝目标前进。(就像滚下弯曲的表面一样)
动态障碍物(dynamic obstacle)：势场的快速更新可以帮助机器人远离移动障碍物。

潜在问题

• 局部最小值 (local minima): 吸引力和排斥力可能会平衡从而导致机器人无法前进。间隔较近的障碍物或者死角。
  
  
  盒子峡谷问题(Box Canyons Problem)：机器人避免过去的势场，从而陷入死胡同或峡谷中。

• 不稳定的振荡(unstable oscillation): 机器人/环境系统的动态变化可能会不稳定，如高速环境，狭窄走廊，或者突然的变化。

旋转场和随机场 (Rotational and Random Fields)

• 旋转场：
  在障碍物周围添加旋转场，这可以：破坏对称，避免一些局部最小值。并且会引导机器人绕过障碍物组合。
  

• 随机场：
  在障碍物周围添加随机场会避免机器人被困住。避免局部最小值。
  

向量场直方图(Vector Field Histogram)：快速避障

1. 绘制本地占据栅格地图 (occupancy grid map)：限于滚动活动窗口 (scrolling active window)，在声纳束轴(axis of sonar beam)上仅使用一个点。
2. 建立障碍物的极坐标直方图(polar histogram of obstacles): 定义安全移动的方向。
3. 转向控制(转向控制): 在障碍物之间中途转向。在实现全局目标方面取得进展。

占据栅格

给定声纳的传感距离d
沿声纳锥(snoar cone)的中间轴来递增单个单元格 (忽略声纳锥其余部分的数据)

收集多次传感器的读数。多次读数将会弥补不复杂的传感器模型。

虚拟力场 (Virtual Force Field)

机器人周围的Ws x Ws活动窗口(Active Window)。仅用于定义"虚拟力场"的网格。

极坐标直方图 (Polar Histogram)

根据机器人的方向，聚集来自占据栅格的障碍物。

权重(weight)与占用率(occupancy)成正比，且与距离(distance)成反比。

安全移动的方向 (Directions for safe travel)

使用极坐标直方图中的阈值确定移动的安全性。


往安全扇面的中心转向。
如果是墙面障碍物，则该方法能够让机器人跟随墙面移动，并且阈值能够决定机器人跟随时和墙面之间的最小距离。

漫游过程

波前算法 (Wavefront Algorithm)

波前算法考虑在相同成本N( p)的所有到达目标的路线。
波前算法从目标传播(propagates)到当前位置：一个活动点(active point)更新其周围8个邻居(neighbors)的成本。如果某个点的成本降低了，该点就变为活动状态(active)。继续传播直到机器人的当前位置。

通过重新计算成本来处理动态的障碍物。

要求：

• 准确的地图，以及
• 在地图中准确定位机器人。

机器人笔记 - 自动导航

• 导航问题
• 定位 (localization)
• 基于行为的导航(Behavior-based Navigation)
• 基于模型的导航 (Model-based Navigation)
• 传感器噪声
• • 来源
  • 结果
  • 解决方案
• 传感器混叠 (Sensor Aliasing)
• • 是什么？
  • 结果
  • 解决方案
• 里程计Odometry (航位推算 Dead Reckoning)
• • 是什么？
  • 怎么使用
  • 优点
  • 改进
  • 里程碑误差
  • 集成误差的分类
• 地图表示 (Map Representation)
• • 基于行的连续表示 (continuous line-based representation)
  • 精确的单元表示 (exact cell representation)
  • 固定单元格表示 (fixed cell representation)
  • 自适应单元表示 (Adaptive Cell Representation)
  • 地图表示的挑战
  • 拓扑分解 (Topological Decomposition)
  • • 地标感知和连通 (landmark perception and connectivity)
    • 地标地图
    • 模糊地图 (Fuzzy Map)
  • 基于地图定位的步骤
• 规划 (planning)
• • 挑战
  • 机器人路径规划 (path planning)
  • • 从程序角度进行规划
    • 从交流角度进行规划
    • 规划语言 (planning language)
  • 路径规划算法
  • • 意义
    • 虫子算法 (Bug Algorithm)
    • • 虫子1算法 (Bug 1 Algorithm)
      • 虫子2算法 (Bug 2 Algorithm)
    • 最短路径算法
  • 势场算法 (potential field algorithm)
  • • 例子
    • 吸引势场 (Attractive Potential Field)
    • 排斥势场 (Repulsive Potential Field)
    • 两个场的向量和 (Vector Sum of Two Fields)
    • 作用到机器人的行动轨迹 (Trajectory)
    • 吸引或远离(Attractive and Avoidance)
    • 潜在问题
    • 旋转场和随机场 (Rotational and Random Fields)
    • 向量场直方图(Vector Field Histogram)：快速避障
    • • 占据栅格
      • 虚拟力场 (Virtual Force Field)
      • 极坐标直方图 (Polar Histogram)
      • 安全移动的方向 (Directions for safe travel)
      • 漫游过程
    • 波前算法 (Wavefront Algorithm)

导航问题

• 机器人定位 (我在哪？)
• 地图建立 (其他地点是如何和我联系的)
• 路径/动作规划 (我如何到达其他地点)
• 避开障碍物 (我要安全到达)

参照人类的导航方式：

• 全局(global)时：基于地图; 商议性的(deliberative); 慢的
• 本地(local)时: 基于传感器的; 反应式的(reactive); 快的

定位 (localization)

方法：

• 里程计(odometry)，航位推算 (dead reckoning)
• 基于外部传感器，信标 (beacons) 或者 地标 (landmarks) 的定位。
• 基于概率地图(probabilistic map)的定位。

挑战:
机器人要知道其绝对位置(absolute position). GPS并不总是足够的,因为其：
在室内环境中不可用，建筑物反射会导致错误。在水下，隧道，洞穴等中不可用。

路径规划需要的不仅仅是位置。
影响位置估算质量的因素有：传感器噪声，传感器错误，车轮打滑(wheel slippage)，里程表位置估计错误(漂移 drift)

导航的限制(constrains):
在导航的过程中不要碰撞到障碍物。检测目标的位置。

备选解决方案：
始终跟随左墙走，并检测是否到达目标。

基于行为的导航(Behavior-based Navigation)

该导航方法不使用地图或者本地定位。只是对感知到的作出反应。

基于模型的导航 (Model-based Navigation)

定位并且使用地图和地标。

传感器噪声

来源

环境：如表面，照明等…
测量原理：如超声波传感器之间的串扰(cross-talk)

结果

会导致接收的信息不佳。

解决方案

传感器融合 (sensor fusion) 与集成 (integration): 多个传感器，多个时间步骤，整合传感器模型。

传感器混叠 (Sensor Aliasing)

是什么？

传感器在多个可能的姿势或者状态中读数相同

结果

会导致信息不足

解决方案

整合多个传感器，随着时间推移整合数据。

里程计Odometry (航位推算 Dead Reckoning)

是什么？

基于本体感受传感器 (proprioceptive sensors) 而进行位置更新。
里程表：车轮传感器。(wheel sensors)
航位推算法: 航向传感器 (heading sensors)。(如陀螺仪 gyros，加速度计 accelerometers)

怎么使用

机器人的运动由车轮编码器(wheel encoders)感应，并用于跟踪机器人的位置。

优点

直截了当，容易实现

改进

添加额外的航向传感器(heading sensors)如陀螺仪。

里程碑误差

分为确定性误差 deterministic (系统的，例如漂移)和非确定性误差 non-deterministic (非系统的，例如表面不规则)。
校准(calibration)可以消除确定性误差。至于非确定性误差就先不用管。
错误来源： 集成时的解析度(resolution)不够。车轮未对准(确定性误差)。车轮直径不相等(确定性)。车轮接触点的变化。地板接触不均匀(打滑，不平坦…)。

集成误差的分类

范围误差 (range error): 机器人移动的集成路径长度(距离)。(车轮移动距离的总和)
转弯误差 (turn error): 和范围误差类似，但是是考虑转弯的情况。(车轮运动的差异 difference)
漂移误差 (drift): 车轮误差的差异会导致机器人角度方向的误差。

在很长一段时间内，转向和漂移误差远远超过范围误差！

地图表示 (Map Representation)

环境表示(environment representation)包括了: 连续度量 continuous metric (x, y, θ), 离散度量 discrete metric (metirc grid), 离散拓扑 discrete topological (topological grid)

特征的环境建模：

• 原始传感器数据，如激光范围数据(laser range data), 灰度图(grayscale images)。数据量大，个体价值水平的独特性低。利用所有获得的信息。
• 底层特征 (low level features), 如几何特征的轮廓。中等数据量，平均独特性。机器人能过滤出有用的信息，但是仍然含糊不清。
• 高级特征 (high level features)，如门，汽车或者埃菲尔铁塔等。数据量少，特色鲜明。能筛选出有用的信息，且很少或没有歧义。

基于行的连续表示 (continuous line-based representation)

用向量行集表示-假设环境是几何 (geometric) 的。

精确的单元表示 (exact cell representation)

对象的图形表示。将映射分区到基于对象的单元格中。

固定单元格表示 (fixed cell representation)

对象被映射到常规网格中的单元格。即：占据栅格(occupancy grid)。

自适应单元表示 (Adaptive Cell Representation)

用可变大小的单元格和值来表示对象。

地图表示的挑战

细颗粒度(finely granulated)的固定分解网格(fixed decomposition grids)会产生出一个巨大的表格。
这需要巨大的处理能力和大的内存需求。

应对挑战：
降低复杂性: 随机采样(randomized sampling) /粒子滤波 (Particle filter): 通过仅代表所有状态(可能的位置)的"代表"子集来估计近似的状态。例如，仅更新10%的所有可能位置。通常对采样过程进行加权(weighted)，例如，在概率密度函数 (probability density function) 中的局部峰(local peaks)周围放置更多样本。
但是，您必须确保仍能跟踪一些不太可能的位置(less likely locations)，否则机器人可能会迷路。

拓扑分解 (Topological Decomposition)

对地标(landmark)的感知和连通性。地标可以分解。
允许对地表进行组织：即从全局地标到本地地标。也可以按外观背景进行组织。

地标感知和连通 (landmark perception and connectivity)

地标地图

模糊地图 (Fuzzy Map)

基于描述性地图。且通过属性来描述特征。

基于地图定位的步骤

1. 根据先前的估计和里程表进行预测。
2. 内置传感器(on-board sensors)观察。
3. 基于预测和地图的测量预测(measurement prediction)。
4. 将观测和地图进行匹配(matching)。
5. 估算 -> 位置更新 (后验位置)
   

规划 (planning)

挑战

现实世界是动态的。感知仍然是一个巨大挑战，因为其容易出错且提取有用的信息较困难。而对于规划，在开放世界中进行遍历，建立拓扑 (结点边界 boundaries of nodes)，传感器融合 (sensor fusion) 这些都是挑战。

机器人路径规划 (path planning)

机器人路径规划涉及使机器人能够规划自己的动作。自动确定要执行哪些任务才能完成由 初始状态 和 目标状态 以及 物理对象空间布置 所指定的任务。
Agre 和 Chapman (1990) 认为我们的规划方式取决于我们如何使用这些规划。
有两种观点：

1. 从程序角度进行规划 (plan as program view): 计划的使用是有效程序的执行。
2. 从交流角度进行规划 (plan as a communication view): 计划的使用就像遵循自然语言说明一样。

从程序角度进行规划

在该规划方式中：

• 将导航理解为解决问题和控制问题。
  世界向机器人提出了一系列需要解决的正式定义的问题 (formally defined problems)。
  规划者(planner)可以解决由机器人执行的每个问题。
  这种方法类似于欧洲航海家如何估计他在地图上的位置并绘制到达目的地的路径。但是，当一个人指向地图上的某个位置时，导航员通常无法将其航行所经过的物理环境相关联。
• 传感器的输入仅用作监视相对于计划的进度，而不用于修改计划。
• 计划的执行旨在独立于领域(domain independent), 从而使地图的构建在很大程度上取决于领域。
• 计划和地图构造的计算复杂性会随着处理所有可能情况而必须包括的所有详细信息呈指数增长(grow exponentially)。

从交流角度进行规划

在该规划方式中：

• 计划仅在规划中扮演间接角色。
  计划的使用就像遵循自然语言说明一样。
  计划不会直接确定用户的行动方针，而是会就如何实现目标向其提供建议。
  计划是决定做什么的众多信息来源之一。
• 使用计划需要弄清楚如何将其于任务相关联，并且在导航的情况下，必须要具备感知环境的能力。需要特定领域知识(domain specific knowledge)。
• 日常生活世界中并不是一系列需要被解决的问题，而是一系列需要处理的突发事件(contingencies)和需要抓住的机会。

规划语言 (planning language)

许多实现的规划者使用规划语言来表达计划，并使用解释程序(interpreter)来执行计划。
规划语言就像具有一组参数化基元 (parametrized primitives) 和组合运算符 (composition operators) 的编程语言。如：室内服务机器人通常使用从地图得出的一系列走廊和门道来被进行编程。
此外，如果计划将由移动机器人(mobile robot)执行，则计划可以用几何方式 (geometrically) 表达。用精确的几何坐标 (geometric coordinates)，航向 (headings) 和速度 (velcocities) 来描述计划。这样的计划可以在图形显示器 (graphics display) 上查看，由模拟机器人(simulated robot)执行或用于控制实际机器人。

路径规划算法

意义

在结构性不强，复杂或部分未知的环境中，路径的可能数量可能非常多。在这种情况下，使用路径规划算法(path planning algorithm)存储世界地图并规划穿过地图的路径 可能比 搜索存储在内存中的大量已知路径 (known paths) 更为有效。
如果仅对环境有部分了解，或者身处不断改变的环境，则可能在很长一段时间路径的数量都会不够，因此必须使用算法路径规划器 (algorithm path planner)。

大多数路径规划者 (path planner) 将搜索空间(search space) 抽象为 可能的路径图。然后搜索该图以找到最短路径。这种方法在学习环境(learning environment)中自然而然地出现，在学习环境中机器人可能已经遍历了数条路径来绘制世界。

虫子算法 (Bug Algorithm)

虫子算法仅假设环境的本地知识(local knowledge)和全局目标(global goal)。

虫子的行为很简单：

• 虫子1：跟随墙壁 (左跟随或右跟随)
• 虫子2：随着直线移动到目标。

这些虫子实际上都是触觉感知的。
Tangent虫子设计有限距离感测(finite distance sensing)。

虫子1算法 (Bug 1 Algorithm)

步骤：

1. 朝着目标前进。
2. 如果遇到障碍，则绕过障碍并时刻感应并记住自身和目标之间的距离。
3. 在绕了一圈之后，机器人返回到与目标点最近的点(蓝色点) (通过墙跟随) 并往其方向移动直到遇到下一个障碍物(回到2)。
   
   

虫子2算法 (Bug 2 Algorithm)

假设起点到目标之间的直线是M。
步骤：

1. 机器人朝着M线上的目标前进。
2. 如果有障碍物，绕着障碍物走直到再次到达M线。
   
   
   
   为了解决上图的问题，算法的改进可以是：
   当q点再次被访问到了，虫子(机器人)继续跟随障碍物边界。

最短路径算法

1. A* 搜索
2. 广度优先搜索
3. 深度优先搜索
4. D* 算法
5. 等等

势场算法 (potential field algorithm)

例子

球门发出恒定的磁场(field)，吸引机器人。
障碍物会产生排斥力(repulsive field)来排斥机器人。
通过添加和减去势场来确定机器人的方向。

吸引势场 (Attractive Potential Field)

排斥势场 (Repulsive Potential Field)

两个场的向量和 (Vector Sum of Two Fields)

作用到机器人的行动轨迹 (Trajectory)

吸引或远离(Attractive and Avoidance)

目标：被吸引势场(attractive fields)包围。
障碍物：被排斥势场(repulsive fields)包围。
理想结果：在避免和障碍物碰撞的同时朝目标前进。(就像滚下弯曲的表面一样)
动态障碍物(dynamic obstacle)：势场的快速更新可以帮助机器人远离移动障碍物。

潜在问题

• 局部最小值 (local minima): 吸引力和排斥力可能会平衡从而导致机器人无法前进。间隔较近的障碍物或者死角。
  
  
  盒子峡谷问题(Box Canyons Problem)：机器人避免过去的势场，从而陷入死胡同或峡谷中。

• 不稳定的振荡(unstable oscillation): 机器人/环境系统的动态变化可能会不稳定，如高速环境，狭窄走廊，或者突然的变化。

旋转场和随机场 (Rotational and Random Fields)

• 旋转场：
  在障碍物周围添加旋转场，这可以：破坏对称，避免一些局部最小值。并且会引导机器人绕过障碍物组合。
  

• 随机场：
  在障碍物周围添加随机场会避免机器人被困住。避免局部最小值。
  

向量场直方图(Vector Field Histogram)：快速避障

1. 绘制本地占据栅格地图 (occupancy grid map)：限于滚动活动窗口 (scrolling active window)，在声纳束轴(axis of sonar beam)上仅使用一个点。
2. 建立障碍物的极坐标直方图(polar histogram of obstacles): 定义安全移动的方向。
3. 转向控制(转向控制): 在障碍物之间中途转向。在实现全局目标方面取得进展。

占据栅格

给定声纳的传感距离d
沿声纳锥(snoar cone)的中间轴来递增单个单元格 (忽略声纳锥其余部分的数据)

收集多次传感器的读数。多次读数将会弥补不复杂的传感器模型。

虚拟力场 (Virtual Force Field)

机器人周围的Ws x Ws活动窗口(Active Window)。仅用于定义"虚拟力场"的网格。

极坐标直方图 (Polar Histogram)

根据机器人的方向，聚集来自占据栅格的障碍物。

权重(weight)与占用率(occupancy)成正比，且与距离(distance)成反比。

安全移动的方向 (Directions for safe travel)

使用极坐标直方图中的阈值确定移动的安全性。


往安全扇面的中心转向。
如果是墙面障碍物，则该方法能够让机器人跟随墙面移动，并且阈值能够决定机器人跟随时和墙面之间的最小距离。

漫游过程

波前算法 (Wavefront Algorithm)

波前算法考虑在相同成本N( p)的所有到达目标的路线。
波前算法从目标传播(propagates)到当前位置：一个活动点(active point)更新其周围8个邻居(neighbors)的成本。如果某个点的成本降低了，该点就变为活动状态(active)。继续传播直到机器人的当前位置。

通过重新计算成本来处理动态的障碍物。

要求：

• 准确的地图，以及
• 在地图中准确定位机器人。