当前位置:首页 >> 信息与通信 >>

一种基于激光雷达的移动机器人环境建模新方法_图文

维普资讯 http://www.cqvip.com

20 0 7年 1月   第3 5卷第 1 期 

机床 与液 压 
MAC NE TOOL & HYDRAUL CS HI   I  

V0. 5 No 1 13  . 

J n ay2 0   a u r 0 7



种基 于 激光 雷 达 的移 动机 器人 环境 建 模新 方 法 
戴博 ,肖晓明, 自兴 , 蔡 邹小兵 
( 中南大学信息科 学与工程学院 , 湖南长沙 40 8 ) 10 3 

摘 要 :环境建模技术是 自主式移 动机器人导航研究 中的一个重要环节。本文在分 析当前普遍采用 的一些环境建 模方法  及其缺 点的基础上 ,针对 复杂环境下移 动机器人 的导航任务提 出了一种结合栅格法 和改进 A B V N法的环境建模 方法 。该方  法首先读取激光雷达数据来建立栅格地 图 ,再通过栅格扩 张形成一个 由可行路径所 组成 的网络拓 扑图 ,从而可利 用图搜索  优化算 法得 到从起始点 到终止 点之 间的一条最短路径 。此方法 的鲁棒性和有效性通过笔者 自行研 制 的移 动机器人 I O 及  MR I 其 H MI G策略得 到了验证 。 O N  

关键词: 激光雷达 ; 移动机器人; 环境建模 
中图分类号:T 2   P4 文献标 识码 :A   文章 编号 :10 — 8 1 (0 7 — 1 5 0 1 3 8 2 0 )1 0 4—  

A  w  n io me t lM o ei gM eh d f rM o i   b tBa e   n La e   d r Ne E vr n n a  d l   t o  o   b l Ro o   sd o   s rRa a   n e
DA   o I B 。XI   a mi g AO Xio n ,C IZ xn Z   a b n   A   ii g, OU Xi o i g

( o eeo  fr t nSin ea dE g er g C nrl o t  nv rt,C a gh   u a    0 3 C ia  C l g f no i  c c n  ni ei , e t   uhU i sy h nsaH n n4 0 8 , hn ) l I ma o e n n aS ei 1
Ab ta t sr c :En i n na  d l gtc n lg sa mp r n ee rhpo esi h   a iain su yo  ea tn m u  bl  vr me tlmo ei  e h ooy i n i ot t sac   rc s nten vg t  td   ft   uo o o smo i o n   a r o h e o o. h  n i me tlmo ei   to sw ih ae pe ae ta o td a dteds v a e ft s  td   eea ay e . o   rb tT ee vrn na  d l g meh d   hc  r  rv ln d pe   n  h   i d a tg so  e eme o sw r  n lz d C m- o n a n h h bn d te G ismeh d a d i rvd AVB   to ie     rd  to  n  mp e   h o N meh d,a n w E vrn na  d l gmeh   a  u ow r  hc  same  o  e   e   n i me tlmo ei   to w sp tfr ad w ih i i d frt   o n d   h
n vg t n o   b l  b t n c mp e   n i n n .   rt h i meh   u l sa g i s ma   t   e d t m  ft e ls r rd r h n i a ia i   f o mo i r o    o lx e vr me t Atf s ,t s eo i o i   to b i     r   p wi t   au o    a e  a a ,t e  t d d d h h h   o msa t p lg c n t r   g t o g   d e p n   t d,c n e u nl   h r s p t  ewe n s r p i ta d e d p i t sg t n f r    o oo ia  ewo k f   r u h g i  x a d me o l i h r h o s q e t a s o e t a b t e   t t o n    n   o n    ot   y t   h a   n wa e t r u h t e o t z d g a h s a c   g rt m. h  o u t e s a d v ii   f h sme h d w r   e f d t r u h t e I 0   b l  b t h o g  h   p i e   r p -e r h a o h T e r b sn s    a d t o   i mi l i n l y t   t o   e e v r e  h g  h  MR 1 mo i r o   i i o eo d s n d b   u s le   n  h   e i e   y o r ev s a d t e HOMI   t tg . g NG s ae   r y Ke wo d y r s:L s r rd ; Mo i   b t n i n n a mo ei g a e  a a r b l r o ;E v r me t   d l   eo o l n

O 引言    智能移动机器人是一类能够通过传感器感知环境  和 自身状态 ,实现在有障碍物 的环境 中面 向目标的 自   主运动 ,从 而完 成一 定 作业 功 能 的机器 人 系统 ¨    。。 近年来 ,移动机器人技术在工业 、农业 、航天及空间  探测等许多领域都起到 了重要 的作用 ,同时又显示了 

避障和规划。因此本 文将采用德 国 SC IK公 司生产 的  L 21 MS9 激光雷达 ( 图 1 见 所示 ) 进行实 验 ,它与计  算机之间主要通过 串行 口进行通信 。   在移动机器人相关技术的研究 中,导航技术是其  核心 ,而导航 的关键在于建立一个合理有效的环境模 

广泛 的应用前景 ,因而成为 国际学术界研究和关注的  热点 问题 。  
车 载 传 感 器 是  移动 机 器人 感 知环  境 的媒 介 和 重要 手 

型 ,以此来描述机器人 的工作环境 。在此基 础上再执  行导航任务的其它环节 ,比如路径规划等。所谓环境  建模是指建立合理 的数学模型来描述移动机 器人的工 
作环境 。所谓路径规划是指移动机器人按照某 一性能 

段 ,常 见 的传 感 器  包 括 声 纳 、摄 像 机 

指标 ( 如距离 、时 间、能 量等 )搜 索一 条从 起 始状  态到 目标状态的最优或次优路径  。   从 目前的研究来看 ,环境建模的方法主要有栅格 
法 、拓扑图 、路径 图和 V r o 图等 。 o ni o   栅格法 用 网格描述机器人 的工作环境 ,根据栅 

等。近 年 来 ,基 于  激 光 测距 的传 感 器  ( 激 光 雷 达 ) 在  即
移动 机 器 人 的 导航  中 应 用 日益 广 泛 ,   这主 要 是 因 为 激 光  测距 范 围广 、精 度  高 、传 输 速 度 快 ,   适合 机 器 人 的实 时 

格的可信度值 可确定 出障碍物 的分布 ,此时通过避 障  规划就可得 到无 碰路 径 。每 个栅 格可 以赋 予一 个数  值 ,可取为 0或 1 。其 中,0表 示 自由栅 格 ,意味 着  没有被障碍物所 占据 ;1 表示障碍 栅格 ,意味着被 障  碍物所 占据 。栅格 法易于构建且对环境 的描述较为精  确 ,但缺点在于空间和时间复杂度较大 。   拓扑 图法  将环境描述为一系列 的点集 ,该方法  对于环境 的构造 比较简单 ,空间复杂度较低 ,不需要 

图 l 激光雷达及其云台 

基金项 目:国家 自然科学基金重点资助项 目 ( 03 00 ;中南大学科学研究基金项 目 ( 8 1— 6 7 ) 6 24 3 ) 1 1 7 16 

维普资讯 http://www.cqvip.com

第l 期 

戴博 等:一种基于激光雷达的移动机器人环境建模新方法 

- 5? 1  

机器人的精确位置信息 , 但该方法对于环境的理解 比   较抽象 ,在大范 围环境下很难保持有效性 ,并难 以区 
分出2 个相 似环境 。  

( )可 以把激光雷 达测 量 的距 离信 息映 射到世 界 坐  1
标系 中:  

路径图法 将 环境也描述成为大量 的点 ,并且 在  此基础上把各个点之 间用直线连接起来 ,对于环境 有 
较好的理解 ,但所产生 的节点数相对较多 ,运算 复杂 
度较高。  

{y x y ' , = : x
r ,

+ +

d.co    a      a +  2 s ,   (   d i


c  



{ '.n2 Ii/ t;  nw+   Y   i ) xt   /  ()i ,  ?    x w ( = :y w
其中 :( ,  表示 障碍 点    Y) 在世 界 坐 标 系 中 的 坐 标 ,  
( ,Y )表 示 机 器 人 中心     

( 2 )  

V rni o o 图  是 由俄 国科 学 家 G V rni 10  o . ooo 在 9 8

年提出的一种计算几何方法 ,最初用于平面点的区域  划分。它将环境分 割 为多个 V rni o o 多边形 ,每个多  o 边形内的任 意一点到本多边形发生点的距离都 要小 于  到其 它多边形 的距离 ,这样就可形成 一幅包含节点 和  边 的链 接 图,每 条 边 就 代 表 一 条 可 行 路 径 。构 造  V rni ooo 图的方法 主要 有基 于矢量 的方 法 、基 于栅 格 

在世 界 坐 标 系 中 的 坐 标 ,  
( ,Y ) 为栅格 在 世 界 坐     

标系 中的坐标 , 为栅 格的   
宽度 。d 表示激 光雷达 通过 
图 2 激光雷达数据  的坐标转换 

测量 所 发 射 的 激 光 束 返 回   时间 而 得 到 的 距 离 值 , ,     表示移 动机 器人 前进 时 的航 向角 ,  

逼近的方法 两种 。矢量方法包括增 量法 、间接法和分  治法等 ,其 中分 治 法 可 将 大 的环 境 分成 几 个 小 的  V rni o o 图来构造 ,最 后再 融合 为一 幅完 整 的、大范  o
围的 V mni ,所 以它的应 用较多 。有学 者提 出 了 o o图  
广 义 V rni 图 (G nrle V mni i rm; o o o eeazd o o i  Da a   g G D) 方法 ,它能在 机器人 的避 碰规划 中直接 描述  V  

表示 激光束 相 

对于激光雷 达的夹角 ,具体情况如图 2所示 。  

通 过公式 ( )可 以将 障碍点 坐标映射 到栅 格地  2
图中相应的栅格上 。经过 以上两次转化可以将激光雷 

达的测量数 据转换到栅格地 图上 。为了简化模型便于  移动机器人建模和规划处理 ,在栅格地图中将所有 的 

出可行 区域 ,但 由于实时较难提取障碍实体 的关键特  征点 ,所 以不太适合于复杂环境的建模 。  
由上可知 ,在复杂 环境 下移 动机 器人对 于环境模 

障碍物 向外 扩张 i ( / 个栅格 , n    ) t  
作一 个质点考虑 。  

为移 动机器人 

外切 圆半径 ,这里 取 为 5 c 4 m,如此 就可把 机器人 当  

型的要求很高 ,一般 的建模 方法往往无 法奏效 ,单独 


种建模方法也很难适应环境 的变化  ,为此本文提  ]

此 时 ,通过公式 ()对栅格数组进行赋值 : 3  
M p  儿Y ]   a[   =1 () 3 

出了一种结 合栅格 法和改进 近似 V m o 边界 网络法  o ni
( prx a   o ni ona   e ok,即 A B   ) A p i t V r o B udr N t r o m e o   y w VN  

( )T ID ( 次读 取所 有 激光雷 达数 据并 给  3 HR 依

的环境建 模方 法。该方 法具 有 较好 的适 应性 和容 错 

局部栅 格地 图赋值 )  
1 2 A N 模 型  .   VB

性 ,适合于移动机器人在复杂环境下 的导航 。  

1 环境 建模方 法 
由于移动机器人主要通过 2个环节来理解环境信  息 ,即感知和认知 。所 以本文采用栅格 法将从感知层 

AB V N方法将栅格空 间划分为 自由集合 与障碍集 
合 ,其模型 的建 立 主 要 采 用 二 值 图像 的数 学 形 态 

学… 的方法,基本变换为具有对偶特性的膨胀和腐    蚀运算。障碍集合的膨胀意味着 自由区域的腐蚀 ,障   碍集合 的腐蚀意味着 自由区域的膨胀。  
膨 胀运算 。膨胀运算 的直观结果为障碍子集 向 自   由区域扩展了一定 的相邻栅格 ( 3 。 图 ) 
腐蚀运算。腐蚀运算 的直观结果为障碍区域被 自  

所得 到的环境信息记录下来 ,再 利用 A B V N方法建立 
合理 的认知模型 。   1 1 栅 格模 型  .

建立栅格模型 的步骤可 以描述如下 :   ( )S A T ( 1 T R 初始 化局部 区域栅格模型 )  

采用二维数组来描述一个局部区域栅格模 型 M p a 
[0 ] [0 ] 4 0 40 ,其维数 取为 4 0× 0 ,并对每个单位  0 40

由子集侵入了一定 的相邻栅格 ( 4 。 图 ) 

栅格赋予初始数值 3  。 ( )S C N ( 2 E O D 对从机器人底层 模块传 递来 的激 

光雷达信 息进行处理 )  
所获得的激光雷达信息是物体距离激光雷达的距 

离数据 ,而该数据不是针对实际 的世界坐标系 ,因此 
在利用该数 据之 前必 须 先进 行坐 标转 换。通过 公 式 

一 一 
图 3 膨 胀 运 算  图 4 腐 蚀 运 算 

维普资讯 http://www.cqvip.com

?

l ? 6 

机床与液压 

第3 5卷 

建立 A B V N模 型的步骤可 以描述 如下 :  

( )S A T ( 上述栅格地 图进行 预处理 ) 1 TR 对  
预处 理的规则 如下 :  

I ( F 障碍栅格周 围 n×n的空 间内有障碍物 )   ( 障碍栅格 向外扩张充满 ( 1 ×( 一1维 空  将 n一 ) n )

间 ,即进 行障碍膨胀运算 )  

E S 将该栅格变为 自由栅格 ,即进行障碍腐  LE(
蚀运算 )  

上述规则能把 相 隔很 近 的离 散障 碍信 息融 合起  来 ,这样 可减少 环境建模 的复杂度 ,避免走入障碍物  之间的狭窄区域 ,对 于消除传感器 的测量误差有较好  的效用 。这里  的选 取幅度要综合考 虑机器人通过半 
径 、定位误差 、传感 器检测误差等 因素。  

图 8 新扩张策略的边界显示 

图9 单向搜索 

首先 给所 有黑 色 
栅格赋予 一个相 同 的 

数值 ,再从 节点开 始 
搜索相邻黑色栅格 ,  

()S C N ( 2 E O D 根据地图中每个栅格的数值来区   分出 自由区域 、未知区域和障碍 区域 )   ( )T I D ( 3 HR 采用栅 格扩张的方法进行处理 )   处理过程 如下 :使 障 碍栅 格 向 自由 区域进 行 腐  蚀 ,同时地图边 界也作 为障碍 向内部 自由区域进行扩  张 ,当 2 不 同的障碍 栅格 相遇 时就会 形成 V mni 个 o o   边界 ,当 3 或 3个 以上 的 障碍 物相 遇 时就会 形 成  个 V m o 节点。最后 可形 成一个 由节点 和边组 成 的 网 o ni   络拓扑图,每个节点至少有 3 条边,一条边连接 2 个 
节点 。  

搜索过 的黑色栅 格将 
被赋予其 他数 值 ,这  样 当搜索 到 图 9中 的  红色栅格 时 ,其周 围  8 域 内就 无 黑色 栅  邻 格 ,算法将终 止无 响  应 。对此 ,我 们将 一  个黑色栅 格 8邻 域 中 
所有搜索 到 的黑 色栅 

格都保存 下来 ,当搜 

( )F U T ( 网络拓扑 图中的节点和边进 行  4 O RH 对 搜索得出边长和节点排列顺序 )   计算边长的算法采用 的是 8邻域搜索方法。  

索到红色 栅格后 找不 
到其它黑 色栅 格 ,算 

由此就可完 成一个 区域的环境建模 ,该方法具有  可行 区域明显 、节点数 目较少等优点 。  
13 A B .   V N方法的 改进  13 1 A B . .  V N建模 过程的改进 

法就 自动 移到蓝 色栅  格 ,再进行搜 索就 可 

图1 新搜索策略流程图 O  

保证算法不会 终止 。该 方法 需建 立 2个 表 :Sa hd er e  c

和 U s hd ne e ,分别存 放待 搜 索节 点和 已搜 索节 点。  ̄c  
其流程 图如图 1 O所示 。   13 2 A B ..  V N的其它改进 

匿 ■ ■ 
图 5 四邻域扩张 图 6 八邻域扩张  图 7 边界失真 

AB V N方法对 于普通离散块状 障碍物 的建模 具有  较好 的效果 ,但如果应用 于复杂室 内环境时会 出现如 
下 3个问题 ,下面分别进行说 明和改进 :  

首先 ,A B V N方法针对 U型 、环型等障碍 物扩张 

就会带来 一些 明显 缺陷 ,如图 1 a 1( )为通过 原始障 
碍信息所建立的环境模 型 ,可 以看到这样形成 了一个 

针对第 三步 的栅格 扩张方法 ,当前普遍采用的是 
四邻域 ( 5 和八邻 域方法 ( 6 ,采用这 些 方  图 ) 图 ) 法会导致边 界非平 滑和失 真 ( 7 。为此本 文设 计  图 )

闭环路径 ,其典 型实例 为室 内环境 中只包含一个入 口   的房 间,机器 人将 无 法进入 其 中完成 导航 任 务。为 
此 ,我们在 A B V N建模 步 骤 中额 外增 加一 些 虚拟 障  碍 ,再按照上述 A B V N方法进 行二次 建模就可解决该 
问题 。   判断虚拟障碍的规则如下 :  

了模糊判决 的方 法 ,设 P为 每个 障碍栅 格 向各 方 向   扩张的概率 ,以 F(, ) i _来表 明当前栅格是 否被 占据 , 『  
i _表示 当前 栅 格 的 坐标 ,m 和 n表 示 扩 张 范 围 和『  

( 这里 都取 一1 1 ,a为常数 ( 到 ) 经过测试 将其取 为 
2有较好 的效 果 ) 。由此我们可 得 出如下 公式 ,其扩 
张效果见 图 8  。 P F i m, +n =1 F i. ( ( + . )   (, )=1 =e  f I   f ) 一  一  (   )

S A T ( 用模糊 判决方法进行栅格扩张 ) TR 采  

I ( 白相 同 障 碍 实 体 的栅 格 扩 张 相 遇 ) F 源  
(D A D虚拟障碍 )  

维普资讯 http://www.cqvip.com

第1 期  ES ( L E 略过 )  
END 

戴博 等:一种基于激光雷达的移动机器人环境建模新方法 

? 7? 1  

动机 器人 的可 行路 

如图 1 b 中的蓝色条状物体 即为所增加 的虚  1( ) 拟障碍。  

径拓 扑 结构 ,从 而  把机 器人 的路 径规 
划 问题 转 化为 拓扑 

第二方面,如果障碍物的形状很不规则 (   如图
1 a 中的障 碍 ) 1( ) ,就有 可能 生成 一些离 散 、微 小  的虚拟障碍 ( 1 b 图 1( )中的绿色小块 ) ,这会带来 


图中给定 2个 节点  ( 即起 始 节 点 和 目   标节点 )间 的最短 
路径 问 题。在 图论  中有很 多 求解 此 问 
题 的方 法 ,采 用较 

些多余 路径 ( 1 b 中的红 色线 段 ) 图 1( ) ,因此 有 

必要将其 除去 ,其过滤算法如下 :   S R T ( 出每个虚拟 障碍周 围 n×n维空 间 内 TA 得  

其它虚拟障碍的出现次数 , 记为 m)   TE ( H N 设置一个阈值p  ) I( P ( F m> )保留该障碍栅格)   I( : )( F m< P 将该 障碍栅格置为 自由栅格 )  
END 

常见 的 图搜索算 法 

( Djsa 如 i t )计 算  kr 得 出 一 条 次 优 路  径 ,然 后对 此 结果 
进行 优 化处 理 ,优  化算法如下 :  
图 1 路 径优化算 法流程 图  3

最后的处理结 果 可见 图 1 c ,可见 绿 色 的虚  1( ) 拟障碍已经被去除掉。通过多次仿真实验我们得到,  
将  取为 4而P取为 4能得 到较好 的过滤效果 。  

算法 中包括初始 节点 i 比较节 点 和 临时节 点  、
n (,) ,L i .表示节点 i . 间的连线 ,更新 _ 『 和『 之 『 的规则 

■■■ 
() - 原始障碍信息建模  () c b 虚于 障碍建模  l () c c 虚于 障碍过滤处理  l

是寻找次优路径上 与 i 相隔最近的后继节点 ,流程图 
可见 图 1 。 3 

为了验证 上述建 模 与 规划 算 法 ,笔者 建立 如 图 

1 4的仿真环 境 ,采用 P 、17 4 .G的计 算机 进行运 算。   构成 了包含一个 2 4个节 点 的网络拓 扑图 ,完成建 模  过程所 需时 间约 为 32。并 给定 起点 与终 点 ,应 用  .s Djs a 法进 行 了 规划 实 验 ,规 划 时 间 为 0 29 。 i t算 kr . 1s   图中蓝色曲线就代表所求 
出的次优路 径 ,其 长度为 

图 1 特殊类 型障碍 物建模显 示    1

第三方面是采用何种 方式对 未知 区域进行 处理 。   AB V N建模方法将地图边界也 作为障碍 物向内部进行 

扩张, 如此一来,对于室内复杂环境障碍物 ( 譬如  个房 间)就会生成 一些虚假 路径 ,如图 1 ( )所  2 a 示 ,因为实际 中这些路径是不可行进的 ,所 以应该将  其除去。为此 本文将 未 知 区域 与某 些 障碍 区域 ( 这  里是指处 于 自由区域与未知 区域之间的障碍区域 ,可  见图 1 ( )中的红色 区域 )相融合 ,这样就可以得  2 b 到图 1 ( )的环境模型 ,显然这样就能避免 出现 虚  2 b


79个 单 位栅格 。然后 利  5 用优 化算法进行处 理得到 
了一条 接 近最 优 的路 径 ,   图中以黑色曲线表 示 ,其 

长度 为 691 单 位 栅  2.3个 格 ,可 以看 到该路 径的长  度要大 大 小 于前 一 路径 ,  
实验证明该优化算 法具有  较好的性能。  
图 1 路径规划及其优  4
化算法仿真演示 

假路径 。  

3 实验过程与分析  针对复杂环境 机器人导航任务 的特点 ,本文设计 
了如下 H M N O I G实验策略 :   为 了模拟移动机器人在未知环境 中的一些导航任 

务 ,比如月 球 车 在 月 球 表 面 执 行 了 某 些 探 测 任 务 
( 如采集 了地表的岩石标本 )耍返 回发射舱 ,如果能 
( ) a 虚假 路径 显示  ( ) 理后 的 环境 模型  b处

选择一条最短路径 ,一方面可以减少不必要的燃料消  耗 ,另一方面也可 以避免进入新 的未知 区域而带来一  些难 以预料 的困难 。为此可使机 器人从起始点所在的 
房间开始进行探测 ,在到达 目标点之后 马上建立所探 

图 1 虚假路径 的处理过程显示  2

2 路径 规 划方 法  在路径规划 中,本 文通 过上面介 绍的方法建立移 

维普资讯 http://www.cqvip.com



l   8-

机床与液压 

第3 5卷 

测区域的环境模 型 ,再采用上述规划方法得 出一条最 

为 8m,所 以其 真 实长 度为 2 .8 。红色 曲线 代表  c 92 m

优路径 并使机器人沿着该路径返 回,如果途 中碰 到新  障碍 ( 如人等 )就 进 行反应式 避 障 ,随后继 续 沿着 
该路径前进直到返 回起始点 。  

优 化处理后 的路径 ,其长度为 3 84个栅格 ,其 真实  2. 长度为 2 .7 m。可以看 到 ,在此非 常复杂的环境下  62 3 该优化算法还是能减少一定长度的路径 ,具有较好 的 
适应性 。实验 中机器人沿着红色路径能够 平稳 、安全 

在 H MN O IG策 略 中,当机 器 人行 走 的时候 ,每 
隔一段 时间会更新地 图信息 ,体现了对于复杂未知环  境 的一个逐 步认知作用 ;而在机器人到达指定 目标 的  时候 ,此 时就能生成一 幅对于整个所探测环境 的全局  地图 ,体 现了对于复杂环境的一个完全认知 过程 ,这 
也能反映出移动机器人 的智能性和 自主性。   根据以上所论述 的方法 ,笔者采 用 C+ 和 Vs— + i   u a C+ 60开发 了环境建模与路径 规划实验平 台 ,实  l +.   验环境可以描述 如下 :  

地返 回到起始点 ,证明 了此建模方法的准确性 和有效 
性 

整体环境包括 5个房 间和一条走 廊 ,其 中障碍 物  有桌子、凳子 、纸箱 子 、石头 、木块 等,包括结构 化  和非结构化的障碍物 ,属 于比较复 杂的环境 ,部 分真 
实场景可见图 1 ;另外 ,由于有 3 房间门的宽度 相  5 个 对较窄 ,几乎与机器人车体半径相 当 ,这也加大 了试  验 的难 度。每个 房 
间的面积约为 8   m×
图 l 室内复杂 环境的感 知与建模 ( 7 包括房间与走廊 )  

4 结论 
为了实现复 杂环境 下 移动 机器 人 的导航 ,对 于 

8 m,楼 道 部 分 约  3 m×3 m。机 器 人  2 以漫 游方式 在环境  中进行 感 知,漫 游  采取沿墙走的策略 ,  

复杂环境 的建模 与识别 一 直是 机器 人研 究领 域 的热  点 问题 。本 文针对 传统 的移动 机 器人环 境建 模方 法  在 识别复 杂环境时所碰 到 的难 题提 出 了一种 结合 栅 
格 法和改 进 A B V N法 的环境 建模 方法 。该方 法 的优 

由此 可获得 所需 的 
栅格地 图,一个 栅  格对应 实 际环境 中  
8m× c c 8m的面积 。  

点 是容错 性和适应 性较好 ,仿 真 和实验 也验 证 了该 
方 法 的有效 性 。下一 步 的工作 是将 该 方法用 于 复杂 
图 1  实验环境部分真实场景  5

室外环境 中 ,期盼 能为移 动机 器人 的实际应 用 提供  更 好 的借 鉴。  

通 过 自行研制  的智能移动 机器人 
IR 1 ( 图 1 ) M O 见 6 

参考文献 
【 】欧青立 , 1 何克忠 .室外智能移动机器人的发展及其相 
关 技术 研 究 [ ].机 器 人 ,20 ,2 ( ) 1   J 0 0 2 6 :5 9—
5 6  2.

进行实 验 ,最后 建  立的环 境模 型可见  图 1 ,其 中总的节  7 点数为 4 。图中没  1 有 障碍 实体 的邻近  区 域 ( 数 字 标  用 出 ,如 1—9等 )   代表该 处增 加 了虚 
图 l 智能移动机器人 I 0  6 MR 1

【】 自 , 2 蔡 兴 贺汉根 , 陈虹 . 未知环境中移动机器人导航控 
制研 究 的 若 干 问 题 [ ].控 制 与 决 策 ,20 ,1  J 02 7
( ) 3 5— 9 . 4 : 8 30  

【】 3 李磊 , 叶涛 , 民,等 . 谭 移动机器人技术研究现状与未 

来 []. J 机器人, 02 2 ( ) 45 40 20 , 4 5 : 7 - 8.   【 Sbsa hm, m  iknItri  r — a d d 4 ea i Tn A o i e. e an G d Bs     1 tn Bc n g tg i ea n
T pl ia MasfrM bl R btN v a o [ .I  oo g l p o  o i  oo ai t n c] n oc  e   gi
P o ednso  eT i enh N t n lC nee c n A t — rce ig f h   hr e t  ai a  ofrn eo   ri   t t o i f
ca  n el e c ilI tl g n e,AAAI o t n i ,P r a d,Org n,Au u t 1 9   l eo g s 9 6,   2: 4 9 4—9 0  5.

拟障碍。黑色 区域代表机器人未探测到的区域 ,红 色  区域是 由机器人探测到 的障碍物分布信息 ,淡紫色区  域代表已探测到 的 自由区域 。显然 ,自由区域和障碍  区域合起来就组成 了机器人所探测到 的全部 区域 。图 

【 】Sbsa hu.e n g e c t o g a m p rn 5 eatn r La i   t —o l i l aso i  i T n rn m r i poc  f  —
do  oi o o nv ai [ ]. rf il neiec , or b er t ai t n J A ic   tlgn e m l b  g o ti a I l  
19 , 9 ( ) 2 — 1 98 9 1 : 1 7 .  

中蓝色 曲线代表 起 始节 点和 目标 节点 之 间的次 优路 
径 ,其 长度 为 36个栅 格 ,注意到一个栅格实际对应  6

( 下转第2 1页)  

维普资讯 http://www.cqvip.com

第1 期 

赵杰 等:一种求解车问作业调度问题的改进遗传算法 

? 1? 2  

第 1步 :初 始 化 产 生 包 含 P个 可 行 解 的 种 群  P k ,P为种群规模 ; ()  
第 2步 :计算个体适应度 ,评价个体适应度值 ;   第 3 :判断是否达到终止条件 ,若符 合取最 优  步

l g ps,pee t n   tr [ ]. uo enJunl f i : at rsn  df ue J E rp a ora o  n a u  
R sac ,19 eerh 99,13 ( ) 9 4 4  1 2 :3 0— 3 .

【】R D M E    ,WHT    .A r et u e o p — 2 O A M RFA I KP   cn sr y f r   E e   v    o dco ceun [ ].E E TasS C 98 8 utnshdl g J IE   r   M ,18 ,1 i i n  
() 4 —5. 6 :8 1 8 1  

个体为问题的解 ,结束算法运行 ,否则转第 4步 ;   第 4步 :将父代放入过渡群 q中 ;  

第5 : 步 按交叉概率P 产生的子代放入过渡群 q     中,按变异概率P  和基于邻域搜索的变异算子,生  成新子代个 体放入过 渡群 q中;   第 6步 :利用联赛选择方式 ,由过渡群 q 生新  产 代的种群 P J ) ( +1 ,返 回到第 2步 。 }   2 实例 验证  ( ) 利 用 本 文 算 法 ,m  1 l 对文献 [ ] 中的表 1 示  2 4 所   实例进 行 求 解 ,在 交 叉 概 m  3 率 P = . ,c=1   08 ,变异 概  率P o1  : . ,A= ,种群规  图3 机器甘特图 3   模 P=10,最 大代 数 4 0 0 0  时 ,在 5 6代 得 到 了最 优 解 [ 2 13)(    )(    (   3 12 2 3 1] ) ,机器甘特图如图 3所 示 ,m k sa  1 a e n 1比实例  p 的 m k sa 1 aepn= 2更优 ,为此问题的最优解 。   ( ) 以 Mu   dT o po ’ M )基准问题来  2 t a  h m sn S( T hn 对改进 的遗传算法进行测试 ,与其它文献利用遗传算  法解 ( )基准 问题 结果进行 比较 ,验证本文所 设  MT 计遗传算法的有效性。这些方法包括 Gn e 算法、G / A  G T等。实验具 体参 数如 下 :交叉 概率 P = . ,c=   08   2 ,变异概率 P 0 1  = . ,A= ,种 群规 模 P=40 4 0 ,最  大代数 10 ,实验结果如表 2所示 。 00  


【】张长水,沈刚,阎平凡 .解 J — o 调度问题的一个  3 oS p bh 遗传算法 [].电子学报,19 , 3( ) 1 5 J 95 2 7 : — .   【】玄光男, 4 程润伟 .遗传算法与工程设计 [ M].北京:  
科 学出版社 ,20 , 00  

【 】顾擎明,曹丽娟 .解 J - o 调度问题的 自 5 oS p bh 适应遗传  方法 []. J 控制与决策,19 ,1 5 : 8 — 9 . 98 3( ) 59 52  
作者简 介 :赵杰 ( 90 ) 18 一 ,男 ,山东 济南 人 ,硕 士 

研究生,主要研究方向:制造业信息化过程中的实时协调 
控制与重构 的方法 与应用 。电话 :159460 38064 ,E— a : mr l  
zaj l 120 @ yh oc札 c 。刘 战 强 ( 9 9 ) h0 e 12 0 3 ao.o n i 16 一 ,男 ,   山东人 ,博 士生 导 师 ,主 要研究 方 向 :高 速切 削 ,C D   A/ C M,虚拟制造技术等 。 A  

收稿 日期 :2 o l O  o 5一 2一 1

( 上接 第 1 8页)  
【 】H weCo t ol u i .esr BsdEp ri : 6 o i hs ,J   r c Sno — a  xl ao     e eB dk e o tn TeHe r i l ee le  o ni r h ¨ ] n  h  ia h a G nri dV r o Ga rc c   az o   p .I . t
JR b R s, 00 9 ( ) 9 — 2. . ot e 20 , . . 1 2 : 6 15  

【】 7 王新生, 毋河海 . o ni V r o 图和非数值随机优化算法在  o
城市 与区域规 划 中的应 用研 究 [ ]. 汉 :武 汉大  D 武
学 , 02 4 2 0 ..  

【 】M hoi R Cnt co o t   nri dVr o d - 8 akv , . osutn fh g e le o ni i  c r i     e e az   o   a
ga  fh nn w  ni n n C].SE’9 Poe  r o teu ko nev omet[ m   r II 9 . r e c


d n s o   e I E It r a in   y o i m  n I d s il i g   ft  EE  n e t a S mp su o  n u t a  h n ol r

裹 2 各种算法 比较  问题  最优  G n G  e  G / 本 文  A 
5  5 90 3  5  5 90 3 

Eet nc C tN . 9 H 4 5 ,19 , 9 4—99 l r i c o s( a o9 T 86 ) 9 9 3: 8 . 8.  

类型  , l  
MT   6 MTl   0
Mr 0 I   2

m  
6   1  0
2  0

解  算法  G   M X 算法  T S 
5  5 90 3  5  5 95 6  5  5 90 3 

【 】 ea i  hm Rbt  ap g ASr y[] e - 9 Sbsa Tn . oocM pi :  u e J .Tc   tn i n v h
nc lR p r C ia  e ot MU —C   S一0 —1 1.Can geMelnUnv  2 1 re i  l   i- o
e r—st , o u e   ce c   p rme t i s u g i y, C mp t r S in e De a t n ,P t b r h,P t A 
1 2 3.2 O . 51 O 2 

6   1  0
2  0

1 6   1 1  15 25

18  16  17  11 15 15

通过上面 的实例可 以看出本文的算法具 有较强 的  搜索能力 ,在参数设定合理的情况下能够得 到较优 的 
解。  

【0 1】邹小兵, 蔡自兴 . 基于近似 V r o图的增量式环境  o ni o 建模方法 [ ].r e i so t   o dCnr s n C Po e n  f h W r  og s o  c d g  e l e 
Itl et ot l n   uo a o WCC  04 ne i n  nr   dA tm t n( I A2 0 ).杭  lg C o a i
州 , u e20 Jn 04,5 4 1 4 2 . ; 6 8— 6 2  

3 结 论 

【l l】龚炜, 石青云, 民德 .数字空间中的数学形态 一 程  
学——理论及应用 [ M].北京 :科学出版社 , 97 19 .  

本文根据 当前遗传算法存在的问题 ,通过深入 分  析 JbSo o.hp调度问题的特性 ,设计 了一种有效 的遗传  算法 ,由于传统遗传算法在解 JbSo p.hp调度 问题时不  是很好 ,为 JbS o 调 度问题设计 了一种 能有效继 承  o .hp 父代优 良模式 的遗传算法 ,该算法能更好地继 承邻 居  搜索 的优势 ,其原理 同样适用 于其 它组合 优化问题 ,   通过实例验证 了此算法获得较优解 的能力 。   参考 文献  【 】JI    ,M E A  . e riscj - o ceu 1 AN A S E R N SDt mn t o s ps d- e ii b h h  

作者简介 : 戴博 (9 1 ) 男 , 18一 , 湖南 岳阳人 , 硕士研  究生。研究 领域 : 移动机器人路径规划技术 , 能控制等 。 智  
电话 : 3 8 29 4 ,E—m i a 2 4 6 .o 肖跷 明  17 75 6 1 a :dl 1 @13 cm。 l o b ( 97 ) 男 ,江西赣 州人 , 16 一 , 博士 ,副教授 。研究领 域 : 智 

能机器人,智能控制,人工生命 等。蔡 自兴 (98 ) 13? ,  
男, 福建莆 田人 ,教 授 ,博 士生 导 师。研 究领 域 :人 工智 

能,智能机器人,智能控制等。   收稿 日期 :2 o  1 2  o 5 2— 8