Path planning for robotics and needs more emphasis on algorithms in order to optimize the total distance travelled and energy spent by the system.
For unexplored Environment with multiple Destinations to cover, Deterministic Algorithms like Kruskal’s Algorithm and Dijkstra's Algorithms fail to perform efficiently.
Other Algorithms concerning Stochastic Algorithms also fail to understand the environment and plan the path accordingly.
This project aims to design and test a customized Markov Decision Process Problem for path planning and attempt to solve it using Q-Learning, one of prominent research areas of Reinforcement Learning Algorithms.
Task is to generate a matrix Y which gives the sequence of points needed by the bot to reach the goal in most optimized way
Create a forest F (a set of trees), where each vertex in the graph is a separate tree. Create a set S containing all the edges in the graph While S is nonempty and F is not yet spanning Remove an edge with minimum weight from S If the removed edge connects two different trees then add it to the forest F, combining two trees into a single tree At the termination of the algorithm, the forest forms a minimum spanning forest of the graph. If the graph is connected, the forest has a single component and forms a minimum spanning tree.
The Matrix R, of dimension NxN, describes the reward for the agent, given the current state and action.
Alternatively, R[‘State’,’Action’] gives the reward that agent will receive when the agent performs the action ‘Action’ given the current state as ‘State’.
The Matrix Q of dimension NxN, describes the quality for the agent, given the current state and action.
Alternatively, Q[‘State’,’Action’] gives the quality of the action ‘Action’ given the current state as ‘State’.
The aim of the algorithm is to find the path of states from given state ‘i’ to a final state ‘N’ in optimized manner.
i) Add reward for the action
ii) Add the Subsequent Cumulative sum of Q