Autonomous indoor robot navigation using Genetic Algorithms
Introduction
Autonomous navigation is a complex task. In this blog, I describe my attempt at developing an efficient autonomous navigation algorithm using as few resources as possible. Several variations of the problem arise depending on the situation, and complex problems such as autonomous cars and drones stem from this discipline.
In this project, however, I focused on a more modest objective, the Area Coverage problem. In short, this consists of getting an autonomous agent to visit every spot in an indoor environment just one time. This mind sound familiar, since its the problem Roombas have to solve every single day.
However, current autonomous vacuum robots aren’t that effective. Most of them incorporate random walk algorithms to navigate the environment, resulting in multiple unvisited areas while others have been visited many times. Maybe this is one of the reasons why they have not become very popular yet.
For a video presentation of this project, please see the youtube link below. If you'd rather read a full technical report, check out the report below.
The algorithm
The goal is simple, come up with an algorithm that allows the robot to navigate the room in the most efficient way possible. Genetic Algorithms are really useful for this purpose since they allow to find optimal conditions in complex situations, according to a cost (or value) function of our choice.
If you are not familiar with Genetic Algorithms, you might want to check some of my posts about the topic. One really important aspect of these algorithms is that they work with encoded information, and they are really useful to find absolute maximums and minimums, in contrast to most optimization methods that can only find local extrema.
The algorithm uses a representation scheme to encode a mini-path or a small section of its journey through the room. A batch of mini-paths is evaluated with respect to a value or cost function and some modifications are made based on the scores obtained. The idea is that through some pseudo-random modifications and a selection process the best solution can be found. This somewhat emulates natural selection. Together with the encoding of the information into chromosomes, is what gives its name to this algorithm.
In a first attempt, I defined a value function that took into consideration how many cells were visited for a given mini-path, and the amount of time it would take to perform such mini-path, according to the required number of turns. However, this solution favored straight lines due to the lower amount of turns and time required. This was not a good solution since the robot had a tendency to wander around and get stuck in tight gaps.
The solution to this problem was to introduce a cohesive factor, that is, introduce an element into the value function that offsets the extra time of a path that runs parallel to previously visited areas or walls compared to the straight line option. This can actually be tweaked so that the robot has a preference to follow the walls or to spiral around its already visited positions, which is similar to one of the most effective random walk algorithms.
The results
I have to say I was quite impressed with the final result. The algorithm performed remarkably well, it was tested in a simulation with several room shapes, sizes, and obstacle densities. The results of the simulation were represented as a heat map, in which white cells are unvisited, black cells are obstacles, green cells were visited only once, and yellow, orange, and red cells were visited 2, 3, or 4+ times, respectively.
In the simulations, this algorithm was tested against a standard random walk algorithm, and the results were impressive. While the time to clean a room increased exponentially with the room's size in the case of the random walk algorithm, this increase was only linear in the case of the genetic algorithm. The results can be seen in the following graphs:
Does this sound too good to be true? Well, it probably is. One of the main issues with path planning consists of accurately knowing the robot’s position so that it can correctly locate obstacles in space and navigate them. However, I still think this algorithm is one of the pieces of the puzzle and it stacks very well against current solutions. It is an improvement over some recent studies in the area and it surely can still be improved upon.
If you would like to know more about its advantages in terms of speed, how it can be implemented into a microcontroller with low computational resources among other things, please have a look at the video presentation I made on the topic for one of my Master’s classes at Purdue.