A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment
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)
- et al.
Multi-robot exploration and terrain coverage in an unknown environment
Robot Auton Syst
(2012) - et al.
A new formulation for the traveling deliveryman problem
Discrete Appl Math
(2008) - et al.
An integer programming approach for the time-dependent TSP
Electron Notes Discrete Math
(2010) - et al.
Facets and valid inequalities for the time-dependent travelling salesman problem
Eur J Oper Res
(2014) - et al.
Natural and extended formulations for the Time-Dependent Traveling Salesman Problem
Discrete Appl Math
(2014) - et al.
A simple and effective metaheuristic for the Minimum Latency Problem
Eur J Oper Res
(2012) - et al.
Heuristics for the traveling repairman problem with profits
Comput Oper Res
(2013) - et al.
The delivery man problem with time windows
Discrete Optim
(2010) - et al.
Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem
Eur J Oper Res
(2011) An effective implementation of the Lin–Kernighan traveling salesman heuristic
Eur J Oper Res
(2000)
Exploration strategies based on multicriteria decision making for searching environments in rescue operations
Auton Robot
Cited by (16)
Static force capability optimization of humanoids robots based on modified self-adaptive differential evolution
2017, Computers and Operations ResearchCitation Excerpt :The use of robots in the industry and the solution of problems associated with robot movements are constantly discussed in specialized literature [39–41]. In this sense, metaheuristics can be adopted to solve complex tasks [15,42], particularly those that are related to constrained optimization problems. In this section, a brief background of two metaheuristics, the DE and SaDE, is presented.
Optimizing Mesh to Improve the Triangular Expansion Algorithm for Computing Visibility Regions
2024, SN Computer SciencePath planning for mobile robots in complex environments based on improved ant colony algorithm
2023, Mathematical Biosciences and EngineeringSolving the traveling delivery person problem with limited computational time
2022, Central European Journal of Operations ResearchBuilding Metric-Topological Map to Efficient Object Search for Mobile Robot
2022, IEEE Transactions on Industrial ElectronicsMultirobot search for a stationary object placed in a known environment with a combination of GRASP and VND
2022, International Transactions in Operational Research