International Journal of Intelligent Robotics and Applications

https://doi.org/10.1007/s41315-020-00129-0

REGULAR PAPER

Path planning for robots: an elucidating draft

Kaushlendra Sharma1 · Rajesh Doriya1

Received: 22 January 2020 / Accepted: 3 April 2020

© Springer Nature Singapore Pte Ltd. 2020

Abstract
Proceeding for an elucidating draft for the robot’s path planning, there are several aspects which need to be addressed and
discuss in detail. Some key points include the definition of the working environment, type of technique used to solve a par-
ticular type of problem, their subclassification and interdependencies with each other. It is also required to discuss in detail
to understand and solve the problem of path planning in the right perspective. To do so, this paper presents the evolution of
path planning algorithms of the last 5 decades, and then a broad classification of all those algorithms. After that, algorithms
are categorized into different sections and has been discussed which are very often used in recent times to make the path
planning approach more effective and efficient. This paper presents an extensive and elaborative survey of path planning
algorithms and associated techniques for robots whose excellent contribution to the filed is invaluable. There are multiple
issues related to the working environment of robots, whether it belongs to the two dimensional or three dimensional, static
or dynamic, single robot or multi-robot, single objective/multi-objective and many more. This paper addresses all these
issues in a detailed way. Another critical issue is related to the scope of algorithms which has been discussed at length in this
paper like whether the algorithm is compatible for global/local path planning, it is Exact or heuristic in nature. This issue
is systematically and hierarchically described to get a clear understanding of the problem domain. The effort is to bring an
insight into the classification and evolution of path planning algorithms with its technical detail and discussions. The paper
presents some emerging technologies which can be clubbed with robots to take it to another level. Cloud computing is one
which is being extensively absorbed in many technologies. This paper discusses some cloud platforms like OpenStack and
Google Cloud to deploy path planning applications for robots. This paper tries explicitly to conclude by testing path plan-
ning robots using Google cloud platform (using it as Infrastructure as a Service IaaS) citing its advantages and capability to
expand its acceptability and assumes to be the future scope for robot path planning.

Keywords Global · Local · Static · Dynamic · Path planning · Exact · Heuristics · Cloud computing

1 Introduction procedures defined to compute path are typically segregated

based on the traversing mechanism of a particular algorithm
Path Planning is considered to be one of the cores primitive for the image or graph given as input to the system. This
in robotics for finding a route to be picked up for reaching particular image or graph is also called as the environmental
goal position. Path planning meant to be finding the best setup/configuration space. There are several other aspects
path in terms of the time it takes to reach its goal and the which need to be considered for deciding the best path or
time it yields to compute that path. All the techniques and optimal path. It also depends on the environmental setup or
execution area where the path needs to be discovered for
Fully documented templates are available in the elsarticle package executing a certain task. In some cases, there might be one
on CTAN. single objective and which can be in the centre for execu-
tion, whereas there are certain situations where more than
* Kaushlendra Sharma one objective needs to be accomplished, and therefore the
ksharma.phd2017.it@nitrr.ac.in
execution has to be moulded (Liu et al. 2018; Artuñedo et al.
Rajesh Doriya 2018) accordingly.
rajeshdoriya.it@nitrr.ac.in
To get detail in-depth understanding of the problem and
1
Department of Information Technology, National Institute its solutions. Let us first know the history of path planning. It
of Technology Raipur, Raipur, India

13
Vol.:(0123456789)
 K. Sharma, R. Doriya

is development and the inception of robots. One of the glori-

ous histories regarding robots is the invention of program-
mable robots named ‘Unimate’ in 1961 which lifted a metal
piece, from there on there was continual development took
place at a rapid pace. Path planning word came into exist-
ence with the commencement of robots, though the debut
of robots was far older and was very much debated in the
first half of the 20th century. The features of robots or robot-
ics developed with each passing year, path planning is one
among them, which was lauded and experimented hugely,
a recent addition is the use of cloud computing platforms
(Kehoe et al. 2015). Computational development started in
the second half of the twentieth century.
Path planning can be studied in details by considering the
scenario as much as possible. This paper presents the dif-
ferent types of environments, generally being considered for Fig. 1  Venn diagram representing environmental classification of
path planning problems. First one complies the environment path planning problems
based on the nature of obstacles, i.e., Static environment/
Dynamic environment and then the environment based on
geographical conditions are some critical areas where sev- After knowing the details about the environment, the
eral different techniques have been applied in the past (Drake next important thing to understand is the traversing mecha-
et al. 2018; Sun and Yu 2017). Fulfilling Single objective or nism. Traversing the given environment results into the path
multi-objective in an environment could be another area of length, computation time and computational complexity,
research. There are also some cases where more than one these variables decide the suitability of several algorithms in
objective has to be fulfilled for satisfying the overall objec- a particular environment. The paper entails all the requisites
tives. This article has tried to cover all those aspects in lit- of these two parameters in the experimental setup and result
erature and experiment section. section. Setting up the environment is also crucial where the
While dealing with the environmental setup, there are algorithm has to perform for finding path, and that can also
many aspects and ways to study the path planning problem be subdivided into a static and dynamic environment.
(Zhang et al. 2017). Broadly it is subdivided into the study The survey of path planning is organized in this paper
of the static region and dynamic region. Also, the research into five different sections with subsections in it, the evolu-
is being laid out regarding the 2-D and 3-D environment, tion of path planning techniques is presented in detail, the
Fig. 1 represents different path planning environments with next sections give an insight to some critical nature-inspired
their inclusions and exclusions with other environments, algorithms used in the past and recent times for robot path
Fig. 1 demonstrates that local path planning and global planning, after that the following sections cite some nota-
path planning which can be understood as unique entity and ble algorithms contribution in the field. After that, the next
fall both in static path planning as well as dynamic path section describes the recent contributions, and in the last
planning. In contrast, these two broad path planning envi- section path planning using cloud computing platform is
ronment comes under both the two-dimensional as well as discussed in detail. The paper also presents the practical
three-dimensional environment, the classification and inter- approach towards using cloud computing platform for robot
linkage path planning environments is depicted in the Venn path planning and displays the result in one section by using
diagram. Local path planning means the robot is having the Google Cloud as IaaS. Finally, the paper concludes the sum-
knowledge of a restricted environment which comes under mary and recommendations for future work based on the
its sensor range or up to a precisely defined radius. Global study and survey done for robot path planning.
path planning means the robot before its actual run is having
the complete knowledge of the entire environment. Static
or Dynamic environment is classified based on the nature 2 Evolution of path planning techniques
of obstacles lying in the environment, if all the obstacles
present is immovable, then the environment can be called Table 1 presents the evolution of path planning algo-
as static environment, and if it is changing its location ran- rithms. The survey considered the research papers from
domly then that would be treated as the dynamic environ- 1970 to 2019, covering almost 50 years. To survey and
ment. Next most important issue is to understand the concept summarize the work done in the last 5 decades is quite a
of path planning for robots. lengthy task. To do so a block of 10 years is first taken into

13
Path planning for robots: an elucidating draft

Table 1  Evolution of path planning techniques over the years

Approach/year References Single robot Multi robot Static/dynamic Local path Global path 2D/3D space R.I

Artificial Neural Net- Martin and Del Pobil ✓ Static ✓ 2D 09

work, 1970 (1970)
Multi Resolution A* Autere and Lehtinen ✓ Static ✓ 2D 01
Method, 1970 (1970)
Travelling Salesmen Lin and Kernighan ✓ Dynamic ✓ 2D 4465
problem, 1973 (1973)
Navigation for JPL Thompson (1977) ✓ Dynamic ✓ 3D 191
robot, 1977
Real Time Obstacle Khatib (1986) ✓ ✓ Dynamic ✓ 2D 7747
Avo., 1986
Multi-Reso. Path Plan- Kambhampati and Davis ✓ Static ✓ 2D 731
ning, 1986 (1986)
Artificial Potential Field, Warren (1989) ✓ Static ✓ 2D 339
1989
New Heuristics Algo- Zhu and Latombe ✓ Static ✓ 2D 236
rithms, 1989 (1989)
Using Laplace’s equa- Connolly et al. (1990) ✓ Static ✓ 3D 735
tion,1990
Numerical Potential Barraquand et al. (1992) ✓ Static ✓ 2D 1137
Field, 1992
Genetic Algorithm, 1997 Han et al. (1997) ✓ Dynamic ✓ 2D 98
Probabilistic Roadmap, Kavraki et al. (1996) ✓ Static ✓ 2D 5050
1996
Evo. Artificial Potential, Vadakkepat et al. (2000) ✓ Static ✓ 2D 346
2000
Rapidly Random Tree, Kuffner and LaValle ✓ Dynamic ✓ ✓ 3D 2532
2000 (2000)
Particle Swarm Optimi- Saska et al. (2006) ✓ Dynamic ✓ 2D 148
zation, 2006
Ant Colony Optimiza- Garcia et al. (2009) ✓ Static ✓ 2D 320
tion, 2009
Sampling Based Algo- Karaman and Frazzoli ✓ Static ✓ 2D 2037
rithms, 2011 (2011)
M* Path Planning Algo- Wagner and Choset ✓ Static ✓ 2D 131
rithm, 2011 (2011)
Hybrid ACO-GA Algo- Châari et al. (2012) ✓ Static ✓ 2D 57
rithm, 2012
Pigeon Inspired Optimi- Duan and Qiao (2014) ✓ Dynamic ✓ 3D 216
zation, 2014
Artificial Bee Colony, Contreras-Cruz et al. ✓ Static ✓ 2D 110
2015 (2015)
Bacteria Foraging Field, Hossain and Ferdous ✓ Dynamic ✓ 2D 91
2015 (2015)
Cuckoo Search Algo- Mohanty and Parhi ✓ Static ✓ 2D 60
rithm, 2016 (2016)
Gravitational Search Das et al. (2016) ✓ Static ✓ 2D 89
Algo., 2016
Fuzzy-Wind Driven Pandey and Parhi (2017) ✓ Dynamic ✓ 2D 44
Opti., 2017
Intelligent Bezier Tharwat et al. (2019) ✓ Static ✓ 2D 64
Method, 2019

13
 K. Sharma, R. Doriya

consideration and top four paper of each decade related Figure 2 represents the bar graph based on the survey
to path planning for robots, which were most cited by the paper mentioned in Table 1, and In the graph, the x-axis
researchers and author’s is taken into account for setting represents the year a block of 10 years is taken to draw
up a benchmark for further studies. Likewise, five differ- the graph, each block comprises of at least 4–5 most cited
ent blocks of 5 decades are prepared, starting from 1970 papers. The value at the top of each pillar is the aggregation
to 2019. Each paper considered for a respective decade is of citations papers has received during the year mentioned.
then thoroughly studied based on following points: sin- A pie chart has presented the graph in Fig. 2, it shows the
gle/multi-robot, static/dynamic environment, local/global percentage weight of contribution made by the papers, i.e.,
path planning, 2D/3D space, number of citation each paper on local/global path and single/multi-robot. The graph and
received. Distinguishing the paper based on these points pie chart is prepared on the basis of the papers mentioned
helps to find out that the focus of path planning algorithms in the Table 1.
that the emphasis was on which particular field and in that
time.
The first column of the Table mentions the name of the 3 Path planning algorithms
algorithm/technique, the citation adjacent to it refers to the
base paper of that algorithm considered for the study. The The next part of this intensive survey was to bring out a
next column shows the year of publication of that paper. detailed note of algorithms which attracted more attention
The next two-column is named as single robot/multi-robot, and had a broad impact on widening the field of robotics.
a checkmark sign is used in the entire Table to show whether Last few decades had witnessed that much contribution is
a particular algorithm is applicable for that column or not, made using nature-inspired algorithms. With the intention to
single robot/multi-robot column represents that the algo- throw light on nature-inspired algorithms, this paper presents
rithm, in particular, is being applied or used for a single the fundamental working principle of Ant Colony Optimiza-
robot application or a team of robots (more than a single tion, Bee Colony, Firefly Algorithm, Particle Swarm Opti-
robot). This concept again subdivides in its own like a robot mization, Bacteria Foraging, Cuckoo Search Algorithm and
or multi robots are deployed to accomplish a single task or BAT algorithm. The next section paper deal with some of
has to serve multiple objectives in an environment or simu- the prominent algorithms which are being observed multiple
lation. Next three columns represent the environments. The times and a good number of advancements made on that, this
definition of each type of environment is already discussed paper discusses A star (A*), Probabilistic Roadmap Planner
in the above section. The last column shows the number of (PRM), Rapidly Exploring Random Tree (RRT) and D star
citations each paper has received; this is one of the essential (D*) algorithm under notable contribution section. The next
and unique features this paper has considered, just to show section deals with some of the recent contributions on path
the impact and acceptance of any algorithm. planning for robots in the recent years, this section includes

Fig. 2  Graphical analysis of different areas of path planing techniques with its impact on each field and year wise impact on the respective field
(based on the research paper considered for this survey)

13
Path planning for robots: an elucidating draft

a detailed note on Parallel Evolutionary Artificial Field, It is found out by the local search procedures which are
Potential Field Approach, Adapting Animal Motion Attrib- being governed by the principle of Bee colony algorithm
utes, Heuristics Approaches in Path Planning. After that, the itself. Secondly, the minimization of the initial path is done
next section deals with some cloud computing platforms. in terms of its length and fluency by using Evolutionary
programming. In the ABC algorithm, bees change the food
position along with time in the population of food position.
4 Nature inspired algorithms Employed bees are the bees which excavate for the new
food position by using its current food position. When an
4.1 Ant colony employed bee could not enhance the food position in the
number of attempts, then it becomes a scout bee. Onlooker
The ant colony optimization (ACO) (Brand et al. 2010) is bees take the data from the employed bees about the quan-
inspired by real-world behaviour of biological ants. It is a tity of nectar amount present in food positions and visits
meta-heuristic approach. Here meta-heuristic denotes the that food position. The role of scout bees is to find a new,
ability to select, generate or find the solution of the optimi- randomly selected food position.
zation problem in the presence of incomplete information The evolutionary method starts by initializing the popu-
and limited computational capacity. It is an optimization lation. The next step is to unmasking the population to the
technique based on swarm intelligent systems to optimize environment and evaluate the fitness for each member. After
the problems like nonlinear objective functions and net- that change each parent and Evaluate parent and children.
work routing in telecommunication networks In this ACO Finally, pick out the members of the new population, and
algorithm, take a fixed size grid and define the initial and this follows until any condition is fulfilled.
the final position and also define the best point for the next ABC-EP planner exhibit better performance in the sce-
move. Pheromone (i.e. a secreted chemical factor that trig- narios without narrow corridors and less number of obsta-
gers a social response in a member of the same species) cles in a large group of environment.The proposed method
initialization plays a vital role in ACO algorithm. The phero- results in deriving paths in minimum time in problems with
mones in the networks are re-initialized after the obstacles spread out obstacles on the map better than PRM. It is also
are added. There are two types of re-initialization schemes deployed in multi-robot path planning (Bhattacharjee et al.
first is global initialization In this procedure, pheromones 2011; Liang and Lee 2015).
present in the complete region is reset to its initial phero-
mones level, while the second one is called as local ini- 4.3 Firefly
tialization where the gradient of pheromones is initialized
around the object. Global initialization can capture infor- In this algorithm, (Brand and Yu 2013) it can find an opti-
mation of the entire environment, but local initialization mal path in a dynamic environment. It also performs better
capture information of some limited range of environment. than Ant colony algorithm in terms of both path length and
With the help of that, we can find the shortest and collision- computational cost. It is similar to ACO with some more
free route in the grid network with avoiding all the obstacle features. Here fitness function is used for glow-worms. The
of various shapes and sizes. Some more work with recent firefly algorithm is based on three rules. First, all firefly is
amendments is being utilized in the area of path planning unisex, so they attract each other. Second, the attractiveness
like in autonomous marine vehicles (Xiong et al. 2019) and is the proposal to brightness level, so less bright firefly move
few more examples cited by Guan-Zheng et al. (2007) and towards high brighter firefly. Third, the brightness deter-
Mei et al. (2006). mined by the objective function to be optimized. In order
to find the shortest path, one firefly is put on the starting
4.2 Bee colony position, and other firefly placed on destination and put some
obstacle between them. After initialization, firefly moves
It is an optimization technique proposed by Contreras-Cruz and converge to the optimal solution. The performance of
et al. (2015) that triggers the look around the behaviour of the firefly algorithm is the same when the workspace size
honey bees and used for solving the parametric optimization is small, and the firefly algorithm performs better when the
problem. workspace size is increased. In two dimensional workspaces
It is the extension of the Genetic algorithm developed by for robot path planning, it is applied to find both the shortest
Fogel in which the structure of the program to improve is path and collision-free path (Fig. 3). Pavon et al. have pro-
fixed. It works in the makeup space. This proposed planning posed the firefly algorithm for solving the multi-objective
system accomplishes its task in two steps. The initial step problem of path planning for robots (Hidalgo-Paniagua et al.
is finding a collision-free path from source coordinates to 2017). Some more reviews regarding the firefly algorithm
the goal coordinates in the available configuration space. are presented by Ali et al. (2014).

13
 K. Sharma, R. Doriya

4.4 PSO 4.6 Cuckoo search

In this algorithm, (Masehian and Sedighizadeh 2010) A The cuckoo search algorithm is one of the highly proclaimed
particle swarm optimization (PSO) algorithm is used for algorithms for solving the problem of optimization. The
global path planning, and a probabilistic roadmap method algorithm was initially proposed as a metaheuristic search
(PRM) is used for obstacle avoidance. This algorithm is algorithm by Mohanty and Parhi (2016). The algorithm is
used in order to find the shortest path and smoothest path based on cuckoo’s egg-laying behaviour. In this process, the
for robots moving in an environment where many obsta- bird cuckoo opts a smart way to preserve its egg from getting
cles are present. This algorithm contains two components, mangled. It chooses other host bird’s nest to lay its egg on to
the first one is the PSO component which is used as the it. In the first step, each cuckoo is supposed to lay one egg.
global planner, and the second one is the modified PRM The working principle of cuckoo search follows a three-
component which is used as a local planner. The path step procedure, in the first step each cuckoo is supposed
smoothness is measured using two objective functions are to lay one egg at one instance, in the next step, to place its
incorporated in the PSO equation, the hypothetical lines egg, it chooses some other cuckoo’s nest, assuming that the
connecting two successive positions of robots and find the number of nests is fixed in number, the best nest among all
difference between the angles to find its goal. The PSO other nests which consist of high-quality egg proceeds for
based robot path planning algorithm is used to find the the next phase, the last step is to discover the egg by cuckoo
shortest path and the smoothest path. This algorithm gives is being done using the probability. This concept is utilized
a new method to combine the PSO and PRM component as a solution to the optimization problem and is also being
by combining four groups of nodes into one single popula- deployed in robot path planning.
tion. To solve the problem of path planning in a dynamic The robot begins from a point and moves in the direc-
environment is being proposed by Raja and Pugazhenthi tion of goal point in a partially known environment with
(2009) whereas to solve multi-objective, the solution is fix obstacles and optimal path length. When the robot
proposed by Gong et al. (2011). approaches near the obstacle, robot sensor is used to identify
the obstacles then the cuckoo search algorithm is triggered
to avoid the obstacles and get the best next position to stay
4.5 Bacteria foraging clear from collision with obstacles from the goal point, each
available solution is bounded with a numeric value and the
In this algorithm (Hossain and Ferdous 2015), in bacte- good quality nest egg will lead to next generation. The ben-
rial foraging technique navigation is used for correlation efit of using the CS algorithm is that the number of param-
of mobile robots. It has two main components localiza- eters to be adjusted is less compared to the genetic algorithm
tion and path planning. Localization means the ability to and particle swarm optimization. A detailed review of the
determine an accurate position, and path planning means cuckoo search algorithm is presented by Fister et al. (2014)
finding an optimal path for a computational purpose. In a (Fig. 4).
dynamic environment, the obstacle would be both static and
dynamic, but in a static environment, the obstacle would 4.7 BAT
be in a static position. Global path planning and local path
planning differs in terms of knowing the reference maps, in It is a metaheuristic algorithm presented by Gigras et al.
global path planning the details of the reference map resides (2015) for global optimization and was inspired by echolo-
with the robot, while in the latter one, details of reference cation behaviour of microbats which has the ability to vary
map remain unknown and it explores while traversing. So their pulse rates of emission and loudness. Microbats have
robots need the capability to build a map. In order to find the the ability to produce sonar waves with which they could
optimal path for a multi-robot, the environment should be encounter prey and obstacles. They emit the sonar waves
first constructed. The sensor is used to detect the obstacle, and wait for the reverberate of sound that comes back after
and both obstacle and final state can be dynamic. After each striking the prey are an obstacle. They have the ability to
step robot finds a feasible path by avoiding an obstacle. This differentiate their targets with the help of Doppler effect,
program runs until the goal has been found. It is very much by combining all their senses to encounter the prey and its
helpful from the resource point of view in finding the solu- navigation they only vary their loudness and frequency while
tion for path navigation. It uses a nonlinear fitness function their velocity, position and frequency remains unmodified
for making decisions. It has the feature of motion planning. In robot path planning robot, moves with angle theta and
For Multi-robot system bacteria foraging algorithm is pro- distanced and for each move, its position is updated until it
posed by Liang et al. (2013). Some more review is presented encounters an obstacle. When a robot encounters an obsta-
by Zafar and Mohanta (2018). cle, it pushes back some step and BAT algorithm initially

13
Path planning for robots: an elucidating draft

pulse rate, bat population, frequency, loudness, is defined minima related problems. Firefly algorithm, on the other
and distance is evaluated then the best position is selected hand, is capable of solving problems in a dynamic environ-
with respect to the minimum distance. After that frequency, ment. The algorithms discussed in this section are all helpful
velocity, current position is updated, and the local best in converging towards the solution at a good pace. There also
solution is found.this procedure continues for each obstacle exist many hybrid approaches to solve a particular type of
encountered. Solutions for path planning UCAV is being problem. Here in this, we tried to put some well known and
proposed by Wang et al. (2012, 2016). Recent modification well-adapted nature-inspired algorithms which are capable
is being reported by Saraswathi et al. (2018)(Fig. 5). of explaining various robots path planning issues.

4.8 Grey wolf
5 Notable contribution
Grey wolf optimization algorithm is based on the princi-
ple of leadership hierarchy and hunting mechanism of the This section deals with algorithms which has mostly talked
grey wolf. Kumar et al. described the grey wolf optimiza- about in the last few decades, several versions of these algo-
tion algorithm for unnamed aerial vehicles. It is used to rithms are present in the field of robot path planning. The
find the optimal path in the presence of dynamic obstacles reason to pick A*, PRM, RRT and D* is that it differs in
(Radmanesh and Kumar 2016). There are four types of grey their primary traversing mechanism while deriving optimal
wolves which are 𝛼 , 𝛽 , 𝛿 and 𝜔 , employed for simulating path from the source point to goal point. Table 2 presented
the leadership hierarchy. The purpose of this algorithm is in the paper shows the comparison of these four algorithms
not only to reach to its goal but also to avoid any obstacles in terms of path length, time taken and no of moves using
coming on the way of aircraft while approaching towards maze reference map.
the goal, also the obstacle in between are dynamic in nature.
UAV is equipped with ADS-B, which provides it with
5.1 A* Algorithm
the position of IAs. While entering into the periphery in an
unauthorized manner, the cell present near UAV would auto-
A* is one of the algorithms which is well known for find-
matically vary their load based on the probability values,
ing solutions with least probability of any collision in the
which indicates the risk of the collision inside the region.
given workspace. It is one of the recognized and accepted
The optimization process is achieved through a prede-
algorithms in many areas of pathfinding and graph traversal.
fined cost function. It is carried out using two modules the
A right amount of work has been done using this algorithm
first one includes the overall distance of the flight while the
(Myint 2018), different versions of A* are also being used
other one consists of the safety measures, which is framed
in many fields like in vessel path planning (Liu et al. 2019),
as the weight of the cell indicating the risk involved of col-
modified versions for robot navigation and many more
lision. Risk function can be defined as the summation of the
(Duchoň et al. 2014). A* entirely relies on the heuristics
complete path.
function for doing path planning, assuming that there is a
Weight of cell signifies the level of risk of collision of
graph with multiple nodes, and there is a need to reach from
that particular cell; it relies on the probability of collision
source to destination in the best optimal way, based on the
in three stages. The initial step is to find out the probabil-
heuristic function. A* performs at each step and selects the
ity of unauthorized inclusion of aircraft into the periphery,
node according to a value say x, which is the sum of y and z.
the second step is to calculate the probability of reaching
Based on the least value obtained of x, it proceeds further.
towards the collision area and the last step is to calculate the
probability of region where UAV is about the approach in x(n) = y(n) + z(n) (1)
few steps. Alpha is the best solution and also is the outcome
of the optimization process. Advantages of this algorithm Where n is the last selected node on the path, y(n) is the
are that it provides an effective optimal solution for path value of the path obtained from the last value, and z(n) is the
planning for different flight missions as compared to other heuristic function which calculates the minimum path cost
algorithms. A detailed review of Grey wolf algorithm is pre- from n to the destination.
sented by Faris et al. (2018) while the recent modification is
reported by Heidari and Pahlavani (2017)(Fig. 6). 5.2 PRM
Nature-inspired algorithms are grabbing more attention
of researchers for solving the problem related to optimiza- PRM works on the fundamental law for constructing paths.
tion. Cuckoo search is well known for solving local minima To traverse from source point to goal point in the given
associated issues, whereas the ant colony optimization is workspace PRM constructs a path using random points from
having the disadvantage of getting trapped into the local the workspace. There can be several methods to generate

13
 K. Sharma, R. Doriya

a random point in a given specific area, python’s random of some unique features as it learns from its past execution,
number generator for generating points is the one which and the second-best feature is that it looks for the goal quite
can be used (Kavraki et al. 1998). A sufficient number of fast as compared to the other algorithms. It makes certain
points need to be generated for building a valid path between assumptions whether there is any obstacle in the path or
the source and goal, lacking for it may result in a fractured not based on its learning and experience and approaches
graph which cannot be used for traversing. After selecting towards the goal at a rapid pace. And all of a sudden, when
any random point, the algorithm frames cluster and adds all its assumption goes wrong, it adds up the information of
the nearby points into the cluster; it keeps on making clus- newly observed obstacles in its database and then replans
ters of points based on the random samples obtained. Two the new path. A different version (Stentz et al. 1995) of the
crucial things it performs are that, while framing clusters it D* algorithm has been proposed in the past to overcome
checks whether all the points belong to that specific radius this problem. The incremental heuristic search algorithm is
selected previously or not, second these clusters (nodes) are one which has an excellent contribution to solve the prob-
added with increasing distance to reach towards goal. There lem. Some well-known application benefited by D star are
are two essential phases under which the working of PRM autonomous vehicle navigation and for mobile robots.
relies upon, query phase and construction phase. The initial
point is given as input to the query phase based on which it
selects the next valid point from a given number of points 6 Recent contribution
available in the workspace. The next phase is the construc-
tion phase, where a valid graph is built based on the random This section gives the detail of algorithms which were most
points. Dijkstra’s algorithm is used for selecting the shortest recently being applied in the area of path planning for robots
path among the valid paths obtained in the given workspace and is being extensively accepted by many applications of
or configuration area (Geraerts and Overmars 2004). robotics. Four algorithm is considered for discussion in the
following subsection.
5.3 RRT​
6.1 Parallel evolutionary artificial field
It is a well-known algorithm in the area of path planning
(LaValle 1998; LaValle and Kuffner 2000). For finding a Parallel evolutionary artificial field (Montiel et al. 2015)
path using the RRT algorithm, there must be a start point and evolved because the methods prior to this were using the
goal point given in the workspace. The start point is given concept of the potential field which failed when dynamic
as input to the system based on which it starts building the obstacles are present. This approach is used in case of com-
tree until the last node or goal node is reached. This method plex real-world situations with dynamic obstacles. It ensures
is well known for fastly building its tree for finding paths. controllability in a dynamic environment which is not pro-
Starting from the initial node, it starts creating a random vided by the electrostatic potential field approach. This par-
node in the workspace and based on the distance between ticular approach is capable of giving solutions to many path
the nodes. It selects the node which is having a minimum planning problems be it a local path planning to global path
distance from this random node in the tree. The distance planning, it also performs very efficiently in case of on-line
between the nodes is already predefined and is called a step global path planning problems, whereas, the electrostatic
size. One by one, these nodes are added to the tree, and the potential approach is restricted to only some specific area of
process keeps on repeating until the goal point of avoiding path planning. The parallel evolutionary artificial potential
all obstacles (Karaman et al. 2011). The whole process, in field method helps the single robot in identifying the path
the end, forms a tree-like structure that’s why it is called from the initial state to goal state where the obstacles are
as rapidly exploring random tree algorithm. A smooth path present in a dynamic environment. This approach uses the
is traced for traversal from source to goal for robots in the concept of a potential field of charged particles. This method
given workspace. Many other extended versions of RRT are ensures a faster and effective path for the robot. Considering
available for different applications (Hirakawa et al. 2019). the obstacle to be present in L-shaped then in APF method
due to the repulsive methods the robot follows the longest
5.4 D* Algorithm path whereas in this method the robot can move along the
edges of the obstacles thereby providing a better path in the
D star (Ferguson and Stentz 2007) is one of the incremental shortest time.
search problem frequently used for solving the path planning
problem for robots. It was first introduced in the year 1994
by Anthony stentz, which was actually the advanced version
of A* that time or is also called as dynamic A*. It consists

13
Path planning for robots: an elucidating draft

6.2 Potential field approach is numerous membership function which is being preferred

and is suitable for solving many problems. Some of the well-
The method of lach is applied when the obstacles are present known techniques include the concept and model of ANN,
at various places. This method uses a potential function for model Bio-inspired algorithms, a combination of two or
every obstacle (Bayat et al. 2018). The problem of path plan- more approaches, fuzzy logic and many more. One of the
ning for single robots is present in an environment where high points of this heuristic approach is that it is capable of
obstacles are scattered. In order to obtain an optimal path, copying human tendency and adds emotional intelligence
the concept of the potential field of the charged particles is to the approach; also, it learns from its experience. In recent
used. In this approach, an individual potential function is times bio-memetic algorithms have grabbed the attention
allotted to the individual obstacles; all the obstacles are scat- for robot navigation.
tered in the environment are integrated into a scalar potential The algorithms like GA, PSO and ACO introduce the
surface. An optimal path is basically obtained by following applications of robot path planning. One of core method
the shortest path and also avoiding obstacles. The key fea- known as Adaptive fuzzy logic is used for solving robots
ture of this approach is that the size, position, colour of the path planning problem. The adaptive fuzzy logic control-
obstacle does not influence this approach. If the informa- ler allows and tracks and minimize errors during trajectory
tion about the environment is not known; it can be obtained execution. The five-phase of the proposed algorithm for path
by digital image processing, then based on the intensity of planning and obstacle avoidance include: phase 1—image
potential function for each obstacle exert the repulsive forces capturing, phase 2—compute three area map which includes
and using this the robot reaches the goal state from the initial dangerous area, forbidden area, safe area, phase 3—compute
state. Some of the applications which are being benefitted a collision-free path from source to target using genetic algo-
by this approach are; dispatch of goods and materials to the rithm (smoothed path), phase 4—carry out the smoothed
warehouse in the manufacturing unit and also to organize path using a fuzzy logic controller, phase 5—if the target
them, handling the places where human involvement is risky, is found, then it stops, if the environment changes the algo-
guiding old helping age people. rithm, begins from the first phase. The adaptive fuzzy logic
controller updates the velocities of the robot (right and left
6.3 Adapting animal motion attributes velocities) quickly using wireless communication so that the
errors converge to zero.
In this approach, the proposed method helps human–robot
interactions (Kovács et al. 2016). It is well proficient in
performing in-line navigation when executed in dynamic 7 Path planning for robots using clouds
environments. People and insects live together, which helps
humans to interact and estimate insect movements easily. Various challenges exist for service robots in unstructured
The algorithm proposed based on this concept is the BUG environments (Moreno et al. 2013) like the inability to
algorithm. This method has been developed to promote effectively interact and cope up with the unstructured envi-
human–robot interactions. The condition here is that if the ronment, this lead in creating the service robots which are
robot and potential field attain local minimum then, in that capable of handling human–related tasks that too with better
case, the robot gets stopped and does not reach the final state. accuracy and reliability (Soliman et al. 2013). Typically the
This is the local minimum problem found in APF method. In robots possess less computation power and are inefficient
this mechanism, at one instance the AFP method is substi- in handling big tasks. So, there is a requirement to offload
tuted by the BUG algorithm, and it saves the potential value the computational complexity of the robot to some other
achieved by the local minimum at that instance. Following means. The cloud-based robot is a promising solution to the
this algorithm, the robot approaches the goal. After that, problems with small robots as it helps in resource sharing
the BUG algorithm converts back to APF when the poten- parallel computation and cost reduction. Some well known
tial of actual positions is lower than the potential that saved and available cloud platforms include names like Microsoft
in a local minimum. More similar approaches like genetic Azure, Zoho, Open-Nebula, Aneaka, IBM, Amazon etc.
algorithm and adaptive fuzzy-logic control are used for path Here we are including Open Stack and Google Cloud in dis-
planning for robots (Bakdi et al. 2017). cussion and tried Google Cloud for implementing path plan-
ning problem. The reason for selecting the Google Cloud
6.4 Heuristics approaches in path planning Computing Platform is that it is very economical from the
usage point of view and for initial level experiments, it is
Heuristic functions (Mac et al. 2016) provide a solution less complicated and user-friendly.
when it becomes difficult to reach the exact solution. It Rapid Elasticity is one of the essential features which
explores the considerable gap between ‘0’ and ‘1’. There makes the cloud more acceptable for many applications, The

13
 K. Sharma, R. Doriya

requirement in terms of processing capabilities or storage is capable of providing services to stimulate the business
can be quickly provisioned and scaled in and out with the responsiveness, sharing of available resource so that they
minimal effort. Deployment of robots in some problematic can be utilized in an optimum way, and is highly elastics in
situation requires a sudden change in the processing require- nature which is also an excellent aesthetic factor for some of
ment, which becomes complex when dealing with the indi- the businesses (He et al. 2019; Borsatti et al. 2018). Some
vidual robot. This issue can be easily handled with the use more cloud computing platforms are being discussed by
of cloud computing platforms. Ruda et al. for robotics (Haidegger et al. 2019).
Reliability is another fundamental aspect which is con-
sidered in any technologies. Reliability can be understood as 7.2 Google cloud platform
the mean time between failure and repair. The percentage of
this parameter should be high for getting it acceptable by any Google cloud computing platform is one of the most popu-
application. Cloud computing platform ensures this feature lar computing platforms which provides services and can
which makes it more lucrative to adopt it. Cloud platforms be a good solution for some robotics application. Here in
are very tolerant as the presence of multiple servers supports this paper, we have also implemented a path planning prob-
it to provide an error-free service on demand. lem using google cloud Garraghan et al. (2013). We have
Response time is another metric which should be taken used it as Infrastructure as a Service to execute the path
care of, as the location of robots from the server and the planning problem. The system architecture that is proposed
exchange of data or information taking place between them to cloud-based path planning system consists of three lay-
with respect to time is essential to read. Reliability is one of ers, server layer, a cloud engine layer(provides lightweight
the parameters which is to be observed in every experiment, virtual machine called container to execute authorized pro-
and its values vary from application to application. grams uses rapyuta) and a client robot layer. To get maxi-
Efficiency or throughput is another crucial factor which mum utilization of computational resources Path Planner
means the performance of a task by a computing service for is implemented using multithreading. Local computational
a particular interval of time. From the robotics prospect, it Power, node properties and network bandwidth are the three
would be on a positive side as to handle and monitor multi- criteria which help us to understand whether it is better to
ple robots will be more accessible when they are governed run a node in the cloud or robot (Mishra et al. 2010; Lam and
centrally. Single robots scenarios are required to test inde- Lam 2014). In this paper service of Google cloud platform
pendently for specific applications to check the performance is utilized as IaaS (Infrastructure as a Service) to carry out
of efficiency. path planning problem using A* algorithm.
Apart from the above four factors, there are several other Figure 7 shows the result obtained, Map-1 to Map-4 in
factors which makes cloud computing platform more accept- the first row are the input reference maps and the second row
able. The reason to move robots path planning to cloud is shows the respective output of each map after implementing
that in term of using robots for many applications like in A* algorithm over it, path length and path time are calcu-
uneven terrain, or in some hazardous situation, it is required lated and displayed at the bottom of the respective outputs.
to deal remotely with the physical robots, and the require- Google cloud computing platform is used to experiment.
ment of the system fluctuates as per the time. Using the
cloud in such cases will be very much facilitating for those
applications.

7.1 OpenStack

Open stack was founded by NASA and Rack space in 2010.

Open stack is free and open-source cloud computing soft-
ware platform which provide users methods and support
to deploy virtual machines in a remote environment. Open
stack is an open-source project by NASA that aims to ten-
der the cloud-based services with simplicity, scalability and
rich in functionality. It is also being used in various applica-
tions of robotics and is being suggested and recommended
by many researchers for mobile robots (Aguiar et al. 2014;
Huang et al. 2016; Dyumin et al. 2015). The open stack can
be used if one wants to reduce the cost per virtual machine
and thus reduces overall infrastructure costs. OpenStack Fig. 3  Diagram representing working of Firefly algorithm

13
Path planning for robots: an elucidating draft

Table 2  Comparison of results obtained on the reference maps using

path planning algorithms

Reference map Path planning Path Time taken (s) No. of

algorithms length moves
(units) (units)

Maze A* 351 143 19

Maze PRM 371 12 24
Maze RRT​ 451 227 440
Maze D* 442 178 436

8 Conclusion

In this paper, we have done an extensive survey of the algo-

Fig. 4  Diagram representing working of Cuckoo search algorithm
rithms used for robot path planning. A detailed analysis is
being done on the various problems and limitations related
to path planning. We had tried to cover all the prominent
path planning algorithm as much possible in this paper. To
put it in the right perspective, the problem of path planning
and its domain, the paper focused on the evolution of path
planning algorithms citing its impact on different application
areas. Along with that, the classification of different working
environments is also presented. It is evident that initially, the
concept of robot path planning is primarily consumed by the
manufacturing and production-based industry and later on
grabbed the attention by many other sections of the industry.
From the evolution perspective, it seems that the path
planning problem for robots witnessed a boom during the
industrialization phase across the world. Later on, it was a
bit dormant while the next decade again took a leap when
the nature-inspired algorithm start commencing in the
research field, and in a very short due course of time, it was
Fig. 5  Diagram representing working of BAT Algorithm
widely accepted and deployed for solving the problem of
optimization. It helped in optimizing the effort being put for
solving the issues related to the concerned domain, which
stimulated its applications and usage. Several amendments
and up-gradation brought out by many researchers using
nature-inspired algorithms for their work.
The paper first tried to put the summary of the evolution
of path planning algorithms. Then the effort was made to
classify it based on the environments and respective prob-
lem domain, discussing some significant contribution, most
recent contribution the paper next focused on the recent
technologies which could be the future prospect of robot’s
path planning and the gist was to bring attention towards
cloud platforms.
Analyzing the evolution, classification and recent trends
this paper try to forecast and presumes that the coming era
will be of cloud, and using cloud computing platform will
give a synthetic boost to the robot path planning problems.
Cloud computing platform can easily handle and coordinate
Fig. 6  Diagram representing working of Grey wolf optimization algo- a cluster of the robot (multi-robot) system. Also, it will ease
rithm the computation problem of robots as that can be handled

13
 K. Sharma, R. Doriya

Fig. 7  Implementation of A* algorithm for robot Path Planning algorithm using Google Cloud Platform

by the cloud server, which will be much more efficient and using genetic algorithm and adaptive fuzzy-logic control. Robot.
capable of handling a large volume of task. So, before actu- Auton. Syst. 89, 95–109 (2017)
Barraquand, J., Langlois, B., Latombe, J.-C.: Numerical potential
ally concluding and going for a recommendation, we have field techniques for robot path planning. IEEE Trans. Syst. Man.
implemented A* algorithm for robot path planning in four Cybern. 22(2), 224–241 (1992)
distinct reference maps using Google Cloud. In the last, as Bayat, F., Najafinia, S., Aliyari, M.: Mobile robots path planning: elec-
a remark and recommendation, the paper tries to attract the trostatic potential field approach. Expert Syst. Appl. 100, 68–78
(2018)
attention of researchers towards clubbing this new technol- Bhattacharjee, P., Rakshit, P., Goswami, I., Konar, A., Nagar, A.K.:
ogy with that of robot path planning. Blending of cloud Multi-robot path-planning using artificial bee colony optimiza-
computing platform with the path planning algorithms will tion algorithm. In: 2011 IEEE Third World Congress on Nature
be the reason for wide acceptability of robots in many more and Biologically Inspired Computing, pp. 219–224 (2011)
Borsatti, D., Davoli, G., Cerroni, W., Contoli, C., Callegati, F.: Per-
application areas in the coming time. formance of service function chaining on the openstack cloud
platform. In: 2018 14th International Conference on Network
and Service Management (CNSM), pp. 432–437 (2018)
Brand, M., Masuda, M., Wehner, N., Yu, X.-H.: Ant colony optimi-
zation algorithm for robot path planning. In: 2010 IEEE Inter-
References national Conference On Computer Design and Applications,
vol. 3, pp. V3–436 (2010)
Aguiar, R.L., Gomes, D., Barraca, J.P., Lau, N.: Cloudthinking as an Brand, M., Yu, X.-H.: Autonomous robot path optimization using
intelligent infrastructure for mobile robotics. Wirel. Pers. Com- firefly algorithm. In: 2013 IEEE International Conference on
mun. 76(2), 231–244 (2014) Machine Learning and Cybernetics, vol. 3, pp. 1028–1032
Ali, N., Othman, M.A., Husain, M.N., Misran, M.H.: A review of fire- Châari, I., Koubaa, A., Bennaceur, H., Trigui, S., Al-Shalfan, K.:
fly algorithm. ARPN J. Eng. Appl. Sci. 9(10), 1732–1736 (2014) Smartpath: A hybrid aco-ga algorithm for robot path planning.
Artuñedo, A., Godoy, J., Villagra, J.: A primitive comparison for In: IEEE Congress on Evolutionary Computation, pp. 1–8
traffic-free path planning. IEEE Access 6, 28801–28817 (2018) (2012)
Autere, A., Lehtinen, J.: A multiresolution a* method for robot path Connolly, C. I., Burns, J. B., Weiss, R.: Path planning using laplace’s
planning. WIT Trans. Inf. Commun. Technol. (1970). https​://doi. equation. In: Proceedings of IEEE International Conference on
org/10.2495/AI970​021 Robotics and Automation, IEEE, pp. 2102–2106 (1990)
Bakdi, A., Hentout, A., Boutami, H., Maoudj, A., Hachour, O., Bou- Contreras-Cruz, M.A., Ayala-Ramirez, V., Hernandez-Belmonte, U.H.:
zouia, B.: Optimal path planning and execution for mobile robots Mobile robot path planning using artificial bee colony and evo-
lutionary programming. Appl. Soft Comput. 30, 319–328 (2015)

13
Path planning for robots: an elucidating draft

Das, P.K., Behera, H.S., Panigrahi, B.K.: A hybridization of an Hirakawa, T., Yamashita, T., Fujiyoshi, H.: Scene context-aware rap-
improved particle swarm optimization and gravitational search idly-exploring random trees for global path planning. In: 2019
algorithm for multi-robot path planning. Swarm Evol. Comput. IEEE International Conference on Pervasive Computing and
28, 14–28 (2016) Communications Workshops (PerCom Workshops), pp. 608–613
Drake, D., Koziol, S., Chabot, E.: Mobile robot path planning with a (2019)
moving goal. IEEE Access 6, 12800–12814 (2018) Hossain, M.A., Ferdous, I.: Autonomous robot path planning in
Duan, H., Qiao, P.: Pigeon-inspired optimization: a new swarm intel- dynamic environment using a new optimization technique inspired
ligence optimizer for air robot path planning. Int. J. Intell. Com- by bacterial foraging technique. Robot. Auton. Syst. 64, 137–141
put. Cybern. 7(1), 24–37 (2014) (2015)
Duchoň, F., Babinec, A., Kajan, M., Beňo, P., Florek, M., Fico, T., Huang, C., Zhang, L., Liu, T., Zhang, H. Y.: A control middleware for
Jurišica, L.: Path planning with modified a star algorithm for a cloud robotics. In: 2016 IEEE International Conference on Infor-
mobile robot. Procedia Eng. 96, 59–69 (2014) mation and Automation (ICIA), pp. 1907–1912 (2016)
Dyumin, A., Puzikov, L., Rovnyagin, M., Urvanov, G., Chugunkov, I.: Kambhampati, S., Davis, L.: Multiresolution path planning for
Cloud computing architectures for mobile robotics. In: IEEE NW mobile robots. IEEE J. Robot. Autom. 2(3), 135–145 (1986)
Russia Young Researchers in Electrical and Electronic Engineer- Karaman, S., Walter, M.R., Perez, A., Frazzoli, E., Teller, S.: Any-
ing Conference (EIConRusNW), pp. 65–70 (2015) time motion planning using the RRT. In: 2011 IEEE Interna-
Faris, H., Aljarah, I., Al-Betar, M.A., Mirjalili, S.: Grey wolf optimizer: tional Conference on Robotics and Automation, pp. 1478–1483
a review of recent variants and applications. Neural Comput. (2011)
Appl. 30(2), 413–435 (2018) Karaman, S., Frazzoli, E.: Sampling-based algorithms for optimal
Ferguson, D., Stentz, A.: Field D*: an interpolation-based path plan- motion planning. Int. J. Robot. Res. 30(7), 846–894 (2011)
ner and replanner. In: Thrun, S., Brooks, R., Durrant-Whyte, H. Kavraki, L.E., Svestka, P., Latombe, J.-C., Overmars, M.H.: Proba-
(eds.) Robotics research, pp. 239–253. Springer, Berlin, Heidel- bilistic roadmaps for path planning in high-dimensional con-
berg (2007) figuration spaces. IEEE Trans. Robot. Autom. 12(4), 566–580
Fister, I., Yang, X.-S., Fister, D.: Cuckoo search: a brief literature (1996)
review. In: Yang, X.S. (ed.) Cuckoo search and firefly algorithm, Kavraki, L.E., Kolountzakis, M.N., Latombe, J.-C.: Analysis of proba-
pp. 49–62. Springer, Cham (2014) bilistic roadmaps for path planning. IEEE Trans. Robot. Autom.
Garcia, M.P., Montiel, O., Castillo, O., Sepúlveda, R., Melin, P.: Path 14(1), 166–171 (1998)
planning for autonomous mobile robot navigation with ant colony Kehoe, B., Patil, S., Abbeel, P., Goldberg, K.: A survey of research
optimization and fuzzy cost function evaluation. Appl. Soft Com- on cloud robotics and automation. IEEE Trans. Autom. Sci. Eng.
put. 9(3), 1102–1110 (2009) 12(2), 398–409 (2015)
Garraghan, P., Townend, P., Xu, J.: An analysis of the server charac- Khatib, O.: Real-time obstacle avoidance for manipulators and mobile
teristics and resource utilization in google cloud. In: 2013 IEEE robots. In: Cox, I.J., Wilfong, G.T. (eds.) Autonomous robot vehi-
International Conference on Cloud Engineering (IC2E), pp. cles, pp. 396–404. Springer, New York, NY (1986)
124–131 (2013) Kovács, B., Szayer, G., Tajti, F., Burdelis, M., Korondi, P.: A novel
Geraerts, R., Overmars, M.H.: A comparative study of probabilistic potential field method for path planning of mobile robots by adapt-
roadmap planners. In: Boissonnat, J.D., Burdick, J., Goldberg, K., ing animal motion attributes. Robot. Autonom. Syst. 82, 24–34
Hutchinson, S. (eds.) Algorithmic Foundations of Robotics V, pp. (2016)
43–57. Springer, Berlin, Heidelberg (2004) Kuffner, J. J., LaValle, S. M.: Rrt-connect: An efficient approach to
Gigras, Y., Gupta, K., Choudhury, K.: A comparison between bat algo- single-query path planning. In: Proceedings 2000 ICRA. Millen-
rithm and cuckoo search for path planning. Int. J. Innov. Res. nium Conference, IEEE International Conference on Robotics
Comput. Commun. Eng. 3(5), 4459–4466 (2015) and Automation. Symposia Proceedings (Cat. No. 00CH37065),
Gong, D.-W., Zhang, J.-H., Zhang, Y.: Multi-objective particle swarm vol. 2, pp. 995–1001 (2000)
optimization for robot path planning in environment with danger Lam, M.-L., Lam, K.-Y.: Path planning as a service ppaas: Cloud-based
sources. J. Comput. 6(8), 1554–1561 (2011) robotic path planning. In: 2014 IEEE International Conference on
Guan-Zheng, T., Huan, H., Sloman, A.: Ant colony system algorithm Robotics and Biomimetics (ROBIO 2014), pp. 1839–1844 (2014)
for real-time globally optimal path planning of mobile robots. LaValle, S.M., Kuffner Jr, J.J.: Rapidly-exploring random trees: pro-
Acta Autom. Sin. 33(3), 279–285 (2007) gress and prospects. In: Algorithmic and Computational Robotics:
Haidegger, T., Galambos, P., Rudas, I.: Robotics 4.0-are we there yet? New Directions, pp. 293–308 (2000)
In: INES 2019, IEEE 23rd International Conference on Intelligent LaValle, S.M.: Rapidly-exploring random trees: A new tool for path
Engineering Systems, Budapest, Magyarország (2019) planning
Han, W.-G., Baek, S.-M., Kuc, T.-Y.: Genetic algorithm based path Liang, J.-H., Lee, C.-H.: Efficient collision-free path-planning of mul-
planning and dynamic obstacle avoidance of mobile robots. In: tiple mobile robots system using efficient artificial bee colony
IEEE International Conference on Systems, Man, and Cyber- algorithm. Adv. Eng. Softw. 79, 47–56 (2015)
netics, Computational Cybernetics and Simulation, vol. 3, pp. Liang, X.-D., Li, L.-Y., Wu, J.-G., Chen, H.-N.: Mobile robot path
2747–2751 (1997) planning based on adaptive bacterial foraging algorithm. J. Cent.
He, M.,Alba, M.A., Mansour, E., Kellerer, W.: Evaluating the control South Univ. 20(12), 3391–3400 (2013)
and management traffic in openstack cloud with SDN. In: 2019 Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the
IEEE International Conference on High Performance Switching traveling-salesman problem. Oper. Res. 21(2), 498–516 (1973)
and Routing (HPSR) (2019) Liu, H., Ma, J., Huang, W.: Sensor-based complete coverage path plan-
Heidari, A.A., Pahlavani, P.: An efficient modified grey wolf optimizer ning in dynamic environment for cleaning robot. CAAI Trans.
with lévy flight for optimization tasks. Appl. Soft Comput. 60, Intell. Technol. 3(1), 65–72 (2018)
115–134 (2017) Liu, C., Mao, Q., Chu, X., Xie, S.: An improved a-star algorithm con-
Hidalgo-Paniagua, A., Vega-Rodríguez, M.A., Ferruz, J., Pavón, N.: sidering water current, traffic separation and berthing for vessel
Solving the multi-objective path planning problem in mobile path planning. Appl. Sci. 9(6), 1057 (2019)
robotics with a firefly-based approach. Soft Comput. 21(4), 949–
964 (2017)

13
 K. Sharma, R. Doriya

Mac, T.T., Copot, C., Tran, D.T., De Keyser, R.: Heuristic approaches Computation. CEC00 (Cat. No. 00TH8512), vol. 1, pp. 256–263
in robot path planning: a survey. Robot. Auton. Syst. 86, 13–28 (2000)
(2016) Wagner, G., Choset, H.: M*: A complete multirobot path planning
Martin, P., Del Pobil, A.: Application of artificial neural networks to algorithm with performance bounds. In: 2011 IEEE/RSJ Inter-
the robot path planning problem. WIT Trans. Inf. Commun. Tech- national Conference on Intelligent Robots and Systems, pp.
nol. 6, 73–80 (1970). https​://doi.org/10.2495/AI940​061 3260–3267 (2011)
Masehian, E., Sedighizadeh, D.: A multi-objective pso-based algorithm Wang, G., Guo, L., Duan, H., Liu, L., Wang, H.: A bat algorithm with
for robot path planning. In: 2010 IEEE International Conference mutation for ucav path planning. Sci. World J. 2012, 418946
on Industrial Technology, pp. 465–470 (2010) (2012). https​://doi.org/10.1100/2012/41894​6
Mei, H., Tian, Y., Zu, L.: A hybrid ant colony optimization algorithm Wang, G.-G., Chu, H.E., Mirjalili, S.: Three-dimensional path planning
for path planning of robot in dynamic environment. Int. J. Inf. for ucav using an improved bat algorithm. Aerosp. Sci. Technol.
Technol. 12(3), 78–88 (2006) 49, 231–238 (2016)
Mishra, A.K., Hellerstein, J.L., Cirne, W., Das, C.R.: Towards charac- Warren, C.W.: Global path planning using artificial potential fields. In:
terizing cloud backend workloads: insights from google compute Proceedings of IEEE 1989 International Conference on Robotics
clusters. ACM SIGMETRICS Perform. Eval. Rev. 37(4), 34–41 and Automation, pp. 316–321 (1989)
(2010) Xiong, C., Chen, D., Lu, D., Zeng, Z., Lian, L.: Path planning of mul-
Mohanty, P.K., Parhi, D.R.: Optimal path planning for a mobile robot tiple autonomous marine vehicles for adaptive sampling using
using cuckoo search algorithm. J. Exp. Theor. Artif. Intell. 28(1– voronoi-based ant colony optimization. Robot. Auton. Syst. 115,
2), 35–52 (2016) 90–103 (2019)
Montiel, O., Sepúlveda, R., Orozco-Rosas, U.: Optimal path planning Zafar, M.N., Mohanta, J.: Methodology for path planning and opti-
generation for mobile robots using parallel evolutionary artificial mization of mobile robots: a review. Procedia Comput. Sci. 133,
potential field. J. Intell. Robot. Syst. 79(2), 237–257 (2015) 141–152 (2018)
Moreno, I.S., Garraghan, P., Townend, P., Xu, J.: An approach for char- Zhang, W., Gong, X., Han, G., Zhao, Y.: An improved ant colony algo-
acterizing workloads in google cloud to derive realistic resource rithm for path planning in one scenic area with many spots. IEEE
utilization models. In: 2013 IEEE Seventh International Sympo- Access 5, 13260–13269 (2017)
sium on Service-Oriented System Engineering, pp. 49–60 (2013) Zhu, D., Latombe, J.-C.: New heuristic algorithms for efficient hier-
Myint, H.: Development of robot navigation system with collision free archical path planning. Stanford Univ CA Dept of Computer SD,
path planning algorithm. Mach. Learn. Res. 3(3), 60 (2018) Tech. rep. (1989)
Pandey, A., Parhi, D.R.: Optimum path planning of mobile robot in
unknown static and dynamic environments using fuzzy-wind Publisher’s Note Springer Nature remains neutral with regard to
driven optimization algorithm. Def. Technol. 13(1), 47–58 (2017) jurisdictional claims in published maps and institutional affiliations.
Radmanesh, M., Kumar, M.: Grey wolf optimization based sense and
avoid algorithm for uav path planning in uncertain environment
using a bayesian framework. In: 2016 IEEE International Confer-
ence on Unmanned Aircraft Systems (ICUAS), pp. 68–76 (2016) Kaushlendra Sharma received his
Raja, P., Pugazhenthi, S.: Path planning for mobile robots in dynamic M. Tech in Computer Technol-
environments using particle swarm optimization. In: 2009 IEEE ogy from National Institute of
International Conference on Advances in Recent Technologies in Technology Raipur in 2011 and
Communication and Computing, pp. 401–405 (2009) is currently pursuing PhD from
Saraswathi, M., Murali, G.B., Deepak, B.: Optimal path planning of NIT Raipur, His research focuses
mobile robot using hybrid cuckoo search-bat algorithm. Procedia on Cloud Computing and
Comput. Sci. 133, 510–517 (2018) Robotics.
Saska, M., Macas, M., Preucil, L., Lhotska, L.: Robot path planning
using particle swarm optimization of ferguson splines. In: 2006
IEEE Conference on Emerging Technologies and Factory Auto-
mation, pp. 833–839 (2006)
Soliman, M., Abiodun, T., Hamouda, T., Zhou, J., Lung, C.-H., Smart
home: Integrating internet of things with web services and cloud
computing. In: IEEE 5th International Conference on Cloud Com-
puting Technology and Science, vol. 2, pp. 317–320 (2013)
Stentz, A.: The focussed d* algorithm for real-time replanning. In: Rajesh Doriya received his PhD
IJCAI, vol. 95, pp. 1652–1659 (1995) from Indian Institute of Informa-
Sun, P., Yu, Z.: Tracking control for a cushion robot based on fuzzy tion Technology Allahabad. He
path planning with safe angular velocity. IEEE/CAA J. Autom. is currently working as Assistant
Sin. 4(4), 610–619 (2017) Professor in the Department of
Tharwat, A., Elhoseny, M., Hassanien, A.E., Gabel, T., Kumar, A.: Information Technology at NIT
Intelligent bézier curve-based path planning model using chaotic Raipur. His research area
particle swarm optimization algorithm. Clust. Comput. 22(2), includes Distributed & Cloud
4745–4766 (2019) Computing, Robotics & Artifi-
Thompson, A.M.: The navigation system of the jpl robot, pp. 77–20. cial Intelligence.
JPL Publication, California (1977)
Vadakkepat, P., Tan, K. C., Ming-Liang, W.: Evolutionary artificial
potential fields and their application in real time robot path plan-
ning. In: IEEE Proceedings of the 2000 Congress on Evolutionary

13