Piecemeal graph exploration by a mobile robot. (English) Zbl 1045.68611
Summary: We study how a mobile robot can learn an unknown environment in a piecemeal manner. The robot’s goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph \(G=(V, E)\) in which the robot explores every vertex and edge in the graph by traversing at most \(O(E+V^{1+o(1)})\) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most \(O(E+V^2)\) edges. We also give an application of piecemeal learning to the problem of searching a graph for a “treasure”.
MSC:
| 68T40 | Artificial intelligence for robotics |
References:
| [1] | Awerbuch, B.; Berger, B.; Cohen, L.; Peleg, D., Near-linear time construction of sparse neighborhood covers, SIAM J. Comput., 28, 254-262 (1998) |
| [2] | Awerbuch, B.; Gallager, R. G., Distributed BFS algorithm, Proceedings of the 26th Symposium on Foundations of Computer Science (1985), p. 250-256 |
| [3] | Awerbuch, B.; Gallager, R. G., A new distributed algorithm to find breadth first search trees, IEEE Trans. Inform. Theory, IT-33, 315-332 (1987) · Zbl 0629.68070 |
| [4] | Bar-Eli, E.; Berman, P.; Fiat, A.; Yan, P., On-line navigation in a room, J. Algorithms, 17, 319-341 (1994) · Zbl 1321.68430 |
| [5] | Bender, M. A.; Slonim, D. K., The power of team exploration: two robots can learn unlabeled directed graphs, Proceedings of the Thirty-Fifth Annual Symposium on Foundations of Computer Science (1994), p. 75-85 |
| [6] | Betke, M. 1992, Algorithms for Exploring an Unknown Graph, Master’s thesis, MIT Department of Electrical Engineering and Computer Science, Published as MIT laboratory for Computer Science Technical Report MIT/LCS/TR-536, March 1992.; Betke, M. 1992, Algorithms for Exploring an Unknown Graph, Master’s thesis, MIT Department of Electrical Engineering and Computer Science, Published as MIT laboratory for Computer Science Technical Report MIT/LCS/TR-536, March 1992. |
| [7] | Betke, M.; Gurvits, L., Mobile robot localization using landmarks, IEEE Trans. Robot. Automat., 13, 251-263 (1997) |
| [8] | Betke, M.; Rivest, R. L.; Singh, M., Piecemeal learning of an unknown environment, Mach. Learning, 18, 231-254 (1995) |
| [9] | Blum, A.; Chalasani, P., An on-line algorithm for improving performance in navigation, Proceedings of the Thirty-Fourth Annual Symposium on Foundations of Computer Science (1993), p. 2-11 |
| [10] | Blum, A.; Raghavan, P.; Schieber, B., Navigating in unfamiliar geometric terrain, SIAM J. Comput., 26, 110-137 (1997) · Zbl 1075.68608 |
| [11] | Cormen, T. H.; Leiserson, C. E.; Rivest, R. L., Introduction to Algorithms (1990), MIT Press: MIT Press Cambridge · Zbl 1158.68538 |
| [12] | Deng, X.; Kameda, T.; Papadimitriou, C. H., How to learn an unknown environment I: The rectilinear case, J. Assoc. Comput. Mach., 45, 215-245 (1998) · Zbl 0904.68115 |
| [13] | Deng, X.; Papadimitriou, C. H., Exploring an unknown graph, Proceedings of the 31st Symposium on Foundations of Computer Science (1990), p. 355-361 |
| [14] | Dudek, G.; Jenkin, M.; Milios, E.; Wilkes, D., Using multiple markers in graph exploration, SPIE Vol. 1195 Mobile Robots IV (1989), p. 77-87 |
| [15] | Klein, R., Walking an unknown street with bounded detour, Comput. Geom. Theory Appl., 1, 325-351 (1992) · Zbl 0752.68086 |
| [16] | Kleinberg, J. M., The localization problem for mobile robots, Proceedings of the 35st Annual Symposium on Foundations of Computer Science (1994), p. 521-531 |
| [17] | Lee, C. Y., An algorithm for path connection and its applications, IRE Transactions on Electronic Computers, EC-10, 346-365 (1961) |
| [18] | Moore, E. F., The shortest path through a maze, Proceedings of the International Symposium on the Theory of Switching (1959), p. 285-292 |
| [19] | Papadimitriou, C. H.; Yanakakis, M., Shortest paths without a map, Theor. Comput. Sci., 84, 127-150 (1991) · Zbl 0733.68065 |
| [20] | Rao, N. S.V.; Kareti, S.; Shi, W.; Iyengar, S., Technical Report (1993) |
| [21] | Rivest, R. L.; Schapire, R. E., Inference of finite automata using homing sequences, Inform. and Comput., 103, 299-347 (1993) · Zbl 0786.68082 |
| [22] | Romanik, K.; Schuierer, S., Optimal robot localization in trees, Proceedings of the 12th Symposium on Foundations of Computational Geometry (1996) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
