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.


[1] Walenz, B. Multi robot coverage and exploration: a survey of existing techniques (2016).
[2] Blatt, F. and Szczerbicka, H Combining the multi-agent ood algorithm with frontier-based exploration in search & rescue applications, International Symposium on Performance Evaluation of Computer and Telecommunication Systems (SPECTS) IEEE, pp. 17 (2017).
[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. 213 (2012).
[7] Dereniowski, D., Disser, Y., Kosowski, A., Paj¡k, D. and Uzna«ski, P. Fast collaborative graph exploration, Information and Computation, 243, pp. 3749 (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, APA 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 NP-completeness, Bulletin (New Series) of the American Mathematical Society (1979).
[13] Christodes, 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] Grith, 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é 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 Szwarcter, 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 Hungerländer, 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. 189206 (2015).
[28] Gabriely, Y., and Rimon, E. Spanning-tree based coverage of continuous areas by a mobile robot, Annals of mathematics and articial, intelligence, 31(1-4), pp. 77-98 (2001).
[29] Czyzowicz, J., Dereniowski, D., G¡sieniec, L., Klasing, R., Kosowski, A.,  and Paj¡k, D. Collision-free network exploration, Journal of Computer and System Sciences, 86, pp. 7081 (2017).
[30] Disser, Y., Mousset, F., Noever, A., ¬íkori¢, 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).