Path planning for Unmanned Ground Vehicle

Fethi DEMIM1 , Kahina LOUADJ2,3 , Abdelkrim NEMRA 1

Abstract— The aim of this paper is to find the path planning of graph where vertices describe states and edges describe possible
an Unmanned Ground Vehicle (UGV) using shortest path algorithm transitions, shortest path algorithms can be used to find an
that is a path of a string sequence of n vertices. Before that, the
optimal sequence of choices to reach a certain goal state,
estimated point which has chosen is thought near real points with two
experiences. These estimated points are chosen as the points which its or to establish lower bounds on the time needed to reach a
minimum distance equal between 0.4m and 0.5m respectively. The goal given state. For example, if vertices represent the states of a
is to calculate a path between the vertices of a graph that minimizes the puzzle like a Rubik’s Cube and each directed edge corresponds
robot path of estimated points. It can explain by finding the shortest to a single move or turn, shortest path algorithms can be used
path between two points. The main contribution of this work is seeking
the shortest path of these points and minimizes the computational time to find a solution that uses the minimum possible number of moves.
and the energy that the robot will be provided along this path in
minimal distance. In a networking or telecommunications mind set, this shortest
path problem is sometimes called the min-delay path problem and
I. I NTRODUCTION usually tied with a wider path problem. For example, the algorithm
Path planning is an important primitive for autonomous mobile may seek the shortest (min-delay) widest path, or widest shortest
robots. Furthermore, lets to the robots find the shortest or otherwise (min-delay) path, often studied in operations research, include
optimal path between two points. Otherwise optimal paths could plant and facility layout, robotics, transportation, and VLSI design.
be paths that minimize the amount of turning, the amount of In our paper; before founding Shortest path, we use the Data
braking or whatever a specific application requires. science [10], to extract of knowledge from data. This domain,
The shortest path is one of the most known problems and brings it incorporates varying elements and builds on techniques
a lot of interest in Early history of shortest paths algorithms and theories from many fields, including signal processing,
which are presented by Shimbel in 1955. Information networks. mathematics, probability models, machine learning, statistical
Ford (1956), RAND, economics of transportation, Leyzorek, Gray, learning, computer programming, data engineering, pattern
Johnson, Ladew, Meaker, Petry, Seitz (1957), Combat Development recognition and learning, visualization, uncertainty modeling,
Dept. of the Army Electronic Proving Ground. Dantzig (1958)[2], data warehousing, and high performance computing. Although
Simplex method for linear programming, Bellman (1958)[1]. use of the term data science has exploded in business environments.
Dynamic programming. Moore (1959), Routing long-distance
telephone calls for Bell Labs, Dijkstra (1959)[2], Simpler and In our paper; before the founding shortest path, we use the data
faster version of Ford’s algorithm. science [10], to extract of knowledge from data. Before that, the
The Shortest path problem is to find a distance between two estimated point we have chosen is the points we thought near real
vertices Shortest path problem is about finding a path between two points of two experiences. These estimates point, we choose the
vertices in a graph such that the total sum of the edge weights is points whose distance minimum is 0.5m, and 0.4m. And the points
minimized. we have sorted and judge are reliable points for our goal, we will
This problem could be solved easily when using all edge weights, seek the shortest path of these points.
but here the weights can take any value. The use of algorithms And this result aims to minimize the travel time, and we will
which find the shortest paths are important and not only in robotics, minimize the energy that the robot will provide along this path
but also in network routing, video games and gene sequencing. in minimal distance.
The shortest path problems are by far the most fundamental The paper is structured as follows : we begin with some definitions
and also most commonly encountered problems in the study of that use in our work. The Diksjtra algorithm is given in section II.
transportation and communication networks. In section III, we applied this algorithm for the robot. We finished
Finding the shortest path in a road network is a well known by conclusion in section IV.
problem. Various proven static algorithms such as Dijkstra are
II. E SSENTIAL D EFINITIONS
extensively evaluated and implemented. When confronted with
dynamic costs, such as link travel time predictions, alternative Definition 2.1: A directed graph G = (V, E) consists of a
route planning algorithms have to be applied. finite set V of nodes and a finite set E of arcs. We will use n and
Shortest path algorithms are applied to automatically find directions e to denote the number of elements in V and E, respectively.
between physical locations, such as driving directions on web The node set is assumed to have elements {1, 2, ..., n}.
mapping websites like Map Quest or Google Maps. For this An arc a in E is an ordered pair (u, u) of nodes.
application fast specialized algorithms are available. Definition 2.2: A path is a finite sequence of arcs P =
If one represents a nondeterministic abstract machine as a (al , a2 , ..., ak ), such that ai starts where ai−l ends, for i = 2, ..., k.
Definition 2.3: The path length (or simply length) of P is
*F.Demim, K.Louadj, A.Nemra defined to be d(P ) = l(al )+....+l(ak ). If ai = ui ) for i = 1, ..., k,
1 Laboratoire Robotique et Productique, Ecole Militaire the path P is also denoted by the node sequence (u0 , ul , ..., uk );
Polytechnique, Bordj El Bahri,BP 17, 16111, Alger. Algérie.
[email protected], karim [email protected] u0 is called the source (or origin) of P , uk is called the destination
2 Université de Bouira. Dpartement de Mathmatiques. Bouira. Algérie. of P , and P is called a path from u0 to uk .
louadj [email protected] P is simple if uf 6= ul for all i 6= j.
 Estimated
Definition 2.4: P is a shortest path from u to u if d(P ) is the True Position
Position
minimum length of any path from u to u; in this case, d(P ) is the (x(m), y(m)
shortest distance from u to u. The shortest distance matrix is an (x, y) First experiment Second experiment
n × n matrix whose (u, u)th entry is the shortest distance from u (0,0) (0,0) (0,0)
to u. (4.90;0.70) (4.87;0.85) (4.84;0.75)
(7.20 ; 1.61) ( 7.16; 1.81 ) (7.04 ; 1.98)
III. D IJKSTRA A LGORITHM ( 7.77; 2.80) (7.77 ; 3.03) (7.43 ; 3.22 )
(6.13 ; 4.54) ( 6.19; 4.77) (5.43 ; 4.57)
Dijkstra’s algorithm one is faster than other Belleman-Ford
( 5.80; 6.16) (5.93 ; 6.33 ) (4.73 ; 6.01 )
algorithm but is restricted to nonnegative length functions. The ( 8.52; 8.27) (8.67 ; 8.41) (7.15 ; 8.62)
general framework of the method is the following scheme, described (8.53 ; 10.33) (8.75 ; 10.39) (6.64 ; 10.73)
in this general form by Ford [1956]. ( -3.35; 8.82) ( -3.17; 9.28 ) ( -4.73; 6.52 )
(-3.55 ; 2.36 ) ( -3.92; 2.73) (-4.28 ; 0.37)
♦ Initially, set d(s) := 0 and d(v) := ∞ for each v 6= s. (-3.36 ; 0.47 ) (-3.85 ; 0.74) (-3.86 ; -1.53 )
(0.08 ; 0.09) ( -0.38; 0.26) (0.09 ; 0.02)
[ Next, iteratively,
choose an arc (u, v) with d(v) > d(u) + l(u, v) TABLE I
and reset d(v) := d(u) + l(u, v). T RUE AND ESTIMATED POSITIONS FOR FIRST AND SECOND
\ If no such arc exists, d is the distance function. EXPERIMENTS

\ The difference in the methods is the rule by which the arc (u, v)
with d(v) > d(u) + l(u, v) is chosen.

Dijkstra’s Algorithm prescribes to choose an arc (u, v) with d(u)

smallest (then each arc is chosen at most once, if the lengths
are nonnegative). This was described by Leyzorek, Gray, Johnson,
Ladew, Meaker, Petry, and Seitz [1957] and Dijkstra [1959]. A
related method, but slightly slower than Dijkstra’s method when
implemented, was given by Dantzig [1958], and chooses an arc
(u, v) with d(u) + l(u, v) smallest.
IV. A PPLICATION OF AN U NMANNED G ROUND V EHICLE
When one tries to get from one point to another in a network,
looking for the shortest path, that is to say the one whose distance
is the smallest. If the number of possibilities Paths between the
starting point and the end point is small, it is sufficient to calculate
the length of each of the paths by summing the length of the links
which compose it and to directly compare the lengths obtained.
But such an exhaustive solution quickly becomes impractical if the Fig. 1. Nodes of the first experiment
number of possible paths is large. Fortunately, there are algorithms
that exist to have to calculate all possible projects. For this purpose,
we implemented a various strategies. The composed of nodes are
represented by a graph (the vertices of the graph) and the Oriented
links (the arcs of the graph).
Dijkstra’s algorithm depends on the principle of ”exploration from
the best”. For example, from the best predecessor visited, it can be
used when all arcs have a non-negative value comparing to what is
expended on a given path. In this case, there can be no absorbing
circuits, but there may be other circuits, such as two-way links. In
practice, this algorithm is very often used to solve routing problems
in telecommunications networks. We consider 12 estimated points
given in table 1, in two cases, firstly in 0.5m, secondly 0.4m.

Let calculate Euclidean distance between the true position and

an estimated position of two experiments. After that, in the first
experiment, we chose the positions which their distances are lower
than 0.5m and 0.4 m in the second experiment. Fig. 2. Corresponding Shortest Path of the first experiment
Minimal distance in second experiment is 24.6214 m. And path
corresponding to this distance is 1, 3, 4, 5.
Minimal distance in second experiment is 6.3856m. And path
corresponding to this distance is 1, 5, 3, 6. V. C ONCLUSION
In figure 1 and figure 3, we present nodes of Graph for estimating In this article, we have found path planning of an Unmanned
points for first experiment and second experiment respectively. In Ground Vehicle uses the shortest path algorithm in two experiences.
figure 2 and 4, its corresponding shortest path of Graph 1 and 2 Our results gave an objective satisfaction.
respectively, its presented in red color. It consists in finding how the robot moves in an environment
 [5] H. Frank. Shortest paths in probability graphs. Operations Research,
17 (4), pp. 583-599, 1969.
[6] R. Hall. The fastest path through a network with random time-
dependent travel time. Transportation Science, 20 (3), pp. 182-188,
1986.
[7] P. Loui. Optimal paths in graphs with stochastic or multidimensional
weights. Communications of the ACM, 26 (9), pp. 670-676, 1983.
[8] P.B. Mirchandani. Shortest distance and reliability of probabilistic
networks. Computers & Operations Research, 3 (4), pp. 347-676, 1976.
[9] D. Dubois, H. Prade. Fuzzy Sets and Systems: Theory and Applica-
tions. Academic Press, New York, 1980.
[10] Lynda Tamine-Lechani, M.Boughanem, M.Daoud, Evaluation of con-
textual information retrieval effectiveness, overview of issues and
research, Knowledge and Information Systems, 24(1), pp.1-34, 2010.

Fig. 3. Nodes of the second experiment

Fig. 4. Corresponding Shortest Path of the second Experiment

between a starting point and an arrival point taking into account

different constraints. In the first experiment, the goal was allowed
to go from point 1 to point 6. The second experiment is going from
the point 1 to point 6. So, at the minimum distance we can find our
robot point quickly if the robot is lost in the map, but it has a map
with intermediate point distances between them in its environment.
This can be interpreted by finding where it is the robot positioned
at and to start from and to make more educated vehicle about which
point is the best.
By comparing two experiences, we can say that the robot shortest
path visits some points that are minimal distance during the search
operation. Hence the robot shortest path algorithm is more efficient,
faster and gains the energy source from the beginning to the final
point.

R EFERENCES

[1] E. Bellman. On a routing problem, Quarterly of Applied Mathematics,

16 (1), pp. 87-90, 1958
[2] E.W. Dijkstra, A note on two problems in connection with graphs.
Numerical Mathematics, 1 (1), pp. 269-271, 1959
[3] S. Dreyfus An appraisal of some shortest path algorithms, Operations
Research, 17 (3), pp. 395-412, 1969.
[4] R.W. Floyd. Algorithm-97-shortest path. Communications of the
ACM, 5 (6), p. 345, 1962.