机器人学8-距离变换

基于地图的路径规划在日常生活中

知道，找到从A点到B点最佳路径的关键是要使用地图。一般来讲最佳意味着距离最短，但也需要考虑道路的可通过性带来的一些代价。可通过性表示驶过某个区域的容易程度，有时走一条距离更远但路况更好的路反而会更快。一个更深思熟虑的规划者往往还会考虑车辆的运动学和动力学，会避开那些存在车辆无法完成的急转弯的路径。机器人的定义：一种能感知、规划并行动的目标导向机械。机器人的规划：表示一张地图以及机器人在其中位置的方法有很多， 法是把机器人位置表示成坐标（x,y）R^2,

把可通行区域或 区表示为多边形，每个多边形都包含一系列的顶点和边线。这种方法可能使表达格式非常紧凑，但要确定机器人和

物之间是否会发生碰撞就会涉及到对每条边线进

试。网格占用法：一个更为简单也更适于计算机操作的方式。它是把整个区域划分为成若干网格，把每个网格分为占用或非占用。用0表示非占用网格，即机器人的可通行区域，1表示占用网格，即不可通行区域或者说是 。单元格的大小取决于具体的应用。随着表示区域的扩大或者单元格的减小，计算机所需

空间都会增加。再给出一些假设：首先，机器人在网格中活动，且只占一格单元格；第二，机器人不含有任何非完整约束，且可以移动到相邻单元格；第三，机器人可以确定它在平面上的位置；第四，机器人可以使用地图计算它要走的路径。背景材料：创建一个地图一个占用网格就是一个矩阵，它对应二的一片区域。>>

map=zeros(100,100);>>

map(20:50,20:80)

=

1;>>

imshow(map);为简化步骤，可以使用工具箱中的地图编辑器makemap来创建更复杂的地图，它使用了一个简单的交互式编辑器：>>

map=makemap(100);makemap:left

button,

click

and

drag

to

create

a

rectangleor

type

the

following

letters

in

the

figure

window:p

-

draw

polygonc

-

draw

circlee

-

erasemapu

-

undo

last

actionq

-

leave

editing

mode背景材料：超级类Navigation本章中所给例子使用的类都是从超级类Navigation衍生而出的，这个类专为基于2D网格的导航设计的。每个例子基本上都包括以下模式。首先，通过调用类构造函数来创建一个基于类Navigation的对象实例>>

nav

=

MyNavClass(world);它被传递给占用网格。然后计算到达目标的一种规划：>>

nav.plan(goal);该规划可以通过一下命令看到：>>

nav.plot();然后计算从起始位置到目标的一条路径：>>

p

=

nav.path(start);>>

p

=

nav.path();距离变换>>

goal

=

[50;30];>>

start

=

([20;10]);>>

load

map1它们分别对应目标点、起始点和世界地图。世界地图被加载到工作空间变量map中。使用上面描述的工具可以改变这些参数，这样占用网格也会改变。创建一个对象DXform，它是从类为了把距离转换用于机器人导航，Navigation衍生出来的：>>

dx

=DXform(map);然后创建一个能达到制定目标的规划：>>

lan(goal);可以将其在屏幕上显示出来：>>

lot();function

n

=

next(dx,

robot)if

isempty(dx.distancemap)error('No

distancemap

computed,

you

need

to

plan');end%

list

of

all

possible

directions

to

move

from

current

celldirections

=

[-1-10-11

-1-1

00

01

0-110

11

1];x

=

robot(1);

y

=

robot(2);%

find

the

neighbouring

cell

that

has

the

smallest

distancemindist

=

Inf;mindir

=

[];for

d=directions'%

use

exceptions

to

catch

attempt

to

move

outside

the

maptryif

dx.distancemap(y+d(1),

x+d(2))

<

mindistmindir

=

d;mindist

=

dx.distancemap(y+d(1),

x+d(2));endcatchendendx

=

x

+

mindir(2);y=

y+

mindir(1);if

all([x;y]

==

dx.goal)%

indicate

we

are

at

thegoaln=

[];elsen

=

[x;

y];endend

%

next%

else

return

the

next

closest

point

to

the

goalload

map1goal

=

[50;30];start

=

([20;10;]);dx

=

DXform(map);lan(goal);lot();上述最艰难的工作完成后，从任意点找到一条到达目标的路径就变得十分简单了。无论机器人从什么地方开始，都会朝着距离目标最近的相邻网格移动，这种算法一直持续，直到抵达目的地为止。寻找一条从点start开始到目标的路径，只需输入：>>

ath(start);之后屏幕上会显示机器人 目标的过程动画。

该路径是一系列点线。如果调用path方法时给定了一个输出参数，则会跳过动画，>>

p

=

ath(start);路径被返回到一个矩阵，每一行代表一个点， 可以讲这些点画出：>>

lot(p);要查看路径包括的点数，输入：>>

numrows(p);ans=205load

map1goal

=

[50;30];start

=

([20;10;]);dx=DXform(map);lan(goal);ath(start);p

=ath(start);lot(p);numrows(p);也可以自己随意设置起始点：>>

p

=>>ath();lot(p);load

map1goal

=[50;30];dx

=

DXform(map);lan(goal);p

=ath();lot(p);可以自己画地图，然后之前的地图都是工具箱里画好的，现在进行路径规划。map

=

zeros(100,100);map(10:30,20:40)

=

1;goal

=

[60;50];start

=

([8;2]);dx

=

DXform(map);lan(goal);ath(start);p=ath(start);lot(p);上述导航算法充分利用了其全局视野，并通过大量计算，发现了最短的路径。相反，bug2算法没有这种全局观，只能舍近求远。当然，这种优化算法的代价算法就是计算的复杂性增加。距离变换的计算是迭代的，每步包含的计算量是O（N），而步数一共是O（N），其中N是地图维度。可以通过以下指令显示距离变换的迭代过程：>>

lan(goal,0.1);它展示出了距离值如同一个波阵而从目标点向外 。波阵面先是向上移动，然后分离为左和右两个部分，在向下移动，最后两个波阵面在沿直线x=32的地图底部发生碰撞。函数中最后一个参数指定了每帧画面之间有0.1秒的暂停。尽管该规划的创建成本高昂，然而一旦创建完成，它就可用于从任何初始点到目标的路径规划。现在 已经把一个相当复杂的规划问题转化为类似Braitenberg机器人处理的简单问题，即仅根据与目标的距离做出局部决策。机器人非常有效地沿着距离函数值减小的方向运动， 可以绘制出其3D图像。>>

lot3d(p);load

map1goal

=

[50;30];start

=

([20;10;]);dx

=

DXform(map);lan(goal,0.1);p

=ath(start);lot3d(p);黑色点线为机器人路线。课后习题：一个真实的机器人具有确定的尺寸，如果想用理想化的机器人点的规划方法，通常的做法是将物大小扩大到机器人半径的一半。尝试使用工具箱函数imorph使物膨胀4个网格单元。map=zeros(100,100);map(20:50,20:80)=1;%

imshow(map);se

=

zeros(7,7);se(2:6,2:6)

=

1;p1

=

imorph(map,se,'max');subplot(1,2,1),imshow(map),title(‘原始图像');subplot(1,2,2),imshow(p1),title(‘膨胀后图像');load

map1se

=

zeros(7,7);se(2:6,2:6)

=

1;%se是结构化元素p1

=

imorph(ma