Navegar

Colección

Datos Estadísticas

Conferencia

Kulich, M.; Preucil, L.; Bront, J.J.M. "On multi-robot search for a stationary object" (2017) 2017 European Conference on Mobile Robots, ECMR 2017
Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor

Abstract:

Two variants of multi-robot search for a stationary object in a priori known environment represented by a graph are studied in the paper. The first one is generalization of the Traveling Deliveryman Problem where more than one deliveryman is allowed to be used in a solution. Similarly, the second variant is generalization of the Graph Search Problem. A novel heuristics suitable for both problems is proposed which is furthermore integrated into a cluster-first route second approach. A set of computational experiments was conducted over the benchmark instances derived from the TSPLIB library. The results obtained show that even a standalone heuristics significantly outperforms the standard solution based on k- means clustering in quality of results as well as computational time. The integrated approach furthermore improves solutions found by a standalone heuristics by up to 15% at the expense of higher computational complexity. © 2017 IEEE.

Registro:

Documento: Conferencia
Título:On multi-robot search for a stationary object
Autor:Kulich, M.; Preucil, L.; Bront, J.J.M.
Filiación:Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Zikova 1903/4, Prague, 166 36, Czech Republic
Departamento de Computación, Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires, Argentina
Palabras clave:Benchmarking; Industrial robots; Mobile robots; Multipurpose robots; Computational experiment; Computational time; Integrated approach; K-means clustering; Multi-robot search; Standard solutions; Stationary objects; Traveling deliveryman problem; Robots
Año:2017
DOI: http://dx.doi.org/10.1109/ECMR.2017.8098696
Título revista:2017 European Conference on Mobile Robots, ECMR 2017
Título revista abreviado:European Conf. Mob. Robots, ECMR
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_97815386_v_n_p_Kulich

Referencias:

  • Kulich, M., Preucil, L., Miranda-Bront, J.J., Single Robot Search for a Stationary Object in an Unknown Environment (2014) Robotics and Automation (ICRA), IEEE Int. Conf. on, pp. 5830-5835
  • Afrati, F., Cosmadakis, S., Papadimitriou, C.H., Papageorgiou, G., Papakostantinou, N., The complexity of the travelling repairman problem (1986) Theoretical Informatics and Applications
  • Gouveia, L., Voß, S., A classification of formulations for the (time-dependent) traveling salesman problem (1995) European Journal of Operational Research, 2217 (93)
  • Mendez-Diaz, I., Zabala, P., Lucena, A., A new formulation for the traveling deliveryman problem (2008) Discrete Appl. Math., 156 (17), pp. 3223-3237. , Oct
  • Abeledo, H., Fukasawa, R., Pessoa, A., Uchoa, E., The time dependent traveling salesman problem: Polyhedra and algorithm (2012) Mathematical Programming Computation, 5 (1), pp. 27-55. , Sept
  • Miranda-Bront, J.J., Mendez-Diaz, I., Zabala, P., Facets and valid inequalities for the time-dependent travelling salesman problem (2013) European Journal of Operational Research, , May
  • Godinho, M.T., Gouveia, L., Pesneau, P., Natural and extended formulations for the time-dependent traveling salesman problem (2014) Discrete Applied Mathematics, 164, pp. 138-153. , Feb
  • Feo, T.A., Resende, M.G., Greedy randomized adaptive search procedures (1995) Journal of Global Optimization, 6 (2), pp. 109-133
  • Hansen, P., Mladenovic, N., Variable neighborhood search (1997) Computers &Operations Research, 24 (1), pp. 1097-1100
  • Salehipour, A., Sorensen, K., Goos, P., Braysy, O., Efficient grasp+vnd and grasp+vns metaheuristics for the traveling repairman problem (2011) 4OR, 9, pp. 189-209
  • Mladenovic, N., Urosevic, 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) European Journal of Operational Research, 221 (3), pp. 513-520
  • Sarmiento, A., Murrieta-Cid, R., Hutchinson, S., A multi-robot strategy for rapidly searching a polygonal environment (2004) Advances in Artificial Intelligence-IBERAMIA 2004, Ser. Lecture Notes in Computer Science, 3315, pp. 484-493. , , C. Lematre, C. A. Reyes, and J. A. Gonzlez, Eds.Springer
  • Koutsoupias, E., Papadimitriou, C., Yannakakis, M., Searching a fixed graph (1996) Automata, Languages and Programming, Ser. Lecture Notes in Computer Science, 1099, pp. 280-289. , F. Meyer and B. Monien, Eds. Springer Berlin Heidelberg
  • Ausiello, G., Leonardi, S., Marchetti-Spaccamela, A., On salesmen, repairmen, spiders, and other traveling agents (2000) Algorithms and Complexity, Ser. Lecture Notes in Computer Science, 1767, pp. 1-16. , G. Bongiovanni, R. Petreschi, and G. Gambosi, Eds. Springer Berlin Heidelberg
  • Kulich, M., Miranda-Bront, J.J., Preucil, L., A meta-heuristic based goal-selection strategy for mobile robot search in an unknown environment (2016) Computers &Operations Research, , in press
  • Sathyan, A., Boone, N., Cohen, K., Comparison of approximate approaches to solving the travelling salesman problem and its application to uav swarming (2015) International Journal of Unmanned Systems Engineering, 3 (1), pp. 1-16
  • Boone, N., Sathyan, A., Cohen, K., Enhanced approaches to solving the multiple traveling salesman problem (2015) AIAA Infotech@ Aerospace, , American Institute of Aeronautics and Astronautics
  • Geetha, S., Poonthalir, G., Vanathi, P., Improved k-means algorithm for capacitated clustering problem (2009) INFOCOMP Journal of Computer Science, 8 (4), pp. 52-59
  • Faigl, J., Kulich, M., Preucil, L., Goal assignment using distance cost in multi-robot exploration (2012) Intelligent Robots and Systems (IROS), 2012 IEEE/RSJ Int. Conf. on, pp. 3741-3746. , oct
  • Reinelt, G., Tsplib-A traveling salesman problem library (1991) INFORMS Journal on Computing, 3 (4), pp. 376-384
  • Lin, S., Kernighan, B., An effective heuristic algorithm for the traveling-salesman problem (1973) Operations Research
  • Arthur, D., Vassilvitskii, S., K-means++: The advantages of careful seeding (2007) Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Ser. SODA '07, pp. 1027-1035. , Philadelphia, PA, USA: Society for Industrial and Applied MathematicsA4 -

Citas:

---------- APA ----------
Kulich, M., Preucil, L. & Bront, J.J.M. (2017) . On multi-robot search for a stationary object. 2017 European Conference on Mobile Robots, ECMR 2017.
http://dx.doi.org/10.1109/ECMR.2017.8098696
---------- CHICAGO ----------
Kulich, M., Preucil, L., Bront, J.J.M. "On multi-robot search for a stationary object" . 2017 European Conference on Mobile Robots, ECMR 2017 (2017).
http://dx.doi.org/10.1109/ECMR.2017.8098696
---------- MLA ----------
Kulich, M., Preucil, L., Bront, J.J.M. "On multi-robot search for a stationary object" . 2017 European Conference on Mobile Robots, ECMR 2017, 2017.
http://dx.doi.org/10.1109/ECMR.2017.8098696
---------- VANCOUVER ----------
Kulich, M., Preucil, L., Bront, J.J.M. On multi-robot search for a stationary object. European Conf. Mob. Robots, ECMR. 2017.
http://dx.doi.org/10.1109/ECMR.2017.8098696