Navigating through a Maze using path-planning (Dijkstra)

Question

I'm working on an robot that would be able to navigate through a maze, avoid obstacles and identify some of the objects in it. I have a monochromatic bitmap of the maze, that is supposed to be used in the robot navigation.

Up till now I have processed the bitmap image, and converted it into an adjacency list. I will now use the dijkstra's algorithm to plan the path.

However the problem is that I have to extract the entrance point/node and exit node from the bmp image itself for dijkstra's algorithm to plan the path.

The robots starting position will be slightly different (inch or two before the entrance point) from the entrance point of maze, and I am supposed to move to the entrance point using any "arbitrary method" and then apply dijkstra algorithm to plan path from maze's entrance to exit.

On the way I have to also stop at the "X's" marked in the bmp file I have attached below. These X's are basically boxes in which I have to pot balls. I will plan the path from entrance point to exit point , and not from the entrance to 1st box, then to second, and then to the exit point; because I think the boxes will always be placed at the shortest path.

Since the starting position is different from the entrance point, how will I match my robot's physical location with the coordinates in the program and move it accordingly. Even if the entrance position would have been same as starting position there may have been an error. How should I deal with it? Should I navigate only on the bases of the coordinates provided by dijkstra or use ultrasonics as well to prevent collisions? And if we yes, can you give me an idea how should I use the both (ultrasonics, and coordinates)?

Answer 1

You will probably want to use a combination of encoders to track the distance that you robot travels as well as ultrasonic sensors to detect the walls of your maze and correct for any minor inaccuracies in your robot's driving.

This sounds somewhat similar to the collegiate Micromouse competition that IEEE and other organizations hold in which small wheeled robots compete to first solve a maze and then run through it in the shortest time possible. If it so happens that the boxes aren't placed in the shortest path, you can find the shortest path between all cells (if I can remember correctly) using the floodfill algorithm (Bellman-Ford) described in the second link.

Links:

Wikipedia article: https://en.wikipedia.org/wiki/Micromouse

Algorithms: http://www.robotix.in/rbtx09/tutorials/m4d4

Answer 2

The original question, how to plan a path from A to B, is well studied, and the Dykstra algorithm is a good start. However, as you are realizing, Dykstra only establishes a series of waypoints and you are expected to maneuver to those waypoints.

If you can be expected to be dropped within a given tolerance of the start coordinates, then you can check physical dimensions to see if that tolerance matters. For example, if each box on your map is 25cm by 25cm in real life and your vehicle is completely contained within a 10cm circle, you can accept a location mismatch of up to 7.5cm, assuming you do not travel diagonally and you have perfect odometry to dead reckon the rest of the map.

Now, if you don't know the tolerance on position, or if you do but it's so large that it impacts your ability to navigate, but your heading is known, then you again have an easy fix. Measure the distance from your actual start location to the nearest wall, then move back/forward until you are in the correct position, then turn 90 degrees and do it again. Return to the original heading, knowing now that you are in the correct starting position, then proceed to maneuver.

The last case is the worst case - your starting position variation is unknown or too large OR your starting heading is unknown. If this is the case you need to determine your location and heading, and this is typically done via an algorithm called SLAM - simultaneous localization and mapping. My only comments here are to point you in the right direction and wish you luck as I have no practical experience with SLAM algorithms.

So, to summarize, either: 1. The starting tolerance is known AND small enough to not matter AND starting heading is known - do nothing =OR= 2. The starting tolerance is unknown OR too large AND your heading is known - localize with 1D rangefinders =OR= 3. The starting tolerance is unknown, too large, or your heading is unknown - use a SLAM technique.