Research Article
Evaluating Recursive Backtracking Depth-First Search Algorithm in Unknown Search Space for Self-learning Path Finding Robot
@INPROCEEDINGS{10.1007/978-3-030-69066-3_47, author={T. H. Lim and Pei Ling Ng}, title={Evaluating Recursive Backtracking Depth-First Search Algorithm in Unknown Search Space for Self-learning Path Finding Robot}, proceedings={Artificial Intelligence for Communications and Networks. Second EAI International Conference, AICON 2020, Virtual Event, December 19-20, 2020, Proceedings}, proceedings_a={AICON}, year={2021}, month={7}, keywords={Maze solving Search space Graph theory Search tree Depth first search Cul-de-sac}, doi={10.1007/978-3-030-69066-3_47} }- T. H. Lim
Pei Ling Ng
Year: 2021
Evaluating Recursive Backtracking Depth-First Search Algorithm in Unknown Search Space for Self-learning Path Finding Robot
AICON
Springer
DOI: 10.1007/978-3-030-69066-3_47
Abstract
Various path or route solving algorithms have been widely researched for the last 30 years. It has been applied in many different robotic systems such as bomb sniffing robots, path exploration and search rescue operation. For instance, an autonomous robot has been used to locate and assist a person trapped in the jungle or building to exit. Today, numerous maze solving algorithms have been proposed based on the some information available regarding the maze or remotely control. In real scenario, a robot is usually placed in an unknown environment. It is required for the robot to learn the path, and exhibit a good decision making capability in order to navigate the path successfully without human’ assistance. In this project, an Artificial Intelligence (AI) based algorithm called Recursive Backtracking Depth First Search (RBDS) is proposed to explore a maze to reach a target location, and to take the shortest route back to the start position. Due to the limited energy and processing resource, a simple search tree algorithm has been proposed. The proposed algorithm has been evaluated in a robot that has the capability to keep track of the path taken while trying to calculate the optimum path by eliminating unwanted path using Cul-de-Sac technique. Experimental results have shown that the proposed algorithm can solve different mazes. The robot has also shown the capability to learn and remember the path taken, to return to the start and back to target area successfully.