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

Optimal map building for constrained mobile robot exploration

作　　者：陈花[1] 张远平[1] 林强[1] 

机构地区：[1]兰州理工大学计算机与通信学院,甘肃兰州730050

出　　处：《计算机工程与设计》2009年第16期3823-3825,共3页Computer Engineering and Design

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

摘　　要：对复杂未知环境构建地图是移动机器人面临的一大问题。通常忽略未知环境的几何特征,将其抽象成未知无向连通图,机器人只沿着图的边进行搜索,并将走过每条边的成本看成是1。机器人构建地图的成本用走过的总边数来表示。对于一个完全未知的环境,从一点出发,限制移动机器人最远能走(如燃料问题及安全线或通信线等)步(边数)的范围内,基于深度受限剪枝生成子树的方法,结合广度优先搜索和受限的深度优先搜索染色策略,给出了对未知环境构建完整地图的有效算法,该算法的成本为||+||,这是目前最优结果。The problem faced by a mobile robot is to construct a complete map of an unknown environment. The geometric features of the environment are neglected and the environment is modeled as an unknown connected undirected graph. The robot can only move along edges of the graph. Suppose that the cost of each edge traversal is 1. A robot has to visit all nodes and edges of the graph, using as few edge traversals as possible. The cost of building map is measured by the number of edges traversed during the exploration. The robot starts at vertex S, and moves no more than the range of r steps. Based on the approach that prunes a tree with a bounded depth, combining with the strategy of BFS and bounded DFS coloring method, an efficient algorithm of building map of unknown environment is presented. The cost of the algorithm is ｜E｜＋O｜v｜, . It is the optimal result until now.

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

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]