An In-Depth Look

Maze Generation

We use an undirected graph as our source of ground truth for the maze.

It begins with a text file that represents the walls of the maze.

Rows with stars represent vertical walls, and rows with X’s represent horizontal walls.

The stars and X’s simply represent empty space and help to visualize the maze.

A space represents the absence of a wall and a “-” or “|” represents a wall.

We wrote programs that convert this text into a NetworkX graph, and into an STL using Trimesh.

Maze Solving

Dijkstra's algorithm uses the concept of a priority queue, and efficiently works its way to the shortest path between a start and end point. Once the algorithm sorts to the end point, it is guaranteed to solve for the shortest path from the start to end point. The time complexity of Dijkstra's algorithm is O(E log V), where E is the number of connections between the node and V is the number of nodes or junction points in the maze.

The base case is we are looking at a neighboring node, and the shortest-yet cumulative path to that place is the shortest we've yet written down. When you encounter the shortest path to a neighbor, note it! You associate the sum total of distance traveled and the node you're coming from with that neighbor's record, then sort that node by its cumulative distance (likely into a top-20% place on the list but not first), then move onto the 1st place position, until finished. Low-scoring nodes get visited first that way.

We did a deep dive into Dijkstra's algorithm and implemented it ourselves. Later, in the final version of the code, we used the NetworkX implementation of Dijkstra's algorithm to integrate with the graph generating code.

Motion Control

Movement Planning

Our motion control node takes in a solution path of ordered nodes to a maze. If the path is [A, B, E, H, I] as shown left, it sends motion commands to the Neato to move through each of these nodes in order.

Our maze solution path is given as a list of (row, column) tuples. Because the maze is an evenly sized grid of 1x1 meter boxes, the x-y position coordinate (in meters) of each node can be inferred from its row and column number. For the maze pictured right, the list of nodes as (row, column) tuples would be [(1, 1), (2, 1), (2,2), (2,3), (3, 3)].

To know what direction it has to move in, the Neato uses the displacement between its current node and its target node. It orients itself to the angle the displacement vector drawn from its current node to its target node faces, and moves one unit distance in that direction.

The Neato can cycle through an entire solution path in this way.

Path Correction

To prevent drift of the Neato over time, we use LiDAR data to detect when the Neato has drifted off its intended path. A perfect path through the maze would travel through the center of each aisle. In a maze with corridors 1 meter across, this means that the center of the Neato should always be at least 0.5 meters from any wall.

In reality, a Neato doesn't always make perfect 90 degree turns or travel exactly 1.0 meters when you command it to. To account for this, the Neato periodically checks the distance between itself and the wall to its left, its right, directly ahead of it, and directly behind it. If it ever detects something closer than about 0.4 meters from it, it will adjust by veering away from a wall or moving slightly forward or backward. Additionally, if it senses it's too far from a wall it should be closer to (for example, a wall straight ahead is greater than 0.5 meters away but less than a full 1 meter away), it moves closer. This is a relatively simple form of path correction and could be made more robust.

Page updated

Google Sites

Report abuse