International Journal of Aerospace and Mechanical Engineering 2:4 2008

A Real Time Collision Avoidance Algorithm for Mobile Robot based on Elastic Force
Kyung Hyun, Choi, Minh Ngoc, Nong, and M. Asif Ali, Rehmani

AbstractThis present paper proposes the modified Elastic Strip method for mobile robot to avoid obstacles with a real time system in an uncertain environment. The method deals with the problem of robot in driving from an initial position to a target position based on elastic force and potential field force. To avoid the obstacles, the robot has to modify the trajectory based on signal received from the sensor system in the sampling times. It was evident that with the combination of Modification Elastic strip and Pseudomedian filter to process the nonlinear data from sensor uncertainties in the data received from the sensor system can be reduced. The simulations and experiments of these methods were carried out. KeywordsCollision avoidance, Avoidance obstacle, Elastic Strip, Real time collision avoidance. I. INTRODUCTION ECENTLY, many studies on real time obstacle avoidance have been achieved. Certainty Grid [1] method was proposed by Moravec. Artificial Potential Field (APF)[2] method was proposed by Khatib and Virtual Force Field (VFF)[3] method was proposed by Borenstein have been applied for mobile robot to avoidance the obstacle. There methods were easy to apply and widely used. However, most of these methods never considered dynamic limitation, therefore, when a robot moves bottleneck in actuality, problem that does not escape is happened. The Elastic strips was proposed by Khatib[4,5]. It was proposing the trajectory of robot as an elastic material to avoid obstacles in real time. When approaching to the obstacles, the virtual force between objects was similar to the artificial potential field concept. However, this method revealed the stabilized navigation technology compared to the artificial potential field method due to the elastic force beside repulsive force whiles reaching to objects. Its application was easy in robots having multi-degree of freedoms which were effective though integrate motion plan and execution of robot at the same time. That command algorithm was optimized the real time obstacle avoidance in dynamic and uncertain
Manuscript received April 28, 2008. This work was supported in part of the project Human function life support intelligence robot technical development business 21st century frontier business, Republic of Korea. K. H. Choi is with Dept. of Mechatronics Engineering, School of Engineering, Cheju national University, Korea(phone: +82-64-754-3713, email: khchoi@cheju.ac.kr). M. N. Nong is with Dept. of Mechatronics Engineering, School of Engineering, Cheju national University, Korea (email: ngocnm@tnut.edu.vn). M. Asif Ali Rehmani is with Dept. of Mechatronics Engineering, School of Engineering, Cheju national University, Korea (email: asif@ cheju.ac.kr ).

environment. The Elastic strips based on only the nearest point with obstacle, therefore, in some cases, robot was not able to continue to reach the target and it has stuck on the way to the target point in a multi-obstacles environment. If the distance between two obstacles was not much, Elastic strips still found the way to reach the target but the trajectory of robot is not smooth. The algorithm for avoiding the collision proposed in the paper can make robot create a safety path to reach the target of using Modification Elastic Strips. This method based on the nearest points; one on the left and one on the right. Also, the application of Pseudomedian filter in data processing with the nonlinear data received from sensor system of robot was proposed. The simulation and experiments of these studies were carried out to illustrate the effectiveness of the proposed approach. II. ROBOT SYSTEM AND CONTROL ARCHITECTURE A. Robot System The Silvermate robot (Fig. 1) has a mobile and manipulators with seven degrees of freedom. The robot moves on two wheels. The sensor system of robot including sonar sensors, LRF, and IR are arranged surrounding the robot to detect information from environment. The mobile and manipulators appear in world coordination of a robot through speed kinematics.

Fig. 1The Silvermate robot system

B. Robot Control Architecture The Control architecture of the Silvermate robot[6] was proposed. It is consisted of three hierarchical structures. Deliberative layer takes charge of role that a robot changes given command to executable machine instruction. At

230

International Journal of Aerospace and Mechanical Engineering 2:4 2008

performs a plan; role of a robot is divided into navigation part and manipulation. The Sequencing layer processes information obtained from sensor to execute planning and creating the information, sequentially. Reactive layer executes commands delivered form higher level as lowest layer of control architecture. And when obstacle appeared in an environment, it coped with real time.

PMED =

1 2

[ Max ( Min(G ) ) + Min ( Max (G ) )] ; i = 1, 2, ...

(1)

The nonlinear data received from laser scanner of Silvermate robot included 360 values with the angular resolution of sensor is 0.5o. It was stored in the share memory of robot. In experiments, the size of windows filter was five (N=2) and three (N=1).
TABLE I PROPERTIES OF LASER SCANNER SYSTEM Parameter Values Distance max./10% reflectivity 80m/ 10m Scanning range Angular resolution Response time Data interface Laser protection class Dimensions (W x H x D) 0o...180 0.25/0.5/1 adjustable 53ms /26ms /13ms RS 232/RS 422 1 (eye-safe) 155 x 210 x 156 mm3

Fig. 2 Mobile-Arm Obstacle Avoidance Module

As shown in Fig. 2, the Reactive layer contains resources, actuator and obstacle avoidance module. Resources contain information of sensor system and encoder values. Master Mobile-Arm Obstacle Avoidance module includes detecting obstacle, establishing Obstacle avoidance algorithm, and determining velocity of module. This cooperates with local localization. Obstacle detection provided the distance and direction of obstacle when sensors detect obstacles. Local localization provided information about current position of a robot from the encoders system. Obstacle avoidance algorithm module decides obstacle avoidance and controls for Mobile. Furthermore, Determining Velocity of Mobile module decides the obstacle avoidance speed and angular velocity of robot. III. SENSOR DATA MANIPULATION The Elastic force included two components the internal force and the external force. To calculate this force, this algorithm based on only the nearest obstacle received from sensor system, therefore, the data of sensor should be reliable. In fact, the data includes the real data and the noises. The Pseudomedian filter one of the most common nonlinear techniques used in signal processing. It was proposed by Pratt, Cooper, and Kabir [10,11]. The Pseudomedian filter was designed to be a computationally efficient alternative to the median filter. This method is useful and popular in imaging processing to remove the salt and pepper noises. The Pseudomedian filter definition is described as calculation of discrete signal in a window width 2N+1. The output (PMED) of the Pseudomedian calculation is the average of the maximum of the minima and the minimum of the maxima of the N+1 sliding subsequences of length N+1 in the window.

Fig. 3The comparison of data with and without applying Pseudomedian filter

As shown in Fig. 3 the noises have been removed at the position of 186th, 264th, 266th, 272th and 292th. The application of Pseudomedian filter method suggests that the results measured using laser scanner with Pseudomedian filter are more reliable compared with the original ones. IV. COLLISION AVOIDANCE ALGORITHM A. Elastic Strips The Elastic strips[4,5], a method is proposed by Khatib supposes trajectory of robot as an elastic material and avoid obstacles in real time. The Elastic Force algorithm uses a virtual force field of repulsive force and elastic force. The internal force is a repulsion force occurs within robot and a target point. The external force is repulsion force occurs within robot and an obstacle, when approaching to obstacles. The internal force controls robot always keeps the trajectory to reach the target. At every position of robot, the internal force vector usually directs to the goal position. The internal contraction force is defined as Eq.2.

Fi int caused by the spring attached to joint

d i j 1 j +1 Fi = K c j 1 P j i1P ) ( ij P j i1 P ) (2) j ( i di + di th are robot poses, the force is decided by Here, j

231

International Journal of Aerospace and Mechanical Engineering 2:4 2008

difference between

j 1 i

P, ij P,
th

j +1 i

P and position vector; Kc is di

the contraction gain value for elasticity force; distance between j 1 and j posture and
th th

is the is the

Fi ( L, R ) = Vr
ext

di j

di j 1 distance between j + 1 and j posture; is the di j 1 + di j

K ( (d d ( P ) ) = d (P ) K d (P ) d
j r r i j i r j i r

d d d d

if

d r > d ( Pi )
j

if

d r d ( Pi

(6) )
(7)

scaling factor assures that the relative distance between adjacent configurations is maintained, as the strip is deformed. The external forces are caused by a repulsive potential associated with the obstacle. This force is the repulse force from obstacle to robot which helps robot does not hit to the obstacle.

Fi ext = Fi ext ( L) + Fi ext ( R)

To calculate the final external force, the nearest obstacle of both sides to calculate the main external force. Another external force can be call the auxiliary external force has calculated based on the other. Here, d r = d safe + d o with d safe = 1000(mm) is the safety distance and d o = 350( mm) is the radius of mobile robot. The Eq.(6) expresses the computation of the external force of Modification Elastic strips with the nearest obstacles on the left and right. The final external force can be calculated using Eq.(7) and the Elastic force has computed by Eq.(5). V. SIMULATIONS AND EXPERIMENTS

1 2 K (d d obs ,min ) if , d o > d obs Vexp ( p) = 2 r o (3) 0 otherwise

= can

Fi

ext

d = Vext ( p) = K r (d o d obs ,min ) d

(4)

The Fi

ext

expresses the external force which pushes out

outside to avoid obstacles. Here, d obs ,min is the shortest distance between robot and obstacles; Kr is the factor of external force; d = Pm P is the o vector between the nearest obstacle and the control point P. The Elastic force is including the internal force and external force. The vector of the force can be calculated by equation 5.

A. Simulations Results Applicability of the proposed obstacle avoidance method was verified through simulation. The parameters were giving in Table II.
Parameter Initial position of robot Target position of robot Kc Kr Safety distance Radius of robot TABLE II SIMULATION PARAMETERS Case 1 (0, 0) (3500,5000) 0.8 0.6 1000 (mm) 350 (mm) Case 2 (0,0) (4000,3500) 0.8 0.6 1000 (mm) 350 (mm)

Fi = Fi int + Fi ext ; Fi = [ f i , x , fi , y , fi , z ]T

(5)

B. Modification Elastic Strips The Elastic Strips method is very useful and adaptive with real time system [12]. However, it still has some problems which are mentioned as follows: The first problem is that robot cannot avoid the obstacle when the nearest point of obstacle on the direction of trajectory to target point. Here, the internal force vector and the external force of the mobile robot have the same direction so the final force controls robot to go straight to target that mean the robot can be hit an obstacle. The second problem suggests that when the space between two obstacle is not much robot can avoids there obstacles. However, the trajectory of robot is not smooth. The Modification of Elastic strips was proposed to solve these problems. The Elastic force in the Modification of Elastic strips includes two components (internal force, external force) similar in the original Elastic strips. In this case, the internal force vector also uses Eq.2 to calculate. However, the external force vector has been computed by two external force components, one on the left based on the nearest obstacles and the other on the right.

The results of simulation in case 1 were illustrated in Fig. 4.

Fig. 4 Simulation results in case 1

Here, the nearest point of obstacle on the direction from current point to target point, that mean the internal force and the external force have the same direction. The original elastic strips have applied to calculate the elastic force. However, in this case robot cannot avoid the obstacle. It has stuck and doesnt reach to target. But with the modification of elastic strips, robot can avoids the obstacle and reaches to the target. The trajectory is not smooth but it is acceptable.

232

International Journal of Aerospace and Mechanical Engineering 2:4 2008

The simulations also are verified in the environment with multi obstacles Fig. 5.

Fig. 5 Simulation results in case 2 In case 2, using both methods, robot can avoid the obstacles. However, with Elastic strips method, the trajectory of the robot is not smooth, the distance safety is infringed at some position. By contrast, the Modification Elastic strips has solved there problems. The trajectory of the robot using Modification Elastic Method is smoother. B. Experiment Results The result of experiment 1 is illustrated in Fig. 6. Here, from the initial position, robot moving to target, it detects the obstacle and then calculated new position of robots trajectory. The robot avoids the obstacle in real-time. The movement is smooth and safety with the speed by 4 cm/s.

robot system integration is suggested. The Pseudomedian filter is applicable to process the nonlinear data of robot sensor system. The noises have been effectively removed with using the Pseudomedian filter and were more reliable. The suggested Modification Elastic strips achieved the simulation of the static obstacles and successfully solved the problems of the original Elastic strips. In future, this method will be needed for real time avoidance of dynamic obstacle for Mobile Manipulator in addition to many-sidedness obstacle for better performance. Also, the Modification elastic strips should be continues study and applying for Manipulator with static obstacle, multi objects and moving objects in an environment. ACKNOWLEDGMENT This paper was supported by Human function life support intelligence robot technical development business 21st century frontier business. REFERENCES
P. Moravec, Certainty Grids for Mobile Robots, Proceedings of the NASA/JPL Space Telerobotics Workshop, Vol. 3, January 1987, pp. 307~312. [2] O. Khatib, Real-time obstacle avoidance for manipulators and mobile robot, The Int. Journal Robotics Research, Vol. 5, No. 1, 1986. [3] J.Borenstein and Y. Koren, "The vector field histogram-fast obstacle avoidance for mobile robot", IEEE Trans. Robotics Automate., Vol. 7, No. 3, June 1991, pp.278~288. [4] O. Khatib, "Motion coordination and reactive control of autonomous multi-manipulator system", Journal of Robotic Systems, Vol. 15, No. 4, 1996, pp. 300~319. [5] O. Khatib, "Robot In Human Environments: basic Autonomous Capabilities", The International journal of Robotics Research, Vol. 18, No. 7, 1999, pp. 684~696. [6] Kyung-Hyun Choi, Su-Jeong Cho, Byung-Kook Kim, "A Study on Behavior-based Hybrid Control For elderly Assistant Robot", The 1st Korean-Austrian Automation Day, May 2006, pp.153~161. [7] Borda, Robert P. and James D. Frost, Jr., "Error reduction in small sample averaging through the use of the median rather than the mean." Electroenceph Clin Neurophysiol, vol. 25, 1968, pp. 391-392. [8] Tukey, J. W. Exploratory Data Analysis. Reading, MA: AddisonWesley, 1971. 30. Rosenfeld, Azriel and Avinash C. Kak. Digital Picture Processing. Orlando: Academic, 1982. [9] Nodes, Thomas A. and Neal C. Gallagher, Jr., "The output distribution of median type filters." IEEE Trans Commun, v. COM-32 n, May 1984, pp. 532-541. 79 [10] Nodes, Thomas A. and Neal C. Gallagher, Jr., "Median filters: some modifications and their properties." IEEE Trans Acoust Speech Signal Process, v. ASSP-30 n., November 1982, pp. 739-746. [11] Pratt, William K., Ted J. Cooper, and Ihtisham Kabir, "Pseudomedian filter." Proc SPIE, v. 534, 1985, pp. 34-43. [12] Nak Yong Ko, Reid G. Simmons, and Dong Jin Seo, , Trajectory Modification Using Elastic Force for Collision Avoidance of a Mobile Manipulator, PRICAI Workshop., Aug 2006, pp. 1214~1224.
Kyung Hyun Choi is currently Professor in Dept. of Mechatronics Engineering, School of Engineering, Cheju National University, Korea. Minh Ngoc Nong is currently as Master student in Dept. of Mechatronics Engineering, School of Engineering, Cheju National University, Korea. M. Asif Ali Rehmani is currently as Master student in Dept. of Mechatronics Engineering, School of Engineering, Cheju National University, Korea.

[1]

Initial position

Avoiding the first obstacle

Avoiding the second obstacle Reaches to the target Fig. 6 Experiment results

VI. CONCLUSION The hybrid control for a Silvermate robot and real time collision avoidance algorithm in reactive layer architecture are suggested in this thesis. It is confirmed that the proposed algorithm is applicable to a Silvermate robot through collision avoidance simulations and experiments of mobile and whole system. In addition, the Pseudomedian filter is proposed to process the nonlinear data. There following conclusions were obtained. Hybrid control architecture can achieves the fast and stable real time avoidance motion by modularization of reactive layer in the motion of a robot. Also, the methodology for the

233