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.