RRT-Based Robotic Exploration Algorithm                        10/2023 - 04/2024
--------------------------------------------------------------------------------

This project aimed to develop an algorithm to enable autonomous robotic
exploration of uncertain environments. It used the properties of RRTs to aid in
the path planning process and identify frontier regions that indicate potential
for information gain.

In order to do this, I first developed my own simulation environment in Rust,
using the MiniFB crate for graphics and using Unix sockets for communication
between the algorithm (which ran as a separate process) and the simulator. The
simulator relies on using different color pixels to represent different aspects
of the environment. Using this color-based scheme to encode information about
the environment allowed a lot of flexibility in how the environment could be
constructed, and so I was able to construct completely random environments with
varied configurations and unique obstacle arrangements and shapes.

    

    

Some examples of environments generated by the simulator. While I opted to use
rectangular obstacle components for ease of generation, the algorithm would work
exactly the same even if the obstacle components were some other shapes.
--------------------------------------------------------------------------------

With obstacles that are randomly generated and that are sometimes irregularly
shaped like these, tracking them by encoding each feature of the environment as
a different color allowed me to directly use the simulator's visual output
as a means of tracking everything about the environment, like in this image:


The visual output of the simulator as the robot is exploring.
--------------------------------------------------------------------------------

Here you can very clearly see the area that has been explored so far (in light
yellow), the obstacles (in purple), the robot's FOV (in bright yellow), the area
that hasn't been explored yet (in black), the robot's location (in red), and the
path followed by the robot (in cyan). It doesn't matter that these are
irregularly shaped, because each pixel is tracked individually and identified by
its color. And, this also makes it convenient to share information with the
exploration algorithm.

The exploration algorithm itself works by growing an RRT within the space that
has been explored by the robot so far, and within a small margin just outside
this space. The nodes that fall within the margin just outside the explored
space are considered "frontier nodes," and these are the nodes that indicate
potential for information gain and that the robot attempts to move between.


Simulator with rendering of RRT. Notice how it extends into the black area.
--------------------------------------------------------------------------------

The benefit of using the RRT algorithm, especially in environments so varied
like these, is that it can grow around obstacles given that the location of the
obstacles is known, and so it makes for a nice method of planning paths in
complicated environments like these. Even in really cluttered environments, the
RRT has no trouble growing around obstacles to find a viable path.

Through my testing, the exploration algorithm I developed based off this concept
performs relatively well, being able to explore over 80% of the free space in
environments with a reasonable amount of obstacle clutter. In obstacle-dense
environments the algorithm sometimes struggles, but even in these cases it can
usually reach around 40-50% coverage of the free space.

I presented this project at SASEF 2024 and won several awards for my work, and I
continue to pursue an extension of this project.

<<< Go back