Multi-robot exploration on grids with a bounded time

Document Type : Research Note


Department of Computer Science and Information Technology, Institute for Advanced Studies in Basic Science, Gavazang, Zanjan



In this paper, the problem of exploring a grid environment in the offline setting has been studied.\ The goal is to propose an algorithm to find the minimum number of robots for exploring a rectangular grid environment with $n$ rows and $m$ columns, denoted by $R(n,m)$, in a predefined time $T$. In the case that there are no obstacles in the environment, an optimal solution has been proposed for the problem.\ In the other case when the environment may contain some obstacles, it has been pointed out that the problem is NP-complete and cannot be approximated within better than a factor 2.\ Finally, a $4$-approximation algorithm has been presented in order to explore $R(n,m)$ in the presence of obstacles.


References      1. Walenz, B. Multi robot coverage and exploration: a      survey of existing techniques" (2016).      2. Blatt, F. and Szczerbicka, H. Combining the multiagent      ood algorithm with frontier-based exploration      in search & rescue applications", International Symposium      on Performance Evaluation of Computer and      Telecommunication Systems (SPECTS), IEEE, pp. 1{      7 (2017).      1526 M. Davoodi et al./Scientia Iranica, Transactions D: Computer Science & ... 28 (2021) 1515{1528      3. Davoodi, M., Abedin, M., Banyassady, B.,      Khanteimouri, P., and Mohades, A. An optimal      algorithm for two robots path planning problem on      the grid", Robotics and Autonomous Systems, 61(12).      pp. 1406{1414 (2013).      4. Davoodi, M. Bi-objective path planning using deterministic      algorithms", Robotics and Autonomous Systems,      93, pp. 105{115 (2003).      5. Davoodi, M., Panahi, F., Mohades, A., and Hashemi,      S.N. Multi-objective path planning in discrete space",      Applied Soft Computing, 13(1), pp. 709{720 (2013).      6. Haynes, P.S., Alboul, L., and Penders, J. Dynamic      graph-based search in unknown environments", Journal      of Discrete Algorithms, 12, pp. 2{13 (2012).      7. Dereniowski, D., Disser, Y., Kosowski, A., Pajkak,      D., and Uzna_nski, P. Fast collaborative graph exploration",      Information and Computation, 243, pp. 37{49      (2015).      8. Davoodi, M., Panahi, F., Mohades, A., and Hashemi,      S.N. Clear and smooth path planning", Applied Soft      Computing, 32, pp. 568{579 (2015).      9. Chen, C.Y. and Ko, C.C. An evolutionary method to      vision-based self-localization for soccer robots", Scientia      Iranica, Transaction B, Mechanical Engineering,      22(6), pp. 2071{2080 (2015).      10. Bahar, M.R.B., Ghiasi, A.R., and Bahar, H.B. Grid      roadmap based ANN corridor search for collision free,      path planning", Scientia Iranica, 19(6), pp. 1850{1855      (2012).      11. Kumar, P.B., Sahu, C., Parhi, D.R., Pandey, K.K.,      and Chhotray, A. Static and dynamic path planning      of humanoids using an advanced regression controller",      Scientia Iranica, 26(1), pp. 375{393 (2019).      12. Book, R.V., Michael, R.G., and David, S.J. Computers      and intractability: A guide to the theory of NPcompleteness",      Bulletin (New Series) of the American      Mathematical Society, 3(2), pp. 898{904 (1980).      13. Christo_des, N. Worst-case analysis of a new heuristic      for the travelling salesman problem", Carnegie-Mellon      Univ Pittsburgh Pa Management Sciences Research      Group (1976).      14. Rigni, M., Koutsoupias, E., and Papadimitriou, C.      An approximation scheme for planar graph TSP",      Proceedings of IEEE 36th Annual Foundations of Computer      Science, 11(4), pp. 640{645 (1995).      15. Arora, S. Polynomial time approximation schemes      for Euclidean traveling salesman and other geometric      problems", ACM, 45(5), pp. 753{782 (1998).      16. Gri_th, J.C., A Meta-Algorithm Analysis of the      Traveling Salesman Problem Using Cluster-Analysis      and Algorithm Recommendation, Bradley University      (2013).      17. Arkin, E.M., Fekete, S.P., and Mitchell, J.S. Approximation      algorithms for lawn mowing and milling",      Elsevier, 17(1{2), pp. 25{50 (2000).      18. Ntafos, S. Watchman routes under limited visibility",      Elsevier, 1(3), pp. 149{170 (1992).      19. Wernli, D. Grid exploration", Master Thesis, ETH      Zurich, Department of Computer Science (2012).      20. Arkin, E.M., Bender, M.A., Demaine, E.D., Fekete,      S.P., Mitchell, J.S., and Sethia, S. Optimal covering      tours with turn costs", SIAM, 35(3), pp. 531{566      (2005).      21. Pajak, D., Algorithms for Deterministic Parallel Graph      Exploration, Universit_e Sciences et Technologies-      Bordeaux I (2014).      22. Umans, C. and Lenhart, W. Hamiltonian cycles in      solid grid graphs", IEEE, 11(4), pp. 496{505 (1997).      23. Itai, A., Papadimitriou, C.H., and Szwarc_ter, J.L.      Hamilton paths in grid graphs," SIAM, 11(4), pp.      676{686 (1982).      24. Salman, A.N.M., Baskoro, E.T., and Broersma, H.J.      A note concerning Hamilton cycles in some classes of      grid graphs", ACM, 35(1), pp. 65{70 (2003).      25. Fischer, A. and Hungerlander, P. The traveling salesman      problem on grids with forbidden neighborhoods",      Journal of Combinatorial Optimization, 34(3), pp.      891{915 (2017).      26. Davoodi, M., Ghadikolaei, M.K., and Malekizadeh,      M.M. Exploring rectangular grid environments",      1st Iranian Conference on Computational Geometry,      Tehran, Iran (2018).      27. Senarathne, P.G.C.N. and Wang, D. Incremental      algorithms for safe and reachable Frontier detection      for robot exploration", Robotics and Autonomous Systems,      72, pp. 189{206 (2015).      28. Gabriely, Y., and Rimon, E. Spanning-tree based coverage      of continuous areas by a mobile robot", Annals of      Mathematics and Arti_cial, Intelligence, 31(1{4), pp.      77{98 (2001).      29. Czyzowicz, J., Dereniowski, D., Gkasieniec, L., Klasing,      R., Kosowski, A., and Pajkak, D. Collisionfree      network exploration", Journal of Computer and      System Sciences, 86, pp. 70{81 (2017).      30. Disser, Y., Mousset, F., Noever, A., _Skori_c, N., and      Steger, A. A general lower bound for collaborative      tree exploration", International Colloquium on Structural      Information and Communication Complexity,      Springer, Cham, pp. 125{139 (2017).      31. Bampas, E., Chalopin, J., Das, S., Hackfeld,      J., and Karousatou, C. Maximal exploration of      trees with energy-constrained agents", arXiv preprint      arXiv:1802.06636 (2018).