In this paper a collision avoidance algorithm with speed control and selfoptimization in order to improve the performance of the autonomous system is presented. The system consists of a group of mobile robots which move autonomously in a certain area where static obstacles are inserted. In this paper a new term called occupancy ratio is proposed with using collision density to evaluate the performance of the autonomous system. Each robot has a start con guration point and destination con guration and it should move to its destination without any collisions with static obstacles or other moving robots. Simulation was carried out with using MATLAB 2016a. It has found out that the collision density can re ect the performance of the system, the less collision density corresponds to a better performance.
The main objectives are to move multiple robots in a common workspace to perform a certain mission that
demand that each robot nd its way from start con guration to a given goal con guration without mutual collision
and collisions with obstacles. Often, movement planner approaches are characterized as coupled (centralized) or
decoupled planner. A coupled planner deals with all robots as a single combined robot and computes a path in
a combined con guration space, while decoupled planner computes a path for each robot independently. In this
approach robots nd their paths and avoid collisions with obstacles or with each other. Each robot has a sensing
scope and can exchange con gurations information only with other robots within its sensing scope. Autonomous
navigation has been widely investigated and many techniques and approaches were presented. One of e ective
techniques is a leader-followers conception is proposed in [
In the paper in section 2 we will discuss the path planning algorithms which we propose for a system of moving robots, in section 3 we will describe the system, taking into account the kinematics characteristics of the robot, the di erent scopes of the robot, and the equations for the motion behavior, consider the collision avoidance algorithm, the cooperative behavior and sequence of the system. Section 4 shows the results of the simulation.
Path planning problem is how to nd a continuous motion that will take a robot from a given initial con guration
to a desired destination con guration, subject to the constraint that a robot does not collide with any obstacle
in its workspace at any point in the motion. Di erent approaches have been introduced to implement path
planning for mobile robots. Approaches possible to be in accordance with the environment, type of sensor, robot
capabilities, etc. Path-planning is needed between start and end point to create a path that should be free of
collision and satisfy certain criteria such as shortest path [
In our model the robots use Bug and PRM algorithms to a nd path to the goal con guration, and it has minimum distance that can sense the environment around it, once obstacle or another robot appear to collide, robots start exchange information about their current position and next position to achieve their goal con guration without collisions. 2.1
Probabilistic roadmaps (PRM) are an e ective tool to capture the connectivity of a robot's collision-frees pace
and to solve path-planning problems with many degrees of freedom [
Bug algorithm is a local path planning algorithm. Bug algorithms use sensors to detect the nearest obstacle
as a mobile robot moves towards a target with limited information about the environment [
Path planning algorithm (PRM or Bug) determines a full trajectory to the robot from the initial point to the goal point, as mentioned before, PRM algorithm is for known environment but Bug is a discovering algorithm for unknown environment. In both cases path-planning divides trajectory into smaller parts of linear trajectories, robot records the coordinates of the points of the start and end of each small trajectory. Such trajectories are free of collisions in terms of static obstacles, for dynamic obstacles we use collision avoidance algorithm. Fig.1 and Fig.2 show the trajectory calculated by Bug and PRM algorithms, respectively, in order to nd collision free path to goal con guration and how it's decremented into smaller linear trajectories. Now, the problem how to compute the path planning to move the robot from the initial point to a target point in the unknown environment has to be discussed. In order to control the behaviors of multi-mobile robots we need kinematic analysis of each robot. It's assumed each robot consist of two wheels in a two dimensional plane and robots move without slipping on a plane. The kinematics model of mobile robot and linear movement illustrated in Fig.3 can be represented in (x; y) Cartesian coordinates by the following: 0 x_ (t) 1 0 cos @ y_(t) A = @ sin _(t) 0 0 1
It's also assumed that the robots move according to constant predetermined acceleration (positive or negative) till they reach maximum velocity and then move in constant speed (v = const) or till they stop (v = 0). Also, as kinematics constraints for robots movement, they can only move in straight lines, and in order to change their directions they need rst to slow down to zero velocity then start to turning to the new direction with predetermined angular velocity (!). Fig.5 shows robots dynamic displacement (distance) with time (period). Robots move in three main modes: 1) acceleration mode, 2) constant velocity mode, 3) deceleration mode. 3.2
We assume that the robots are provided by sensors that enable them to discover all objects (moving robots or static obstacles) in a circular sensing scope within a radius of dsensor as shown in Fig.5, also they can nd distances between them and any object existed in a distance equal or less than dsensor. Critical distance dcritical indicates the distance at which the robot must start to slow down till stand still if any other robot or obstacles are in a distance less than this critical distance, robot should stop and collision avoidance algorithm will be activated. A robot moves toward its destination coordinates in iterations, at each iteration, the robots calculate the next position according to path planning sequence information. Sensor scope check for expected collisions, it returns a value of (1) if there are any object within a distance less than dcritical or value of (0) if there are no objects located in a distance less than dcritical radius scope. In the case of (0) feedback, it means that next position is clear of any possible collisions and robot start to continue moving to this position, next position coordinates are being calculated by
Kinematics during turning 8 xnext = xcurrent + v1 cos ; > > > > <
ynext = ycurrent + v1 sin ; > > > > : v1 = minfv + acc; vmaxg: Here, v is instantaneous velocity, acc is acceleration value, (xdest; ydest) calculated with is angle between x-axis and destination point = arctan(y ydest)=(x xdest):
After that linear distance between robot's position and destination point is calculated to determine if the robot reaches its destination and ready to receive a new destination coordinates or it stills not yet reaches its destination and have to repeat the previous calculation.
distance = p(xdest xcurrent)2 + (ydest
ycurrent)2: If the sensor data returns value of (1), it indicates the presence of obstacle or moving robots that block robot's path to the destination point and there is a risk of collision, hence the obstacle avoidance algorithm is activated. This algorithm works in the following steps: 1. Slow down the moving robot till zero velocity according to its kinematics restrictions. 2. Start searching for a new free of collisions position according to sensor feedback data.
3. If the distance between the new position and the blocking objects is more than dcritical, robot's path is modi ed and robot move to this new position.
4. If the distance is equal or less than dcritical, position reserved as occupied and algorithm starts searching for another point. The searching for a new position achieved by checking positions on the circumference of distance equal to the critical distance, in each iteration algorithm adds radial interval ( ) to the default next position to get new possible positions, the sequence of searching for alternative points indicated by numbers in Fig.7. Then algorithm checks if the point is valid or not, this is achieved by the following sequence (n is a number of robots and obstacles in sensing scope).
Step 1. Checking for the next position of the robot (xnext; ynext ).
di = p(xi xnext)2 + (yi ynext)2;
i = 1; :::; n: if (di > dcritical); (di dcritical); (xnext; ynext) = accepted; (xnext; ynext) = ref used: Step 2. The next position is refused. Adding (
) to the current theta of the robot: ( (new r) = + )And( (new l) = ): Step 3. Find new coordination of the new two positions for ( (new r) and (new l) ) as in equation (1).
Step 4. Check validity of those two positions as in Step 1, next position of the robot is set to be the accepted position, if both positions are accepted, the nearest one to the destination is set to be the accepted position and its coordinates is set as (xnext; ynext).
This algorithm continues in iterating till it can nd positions free of collisions otherwise robot stops and repeat these calculations after time interval t. 3.5
In this model the robots can cooperate and exchange information with each other. For more reality we made some restrictions for this cooperative behavior. First, the robots can only cooperate with other robots located in their sensing scope. Robots can't cooperate with other robots which are located in a distance more than their sensing scope. Second, nearby robots can only interact with limited information, they can only exchange their position coordinates with each other. When robots block the way of each other, collision avoidance algorithm start to search for an alternative free of collision con guration, and share the resulting coordinates with all robots within their sensing scope.
In this simulation using MATLAB R2016a, we simulate the dynamics of a group of robots (2 till 5) moving autonomously through start and goal con gurations, which chosen randomly using collisions avoidance algorithms then calculate collision density as a number of collisions per minute. Then each robot con gures its own velocity and accelerating parameters to reduce the number of collisions and raise the e ciency of the autonomous system.
Robot relative dimensions are 2.4 cm x 2.4 cm, area occupied by each robot is 5.76 cm2, dimension of the con guration space is 30 cm x 30 cm, occupancy ratio is the percentage of space occupied by robots and obstacles to the total area of the con guration space, so the occupancy ratio of 3 robots autonomously moving without the any obstacles is (3 x 5.76 cm2)/(900 cm2)=1.92% , acc=0.01 cm/sec2, vmax=0.1 cm/sec, !=0.1 rad/sec, and the sensor scope dcritical=5 cm (the critical distance that each robot start to action to avoid collision while any other object are near by less than this distance).
Robots record its maximum sensing scope dsensor and automatically optimize its maximum velocity vmax and critical distance dcritical according to the braking distance which is the distance that robot needs to reach the standstill. dbrake=(vf2 vm2ax)=2a), vf is a nal velocity and equals to zero, vmax is an initial velocity, a is a negative acceleration, dbrake is a braking distance and in this case dcritical 2dbrake so that robot can calculate vmax which ensure that robot will stop safely without any object that may suddenly appears in its sensing scope. Fig. 7 shows the main three scopes for the robot in shape of three circles. Robot is in the center. The outer circle represents the sensing scope dsensor of the robot. Robot can be aware of any object exist in the range of this circle and measure the distance between its position and the object's position. The middle circle represents the critical distance dcritical, any object in the range of this circle represent a danger of collision with the robot. In such case robot starts to brake. The inner circle represents the brake distance dbrake that the robot needs to reach zero velocity.
Fig. 8 and Table 1 show the occupancy ratio and collision density. Collision density can be integrated with other factors like duration to evaluate the autonomous systems. It's clear that optimizing the velocity of robots enhance the performance of the system by decrease collision density to zero value. Fig.9 shows snapshots of the system simulation model for multi-robot system on MATLAB.
In this paper simulation of autonomous system for a group of decoupled multi robots is presented, this simulation take in mind the dynamics restrictions of mobile robots or a group of vehicles. An approach to evaluate the performance of autonomous system by using occupancy ratio and collision density is proposed. Each robot in this system can optimize its own velocity, search for free con gurations and in the same time it collaborates with nearby robots to avoid collisions and achieve the demanded mission. This system is tested with robots up to group of 5 robots using MATLAB. It has found out that the collision density can re ect the performance of the system, the less collision density corresponds to a better performance while occupancy ration has inverse e ect on system performance. In case of optimizing the velocity of the robots it is possible to improve the performance of the system as collision density equal to zero.