A PROJECT REPORT

on

CO-ORDINATED OBSTACLE AVOIDANCE SYSTEM OF S-BOTS

Submitted in partial fulfillment for the award of the degree
of

BACHELOR OF TECHNOLOGY
in

ELECTRICAL AND ELECTRONICS ENGINEERING

by

ATUL KUMAR JHA [10507039] BAIBHAB GURU [10507040] BINOY ACHARYA [10507044]
Under the guidance of

Mr. A. RATHINAM, M.E, (Ph.D)

(Asst. Professor[S.G], Department of Electrical and Electronics Engineering)

FACULTY OF ENGINEERING AND TECHNOLOGY SRM Nagar, Kattankulathur 603 203 Kancheepuram Dist MAY 2011

BONAFIDE CERTIFICATE

Certified that this project report titled COORDINATED OBSTACLE AVOIDANCE SYSTEM OF S-BOTS is the bonafide work of ATUL KUMAR JHA (Reg. No.: 10507039), BAIBHAB GURU (Reg. No.:10507040) and BINOY ACHARYA (Reg. No.:10507044) who carried out the project work under my supervision. Certified further, that to the best of my knowledge the work reported herein does not form part of any other project report or dissertation on the basis of which a degree or award was conferred on an earlier occasion on this or any other candidate.

Signature of the Guide Mr. A. Rathinam (Asst. Prof.)

Dept. of Electrical & Electronics Engineering

Signature of Head of the Department Dr. S.S. Dash

Dept. of Electrical & Electronics Engineering

Signature of the Internal Examiner

Signature of the External Examiner

Date:

ACKNOWLEDGEMENT
We would like to express our gratitude to our respected Chancellor DR.T.R.PACHAMUTHU, Vice Chancellor DR.P.SATHYNARAYANAN and management of our college for their encouragement towards our growth and activities. We would like to express our gratitude to our respected Director (E&T), DR.C.MUTHAMIZHEELVAN, Ph.D for their encouragement towards our growth and activities. I wish to express sincere thanks and gratitude to our Head of the Department and Professor, DR.S.S.DASH, M.E. Ph.D, MISTE, MIE for his commendable support and encouragement towards the completion of the project with perfection, who has been a guiding force and constant source of inspiration to us. We sincerely thank to our guide, MR.A.RATHINAM, Assistant

Professor[S.G] for his encouraging attitude, fullest co-operation, guidance and sustained interest in completing the project work successfully. Our project coordinators MRS.D.SUCHITRA, AP/EEE &

MRS.N.KALAIARASI, AP/EEE for the unending support and valuable advice that helped us to finish the project. We owe our deep sense of gratitude to our friends, SHALIL SHANKAR, AAKASH SOLANKI, PRATIK KUMAR for his time, patience, guidance and having extended their fullest support in completing the project work. And we extend thank to the School of Electrical and Electronics Engineering faculty and supporting staff to their good support for providing computer and software necessary complete the project. Last but not the least, we thank our cheerful Parent & Friends who chipped in with timely advices, constant appreciation and criticism and also for giving a great company.

iii

ABSTRACT
Swarm bots have a quality of organized behavior and mutual information sharing among them. The problem in the design of the control system of S-bots deals with their proper and efficient coordination through defining individual rules. It is possible by the automatic synthesis of the individual controller through evolutionary or learning process. One or Two S-bots will be trained to produce coordinated behavior. Both S-bots will be using Particle Swarm Optimization (PSO) technique for their desired operation. The experiment will consist of one or two S-bots maneuvering a path comprising of obstacles. The software implementation of this experiment will be done by using MATLAB (i.e, coding are to be written in MATLAB by deducing equations generated from PSO algorithm and multi objective optimization algorithms). Simulation of the experiment will be done taking three cases into consideration namely: Case 1: One robot with one obstacle Case 2: One robot with two obstacle Case 3: One robot with three obstacle Case 4: Two robot with One obstacle

.
iv

TABLE OF CONTENTS
CHAPTER TITLE PAGE NO.

ACKNOWLEDGEMENT ABSTRACT LIST OF TABLES LIST OF FIGURES LIST OF SYMBOLS

iii iv vii viii ix

INTRODUCTION 1.1 1.2 1.3 Objective Organization of project report Project Proposal

1 1 2 2

SWARM BOTS 2.1 2.2 2.3 Introduction Particle Swarm Optimisation Technique The Etiology Of Particle Swarm Optimisation 2.3.1 2.3.2 2.3.3 2.3.4 2.3.5 Basic Idea Working Particle Swarm PSO Modeling Particle Swarm Dynamics

3 3 3 3 4 4 4 4 4

FORCE FIELD METHOD 3.1 3.2 3.3 3.4 3.5 Introduction Construction Of Force Field Repulsive Force Attractive Force Algorithm Of Force Field Method

7 7 11 13 13 14

CHAPTER

TITLE

PAGE NO.

4.

MULTI- OBJECTIVE PARTICLE SWARM OPTIMIZATION 4.1 4.2 4.3 Introduction MOPSO Multi Objective Optimization

15 15 15 17

IMPLIMENTATION OF FORCE FIELD METHOD AND PSO IN S-BOTS 5.1 5.2 5.3 5.4 Introduction Coding In Force Field Method Linking Of F Method With PSO Linking Of F Method With MOPSO
2 2

19 19 19 20 20

RESULTS AND DISCUSSION

6.1

21 21 31

Amigo Robot Specification

CONCLUSIONS

vi

LIST OF TABLES
TABLE NAME PAGE NO.

3.1 6.1 6.2 6.3

Parameters of Force Field Method Force Field Method Linked With PSO Algorithm Force Field Method for Two Robot Multi Objective Particle Swarm Optimisation

11 29 29 30

vii

LIST OF FIGURES
FIGURE 2.1 2.2 3.1 3.2 3.3 4.1 4.2 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 6.9 TITLE Particles in a 2D Search Space Flow Chart of Basic PSO Global and Local Reference Frame Illustration of a Robots Parameter Attractive Force Pareto Optimal Front Optimal Front Generated By MOPSO A Amigo Robot Input: One Robot and One Obstacle Output: One Robot and One Obstacle Input: One Robot and Two Obstacle Output: One Robot and Two Obstacle Input: One Robot and Three Obstacle Output: One Robot and Three Obstacle Input: Two Robot and One Obstacle Output: Two Robot and One Obstacle PAGE NO. 5 6 10 12 14 16 16 21 21 22 23 24 25 26 27 28

viii

LIST OF SYMBOLS USED

Xr Yr
r

= = = = = = = = = = = =

Position Of The Bot in X-Axis Position Of The Bot in X-Axis Direction Of Motion Of The Robot Absolute value of a robots speed Maximum absolute value of a robots speed A Constant A Constant Magnitude Of Repulsive Force Magnitude Of Attractive Force Environmental Factor Task Priority Number Of Time steps

Vr Vmax
0

K P Q C Tp t

ix

1. INTRODUCTION
1.1 OBJECTIVE Swarm Robotics is a new approach to the co ordination of Multi robot systems which consist of large numbers of simple physical robots. It is supposed that a desired collective behavior emerge from the interactions between the robots and the interaction of robots with the environment. This approach emerged on the field of artificial swarm intelligence. Swarm bots have a quality of organized behavior and mutual information sharing among them.. But the problem in the design of the control system of S-bots deals with their proper and efficient coordination through defining individual rules. It is possible by the automatic synthesis of the individual controller through evolutionary or learning process. The aim is to cross an environment full of obstacles with the help of one or more than one swarm bot [1] .The algorithms used in our project is the multi objective particle swarm optimization(MOPSO) and technique used to calculate the shortest distance is F2 (Force Field) method. In force field method shortest distance is calculated using random value of certain parameters like K, P, Q, C and R0. By including one more objective of avoiding obstacles our problem becomes multi objective. In MOPSO algorithm, for distance calculation function taken is f1 (xi) and for obstacle avoidance is f2(xi). f1(xi) = FF(xi), I = 1,2,.. (1.1)

[ FF(xi) is resultant path length obtained using parameters xi] f2 (xi) = 1/Dn,xi , [i = 1,2.] [ Dn : shortest distance from the bot to obstacles ] (1.2)

Multi-objective particle swarm optimization algorithm will calculate the suitable values of parameters like K, P, Q, C and R0.

1.2 ORGANISATION OF THE PROJECT REPORT The project talks about swarm bots manoeuvrings. It is started with the introduction about the objective of our project in the first chapter. The second

chapter deals with PSO algorithm. Third chapter deals with the FORCE FIELD METHOD for calculation of distance. The fourth chapter deals with the MOPSO algorithm. Fifth chapter deals with the linking of PSO algorithm with force field method for giving a set of best values of parameters used in force field method to calculate the distance
1.3 PROJECT PROPOSAL

This project report presents an effective shortest distance calculation method that has to be covered by one or two swarm bots without having any collision with obstacles present in the environment. It also gives an idea of MOPSO(multi objective particle swarm )algorithm that has been used for finding best values of parameters required in field method. The various cases are run by writing codes in MATLAB SIMULINK software (V.7.6.0R2008a). The MOPSO codes are also written in the same for optimization purpose. These two programs are been linked to full fill our objective of incorporating MOPSO with FORCE FIELD METHOD for distance calculation that will give desired outputs.

2. SWARM BOTS
2.1 INTRODUCTION Swarm robotics is a new approach to the coordination of multi robot systems which consist of large numbers of mostly simple physical robots. It is supposed that a desired collective behavior emerges from the interactions of robots with the environment. This approach emerged on the field of artificial swarm intelligence, as well as the biological studies of insects, ants and other fields in nature, where swarm behaviour occurs [3]. This is a differential wheeled robot (with additional tracks) developed and targeted to swarm robotics, a field of artificial intelligence. Swarm bots have an intelligence of their own. 2.2 PARTICLE SWARM OPTIMISATION TECHNIQUE Particle swarm optimisation is based on population based optimisation Technique. It is developed by Dr.Eberheart and Dr.kenedy in 1995. Particle swarm optimization has roots in two main component methodologies. Perhaps more obvious are its ties to artificial life (A-life) in general, and to bird flocking, fish schooling, and swarming theory in particular. It is also related, however, to evolutionary computation, and has ties to both genetic algorithms and evolutionary programming. Particle swarm optimization developed comprises a very simple concept, and paradigms that can be implemented in a few lines of computer code. It requires only primitive mathematical operators, and is computationally inexpensive in terms of both memory requirements and speed. 2.3 THE ETIOLOGY OF PARTICLE SWARM OPTIMISATION The particle swarm optimizer is probably kcst presented by explaining its conceptual development. Agents were thought of as collision-proof birds, and the original intent was to graphically simulate the graceful but unpredictable choreography of a bird flock.

2.3.1 Basic Idea One should always keep Track of global best (gbest) and particle best (pbest) solutions in PSO.

2.3.2 Working 1. Take a function f(x). 2. Find x that minimizes f(x).

2.3.3 Particle Swarm Optimisation 1. Start-Random set of solution vectors. 2. Experiment-Include randomness in the choice of new states. 3. Encode information about good solutions. 4. Use the experience information to initiate search in a new regions.

2.3.4 PSO Modeling Each solution vector is modelled as (i) (ii) The coordinates of a particle in a swarm flying through search space. All the particles have a non-zero velocity and thus never stop flying and are always sampling new regions. Each particle remembers where the global best and where the local best are. The search is guided by collective consciousness of the swarm.

2.3.5 Particle Swarm Dynamics

Xi(k+1)=Xi(k)+Vi (k) Vi (k+1)=w*V(k)+r(0,a1)*(Xbest (k)-X(k))+r(0,a2)(Xgroupbest(k)-x(k))

(2.1)

(2.2)

Figure 2.1: Particles in a 2D search space Particle swarm optimization is an extremely wimple algorithm that seems to be effective for optimizing a wide range of functions. Social optimization occurs in the time frame of ordinary experience - in fact, it is ordinary experience. In addition to its ties with A-life, particle swarm optimization has obvious ties with evolutionary computation. Conceptually, it seems to lie somewhere between genetic algorithms and evolutionary programming. It is highly dependent on stochastic processes, like evolutionary programming. The adjustment toward pbest and gbest by the particle swarm optimizer is conceptually similar to the crossover operation utilized by genetic algorithms. It uses the concept of fitness, as do all evolutionary computation paradigms.

Figure 2.2: Flow Chart Of Basic PSO

3. FORCE FIELD METHOD

3.1 INTRODUCTION In the F2 method, a virtual force field is generated for each robot in its vicinity and is continuously changing based on its status, including its size, travelling speed, priority with respect to other robots and environment factors. The force field varies with this robots status when it travels in an environment. If there are obstacles or other robots in the area of a robots force field, this robot will be acted on by virtual repulsive forces from them and be repelled. A robot with larger volume, travelling at higher speed or with higher priority, will have priority in collision avoidance[1]. The interaction of a robots force field with its environment provides a natural way for real-time motion planning and collision avoidance. In the F2 method, a robot is attracted by a force from a selected target point. This target point can be its final destination or a temporary subgoal which is generated based on local sensor data or by other external global planners. This research focuses on the theoretical developments and experimental studies of the F2 method on mobile robots in 2-dimensional (2D) environments, but it is also applicable to manipulator motion planning problems in 3-dimensional (3D) environments. The concept of F2 resembles the Potential Field to some extent. Both concepts use repulsive potential/force fields to avoid collision with obstacles and an attractive potential/force to guide a robot to its target[1]. However the differences between the F2 and the Potential Field are distinct. A potential field is generated based on environment information. That is to say, the potential value of a point in potential field is determined by its location in the environment. This potential field remains unchanged if the environment does not change. In the F2 method, the repulsive force field of a robot covers the robot body, instead of being around an obstacle, as those of potential field-based approaches. This force field is continuously changing during the robots movement based on its own status. Collision avoidance is achieved by the interaction of a robots repulsive force field with its environment. Compared with currently existing approaches, the F2 method has the following desirable features:
7

In the F2 method, a robots physical characteristics, such as size and geometry, are used in the construction of its force field. Its dynamic and kinematics characteristics, such as constraints on linear velocity and angular velocity, are taken into consideration when determining a robots motion. The F2 method is a generic approach for any kind of mobile robot and suitable for real applications. The F2 method[2] is suitable for applications in partially known or dynamically changing environments. A robot using the F2 method needs to know its location and destination in its movement but a precise map is not essential. If there are environmental changes or moving obstacles in the work space, a robot reacts immediately based on information obtained from inter-robot communication and sensor data. No preplanning and replanning is needed.  The F2 method is suitable for motion planning and collaboration of multiple robots working in a decentralized manner. A robot plans its path and motion independently according to the surrounding environment and its own status, so the F2 method will not suffer from the exponentially increasing computation burden, as do some centralized approaches, and can be used online. Another advantage of the F2 method is that the task priority is taken into account in the construction of the force field.  In the F2 method, a robot only reacts to obstacles which are in the coverage of its own force field. A robot using the F2 method[2] does not therefore need to search the whole work space as many other methods do, which significantly increases the efficiency of motion planning and coordination. In the F2 method, the coverage of a robots force field is determined by

parameters including the robots size, travelling speed, and priority with respect to other robots. If there are obstacles or other robots in the area of a robots force field, this robot will be acted on by virtual repulsive forces from other robots/obstacles. A robot only reacts to obstacles that are in the coverage of its own force field and does not need to search the whole work space as many other methods require, which significantly increases the efficiency of motion planning and coordination. In the F2 method, a robots physical characteristics, such as size and geometry, are used in the construction of its force field. Its dynamic and kinematic characteristics, such
8

as linear velocity and angular velocity, are taken into consideration when determining a robots motion. These make the F2 method suitable for real applications. In the F2 method, a robot needs to know its location and destination in the environment but a precise map is not essential. The F2 method is suitable for use in multirobot cases. A robot using the F2 method works in a decentralized manner, that is, a robot plans its path and motion independently according to the surrounding environment and its own status, so the F2 method will not suffer from an exponentially increasing computation burden as some centralized approaches do [2]. Another advantage of the F2 method is that the task priority is taken into account in the construction of the force field. A robot with higher task priority will have priority in collision avoidance. The concept of the proposed force field (F2) method is described in detail. In the F2 method, a virtual repulsive force field is created and centered on the robot. This force field varies with the robots status during its movement, including the robots speed, task priority, environmental factors and the robot body dimension. If any obstacle exists in the coverage area of this force field, the robot will act on a repulsive force from the obstacle. If a robots force field overlaps with another robots force field, both robots will suffer repulsive forces from each other. The interactions among a robots force field with obstacles and other robots, i.e., the repulsive forces, combining with the attractive force from the goal, are utilized to determine a robots motion in the F2 method. In this research, a robot is modeled as a rigid body moving on a horizontal plane. The dimensionality of the robot in a working space is three, two for position in the plane and one for orientation along the perpendicular axis, which is orthogonal to the plane. Other factors which may affect the robots movement, such as wheel slippages and additional degrees of freedom due to a robots internal structure, are ignored. Two reference frames are defined: a global reference frame O(X,Y) and a local reference frame o(x, y) attached to a robots body (Figure 3.1). The axes X and Y define an inertial frame of reference on the plane as a global reference frame from an origin O(X, Y). To specify the position of the robot, choose a point on the robot as its position reference point. o(x, y)defines two axes relative to on the robot body and is thus the robots local reference frame. Note that x axis is set to be along this robots moving
9

direction. The position of in the global reference frame is specified by (Xr, Yr) and the angular difference between the global and local reference frames is given by r. The pose of a robot in the global reference frame is described as a vector with three elements.

r = [Xr, Yr , r]T

( 3.1 )

Figure 3.1 Global reference frame and local reference frame A robot is assigned a task such that it needs to travel from its current or start location to a goal location at rg = (Xg , Yg) . The robot then moves, under an appropriate control, towards the goal in a number of time steps t. The equation that describes the robot motion from time interval s to s+1 can be expressed as a function of the current location, orientation and control: ri,s+1 = h(ri,s , ui,s) where ui,s = (vi,s ,
i,s)

(3.2) is the control issued to the mobile robot i, in which vi,s is

i,s

the translational velocity and

is its angular velocity.[1] The motion equation of robot i

at time interval s+1 is described by: xi,s+1 = xi,s + vi,scos( yi,s+1 = yi,s + vi,ssin(
i,s+1 = i,s + i,s t i,s) i,s)

t t

(3.3) (3.4) (3.5)

10

The control commands, vi,s and

i,s

are determined such that during the travel, the

robot is free of collisions onto obstacles or other robots. The force field method is applied to generate the control commands based on the forces exerted on the robot, which is the function of attractive force from the goal and repulsive force from obstacles and other robots. 3.2 CONSTRUCTION OF FORCE FIELD In the F2 method, a force field is defined as a virtual field of repulsive force in the vicinity of a robot when it travels in a working space. The magnitude and orientation of a force field are determined by, and vary with, the robots status. This virtual repulsive force increases when the distance to the robot decreases. Note that the construction of the force field described below is in the global reference frame[1]. =
0 r

(3.6) (3.7) (3.8) (3.9) Table 3.1 Parameters of Force Field Method Parameters Descriptions radius of a robot absolute value of a robots speed maximum absolute value of a robots speed a robot's task priority angle between a robots moving direction and the X coordinate

Er = vr/(vmax * C) Dmax = k*Er *Rr *Tp/(1-Er cos( )) Dmin =

0

* Dmax

Rr vr vmax Tp
r

11

Figure 3.2 Illustration of a robots parameters For any point P(Xp, Yp)in the robots local reference frame, denotes the angle of
r

this point in the robots coordinates (Figure 3.2.1), which can be determined from

and

the angle of this point in the global coordinates ( 0), as in the equation. c is a positive number (c >1) which represents the environmental influence to the force field. Er is a positive decimal fraction with 0 Er 1. k is a positive coefficient which determines the size of the area to be covered by the force field. Dmax is the maximum action distance of a robots force field and Dmin is the distance at which this robot has maximum repulsive force. Dmax shows how far this robot can affect others in its vicinity. Dmin provides a safe distance for the robot to prevent other objects from moving into this area. fractional number with 0 <
0 0

is a positive

< 1 that defines how close the robot can be to obstacles. Tp

represents the priority of a robot, which is especially useful for multi-robot coordination. Note that for single robot case, Tp is set to be 1. The above equation defines which the influence area of the force field is. It indicates that the coverage of a force field (Dmax) in the F2 method is determined by a robots size (Rr), its travelling speed (vr) and maximum speed (vmax), a positive multiplier (k), an environment factor (c ) and priority (Tp) . For a robot with larger volume or travelling at higher speed, its force field will cover a larger area. When a robot travels in an obstacle-cluttered environment, the environment factor (c) can be set larger. Then the coverage of its force field will become smaller and allow the robot to pass through narrow passages.

12

3.3 REPULSIVE FORCE

The magnitude of a repulsive force to be generated by a robots force field is defined by:

(3.10) where D is the shortest distance from point P(Xp, Yp ) in the 2D space to the perimeter of the robot. P is a positive constant scalar which determines the magnitude of the repulsive force. When D changes from to Dmin to Dmax, the magnitude of the repulsive force changes from P to 0 gradually. Furthermore, Fmax is the maximum repulsive force which will cause the maximum deceleration on the robot. With Fmax >> P, P and Fmax should be selected on the basis of the robots characteristics, above equations shows that the magnitude of repulsive force varies with the distance to the robot, robot speed, robot size, task priority and several scaling parameters. The force starts from the robots centre to the given point, whose direction in the global reference frame is given by

(3.11) 3.4 ATTRACTIVE FORCE When a robot is undertaking a particular task, for example, travelling from start point (Xs, Ys) to goal point (Xg, Yg), a virtual attractive force which attracts this robot from the start point to the goal point is generated (Figure 3.3.1). The attractive force, denoted by Fatt_g, directs to the goal point from the centre of the robot and its magnitude can be assumed to be a constant. It drives a robot to its destination (Xg, Yg). The magnitude of this attractive force is given by:
13

(3.12) where Q is a positive constant scalar which determines the magnitude of the attractive force. The attractive force directs the robot to the goal point from the centre of the robot and can be assumed to be a constant. Furthermore, the orientation of the attractive force in the global reference frame is given by:

(3.13)

Figure 3.3: Attractive force 3.5 ALGORITHM OF FORCE FIELD METHOD 1. Enter the coordinates of source, obstacle and the destination. 2. Calculate the direction of motion of robot. 3. Calculate various parameters like Dmax, Dmin, Frep, Fatt , v from the given parameters like K, P, Q, C,
o.

4. Distance calculated from the formula D = iteration * t * v. 5. Now compare the distance obtained with the straight line distance calculated. 6. Stop.

14

4. MULTI- OBJECTIVE PARTICLE SWARM OPTIMIZATION

4.1 INTRODUCTION One of the successful applications of PSO to MOO problems, named MultiObjective PSO (MOPSO) PSO is a population-based approach using a set of candidate solutions, called particles, which move within the search space. The trajectory followed by each particle is guided by its own experience as well as by its interaction with other particles. Specific methods of adjusting the trajectory are motivated by the observations in birds, fishes, or other organisms that move in swarms. Multi-objective optimization (MOO) is an important field to apply swarm intelligence metaheuristics because there is not only one solution for MOO in general[4].

4.2 MOPSO The solution of a MOO problem is generally referred as a non-dominated solution, which is different from the optimal solution of single-objective optimization problem. A solution is said to be non-dominated over another only if it has superior, at least no inferior, performance in all objectives[4]. Hence, non-dominance means that the improvement of one objective could only be achieved at the expense of other objectives. This concept always gives not a single Solution, but rather a set of solutions called the non-dominated set or non-dominated archive. The goal of generating the non-dominated front is itself multi-objective. That is, designing a Pareto optimizer usually has two major goals how to converge to the true Pareto-optimal front while achieving a welldistributed set of solutions.

15

Figure 4.1: Pareto Optimal Front

Figure 4.2: Optimal Front generated by MOPSO

16

4.3 MULTI OBJECTIVE OPTIMIZATION Without loss of generality, a MOO problem (also known as a vector optimization problem)[5] is the problem of simultaneously minimizing K objectives f(k), k =1,2,L,K , of a vector xr in the feasible region . That is,

(4.1) Where = [X1, X2,.,XD]T is a D-dimensional vector and

Are linear or non-linear function.

In PSO, a population is initialized with random solutions, called particles[5]. All particles have fitness values that are evaluated by the function to be optimized. Each particle flies through the problem space with a velocity, which is constantly updated by the particles own experience and the experience of the particles neighbors, to search for optima iterations by iterations. In every iteration, the velocity of each particle is updated by two best values. The first one is the best solution it has achieved so far. This value is called pbest. Another best value tracked by the optimizer is the best value obtained so far by the neighborhood of each particle. This best value is a local best and is called lbest[6]. If the neighborhood is defined as the whole population, each particle will move towards its best previous position and towards the best position ever been in the whole swarm, this version is called gbest model. The velocity and position of each particle are updated by the following equations.

Vd i(new)

= w.Vdi(odd) + C1.RAND(Pdi-xdi) + C2.RAND(gd-xdi)

(4.2) (4.3)

Xdi(new) = xdi(old) + Vdi(new) where, Vdi(old) is the old velocity of the particle i along the dimension d
17

Vdi(new) is the new velocity of the particle i along the dimension d W is the inertia weight which is usually in between 0.8 to 1.2 C1 and C2 are the learning factor (or accelerating coefficients) usually between 1 and 4 Xdi is the current position of the particle i along the dimension d Pdi is the personal best solution of particle i along the dimension d Gd is the global best solution the whole population ever been along the dimension d, and RAND is a random number between 0 and 1

18

5. IMPLIMENTATION OF FORCE FIELD METHOD AND PSO IN S-BOTS

5.1 INTRODUCTION This chapter investigates the optimization of parameters in the F2 method. It states that that the parameter setting in the F2 method has a significant effect on the performance of the robot. For this reason, this chapter proposes a PSO-tuned F2 method for single objective parameter optimization problems. A multi-objective optimization method is again developed, and proves to be capable of solving multi objective

parameter optimization problems efficiently.

5.2 CODING IN FORCE FIELD METHOD In this method for constructing a kind of safe zone or Free Zone to protect a robot from possible collisions with obstacles and other robots. It proposes a repulsive field which is strictly localized in a robots vicinity to protect it from collision, in which the repulsive field is generated as the gradient flow of a spherically symmetric potential field. A theory of collision avoidance, in which a Safe Zone is defined for each obstacle, is taken into account here. When a robot enters this safe zone, it will suffer from virtual repulsive force, and as it increases and its maximum limit is reached as the robot moves away from the obstacle. This virtual force will push the bot out of the safe zone. Again there comes a attractive force into account that attracts the robot towards the goal. The repulsive force may vary from obstacle to obstacle but the attractive force remains same as the goal is fixed. The main aim here is to calculate repulsive force from the obstacle and attractive force towards the goal. This can be calculated using elements like Dmax, Dmin, P, Q and several other parameters. Using the repulsive and attractive force values the velocity and angle of motion of the robot is determined .Using those two values, the robots next position is determined. By putting it in a loop the robot reaches from its source to destination by avoiding obstacle. The distance travelled is obtained by multiplying number of iteration with the velocity in each step and the time taken for each iteration.
19

By comparing the shortest distance with the distance obtained one can prove the efficiency of F2 method, as the main objective here is that, the robot should cover the shortest distance by avoiding the obstacles. 5.3 LINKING OF F2 METHOD WITH PSO The Parameters used in F2 method are mainly k, P, Q ,C ,R0 .These parameters have a certain range. By varying the ranges from its lower limit to upper limit, the set of distance travelled by the robot is calculated. PSO algorithm is linked with the F2 Method. It performs optimisation to give a best set of values of the above parameters, those can be able to find the optimum distance value travelled by the bot. 5.4 LINKING OF F2 METHOD WITH MOPSO

In the above case, while linking the F2 method with PSO, only one objective function has been taken into account i.e F1(xi) =shortest distance travelled by the robot. To make problem multi objective, another function taken into account. F2(xi) = 1/ Dn,xi, i=1,2, ( Dn.= shortest distance from robot to obstacle) (5.2) (5.3) (5.1)

The total fitness is given as :Fitness = F1(xi) + F2(xi) where F1(xi) = FF(xi) , i=1,2, parameters xi) F2(xi) = 1/ Dn,xi, i=1,2, ( Dn.= shortest distance from robot to obstacle)

( FF(xi)= resultant path length obtained using

Multi-Objective Particle Swarm Optimization (MOPSO) will optimize the total fitness thereby giving a set of best values of parameters K, P, Q, C and Ro. These set of best values of parameters will calculate the shortest distance travelled by the robot and the danger index obtained from the second function. The results obtained are been tabulated in the next chapter.

20

6. RESULTS
6.1 AMIGO ROBOT SPECIFICATION Amigo robots are used in the simulation studies. The parameters of an Amigo robot (Figure 6.1) are: the dimension is 33cm by 28cm and the body clearance is 3cm . The weight of this robot is 3.6kg . The maximum speed of an Amigo robot is 1m/s and the maximum angular speed is 300 degrees per second.

Figure 6.1: Amigo Robot

Figure 6.2: Input: One Robot and One Obstacle

21

INFERENCE: In this case initial point is denoted by (Xr, Yr) which is taken as (1, 2), (Xp, Yp) denotes the point on the periphery of the obstacle which is taken as (5, 7.5), (Xg, Yg) denotes the destination point which is taken as (9.5, 9).

Figure 6.3: Output: One Robot and One Obstacle INFERENCE: Number of iteration tell us about the step required by the bot to reach the destination point i.e., 5468.So, after this(5468) number of iteration bot reached the point (Xr, Yr) i.e., (9.35, 8.86) hence the goal is achieved. Sld denotes the shortest distance which is a straight line in any case and Distance denotes the distance travelled by the bot avoiding the obstacle.

22

Figure 6.4: Input: One robot and two obstacles

23

INFERENCE: In this case initial point is denoted by (Xr, Yr) which is taken as (1, 2), (Xp1,Yp1), (Xp2,Yp2) denotes the point on the periphery of the obstacle which is taken as (3,6), (7,4), (Xg, Yg) denotes the destination point which is taken as (9.5, 9).

Figure 6.5: Output: One robot and two obstacles INFERENCE: Number of iteration tell us about the step required by the bot to reach the destination point i.e., 5468.So, after this (5468) number of iteration bot reached the point (Xr, Yr) i.e.,(9.35, 8.86) hence the goal is achieved. Sld denotes the shortest distance which is a straight line in any case and Distance denotes the distance travelled by the bot avoiding the obstacle.

24

Figure 6.6: Input: One robot and three obstacles

25

INFERENCE: In this case initial point is denoted by (Xr, Yr) which is taken as (1, 2), (Xp1,Yp1), (Xp2, Yp2), (Xp3, Yp3) denotes the point on the periphery of the obstacles which is taken as (3,6), (7, 4), (5, 7.5), (Xg, Yg) denotes the destination point which is taken as (9.5, 9)

Figure 6.7: Output: One robot and three obstacles INFERENCE: Number of iteration tell us about the step required by the bot to reach the destination point i.e., 4933.So, after this(4933) number of iteration bot reached the point (Xr, Yr) i.e.,(8.85, 7.86) hence the goal is achieved. Sld denotes the shortest distance which is a straight line in any case and Distance denotes the distance travelled by the bot avoiding the obstacle.

26

Figure 6.8: Input: Two robot and one obstacle INFERNCE: In this case, for first bot initial point is denoted by (Xr1, Yr1) which is taken as (2, 3),(Xp1, Yp1) denotes the point on the periphery of the obstacle1 which is taken as (5,8), (7, 4),(Xg1, Yg1) denotes the destination point which is taken as (9,10 ).For second bot initial point is denoted by (Xr2, Yr2) which is taken as (8, 9), (Xp2, Yp2), denotes the point on the periphery of the obstacle1 which is taken as (3,6). (Xg2, Yg2) denotes the destination point which is taken as (2,1.5).

27

Figure 6.9: Output: Two robot and one obstacle

INFERENCE: In this case, one robot is reaching to its goal point. Other is not reaching its destination. Number of iteration tell us about the step required by the bot to reach the destination point i.e., 4853.So, after this(4853) number of iteration bot reached the point (Xg2, Yg2) i.e., (2,1.5) hence the goal is achieved.

28

Table No: 6.1 Force Field Method Linked With PSO Algorithm INPUT CASES One robot one obstacle One robottwo obstacle One robot 3 obstacles Xr 1 2 2 Yr 2 4 1 Xg 9.5 7 9 Yg 9 10 8 Xp1 5 4 2 Yp1 7.5 3 7 6 5 3 1 5 7.5 Xp2 Yp2 Xp3 Yp3

OUTPUT CASES Xi Yi No. of ITER 5468 4173 4933 Distance by force field method 10.93 8.346 9.866 Straight Line Distance 11.011 7.810 9.89 Optimum Distance by PSO 10.89 7.708 9.826

One robot one obstacle One robot-two obstacle One robot - 3 obstacles

9.35 6.85 8.85

8.86 9.86 7.8

Table No: 6.2 Force Field Method INPUT CASE 2 robot2obstacle Xr1 2 Yr1 3 Xp1 5 Yp1 8 Xg1 9 Yg1 10 Xr2 8 Yr2 9 Xp2 3 Yp2 6 Xg2 2 Yg2 1.5

CASE

Xi2

OUTPUT Yi2 No. of Iteration 8.86 5468

2 robot 2 obstacle

9.35

Distance1 by force field method 9.70

Straight Line Distance 9.604

29

Table No: 6.3 Multi Objective Particle Swarm Optimization Optimized Values Distance Danger Danger Danger c k P Q Index1 Index2 Index3 1 robot- 11.974 1.002 3.00 10.00 5.00 13.8006 1 obstacle 1 robot7.84 1.00 1.00 2.238 5.8018 13.697 7.522 2 obstacle 1 robot3 obstacle 9.766 1.001 1.002 1.001 2.566 6.3694 17.694 10.352 CASES

Fitness 0.0771

1.00

0.779

0.0238

0.4469

0.1024

30

7. CONCLUSIONS

Thus the objective of the problem statement has been successfully achieved with the help of MATLAB codes and can be implemented in a real time environment. Best values of different parameters of Force Field method are obtained by MOPSO algorithm in which fitness function was optimized. From the above results it can be inferred that by taking various source, destination and obstacle point in between, robot (one or two) was/ were tested in different cases or conditions. The distance travelled by the robots was obtained by force field method. Taking the parameters (different range) of F2 method in PSO algorithm, the optimized distance as well as best suitable values of the parameters had been achieved. Using MOPSO algorithm one more function named Danger Index was added to the fitness function which earlier consisted of single objective function named shortest distance and the total fitness was minimized. The future scopes of the project are: y Several research works have focused on the development of localization and communication systems. Many of these works are emulations of relative positioning systems, and in some cases the systems are developed and tested in simulation. y The main objective of this project will be simulation implementation of swarm intelligence into one or more robots that will show organized behavior. y If the hardware implementation of the project is possible with a less expense then y it would be very beneficial in different fields. There are many fields in which S-Bots can be used and some of them are as follows: o Education and Research o Defense sector o Communication sector o Automated transportation o Dangerous area detection and avoid

31

REFERENCES
[1] A Generic Force Field Method for Robot Real-time Motion Planning and Coordination by D.Wang, A thesis submitted in fulfilment of the degree of Doctor of Philosophy, Faculty of Engineering and Information Technology University of Technology,Sydney October 2009. [2] A Force Field Method Based Multi-Robot Collaboration By D.K. Liu, D. Wang, A paper submitted in fulfilment of the degree of Doctor of Philosophy, Faculty of Engineering and Information Technology University of Technology,Sydney October 2009. [3] Trianni, V., Nolfi, S., and Dorigo, M. Cooperative hole avoidance in a swarm-bot. Robotics and Autonomous Systems 54, 2 (2006), 97103). [4] Using Crowding Distance to Improve Multi-Objective PSO with Local Search Ching-Shih Tsou1, Shih-Chia Chang1 and Po-Wu Lai2 1. Department of Business Administration, National Taipei College of Business 2. Department of Information Management, Taiwan [5] Micro-MOPSO: A Multi-Objective Particle Swarm Optimizer that Uses a Very Small Population Size by Juan Carlos Fuentes Cabrera and Carlos A. Coello. [6] A Tutorial on Evolutionary Multi-objective Optimization by Eckart Zitzler, Marco Laumanns, and Stefan Bleuler. [7] Sporns and M. Lungarella. Evolving coordinated behavior by maximizing information structure. In L.M. Rocha, L.S. Yaeger, M.A. Bedau, D. Floreano, R.L Goldstone, and A. Vespignani, editors, Artificial Life X: Proceedings of the Tenth International Conference on the Simulation and Synthesis of Living Systems, pages 323329. MIT Press, Cambridge, MA, 2006. [8] T. Taha, J. V. Miro, and D. Liu, "An efficient path planner for large mobile platforms in cluttered environments," Proceedings of the IEEE International Conference on Robotics, Automation and Mechatronics, Bangkok, Thailand, 2006, pp. 225-230. [9] J. L. Jones, "Robots at the tipping point: the road to iRobot Roomba," IEEE Robotics & Automation Magazine, vol. 13, pp. 76-78, 2006.
32

[10]

H. Durrant-Whyte and T. Bailey. Simultaneous localization and mapping: part i. Robotics and Automation Magazine, IEEE, 13(2):99110, June 2006.

[11]

Roland Siegwart and Illah R. Nourbakhsh. Introduction to Autonomous Mobile Robots. MIT Press, 2004.

[12]

M. Bennewitz, "Mobile robot navigation in dynamic environments," PhD Thesis, University of Freiburg, 2004.

[13]

I. R. Nourbakhsh, C. Kunz, and T. Willeke, "The mobot museum robot installations: a five year experiment," Proceedings of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2003, pp. 3636-3641.

[14]

R.R. Murphy. competing for a robotics education. Robotics and Automation Magazine, IEEE, 8(2):4455, Jun 2001.

[15]

P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization, Academic Press Inc., 1981.

[16]

Deb, K.; Pratap, A.; Agarwal S. & Meyarivan, T. (2002). A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, Vol. 6,182-197

[17]

S.Thrun, D.Fox, W.Burgard, F.Dellaert," Robust Monte Carlo localization for mobile robots", Journal of Artificial Intelligence, 2001.

[18]

D. Dutta, et al., Multi-objective Evolutionary Algorithms for Land-Use Management Problem, International Journal of Computational Intelligence Research, vol. 3, no. 4, pp/ 371-384, 2007.

[19]

Y. Guo and L. E. Parker, "A distributed and optimal motion planning approach for multiple mobile robots," in Proc. of the IEEE Int. Conf on Robotics andAutomation, vol.3, Page(s):2612 - 2619,11-15 May, 2002.

[20]

A. Stentz, "The focussed D* algorithm for real-time replanning," in Proc. of the Int. Joint Conf on Artificial Intelligence, Page(s):1652--1659, 20-25 Aug., 1995.

[21]

A.

Stentz,

"Optimal and

efficient

path

planning

for

partially-known

environments," in Proc. of the IEEE Int. Conf on Robotics and Automation, vol.4, Page(s):3310 - 3317, 8-13 May, 1994.

33

[22]

K. Azarm and G. Schmidt, "Conflict-free motion of multiple mobile robots based on decentralized motion planning and negotiation," in Proc. of the IEEE Int. Conf on Robotics and Automation, vol. 4, Page(s):3526 - 3533, 20-25 April, 1997.

[23]

C. W. Warren, "Multiple robot path coordination using artificial potential fields," in Proc. ofthe IEEE Int. Conf on Robotics andAutomation, vol.1, Page(s):500 505, 13-18 May, 1990.

[24]

O. Khatib, "Real-time obstacle avoidance for manipulators and mobile robots," in Proc. of the IEEE Int. Conf on Robotics and Automation, vol.2, Page(s):500 505, Mar, 1985.

34