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

Shadman Sakib, Anik Chowdhury, Shekh Tanvir Ahamed, Syed Imam HasanarXiv 2014 · arXiv

TL;DR

This paper presents a novel, general algorithm for autonomous robots to map and solve any type of line maze, including those with loops. It introduces a method to accurately derive linear path distances from noisy wheel encoder data, crucial for precise navigation in complex environments.

What Problem Does This Paper Address?

Navigating complex mazes autonomously is a long-standing challenge in mobile robotics. Existing algorithms often struggle with mazes that have unknown goal locations, loops, or require finding the absolute shortest path. Furthermore, accurately measuring distance traveled by a robot, especially when its movement isn't perfectly linear due to motor imperfections, is critical for mapping and path planning. This paper addresses these issues by proposing a comprehensive approach that combines robust maze mapping with precise distance calculation.

Methods

The paper proposes two main algorithms. The first is a simplified approach for "no-loop" or "short loop" mazes, which is an enhancement of the classic "follow-the-wall" strategy. It uses a preference-based direction selection at junctions and recursively updates a direction array to find a path.

The core contribution lies in the second, general algorithm for any maze type. This algorithm focuses on mapping the entire maze by representing it as a graph using an "Adjacency-list representation." The robot explores the maze, identifying and recording turning points and junctions. It uses a coordinate system and direction tracking to build this graph. A key innovation is the derivation of equations to accurately calculate linear path distance from wheel encoder readings, which are inherently noisy due to non-linear robot movement (imperfect alignment and differing motor speeds). This involves analyzing the robot's curved path and deriving formulas that account for these deviations.

Datasets

Not discussed in the paper. The paper uses a simulated maze (Fig. 2) for demonstration and presents sample measured path distances in Table I.

Key Insights and Ideas

  • General Maze Solving: The paper moves beyond specific maze types to offer a unified approach for mapping and solving any line maze, including complex ones with loops.
  • Graph-Based Mapping: Representing the maze as a graph (Adjacency-list) is a powerful way to store topological information and enable algorithmic pathfinding (like Dijkstra's).
  • Linearizing Encoder Data: The most significant technical contribution is the derivation of equations to correct for non-linear robot motion and extract accurate linear distances from wheel encoder data. This is crucial for precise localization and mapping.
  • Handling Real-World Robot Imperfections: The paper explicitly addresses two major sources of error in robot navigation: imperfect alignment with the line and differences in motor speeds, and provides a mathematical framework to compensate for them.

Key Results

The paper demonstrates the effectiveness of its algorithms through a case study maze (Fig. 2) and presents sample measured path distances in Table I. The table shows that the derived formula provides path distances very close to the actual lengths, with minimal error (generally ±3% as noted in Fig. 3 caption). The authors suggest that incorporating a Kalman filter could further reduce error, though they also note that the wheel encoder signal itself appears steady enough not to strictly require filtering.

Limitations and Future Work

Limitations: * The paper mentions that mazes with a very large number of nodes might require ICs with high computational power. * While the derived equations are presented as accurate, the paper acknowledges that the error is generally ±3%.

Future Work: * The authors suggest that the proposed algorithm can be extended beyond line following to applications like autonomous road mapping, cave mapping, and general exploration. * For such applications, low-cost GPS devices could potentially replace wheel encoders for coordinate tracking. * The paper implies that further refinement of the distance calculation equations or the integration of advanced filtering techniques (like Kalman filters) could lead to even greater accuracy.

Summary updated

BibTeX
@misc{sakib2014maze,
  author = {Shadman Sakib and Anik Chowdhury and Shekh Tanvir Ahamed and Syed Imam Hasan},
  title = {{Maze solving Algorithm for line following robot and derivation of linear path distance from nonlinear path}},
  year = {2014},
  eprint = {1410.4145},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1410.4145},
}
Figure