Mobile Bot Maze Solving

Question

I am using ROS melodic on ubuntu 18.04

I have a simple 2 wheeled mobile bot, with a lidar attached to it. It is kept at the entrance of a maze (any maze). The bot has to "solve" the maze, i.e. exit it, using the shortest possible path. We get 30 seconds first to "map" the maze.

First, using odometry and laser data, I used the slam gmapping package to try and create a map of the maze. I used a rudimentary algorithm (out of the three directions right ,left and straight, it choses the one with the most free space), just to check out if the mapping process is working out, and it indeed is. I am getting a fairly accurate occupancy grid till the time the algorithm runs properly (it runs into problems later).

From what I understand, after an appropriate map (occupancy grid) is obtained, we can apply graph algorithms like A*,RRT,RRT*etc. to obtain the optimum path.

However, I am confused regarding creating the appropriate map in the first place. I mean, I have the package working properly that will create the map for me, but what kind of algorithm should I implement to ensure a path is taken from the starting of the maze, to the end of the maze, and back to the start? (To create the appropriate map). The main issue here is that we also have to deduce weather we have reached the end of the maze or not.... We cannot hard-code the location of the maze as the algorithm has to be general.

In short, the main problem I have is not "how to create a map", but rather, "what path should the robot take so that the map it creates is appropriate for the purpose".

Answer 1

Here's a video of a micromouse competition. The video starts with what I believe you're looking for - a mapping run.

How do you ensure you have appropriate coverage, though? It's up to you to define appropriate coverage. Is it okay to find one route to the end, or should you find all routes to the end?

If the end point isn't defined in advance then you need to explore the entire map. The most straightforward way to do that would be:

1. Collect the number of new available options,
2. Take the first available option and advance one space,
3. If it's not a dead end, go to 1 and repeat.
4. If it is a dead end, go back to the last intersection where you had new options and take the next available option.

If you're tracking/eliminating new options as you continue then when you fully exhaust one branch you should wind back up at your starting position and go down the next branch of possible options. You can do all kinds of tricks to try to optimize the mapping run, and you'll need safeguards to protect against pitfalls like what to do if you enter a grid location you've previously discovered (hint: treat it like a dead end!).

The type of data structures you choose to represent your map and the particular algorithms you use to build that map are your choice and will either make the problem really difficult or relatively simple, but that's what programming's all about!

Answer 2

what kind of algorithm should I implement to ensure a path is taken from the starting of the maze, to the end of the maze, and back to the start?

This is an exploration-exploitation problem. Please see this article for an overview of the challange and this paper for an example of how researchers approached a similar problem.

Basically, you need a decision criterea to govern the robot's behavior in a way so that it explores the environment without attempting to actually find the goal. As your robot learns more about the environment, it may stumble across the goal or find guides toward the goal that help it to exploit this goal. In practical RL research, this is often implemented by an exponentially decreasing exploration-exploitation tradeoff $\alpha=e^{-\beta t} \in [0,1]$.