Artificial Intelligence for Communications and Networks. Second EAI International Conference, AICON 2020, Virtual Event, December 19-20, 2020, Proceedings

Research Article

Evaluating Recursive Backtracking Depth-First Search Algorithm in Unknown Search Space for Self-learning Path Finding Robot

Download
576 downloads
  • @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
T. H. Lim1, Pei Ling Ng1
  • 1: Tungku Highway

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.