机器人学——机器人导航_braitenberg

一、反应式导航

机器人可以在没有任何地图信息且不清楚自身所在位置的情况下完成复杂的工作任务，比如机器人寻找光源前行，这样的导航方式称为反应式导航。

1.1Braitenberg 车

Braitenberg车是一种非常简单的目标达成机器人,其特点是传感器与电机之间直接连接。小车自身既没有其作业环境的信息,也没有任何路径规划可言，其工作方式是寻求一个标量场的最大值，如光强或化学物质浓度。
执行这行代码可以看到Braitenberg车例程的simulink仿真

sl_braitenberg
1

传感器函数：

function sensor = sensorfield(x, y)
    xc = 60; yc = 90;
    sensor = 200 ./ ((x-xc).^2 + (y-yc).^2 + 200);
1
2
3

该函数返回传感器值$s(x,y)\in [0,1]$，它是一个平面上传感器位置的函数。当传感器越接近标量场场源时，s越大。当到达目标点时，$s_R=s_L=1$
小车的速度：$v=2-s_R-s_L$。当到达目标点时，小车的速度为0。
转向角：$\gamma =k(s_L-s_R)$
开始仿真：

1.2简单自动机

这类机器人具备感知和避开障碍物的能力，感知和驱动之间加了状态机，如遇到障碍物后逆时针绕行，具备一定的记忆能力。
在此处，重点讨论bug2算法。
首先给出一些假设：

1. 机器人只在网格中活动，且只占一格
2. 机器人不具有任何非完整约束，可以移向任意相邻网格
3. 机器人可以确定自己在平面上的位置
4. 机器人仅可以感知它的下一个位置及目标位置。
   创建一个bug2类：

load map1
bug = Bug2(map);
start = [20,10];%起始点（20,10）
goal = [50,35];%目标点是（50,35）
path = bug.query(start,goal);
bug.plot(path)
1
2
3
4
5
6

bug2算法的路径显然不是最佳,因为沿着障碍绕行至最初路线上耗费时间很多。而且本例中机器人如果顺时针绕行障碍物可能要快很多。bug算法还衍生出很多变种,但它们都是针对某种环境提升了其性能,而对于其他环境则性能会下降。归根结底,不依赖地图使得这种算法的功能受到很大局限。没有全局意识就只能在局部生成最佳路径,但局部的最佳往往不是整体的最佳。

二、基于地图的路径规划

基于对地图的分析，我们可以得到最佳的规划路径，规划的最佳路径不一定最短，要同时考虑可通过性，如路面拥堵性、平整性等。
首先确定地图的表示方法。一个简单且于计算机操作的方式是网格占用法。它是把整个区域划分成若干网格,把每个网格分为占用或非占用。用0表示非占用网格,即机器人的可通行区域,1表示占用网格,即不可通行区域或者说是障碍。即建立一个矩阵，矩阵中0元素代表机器人可以自由移动的空间，矩阵中1元素代表此处有障碍物。
为了简化创建带有障碍物地图的步骤,可以使用“工具箱”中的地图编辑器makemap来创建复杂的地图,它使用了一个简单的交互式编辑

map=makemap(100)
>>makemap:
  left button, click and drag to create a rectangle
  or type the following letters in the figure window:
  p - draw polygon
  c - draw circle
  e - erase map
  u - undo last action
  q - leave editing mode
click a sequence of points, <enter> when done
1
2
3
4
5
6
7
8
9
10

再对机器人做出一些假设：

1. 机器人只占一个网格
2. 机器人不含有任何非完整约束，可自由移动到相邻单元格
3. 机器人可以确定他在平面上的位置（定位）
4. 机器人可以利用地图规划路径

2.1距离变换

考虑只有一个代表目标的非零元素的矩阵。此矩阵通过距离变换得到另一个大小相同的矩阵,但其中每个元素的值是它到最初非零目标元素的距离。在机器人路径规划中,我们使用默认的欧氏距离。距离变换的原理是：机器人沿着距离小的方向前进，类似寻找光源强度。

注：（x1,y1），(x2,y2)两点的欧氏距离可以用$\sqrt{\Delta x^2+\Delta y^2}$表示。

goal = [50,30];
start = [20,10];
load map1
dx = DXform(map);
dx.plan(goal)
dx.plot()
1
2
3
4
5
6

我们可以看见红色的障碍物区域被叠加到距离地图上,其中任何一点的灰度等级表示了它到目标点的距离（颜色越深代表离目标越近）,从而为障碍物绕行提供了依据。

p = dx.query(start);
dx.plot(p);
numrows(p)%查看路径点数
1
2
3

背景材料:超级类Navigation。本章中所给例子使用的类都是从超级类Navigation衍生而出的,这个类是专为基于2D网格的导航设计的。每个例子基本上都包括以下模式。首先,通过调用类构造函数来创建一个基于类Navigation的对象实例。
》nav=MyNavClass(world)
它被传递给占用网格。然后,计算出到达目标的一种规划：
》nav.plan(goal)
该规划可以通过一下命令看到：
》nav.plot()
然后计算从起始位置到目标的一条路径：
》p=nav.query(start)
》p=nav.path()
其中,p是路径,即从起点到目标的一系列点,一行代表一个点,每一行包括点的x和y坐标。如果未指定start(如第二个例子),用户会被提示以交互方式点击选择起点。如果没有输出参数,则会显示机器人运动的动画。

这种方法的缺点是：距离变换对于较大地图计算量较大。

• 距离变换法是如何计算各点到目标点的距离的？

2.2$D^{\ast }$

Dijkstra算法：看这里
要想了解D算法，首先需要学习什么是$A^{\ast }$算法：看这里
D是A*的扩展，在图中从目标规划一条到初始点的路径，使得总成本最低。从目标点出发，根据单元成本，逐步扩散计算每个单元的距离值，保存到密集有向图中，节点包含

1. 单元成本
2. 到目标的距离
3. 与最靠近目标的相邻单元的链接

%D*算法
ds = Dstar(map);    % create navigation object
ds.plan(goal)       % create plan for specified goal
ds.plot();
p = ds.query(start);% animate path from this start location
ds.plot(p);
1
2
3
4
5
6

ds.plan(goal)将产生一个密集的有向图。每个单元是一个顶点,它具有成本,到达目标的距离,以及与最靠近目标的相邻单元的一个链接。每个单元还有一个状态{NEW,OPEN,CLOSED}。起初每个单元都处于NEW状态,只有目标单元的成本是0,状态是OPEN。我们可以将所有的处于OPEN状态的单元看作从目标向外传播的一个波前,计算与OPEN态相邻的即将到达的单元的成本,然后这些单元依次被设定为OPEN状态,最初的单元则从OPEN态移除改为CLOSED态。在MATLAB中这个最初的规划阶段是非常慢的,需要花费几十秒的时间

ds.niter
	ans=10558%以上指令显示了规划循环迭代的次数。
1
2

D星算法的真正威力在于它能在任务中有效地更改成本地图。这种能力在机器人领域非常需要,这是因为实际的机器人传感器量程有限,而且机器人在行进过程中会发现更多不可预知的情况。我们可以采用modify-cost方法告诉D"所要做的修改,例如:

这给的函数有点问题
1

• 我还是没搞懂啥是$D^{\ast }$算法，呜呜呜~

2.3沃罗诺伊路线图法

2.4概率路线图法

2.5RRT

（未完待续）