St Albans Robots

Flood Fill
The following image shows how Flood-filling can find the shortest path

Search for "Flood Fill Maze" in google.

Introduction to Maze Solving

A straightforward approach to Maze Solving is to separate out the physical :

control of the robots motors,
and sensing of walls,

from the logic of keeping track of

where the robot is,
Which cells have been visited
Where the end cell is
and possible routes to the end cell.

There are a number of programs for solving the logic,
but they all depend on the proper control, and measurement of the robot's position.

Control of the robot

There are four manoevres that are needed to negotiate a maze:

Go forward 1 cell
Turn left
Turn right
Turn about.

For each of these the robot starts in a standard position relative to the cell:

and finishes in the corresponding position in the "next" cell.

This could then in theory traverse a maze under control of a human pressing one of 4 buttons when the robot stops.
A sample program in BASIC is here

The place of the human is taken by the maze solver program for a real robot maze solver.

A very simple solver program could just do left wall following,
which would be a way to test the four manoevres.

Here is a link to a BASIC solver,
and a C++ solve and its include file

Maze solving programs

There are two approaches to flood filling.
The Classic number approach is where each cell is one greater than the minimum of its four surrounding cells.
Target is zero, and the whole maze is processed row-by-row, again and again, until no more cells change value.
Latestexample of this ( in Python) is in this file solver_F2.py (download) (view)

Older version CPPSolver (download) (view)

An earlier approach - which requires less memory, just stores one of four codes (UP,DOWN,LEFT,RIGHT) in the same cell as the wall codes,
The maze is filled by considering all 4 cells around each on the previously filled cells.
It uses a list of cells previously filled, and constructs a new list for the next cycle.
It stops when there are no more cells to be considered.
An example of this ( in Python) is in this file solver_PicOne.py (download) (view)

Control of the robot movement.

Wheel encoders

We have fitted encoding discs to the inside of both wheels of robot UKM5:

These are monitored by optical sensors mounted over the motors, and feed in to the Pico chip on the
inputs previously used for the motor encoders.

WE have only 1 sensor for each wheel, so we can't tell whether it's moving forwards or backwards,
but we know which direction we are powering the motor, so it doesn't matter.

The measurement of the wheel rotation allows us to turn accurately 90 (or 180) degrees when required,
and also to move forward by exactly one cell when required.

Wall sensors

These allow us to keep the correct distance from the wall when going down a straight path, and importantly
to detect which walls are ahead of us.

If a wall is missing, and we are going straight ahead, we should use the other wall instead , for steering.

Distance correction:
When going forward , the robot should check for significant changes in the presence of the side walls.
If a wall suddenly disappears, or appears, that indicates it is nearly at the correct position for the end of
the forward movement. It resets the target distance tobe the current position plus a fixed amount.

However, if the "wall present" tuning is incorrect it can see one or more false breaks in the wall,
and therefore readjust the distance too soon,
It can also repeatedly re-adjust, causing it to keep moving forward beyond the end of the cell.

1 The wall detection should be correctly tuned, so that it correctly identifies continued wall presence.
2 It should use hysteresis tohave a higher threshold for detecting "present" and a low threshold for "absent".
3 It should only cottect once per forward movement, and only reduce the distance.

An example of a log is shown below1,0,1,+ 1,0,1,+ 1,0,1,+ 1,1,0,> 1,1,0,> 0,1,1,<