Hostname: page-component-78c5997874-v9fdk Total loading time: 0 Render date: 2024-11-04T18:12:44.348Z Has data issue: false hasContentIssue false
  • English
  • Français

Terrain Exploration of a Sensor-Based Robot Moving Among Unknown Obstacles of Polygonal Shape

Published online by Cambridge University Press:  09 March 2009

Zen Chen  and
Chih-Ming Huang
Zen Chen
Affiliation:
Institute of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan 30050 (Republic of China)
Chih-Ming Huang
Affiliation:
Institute of Computer Science and Information Engineering, National Chiao Tung University, Hsinchu, Taiwan 30050 (Republic of China)
Get access Rights & Permissions [Opens in a new window]

Extract

The problem of incremental terrain acquisition is addressed in this paper. Through a systematic planning of movements in an unknown terrain filled with polygonal obstacles, a sensor-based robot is shown to be able to incrementally build the entire terrain model; the model will be described in terms of visibility graph and visibility window. The terrain model is built area by area without any overlapping between explored areas. As a consequence, the terrain is obtained as a tessellation of disjoint star polygons. And the adjacency relations between star polygons are represented by a star polygon adjacency graph (SPAG graph). The incremental exploration process consists of two basic tasks: local exploration and exploration merging. Useful lemmas are derived for these two tasks and, then, the algorithms for the tasks are given. Examples are used to illustrate the algorithms. Two strategies for planning robot movements in the unknown terrain environment are suggested and compared. They are the depth-first search and the breadth-first search applied to the SPAG graph. Finally, the performance evaluation of the method and comparison with some existing methods are presented.

Keywords

Terrain explorationVisibility graphVisibility windowStar polygonExploration updatingExploration strategies.
Type
Research Article
Information
Robotica , Volume 12 , Issue 1 , January 1994 , pp. 33 - 44
Copyright
Copyright © Cambridge University Press 1994

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Brooks, R.A., “Solving the find-path problem by good representation of free space” IEEE Trans. on Systems, Man, and Cybernetics SMC-13, No. 3, 190–196 (03/04. 1983).CrossRefGoogle Scholar
2.Singh, J.S. and Wagh, M.D., “Robot path planning using intersecting convex shapes: analysis and simulation” IEEE J. Robotics and Automation RA-3, No. 2, 101–108 (04, 1987).Google Scholar
3.Rueb, K.D. and Wong, A.K.C., “structuring free space as a hypergraph for roving robot path planning and navigation” IEEE Trans. on Pattern Analysis and Machine Intelligence PAID-9, No. 2, 263–273 (03, 1987).Google Scholar
4.Kuan, D.T., Zamiska, J.C. and Brooks, R.A., “Natural decomposition of free space for path planning” IEEE International Conference on Robotics and Automation (1985) pp. 168–173.Google Scholar
5.Takahashi, O. and Schilling, R.J., “Motion planning in a plane using generalized Voronoi diagram” IEEE J. Robotics and Automation 5, No. 2, 143–150 (04, 1989).Google Scholar
6.Canny, J., “A Voronoi method for the piano-movers problem” IEEE International Conference on Robotics and Automation (1985), pp. 530–535.Google Scholar
7.Oommen, B.J., Iyengar, S.S., Rao, N.S.V. and Kashyap, R.L., “Robot navigation in unknown terrains using learned visibility graphs. Part I: The disjoint convex obstacle case” IEEE J. Robotics and Automation RA-3, No. 6, 672–680 (12, 1987).CrossRefGoogle Scholar
8.Rao, N.S.V., Iyengar, S.S., Oomen, B.J. and Kashyap, R.L., “Terrain acquisition by point robot amidst polyhedral obstacle” IEEE International Conference on Robotics and Automation (1987) pp. 170–175.Google Scholar
9.Welzl, E., “Constructing the visibility graph for n-line segment in O(n2) time” Information Processing Levers 20, 167–171 (1985).Google Scholar
10.Lozano-Perez, T., “Spatial planning: A configuration space approach” IEEE Trans. Comput. c-32, No. 2, 108–119 (1983).Google Scholar
11.Asano, T., Gulbas, L., Hershberger, J. and Imai, H., “Visibility polygon search and Euclidean shortest paths” Proceedings 26th Symposium on Foundations of Computer Science (1985) pp. 155–164.Google Scholar
12.Lumelsky, V.J., Mukhopadhyay, S. and Sun, K., “Dynamic path planning in sensor-based terrain acquisition” IEEE J. Robotics and Automation 6, No. 4, 462–472 (1990).CrossRefGoogle Scholar
13.Lumelsky, V.J. and Stepanov, A.A., “Path-planning strategies for a point mobile automation moving amidst unknown obstacles of arbitrary shape” Algorithmica 2, 403–430 (1987).CrossRefGoogle Scholar
14.Sankaranarayanan, A. and Vidyasagar, M., “Path planning for moving a point object amidst unknown obstacles in a plane: The universal lower bound on worst case path lengths and a classification of algorithms” IEEE International Conference on Robotics and Automation (1991) pp. 1734–1741.Google Scholar