PALADYN Journal of Behavioral Robotics

Research Article · DOI: 10.2478/s13230-012-0013-4 · JBR · 3(1) · 2012 · 23-34

Robot Path Planning using Dynamic Programming with

Accelerating Nodes

Rahul Kala∗ , Anupam Shukla† ,

Abstract
Ritu Tiwari‡
We solve the problem of robot path planning using Dynamic Programming (DP) designed to perform well in case
of a sudden path blockage. A conventional DP algorithm works well for real time scenarios only when the update
Soft Computing and Expert System Laboratory,
frequency is high i.e. changes can be readily propagated. In case updates are costly, for a sudden blockage the
Indian Institute of Information Technology and robot continues moving along the wrong path or stands stationary. We propose a modified DP that has nodes with
Management Gwalior, additional processing (called accelerating nodes) to enable di erent segments of the map to become informed about
Gwalior, Madhya Pradesh-474010, India the blockage rapidly. We further quickly compute an alternative path in case of a blockage. Experimental results
verify that usage of accelerating nodes makes the robot follow optimal paths in dynamic environments.

Received 2011/09/11
Keywords
Accepted 2012/01/26
path planning · dynamic programming · artificial neural networks · A* · robotics · heuristics

1. Introduction points (problem) is computed based on the pre-computed distance to

nearer points (sub-problem). In this way the entire problem is divided
Robot Path Planning is a much studied problem in the field of robotics. into sub-problems, with a unit sub-problem as the distance of the goal
The problem is much harder to solve for dynamic maps, which have from itself, which is zero.
larger issues than static path planning, due to a constantly changing We use a recurrence relation to show the relation between a prob-
map and the real time nature of the algorithm. As a result many ap- lem and its sub-problems. Iterative solutions of the recurrence rela-
proaches primarily work only in static environments. In dynamic maps, tion, starting from the smallest sub-problem and proceeding towards
the path of the robot may frequently be completely obstructed by obsta- the higher sub-problems, may result in the solution of the main prob-
cles. In such a case a blockage is said to have occurred and the robot lem. In the problem of path planning we calculate the shortest distance
needs to re-plan the path. Blockage is a still harder problem in robotics, from any point to destination at iteration i+1 using the shortest distance
as there may be few similarities in the optimal path after blockage to the of neighboring points at iteration i. Every time we update the shortest
one prior to blockage. This fundamentally means re-planning the entire path of a point, we even update the source from which this smallest
robotic path. For most algorithms this re-planning may be very time path was found. This helps in building up the path that corresponds
consuming. to the smallest path length. It can be easily shown that for all points,
Our motivation is to study the problem of path planning in case of block- smallest distances can be computed after a maximum of I iterations
ages, and to propose a new algorithm that performs well in case of such where I is the total number of points in the map.
blockages. In a dynamic map blockages happen suddenly. While the The basic DP may be able to solve the problem of robot path planning
robot is moving, there is little time available for the algorithm to detect to a good extent; however it is unable to solve the problem of blockages
the blockage, and once detected to decide the plan of action. A good which is the main intent behind the work. In this work we hence propose
algorithm must hence be able to guide the robot towards an optimal a new set of nodes, called the accelerating nodes, which aid the DP
path immediately after the occurrence of a blockage. in performing well in cases of blockages. These nodes are fewer in
We choose Dynamic Programming as the base algorithm for work [1]. number and give a coarser representation of the map. These nodes
The basic concept behind DP is to break up a problem into multiple are able to quickly detect blockages and further build an approximate
related sub-problems. A sub-problem may in turn be broken down into path from the current position to goal in case of a blockage. The robot
similar sub-problems and so on until the sub-problem is of a unit size. may use this path for its immediate motion, while the optimal path may
Solving the main problem naturally requires solving a large number of take time to be built.
sub-problems. DP attempts to solve all unique sub-problems once only, Another similar approach to solve the problem is with the use of Artificial
and these results are stored in a memory structure from where they may Neural Networks [2]. Here there are numerous models that work on the
be fetched next time they need to be solved. basic principle of propagating the least distances from the destination
In robot path planning, the problem solved by DP is to calculate the in various directions. As the passage of information takes place be-
distance of the goal from all the points in the map. Distance to further tween the nodes, the distances are computed and passed. The obsta-
cles have a fixed maximum distance. These approaches also include
the solutions using shunting equation for propagation of distances [3].
∗
E-mail: rahulkalaiiitm@yahoo.co.in A point in our DP formulation plays a similar role to a neuron. However
†
E-mail: dranupamshukla@gmail.com neurons have di erent dynamics governed by neural activation, unlike
‡
E-mail: rt_twr@yahoo.co.in our approach.

23
 PALADYN Journal of Behavioral Robotics

Lebedev et al. [4] used a type of neural network called dynamic wave search is performed. Change in the robotic map leads to re-planning
expansion neural network for the e cient and optimal planning of the and cost modification of nodes. Hierarchical planning may also be car-
robot in a real time environment. Here every grid is a neuron that propa- ried out using D* as presented in [16]. These algorithms perform well
gates some activity to the other nearby neurons or grids. The obstacles in dynamic environments with small changes in map, for which they are
and goals are clearly identified by the activity they propagate. The robot best suited. For cases of a path blockage there is a completely new
motion is computed by measuring this activity, which is driven by the path which needs to be determined. In such cases computational re-
intrinsic neuron equations, also referred to as the shunting equations. quirements are very large, which may require the robot to wait while a
The model proposed avoided the robot oscillating in certain likely situ- new path is sought. Blockage completely changes all costs, and hence
ations. In turn, the robot was made to remain stationary and wait for the computations prior to blockage have less use after the blockage
a new activity being propagated by the network. All these approaches scenario.
cannot perform well in case of blockages unless the update frequency Another popular mechanism to handle the problem of a large number of
is very high, which demands very high computational requirements. nodes is to sample out some nodes for the planning purpose. Rapidly-
The only way of sensing and acting in response to blockages is through exploring random trees (RRT) [17, 18] are widely used for this purpose.
the activity of neurons. This may lead the robot to come very near to the They start the search process by using the source as the root of a tree-
blockage and it may then have to back track its path, which is clearly like data structure. Search proceeds by expansions of the tree structure
sub-optimal. until a goal is found. Recent works includes use of multiple RRTs and
DP principles are also used in numerous graph search algorithms abun- combining them to produce optimal results [19]. It is di cult to pass
dantly used for robotic planning. Literature points to extensive use of through narrow passages using these sampling based approaches for
A* algorithm [5] which is additionally guided by heuristics to direct the which a better sampling technique was proposed in [20].
search process towards goal. The various points on the map corre- Another popular sampling based method is probabilistic roadmaps
spond to the nodes of the A* algorithm, with weighted connections be- (PRM) [21, 22] where random samples are drawn out from the en-
tween two neighboring nodes if the robot can directly move between tire map and connectivity is determined by a local search algorithm.
these nodes. The weights correspond to the Euclidean distances be- Once formulated, the map may be made adaptive as per the chang-
tween the nodes. The A* algorithm considers both historic as well as ing environments [23]. Similarly, the local search may be performed
heuristic cost to find the path between the source and the destination. on a coarser level before checking on a finer level, as most con-
It keeps expanding the nodes until the destination node is reached. nections are collision prone which may be easily found at a coarser
Heuristics make the algorithm computationally less expensive; however level [24]. Clark [25] presented a PRM solution for robot planning and
in case of a blockage the only thing that can be done is to re-calculate control where multiple robots could communicate and build a complete
the path. This means the robot has to wait for some time while the path roadmap.
is re-computed. In DP however the extra computations are a source of Sampling based approaches are able to come up with a travel plan
blockage detection and alternative path buildup, which justifies its high early, which may be used post detection of blockage. However this
initial computational cost. leaves the question unanswered of how blockages would be detected,
Both DP and graph search based techniques have a common problem which is a big problem in itself. Further sampling based approaches
of having a large number of nodes or high complexity which restricts would start afresh the task of building up an alternative path. This
their use in real time systems. An alternative is to use a multi-resolution means a greater time as compared to our notion of accelerating nodes.
approach where the map is represented at multiple resolutions and a Also these approaches return sub-optimal paths. Hence the complete
planning algorithm may start the search process on a higher resolution motion of the robot cannot be done by the results generated by these
and query lower resolutions if needed. Commonly used representa- algorithms.
tions include Quad Tree [6], Mesh [7] and Pyramid [8]. Another repre- O’ Hara [26] presents another unique algorithm that works at the hard-
sentation is the framed quad-tree representation [9]. In this approach ware level with embedded systems. Here multiple sensors are embed-
every grid is additionally broken into a number of unit sized grids that ded in the map which communicate with each other and propagate
surround the main grids. This representation gives the capability to the distances to the goal. The robot simply queries the sensors and
generate more flexible paths, at the same time limiting the number of moves. A similar approach was used by Yao and Gupta [27] where
grids for easy execution. each sensor was a local planning agent whose role was to guide the
Kala et al. [10] used a similar approach of multi-resolution maps. Plan- robot to the nearest sensor such that the robot advances towards the
ning was initiated at the lower resolution and upon receiving a valid goal along a shortest path. These approaches are naturally better as
path, the resolution along areas of returned path was increased. Graph they can rapidly detect blockages and plan an alternative path. How-
search was done using Multi-Neuron Heuristic search [11, 12], which is ever for these approaches to be applied it is important that the map
an advancement over the conventional A* algorithm. In another recent already has sensors embedded. This restricts planning to some spe-
approach, multi-resolution based planning is presented [13] where the cific application areas and further may involve higher costs.
planning algorithm used is Lifelong A* algorithm (LPA*) [14]. The basic The basic purpose behind the use of DP with accelerating nodes is
idea behind these approaches is quick computation of a path in case that some extra computation (while the robot is moving) can be used
of blockage. Since the map is assumed to be of high resolution, the for rapid development of an alternative path in case of blockages. This
computation of a path using these hierarchical approaches may also enables the algorithm to handle the cases of blockages better. While
take time, resulting in the robot waiting. When a blockage is detected, the robot is traveling, most planning approaches would have no com-
the algorithm needs to initiate the process of constructing the path right putation except a small validation phase to check the validity of the
from the start. In DP with accelerating nodes, many of the computa- path being followed. While the robot travels at its pace, some amount
tions of the previous iterations can be used to give an approximate of computations may be performed. It is here that we monitor and
path for immediate traversal of the robot. Further, solely using these store map state as computed by all the nodes and accelerating nodes.
approaches means a robot traveling on a sub-optimal path provides a These computations help in case of blockages.
computational speedup at the cost of minimal loss of optimality. The problem considered is path planning of a mobile robot. The plan-
The D* [15] algorithm is the dynamic variant of the A* algorithm. Here ning especially needs to be near-optimal and computationally less ex-
the planning starts with an o ine phase where heuristic guided graph pensive in scenarios of blockages. Since the map is dynamic and may

24
 PALADYN Journal of Behavioral Robotics

constantly change, the optimality of any travel plan cannot be guaran- gion of the map with obstacles (ζ free = ζ – ζ obs ). The obstacles may be
teed, although for static maps the planned path is optimal. It is as- static, where the position of the obstacles does not change over time,
sumed that the map is of high resolution. Further it is assumed that leading to a constant map ζ free ; or they may be dynamic where the po-
free
computation is limited and hence the maximum number of calculations sition of obstacles changes over time, leading to a dynamic map
(∪ ) ζ (t).
per step of the robot needs to be limited. The problem is to come up with a path τ c (x(c), y(c)) which the
The contributions of the work are: (i) We propose new nodes called robot may use for navigation without colliding with any of the obstacles
accelerating nodes in the conventional structure of the DP, which work or (x (c ),y (c ))∈ζ free (c ). Here (x (c ), y (c )) denotes the planned position
at a coarser map, while the normal nodes work at a finer level. (ii) We of the robot at time c (≥ t ) knowing the map (ζ free (t)) at the time the
state a mechanism to deal with the problem of blockages consisting plan was generated (say t ). While t denotes the global time, c denotes
of blockage detection, alternative path buildup, and optimal path re- the time an action is scheduled to take place in the future. We assume
buildup. (iii) Through simulations we show the ability of DP to handle that there is only one source (S = τ(0) = (x(0), y(0))) and one des-
cases of moving obstacles, moving targets and blockages, generating tination (G = τ(T ) = (x(T ), y(T ))) both of which are given, and the
near-optimal trajectories. aim of the robot is to reach the destination starting from the source. T
This paper is organized as follows. The problem of this work is for- is the time in which the robot is projected to reach the given destina-
mally introduced in Section 2. In Section 3 we briefly summarize the tion. The entire path generated by the algorithm needs to be optimal in
Dynamic Programming paradigm, discuss the problems with DP and terms of length, so the objective is to minimize ||τ ||.
present the concept and working of the accelerating nodes. The mon-
itoring of changes and working of the algorithm in a dynamic scenario Changes in the environment may be sudden or gradual. Let O be the
is explained in Section 4. Section 5 presents the simulation results. set of obstacles and area (t, o) be
∪ the region of the map occupied by
Section 6 gives the concluding remarks. obstacle o at time t, such that o∈O area(t, o) = ζ obs (t). Sudden
environment changes may be caused in real life by various factors such
2. Problem Formulation as an obstacle rapidly∪entering the map or emerging somewhere in the
map (O (t +1) = O (t ) o ), or an obstacle suddenly leaving the map
Map (donated by ζ ) of size m x n is assumed to be already known. or disappearing from somewhere in the map (O (t +1) = O (t ) - o ), or
Each cell of this map (x, y ) ∈ ζ , 1 ≤ x ≤ m, 1 ≤ y ≤ n, corresponds to two obstacles blocking the space between them (Blockage(o1 ,o2 ,t )),
a navigable area ((x,y )∈ ζ free ), or an obstacle ((x,y )∈ ζ obs ). Here ζ free or two obstacles clearing the way between them (Clear (o1 ,o2 ,t )), etc.
denotes the region of the map free of obstacles and ζ obs denotes the re- Here the two functions are given by equation 1 and equation 2

( ∩ ∩ )
Blockage(o1 , o2 , t) = Boundary(t + 1, o1 ) Boundary(t + 1, o2 ) ̸= ϕ ∧ Boundary(t, o1 ) Boundary(t, o2 ) = ϕ (1)

( ∩ ∩ )
C lear(o1 , o2 , t) = Boundary(t + 1, o1 ) Boundary(t + 1, o2 ) = ϕ ∧ Boundary(t, o1 ) Boundary(t, o2 ) ̸= ϕ (2)

Boundary (o) represents the boundary of an obstacle o. The sudden navigate. This results in invalidating the(∪present path and engineering
)
∗ ∗
changes are very di cult to incorporate in many implementations of a new path by the algorithm. Let τ *(t ) c (x (t, c), y (t, c)) denote
path planning algorithms since we may not be able to reuse many of the the optimal path at time t using a static map which appears as ζ free (t ).
properties of solutions from the previous time step in the next time step. In such scenarios ||τ *(t +1) - τ *(t ) ||> ε2 for small ε2 . In the same
Sudden changes at many times may be equivalent to re-calculating the example consider a car covering the entire road. Now you may need to
entire robotic path. This is di cult and in many cases time consuming. choose another road in order to reach the destination. A path planning
The e ect of gradual changes to a map may not be that large which algorithm in a dynamic environment is supposed to cater to the needs
may be caused by gradual movements of the obstacles (equation 3) or of all these situations.
similar reasons.
The purpose behind the algorithm is e cient planning in cases of block-
ages. This emphasizes that the algorithm is quickly able to detect
||Boundary(t + 1, o) − Boundary(t, o)|| blockages and quickly direct the robot to move, by the optimal path
considering the map after the blockage.
< ε1 ¬Blockage(o, o1 )∀o1 ∈ O (3)

Here ε1 is a small number. In such scenarios only a few changes may

be required in the robotic path returned by the algorithm to make it 3. Accelerating Nodes
valid and optimal as per the new map. Consider you are traveling on
a road with some cars. The internal movement of other cars does not
appreciably a ect your movements or path followed. The contribution of this paper is to propose a new set of nodes called
However many times changes may be considerable when they result in accelerating nodes within the conventional working of the DP. In or-
completely segregating two parts of the map, or in other words blocking der to understand the approach proposed, it is important to study the
the path, or alternatively clearing a path which the robot can now use to conventional DP and understand its limitations in dynamic scenarios,

25
 PALADYN Journal of Behavioral Robotics

Here Z is given by equation 6.

I J Dmax is the maximum possible value of D (V ). All values greater than
(x-1,y+2) (x+1,y+2) Dmax are trimmed down to Dmax .
P B C D K
(x-2,y+1) (x-1,y+1) (x,y+1) (x+1,y+1) (x+2,y+1) Z = z:D(z, i)+ V − z ≤ D(k, i)+ V − k ∧z, k ∈ δ(V )∀k ̸= z
A V E (6)
(x-1,y) (x, y) (x+1,y) We further need to keep a track of the manner in which the update
O H G F L is taking place to facilitate the construction of the path with the short-
(x-2,y-1) (x-1,y-1) (x,y-1) (x+1,y-1) (x+2,y-1) est distance to the goal. This is done by using equation 7 that stores
N M the successor S (V, i+1) of any node V from the information up until
(x-1,y-2) (x+1,y-2) iteration i+1.

Figure 1. The neighborhood of any node in the map. S(V , i + 1) = Z

S(V , 0) = null ∀V ∈ζ (7)
which we do in the following sub-sections. We then present the basic
concept behind accelerating nodes. At any instance of time the robot moves to the successor S (V ) while
placed at node V. In this manner the robot traverses the entire path
from the source to the destination. The successor of destination is
3.1. Dynamic Programming kept null. We do not assume the number of cells to be small for real
time operations. As a result the algorithm has an initial setup phase
We first present the general DP technique of solving the problem of where the initial values of D (V, i ) and S (V, i ) are computed for all V.
robotic path planning. The model has been motivated by the work of The robot has to be stationary until this phase has completed. Once the
Willms and Yang [1] who used DP for real time robot path planning. source is given a non-null value of S (V,i ), the robot can start moving. It
At every iteration we try to propagate the distance from the destina- is natural that in a static environment the robot would move as per the
tion to all the cells of the map. In this manner this approach is similar path calculated by the DP. Also, the path would be optimal in nature
to the Neural Network approach used by Yang and Weng [2] and Zel- due to the properties of DP.
ingsky [3]. The surrounding few cells are used for the distance update
or distance propagation at every iteration. These cells constitute the
neighborhood of a cell. 3.2. Dynamic Programming for Dynamic Scenarios
Suppose that we are updating the cell V (x,y) at an iteration i. In our
model, the cells that constitute the neighborhood (δ (V )) and thus aid In a static environment the robot continues its motion by following the
in computation of the distance from the destination are given by equa- successor S (V,i ) at every node V resulting in the path τ . However, in a
tion 4 and shown in Figure 1. dynamic case, this may not be possible as some obstacle might move
into the path of the robot. The algorithm then needs to adjust accord-
ingly. DP is able to perform su ciently well in the case of a dynamic
δ(V) = {A(x − 1, y), B(x − 1, y + 1), C(x, y + 1), D(x + 1, y + 1), environment as well.
In most dynamic environments it is common to have obstacles that
E(x + 1, y), F(x + 1, y − 1), G(x, y − 1), H(x − 1, y − 1), move constantly with time. The motion of the obstacle changes the
map (ζ free (t)). The motion of the obstacles causes a change in the
I(x − 1, y + 2), J(x + 1, y + 2), K(x + 2, y + 1), L(x + 2, y − 1),
optimal path of the robot (τ *(t +1) ̸= τ *(t )). The DP keeps updating
M(x + 1, y − 2), N(x − 1, y − 2), O(x − 2, y − 1), the values of D (V, i ) and S (V,i ) using equations 4, 5, 6 and 7. Hence
∩ as soon as the obstacle moves, the distances are re-calculated as per
P(x − 2, y + 1)} ζ the modified map. These changes would need time to propagate to
(4) all sections of the map from the location of the change. Let the robot
be moving with an optimal plan at time t which is τ *(t ). The number
of iterations (I ) of DP required to generate an optimal path at time t +1
√ √
The weights of the edges are 1, 2 or 5. It may be noted that other which is τ *(t +1) is given by equation 8.
cells in the figure are not considered directly as they may easily be
visualized as a combination of 2 or more moves totaling to same weight. I = nodes(τ ∗ (t + 1, c)), t ≤ c ≤ c2 (8)
The recurrence relation of the DP to calculate the distance D (V, i +1) nodes () returns the number of nodes on the input path.
of the target (G ) from any node V at an iteration i+1 using the values c2 is the projected time corresponding to the first common cell between
of iteration i may hence be given by equation 5. τ *(t +1) and τ *(t ) beyond which the two paths are equivalent. This is
  given by equation 9.

 0 V =G 

D(V , i + 1) = Dmax V ∈ ζ obs c2 = d: mind (τ ∗ (t + 1,e) ∈ τ ∗ (t) ∧ τ ∗ (t + 1,d − 1)
 min (D , D(Z , i) + V − Z )

otherwise


max / τ ∗ (t)∀e, t < d < e ≤ T )
∈ (9)
{ }
0 V =G
D(V , 0) = The statistics are therefore wrong if fewer than I iterations have taken
Dmax otherwise
place after the obstacle moves. After these iterations the optimal path
(5) τ *(t +1) may be generated.

26
 PALADYN Journal of Behavioral Robotics

In most cases, an obstacle motion produces only a small a change in

distance values (equation 3). Let us consider motion of a single obsta-
cle o from time t to time t +1. Modified distances are propagated from
point c2 and take I iterations for generation of optimal plan τ *(t +1). If
the updates of DP per unit time are fewer than I, it is evident that the
robot would continue its motion on a non-optimal path. Since changes
in the map ζ free (t +1)(∪ are small and there is no blockage,
) we can com-
′ ′
pute a path τ ’(t +1) c (x (t + 1,c), y (t + 1,c)) by the smallest de-
viation of the path τ *(t ) such that (x ’(t +1,c ),y ’(t +1,c ))∈ ζ free (t + 1).
It is evident that cost of τ ’(t ) is almost equal to that of τ *(t) (or
abs (||τ ’(t+1)||- ||τ *(t)||) < ε3 for small ε3 ). After a unit update of DP,
all non-obstacle nodes V in the path of the robot receive a value D (V,
i ) < Dmax , which means the robot cannot collide with an obstacle (if
not already at an obstacle node). This means the robot starts follow-
ing a path similar to τ ’(t +1) until I DP updates are made, after which
it follows an optimal path τ *(t +Ic ) which may itself be close to τ ’(t +1). Figure 2. Map showing accelerating nodes.
Ic denotes the time taken for I DP updates. We know abs (||τ ’(t+1)||-
||τ *(t)||) < ε3 and abs (||τ *(t+1)||- ||τ *(t)||) < ε3 (changes in map are
small). Hence following path τ ’(t +1) is sub-optimal, however, the loss use of accelerating nodes. They monitor the changes in the distances
of optimality is not significant. If the obstacle is continuously moving, and hence sense the blockage in the path presently being used by the
we may similarly argue that there is a non-significant loss of optimality robot. In case of a blockage an approximate path is swiftly built, until
as long as no blockage occurs, and the number of DP updates per unit the main path is being computed. These nodes are put into the map in
motion of robot is more than unity. The loss of optimality may however addition to the normal nodes and work in the map at a coarser level.
be proportional to total traversal of the obstacle, summing a small loss The concept of accelerating nodes may be easily understood with the
at every move. help of Figure 2. Here the various nodes marked with ‘* ’ are the ac-
The other case may be that the target is moving. In this situation as celerating nodes. From a general theoretical perspective these nodes
well, the optimal path of the robot changes as the target moves. The are blockage detectors and path re-constructors which may be placed
update is carried in the map which is later reflected or propagated by the anywhere in the map. Large number of accelerating nodes may require
DP using equations 4, 5, 6 and 7. Consider motion of the target from a large computational cost which means their total number has to be
G1 at time t to G2 at time t +1. We consider that the target signifies a limited. However, a large number of nodes may aid in early blockage
physical entity of interest and hence (assuming no dynamic obstacles) detection and an optimal alternative path construction. If an a priori
the path of the target from G1 to G2 is collision free. This means that analysis of the robotic map can be done, it would be viable to place
a path τ ’(t +1) is possibly formed by appending the traversed path of these nodes near the optimal travel plan of the robot at areas where
∪ blockage may be likely, as well as at the alternative areas to aid con-
the target to the original robot path, or τ ’(t +1)= τ ’(t ) G2 . If the tar-
get motion is small, by same reasoning we may have abs (||τ ’(t +1)||- struction of a new alternative path. The same reasoning holds for the
||τ *(t )||) < ε3 and abs (||τ *(t +1)||- ||τ *(t )||) < ε3 which means the loss alternative path. In this paper we however do not rely on any such a pri-
in optimality on initially tracing the path close to τ ’(t+1) is small. If the ori analysis and present a uniform placement strategy. All these nodes
target moves continuously, similar reasoning may be applied. Again, always lie in points without obstacles. In case the uniform placement
loss of optimality would be proportional to the total motion of the target results in an accelerating node being placed at a point with an obstacle,
which emphasizes that the gap between target and robot (following a that node is not placed at all, resulting in lowering the total number of
sub-optimal path) should decrease with time. If the target moves faster accelerating nodes in the graph. Let N be the number of accelerating
than the robot, it is hence possible that the robot may never catch the nodes in the map.
target. Similarly, the number of DP updates per unit move of the robot All the nodes of the map, V, store distances from these accelerating
should be more than the number of nodes traversed by the target in nodes in addition to the target. Let Q be the set of accelerating nodes.
order to make construction of the path τ ’(t +1) possible. Every accelerating node Qj denotes a physical position on the map.
Hence we re-formulate the notations of Section 3.1 to denote D (V,Qj ,i )
The most interesting condition is when a blockage takes place a ecting
as the distance of node V in the map from the accelerating node Qj
the optimal path (equation 1) or a blockage becomes cleared (equa-
after i DP iterations, and D (V, G, i ) to denote the distance of node
tion 2). This may result in a significant change of optimal path or
abs (||τ *(t +1)||- ||τ *(t )||) >> ε3 . In case of blockage it means pro- V from the target after i DP updates. The corresponding successors
are given by S (V,Qj ,i ) and S (V, G, i ). The update procedure for the
ducing a path τ ’(t +1) by small deviations may not be possible. Moving
target remains the same as shown in equation 4, 5, 6 and 7. The update
by τ *(t ) may be regarded as random with no certainty of moving to-
procedure of the accelerating nodes is given by equation 10.
wards goal. Further it may require a long time for the optimal plan to
be built (equation 8 and 9). If the map is of high resolution or the DP
iterations are expensive, it would take a long time for the change to
D(V , Qj , i + 1) =
propagate. Hence the discussed DP approach may not work unless  
the updates are very fast or the map is of small size.
 0Q
 V = Qj 

Dmax( ) V ∈ ζ obs

 min D Q , D(Z , Q , i) + V − Z 
3.3. Accelerating Nodes max j otherwise 
{ }
Looking at the limitations of DP in case of blockages, we need to model 0 V = Qj
the problem in such a manner that the changes in the map which may D(V , Qj , 0) = Q (10)
Dmax otherwise
largely a ect the path are well identified. We achieve this through the

27
 PALADYN Journal of Behavioral Robotics

Here Z is given by equation 11.

Q
Dmax is the maximum possible value of D (V,Qj ). All values greater than
Q Q
Dmax are trimmed down to Dmax .

Z = z:D(z, Qj , i) + V − z
≤ D(k, Qj , i) + V − k ∧ z, k ∈ δ(V )∀k ̸= z (11)

The successor of any node S(V, Qj , i ) is given by equation 12.

S(V , Qj , i + 1) = Z
Figure 3. Map showing change in optimal path due to sudden environment
S(V , Qj , 0) = null ∀V ∈ ζ (12) change.

In such a way |Q| accelerating nodes may be visualized as |Q|+1 would occur if a moving obstacle causes a blockage. Now we need to
agents (|Q| accelerating nodes and 1 target) propagating their dis- use the information stored in the accelerating nodes for computation of
tances. Each node V has to store |Q|+1 distances. In this manner the a strategy to overcome this problem.
computational cost for each update of DP increases with an increase Figure 4 depicts the overall procedure of working in the case of dynamic
in the number of accelerating nodes. environments. The first step is to compute the initial values of the DP
The major di erence between the target and accelerating nodes is that (D (V,Qj ,i ) and D (V,G,i ) ) and the successor (S (V,Qj ,i ) and S (V,G,i )
Q
the maximum distance Dmax for these nodes is much less than that of ) of all nodes V. Then the robot starts its journey and keeps moving
Q at every instant of time based on the successor of the node. Let R (t )
Dmax of the target (Dmax < Dmax ). This is done to restrict the view of
be the position of the robot at time t. The robot moves towards the
all nodes to the nearby accelerating nodes only, rather than having all
node S (R (t ),G,i ) where the motion continues. The robot terminates
accelerating nodes within their view and computation. Hence, as we
if S (R (t ),G,i ) is null denoting reaching the target (G ). As the robot
move a considerable distance from the accelerating nodes, their e ect
Q moves, the DP iterations continue (equation 4, 5, 6, 7, 10, 11, and 12)
reduces and all other nodes outside a range of Dmax take the maximal wherein a change in values is observed in the case of a change of the
possible value. map ζ free (t ). Each accelerating node (Qj ) monitors for any loss of con-
Two accelerating nodes Qj and Qk are said to be connected to each nectivity with other neighboring accelerating neurons. If a blockage is
other if ||Qj - Qk ||< Th, where Th is a threshold governing connectiv- detected (Blockage(Qj , Qk )), an alternative path (Path) is built us-
ity. The connections are preferred to be local only, or in other words ev- ing graph search which uses the accelerating node graph as the input.
ery accelerating node is connected to a few accelerating nodes around After necessary iterations of DP have been reached, the robot termi-
it. Let D *(Qj , Qk ) denote the stable value of D (Qj , Qk , i ) (beyond nates its motion along the alternative path and continues along the DP
which any number of updates do not produce any change) which is the path. The algorithm ends when the target is reached. Each part of this
optimal distance between the nodes Qj and Qk . In case of any change concept is discussed in the next subsections.
in the environment the maximum number of DP iterations needed to
ensure that value of D (Qj , Qk , i ) is stable or optimal in value is equal
to D *(Qj , Qk ), as per the modified map. This value has a threshold 4.1. Monitoring Change
Q
ofDmax . Hence the maximum number of iterations needed to deter-
The first requirement is to monitor the changes in the map that may
mine a loss of connectivity between 2 accelerating nodes or to detect
Q cause a blockage between any segments of the map. Monitoring of
a blockage is Dmax . the map is performed by the accelerating nodes. Upon detection of a
Q
The value Dmax is chosen such that it is small enough to detect any blockage alternative path construction takes place. Only the segments
change in the environment reasonably early and large enough to imply in the way of the current path (τ ) are of interest. Each node V of the
a high connectivity between nodes (which results in the production of map knows the distances from itself to the target as well as the accel-
better alternative paths in case of a blockage). In this paper with uni- erating nodes. Consider any two accelerating nodes Qj and Qk . The
formly distributed accelerating nodes this value is chosen to facilitate distance between these accelerating nodes D (Qj , Qk , i ) is computed
connectivity to the 2nd accelerating node. Alternative methods may be by the DP updates. In the case these nodes are far apart from each
formulated as well. Accelerating node connectivity is shown by the cir- Q
other the distance would be Dmax . Suppose we make a series of J
cle for one accelerating node in Figure 2. iterations of DP. A blockage between two segments covered by accel-
erating nodes Qj and Qk is identified by a constant increase in D (Qj ,
Q
Qk , i ) along with iterations until it reaches a maximum value of Dmax .
4. Dynamic Environment Changes Every time equations 10 and 11 are executed in a single DP iteration in
case of a blockage, the distance D (Qj , Qk , i ) is increased. Blockages
In a static environment the algorithm is a simple DP solution to the prob- are checked by using equation 13.
lem. The novelty in the use of accelerating nodes lies in the scenario
when the map changes in a manner resulting in a change in the optimal
path due to blockage. Consider Figure 3. The light region is the ob- Blockage(Qj , Qk ) = (D(Qj ,
stacle that suddenly appears in the map. As a result the optimal path
when the robot is at position A suddenly changes. A similar scenario Qk , i + J) − D(Qj , Qk , i) > U) (13)

28
 PALADYN Journal of Behavioral Robotics

DP Initialization

Robot Movement

DP Update Iterations

Monitor Changes

Change Target

Yes
Path A* Algorithm
Change?

No

Switch to Normal DP Criterion

Yes
Target
Change
Criterion?

No
Figure 5. Generation of an alternative path by graph search algorithm.
No
Target
Reached?

graph search. The path returned by uniform cost search is a guiding

Yes path that has been built over an abstract map consisting only of acceler-
Stop ating nodes. This path, in a very small time, gives an approximate idea
of the optimal path (τ *(t )) that the robot may follow to reach the goal.
By working over an abstract map we are able to generate an approx-
Figure 4. Algorithm for handling dynamic environment. imate path when the optimal path cannot be found instantaneously.
This compensates for the time wasted earlier in the computation of the
U is a constant that is kept just smaller than J. The factor J needs to distances propagated by the accelerating nodes.
be small enough to detect blockages early as a blockage can only be The other major issue is the use of this path generated for the motion
detected after J iterations of DP. However the factor has to be large of the robot. Consider the path as a set of nodes (Path = <R (t ), Q1 ,
enough so as not to identify as a blockage a small change in the map Q2 , Q3 , . . . Qn , G>). It might however not be possible to travel in
which does not actually cause a blockage. a straight line between any two consequent nodes mentioned in the
We are only interested in blockages that a ect the current path of the path without collision. Hence the coarser path formulated by a coarser
robot. The current path (τ ) is looked up using the successor values graph needs to be worked out at a finer level. Consider the case that
(S (V,G,i )). The distance of the current path (τ ) from the blocked seg- the robot is located at position S given in Figure 5. The path generated
ment (Qj , Qk ) is used to decide whether the blockage potentially af- by the graph search algorithm is marked with a solid line. We instan-
fects the current path of the robot. In case the path is a ected, an taneously change the target of the robot from the actual target to the
alternative path is built and acted upon. In all other cases, no change second point in the path (Path) of the robot which is Q2 . In case the
is performed. path does not have two points, then the last point serves as the target.
This may be easily implemented by using the successors S (R (t ),Q2 ,i )
for motion of the robot when it is placed at R (t ). The robotic move-
4.2. Graph Search Algorithm
ment continues until the robot has almost reached the current target
An alternative path is computed with the help of graph search on the Q2 . In the present implementation motion continues until a distance of
Q
map formed by the accelerating nodes. The input graph contains all Dmax /2. As soon as the distance from the robot to Q2 is less than this
the accelerating nodes (Q ), the present location Q
∪ ∪the robot (R (t )) and
of amount (D (R (t ),Q2 ,i ) < Dmax /2), the uniform cost search algorithm
the target (G ) as vertices (Vertices = Q R (t ) G ). An edge exists is again invoked. The re-invocation accounts for the updated distance
between any two vertices if the distance between them is recorded measures while the robot moved using the alternative path. In this man-
Q
to be less than Dmax . The weights of the edges correspond to the ner the process continues.
distances between them as computed by the DP (equation 14). It would be interesting to note why the views of the accelerating nodes
Q
are restricted to be local only by keeping a low value of Dmax rather than
giving them a full global view of the entire map. For this we compare
Edges = (ver1 , ver2 )/D(ver1 , ver2 , i):D(ver1 , ver2 , i) the accelerating nodes to the target node. The target node has a global
Q
< Dmax ∧ ver1 , ver2 ∈ V ertices (14) view as its distances are accurately recorded by the various nodes with-
out trimming down the values after some amount. Now when a node
reports some value as its distance from the target (D (V, G, i )), we can
Here (ver1 ,ver2 )/w denotes an edge between vertices ver1 and ver2 never be assured of correctness of the value. This is because it may
with weight w. be possible that this value was achieved by some path that passed
Edges from one accelerating node are shown in Figure 2 by dark black through a segment that is now blocked by an obstacle. Let I be the
lines. Uniform Cost Search algorithm is used to compute the shortest number of DP iterations after a potential change of map. Any node V
path between the source (R (t )) and the goal (G ). The execution time with D *(V, G ) ≤ I is guaranteed to have correct value after I iterations,
of the algorithm depends on the number of accelerating nodes. More while the other nodes may be storing incorrect values not accounting
accelerating nodes (|Q |) implies higher execution time. However a for a changed map. I is a reasonably low number in case the blockage
higher number of nodes also implies a better path resulting from the has happened recently. Now consider the accelerating nodes. They

29
 PALADYN Journal of Behavioral Robotics

Q
only store local information. Since the number Dmax is small, the con-
Q
nectivity information about nodes may be relied on after Dmax iterations
at the maximum. This ensures that on detecting a blockage, the in-
put graph to the graph search algorithm is correctly incorporating all
Q
changes which have taken place earlier than Dmax DP updates.

4.3. Switch to Normal DP

In Sections 4.1 and 4.2 we discussed detecting blockages and there-
after taking an alternative path to reach the destination. The alternative
path is however sub-optimal. After some DP iterations all nodes have
optimal values of distances (D (V, G, i )) and successors (S (V, G, i )). It
is hence advisable to discontinue a sub-optimal alternative path (Path) Figure 6. Map and path traced by robot in case of static environment.
and continue with the path as per the updated values of the successors
(S (V, G, i )). The important issue is to decide the time when the revo-
cation of the DP may be done considering all the distances updated as
per the changed map.
Let nodes (Path) denote the number of nodes in the built alternative
path and ||Path ||denote the path length. Let the revocation take place
at a time t2 after I iterations of DP. Let t be the time the blockage was
detected. Since Path is a sub-optimal path to reach destination as per
the modified map, ||Path ||≥ ||τ *(t ) ||. Since the robot moves towards
the goal ||τ *(t ) ||≥ ||τ *(t2 ) ||, which means ||Path||≥ ||τ *(t2 )||. Con-
sidering all weights greater than or equal to unity we have ||τ *(t2 ) ||≥
nodes (τ *(t2 )), or ||Path ||≥ nodes (τ *(t2 )). The number of DP updates
needed when the robot is at R (t2 ) is nodes (τ *(t2 )), which is always
less than the alternative path length (||Path ||). Hence after a total of
||Path||DP iterations (a computed quantity) the revocation may safely
Figure 7. Map and path traced by robot in case of moving target.
be initiated.

5. Results tial setup phase occurred in the algorithm before the robot could start
moving. During this time the target propagated the distances to the
various nodes in the map. Thereafter the robot started moving. After
The algorithm was implemented using a simulation engine imple-
the start of the robotic movement, update cycles of the DP continued.
mented in JAVA. The simulation engine used JAVA Applets for the dis-
However no change was made in these updates as the environment
play of the map, obstacles and the robot movement. The map was
was completely static.
given as a JPEG image. Sudden obstacle changes were simulated by
In the second case we moved the target as the robot moved in the map.
giving multiple images to the simulation agent and loading the needed
We know that the robot can always catch the target if the speed of mo-
image at a given time. The algorithm was implemented as a separate
tion of the robot is greater than that of the motion of the target. Hence
module in the simulation. This implemented the DP with all acceler-
the simulation was run keeping the speed of the target half of that of
ating nodes. All simulations used maps of size 100×100 pixels. The
the robot. At every instance of time the robot tried to chase the target.
source is the top left corner of the map and the destination is the bot-
While doing so the robot also avoided the obstacles that appeared in
tom right corner. The simulations were carried on a 3.0 3.0 Core 2 Duo
its path. The target moved in a straight line that was predefined. The
processor with 4 GB RAM.
simulation result for this problem has been given in Figure 7. The cir-
The entire algorithm has many parameters that we analyze one by one.
cles denote the accelerating nodes. The motion of the target has been
These include the number of accelerating nodes, number of iterations
shown by the dashed line. It can clearly be seen that the robot was not
of the update cycle, and maximum distance of accelerating nodes. We
only able to catch the target, but the entire path length was also opti-
even discuss the trade-o in time and path length in the next sub-
mal. During the course of the run, the value of the DP changed multiple
sections.
times. However no blockage was detected by the algorithm.
The next experiment analyzed the behavior in case of moving obsta-
5.1. Path Optimality cles. Obstacles were moved while the robot was traveling from the
source to the goal. The robot was now supposed to reach the tar-
We first study the optimality of the path for various maps. We provided get and at the same time avoid the moving obstacles. The avoidance
various maps and used the stated algorithm to solve the problem. In of obstacles was di cult because of the fact that they came between
all the test cases that we supplied, the algorithm was able to generate the source and the target in the path of the robot. We gave two kinds
optimal paths. In the first case we took a static map. There was no of motions and maps for the simulation purposes. In the first simula-
movement of the target or obstacles. This was done to see the path tion we observed that the robot was able to catch the target using an
finding capability of the algorithm in static conditions. The map and optimal path, and at the same time avoid the obstacles. However no
the path generated by the algorithm are shown in Figure 6. The accel- blockage was detected. The obstacles moved at half the speed of the
erating nodes are shown by circles in the map. Here it can easily be robot. This is shown in Figure 8(a), (b), (c) and (d) at timestamps of
seen that the algorithm gave an optimal path as the final result. An ini- 20, 120, 158 and 174 respectively. The initial position of the moving

30
 PALADYN Journal of Behavioral Robotics

(a) 20 timestamps (b) 120 timestamps

Figure 9. Map and path traced by robot in case of moving obstacle causing
path blockage.

(c) 158 timestamps (d) 164 timestamps

Figure 8. Map and path traced by robot in case of moving obstacle after (a)
20 timestamps, (b) 120 timestamps, (c) 158 timestamps, (d) 164 (a) (b)
timestamps.

Figure 10. Map and path traced by robot in case of sudden obstacle emer-
gence causing path blockage (a) before obstacle emergence (b) at
the end of journey.
obstacle is shown by empty boxes and instantaneous position by filled
boxes. It may be easily noted that the robot showed behaviors of nor-
mal human walk. The robot arrived at the top of the first obstacle when
the destination was on the other side. These facts caused it to wander pletely blocked. The original map and part of the path traced is given in
around for some time as the obstacle moved as shown in Figure 8(a). Figure 10(a). At this instance sudden obstacle occurrence took place
The obstacle moved rightward and the robot struggled for a diagonal which blocked the path. The path thereafter is given in Figure 10(b).
movement at the 120th timestamp given in Figure 8(b). The obsta- It may be seen that accelerating nodes helped as the robot did not go
cle was completely passed at timestamp 158 as shown in Figure 8(c). very close to the obstacle.
Then the robot could easily rush through to find the second obstacle
which it passed in a similar manner as given in Figure 8(c). The final
positions of the robot, obstacles and path are given in Figure 8(d). 5.2. Algorithmic Analysis
This second path witnessed a path blockage, and the accelerating One of the major parameters of the algorithm that largely contributes to-
nodes were put to use. The robot now completely changed direction in wards the algorithmic novelty is the total number of accelerating nodes
the middle of its journey and used some other path when the blockage (|Q |) in the algorithmic execution. In this section we try to analyze
happened. This case is shown in Figure 9. It may be easily noticed and verify the e ect of increasing or decreasing the number of accel-
that the accelerating nodes helped in early detection of the blockage erating nodes. A high number of nodes in the map has a multiplicative
and hence the robot did not go very close to the obstacle that caused increase in the execution time of the algorithm. This is because of the
the blockage. The obstacle traveled downwards as the robot moved. multiple processing of the distances propagated by each and every ac-
When the robot was very near to the turn it made (as shown in Figure 9), celerating node. Further a high number of nodes mean a greater time
blockage occurred which was quickly detected. The robot hence took of execution in building of an alternative path by graph search. Since all
the alternate path. this happens in real time, the e ects may be adverse. The robot would
The most innovative part of the algorithm is its capability of handling have to traverse slowly as well as wait for the alternative path to build
the sudden occurrence of an obstacle that causes a blockage of the in case of a blockage. The advantage of having a larger number of ac-
path from the source to the destination. As a result of this change, celerating nodes is in optimality of the alternative path generation. The
the complete path of the robot needs to be re-calculated in real time. larger the number of accelerating nodes, the better the path returned
The accelerating nodes are again useful in detecting the blockage and by the graph search algorithm due to more information being available
optimally moving the robot using good moves until the actual path is from the various nodes. This would have two benefits. Firstly the al-
re-calculated by the DP algorithm. Here we took a map and made the gorithm would be able to account for small obstacles and blockages
robot move. As soon as the robot was somewhere in the middle of the in the map that a ect the path. Secondly the path of the graph search
journey, an obstacle was placed that caused its path to become com- algorithm would be close to the optimal path. Hence until the algorithm

31
 PALADYN Journal of Behavioral Robotics

Figure 13. Path traced by robot for increasing number of dynamic programming
Figure 11. Path traced by robot for increasing number of accelerating nodes. update iterations.

Figure 12. E ect of number of accelerating nodes on time of execution. Figure 14. E ect of dynamic programming number of update iterations on time
of execution.

builds the distance values by DP iterations, the robot would be traveling We further analyze the contribution of this parameter to the overall path
by a path which very closely resembles the optimal path of the modified of the robot and the corresponding execution times. It is natural that the
map. increased number of iterations in between robot moves would mean an
Figure 11 shows the paths for various numbers of accelerating nodes increase in computation time. This is because of the extra number of
for the case of the sudden appearance of an obstacle. It may be easily iterations or updates. The advantage would however be the decrease
seen that in all cases the robot moved from the initial point to the point A in time in which information regarding the blockage takes to reach the
using the target DP values. As soon as the point A was reached, the in- nodes. A larger update frequency would result in more flow of infor-
formation regarding the sudden blockage was received. This is the time mation per move and as a result the information regarding blockages
that the alternative path was computed and followed. The closeness would be readily available before the robot makes many moves. Sim-
of the computed alternative path to the optimal path decreased as we ilarly, the larger update frequency would allow the robot to catch up
decreased the number of accelerating nodes. This can be easily seen with the conventional DP algorithm reasonably early and continue its
from the various paths in Figure 11. Point B in the same figure denotes journey for the rest of the path.
when the algorithm reverts back to the normal DP algorithm. The cor- Figure 13 shows the path traced by the robot for various update fre-
responding execution times used by the robot are shown in Figure 12. quencies. An early deviation is found in the cases with a larger update
The time almost linearly increases with the increase in the number of frequency compared to ones with a smaller update frequency. This is
accelerating nodes. By examining Figures 11 and 12 we can state that due to the early information availability regarding blockages. The cor-
the trade-o for this parameter is that a higher number of accelerating responding time of execution is given in Figure 14. By examining Fig-
nodes implies better paths (desirable) with higher computational cost ures 13 and 14 we can state that the trade-o for this parameter is that
(non-desirable), and vice versa. a higher update frequency implies better paths (desirable) with higher
Another important factor is the number of updates of DP carried out computational cost (non-desirable), and vice versa.
Q
by the system between every two consecutive moves of the robot. In The factor Dmax storing the vision of every accelerating node is a rather
practice this parameter would depend on the natural speed of the robot. passive parameter in terms of computational time. The value of this
The robot would continue moving at its natural speed along the guided parameter does not appreciably a ect the computational cost of the al-
path and the time to travel in between the nodes would be the time gorithm since all the computations have to be made. This factor mainly
given to the system to make all computations. This determines the a ects the graph search algorithm and its result. A very low value
number of iterations of DP update that the system can perform. A high of this parameter would result in no connectivity of the accelerating
speed robot would mean a low number of iterations and vice versa. node graph. This would eliminate any blockage detection or alternative

32
 PALADYN Journal of Behavioral Robotics

We analyzed the working of the algorithm in several cases and found

our algorithm to be optimal and real-time in all experimented cases. An
analysis of the various algorithmic parameters was also conducted. We
studied how each one of these contributed to e ective reporting of the
blockage, optimality of the alternative path, and other elements of the
real-time nature of the algorithm. We further studied the execution time
of the algorithm in each of these cases. We could easily see that best
performances were obtained using parameter settings which also im-
plied high computational cost. This emphasizes the trade-o between
path optimality and execution time for an optimal parameter setting.
The presented algorithm e ectively solves the problem for experi-
mented scenarios. It may however be augmented by the study of ob-
stacle dynamics in case of moving obstacles. Obstacle motion may
Figure 15. Path traced by robot for increasing vision of accelerating nodes (or be extrapolated for early blockage predictions. Furthermore, a closer
Q
increasing factor Dmax ). study of the algorithmic parameters may be conducted. These param-
eters may be made adaptive in future to automatically adjust for each
map and past behavior of the robot in the map. The results so far have
been simulation only. This implementation may also be used by real
path computation. For execution of the algorithm, some connectivity is robots in dynamic environments.
needed between the accelerating nodes. A medium value of this pa-
rameter which is su cient to establish the connectivity of every node to
its neighbors would mark a local vision for the graph. The robot in case
of blockage can select the alternative path. Very large values of this References
parameter would imply a global vision. Here the major problem would
be that every node does not know whether the connectivity reported
by the accelerating nodes account for the blockage or not. Since they [1] A. R. Willms, S. X. Yang, An E cient Dynamic System for Real-
are now allowed to report even large values, it may be possible that the Time Robot-Path Planning, IEEE Transactions on Systems Man
blockage has not yet been updated and the graph search algorithm and Cybernetics – Part B Cybernetics, 36(4) (2006), 755-766
works over wrong inputs. This would result in the algorithm working [2] S. X. Yang, M. Meng, An e cient neural network approach to dy-
like conventional the DP algorithm since connectivity is guaranteed by namic robot motion planning, Neural Networks, 13(2)(2000), 143-
some pair of nodes. These two conditions are shown in Figure 15. 148.
[3] A. Zelinsky, Using path transforms to guide the search for findpath
in 2d, International Journal of Robotic Research, 13(4)(1994),
315–325
6. Conclusions [4] D. V. Lebedev, J. J. Steil, H. J. Ritter, The dynamic wave expansion
neural network model for robot motion planning in time-varying
In this paper we presented a simple and powerful algorithm to compute environments, Neural Networks, 18(3), 267-285.
the optimal path from the source to the destination in the presence of [5] A. Shukla, R. Tiwari, R. Kala, Mobile Robot Navigation Control in
static and dynamic obstacles. The novelty of the algorithm was its real Moving Obstacle Environment using A* Algorithm, In Proceedings
time nature in detecting and acting on the path blockages which is a of the International Conference on Artificial Neural Networks in En-
case not appreciably discussed in the literature so far. The algorithm gineering Vol. 18, ASME Publications, 2008, 113-120.
gives good performance in the presence of complex maps with high [6] S. Kambhampati, L. Davis, Multiresolution path planning for mo-
resolutions and the occurrence of a sudden or gradual blockage in the bile robots, IEEE Journal of Robotics and Automation, 2(3)(1986),
path being followed by the robot. Our algorithm can detect the block- 135-145.
age very early which saves it from continuing its motion in the wrong [7] J. Y. Hwang, J. S. Kim, S. S. Lim, K. H. Park, A Fast Path Planning
path. Further, the robot is not asked to stand stationary or explore the by Path Graph Optimization, IEEE Transaction on Systems, Man,
wilderness for the rest of the path. It is rather guided by a path that and Cybernetics—Part A: Systems and Humans, 33(1)(2003),
closely resembles the optimal path in the modified map. As soon as 121-128.
the optimal path is computed by DP, the robot may continue its move- [8] A. Yahja, A. Stentz, S. Singh, B. L. Brumitt, Framed-quadtree
ment using the optimal strategy. path planning for mobile robots operating in sparse environments,
The functionality of sensing a blockage and building up an alternative In Proceedings of the 1998 IEEE International Conference on
path was implemented with the help of special nodes called acceler- Robotics and Automation, 1998, 650-655.
ating nodes. These nodes performed the additional task of computing [9] C. Urdiales, A. Bantlera, F. Arrebola, F. Sandoval, Multi-level path
their distances to the other nodes. This was done using the same planning algorithm for autonomous robots, IEEE Electronic Let-
mechanism of DP that is referred to as the distance propagation mech- ters, 34(2) (1998), 223-224.
anism. This additional computation helped in sensing changes as well [10] R. Kala, A. Shukla, R. Tiwari, Robotic path planning in static envi-
as taking the needed actions. The accelerating nodes were modeled ronment using hierarchical multi-neuron heuristic search and prob-
as a connected graph with weighted edges. A detected change in con- ability based fitness, Neurocomputing, 74(14-15) (2011), 2314-
nectivity of this graph corresponded to a blockage of the robotic path. 2335.
When any sort of blockage was reported by the accelerating nodes, the [11] A. Shukla, R. Kala, Multi-Neuron Heuristic Search, International
graph search algorithm was used to compute an abstract path com- Journal of Computer Science and Network Security, 8(6) (2008),
prising only of the accelerating nodes. This path was followed until the 344-350.
actual path was re-computed by the DP. [12] R. Kala, A. Shukla, R. Tiwari, Robotic Path Planning using Multi-

33
 PALADYN Journal of Behavioral Robotics

Neuron Heuristic Search, In Proceedings of the 4th International In Proceedings of the IEEE International Conference on Robotics
Conference on Computer Sciences and Convergence Information and Automation, 2008, 3743-3750.
Technology, 2009, 1318-1323. [21] L. E. Kavraki, M. N. Kolountzakis, J. C. Latombe, Analysis of
[13] Y. Lu, X. Huo, O. Arslan, P. Tsiotras, Incremental Multi-Scale probabilistic roadmaps for path planning, IEEE Transactions on
Search Algorithm for Dynamic Path Planning With Low Worst- Robotics and Automation, 14(1) (1998), 166-171.
Case Complexity, IEEE Transactions on Systems, Man, and Cy- [22] L. E. Kavraki, P. Svestka, J. C. Latombe, M. H. Overmars, Prob-
bernetics, Part B: Cybernetics, 41(6)(2011), 1556-1570. abilistic roadmaps for path planning in high-dimensional configu-
[14] S. Koenig, M. Likhachev, and D. Furcy, Lifelong planning A∗, Arti- ration spaces, IEEE Transactions on Robotics and Automation,
ficial Intelligence, 155(1-2) (2004), 93–146. 12(4)(1996), 566-580.
[15] A. Stentz, Optimal and e cient path planning for partially-known [23] R. Gayle, A. Sud, E. Andersen, S. J. Guy, M. C. Lin, D. Manocha,
environments, In Proceedings of the 1994 IEEE International Con- Interactive Navigation of Heterogeneous Agents Using Adaptive
ference on Robotics and Automation, 1994, 3310-3317. Roadmaps, IEEE Transactions on Visualization and Computer
[16] D. Cagigas, J. Abascal, A Hierarchical Extension of the D* Algo- Graphics, 15(1)(2009), 34-48.
rithm, Journal of Intelligent and Robotic Systems, 42(4)(2005), [24] R. Bohlin, L. E. Kavraki, Path Planning Using Lazy PRM, In Pro-
393–413. ceedings of the 2000 IEEE International Conference on Robotics
[17] J. J. Ku ner, S. M. LaValle, RRT-connect: An e cient approach and Automation, 2000, 521-528.
to single-query path planning, In Proceedings of the IEEE Inter- [25] C. M. Clark, Probabilistic Road Map sampling strategies for
national Conference on Robotics and Automation vol. 2, 2000, multi-robot motion planning, Robotics and Autonomous Systems,
995-1001. 53(2005), 244–264.
[18] S. M. LaValle, J. J. Ku ner, Randomized kinodynamic planning, [26] K. J. O’ Hara, D. B. Walker, T. R. Balch, Physical Path Planning
In Proceedings of the IEEE International Conference on Robotics Using a Pervasive Embedded Network, IEEE Trans. Robotics,
and Automation, 1999, 473–479. 24(3)(2008), 741-746.
[19] B. Raveh, A. Enosh, D. Halperin, A Little More, a Lot Better: Im- [27] Z. Yao, K. Gupta. Distributed Roadmaps for Robot Navigation in
proving Path Quality by a Path-Merging Algorithm, IEEE Transac- Sensor Networks, IEEE Transactions on Robotics, 27(5)(2011),
tions on Robotics, 27(2) (2011), 365-371. 997-1004.
[20] L. Zhang, D. Manocha, An e cient retraction-based RRT planner,

34