Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor


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. © 2016 Elsevier Ltd


Documento: Artículo
Título:A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment
Autor:Kulich, M.; Miranda-Bront, J.J.; Přeučil, L.
Filiación:Czech Institute of Informatics, Robotics, and Cybernetics, Czech Technical University in Prague, Czech Republic
Departamento de Computación, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, CABA, Argentina
Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina
Palabras clave:Graph Search Problem; GRASP; Mobile robotics; Robotic search; Traveling Deliveryman Problem; Robotics; Graph search; GRASP; Mobile robotic; Robotic searches; Traveling deliveryman problem; Heuristic algorithms
Página de inicio:178
Página de fin:187


  • Kulich, M., Přeučil, L., Miranda-Bront, J.J., (2014), pp. 5830-35. , Single robot search for a stationary object in an unknown environment. In: 2014 IEEE international conference on robotics and automation;; Yamauchi, B., (1998), pp. 47-53. , Frontier-based exploration using multiple robots. In: Proceedings of the second international conference on autonomous agents;; Basilico, N., Amigoni, F., Exploration strategies based on multicriteria decision making for searching environments in rescue operations (2011) Auton Robot, 31 (4), pp. 401-417
  • Senthilkumar, K.S., Bharadwaj, K.K., Multi-robot exploration and terrain coverage in an unknown environment (2012) Robot Auton Syst, 60 (1), pp. 123-132
  • Kulich, M., Faigl, J., Přeučil, L., (2011), pp. 4455-60. , On distance utility in the exploration task. In: 2011 IEEE international conference on robotics and automation (ICRA);; Faigl, J., Kulich, M., Přeučil, L., (2012), pp. 3741-46. , Goal assignment using distance cost in multi-robot exploration. In: 2012 IEEE/RSJ international conference on intelligent robots and systems (IROS); October; Sarmiento, A., Murrieta-Cid, R., Hutchinson, S., (2004), pp. 484-93. , A multi-robot strategy for rapidly searching a polygonal environment. In: Lematre C, Reyes CA, Gonzlez JA, editors. Advances in artificial intelligence—IBERAMIA 2004, Proceedings of 9th Ibero-American conference on AI, Puebla, México, November 22–26, 2004. Lecture notes in computer science, vol. 3315. Berlin, Heidelberg: Springer;; Shermer, T., , pp. 1384-99. , Recent results in art galleries [geometry]. Proc IEEE 1992;80(September):; Sarmiento, A., Murrieta, R., Hutchinson, S., An efficient motion strategy to compute expected-time locally optimal continuous search paths in known environments (2009) Adv Robot, 23 (12-13), pp. 1533-1560
  • Hollinger, G., Djugash, J., Singh, S., (2008), pp. 433-42. , Coordinated search in cluttered environments using range from multiple robots. In: Laugier C, Siegwart R, editors. Field and service robotics, Springer tracts in advanced robotics, vol. 42. Berlin, Heidelberg: Springer;; Koutsoupias, E., Papadimitriou, C., Yannakakis, M., Searching a fixed graph. In: Meyer F, Monien B, editors. Automata, languages and programming. Lecture notes in computer science, vol. 1099. Berlin, Heidelberg: Springer; 1996. p. 280–9; Ausiello, G., Leonardi, S., Marchetti-Spaccamela, A., (2000), pp. 1-16. , On salesmen, repairmen, spiders, and other traveling agents. In: Bongiovanni G, Petreschi R, Gambosi G, editors. Algorithms and complexity. Lecture notes in computer science, vol. 1767. Berlin, Heidelberg: Springer;; Fischetti, M., Laporte, G., Martello, S., , pp. 1055-64. , The delivery man problem and cumulative matroids. Oper Res 1993;(March):; Gouveia, L., Voß, S., A classification of formulations for the (time-dependent) traveling salesman problem (1995) Eur J Oper Res, 2217, p. 93
  • Méndez-Díaz, I., Zabala, P., Lucena, A., A new formulation for the traveling deliveryman problem (2008) Discrete Appl Math, 156 (October), pp. 3223-3237
  • Abeledo, H., Fukasawa, R., Pessoa, A., Uchoa, E., The time dependent traveling salesman problem: polyhedra and algorithm (2012) Math Program Comput, 5 (September), pp. 27-55
  • Miranda-Bront, J.J., Méndez-Díaz, I., Zabala, P., An integer programming approach for the time-dependent TSP (2010) Electron Notes Discrete Math, 36 (August), pp. 351-358
  • Miranda-Bront, J., Méndez-Díaz, I., Zabala, P., Facets and valid inequalities for the time-dependent travelling salesman problem (2014) Eur J Oper Res, 236 (3), pp. 891-902
  • Godinho, M.T., Gouveia, L., Pesneau, P., Natural and extended formulations for the Time-Dependent Traveling Salesman Problem (2014) Discrete Appl Math, 164 (February), pp. 138-153
  • Feo, T.A., Resende, M.G., Greedy randomized adaptive search procedures (1995) J Glob Optim, 6 (2), pp. 109-133
  • Hansen, P., Mladenović, N., Variable neighborhood search (1997) Comput Oper Res, 24 (1), pp. 1097-1100
  • Salehipour, A., Sörensen, K., Goos, P., Bräysy, O., Efficient GRASP+VND and GRASP+VNS metaheuristics for the traveling repairman problem (2011) 4OR, 9, pp. 189-209
  • Mladenović, N., Urošević, D., Hanafi, S., Variable neighborhood search for the travelling deliveryman problem (2012) 4OR, pp. 1-17
  • Silva, M.M., Subramanian, A., Vidal, T., Ochi, L.S., A simple and effective metaheuristic for the Minimum Latency Problem (2012) Eur J Oper Res, 221 (September), pp. 513-520
  • Dewilde, T., Cattrysse, D., Coene, S., Spieksma, F., Vansteenwegen, P., Heuristics for the traveling repairman problem with profits (2013) Comput Oper Res, 40 (July), pp. 1700-1707
  • Heilporn, G., Cordeau, J.-F., Laporte, G., The delivery man problem with time windows (2010) Discrete Optim, 7 (November), pp. 269-282
  • Amigoni, F., Li, A.Q., Holz, D., (2013), pp. 68-73. , Evaluating the impact of perception and decision timing on autonomous robotic exploration. In: ECMR;; Lin, S., Kernighan, B., An effective heuristic algorithm for the traveling-salesman problem (1973) Oper Res
  • Applegate, D.L., Bixby, R.E., Chvatal, V., Cook, W.J., (2007), The traveling salesman problem: a computational study. Princeton series in applied mathematics. Princeton, NJ, USA: Princeton University Press;; Karapetyan, D., Gutin, G., Lin–Kernighan heuristic adaptations for the generalized traveling salesman problem (2011) Eur J Oper Res, 208 (February), pp. 221-232
  • Helsgaun, K., An effective implementation of the Lin–Kernighan traveling salesman heuristic (2000) Eur J Oper Res, 126, pp. 106-130
  • Reinelt, G., Tsplib—a traveling salesman problem library (1991) INFORMS J Comput, 3 (4), pp. 376-384
  • Faigl, J., Kulich, M., (2015), On benchmarking of frontier-based multi-robot exploration strategies. In: European conference on mobile robots;;, Motion planning maps. 〈〉. [accessed: September 30, 2015]; Krajník, T., Kulich, M., Mudrová, L., Ambrus, R., Duckett, T., (2015), pp. 2140-6. , Where's Waldo at time t? Using spatio-temporal models for mobile robot search. In: IEEE international conference on robotics and automation, ICRA 2015, Seattle, WA, USA, 26–30 May, 2015;


---------- APA ----------
Kulich, M., Miranda-Bront, J.J. & Přeučil, L. (2017) . A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment, 84, 178-187.
---------- CHICAGO ----------
Kulich, M., Miranda-Bront, J.J., Přeučil, L. "A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment" 84 (2017) : 178-187.
---------- MLA ----------
Kulich, M., Miranda-Bront, J.J., Přeučil, L. "A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment" , vol. 84, 2017, pp. 178-187.
---------- VANCOUVER ----------
Kulich, M., Miranda-Bront, J.J., Přeučil, L. A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment. 2017;84:178-187.