A Greedy Approach in Path Selection for DFS Based Maze-map Discovery Algorithm for an autonomous robot

Abstract

This research addresses the map discovery issue for an autonomous robot in an unknown maze. Breadth First Search (BFS) and Depth First Search (DFS) algorithm can be used to do it. Here, we proposed three variants of DFS to discover the map of unknown maze. We implemented Greedy Approach in Path Selection for DFS Based Maze-map Discovery Algorithm which is one of the variants of DFS based approaches. Performance analysis with standard DFS shows that this algorithm produces better result in terms of number of movements and number of rotations. However, we also found that this performance improvement is dependent on certain parameters like the starting position of the robot, presence of boxed pattern in the maze, number of walls, etc.