Ability of a Robot to Travel Through its Free Work Space in an Environment with Obstacles

Abstract

This article presents a new geometric analysis of the free work space of a robot among obstacles. The free work space (FW) is defined as the set of positions and orientations that the robot's end effector can reach, according to the joint limits and the various obstacles lying in the environment. The aim is to give global descriptions of the robot's ability to move in the operational space (which coincides with Carte sian space when only position coordinates are specified).

The main contribution of this work is the characterization of the effects of obstacles on the work space geometry, as well as on its topology. The ability of a robot to move freely in its work space (called the "moveability") is difficult to describe and needs stringent formalizations. The concept of move ability is introduced through various properties and their cor responding necessary and sufficient conditions. Using a Con structive Solid Geometry (CSG) Computer-Aided Design (CAD) description of robots and obstacles and an octree model of the FW, these properties permit characterization of selected moveability areas in the FW, where, for instance, any n points can be linked together or where any continuous trajectory can be achieved without changing configuration. This new global description is of great interest for the user of CAD systems when designing robotic cells.

Get full access to this article

View all access options for this article.

References

Bernard, F. 1984. CATIA: du dessin au volume, de la cinématique aux calculs scientifiques, de la commande numérique à la robotique, un outil complet de C.F.A.O. Proc. M.I.C.A.D., (2):1082-1097.

Borrel, P. 1986. A study of multiple manipulator inverse kinematic solutions with applications to trajectory planning and workspaces determination. IEEE Conf Robot. Automat., pp. 1181-1185.

Brady, M. , Hollerbach, J.M. , Johnson, T.L. , et al. 1982. Robot Motion: Planning and Control. Cambridge, Mass.: MIT Press.

Brooks, R.A. 1983a. Planning collision free motions for pick-and-place operations . Int. J. Robot. Res. 2(4):19-44.

Brooks, R.A. 1983b. Solving the path-finding problem by good representation of free space. IEEE Trans. Sys. Man. Cybernet. SMC-13:190-197.

Canny, J.F. 1987 (Los Angeles). A new algebraic method for robot motion planning and real geometry. Presented at IEEE 28th symposium.

Canny, J.F. , and Reif, J. 1987 (Los Angeles). New lower bound techniques for robot motion planning problems. Presented at IEEE 28th symposium.

Canny, J.F. , and Donald, B.R. 1988. Simplified Voronoi diagrams. Discrete Computat. Geomet. 3(3):219-236.

Chedmail, P. , and Wenger, P. 1988 ( Karlsruhe, F.R.G. ). Ability of a robot to move between two points within cartesian free workspace with an encumbered environment . IFAC Symposium on Robots Control, pp. 73.1-73.6.

10.

Chedmail, P. , and Wenger, P. 1987 (Nantes, France). Domaine atteignable par un robot: Généralisation de la notion d'aspects a un environnement avec obstacles. Application aux robots articulés plans. Proc. AUM Symposium (2):312-313.

11.

Chedmail, P. , and Wenger, P. 1989 (Scottsdale, Arizona, May 14-19). Design and positioning of a robot in an environment with obstacles using optimal research. IEEE Conf Robot. Automat. Vol. 2.

12.

Deligneres, S. 1987. Choix de morphologies de robots. Ph.D. thesis, E.N.S.M., Nantes, France.

13.

Dombre, E. , Fournier, A. , Quaro, C. , and Borrel, P. 1986. Trends in CAD/CAM systems for robotics. IEEE Conf Robot. Automat., pp. (3):1913-1918.

14.

Faverjon, B. 1984 (Atlanta). Obstacle avoidance using an octree in the configuration space of a manipulator. 1st IEEE Conf. Robot. Automat., pp. (1):504-512.

15.

Faverjon, B. 1986. Object level programming of industrial robots. IEEE Int. Conf Robot. Automat. 3:1406-1412.

16.

Gupta, K.C. , and Roth, B. 1982. Design considerations for manipulators workspace . ASME J. Mechan. Des. 104:704-711.

17.

Hansen, J.A. , Gupta, K.C. and Kazerounian, S.M.K. 1983. Generation and evaluation of the workspace of a manipulator. Int. J. Robot. Res. 2(3):22-31.

18.

Khalil, W. , and Kleinfinger, J.F. 1986. A new geometric notation for open and closed-loop robots. IEEE Int. Conf. Robot. Automat. 2:1174-1179.

19.

Khatib, O. 1985 (St. Louis). A real time obstacle avoidance for manipulator and mobile robots. IEEE Conf. Robot. Automat. pp. 500-505.

20.

Koditschek, D. 1987 (Raleigh). Exact robot navigation by means of potential functions: Some topological considerations. Proc. IEEE Int. Conf. Robot. (1):1-6.

21.

Kumar, A. , and Waldron, K. 1981. The workspaces of mechanical manipulators. ASME J. Mechan. Des. 103:665-672.

22.

Lenarcic, J. , Stanic, U. , and Oblak, P. 1988 (Ljubljana, Yugoslavia). Optimum design of robot mechanisms based on workspace analysis. Proc. Adv. in Rob. Kin., (1):59-165.

23.

Lozano-Pérez, T. 1986 (Philadelphia). A simple motion planning algorithm for general robot manipulators. Proc. Fifth Nat. Conf. for the Am. Assoc. of Art. Int., pp. 626-631.

24.

Lozano-Pérez, T. , et al. 1987. Handley: A robot system that recognises, planes and manipulates. Proc. IEEE Int. Conf. Robot. Automat. , (2):843-849.

25.

Martin, D. , Martin, P. , Plemenos, D. 1985. La modèlisation des solides. Nantes , France, Université de Nantes, Institut de mathématiques et d'informatique. Res. rep. IMI-INFO-R20.

26.

O'Dunlaing, C. , Sharir, M. , and Yap, C. 1984. Generalized Voronoi diagrams for moving a ladder . NYU-Courant Institute, Robotics Lab., Technical rep. no. 32-33.

27.

Paden, B. , and Sastry, S. 1988. Optimal kinematics design of 6R manipulators. Int. J. Robot. Res. 7(2):43-61.

28.

Samet, H. 1979. Connected component labeling using quad-trees. College Park, Maryland, Computer Science Department , University of Maryland.

29.

Schwartz, J. , and Sharir, M. 1982. On the piano mover's problem: General techniques for computing topological properties of real algebraic manifolds. New York, N.Y., Computer Science Department, New York University , report no. 41.

30.

Vijiaykumar, R. , Waldron, J. , and Tsai, M.J. 1986. Geometric optimization of serial chain manipulator structures for working volume and dexterity. Int. J. Robot. Res. 5(2):91-103.

31.

Wenger, P. 1985. Modélisation du robot et de l'environnement en vue de la détection de collision. Nantes, France, D.E.A., Université de Nantes, E.N.S.M .

32.

Yang, D.C.H. , and Chiueh, T.S. 1986. Workspace of 6-joints robots with fixed hand orientation . Int. J. Robot. Automat. 1(1):23-32.

33.

Yu, Z.Q. , and Khalil, W. 1986 (Vienna, Dec. 3-5). Table look up for collision detection and safe operation of robots. IFAC Symposium on Theory of Robots, pp. 407-477.