Navigating in unfamiliar geometric terrain

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Navigating in unfamiliar geometric terrain

Full text

Pdf (1.15 MB)

Source

Annual ACM Symposium on Theory of Computing archive
Proceedings of the twenty-third annual ACM symposium on Theory of computing table of contents

New Orleans, Louisiana, United States

Pages: 494 - 504

Year of Publication: 1991

ISBN:0-89791-397-3

Authors

Avrim Blum	Laboratory for Computer Science, MIT, Cambridge, MA
Prabhakar Raghavan	IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY
Baruch Schieber	IBM Research Division, T. J. Watson Research Center, Yorktown Heights, NY

Sponsor

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 4, Downloads (12 Months): 45, Citation Count: 23

Additional Information:

references cited by index terms review collaborative colleagues

Tools and Actions:	Request Permissions 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/103418.103419 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	Ricardo A. Baeza-Yates , Joseph C. Culberson , Gregory J. E. Rawlins, Searching in the plane, Information and Computation, v.106 n.2, p.234-252, Oct. 1993 [doi>10.1006/inco.1993.1054]
	2	S. Ben-David , A. Borodin , R. Karp , G. Tardos , A. Wigderson, On the power of randomization in online algorithms, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.379-386, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100268]
	3	A. Blum, A. Borodin, D. Foster, H.J. Karloff, Y. Mansour, P. Raghavan, M. Saks, and B. Schieber. Randomized on-line algorithms for graph closures. Personal communication, 1990.
	4	M. Blum and D. Kozen. On the power of the compass (or, why mazes are easier to search than graphs), in 19th Annual Symposium on Foundations of Computer Science, pages 132-142, October 1978.
	5	A. Borodin , N. Linial , M. Saks, An optimal online algorithm for metrical task systems, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.373-382, January 1987, New York, New York, United States [doi>10.1145/28395.28435]
	6	L. Cheng and J.D. McKendrick. Autonomous knowledge based navigation in an unknown two dimensional environment with convex polygonal obstacles. In Proc. of the int. Soc. Opt. Eng., volume 1095, pages 752-759, 1989.
	7	E.G. Coffman and E.N. Gilbert. Paths through a maze of rectangles. In preparation, AT&T Bell Labs, 1991.
	8	M. Daily, J. Harris, D. Keirsey, D. Olin, D. Payton, K. Rci#cr, J. Rosenblatt, D. T#eng, and V. Wong. Autonomous cross-country navigation with the ALV. in Proc. of the IEEE International Conference on Robotics and Automation, volume 2, pages 718-726, 1988.
	9	John Hallam , P. Forster , J. Howe, Map-Free Localisation in a Partially Moving 3D World: the Edinburgh Feature-Based Navigator, Intelligent Autonomous Systems 2, An International Conference, p.726-736, December 11-14, 1989
	10	B. Kalyanasundaram and K. Pruhs. Visual searching and mapping. Technical Report 90-15, Dept. of Computer Science, Univ. of Pittsburgh.
	11	Howard Karloff , Yuval Rabani , Yiftach Ravid, Lower bounds for randomized k-server and motion-planning algorithms, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.279-288, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103450]
	12	V. Lumelsky. Algorithmic issues of sensor-based robot motion planning. In P6th IEEE Con}erence on Decision and Control, pages 1796-1801, 1987.
	13	V.J. Lumelsky and A.A. Stepanov. Dynamic path planning for a mobile automaton with limited information on the environment. IEEE Transactions on Automatic Control, AC-31:1058-1063, 1986.
	14	Mark S. Manasse , Lyle A. McGeoch , Daniel D. Sleator, Competitive algorithms for server problems, Journal of Algorithms, v.11 n.2, p.208-230, Jun. 1990 [doi>10.1016/0196-6774(90)90003-W]
	15	H. Moravec. The Stanford cart and the CMU rover. Proceedings o} the IEEE, 71:872-874, 1983.
	16	B.J. Oomen, S.S. Iyengar, N.S.V., Rao, and R.L. Kashyap. Robot navigation in unknown terrains using learned visibility graphs. Part I: The disjoint convex obstacle case. IEEE Journal o} Robotics and Automation, 3:672-681, 1987.
	17	Christos H. Papadimitriou , Mihalis Yannakakis, Shortest Paths Without a Map, Proceedings of the 16th International Colloquium on Automata, Languages and Programming, p.610-620, July 11-15, 1989
	18	N. S. Rao, Algorithmic Framework for Learned Robot Navigation in Unknown Terrains, Computer, v.22 n.6, p.37-43, June 1989 [doi>10.1109/2.30719]
	19	N.S.V. Rao, S.S. Iyengar, and G. deSaussure. The visit problem: visibility graph based solution. In IEEE International Conference on Robotics and Automation, pages 1650-1655, 1988.
	20	N.S.V. Rao, S.S. Iyengar, B.J. Oomen, and R.L. Kashyap. On terrain model acquisition by a point robot amid polyhedral obstacles. 1EEE Journal of Robotics and Automation, 4:450-455, 1988.
	21	C.N. Shen and G. Nagy. Autonomous navigation to provide long distance surface traverses for Mars rover sample return mission. In 1EEE International Symposium on Intelligent Control, pages 362-367, 1989.
	22	Daniel D. Sleator , Robert E. Tarjan, Amortized efficiency of list update and paging rules, Communications of the ACM, v.28 n.2, p.202-208, Feb. 1985 [doi>10.1145/2786.2793]
	23	C-K. Yap. Algorithmic motion planning. In J.T. Schwartz and C.K. Yap, editors, Advances in Robotics, pages 95-144. Lawrence Erlbaum Associated, Hillsdale, NJ, 1987.

CITED BY 23

	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
	Jon M. Kleinberg, On-line search in a simple polygon, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.8-15, January 23-25, 1994, Arlington, Virginia, 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
	Ming-Yang Kao , Yuan Ma , Michael Sipser , Yiqun Yin, Optimal constructions of hybrid algorithms, Proceedings of the fifth annual ACM-SIAM symposium on Discrete algorithms, p.372-381, January 23-25, 1994, Arlington, Virginia, 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
	Gregory Dudek , Kathleen Romanik , Sue Whitesides, Localizing a robot with minimum travel, Proceedings of the sixth annual ACM-SIAM symposium on Discrete algorithms, p.437-446, January 22-24, 1995, San Francisco, California, United States
	Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal learning of an unknown environment, Proceedings of the sixth annual conference on Computational learning theory, p.277-286, July 26-28, 1993, Santa Cruz, California, United States
	Dana Angluin , Jeffery Westbrook , Wenhong Zhu, Robot navigation with range queries, Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, p.469-478, May 22-24, 1996, Philadelphia, Pennsylvania, United States
	Baruch Awerbuch , Margrit Betke , Ronald L. Rivest , Mona Singh, Piecemeal graph exploration by a mobile robot (extended abstract), Proceedings of the eighth annual conference on Computational learning theory, p.321-328, July 05-08, 1995, Santa Cruz, California, United States
	Piotr Berman , Avrim Blum , Amos Fiat , Howard Karloff , Adi Rosén , Michael Saks, Randomized robot navigation algorithms, Proceedings of the seventh annual ACM-SIAM symposium on Discrete algorithms, p.75-84, January 28-30, 1996, Atlanta, Georgia, United States
	Christian A. Duncan , Stephen G. Kobourov , V. S. Anil Kumar, Optimal constrained graph exploration, Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms, p.807-814, January 07-09, 2001, Washington, D.C., United States
	Kathleen Romanik , Sven Schuierer, Optimal robot localization in trees, Proceedings of the twelfth annual symposium on Computational geometry, p.264-273, May 24-26, 1996, Philadelphia, Pennsylvania, United States
	Frank Hoffmann , Christian Icking , Rolf Klein , Klaus Kriegel, A competitive strategy for learning a polygon, Proceedings of the eighth annual ACM-SIAM symposium on Discrete algorithms, p.166-174, January 05-07, 1997, New Orleans, Louisiana, United States
	Sandeep K. S. Gupta , Goran Konjevod , Georgios Varsamopoulos, A theoretical study of optimization techniques used in registration area based location management: models and online algorithms, Proceedings of the 6th international workshop on Discrete algorithms and methods for mobile computing and communications, September 28-28, 2002, Atlanta, Georgia, USA
	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
	Yair Bartal , Avrim Blum , Carl Burch , Andrew Tomkins, A polylog(n)-competitive algorithm for metrical task systems, Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, p.711-719, May 04-06, 1997, El Paso, Texas, United States
	Xiaotie Deng , Sanjeev Mahajan, Infinite games: randomization, computability, and applications to online problems, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.289-298, May 05-08, 1991, New Orleans, Louisiana, United States
	Ming-Yang Kao , John H. Reif , Stephen R. Tate, Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.441-447, January 25-27, 1993, Austin, Texas, United States
	Amitava Datta , Christian Icking, Competitive searching in a generalized street, Proceedings of the tenth annual symposium on Computational geometry, p.175-182, June 06-08, 1994, Stony Brook, New York, United States
	Alejandro López-Ortiz , Sven Schuierer, Searching and on-line recognition of star-shaped polygons, Information and Computation, v.185 n.1, p.66-88, August 25, 2003
	Amitava Datta , Subbiah Soundaralakshmi, On-line path planning in an unknown polygonal environment, Information Sciences—Informatics and Computer Science: An International Journal, v.164 n.1-4, p.89-111, 2 August 2004
	Carlos Rodríguez Lucatero , Rafael Lozano Espinosa, Application of automata learning algorithms to robot motion tracking, Proceedings of the 4th WSEAS International Conference on Signal Processing, Robotics and Automation, p.1-6, February 13-15, 2005, Salzburg, Austria
	Yoav Gabriely , Elon Rimon, Spanning-tree based coverage of continuous areas by a mobile robot, Annals of Mathematics and Artificial Intelligence, v.31 n.1-4, p.77-98, 2001

INDEX TERMS

Primary Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Geometrical problems and computations

Additional Classification:
I. Computing Methodologies
I.2 ARTIFICIAL INTELLIGENCE

General Terms:
Algorithms, Design, Theory

REVIEW

"Kirk Pruhs : Reviewer"

The setting for the problems considered in this paper is a plane littered with obstacles and inhabited by a robot. The locations and shapes of the obstacles are initially unknown to the robot. The robot's goal is to find a short, obstacle-avoi more...

Collaborative Colleagues:

Avrim Blum: colleagues

Prabhakar Raghavan: colleagues

Baruch Schieber: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player