Sensor-based Planning for a Rod-shaped Robot in Three Dimensions: Piecewise Retracts of R3 × S2

Abstract

We present a new roadmap for a rod-shaped robot operating in a three-dimensional workspace, whose configuration space is diffeomorphic to R ³ × S ². This roadmap is called the rod hierarchical generalized Voronoi graph (rod-HGVG) and can be used to find a path between any two points in an unknown configuration space using only the sensor data. More importantly, the rod-HGVG serves as a basis for an algorithm to explore an unknown configuration space without explicitly constructing it. Once the rod-HGVG is constructed, the planner can use it to plan a path between any two configurations. One of the challenges in defining the roadmap revolves around a homotopy theory result, which asserts that there cannot be a one-dimensional deformation retract of a non-contractible space with dimension greater than two. Instead, we define an exact cellular decomposition on the free configuration space and a deformation retract in each cell (each cell is contractible). Next, we “connect” the deformation retracts of each of the cells using a roadmap of the workspace. We call this roadmap a piecewise retract because it comprises many deformation retracts. Exploiting the fact that the rod-HGVG is defined in terms of workspace distance measurements, we prescribe an incremental procedure to construct the rod-HGVG that uses the distance information that can be obtained from conventional range sensors.

Get full access to this article

View all access options for this article.

References

Abraham, R., Marsden, J. E., and Raitu, T. 1988. Manifolds, Tensor Analysis and Applications, 2nd edition, Springer-Verlag, New York .

Acar, E. U., Choset, H., and Atkar, P. N. 2001. Complete sensor-based coverage with extended-range detectors: a hierarchical decomposition in terms of critical points and Voronoi diagrams . Proceedings of the 2001 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Maui, HI, October.

Aurenhammer, F. 1991. Voronoi diagrams—a survey of a fundamental geometric data structure . ACM Computing Surveys 23(3): 345-405 .

Aurenhammer, F. and Klein, R. 2000. Voronoi diagrams. Handbook of Computational Geometry, J. Sack and G. Urrutia, editors, Elsevier, Amsterdam , Chapter V, pp. 201-290.

Borenstein, J. and Koren, Y. 1998. Real-time obstacle avoidance for fast mobile robots . IEEE Transactions on Systems, Man and Cybernetics 19(5): 1179-1187 .

Brand, L. 1966. Differential and Difference Equations, Wiley, New York .

Bredon, G. 1995. Topology and Geometry, 3rd edition, Springer-Verlag, Berlin .

Brooks, R. A. 1983. Solving the find-path problem by good representation of free space . IEEE Transaction on Systems, Man and Cybernetics 13(3): 190-197 .

Brooks, R. A. and Lozano-Pérez, T. 1983. A subdivision algorithm in configuration space for Findpath with rotation . Proceedings of the International Joint Conference on Artificial Intelligence, Karlsruhe, Germany, August, pp. 799-806 .

10.

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

11.

Choset, H. and Burdick, J. 2000a. Sensor-based motion planning: the hierarchical generalized Voronoi graph . International Journal of Robotics Research 19(2): 96-125 .

12.

Choset, H. and Burdick, J. 2000b. Sensor-based motion planning: incremental construction of the hierarchical generalized Voronoi graph . International Journal of Robotics Research 19(2): 126-148 .

13.

Choset, H. and Burdick, J. W. 1996. Sensor-based planning for a planar rod robot . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Minneapolis, MN.

14.

Choset, H. and Lee, J. Y. 2001. Sensor-based construction of a retract-like structure for a planar rod robot . IEEE Transaction of Robotics and Automation 17(4): 435-449 .

15.

Chuang, J. H. and Ahuja, N. 1998. An analytically tractable potential fidel model of free space and its application in obstacle avoidance. IEEE Transactions on Systems, Man and Cybernetics - Part B: Cybernetics 28(5):729-736.

16.

Cox, J. and Yap, C. K. 1991. On-line motion planning: case of a planar rod . Annals of Mathematics and Artificial Intelligence 3: 1-20 .

17.

Dattasharma, A. and Sathiya Keerthi, S. 1995. An augmented Voronoi roadmap for 3D translational motion planning for a convex polyhedron moving amidst convex polyhedral obstacles . Theoretical Computer Science 140(2): 205-230 .

18.

Foskey, M., Garber, M., Lin, M., and Monocha, D. 2000. A Voronoi-based hybrid motion planner for rigid bodies. Technical Report TR00-025, UNC Chapel Hill Computer Science .

19.

Kavraki, L. 1997. Part orientation with programmable vector fields: two stable equilibria for most parts . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Albuquerque, NM, April.

20.

Kavraki, L. and Latombe, J.-C. 1994. Randomized preprocessing of configuration space for path planning: articulated robots . Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), Munich, Germany, pp. 1764-1771 .

21.

Kavraki, L., Svestka, P., Latombe, J.-C., and Overmars, M. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces . IEEE Transactions on Robotics and Automation 12(4): 566-580 .

22.

Khatib, O. 1986. Real-time obstacle avoidance for manipulators and mobile robots . International Journal of Robotics Research 5: 90-98 .

23.

Khosla, P. and Volpe, R. 1988. Superquadric artificial potential for obstacle avoidance and approach . Proceedings of the IEEE Conference on Robotics and Automation (ICRA), Philadelphia, PA, pp. 1778-1784 .

24.

Koren, Y. and Borenstein, J. 1991. Potential field methods and their inherent limitations for mobile robot navigation . Proceedings of the IEEE Conference on Robotics and Automation (ICRA), Sacramento, CA, pp. 1398-1404 .

25.

Kuan, D. T., Zamiska, J. C., and Brooks, R. A. 1985. Natural decomposition of free space for path planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), St. Louis, MO, pp. 168-173 .

26.

Kuffner, J. J. and LaValle, S. M. 2000. RRT-connect: an efficient approach to single-query path planning . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), San Francisco, CA, April 24-28, pp. 995-1001 .

27.

Latombe, J.-C. 1991. Robot Motion Planning, Kluwer Academic, Boston, MA .

28.

Latombe, J.-C., Kavraki, L. E., Svestka, P., and Overmars, M. 1996. Probabilistic roadmaps for path planning in high-dimensional configuration spaces . IEEE Transactions on Robotics and Automation 12(4): 566-580 .

29.

LaValle, S. M. 1998. Rapidly-exploring random trees: a new tool for path planning. Technical Report TR 98-11, Computer Science Department, Iowa State University , October.

30.

Lee, J. Y., Choset, H., and Rizzi, A. A. 2001. Sensor-based planning for rod-shaped robots in three dimensions: piecewise retracts of R3 × S2 . Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), Seoul, Korea, May 21-26, pp. 991-999 .

31.

Munkres, J. R. 2000. Topology, Prentice-Hall, Englewood Cliffs, NJ .

32.

Nilsson, N. J. 1969. A mobile automation: an application of artificial intelligence techniques . Proceedings of 1st International Joint Conference on Artificial Intelligence, Washington, DC.

33.

Noborio, H., Haniwa, T., and Arimoto, S. 1989.A feasible motion planning algorithm for a mobile robot on a quadtree representation . Proceedings of IEEE International Conference on Robotics and Automation (ICRA), Scottsdale, AZ, May, pp. 327-332 .

34.

Ó’Dúnlaing, C., Sharir, M., and Yap, C. K. 1986. Generalized Voronoi diagrams for moving a ladder. I: topological analysis . Communications on Pure and Applied Mathematics 39: 423-483 .

35.

Ó’Dúnlaing, C. and Yap, C. K. 1985. A “retraction” method for planning the motion of a disc . Journal of Algorithms 6: 104-111 .

36.

Overmars, M. H. 1992. A random approach to motion planning. Technical Report RUU-CS-92-32, Department of Computational Science, Utrecht University, Utrecht, the Netherlands , October.

37.

Pisula, C., Hoff, K., Lin, M., and Manocha, D. 2000. Randomized path planning for a rigid body based on hardware accelerated Voronoi sampling . Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics (WAFR), Hanover, NH, March 16-18.

38.

Press, W. H., Teukolsky, S.A., Vetterling, W. T., and Flannery, B. P. 2002. Numerical Recipes in C++: The Art of Scientific Computing, 2nd edition, Cambridge University Press, Cambridge .

39.

Rimon, E 1997. ConstructionofC-spaceroadmapsfromlocal sensory data. What should the sensors look for? Algorithmica 17(4): 357-379 .

40.

Sharir, M. 1997. Algorithmic motion planning. Handbook of Discrete and Computational Geometry, J. E. Goodman and J. O’Rourke, editors, CRC Press, Boca Raton, FL , pp. 733-754.

41.

Thorpe, J. A. 1979. Elementary Topics in Differential Geometry, Springer-Verlag, Berlin .

42.

Wilmarth, S. A., Amato, N. M., and Stiller, P. F. 1999. Motion planning for a rigid body using random networks on the medial axis of the free space . Proceedings of the 15th Annual ACM Symposium on Computational Geometry, Miami Beach, FL, June, pp. 173-180 .

43.

Yu, Y. and Gupta, K. 1999. On sensor-based roadmap: a framework for motion planning for a manipulator arm in unknown environment . Proceedings of the IEEE/RSJ International Conference on Intelligent Robotics and Systems, Kyongju, Korea, pp. 1919-1924 .

Supplementary Material

Please find the following supplemental material available below.

For Open Access articles published under a Creative Commons License, all supplemental material carries the same license as the article it is associated with.

For non-Open Access articles published, all supplemental material carries a non-exclusive license, and permission requests for re-use of supplemental material or any part of supplemental material shall be sent directly to the copyright owner as specified in the copyright notice associated with the article.

0.00 MB