On distance utility in the exploration task

On distance utility in the exploration task,10.1109/ICRA.2011.5980221,Miroslav Kulich,Jan Faigl,Libor Preucil

On distance utility in the exploration task  
BibTex | RIS | RefWorks Download
Performance of exploration strategies strongly depends on the process of determination of a next robot goal. Current approaches define different utility functions how to evaluate and select possible next goal candidates. One of the mostly used evaluation criteria is the distance cost that prefers candidates close to the current robot position. If this is the only criterion, simply the nearest candidate is chosen as the next goal. Although this criterion is simple to implement and gives feasible results there are situations where the criterion leads to wrong decisions. This paper presents the distance cost that reflects traveling through all goal candidates. The cost is determined as a solution of the Traveling Salesman Problem using the Chained Lin-Kernighan heuristic. The cost can be used as a stand-alone criterion as well as it can be integrated into complex decision systems. Experimental results for open-space and office-like experiments show that the proposed approach outperforms the standard one in the length of the traversed trajectory during the exploration while the computational burden is not significantly increased. I. INTRODUCTION The exploration can be understood as a process of au- tonomous navigation of a mobile robot in an unknown environment in order to build a model of the environment. An exploration algorithm can be defined as an iterative procedure consisting of a selection of a new goal and a navigation to this goal. Such an algorithm is terminated whenever the defined condition (mission objective) is fulfilled. In this paper, the mission objective is building of a complete map of the environment. Besides, the usage of resources (e.g. the exploration time, the length of the trajectory) is optimized. In other words, the exploration strategy determines the next robot goal in each exploration iteration (one exploration step) with respect to the actual robot position, the current knowledge of the environment, and a selected optimization criterion. Several exploration strategies have been proposed over last decades. The strategies differ in the way how candidates for the next goal are generated and in the criterion how the best candidate is selected. Yamauchi (1) introduced a frontier- based strategy that guides the robot to the nearest frontier, i.e. the boundary between a free and an unexplored space. It has been shown (2), (3) that this strategy produces reasonably short trajectories for graph-like environments with upper bound O(jVj log(jVj)), wherejVj is the number of vertices of the graph. The authors of (4) discussed two simple heuristics improving Yamauchi's approach. The first one uses Voronoi diagrams to prefer exploration of the whole
Cumulative Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.