Keywords

1 Introduction

The Target Search or tracking of the target is a very complex problem mostly when the surrounding environment of the target or search area is unknown or is too complex i.e. containing many different kinds of obstacles. In recent times a variety of efficient applications have been made in this field including search and tracking in the disaster area, exploration of Natural resources, monitoring of Natural resources and environment, air traffic control, etc. [1].

The common thing in all of the target search and tracking applications is path planning which is to be followed by the multi-robots to reach the desired target position. This problem is also previously partially solved by the use of multi-robot systems, by the use of the mobile robots which can dynamically adapt to the changing position of the target in some complex environments [2].

In this paper, a discussion of various search and tracking algorithms is given which can be used in different environments. In recent years, there are many reviews on the path planning in swarm intelligence but most of them are the broad reviews, instead of going into the details of the previous papers.

2 Overview of Swarm Robotics

The term Swarm Robotics defines itself as it includes the swarm of homogeneous robots which have the capability of working in coordination with each other. They do not include any centralized system or no head robot or system is controlling all other systems or robots. In 1989 the term ‘swarm intelligence’ was introduced by Beni and Wang in the context of cellular robotic systems. The first cellular robotic system was introduced by Fukuda which was termed as CEBOT [4, 5].

Basically, Swarm robotics is introduced because of the advantages it provides as compared to a single robot.

  • Scalable: Scalability in swarm robotics means the size of the swarm can be increased or decreased as needed. This does not have any effect on the performance of the swarm as each robot is independent in itself [6, 7].

  • Flexible: Here in the context of swarm robotics, flexible means that the robots are flexible with the changes in the environment [6], surroundings, and/or nature of the task given. For SRSs it is essential to be flexible so that there is no need to reprogram the robots when the problem changes.

  • Robust: The swarm of robots can be termed as robust by the measure by which the swarm can continue to perform the assigned task even if some of the robots of the swarm fails due to some reason or if there arise some non-suitable conditions for robots [6]. This is possible because of the design of every individual robot. So some technical issues don’t affect the complete swarm that much.

3 Parameters Used in Searching and Tracking

Parameters used to compare different path planning algorithms in Swarm robotics are given below.

  • No. of Targets.

  • Target Mobility

  • Tracker Mobility

  • Environment Complexity

  • Knowledge of target motion in advance

  • Cooperation among the robots

  • Coordination between the trackers.

4 Path Planning Algorithms for SRS

In Sect. 1, it is mentioned that target searching and tracking is a complex task in swarm intelligence. In this section, the methods used for searching and tracking the targets in different environments are discussed. Few problems related to SRS are also discussed in this section.

4.1 Local Minimum Problem solution Based on PSO

The local minimum problem in SRS means that the robot is surrounded by obstacles from both sides. Basically, there are two kinds of path planning algorithms in SRS – local path planning and global path planning [16,17,18]. The problem of local minimum arises in local path planning algorithms. The local path planning is preferred over global path planning because local planning works in real-time and is more accurate than global planning due to the presence of more adaptability in a dynamic environment.

The further subsections include the dynamic model of the robot and the method to set up the virtual robot in a virtual environment and then the cost function used in the method.

Dynamic Model of Mobile Robot

In this paper the dynamic position and dynamic velocity of the robot are represented as:

$$ \left\{ {{ }\begin{array}{*{20}c} {p\left( {x + 1} \right) = v\left( x \right) + p\left( x \right)} \\ {v\left( {x + 1} \right) = v\left( x \right) + u\left( x \right)} \\ \end{array} } \right. $$
(1)

Virtual Robot

Here a virtual robot is used which is just the projection of the real robot over the edge of the obstacle as shown in Fig. 1.

Fig. 1.
figure 1

Path of virtual Robot along the edge

Full size image

The position and the velocity of this virtual robot is given by \(\hat{x}_{i}\) and \(\hat{v}_{i}\). These are calculated as follows:

$$ \hat{p}_{i} = Pp_{j} + \left( {I - P} \right)y_{i} $$
(2)
$$ \hat{v}_{i} = Pv_{j} $$
(3)

The Particle Swarm Optimization (PSO) Algorithm

Particle Swarm Optimization is an optimization algorithm proposed by Kennedy and Eberhart [23]. In this system, each candidate works in co-operation with each other and give their solution (particle) which are compared with each other to get global optimized value. Here particle moves in problem space and seeks for its best position. This space may be multi-dimensional say \(d\)-dimensional and there can be \(n\)-number of particles. So by using these, the position and velocity of the \(i^{th}\) particle at \(k^{th}\) iteration can be given by:

$$ \vec{x}_{i} \left( k \right) = \left( {x_{i,1} \left( k \right),x_{i,2} \left( k \right), \ldots \ldots ,x_{i,d} \left( k \right)} \right) $$
(4)
$$ \vec{v}_{i} \left( k \right) = \left( {v_{i,1} \left( k \right),v_{i,2} \left( k \right), \ldots \ldots ,v_{i,d} \left( k \right)} \right) $$
(5)

These positions and velocities are updated at each iteration by using below:

$$ \vec{x}_{i} \left( {k + 1} \right) = \vec{x}_{i} \left( k \right) + \vec{v}_{i} \left( {k + 1} \right) $$
(6)
$$ \vec{v}_{i} \left( {k + 1} \right) = {\upomega }\vec{v}_{i} \left( k \right) + c_{1} r_{1} \left( {\overrightarrow {Pb}_{i} \left( k \right) - \vec{x}_{i} \left( k \right)} \right) + c_{2} r_{2} \left( {\overrightarrow {Gb}_{i} \left( k \right) - \vec{x}_{i} \left( k \right)} \right) $$
(7)

where \(\overrightarrow {Pb}_{i} \left( k \right) = \left( {Pb_{i,1} \left( k \right),Pb_{i,2} \left( k \right), \ldots \ldots ,Pb_{i,d} \left( k \right)} \right)\) is the local optimum location of the \(i^{th}\) particle and \(\overrightarrow {Gb}_{i} \left( k \right) = \left( {Gb_{i,1} \left( k \right),Gb_{i,2} \left( k \right), \ldots \ldots ,Gb_{i,d} \left( k \right)} \right)\) is the global optimum location. \(c_{1}\), \(c_{2}\) are the acceleration coefficients. They control the step size of the particles. \(\omega\) is the inertia [24]. \(r_{1}\) and \(r_{2}\) are the random numbers between 0 and 1.

A Solution to the Local Minima Problem

The solution to the local minima problem is given by using a virtual target point method [25]. In this method, a virtual target point is set up outside the boundaries of the detected obstacle. Now the original robot tries to reach this virtual target point. If it is unable to reach this virtual target point then this target point is changed repeatedly. After reaching this virtual target, the robot moves to its original destination. For this, the PSO algorithm is used.

4.2 PSO Based path Planning in Dynamic Environments

Deciding a path for multi-service robots traveling in dynamic environments is a very complex problem.

In this paper, a PSO based optimized path planning is done for multi-service robots. The aim is to take all the robots from their source to a destination without collision between themselves or with any obstacle on the way. A simulation platform Virtual Reality Educational Pathfinder (VREP) is used to experiment.

The Approach of PSO

The particle swarm optimization is explained in (4.1.4). The approach used here is shown in the flowchart below (Fig. 2).

Fig. 2.
figure 2

Flow of the proposed algorithm

Full size image

In this study, PSO steps followed are given as:

  1. 1.

    The current position and target of all the multi-service robots are determined.

  2. 2.

    The planning is done to decide the path from the current position of the robots to the destination position of the robots.

  3. 3.

    When met with any obstacle, each robot re-plan the path in the direction of the destination.

  4. 4.

    If any robot does not encounter any obstacle on the way, each robot follows the same path plan as decided earlier.

This fitness function is given as follows:

$$ f\left( x \right) = \min \mathop \sum \limits_{i}^{n} \left[ {\left( {x_{i} - x_{goal} } \right)^{2} + \left( {y_{i} - y_{goal} } \right)^{2} } \right] $$
(8)

where \(\left( {x_{i} ,y_{i} } \right)\) is the current position of the \(i^{th}\) robot and \(\left( {x_{goal} ,y_{goal} } \right)\) is the co-ordinations of the target point. Here in this algorithm, the population size is decided by the user and can be changed accordingly.

The simulation has been done by using 4 robots. The attributes and their values of the simulation environment are given in Table 1 shown (Table 2):

Table 1. Simulation 2D environment
Full size table
Table 2. Simulation result
Full size table

4.3 A Path Planning of Multi-destination for Mobile Robots

There are many algorithms when it comes to deciding the path from one point to other or in complete coverage of the environment in path planning, but the question always arises when it comes to decide the path in case of multi-destinations. So in this paper, a new algorithm that focuses on the multi-destination path planning is mentioned. This algorithm is the combination of the particle swarm optimization and the Vortex Search Algorithm (VS) [36]. In the first place, the sequence of the destinations is decided/optimized by using the PSO algorithm. After the VS algorithm is applied to get the collision-free path from one destination to the other. By using this algorithm a smooth and short path can be decided efficiently.

Fig. 3.
figure 3

The proposed algorithm based on PSO and VS

Full size image

Problem Statement and Definitions

The algorithm proposed here is much similar to the Travelling Sales Person (TSP) problems [37].

The framework proposed here is shown in Fig. 5. It is based on PSO and VS algorithms (Fig. 3).

Here a mobile robot is taken as a point. The boundaries of each obstacle are increased by the sum of the size of the robot and the safety distance. After this, the optimal sequence of the destinations is found with the help of PSO. And at last, the path between the destinations is found with the help of the VS algorithm without any collision.

Fig. 4.
figure 4

Path between the source and the target.

Full size image
Fig. 5.
figure 5

Iterations in 4 target path planning

Full size image

The Multi-destinations Approach

The approach goes as: Firstly the best path is decided from source to multi-destination using PSO. Then this sequence is passed to VS as input. Lastly, the path between these destinations is decided using the VS algorithm such that there is no collision [39].

  1. I.

    Optimizing the destinations.

  2. II.

    Generating the Initial Solution.

  3. III.

    Replacing the current solution.

  4. IV.

    Adaptive radius Decrement

  5. V.

    The smoothness of the path.

The Result

To verify the effectiveness of the proposed algorithm, it is compared with the PSO, VS, and A* algorithm in the same environment (Fig. 4).

As shown in Fig. 10 the iteration speed of VS is more than PSO, which is more than the A* algorithm. The Fig. 14 Shows the iterations involved in the path planning when the number of targets is 4.

5 Result Analysis

See (Tables 3 and 4).

Table 3. Problem classification in various research
Full size table
Table 4. Algorithm comparison
Full size table

6 Conclusion

Due to the robustness, scalable, flexible, fault tolerance, and many other properties of SRSs can be used in many different applications. Many algorithms are described and discussed in this paper. Among the different problems discussed in the paper, the most challenging problem is to solve the local minimum problem. This problem is the most challenging because if the robot is trapped in the local minima the already taken path by the robot becomes erroneous. So the robot has to firstly get out of the local minimum and then again take some other path to reach its target position. For this purpose, a virtual target point method is discussed in this paper.

Few other problems related to optimized path planning for robots in a complex environment are also discussed. Few algorithms which are suitable for some specific type of situations are discussed in the paper. Although there is no algorithm in swarm robotics which optimizes the path for every situation or which can solve all of the problems related to SRS. This is just because of the complex nature of swarms and the highly complex calculations related to swarm.