Maze solving algorithm for line following robot and derivation of linear path distance from nonlinear path

摘要

In this paper we have discussed a unique general algorithm for exploring and solving any kind of line maze with another simple one for simple mazes without loops or with loops having highest two branches none of which are inward. For the general algorithm, we need a method to map the whole maze, which is required if the maze is complex. The proposed maze mapping system is based on coordinate system and after mapping the whole maze as a graph in standard `Adjacency-list representation' method, shortest path and shortest time path was extracted using Dijkstra's algorithm. In order to find the coordinates of the turning points and junctions, linear distances between the points are needed, for which wheel encoder was used. However, due to non-linear movement of robot, the directly measured distance from the encoder has some error and to remove this error an idea is built up which ended by deriving equations that give us almost exact linear distance between two points from the reading of wheel encoder of the robot moving in a non-linear path.