How do maze-solving robots work?

To plan and navigate a particular environment, you will need a model of that environment. Even if the model of the environment is perfect and free from noise, finding an optimal path to navigate the environment isn’t an easy task. Where the environment is static, the navigation technique will still have to deal with various obstacles and when the environment is dynamic the navigation becomes very complex.

Motion planning

You may think of the motion planning as the set of all possible transformations that could be applied to the robot. Given a particular environment and a robot to navigate, the goal is to start from a given location (current position) and navigate safely to the destination (final position). The environment can be modelled as the union of the set of all obstacles and the set of free (or available) space that the robot can traverse. The trajectory or the path that the robot will take from the current position to the final position can be modelled as the shortest path problem. The solution (algorithm/technique) the robot will use to navigate the environment is considered complete, if and only if a path from the current location to the final location exists and the solution is able to find it or returns a failure. Similarly, the solution is semi-complete if a path from the current location to the final location exists and the solution can find it or runs forever.

To understand the difference between complete and semi-complete navigation algorithms, we can model the environment as a maze and the navigating agent as a rectangular robot.

The aim is to navigate the environment from the start to the finish location safely. We can make some assumptions about the environment and the robot. The maze is made up of squares and the robot can detect an obstacle ahead, and estimate the distance of any obstacles to the left and right. We can look at the rules for three simple maze navigation algorithms:

1: Right-then-Left navigation

a. The robot should move forward until an obstacle is detected ahead

b. The robot should record the distance to the next obstacle on the right

c. The robot should record the distance to the next obstacle on the left

d. If the right obstacle is further away, then the robot should turn right else it should turn left. Thus, if the left and right obstacles are at the same distance the robot turns left

e. Go to step ‘a’ if the current location isn’t the final (goal) location.

With these rules, the robot from the start location will turn left at locations A, B and C, and eventually be trapped at location D and E.

2: Left-then-Right navigation

a. The robot should move forward until an obstacle is detected ahead

b. The robot should record the distance to the next obstacle on the left

c. The robot should record the distance to the next obstacle on the right

d. If the left obstacle is further away, then the robot should turn left else it should turn right. Thus, if the right and left obstacles are at the same distance the robot turns right

e. Go to step ‘a’ if the current location isn’t the final (goal) location.

With these rules, the robot from the start location will turn left at locations A and B then turn right at C, and eventually be trapped at location E and D.

These two navigation rules can be seen as a semi-complete solution as a path from the start to the finish exists, but the robot gets trapped in location D or E forever.

3: Wall following (right wall and left wall)

a. The robot moves forward by making small adjustments to keep parallel with the right wall (or left wall) until either:

• An obstacle is detected ahead and in that case the robot should turn in the opposite direction (left, if right wall following) of the wall being followed.
• There is no wall (right wall if right wall following), the robot should turn in the same direction (right, if right following) of the wall being followed.

b. Go to step ‘a’ if the current location isn’t the final (goal) location.

Either the right wall following, or the left following rule is capable of taking the robot from the start to the end location and is an example of a complete solution.