Optimal map building for constrained mobile robot exploration
Qiang Lin · Jisuanji gongcheng yu sheji · 2009
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,and moves no more than the range of 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 | |+ | |.It is the optimal result until now.