Sensor-Based Exploration: Incremental Construction of the Hierarchical Generalized Voronoi Graph

Abstract

This paper prescribes an incremental procedure to construct roadmaps of unknown environments. Recall that a roadmap is a geometric structure that a robot uses to plan a path between two points in an environment. If the robot knows the roadmap, then it knows the environment. Likewise, if the robot constructs the roadmap, then it has effectively explored the environment. This paper focuses on the hierarchical generalized Voronoi graph (HGVG), detailed in the companion paper in this issue. The incremental construction procedure of the HGVG requires only local distance sensor measurements, and therefore the method can be used as a basis for sensor-based planning algorithms. Simulations and experiments using a mobile robot with ultrasonic sensors verify this approach.

Get full access to this article

View all access options for this article.

References

Avis, D., and Bhattacharya, B. K. 1983. Algorithms for computing D-dimensional Voronoi diagrams and their duals . Advances in Computing Research 1: 159–180 .

Borenstein, J., and Koren, J. 1990 (May). Real-time obstacle avoidance for fast mobile robots in cluttered environments . IEEE Conference of Robotics and Automation, pp. 572–577 .

Brooks, R. A. 1986. A robust layered control system for a mobile robot . IEEE Journal on Robotics and Automation RA-2(March).

Canny, J. F. 1988. The Complexity of Robot Motion Planning Cambridge, MA: MIT Press .

Canny, J. F., and Lin, M. C. 1993. An opportunistic global path planner . Algorithmica 10: 102–120 .

Choset, H. 1996. Sensor Based Motion Planning: The Hierarchical Generalized Voronoi Graph. Ph.D. thesis, California Institute of Technology, Pasadena, CA.

Choset, H. 1998. Nonsmooth analysis, convex analysis, and their applications to motion planning . Special Issue of the Int. J. of Comp. Geom. and Apps., to appear.

Choset, H., and Burdick, J. W. 1994. Sensor based planning and nonsmooth analysis . Proc. IEEE Int. Conf. on Robotics and Automation, pp. 3034–3041 .

Choset, H., and Burdick, J. W. 1995. Sensor based planning, Part I: The generalized Voronoi graph . Proc. IEEE Int. Conf. on Robotics and Automation.

10.

Choset, H., and Burdick, J. 2000. Sensor-based motion Exploration: The hierarchical generalized Voronoi graph . International Journal of Robotics Research 19: 119–148 .

11.

Keller, H. B. 1987. Lectures on Numerical Methods in Bifurcation Problems. Bombay, India: Tata Institute of Fundamental Research .

12.

Kuipers, B., and Byan, Y. T. 1991. A robot exploration and mapping strategy based on a semantic hierarchy of spatial representations . Journal of Robotics and Autonomous Systems 8: 47–63 .

13.

Rao, N.S.V., Kareti, S., Shi, W., and Iyenagar, S. S. 1993. Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms . Oak Ridge National Laboratory Technical Report ORNL/TM-12410(July): 1–58 .

14.

Rao, N.S.V., Stolzfus, N., and Iyengar, S. S. 1991. A retraction method for learned navigation in unknown terrains for a circular robot . IEEE Transactions on Robotics and Automation 7(October): 699–707 .

15.

Rimon, E., and Canny, J. F. 1994. Construction of C-space roadmaps using local sensory data—What should the sensors look for? Proc. IEEE Int. Conf. on Robotics and Automation, pp. 117–124 .