In this paper, a new algorithm is developed for multi-robot path planning of mobile Robot in unknown environment. The robots use radiation from their sensors to detect their surroundings, as well as positions of the other robots. In this paper a new approach for simultaneous consideration of two objectives is extended. The first objective is finding the safest path and another one is finding a path with minimum length. Voronoi Diagram is applied to achieve the safest path. In order to provide the safest path, we try to minimize the distance to the Voronoi Diagram (VD). Because the VD is a geometric location that is a distance from all obstacles to the workspace, it is therefore a safe place in terms of distance to obstacles. For gaining the second objective, shortest path, Euclidean distance from the current position of the robot to target is used. For solving this problem, it is used from particle swarm optimization (PSO).
The general Robot Motion Planning (RMP) problem deals with finding a collisionfree path for a robot from a start path to a goal path, in a workspace containing multiple obstacles considering an objective function. In modeling this issue, the more we bring things closer to the real world, the accuracy of the model increases when it is used in the real world. It is also assumed that the problem has different objective, with two objectives being the safest and shortest path. Finally, the problem is considered online and it has been tried to make real world affairs possible under the assumptions of the problem.
For the first time, online RMP for multiple robots is expanded in [
The rest of this paper is organized as follow. Section 2 states the proposed objective function. Then, the problem formulation is discussed in Section 3. Afterwards, Section 4 explains the proposed algorithm and numerical results and finally, conclusions are given in Section 5.
By minimizing the general objective function and taking into account the appropriate weights allocated to each criterion, a suitable path is obtained. The weights for the safest and shortest length criteria are λ1 and λ2 respectively. After performing the simulation and trying and error, the best values for them were λ1 = 1, λ2 = 0.25. 2.1
Since paths generated by a program must be run by robots, and each robot has its own static and dynamic constraints, the program should generate a path that is collisionfree and efficient in relation to some performance criteria. The main performance indicators and constraints inherently part of a motion planning is listed in Table 1. Total Objective Function including safest and minimum length on the path = 1 × 1 + 2 × 2 (1)
The majority of motion planners are designed to produce an optimal path by
considering a criterion similar to the time path or path length. However, in practice, it is a
feasible path if it meets two criteria including safety and shortest length, and so on.
A path that is defined as an optimal path with a particular criterion may not necessaril
y be optimal, for example, in terms of safety or other criteria [
The most important performance indicator is the time it takes to navigate. To find it and some other factors, several equations will be extracted. First, assume that the path consists of a number of discrete sections connected together to make the path of motion. Moving along the path will have several characteristics, and these will form the basis of a series of equations. The important phrases involved in the proposed model are described in detail below. 3
3.1
In this section, we describe the formulation as below.
In order to provide the safest path, we try to minimize the distance to the Voronoi
Diagram (VD). Because the VD is a geometric location that is a distance from all
obstacles to the workspace, it is therefore a safe place in terms of distance to
obstacles. Initially, the description of this algorithm is presented. The Voronoi diagram:
The fascinating truth about the Voronoi diagram is that its history dates back to the
seventeenth century, When Descartes used a subjectivity to describe the structure of
solar systems. Later mathematicians such as Dirichlet and Voronoi were principally
the first to introduce this approach. They used it for quadratic shapes in which the
branches, as well as the points, are measured in a regular diagram and measured by
Euclidean distance. The structure of the result is under titles: Dirichlet Tessellation
and Medial axis and Voronoi diagram, which is the standard name for this approach
today [
B( p, q) x | d ( p, x) d (q, x) D( p, q) x | d ( p, x) d (q, x)
VR( p, s)
D( p, q)
qs,q p
is bisector p and q. B(p, q) is a vertical line from the center of the line segment pq. B
is the half-panel separator:
contains p of the half-panel D(p,q) containing q. We will say that V is the V region
relative to S. Thus,
V (S )
VR ( p, s)VR (q, s)
(6)
According to the above definition, each Voronoi region, such as VR (p, s), is a 1-n
intersection of the half-open plate containing the p location. Therefore, VR (p, s) is
open and convex. Voronoi areas are as distinct and discrete as shown in Fig. 1.
The remarkable point is that due to inaccuracy of the scanner, the barriers of the
obstacles are not exactly recognized. The generalized local VD obtained from the VD is
based on the algorithm [
In this paper, two objectives are considered that are including safest path and the shortest path as below: Most path planners aim to generate an optimal path considering a single criterion like path travel time or path length. However, in practice, a path is feasible if it meets several conditions, such as safety, estimated needed time for navigation, shortest length, etc.
A path which is considered as optimal in terms of a single criterion may not
essentially satisfy other criteria all together [
Some works exist in the field of multi-objective robot motion planning, including an
approach for obstacle avoidance with multi-objective optimization by PSO in
dynamic environment in [
Path planning in dynamic environments epitomizes the necessity of considering multiple objects in path planning: when the environment is time varying, the minimum length path and minimum delay path are usually different issues. Delay is defined as the time needed for traveling from start to goal, whereas length is the distance actually traveled by the robot along the path.
For robots needing to reach their destination as early as possible, a minimum-time
path might seem desirable, but it may require a lot of time to be traversed due to
uneasy terrain. Surely there exist various feasible paths between start and goal points
being neither short nor fast but providing reasonable tradeoffs between shortness and
fastness. These are generally desirable paths, while a path optimal for a single
criterion without considering other equally important criteria is not desirable [
In the proposed method, the criterion for path shortness is defined as the Euclidean distance between each particle and the goal point in each iteration, and the criterion for path smoothness is defined as the angle between two hypothetical lines connecting the goal point to the robot’s positions in two successive iterations, i.e. gbest i and gbest i−1, in which i is the iteration number. The definition of path smoothness in this way is a novel idea. The first objective function, the shortest path, is defined as: Fshortij (xprtposij xgoal )2 ( yprtposij ygoal )2 (9) 3.3
The aim of the total objective function is the simultaneous maximizing safety path and minimizing length of path. As mentioned above for the safest path, minimizing the distance to the geometric location of the points on VD is used and we use the aggregated weighted approach to minimize them simultaneously. In order to make the safest path, the total distance between the segments of the path and VD is considered. In order to minimize length of path, Euclidean distance from the current position of the robot to target of each segment is calculated. Each of these objective functions has a weight in the total objective function. 4
In this section, it is assumed that the robot is not only unaware of its surroundings but also of its location. Therefore, the robot uses the two PSO and VD algorithms as the general and local search algorithms in the work environment to sense and identify the environment, respectively. The paper assumes that borderlines are static in the workplace and do not change over time.
How to use two of these algorithms in an online environment is that after sensing the environment by a robot, the sensor is in a visual environment that is circular to the radius of the robot's vision in its surroundings, a local and global search in the visible space is done. First, using the PSO algorithm, the best robot next position, which is the gbest, is determined in the visual environment.
Because in determining the gbest in the PSO algorithm, goal is secure path and shortest length, and these goals are presented in the PSO objective function. How to do it is that the gbest point is determined by the two goals of most safe path and minimum path length and the robot moves to the gbest point. In the other worlds, the gbest point obtained which satisfies the above-mentioned two goals.
Using the VD algorithm, which is applied as a local optimizer, the visible region is first obtained. How to use the Voronoi diagram, which is addressed as a first time in this paper, that’s is that VD is using lines with an equal distance of the intersection points obtained from the collision point of the sensor with surrounding obstacles. An illustration of how to create a Voronoi diagram in each stage for the robot is shown in Fig. 3.
20 18 16 14 12 10 8 6 4 2 00 2 4 6 8 10 12 14 16 18 20
Fig 3. An overview of how to create a Voronoi diagram at each stage for the robot For solving the problem and implementation it, we used from a hybrid of the algorithms titled Basic PSO (BAPSO) and VD. In each of the mentioned algorithms, the robot's motion is planned. In this way, the initial population is generated through related mechanism’s BAPSO, then VD is established, and in the visual range, based on population upgrade mechanisms in the mentioned algorithms are searched. Updating BAPSO is according equations (10) to (13).
prtvel ij w prtvel ij1 c1 rand ( pbest ij1 prtpos ij1 ) c2 rand (gbest i1 prtpos ij1 ) prtpos ij prtpos ij 1 prtvel ji prtpos 0j xmin rand(xmin xmax ) prtvelij xmin rand(xmin xmax ) t (10) (11) (12) (13) After several tests for 14 problems, the mean and standard deviation of the results of the time and distance traversed for the the BAPSO + VD and Genetic Algorithms (GA) +VD method were obtained and the results are presented in Table 2 and the Figs (4) to (6) are given. 9 Fig. 5 shows a simulation from robot motion planning in the more complicated environment Fig. 6 shows a simulation from robot motion planning in the most complicated environment
gbesti prtvelji+1 prtposji
Collective Memory
pbestji Fi Current Move
Personal Memory In this article, the problem of Motion Planning for mobile Multiple Robots Considering two objectives, the safest path with minimum of path length was analyzed. As the environmental conditions are timely. In fact, at this stage, for reaching to a safest path, we used from Voronoi Diagram for this objective. In addition, minimizing the length of path of the robot is also added to another problem objective and is considered in the objective function of the algorithm. In finally the problem is solved with two algorithm named BAPSO+VD and GA+VD that the results illustrated that BAPSO+VD have the better results.