Maze Solving Robot

The brief for our Embedded Systems Design module: build a robot that enters an unknown two-part course - a 4 x 4 walled maze that leads, via a line-following corridor, into a 9 x 9 maze - maps it completely, then comes back and beats it by the shortest path. Two constraints shaped every design decision. The mapping run and the solving run are separate, so everything the robot learns has to survive a power cycle. And there is no external positioning - the robot's only knowledge of where it is comes from its own wheels and sensors.

Hardware

Way-Finder is built around the Arduino Mega 2560 with a modular software architecture and DIP-switch mode selection:

• Microcontroller: Arduino Mega 2560
• Motors: 2 x DC Geared Motors with Quadrature Encoders (360 counts/rev)
• Motor Control: Dual H-Bridge Motor Driver (TB6612/L298N)
• Distance Sensing: 3 x HC-SR04 Ultrasonic Sensors (Front, Left, Right, and additional angles)
• Line Detection: QTR-8A/8RC 8-Channel IR Line Sensor Array
• Power System: 12V 1500mAh Rechargeable Lipo Battery + 5V Buck Converter
• Mode Selection: DIP Switch for operational mode selection
• Mechanical Design: Custom 3D-printed chassis with laser-cut acrylic layers

One course, three navigation problems

The course mixes environments that need different sensing, so the robot runs distinct modes and switches between them - each mode trusting the sensor best suited to its terrain.

1. Line following (the corridor)

On the connecting corridor the robot is a pure line tracker: the 8-channel IR array is reduced to a weighted positional error, and a tightly tuned PID controller converts that error into smooth lateral corrections without giving up forward speed.

• Weighted IR-based position estimation with PID control
• Automatic junction and turn detection
• Adaptive speed regulation with error smoothing

2. Wall following (the 4 x 4 maze)

The small maze has walls but no lines, so navigation switches entirely to ultrasonic sensing and encoder feedback. A consistent wall-following strategy makes junction decisions without any prior knowledge of the layout, while encoder-counted turns and distance-thresholded wall detection keep cell-to-cell movement predictable in tight spaces.

• Ultrasonic-based wall detection with fixed distance thresholds
• Real-time junction decision making
• Encoder-accurate 90° and 180° turns

3. Exploration run (the 9 x 9 maze)

Inside the 9 x 9 maze the robot explores systematically, recording wall connectivity and cell transitions as it goes. After covering the maze and locating the goal, it returns to the origin and writes the complete maze representation to EEPROM - the whole point of the first run is to make the second one trivial.

• Sequential navigation across 4 x 4 and 9 x 9 maze domains
• DFS-based maze registration and mapping
• Persistent storage of maze data in EEPROM

4. Solving run

On the second run the robot re-enters the course, loads the stored maze from memory, computes the shortest path, and executes it - no exploration, no hesitation at junctions.

The decisions that mattered

DFS to explore, Flood Fill to solve

These are two different jobs, and we deliberately used two different algorithms. You cannot claim a shortest path until every wall is known, so the exploration run uses stack-based depth-first search with backtracking - it guarantees full coverage, and its bookkeeping (a visited-state stack plus a wall grid) fits comfortably in the Mega's limited RAM.

Once the map exists, Flood Fill takes over for the solving run: each cell is assigned a Manhattan distance from the goal, values propagate outward from zero, and the robot simply follows the descending gradient. Splitting the problem this way means neither algorithm has to compromise - coverage is guaranteed during mapping, optimality during solving.

Surviving the power cycle

Because the solve run can happen after a reset, the maze representation is serialized to EEPROM with magic-number validation - the robot can tell a genuine stored map from uninitialized memory before trusting it.

Trusting the encoders

With no external positioning, all odometry is dead reckoning on quadrature encoders (360 counts/rev), which only works if the constants are right. We calibrated straight-line traversal of one 25 cm maze cell to 288 encoder ticks, and in-place rotations to 116-117 ticks per wheel for 90° and 232-233 for 180° - giving turn accuracy within ±2°. Those numbers came from repeated physical trials, not the datasheet.

Control systems

The left and right DC motors run independent closed-loop PID controllers on encoder feedback, and three sensor systems are fused per mode:

• Ultrasonic Sensors: Wall detection and distance measurement (20cm threshold)
• IR Line Array: Tile boundary detection and line following
• Encoder Feedback: Precise position tracking and odometry

Mechanical design

The chassis is custom-designed around maze navigation rather than adapted from a kit:

• Chassis Material: 3D-printed frame with laser-cut acrylic layers
• Wheelbase: 15.5cm for stable turning
• Wheel Diameter: 6.0cm (65mm robot wheels)
• Sensor Mounting: Custom 3D-printed ultrasonic holders with 3-5° down-tilt
• Weight Distribution: Battery placement chosen for center of gravity
• Modularity: Two-layer design allows easy access to electronics

Software architecture

The firmware separates responsibilities so each navigation mode could be developed and tuned independently:

• Mode Manager: Central state machine for mode selection and transitions
• Algorithm Modules: Independent namespaces for each navigation algorithm
• Utility Functions: Shared motor control, sensor reading, and PID calculation functions
• Constants Management: Centralized configuration for tuning parameters
• EEPROM Manager: Persistent storage with magic number validation
• Interrupt Handlers: Efficient encoder counting with atomic operations

What the maze taught us

The algorithms were the easy part. What the project actually taught was the distance between simulation and physical hardware: ultrasonic mounts that needed a deliberate 3-5° down-tilt before readings became trustworthy, encoder constants that had to be established through repeated trials, and PID gains that only mean something once the robot is on real wheels - real-time control on a resource-constrained platform is a different discipline from getting the theory right.

Contributors

• Gayanuka Amarasuriya
• Sanuda Amasith
• Kaviru Nimsith
• Tharumal Dinuranga

For more details, explore the GitHub repository containing complete source code, mechanical design files, and documentation.