OBSTACLE ANALYSIS FOR FAST ON-LINE

OBSTACLE ANALYSIS FOR FAST ON-LINE PLANNING IN A MULTI-ROBOT SYSTEM José Manuel Fuentes González Department of Systems Engineering and Automatic Control E.T.S.I.I. University of Valladolid. Spain Abstract: The present work describes an analysis of obstacles in a multi-robot system, allowing for fast path planning. In multi-robot systems, the obstacles for a robot are the rest of the robots, therefore, the possible shapes and situations of the obstacles are limited. If the robots are working on repetitive tasks, the set of obstacles is reduced to a smaller one. In many situations, searching all the configuration space would not be necessary, because collision free paths can be found exploring only a reduced subspace where path planning is fast INTRODUCTION

Motion planning for robots is basically the problem of given an initial and a final configuration of the robot in its workspace, find a path, starting at the initial configuration and terminating at the goal configuration, while avoiding collisions with the obstacles. From a theoretical point of view, motion planning has already been solved (Jacob, 83 and Canny, 88), in practice the complexity of algorithms still has many problems.

Most of the first planners were based on extensive searches in the configuration space (Brooks & Lozano-Perez, 83 and Latombe, 91). When used in spaces with more than three dimensions, these approaches showed that it is practically impossible to explore all the space. Potential field techniques are thought of for on line use (Khatib, 86), but they have one important drawback: the generation of local minima. Barraquand (92) describes numerical potential fields free of local minima. However, these potentials require an exploration of the entire configuration space. This method has been successfully used in robots with less than four degrees of freedom (Lee&Latombe, 95).

In many practical problems path planning is not difficult. This is the reason why emphasis has been currently placed on designing efficient algorithms that solve problems that may not be complete. Among these methods are potential fields with random motions (Barraquand, 90 and Lamiraux, 96), the exploration using smaller subspaces and backtracking (Gupta, 95), and the potential fields free of local minima (Kim&Khosla, 92 and Leena, 96). One of the latest approaches is based on probabilistic roadmaps (Kavraki, 94 and Kavraki, 96), that tries to characterize the connectivity of the configuration space.

The problem that inspires this work is based on the use of multiple robot arms systems composed of several manipulators that share common working areas. The robots must follow certain trajectories in order to complete their operations without colliding with other robots. In general they will be doing repetitive operations whose paths are determined. But, if for any reason the trajectory has to be changed, the robots must plan their trajectories on line.

Let us consider there are two robots in a workcell and they are moving in their usual trajectories. When one of them stops because of a failure, the other robot can continue working, but now there is a new obstacle in its way that must be avoided. Its path must be planned on line.The obstacle that the robot finds in its way is the other robot and since this robot has stopped while it was in its usual trajectory, there is some information about the obstacle we know. Instead of using a conventional method to explore all the configuration space for path planning, the authors propose to explore only a reduced set of the configuration space.

Some other methods have worked with the idea of exploring only reduced sets of the configuration space (Gupta, 90 and Lumelsky, 90). The contribution of this paper is to study the properties of obstacles so the reduced set of the configuration space is the most appropriated one, or at least is one that will lead to an efficient search. It is applied to a two robot system, where one robot's path is planned with three rotating links and the other robot's path has four rotating links.

PATH PLANNING USING REDUCED SUBSPACES

The method we present in this paper is based on a reduction of the search space into a two dimensional set. There are other two procedures that have used this same approach based on subspaces (Gupta, 90 and Lumelsky, 90). One is the Preplaned Path Method by Gupta and the other is due to Lumelsky.

Lumelsky (90) presents a plane in the configuration space for path searching. In Figure 1 we can see the configuration space of a three degrees of freedom robot. In this space there are two points defined, the start and ending points of the robot trajectory. The line that joins those points will be called the M-line (main line). If we restrict our search of collision free paths to a plane, the plane must contain both the initial and the final points, therefore it must contain the M line. The possible planes are those that contain the M line.

In Lumelsky's approach the planes are chosen based on the topologic properties of the configuration space of certain types of robots. It has been applied to two and some type of three links robots.

Figure 1: Configuration space of a three degrees of freedom robot

The approach we propose explores planes of the configuration space, but we would like to choose an appropriate plane based on our knowledge of the configuration space obstacles. The planes we propose are similar to the ones described by Lumelsky, since they contain the M line. The M line is defined by its tangent vector. If we call q _Ithe initial configuration of the robot and q _F the final one, this vector is t = (q _F- q _I) / || q _F- q _I || The planes containing this line are defined by a normal vector that is perpendicular to t. All the n vectors that have this property are the ones contained in the null space of t, n*t=0. A robot with three links in this space has 2 degrees of freedom. It is possible to find a base in this space, for example one of the vectors would be n₁ satisfying n1*t=0 and n1*u3=0, and the other n₂ such that n2*t=0 and n2*n1=0. Since the normal vector of our plane must be normalized, the number of degrees of freedom is restricted to one. A normal vector of the plane can be obtained by
n = cos a n₁ + sen a n₂

where a (alpha) is the angle between n and u3=(0,0,1). Thus, a plane is defined by this vector.

We could use a strategy similar to the ones described in Gupta (95) and Barraquand (92) to find a collision-free path in this plane. This is the mathematical potential field, which is a very efficient method in spaces with a low number of degrees of freedom. To efficiently apply this strategy, the plane has to be discretized and then the obstacles should be mapped into it. However, we should first obtain a set of discrete points along the plane. Thus, we choose two appropriate vectors that expand this plane for instance u1=t and u2 such that u2*t=0 and u2*n=0, both of them normalized.

A discrete net of points in this plane is defined by

q _k1,k2= q _I + D ₁ k₁ u₁ + D ₂ k₁ u₂(k1, k2 = 1, 2, 3, ....)

where D ₁and D ₂ are the discrete intervals, which length is related to the resolution of the configuration space.

OBSTACLE ANALYSIS IN THE CONFIGURATION SPACE

We have done a discrete mapping of obstacles in the configuration space to explore it. The obstacle in this case is only the other robot of the cell, this robot has four rotating links while the robot whose path is going to be calculated has only three degrees of freedom (three rotating links). This simple robot has been chosen because it is easier to visualize the configuration space. However, the approach can be extended to robots with more links, though in this case the search for appropriate planes would be more complicated.

The robots are two scorbot robots that work transporting certain pieces from one working position to another. When the obstacle robot moves from its initial to its final point, we divide its trajectory in 4 equally spaced points and then we present the possible collisions with the other robot in the configuration space as it is shown in Figure 2.

Figure 2: Shapes of the obstacle in the configuration space for different positions

In Figure 3 we can see several planes that contain the M line for the second position in Figure 2. We can see that at each point some planes are more adequate than others. The planes that lead to a dead end in any position of the obstacle are eliminated form the list of possible planes, and the most appropriate at every position are stored.

Figure 3: The planes that contain the M line for the second position

The plane chosen for the path planning has no dead ends in any of the snapshots of the trajectory and has a good behaviour for all of them.

In this example we choose the plane with a =45º. Furthermore, if we use a =0º or a =135º we cannot solve the problem.

CONCLUSIONS AND FUTURE WORK

We presented in this paper an analysis of the obstacles in a multi-robot system. This analysis is used for fast path planning in the robots system by searching for collision free paths in a reduced set of the configuration space. This analysis is done in a three link robot whose obstacle is a similar robot that faces it and that follows a predetermined trajectory.

Our future work will be mainly focused on finding better ways of analyzing the appropriate two dimensional subsets of the configuration space. We plan to apply this method to more general robots and situations. Further work needs to also be done on implementing a path search algorithm to compare this method with previous ones.

REFERENCES

Barraquand, J., Langloids, B. and Latombe, J.C. Numerical potential field techniques for robot path planning. IEEE Transactions on Systems, Man and Cybernetics., 22(2):224-241, 1992.

Brooks, R.A. and Lozano-Pérez T. A subdivision algorithm in configuration space for findpath with rotation. IEEE Transactions on Systems, Man and Cybernetics., SMC-15(2):224-233, 1985.

Gupta, K. A 7-dof practical motion planner based on sequential framework theory and experiments. In Invited paper in the Proc. Of IEEE International Symposium on Assembling and Task Planning (ISATP), 1985.

Kavraki, L. and Latombe, J.C. Randomized preprocessing of configuration space for fast path planning. In Proceedings of the IEEE International Conference on Robotics and Automation., 2138-2145, 1994.

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

Kim, J.O. Real-time obstacle avoidance using harmonic potential fields. IEEE Transactions on Robotics and Automation., 8(3):338-349, 1992.

Lamiraux, F. and Laumond, J.P. On the expected complexity of random path planning. In Proceedings of the IEEE International Conference on Robotics and Automation., 3014-3019, 1996.

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

Lozano-Pérez, T. Spatial planning: A configuration space approach. IEEE Transactions on Computers, 32(2):108-120, 1983.