• Home
  • Pages
    • Labs
    • Milestones
    • Team
    • Documents
  • Gallery
  • Robot Design
  • Software Design
Robots 'N' Roses

Goal

Our robot is capable of maze exploration using DFS, BFS, Dijkstra, or A* as well as update the GUI with the correct information. We implemented this using DFS with BFS backtracking rather than right-wall following to navigate the maze because DFS allows us to explore the open areas of the maze unaccessible to right-wall following without the extra complexity of Dijkstra’s or purely BFS algorithms.

Materials

2 Arduino Unos

Radio Chips

1 USB A/B Cable

2 Continuous Rotation Servos

2 Line Sensors

1 Battery Pack

Laser Cut Acrylic and 3D printed Custom Lab Assembly Pieces

Microphone

Breadboard

IR Wall Sensor

Data Structures

We used a struct node to keep track of each intersection in the maze (Figure 1). Each node contains fields node_dir and visited. Node_dir keeps track of the direction the robot was facing when it first visited that node. Visited is a bool that keeps track of whether the node was visited or not. We keep track of each node in maze, a 9x9 array. Nodes are identified by their indices in the matrix (eg. intersection at y = 1 and x = 2 is the node at maze[1][2]).

We first access the current node in maze and check if it has already been visited. If not, we update the node’s node_dir to the direction the robot is facing when it entered the node (prev_dir). Then, we set that node to visited.

DFS Continued

We then calculate the (x,y) positions of the adjacent nodes and decide if they are blocked (Figure 5). We use helper functions get_x() and get_y() to calculate positions (Figure 4). get_x() and get_y() take in parameters: position in the maze (x or y, respectively) and the direction the robot has to travel to get from the current node to the adjacent node. The functions return the x or y values of the position of the adjacent node.

Still more DFS

To decide whether the path to a adjacent node is blocked, we check if a wall is present. If not, we check if the adjacent node has already been visited (Figure 6).

After figuring out which paths are blocked, we update global variable dir to let the robot know its next cardinal direction. If all directions are blocked, we backtrack until we find a node where at least one direction is not blocked (BFS) (Figure 7).

After deciding the next direction, the position of the next node to be visited is updated, and the function returns. dfs() is called every time the robot reaches an intersection.

Implementation and Testing

We first implemented DFS in the Matlab simulation provided by Team Alpha. After we got our algorithm to work on Matlab, we ported the code to our robot.

This is what the Slash does in the final implementation.

Copyright © 2016 - All Rights Reserved - Domain Name

Template by OS Templates