Elsevier

Computers & Operations Research

Volume 84, August 2017, Pages 178-187
Computers & Operations Research

A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment

https://doi.org/10.1016/j.cor.2016.04.029Get rights and content

Highlights

  • We study the single-robot search problem in an unknown environment.

  • We propose a goal selection strategy based on the solution of a Graph Search Problem.

  • We propose GRASP meta-heuristic to obtain good solutions in short computing times.

  • The proposed goal selection strategy outperforms strategies taken from exploration.

Abstract

The single-robot search problem in an unknown environment is defined as the problem of finding a stationary object in the environment whose map is not known a priori. Compared to exploration, the only difference lies in goal selection as the objectives of search and exploration are dissimilar, i.e. a trajectory that is optimal in exploration does not necessarily minimize the expected value of the time to find an object along it. For this reason, in this paper we extend the preliminary ideas presented in Kulich et al. [1] to a general framework that accounts for the particular characteristics of the search problem. Within this framework, an important decision involved in the determination of the trajectory can be formulated as an instance of the Graph Search Problem (GSP), a generalization of the well-known Traveling Deliveryman Problem (TDP) which has not received much attention in the literature. We developed a tailored Greedy Randomized Adaptive Search Procedure (GRASP) meta-heuristic for the GSP, which generates good quality solutions in very short computing times and is incorporated in the overall framework. The proposed approach produces very good results in a simulation environment, showing that it is feasible from a computational standpoint and the proposed strategy outperforms the standard approaches.

Section snippets

Introduction and literature review

Single-robot search, similar to exploration, can be understood as a process of autonomous navigation of a mobile robot in an unknown environment in order to find an object of interest. The search algorithm can be formulated as the iterative procedure consisting of model updating with actual sensory data, selection of a new goal for a robot based on the current knowledge of the environment, and subsequent navigation to this goal. A natural condition is to perform the search with an expected

Problem definition

Assume an autonomous mobile robot equipped with a ranging sensor with a fixed, limited range (e.g. laser range-finder) and 360° field of view operating in a priori unknown environment. The search problem is defined as the process of navigation of the robot through this environment with the aim to find a stationary object of interest placed in the environment randomly and reachable by the robot.1

General settings

The proposed framework for single-robot search is derived from seminal Yamauchi's frontier based approach (FBA) [2] successfully used for exploration. FBA utilizes an occupancy grid as the environment representation, which divides robot's working space into rectangular grid cells, where each cell stores information about the corresponding piece of the space in the form of a probabilistic estimate of its state. The grid is built incrementally as actual sensor measurements are gathered during

Solution approach for the GSP

In this section we provide the details regarding the meta-heuristic approach considered for solving the GSP in the context of the search problem. We first describe two greedy heuristics and the local search operators developed, and then explain how they are combined within a GRASP scheme.

Computational results

In this section we present the computational results obtained for the search problem. Firstly, we conducted an experimental study in order to evaluate the quality and the computation effort required to solve the GSP on literature benchmark instances. Then, the selected meta-heuristic has been embed within the framework described in Section 3 and evaluated in a simulation environment, comparing the results obtained with the usual strategy adopted in the exploration problem.

Conclusions and future research

This paper presents a general frontier-based framework for the single-robot search problem in an unknown environment, where the goal selection strategy involves the solution of a GSP instance. We provide a complete implementation of such a framework, including a tailored GRASP meta-heuristic for the GSP, which is able to find near-optimal solutions in about one second of computing time. The overall framework is evaluated in a simulation environment on four different maps and 1200 trials in

Acknowledgments

The work of J.J. Miranda-Bront is partially supported by Grants PICT-2011-0817, PICT-2013-2460 and project MEYS 2013 ARC/13/13. The work of M. Kulich is supported by the Czech Science Foundation (GAČR) under research project No. GA15-22731S and the Czech Ministry of Education, Youth and Sports under the Project no. 7AMB14AR015 “Multi-Robot Autonomous Systems”.

Access to computing and storage facilities owned by parties and projects contributing to the National Grid Infrastructure MetaCentrum,

References (35)

  • Kulich M, Přeučil L, Miranda-Bront JJ. Single robot search for a stationary object in an unknown environment. In: 2014...
  • Yamauchi B. Frontier-based exploration using multiple robots. In: Proceedings of the second international conference on...
  • N. Basilico et al.

    Exploration strategies based on multicriteria decision making for searching environments in rescue operations

    Auton Robot

    (2011)
  • Kulich M, Faigl J, Přeučil L. On distance utility in the exploration task. In: 2011 IEEE international conference on...
  • Faigl J, Kulich M, Přeučil L. Goal assignment using distance cost in multi-robot exploration. In: 2012 IEEE/RSJ...
  • Sarmiento A, Murrieta-Cid R, Hutchinson S. A multi-robot strategy for rapidly searching a polygonal environment. In:...
  • Shermer T. Recent results in art galleries [geometry]. Proc IEEE...
  • Cited by (16)

    View all citing articles on Scopus
    View full text