Header menu link for other important links
X
Low Complexicity Graph Based Navigation and Path Finding of Mobile Robot Using BFS
, Hrudaya Kumar Tripathy
Published in ACM Press
2015
Pages: 189 - 195
Abstract

Path-finding is a fundamental problem, in mobile robotics which involves finding an optimal collision-free path from the source node to the destination node. Before the robot traces out the required path, the first step to be carried out is, exploring the environment. Localization plays a major role in this case. This paper adopts an RFID (Radio Frequency Identification) based localization technique. A set of RFID(IC) tags arranged in a grid structure in an equidistant manner are used for the purpose of tracing the current co-ordinate/location of the robot. After exploring the environment one virtual map is generated which contains the location of source, destination, obstacles and landmarks. From the map one graph is generated which is composed of a set of vertices that indicates the cells of the grid and a set of edges which indicates the free path in the environment reachable from the source. After analyzing different searching algorithms we found Breadth First Search (BFS) algorithm to be more effective, because it finds the shortest path from the source node to each node in the graph. We improved the BFS algorithm so that the optimal collision free path from source to destination node is generated. We have implemented our techniques in a simulated environment. We have used MATLAB and JAVA for the simulation purpose. Finally we have demonstrated the result of the implementation through examples.

About the journal
JournalData powered by TypesetPerMIn '15: Proceedings of the 2nd International Conference on Perception and Machine Intelligence
PublisherData powered by TypesetACM Press
Open AccessNo