About | Contact Us | Register | Login
ProceedingsSeriesJournalsSearchEAI
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(Requires a free EAI acccount)
871 downloads
Cite
BibTeX Plain Text
  • @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.

Keywords
Maze solving Search space Graph theory Search tree Depth first search Cul-de-sac
Published
2021-07-16
Appears in
SpringerLink
http://dx.doi.org/10.1007/978-3-030-69066-3_47
Copyright © 2020–2025 ICST
EBSCOProQuestDBLPDOAJPortico
EAI Logo

About EAI

  • Who We Are
  • Leadership
  • Research Areas
  • Partners
  • Media Center

Community

  • Membership
  • Conference
  • Recognition
  • Sponsor Us

Publish with EAI

  • Publishing
  • Journals
  • Proceedings
  • Books
  • EUDL