Introduction

In fulfilling this Milestone, we needed to deviate from our Right-Hand-Rule following strategy to a more robust method. We chose a variation of DFS to accomplish this. The main structures we used were a stack of visited nodes, and a stack of "seen" nodes, or nodes that we had access to but didn't visit.

Basic Organization of Tasks

One of the most difficult parts of this task was determining where to start. We began by first outlining what actions we thought we could expect from our robot that would be robust enough to handle any situation.

  1. Reach a target position (targetX, targetY)
  2. Update wall and treasure information about this position
  3. Push traversable nodes onto a stack
  4. Choose a new node's position (*targetX, *targetY)

This plan takes care of a raw version of maze exploration, but there was one major corner case for us to deal with: getting into a dead-end situation, our robot would need to be able to retrace its steps somehow and find new nodes. This we accomplished quite simply by retraversing the stack we dynamically created of our visited locations. Below, you can view some sample mazes we had our robot run. Most of the troubleshooting involved in this process were maintenance of logical identities as we passed parameter values across many files; for example, passing wall information from our sensor file to our algorithm, then back out to our main loop to be passed into our radio gave us some difficulty.

DFS Test 1

Here, we just wanted to determine that our robot was adding new nodes to the stack where possible. Notice that in our impmlementation of DFS, a left turn is prioritized over a right turn. This was in part because we knew that we would be starting our robot in the left corner of our maze, but coudl very easily be changed by just changing the order of pushes to our stack.

DFS Test 2

This test is mostly reviewing that our robot can retrace its steps until it reaches a point where new nodes are available. Here, we see it trace a pattern into a dead-end before coming back to the start and exploring the other fork.

DFS Test 3

And once more we extensively test the ability for our robot to backtrack and continue maze exploration. At this point, we are quite happy with our DFS implementation and believe everything is in working order.

Conclusion

LABron was successful in completing the maze using our logic. However, as we switched over to the larger maze, we began to run into major mechanical issues. For instance, debris left throughout the maze area made line tracing erratic and would often lead to our robot being thrown off course or jammed at an intersection. Most unfortunate was the non-level surface upon which the maze was laid out, creating large lumps that would catch on our line sensors and pin LABron between intersections. For this reason, we were unable to post a large maze video.