受限移动机器人构建地图的最优探测法

作     者：陈花 张远平 林强 CHEN Hua;ZHANG Yuan-ping;LIN Qiang

作者机构：兰州理工大学计算机与通信学院甘肃兰州730050 

出 版 物：《计算机工程与设计》 (Computer Engineering and Design)

年 卷 期：2009年第30卷第16期

页      面：3823-3825页

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 081104[工学-模式识别与智能系统] 08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 

基　　金：甘肃省自然科学基金项目(3ZS051-A25-037) 

主　　题：无向图 移动机器人 未知环境探测 构建地图 深度优先搜索 广度优先搜索 

摘      要：对复杂未知环境构建地图是移动机器人面临的一大问题。通常忽略未知环境的几何特征,将其抽象成未知无向连通图,机器人只沿着图的边进行搜索,并将走过每条边的成本看成是1。机器人构建地图的成本用走过的总边数来表示。对于一个完全未知的环境,从一点出发,限制移动机器人最远能走(如燃料问题及安全线或通信线等)步(边数)的范围内,基于深度受限剪枝生成子树的方法,结合广度优先搜索和受限的深度优先搜索染色策略,给出了对未知环境构建完整地图的有效算法,该算法的成本为||+||,这是目前最优结果。