Shortest Path Find Using Q-Learning

This page will show the use of Q-learning for navigation in a complete unknown environment. This will calculate the shortest path from current state to goal state by analyzing the environment through captured images. Further the captured images will be processed through image processing and machine learning techniques. The proposed method also takes care of the obstacles present in that environment. Initially, the unknown environment will be captured using a camera. Obstacle detection method will be applied on it. Then the grid based map obtained from vision based obstacle detection method will be given to Q-Learning algorithm which will be further made live with motion planning.
Simply Q learning is a method which follows a policy (greedy) to create reward table of all the states and to their corresponding actions. To make this Q learning works you need

• State Space (Where the robot has to move)
• Action Space (Which directions the robot has to move)
• Reward Function ( rewarding for good moves penalizing the bad)

StateSpace:

In our case an image of the environment where the robot has to move will be fed to the algorithm. The state space is a created by drawing a grid on the image.

 After dividing the imaging into grid, free space should be found in that image where the robot can move. For that cany edge detection with edge dialtion has been done.  

  

The state space can be more smaller grid for the fine learning, but that may cause higher time of learning bu the better understanding of the environment.

 Action Space :

After creation of state space the action space has been created with 8 actions (North South East West North-East North-West South-East South-West). You can increase the no of actions as per your need.

Reward Function :

Reward function is the very important in updating the values of reward table. Reward function can be explained like below

if the current state is goal

       reward=100

elif current state is out of grid

       reward =-100

else

       reward= -1

The Q learning method has been inspired form here
Please find the repository here and compile the code with your test image.
After running the code you have to give the start and goal nodes then there comes the shortest path with obstacle avoidance. (test has been carried out with start node 11 and goal as 129 ).

 This work has been published in IEEE Explore as a proceeding of ISCO 2016.

Publication URL : http://ieeexplore.ieee.org/document/7727034