Optimal graph exploration without good maps. (English) Zbl 1071.68081
Summary: A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm \(\mathcal A\) is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class \(\mathcal U\), is called the overhead of algorithm \(\mathcal A\) for the class \(\mathcal U\) of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map).
For all of the above scenarios, we construct natural exploration algorithms that have smallest, or – in one case – close to smallest, overhead. While for the class of all graphs, depth-first search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at least \(\sqrt 3\) but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is \(\frac 3 2\). We also consider exploration of the class of lines (simple paths). In this case, depth-first search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is \(\sqrt 3\). Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is \(\frac 7 5\). An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms.
For all of the above scenarios, we construct natural exploration algorithms that have smallest, or – in one case – close to smallest, overhead. While for the class of all graphs, depth-first search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at least \(\sqrt 3\) but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is \(\frac 3 2\). We also consider exploration of the class of lines (simple paths). In this case, depth-first search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is \(\sqrt 3\). Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is \(\frac 7 5\). An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 05C85 | Graph algorithms (graph-theoretic aspects) |
| 68T40 | Artificial intelligence for robotics |
Keywords:
exploration algorithmsReferences:
| [1] | Albers, S.; Henzinger, M. R., Exploring unknown environments, SIAM J. Comput., 29, 1164-1188 (2000) · Zbl 0947.68165 |
| [2] | Awerbuch, B.; Betke, M.; Rivest, R.; Singh, M., Piecemeal graph learning by a mobile robot, (Proc. 8th Conf. on Computer Learning Theory (1995)), 321-328 |
| [3] | Bar-Eli, E.; Berman, P.; Fiat, A.; Yan, R., On-line navigation in a room, J. Algorithms, 17, 319-341 (1994) · Zbl 1321.68430 |
| [4] | Bender, M. A.; Fernandez, A.; Ron, D.; Sahai, A.; Vadhan, S., The power of a pebbleexploring and mapping directed graphs, (Proc. 30th Ann. Symp. on Theory of Computing (1998)), 269-278 · Zbl 1027.68652 |
| [5] | Bender, M. A.; Slonim, D., The power of team explorationtwo robots can learn unlabeled directed graphs, (Proc. 35th Ann. Symp. on Foundations of Computer Science (1994)), 75-85 |
| [6] | Betke, M.; Rivest, R.; Singh, M., Piecemeal learning of an unknown environment, Mach. Learn., 18, 231-254 (1995) |
| [7] | Blum, A.; Raghavan, P.; Schieber, B., Navigating in unfamiliar geometric terrain, SIAM J. Comput., 26, 110-137 (1997) · Zbl 1075.68608 |
| [8] | Deng, X.; Kameda, T.; Papadimitriou, C. H., How to learn an unknown environment Ithe rectilinear case, J. ACM, 45, 215-245 (1998) · Zbl 0904.68115 |
| [9] | Deng, X.; Mirzaian, A., Competitive robot mapping with homogeneous markers, IEEE Trans. Robotics Automat., 12, 532-542 (1996) |
| [10] | Deng, X.; Papadimitriou, C. H., Exploring an unknown graph, J. Graph Theory, 32, 265-297 (1999) · Zbl 0941.68099 |
| [11] | Diks, K.; Fraigniaud, P.; Kranakis, E.; Pelc, A., Tree exploration with little memory, (Proc. 13th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA’2002), San Francisco, U.S.A. (January 2002)), 588-597 · Zbl 1093.68615 |
| [12] | Dudek, G.; Jenkin, M.; Milios, E.; Wilkes, D., Robotic exploration as graph construction, IEEE Trans. Robotics Automat., 7, 859-865 (1991) |
| [13] | Dujmović, V.; Whitesides, S., On validating planar worlds, (Proc. of the 12th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA’2001), Washington DC, U.S.A (January 2001)), 791-792 · Zbl 0988.05085 |
| [14] | Duncan, C. A.; Kobourov, S. G.; Kumar, V. S.A., Optimal constrained graph exploration, (Proc. 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (2001)), 807-814 · Zbl 0992.68160 |
| [15] | Panaite, P.; Pelc, A., Exploring unknown undirected graphs, J. Algorithms, 33, 281-295 (1999) · Zbl 0957.68092 |
| [16] | Panaite, P.; Pelc, A., Impact of topographic information on graph exploration efficiency, Networks, 36, 96-103 (2000) · Zbl 1145.68599 |
| [17] | N.S.V. Rao, S. Hareti, W. Shi, S.S. Iyengar, Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms, Technical Report ORNL/TM-12410, Oak Ridge National Laboratory, July 1993.; N.S.V. Rao, S. Hareti, W. Shi, S.S. Iyengar, Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms, Technical Report ORNL/TM-12410, Oak Ridge National Laboratory, July 1993. |
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.
