Spring 2021: DeRobot Mazebot Project
Finding a Robot’s Initial Position Using Pruning
Author/s: Alexander Littleton – Game Software Engineer
Table of Contents
Introduction
In this post, a method of finding the initial position inside of a graph using pruning is described. This post will start with the purpose of the proposed initial position finding method in the mazebot project. Afterward, the requisite background information required to understand the proposed method is described. Then the post ends with the description of the initial position finding method.
Initial Position Finding in the MazeBot Project
One of the core pieces of information required to have our robot successfully navigate the maze is the robot’s current position in the maze. Knowing the robot’s position is required for many core processes such as path-finding, decision making, and successfully not running through walls.
Our position tracking currently works as follows: The robot detects intersections that occur during room transitions. Depending on the robot’s current orientation, an index value is incremented by a specific value to obtain the new position. This method requires knowledge of the robot’s initial position inside the maze and the robot’s initial orientation.
We can currently detect the robot’s orientation using a magnetometer; However, we also need the robot’s initial position, which the method for finding this information is shown in this post.
Background Information
Graphs
The contents of the maze are stored as a graph. A graph is a data structure consisting of interconnected nodes to form a linked network of nodes. The reason why a graph was chosen is that a maze is a perfect representation of a graph. Each square is a node with the square’s information (walls, card, etc.) attached and has a finite amount of connections between other nodes (squares). An image of the maze constructed as a graph is shown in figure 1 below:
Figure 1. Maze Graph Structure
Initial Position Finding using Pruning
Description
The pruning method works by finding series of connected nodes that share common characteristics such as cards and wall structures. The robot will wander until a unique series of connected nodes is found, which will point out the robot’s location. The algorithm can be described as a four-step process where:
- Mark all squares that have the same configuration (wall structure and cards) as the currently occupied square
- Move in any legally travelable direction
- Go through each marked square and search the tile in the same direction as the robot moved
- Mark the square if it has the same configuration as the currently occupied square
- Repeat steps 2-3 until there is only one newly marked square, the newly marked square will be the currently occupied square
Example
An example of this algorithm is shown below:
First, we search the maze for similar wall configurations
Figure 2. Maze initial position finding iteration 1
We then need to move in a legal direction (north) and mark similar squares that are north to the previously marked square
Figure 3. Maze initial position finding iteration 2
We then repeat the previous step
Figure 4. Maze initial position finding iteration 3
Since we only marked one square this time we now know the robot’s location
Conclusion
In conclusion, this post proposed a method of finding the initial position inside a graph by using a pruning method. The post first stated that we needed the initial position in order for our position tracking code to work, which enables the functionality of our pathfinding system. Afterward, a review of graphs was given, which explained graphs as a series of interconnected nodes. Finally, the pruning method was shown, which showed that the method searched for unique strings of rooms inside a maze to find the robot’s current location.