Piecemeal graph exploration by a mobile robot (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Piecemeal graph exploration by a mobile robot (extended abstract)

Full text

Pdf (844 KB)

Source

Annual Workshop on Computational Learning Theory archive
Proceedings of the eighth annual conference on Computational learning theory table of contents

Santa Cruz, California, United States

Pages: 321 - 328

Year of Publication: 1995

ISBN:0-89791-723-5

Authors

Baruch Awerbuch	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA and Johns Hopkins University, Baltimore, MD
Margrit Betke	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
Ronald L. Rivest	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA
Mona Singh	Laboratory for Computer Science, Massachusetts Institute of Technology, Cambridge, MA

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
University of California : University of California

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 29, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/225298.225337 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Baruch Awerbuch and Robert G. Gallager. Distributed BFS algorithms. The 25th Symposvurn on Foundations of Computer ,qczence, pages 250-256, October 1985.
	2	Baruch Awerbuch , Robert G. Gallager, A new distributed algorithm to find breadth first search trees, IEEE Transactions on Information Theory, v.33 n.3, p.315-322, May 1, 1987 [doi>10.1109/TIT.1987.1057314]
	3	E. Bar-Eli , Piotr Berman , A. Fiat , Peiyuan Yan, On-line navigation in a room, Proceedings of the third annual ACM-SIAM symposium on Discrete algorithms, p.237-249, September 1992, Orlando, Florida, United States
	4	R. Behringer and S. HStzel. Simultaneous estimation of pitch angle and lane width from the video image of a marked road. Ill IEEE/RSJ/GI International Conference on Intelligent flobols and ,qysterns, September 1994.
	5	Michael A. Bender and Donna K. Slonim. The power of team exploration: two robots can learn unlabeled directed graphs. In Proceedings of the Thirty-Fifth Annual Symposium on Foundatwns of Computer Science, pages 75-85, November 1994.
	6	M. Betke, ALGORITHMS FOR EXPLORING AN UNKNOWN GRAPH, Massachusetts Institute of Technology, Cambridge, MA, 1992
	7	Margrit Betke and Leonid Gurvits. Mobile robot localization using landmarks. IEEE/RSJ/GI International Conference on }7~tellige~t Robots and Systems, September 1994. To appear in IEEE Transactions on Robotics and Automation.
	8	Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal Learning of an Unknown Environment, Machine Learning, v.18 n.2-3, p.231-254, Feb./March 1995 [doi>10.1007/BF00993411]
	9	Avrim Blum and P. Chalasani. An on-line algorithm for improving performance in navigation. In Proceedings of the Thirty-Fourth Annual Symposium on Foundations of Computer Science, pages 2-11, November 1993.
	10	Avrim Blum , Prabhakar Raghavan , Baruch Schieber, Navigating in unfamiliar geometric terrain, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.494-504, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103419]
	11	Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest. Introductwn to Algordhrns. MIT Press/McGraw-Hill, 1990.
	12	Xiaotie Deng , Tiko Kameda , Christos Papadimitriou, How to learn an unknown environment (extended abstract), Proceedings of the 32nd annual symposium on Foundations of computer science, p.298-303, September 1991, San Juan, Puerto Rico [doi>10.1109/SFCS.1991.185382]
	13	Xiaotie Deng and Christos H. Papadimitriou. Exploring an unknown graph. In Proceedings of the 31st Symposium on Foundations of Computer Science, volume I, pages 355-361, 1990.
	14	Gregory Dudek, Michael Jenkin, Evangelos Milios, and David Wilkes. Using multiple markers in graph exploration. In SPIE Vol. 1195 Mobile Robots IV, pages 77 87, 1989.
	15	John Evans. HelpMaterM: An autonomous mobile robot courier for hospitals. In IEEE/RSJ/GI International Conference on IntelhgeT~l Robots and Systems, September {994.
	16	Rolf Klein, Walking an unknown street with bounded detour, Computational Geometry: Theory and Applications, v.1 n.6, p.325-351, June 1992 [doi>10.1016/0925-7721(92)90010-P]
	17	Jon IX{. Kteinberg. The localization problem for mobile robots. In Proceedings of the ThirIy-Flfih A~nual Symposium on Foundations of Cornp~tter Science, pages 521-531, May 1994.
	18	C. Y. Lee. An algorithm for path connection and its applications. IRE Transactwns o77 Electronic Computers, EC-10(3):346 365, 1961.
	19	Edward F. Moore. The shortest path through a maze. In Proceedings of the International Symposium on the Theory of Switching, pages 285-292 Harvard University Press, 1959.
	20	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest paths without a map, Theoretical Computer Science, v.84 n.1, p.127-150, July 22, 1991 [doi>10.1016/0304-3975(91)90263-2]
	21	Nagewara S. V. Rao, Srikumar Kareti, Weimin Shi, and S. Sitharama Iyengar. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Technical Report ORNL/TM-12410, Oak Ridge National Laboratory, .July 1993.
	22	Ronald L. Rivest , Robert E. Schapire, Inference of finite automata using homing sequences, Information and Computation, v.103 n.2, p.299-347, April 1993 [doi>10.1006/inco.1993.1021]

CITED BY 11

	Petrişor Panaite , Andrzej Pelc, Exploring unknown undirected graphs, Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, p.316-322, January 25-27, 1998, San Francisco, California, United States
	Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil Vadhan, The power of a pebble: exploring and mapping directed graphs, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.269-278, May 24-26, 1998, Dallas, Texas, United States
	Susanne Albers , Monika R. Henzinger, Exploring unknown environments, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.416-425, May 04-06, 1997, El Paso, Texas, United States
	Baruch Awerbuch , Stephen G. Kobourov, Polylogarithmic-overhead piecemeal graph exploration, Proceedings of the eleventh annual conference on Computational learning theory, p.280-286, July 24-26, 1998, Madison, Wisconsin, United States
	Krzysztof Diks , Pierre Fraigniaud , Evangelos Kranakis , Andrzej Pelc, Tree exploration with little memory, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.588-597, January 06-08, 2002, San Francisco, California
	Martin Kummer , Matthias Ott, Learning branches and learning to win closed games, Proceedings of the ninth annual conference on Computational learning theory, p.280-291, June 28-July 01, 1996, Desenzano del Garda, Italy
	Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil Vadhan, The power of a pebble: exploring and mapping directed graphs, Information and Computation, v.176 n.1, p.1-21, July 2002
	Krzysztof Diks , Pierre Fraigniaud , Evangelos Kranakis , Andrzej Pelc, Tree exploration with little memory, Journal of Algorithms, v.51 n.1, p.38-63, 1 April 2004
	Anders Dessmark , Andrzej Pelc, Optimal graph exploration without good maps, Theoretical Computer Science, v.326 n.1-3, p.343-362, 20 October 2004
	Pierre Fraigniaud , David Ilcinkas , Andrzej Pelc, Tree exploration with advice, Information and Computation, v.206 n.11, p.1276-1287, November, 2008
	Leszek Gasieniec , Andrzej Pelc , Tomasz Radzik , Xiaohui Zhang, Tree exploration with logarithmic memory, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.585-594, January 07-09, 2007, New Orleans, Louisiana