×

On a simple depth-first search strategy for exploring unknown graphs. (English) Zbl 1509.68278

Dehne, Frank (ed.) et al., Algorithms and data structures. 5th international workshop, WADS ’97, Halifax, Nova Scotia, Canada, August 6–8, 1997. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1272, 345-353 (1997).
Summary: We preset a siple epth-first search strategy for exploring (constructing) an unknown strongly connected graph \(G\) with \(m\) edges and \(n\) vertices by traversing at most \(\min ( mn,dn^2 + m)\) edges. Here, \(d\) is the minimum number of edges needed to add to \(G\) to make it Eulerian. This parameter \(d\) is known as the deficiency of a graph and was introduced by S. Kutten [“Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks or: traversing one way streets with no map”, in: Proceedings of the 9th international conference on computer communication, ICCC’88. Amsterdam: Elsevier. 446–452 (1988)]. It was conjectured that graphs with high deficiency. X. Deng and C. H. Papadimitriou [“Exploring an unknown graph”, in: Proceedings of the 31st annual symposium on foundations of computer science, FOCS’90. Los Alamitos, CA: IEEE Computer Society. 355–361 (1990; doi:10.1109/FSCS.1990.89554)] provided evidence that the conjecture may be true by exhibiting a family of graphs where the robot can be forced to traverse \(\Omega (d^2m)\) edges in the worst case. Since then, there has been some interest in determining whether a graph with deficiency \(d\) can be explored by traversing \(O(\operatorname{poly}(d)m)\) edges. Our algorithm achieves such bound when the graph is dense, say \(m = \Omega (n^2)\).
For the entire collection see [Zbl 1492.68014].

MSC:

68T40 Artificial intelligence for robotics
68R10 Graph theory (including graph drawing) in computer science
68T20 Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] B. Awerbuch, M. Betke, R. Rivest, and M. Singh. Piecemeal graph exploration by a mobile robot. In Proc. 8th Annu. Conf. on Comput. Learning Theory, pages 321-328. ACM Press, New York, NY, 1995. · Zbl 1045.68611
[2] S. Albers and M. Henzinger. Exploring unknown environments. In Proc. 29th Annu. ACM Sympos. Theory Comput., pages 416-425, 1997. · Zbl 0968.68156
[3] D. Angluin, J. Westbrook, and W. Zhu.Robot navigation with range queries. In Proc. 28th Annu. ACM Sympos. Theory Comput., 1996. 469-478. · Zbl 0925.93673
[4] P. Berman, A. Blum, A. Fiat, H. Karloff, A. Rosen, and M. Saks. Randomized robot navigation algorithms. In Proceedings SODA 96, 1996. to appear. · Zbl 0960.68593
[5] A. Blum and P. Chalasani. An on-line algorithm for improving performance in navigation. In Proc. 34th Annu. IEEE Sympos. Found. Comput. Sci., pages 2-11. IEEE Computer Society Press, Los Alamitos, CA, 1993.
[6] A. Bar-Noy, S. Kutten, B. Scieber, and D. Peleg. Competitive unidirectional learning. Unpublished Manuscript, 1997.
[7] A. Blum, P. Raghavan, and B. Schieber. Navigating in unfamiliar geometric terrain. In Proc. 23th Annu. ACM Sympos. Theory Comput., pages 494-504. ACM, 1991. · Zbl 1075.68608
[8] M. Betke, R. Rivest, and M. Singh. Piecemeal learning of an unknown environment. Machine Learning, 18(2/3):231-254, 1995.
[9] M. Bender and D. Slonim. The power of team exploration: two robots can learn unlabeled directed graphs. In Proceedings of the 35rd Annual Symposium on Foundations of Computer Science, pages 75-85. IEEE Computer Society Press, Los Alamitos, CA, 1994.
[10] X. Deng, T. Kameda, and C. Papadimitriou. How to learn in an unknown environment. In Proc. of the 32nd Symposium on the Foundations of Comp. Sci., pages 298-303. IEEE Computer Society Press, Los Alamitos, CA, 1991.
[11] X. Deng and C. H. Papadimitriou. Exploring an unknown graph. In Proc. 31th Annu. IEEE Sympos. Found. Comput. Sci., volume I, pages 355-361, 1990.
[12] A. Fiat E. Bar-Eli, P. Berman and P. Yan. On-line navigation in a room. In Proc. 3rd SODA, pages 75-84, 1992.
[13] R. E. Korf. Real-time heuristic search. Artificial Intelligence, 42(3):189-211, 1990. · Zbl 0718.68082
[14] S. Keonig and Y. Smirnov. Graph learning with a nearest neighbor approach. In Proceedings of the 9th Conference on Computaitonal Learning Theory, pages 19-28, 1996.
[15] S. Kutten. Stepwise construction of an efficient distributed traversing algorithm for general strongly connected directed networks. In 9th International Conference on Computer Communication, Tel Aviv, Israel, pages 446-452, 1988.
[16] V. Lumelsky and A. Stepanov. Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Trans. on Automatic Control, AC-31:1059-1063, 1986. · Zbl 0615.93050
[17] V. Lumelsky and A. Stepanov. Path planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shapes. Algorithmica, 2:403-430, 1987. · Zbl 0643.68150
[18] V. Lumelsky and S. Tiwari. An algorithm for maze searching with azimuth input. In IEEE Conference on Robotics and Automation, pages 111-116, 1994.
[19] J.C. Pemberton and R.E. Korf. Incremental path planning on graphs with cycles. In Proceedings of the AI Planning Systems Conference, pages 179-188, 1992.
[20] C. Papadimitriou and C. Yannakakis. Shortest path wothout a map. Theoretical Computer Science, 84:127-150, 1991. · Zbl 0733.68065
[21] Y. Smirnov, S. Keonig, M. Veloso, and R. Simmons. Efficient goal-directed exploration. In Proceedings of the National Conference on AI, 1996. 292-297.
[22] Stentz. The focussed \(d^*\) algorithm for real-time replanning. In Proceedings of the International Joint Conf. on AI, pages 1652-1659, 1995.
[23] C. J. Taylor and D. J. Kriegman. Vision-based motion planning and exploration algorithms for mobile robots. In Proc. of the Workshop on Algorithmic Foundation of Robotics, 1994.
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.