Simon Bennett (photo) and Chris CzarneckiSchool of Computing Sciences,
De Montfort University,
Electronic mail:Chris Czarnecki: firstname.lastname@example.org
Telephone: +44 (0)116 2551.551 Fax: +44 (0)116 541.891
Click here for audio statement. AIFF (143k)
School of Computing Sciences, De Montfort University
Leicester, LE1 9BH ,UK
An investigation into the applicability of fuzzy sets to the development of a control module that enables the on-line collision-free operation of a two robot workcell is presented. An approach is proposed based upon planning the collision-free paths off-line and utilising a real time monitor to then track the execution of these paths. The monitor activates a collision detection algorithm when any robot deviates from its preplanned path. The algorithm predicts possible collision situations. Prediction of a collision situation activates a fuzzy based reactive motion planner which determines the appropriate joint torques required to avoid the collision situation. The structure of the low level fuzzy control loop is presented and the associated fuzzy sets and rules for a two robot workcell are discussed. Simulation results are presented. These results show that the approach taken is feasible both from a conceptual point of view as well as satisfying the performance requirements required for real time implementation. The work forms the first stage of a programme of work which aims to utilise space filling curves to reduce the high dimensionality and complexity of multiple robot control system design.
In many robotic areas ranging from simple material handling to complex assembly, the application range can be extended by using multiple robots. Since multiple robots not only reduce the working space but also the manufacturing cycle, the control of multiple robots is an essential factor in factory automation. To accomplish tasks successfully by using multiple robot configurations, operating in a common workspace, a robot motion planning method that can have the robots move safely without collision is indispensable. Many approaches to multiple robot path planning have been reported in the literature. Whilst these provide satisfactory solutions in an ideal world, their performance in an industrial environment is often very different from that predicted. For example, the proposed methods rely on the complete sequence of robot moves to be known before being undertaken, then use computer simulation to preplan off-line each robot's moves. Each robot then follows the preassigned paths and completes the task assigned. However, numerous external factors may influence a robot's motion and cause it to deviate from the preplanned path. This in turn can cause a potential for collision either with other robots or with objects in the workplace.
This paper presents a new fuzzy logic based reactive collision avoidance method which works in real time to solve the multiple robot collision avoidance problem. The technique is essentially very simple. Each robot plans collision-free motions off-line. They then undertake these motions, whilst simultaneously a monitor tracks individual robot movements. A simple collision detection algorithm allows potential collisions to be detected and invokes the fuzzy reactive collision avoidance module whose task is to avoid the collision situation.
The format of the paper is as follows. A brief overview of work in the field of collision-free motion planning is presented. The system architecture proposed in this paper is then described which highlights how all the individual components interact to provide a robust multiple robot control scheme. The fuzzy based collision avoidance module is then introduced and its application to a dual robot workcell presented. Finally conclusions are drawn and a summary of potential applications provided.
2. Previous Work
Much of the early work undertaken in multi-robot systems was reported by Freund and Hoyer [1-3]. They developed a systematic design method, which uses a hierarchical structure for overall system control. Robot dynamics are included in their formulation and useful couplings between axes are utilised. The collision avoidance method uses a fictitious robot to define a collision-free trajectory. Lee and Lee , provided a solution to the two robot case by deriving a collision map which incorporates both path and trajectory information of the robots moving simultaneously and highlighting collision regions in the workspace. Collisions are then avoided by time scheduling one of the robots around the collision regions. This method relied on straight line motions and collision detection was restricted to the robot wrists.
Shin and Bien , present an approach where the concept of a virtual obstacle is used to describe potential collision between the links of two robots along designated paths. A notion of virtual co-ordination space is then used to visualise all the collision-free co-ordinations of two trajectories. From this the minimum-time collision-free trajectory pair for the two robots is sought. Chang et al , use minimum distance functions to describe the constraints that guarantee no collision between two robot arms. The collision-free motion planning problem is then formulated as a pointwise constrained non-linear minimisation problem, and solved by a conjugate gradient method with barrier functions.
Lee and Bien , propose a method based on a neural optimisation network. The positions or configurations of robots are taken as the variables of the neural circuit and the energy of the network is determined by combining various functions, in which one is to make each robot approach its goal and another helps each robot from colliding with other robots or obstacles. Park , presents a state space approach where an obstacle map is generated in N dimensional state space, where N is the total number of degrees of freedom of all robots. A local pathfinding method based on repelling pseudo forces is then used to automatically prevent the arms from colliding with fixed obstacles or with each other. Yuh , proposed a collision-free path finding algorithm for robots with prismatic joints and then used an adaptive control algorithm to follow the desired collision-free path. Each of these methods relies on the set of moves to be performed by the robots being known before the operation is performed.
Whilst this is the case for many automated systems, an increasing number of applications are being reported where the path to be travelled is not well defined, for example in tele-operated robots, Beaumont and Crowder , Shaffer and Herb , who proposed real-time approaches to detecting collisions. Beaumont and Crowder  modelled each robot via a combination of spheres, polyhedrons and cylinders to define an exclusion volume, whilst Shaffer and Herb  used a hierarchical data structure to track occupied zones in the three dimensional workspace. A similar approach was reported by Fujimara and Samet , who considered two dimensional objects with time representing the third dimension. Dodds , and Zalzala et al , reported collision-free on-line motion planning using a look ahead concept. Parallel processing is deemed necessary due to the vast computational complexities required to be completed in real-time. Example applications are presented for a two robot system. Chien et al.  developed algorithms for on-line generation of collision-free trajectories for Stamford type manipulators. Chu and ElMaraghy  proposed a real time multi-robot path planner based on a heuristic approach. The limitation of this work was that operation was essentially restricted to two dimensional workspaces. Seitz and Cipra  developed algorithms for real time collision avoidance for a three link planar manipulator and a single link arm having random motions.
Whilst all the above works provide solutions to the multiple robot motion planning problem, all suffer from some of the following shortcomings.
3. Control System Architecture
A hierarchical architecture is proposed here for the control of the multiple robot system and is shown in Figure 1. It is assumed that the motions to be undertaken are known beforehand and collision free motions are planned off-line. The method used in our experiments has been reported previously . A monitor module then continually tracks robot motions and detects any deviations from the preplanned paths. Any such deviation triggers the operation of a collision detection module which utilises a novel computationally efficient algorithm . The collision detection module is able to predict any forthcoming collisions and in doing so activates the fuzzy collision avoidance module. The fuzzy controller has the task of deriving the appropriate joint torques that will enable the predicted collision to be avoided. The control sequence for the monitor is shown in Figure 2.
4. Fuzzy Collision Avoidance
Once a potential collision is detected, the collision avoidance strategy must decide the appropriate joint torques to be applied so as to avoid the collision. The avoidance strategy presented here is a reactive control system that uses fuzzy logic. The architecture of the collision avoidance module is shown in Figure 3. Our approach is best described by means of an example. For this purpose we consider a two robot workcell, with the operating envelopes of the robots overlapping, as shown in Figure 4. The robots are identical and of a cylindrical configuration with d.c. motor drives. Our initial study applied the following restrictions, with the justification that if positive results are achieved we can expand the controller sophistication to increase its applicability.
The fuzzy logic controller is a two input single output system. The inputs are distance between the end effectors, measured between the points of nearest contact and relative speed of the axes. The output is the motor drive torque. Membership functions and their corresponding labels are shown in Figure 5. The aggregated output fuzzy set is derived using the min=max method, with this set being defuzzified using the centroid technique .
The fuzzy rule base for the system consists of a set of IF-THEN rules that map the fuzzy distance and speed variables into a resultant torque drive for the robot which has been deemed to alter its trajectory in an attempt to avoid collision. A total of 22 rules were derived for the example scenario. A typical rule in the collision avoidance system is shown below.
IF end_effector_distance is NEAR AND
velocity is POSITIVE_MEDIUM THEN
torque is NEGATIVE_MEDIUM
To test the performance of the algorithm five different scenarios were considered covering all ranges of the robot's operational workspace. The trajectory of one of the robots was altered to induce a collision situation. In each instance the trajectory of the slower moving robot was altered to successfully avoid the collision scenario. Examination of the end effector profiles revealed that to avoid the collision situation two strategies evolved depending on the likelihood of collision. The first results in a slowing down of one of the robots, allowing the second to pass freely, the second strategy incorporated a complete change in direction of rotation to avoid the situation.
This paper has presented the initial results of an investigation into the applicability of fuzzy sets to the development of a control module that enables the on-line collision-free operation of a two robot workcell. An approach has been proposed based upon planning the collision free paths off-line and utilising a real time monitor to then track the execution of these paths. The monitor activates a collision detection algorithm when any robot deviates from its preplanned path which predicts collision situations. Prediction of a collision situation activates a fuzzy based reactive motion planner which determines the appropriate joint torques required to avoid the collision situation. These results show that the approach taken is feasible both from a conceptual point of view as well as satisfying the performance requirements required for real-time implementation. Further experiments will be conducted introducing the extra degrees of freedom available. The ability of space filling curves to reduce the high dimensionality and complexity of the problem will also be addressed.
1. E. Freund and H. Hoyer, "Pathfinding in multi-robot systems : solutions and approaches",
in Proc. 1986 IEEE Int. Conf. Rob. and Aut., pp. 103-111
2. E. Freund and H. Hoyer, "On the on-line solution of the findpath problem in multi-robot systems ", in Proc. 3rd Int. Symp. Rob. Res., 1985, pp. 253-262
3. E. Freund, "On the design of multi-robot systems ", in Proc. 1984 IEEE Int. Conf. Rob. and
Aut. , pp. 477-490
4. B.H. Lee and C.S.G. Lee, " Collision free motion planning of two robots", IEEE Trans. Sys.
Man Cyb., vol. SMC-17, no. 1, pp 21-32
5. Y. Shin and Z. Bien, " Collision free trajectory planning for two robot arms ", Robotica, Vol. 7, pp. 205-212, 1989
6. C. Chang, M.J. Chung and Z. Bien, " Collision free motion planning for two articulate armsusing minimum distance functions" Robotica, vol. 8, pp. 137-144, 1990
7. J. Lee and Z. Bien, "Collision free trajectory control for multiple robots based on neural optimization network ", Robotica, vol. 8, pp. 185-194, 1990
8. W.T. Park, "State space representations for coordination of multiple manipulators", in Proc. 11th Int. Symp. Ind. Robots, pp. 397-405, 1984
9. J Yuh "Adaptive collision free path following control of two robots with prismatic joints". , inJnl. Manuf. Sys., Vol. 9, No. 1, pp. 35-43
10. R.G. Beaumont and R.M. Crowder, "Two armed robot systems- a review of current theory and the development of algorithms for real time collision avoidance " in IEE Colloquium, vol. 1989/127, pp. 1/1-1/4
11. C.A. Shaffer and G.M. Herb, "A real time robot arm collision avoidance system", in IEEE
Trans. Rob. and Aut.Vol. RA-8, no. 2, pp.149-160
12. K. Fujimuru and H. Samet, " A hierarchical strategy for path planning amongst moving obstacles" , in IEEE Trans. Rob. and Aut. Vol. RA-5, no. 1, pp61-69
13. G. Dodds, "Robotic collision control", in IEE Colloquium, vol. 1989/127, pp. 2/1-2/4
14. A.M.S. Zalzala, G.I. Dodds and G.W. Irwin, "Advanced multi-robotic control on a transputernetwork", in Proc. IEE Systems Eng. for Real Time Sys., 1993, pp. 31-36
15. Y.P. Chien, A.J. Koivo and B.H. Lee, " On-line generation of collision free trajectories for
multiple robots", in Proc. 1988 IEEE Int. Conf. Aut. and Rob., pp. 209-214
16. H. Chu and H.A. ElMaraghy, "real-time multi-robot path planner based on a heuristic approach ", in Proc. 1992 IEEE Int. Conf. Aut. and Rob., pp 475-480
17. B. D. Seitz and R.J. Cipra, " Real time collision avoidance of a planar manipulator with an
interfering single link arm", in Proc. 1992 IEEE Int. Conf. Aut. and Rob., pp 1494-1499
18. C.A. Czarnecki, "Collision free motion planning for two robots operating in a common workspace", Proc. IEE Control 94, pp. 1006-1011
19. C.A.Czarnecki,"A knowledge based real time collision avoidance method for multi-robot systems", in Proc. IEE EURISCON'94, pp. 470-479
20. E. Cox,"The fuzzy systems handbook", AP professional, 1994.
For more SYNDICATE SPEAKERS
For other SYNDICATES