Assisting Blind person using
DIjkstra’s shortest path algorithm
This Project comprises of a
Hardware mechanical model which is controlled by the electronic circuits to
assist a blind person. I.e., This mechanical model is attached with the walking
stick of the blind person. The model
will move automatically. This model helps the blind person to reach the
destination quickly. The model has a wireless link to a nearby computer system
through which it can identify the shortest path. When the source and destination
is selected the unit will send the data to the computer. The computer will calculate the shortest path
using Dijkstra’s shortest path algorithm and transfers the route to the unit. The unit will then tell the user to move in
which direction. The movement of the user in ensured using a RFID proximity
cards and a reader. The reader will be placed on the unit and on encountering
of cards (Cards placed at each point) will tell the user has to take right or
left or straight through voice output.
An APR 9600 voice storage and retrival IC is used for this purpose. The unit will give alarm signal when it finds
a Obstacle. This project is divided into modules for better understanding of
the circuit.
The modules
included in this project are
Pic
Embedded Microcontroller PIC 16F877
Battery for Power Supply
RFID
Card Reader with cards
APR 9600 Voice Recording and Playback IC
Wireless RF Receiver unit
Wireless RF Transmitter unit
Software Driver in Hitech ‘C’ Language.
Pic
Embedded Microcontroller (PIC 16F877):
This is the heart of the device
which is responsible for sensing the obstacles and producing voice Output.
RFID Card Reader with Cards
A RFID Card reader is
fixed on the unit. Cards will be placed
on the path at regular intervals. When
the unit encounters a card, it can sense the point at which the unit is present
through the unique code present in the card.
APR 9600 Voice Recording and Play Back IC
This IC is
a Single Chip Voice Recording and Playback IC.
A Prerecorded Voice is Stored into the IC. It can be played again by the controller by
sending a control signal to the IC.
RF Wireless Transmitter and Receiver:
A
Wireless RF module is used to establish a wireless link between the unit the
PC. The frequency range is 433.92 and 315 MHZ.
Dijkstra's algorithm
Conceived by Dutch computer scientist Edsger
Dijkstra in 1959, is a graph search algorithm that solves the
single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree. This algorithm is often used
in routing. An
equivalent algorithm was developed by Edward
F. Moore in 1957
For a given source vertex (node) in the graph, the algorithm
finds the path with lowest cost (i.e. the shortest path) between that vertex
and every other vertex. It can also be used for finding costs of shortest paths
from a single vertex to a single destination vertex by stopping the algorithm once
the shortest path to the destination vertex has been determined. For example,
if the vertices of the graph represent cities and edge path costs represent
driving distances between pairs of cities connected by a direct road,
Dijkstra's algorithm can be used to find the shortest route between one city
and all other cities. As a result, the shortest path first is widely used in
network routing protocols, most notably IS-IS and OSPF (Open Shortest
Path First).
Algorithm
Let the node we are starting be called an initial
node. Let a distance of a node Y be the distance from the initial
node to it. Dijkstra's algorithm will assign some initial distance values
and will try to improve them step-by-step.
1. Assign to
every node a distance value. Set it to zero for our initial node and to
infinity for all other nodes.
2. Mark all
nodes as unvisited. Set initial node as current.
3. For current
node, consider all its unvisited neighbours and calculate their distance (from
the initial node). For example, if current node (A) has distance of 6, and an
edge connecting it with another node (B) is 2, the distance to B through A will
be 6+2=8. If this distance is less than the previously recorded distance
(infinity in the beginning, zero for the initial node), overwrite the distance.
4. When we are
done considering all neighbours of the current node, mark it as visited. A
visited node will not be checked ever again; its distance recorded now is final
and minimal.
5. Set the
unvisited node with the smallest distance (from the initial node) as the next
"current node" and continue from step 3.
| CONTACT: MEGATECH NO7,KANNAN AVENUE 1ST CROSS STREET, MUDICHUR ROAD,OLD PERUNGALATHUR, TAMBARAM WEST-CHENNAI 63 (NEAR HERO SHOWROOM,ANNAI ARUL HOSPITAL) TEL:044 22761990 WHATSAPP:98402 34766 MOBILE:81444 34766,9659246311 WEBSITE: http://megatechallprojects.blogspot.in/ EMAIL: megatechallprojects@gmail.com | ||||||
No comments:
Post a Comment