基于启发式搜索的移动机器人主动定位

第 34卷第 5期 2012年 9月 机器人 ROBOT Vol.34, No.5Sep., 2012 DOI：10.3724/SP.J.1218.2012.00590 基于启发式搜索的移动机器人主动定位 刘艳丽 1,2，樊晓平 1，张 恒 2 （1. 中南大学信息科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 学院，湖南 长沙 410075； 2. 华东交通大学信息工程学院，江西 南昌 330013） 摘 要：提出了一种基于启发式搜索的主动定位算法．首先利用自适应粒子聚类算法对粒子进行聚类；然后分 别构造路径规划树和解空间树，并根据优先级评估函数计算解空间树中所有节点的优先级，利用优先队列式分支限 界法解决路径搜索问题；最后针对单个粒子簇分散问题提出了一种定位精度主动提升方法．仿真实验验证了所提出 方法的有效性． 关键词：主动定位；启发式搜索；解空间树；移动机器人 中图分类号：TP24 文献标识码：A 文章编号：1002-0446(2012)-05-0590-06 Heuristic Search Assisted Active Localization for Mobile Robot LIU Yanli1,2，FAN Xiaoping1，ZHANG Heng2 (1.School of Information Science and Engineering, Central South University, Changsha 410075, China; 2.School of Information Engineering, East China Jiaotong University, Nanchang 330013, China) Abstract: A heuristic search assisted active localization method is proposed. The algorithm clusters the particles by using adaptive particle clustering algorithm. Then, path planning trees and solution space trees are constructed respectively. Priories of all the nodes in the solution space trees are calculated according to the priority evaluation function, and the problem of path search is solved by the priority queue-type branch-and-bound method. Finally, a localizing accuracy active enhancing method is presented to solve the particle divergence problem in a single particle cluster. Simulation experiments validate the feasibility of the methods. Keywords: active localization; heuristic search; solution space tree; mobile robot 1 引言（Introduction） 移动机器人的主动定位是指根据已知的地图 环境和机器人的传感器数据，主动控制机器人的行 走路径以使机器人位姿的不确定性最小．1997 年， 德国波恩大学的 Burgard和 Fox以及美国卡耐基梅 隆大学的 Thrun 提出了移动机器人的主动定位算 法 [1-2]，明确了主动定位需要解决机器人“往哪走” 和“往哪看”2 个基本问题，通过使机器人位姿的 不确定性的期望值最小来选择最佳的行为，从此揭 开了主动定位算法研究的序幕并奠定了其基础．近 几年来，主动定位问题已成为移动机器人领域备 受国内外学者关注的热点问题，技术方法不断完 善．Jensfelt等在多假设跟踪的基础上提出了主动全 局定位方法，讨论了主动定位的启发式规则 [3]，在 一个拓扑地图环境里，通过使机器人的下一步运动 所观测到的特征数量最大来确定机器人的运动行 为．这种方法在具有易识别特征集合的环境中非常 有效，然而当不考虑环境的结构时，这种方法的执 行变得非常困难．Zhou 和 Sakane 提出了基于贝叶 斯网络优化主动行为的方法 [4-5]；Fox[2] 以及 Porta 等 [6-7] 预先构造一个行为集合，然后以行为效用和 行为开销构成 评价 LEC评价法下载LEC评价法下载评价量规免费下载学院评价表文档下载学院评价表文档下载 函数进行行为选择．这类方法的 计算复杂度较大，且其有效性在很大程度上依赖于 行为集合构造的合理性，对于不同环境需要构造不 同的行为集合．Petillot等 [8] 提出了一种基于树形结 构的路径搜索算法，并将其应用于水下机器人．在 国内，对主动定位算法的研究起步较晚，刘志斌等 提出了一种以环境势场提供辅助线索的主动定位方 法 [9]，通过构造运动目标搜索空间，采用综合行为 效用和行为代价的评价指标，从中选择最佳运动目 标，从而确定运动方向，并在此基础上规划出机器 人下一步的位移量和观测方向．黄庆成等根据机器 人之间的相对位置关系，设计了一种适用于多机器 人系统的主动协同定位方法 [10]，并在此基础上提出 基金项目：国家自然科学基金资助项目（61165007）；江西省教育厅科技项目（GJJ12290）；华东交通大学校立科研课题（10XX02）． 通讯作者：刘艳丽，hbliuyanli@126.com 收稿／录用／修回：2012-03-02/2012-04-13/2012-05-27 590 第 34卷第 5期 刘艳丽等：基于启发式搜索的移动机器人主动定位 591 了基于决策论的多机器人行为协调方法，使机器人 在定位过程中可以根据已获得的信息自主调整自己 的行为，从而获得更多有益于定位的观测信息．这 些成果从不同角度分析和论述了主动定位中存在的 一些缺点和解决方法，为该领域的进一步研究奠定 了坚实的基础并指明了方向． 本文深入研究了机器人基本的主动定位算法， 分析了该算法的不足．针对多粒子簇和单粒子簇的 情况，先后分别提出了基于启发式搜索的多假设主 动消除算法和定位精度主动提升算法．实验表明综 合两种算法的主动定位方法降低了位姿不确定度， 主动控制机器人的运动和朝向，提高了定位精度和 速度． 2 基本主动定位方法（Basic active localiza- tion） 记 l = 〈x,y,θ〉为机器人的位姿，B(l)表示机器 人的真实位姿在 l 上的可信度．为了减小机器人位 姿估计 B(l)的不确定性，机器人必须选择能够区别 不同位置的行为．位姿的不确定度用熵来描述，即 H =− w B(l) log(B(l))dl (1) 当机器人位姿完全确定时，B(l)在单一位姿处形成 尖峰分布，此时 H = 0，其值最小；而当 H 值最大， 即机器人位姿完全不确定时，B(l)在整个定位空间 趋于均匀分布．行为选择的基本原则就是使熵的期 望值最小化．为了能公式化，计算某个行为 a后的 熵的期望值，需要引入两个符号表示：Ba(l)表示执 行行为 a后的位姿估计，Ba,s(l)表示执行行为 a和 传感器的观测 s后的位姿估计．这两个量很容易通 过机器人的运动模型和观测模型得到 [1]．因此，熵 的期望值可以通过下面的公式得到： Ea(H) =− x Ba,s(l) log(Ba,s(l))p(s)dlds =− x P(s|l)Ba(l) log ( P(s|l)Ba(l)p−1(s) ) dlds (2) 为了能得到使熵的期望最小的行为，必须利用 式 (2) 计算出所有可能的行为的熵的期望，因此计 算是非常耗时的．为了简化计算，下文中所提出的 启发式方法主要通过搜索树形结构，扩展有限个子 节点，计算出节点的优先值，该方法就不需要计算 出所有行为的熵的期望． 3 启 发 式 搜 索 多 假 设 主 动 消 除 算 法 （Heuristic search assisted multiple hy- pothesis active removing algorithm） 为了降低基本主动定位算法的复杂度，本文提 出了一种基于启发式搜索的多假设主动消除算法． 其基本思想是：首先利用文 [11]提出的自适应粒子 聚类算法对粒子进行聚类，该方法可以很好地克服 粒子匮乏的问题，然后分别构造路径规划树和解空 间树并计算解空间树中所有节点的优先级；最后利 用优先队列式分支限界法优先扩展解空间树中优先 级最大的节点，以使路径朝向使机器人的位姿不确 定性最小的方向，如此反复，直到存在满足一定的 约束条件的路径．其目的是消除错误的位姿假设， 最终使机器人的位姿估计收敛于真实值（单个粒子 簇）． 3.1 构造树形结构 3.1.1 定义基本行为集合 预先定义一个移动机器人的基本行为集合： T = {t1, t2, t3, t4} (3) 一个基本行为集合可以包括以下 4种基本行为，每 一个基本行为可描述为“向前行走 x米”、“向右行 走 x米”、“向后行走 x米”以及“向左行走 x米”． 3.1.2 优先队列式的分支界限法 优先队列的分支限界法将活节点组织成一个优 先队列，并按优先队列中规定的节点优先级选取优 先级最高（最有利）的下一个节点成为当前扩展节 点，使搜索朝着解空间树上最优解的分支推进，以 便尽快地找出一个最优解．在树形结构中，就是根 据上面的 4种基本行为扩展节点的，即分别向 4个 方向扩展节点．也就是说，从父节点到子节点的运 动就是一个基本行为．也可以设置不同的基本行为 来扩展子节点．比如，可以以父节点为圆心生成一 个固定半径的圆，然后在这个圆上随机均匀地产生 n个子节点，但是需要保证所有路径规划树和解空 间树的结构一致性． 3.1.3 路径规划树和解空间树构造 路径规划树以每个粒子簇的质心为根节点进行 扩展，如图 1所示．图 1表示在一个矩形的环境中， 经过聚类分析之后得到代表机器人定位假设的 3个 粒子簇，图中的半圆表示激光传感器的观测范围． 图 2给出了以每个粒子簇的质心为根节点的路径规 划树，tdi (m)表示在以第 m 个粒子簇的质心为根节 点的树形结构上深度为 d、索引为 i 的节点，其中 i ∈ {1,2,3,4}分别用来表示机器人向上、向右、向下 592 机 器 人 2012年 9月 和向左 4个方向的扩展．t0(m)（m表示第 m个粒子 簇）表示 3个粒子簇的质心，即 3个路径规划树的 根节点．路径规划树构建是为了得到假定机器人从 父节点运动到子节点时的观测信息，然后利用所有 的观测信息可以计算出解空间树中相应节点的优先 级． 图 1 机器人定位假设 Fig.1 Hypotheses of robot localization t0(1) t0(3) t0(2) t2(1)2t 1 (1)3 t2(2)2t 1 (2)3 t2(3)2t 1 (3)3 图 2 路径规划树 Fig.2 Trees for path planning 与路径规划树不同，解空间树只有一个，如图 3 所示．对解空间树中的每个节点都赋予了相应的优 先级，可以从树中选择当前优先级最大的节点作为 父节点进行扩展． t0 1t 3 2t 2 图 3 构造解空间树 Fig.3 Constructing the solution space tree 3.2 确定节点优先级 3.2.1 优先级评估函数 优先队列中节点优先级常规定为一个与该节点 相关的数值 w，w一般表示以该节点为根的子树中 的分支接近最优解的程度．启发式搜索的有效性直 接取决于解空间树中节点优先级的确定，即优先级 的评估函数．我们根据环境本身的特点并考虑了时 间和空间之间的折中，提出了合适的优先级评估函 数．首先将解空间树中的根节点的优先级设置为 0． 用 td−1j 来表示节点 tdi 的父节点，通过下面的公式给 定节点 tdi 的优先级： Ptdi = Ptd−1j +(r d j,i− cdj,i) (4) 其中 Ptd−1j 表示父节点 td−1j 的优先级，rdj,i 和 cdj,i 分 别表示假定机器人从父节点 td−1j 运动到子节点 tdi 的收益和代价．为了简化行为代价的计算，忽略了 机器人转身等所产生的耗费，直接用从父节点 td−1j 到子节点 tdi 的行程来衡量 cdj,i．因此，解空间树中 从父节点到子节点的收益 rdj,i 是节点优先级定义的 难点．首先需要得到在所有以粒子簇质心为根节点 所生成的树形结构中，机器人虚拟地沿着从父节点 td−1j (m)（m表示第 m个粒子簇）到子节点 tdi (m)的 方向、在子节点 tdi (m)观测到的信息，我们用所有观 测信息的差异度来衡量 rdj,i． 3.2.2 创建栅格地图 为了快速方便地计算观测信息差异度，将所观 测到的地图环境划分为若干大小相同的栅格．本文 采用的环境地图就是栅格地图，在每个栅格中存储 一个或多个值来表示该栅格的状态．可以用以下 3 种来表示：−1、0 和 1，其分别意味着空闲、未知 和被障碍物占据．未知表示该单位栅格在全局环境 范围之外．由于地图信息是已知的，我们很容易得 到每个栅格被占据的信息．如图 4分别表示了机器 人虚拟地沿着从 3个路径规划树的根节点 t0(m)到 t13(m)的方向，在 t13(m)所观测到的栅格信息．然后 通过衡量这 3个栅格信息的差异度就可以得到在解 空间树中节点 t13 的优先级． t0(1) t0(3) t0(2) t1(1)3 t1(2)3 t1(3)3 图 4 传感器观测的栅格信息 Fig.4 Grid mapping of sensor observation 3.2.3 计算差异度 观测信息的差异度越大，节点优先级越大．这 是因为观测信息的差异度表示了机器人沿着这个方 第 34卷第 5期 刘艳丽等：基于启发式搜索的移动机器人主动定位 593 向行走的行为所获取的可以用来区别不同粒子簇的 观测信息的丰富程度．差异度越大，表明该行为能 区别不同粒子簇的可能性越大，即机器人能识别错 误的位姿假设的可能性越大．通过迭代使用基于启 发式搜索的主动定位方法，最终使机器人定位收敛 于真实的位姿． 为了得到这些观测信息的差异度，首先需要计 算出任意两个观测信息的差异，即对任意两个观 测信息中相对应的栅格状态进行逐一匹配，由于每 一个观测的栅格总数是相同的，因此，我们用不一 致的栅格数目与栅格总数的比例来定义两个节点 tdi (m)和 tdi (n)的观测的差异： ρ(ztdj,i(m),ztdj,i(n)) =∑δ (ztdj,i(m),ztdj,i(n)) / G(z) (5) 这里 G(z) 表示栅格总数，是一个常量，ztdj,i(m) 表示 在第 m粒子簇所构造的树形结构中，机器人沿着从 父节点 td−1j (m)到子节点 tdi (m)的方向上、在子节点 tdi (m) 处对环境的观测．∑δ (ztdj,i(m),ztdj,i(n)) 表示两个 观测的栅格地图中相对应的栅格不一致的数目．因 此，rdj,i 定义为任意两个观测信息的差异度之和： rdj,i = k ∑ m=1 k ∑ n>m ρ(ztdj,i(m),ztdj,i(n)) (6) 这里，k表示粒子簇的数目． 3.3 组织优先队列 当解空间树中的节点优先级确定之后，需要将 这些节点加入优先队列中并根据优先级进行排序． 排序算法的时间复杂度较高，考虑到搜索算法每次 只扩展优先级最高的节点，因此使用数据结构中的 堆排序比较合适，这样每次扩展节点时，比较交换 的次数最少．堆排序又分为最大堆和最小堆．使用 最大堆，体现最大效益优先；使用最小堆，体现最小 费用优先．在本文中，采用最大堆来实现优先队列 的排序． 3.4 算法描述 该算法首先利用文 [11]提出的自适应粒子聚类 算法对粒子进行聚类，将每个粒子簇的质心作为该 算法的输入．树的最大深度是预先给定的． Step 1 以每个粒子簇的质心为根节点构造路 径规划树，并同时构造解空间树； Step 2 确定解空间树上的节点的优先级； Step 3 判断解空间树是否达到最大深度，或 者存在节点的优先值大于预先设定的阈值，如果满 足其中一个条件则停止执行算法，并输出一条机器 人将要执行的路径，否则执行第 4步； Step 4 将节点加入优先队列，并扩展优先级 最大的节点，返回执行第 2步． 该算法输出一个机器人将要执行的最优的路 径，这个路径由一个基本行为序列组成．实验表明 不仅可以使定位快速收敛到包括真实位姿在内的若 干个相似位姿处，而且能通过主动控制机器人运动 获取更多的环境信息来区分多个假设位姿，使定位 收敛到真实值．但在将该算法应用到大量不同的环 境中时，发现了一个新的问题：机器人在一条具有 较少环境特征的狭长走廊运动时，可能不会获取足 够的环境信息，并且由于机器人本身固有的误差积 累，单个粒子簇会变得越来越分散，也就意味着定 位的精度会逐渐降低，对机器人执行任务会产生不 利的影响．为了克服这个问题，本文提出了基于启 发式搜索的定位精度主动提升算法． 4 启发式搜索定位精度主动提升算法 （Heuristic search assisted localization ac- curacy active enhancing algorithm） 4.1 基本思路 基于启发式搜索的多假设主动消除算法，可以 使代表多个位姿假设的多粒子簇收敛于单个粒子 簇．当机器人定位收敛于单个粒子簇后，在某些环 境中运动一段时间后，尤其是在具有对称性或局部 相似区域的地图环境中，定位的精度会逐渐降低， 也就是粒子簇变得更加分散．针对这个问题，本节 提出了基于启发式搜索的定位精度主动提升算法． 该算法以多假设主动消除算法作为基础，即先通过 多假设主动消除算法使机器人定位收敛于单个位 姿，然后简单地度量粒子簇的包络体各边是否超过 预定值，如果超过则表明单个粒子簇开始变得分散， 此时执行定位精度提升算法． 定位精度主动提升算法主要解决单粒子簇的定 位精度降低问题，该算法也是基于树形搜索结构的． 其基本思想是：首先构造路径规划树和解空间树， 通过使用优先队列式分支限界法，优先扩展解空间 树中优先级最大的节点，以使路径朝向使机器人的 位姿不确定性最小的方向，如此反复，直到存在满 足一定的约束条件的路径．该算法的目的是使机器 人的定位精度更加精确，并且始终保持在很高的水 平，算法步骤与多假设主动消除法类似，主要不同 之处是该算法将单个粒子簇的质心作为该算法的输 入，节点优先级的计算方法不同． 4.2 节点优先级的计算 单粒子簇情况下只有一个路径规划树，因此其 594 机 器 人 2012年 9月 确定节点优先级原则是获取的环境信息越丰富，表 明机器人能识别更多的环境信息，优先级越大．从 3.2.1节的优先级评估函数中获知算法的关键是计算 rdj,i．首先需要得到在路径规划树中，机器人虚拟地 沿着从父节点 td−1j 到子节点 tdi 的方向上、在子节点 tdi 处的观测信息．rdj,i 的值依赖以下两个量： (1) 激光传感器所观测到的距离它最短的距离 dmin(tdi )．如果机器人朝着离它最近的障碍物的方向 前进，它可以在最短的时间内获取环境中较多的可 识别的特征信息．因此，dmin(tdi ) 越短，rdj,i 的值越 大． (2) 激光传感器所观测到的距离曲线的弯曲程 度．本文用曲线拟合的最小二乘法得到距离曲线． 然后用离散的坐标到拟合曲线的距离的方差来衡量 距离曲线的弯曲程度，用 σ 2d(tdi ) 表示方差．σ 2 d(tdi ) 越 大，表示环境信息越丰富，rdj,i 的值越大． 综上所述，机器人从父节点 td−1j 运动到子节点 tdi 的收益 rdj,i 可以用下面的公式来表示： rdj,i = (dmin(t d i )) −1 +α ·σ 2d(tdi ) (7) 式中 α > 0为偏好系数，表示对距离曲线弯曲程度 的侧重程度． 5 仿真实验及分析（Simulation experiment and analysis） 5.1 仿真实验环境 在基于 Player/Stage 的移动机器人平台上对算 法进行了仿真实验，设置粒子数目的下限和上限分 别是 100和 10000．本文在 2维环境中进行仿真实 验，可以直接扩展到 3维的环境，唯一的改变就是 基本行为集合的元素个数．在 2维环境中，可以简 单地将基本行为分为以下 4个，即向前、向右、向后 和向左移动 0.5 m．解空间树的最大深度设置为 8， 仿真环境为一个 16 m×16 m的地图． 5.2 实验结果及分析 在文 [11]提出的自适应粒子聚类蒙特卡洛定位 算法的基础上，运用本文提出的多假设主动消除算 法，对比结合了多假设主动消除算法和精度提升算 法的方法，进行了大量仿真实验．图 5和图 6分别 为只使用多假设主动消除算法和结合两种主动定位 算法的方法的实验结果．仿真地图为一个 U形的闭 合环境． 机器人的初始位置位于环境的左上角区域，方 向竖直向下．机器人的初始粒子分布位于整个闭合 空间中．图 5(a)表示机器人在第 3 s时的位姿分布， 在左右两个角分别有一个位姿假设．此时，使用多 假设主动消除算法，输出一条最优路径，先向下运 动再向左运动，之后粒子分布如图 5(b)所示，此时 定位收敛于单个粒子簇．然后主动定位算法停止执 行．由于机器人的随机运动和环境中具有较少特征， 因此，在图 5(c)和图 5(d)中，粒子变得更为分散，即 定位精度逐渐降低． (a) t = 3 s (b) t = 24 s (c) t = 68 s (d) t = 92 s 图 5 多假设主动消除算法的仿真实验结果 Fig.5 Simulation results of multiple hypothesis active removing algorithm 图 6 给出了第 75 s 和第 94 s 的粒子分布情况． 可以看出，代表机器人位姿的粒子分布得更加紧密． 由于是首先执行的基于启发式搜索的多假设主动 消除算法，因此，前面时刻的粒子分布与图 5(a)和 图 5(b)的情况一致．在本次实验中，通过判断相应 的条件，机器人在第 68 s开始执行基于启发式搜索 的定位精度主动提升算法，输出一条路径（向上运 动）．然后机器人在第 85 s开始第二次执行该算法， 图 6(b)为执行输出路径（向左下方向运动）后的粒 子分布． (a) t = 75 s (b) t = 94 s 图 6 结合两种主动定位算法的仿真实验结果 Fig.6 Simulation results of combination algorithm of the two active localization algorithms 第 34卷第 5期 刘艳丽等：基于启发式搜索的移动机器人主动定位 595 图 7 给出了 3 种定位方法 50 次仿真实验的平 均定位误差（用机器人的估计位姿到真实位姿的距 离来衡量）曲线．A1、A2和 A3分别表示非主动自 适应粒子聚类蒙特卡洛定位算法（即随机运动）、多 假设主动消除算法以及结合两种主动定位算法的方 法．从图中可以看出，随机运动定位方法向真实值 靠近的速度最慢，并且定位误差始终比另外两种方 法高．由于 A2和 A3方法在定位前期都使用了基于 启发式搜索的多假设主动消除算法，因此，它们在 第 68 s前误差水平保持一致，但是在定位后期，A2 曲线出现了定位误差逐渐增大的趋势，而使用结合 两种主动定位算法的方法使定位误差始终保持在最 低的水平． 0 50 100 150 200 2 4 6 8 a v e ra g e l o c a li z a ti o n e rr o r /m time /s A1 A2 A3 图 7 定位误差平均值随时间的变化曲线 Fig.7 Average localization error vs. time 根据以上实验结果分析其原因为：随机运动由 于运动的随机性使得机器人在闭合环境中盲目地运 动，导致其位姿估计向真实值的靠近速度最慢；算 法 A2由于使用了基于启发式搜索的多假设主动消 除算法，该算法以降低位姿不确定度为目的主动控 制机器人的运动和朝向，使其定位快速向真实值靠 拢，但在定位后期，由于使用了被动的定位方法（即 机器人随机游动）和仿真环境具有较少的障碍物， 使得其定位误差有逐渐增大的趋势；算法 A3结合 了两种主动定位算法，在定位前期，会有多个粒子 簇，此时通过执行基于启发式搜索的主动定位算法 使机器人定位收敛到单个粒子簇，因此与 A2算法 的定位误差保持一致．当位姿不确定度达到一定程 度时，会自动执行基于启发式搜索的定位精度主动 提升算法，能通过主动控制机器人运动获取更多的 环境信息，因此定位精度和效率都是最高的． 6 结论（Conclusion） 针对目前主动定位算法的计算复杂度较大以 及实时性较差的问题，提出了基于启发式搜索的主 动定位算法．仿真分析表明该算法实时性强，定位 的效率和精度高，既可应用于多个相似局部区域、 对称结构或者较少环境特征的特殊环境，也可应用 于大规模环境中．该算法的不足之处是：本文的定 位算法应用于单个机器人，但是很多情况下，需要 多个机器人来协作完成任务．我们今后工作重点将 是在此算法的基础上，设计一种适用于多机器人协 同定位的动态结构，将其应用于多机器人的网络控 制． 参考文献（References） [1] Burgard W, Fox D, Thrun S. Active mobile robot localiza- tion[C]//15th International Joint Conference on Artificial Intel- ligence: Vol.2. San Francisco, CA, USA: Morgan Kaufmann Publishers, 1997: 1346-1352. [2] Fox D, Burgard W, Thrun S. Active Markov localization for mobile robots[J]. Robotics and Autonomous Systems, 1998, 25(3/4): 195-207. [3] Jensfelt P, Kristensen S. Active global localization for a mobile robot using multiple hypothesis tracking[J]. IEEE Transactions on Robotics and Automation, 2001, 17(5): 748-760. [4] Zhou H J, Sakane S. Sensor planning for mobile robot local- ization based on probabilistic inference using Bayesian net- work[C]//IEEE International Symposium on Assembly and Task Planning. Piscataway, NJ, USA: IEEE, 2001: 7-12. [5] Zhou H J, Sakane S. Sensor planning for mobile robot local- ization: A hierarchical approach using Bayesian network and particle filter[J]. IEEE Transactions on Robotics, 2008, 24(2): 481-487. [6] Porta J M, Terwijin B, Krose B J A. Efficient entropy-based ac- tion selection for appearance-based robot localization[C]//20th IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2003: 2842-2847. [7] Porta J M, Verbeek J J, Krose B J A. Active appearance-based robot localization using stereo vision[J]. Autonomous Robots, 2005, 18(1): 59-80. [8] Petillot Y, Maurelli F. A tree-based planner for active localiza- tion: Applications to autonomous underwater vehicles[C]// Pro- ceedings of ELMAR 2010. Piscataway, NJ, USA: IEEE, 2010: 479-483. [9] 刘志斌，石宗英，赵明国，等．基于环境势场的移动机器人 主动定位 [J]．控制与决策，2008，23(2): 187-194. Liu Z B, Shi Z Y, Zhao M G, et al. Environment potential field assisted active localization for mobile robot[J]. Control and De- cision, 2008, 23(2): 187-194. [10] 黄庆成，罗荣华．一种多移动机器人主动协同定位方法的 研究 [J]．电子学报，2010，38(11): 2644-2648. Huang Q C, Luo R H. An active cooperative localization method for mobile robots[J]. Acta Electronica Sinica, 2010, 38(11): 2644-2648. [11] 张恒，樊晓平，瞿志华．基于多假设跟踪的移动机器人 自适应蒙特卡罗定位研究 [J]．自动化学报，2007，33(9): 941-946. Zhang H, Fan X P, Qu Z H. Mobile robot adaptive Monte Carlo localization based on multiple hypothesis tracking[J]. Acta Au- tomatica Sinica, 2007, 33(9): 941-946. （下转第 603页） 第 34卷第 5期 王 勇等：面向拥挤环境的移动机器人改进粒子滤波定位 603 ban areas[C]//IEEE International Conference on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2003: 842-849. [3] Yang S W, Wang C C. Feasibility grids for localization and map- ping in crowded urban scenes[C]//IEEE International Confer- ence on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2011: 2322-2328. [4] 王炜，陈卫东，王勇．基于概率栅格地图的移动机器人可定 位性估计 [J]．机器人，2012，34(4): 485-491,512. Wang W, Chen W D, Wang Y. Probabilistic grid map based lo- calizability estimation for mobile robots[J]. Robot, 2012, 34 (4): 485-491,512. [5] 王卫华，陈卫东，席裕庚．移动机器人地图创建中的不确定 传感信息处理 [J]．自动化学报，2003，29(2): 267-274. Wang W H, Chen W D, Xi Y G. Uncertainty sensor information processing in map building of mobile robot[J]. Acta Automatica Sinica, 2003, 29(2): 267-274. [6] Bobrovsky B, Zakai M. A lower bound on the estimation er- ror for Markov processes[J]. IEEE Transactions on Automatic Control, 1975, 20(6): 785-788. [7] Doucet A, de Freitas N D, Gordon N, et al. Sequential Monte Carlo in practice[M]. Berlin, Germany: Springer-Verlag, 2001. [8] Antonelli G, Chiaverini S, Fusco G. A calibration method for odometry of mobile robots based on the least-squares technique: Theory and experimental validation[J].IEEE Transactions on Robotics, 2005, 21(5): 994-1004. [9] Kleeman L. Advanced sonar and odometry error modeling for simultaneous localisation and map building[C]//IEEE/RSJ In- ternational Conference on Intelligent Robots and Systems. Pis- cataway, NJ, USA: IEEE, 2003: 699-704. [10] Roecker J A, McGillem C D. Comparison of two-sensor track- ing methods based on state vector fusion and measurement fu- sion[J]. IEEE Transactions on Aerospace and Electronic Sys- tems, 1988, 24(4): 447-449. [11] Li Q N, Chen W D, Wang J C. Dynamic shared control for human-wheelchair cooperation[C]//IEEE International Confer- ence on Robotics and Automation. Piscataway, NJ, USA: IEEE, 2011: 4278- 4283. [12] Thrun S. Robotic mapping: A survey[D]. Pittsburgh, USA: Carnegie Mellon University, 2002. 作者简介： 王 勇（1982 –），男，博士生．研究领域：智能机器人，多 机器人系统． 陈卫东（1968 –），男，博士，教授，博士生导师．研究领域： 智能机器人，多机器人系统． 王景川（1979 –），男，硕士，助理研究员．研究领域：移动 机器人． （上接第 595页） 作者简介： 刘艳丽（1979–），女，博士生，讲师．研究领域：移动机器 人导航技术，机器人网络，计算机视觉． 樊晓平（1961–），男，博士，博士生导师．研究领域：无线 传感器网络，机器人控制，智能交通系统等． 张 恒（1979–），男，博士，副教授．研究领域：移动机器 人导航技术，机器人网络，压缩感知．