Colin Taylor-McGrane Capstone
For my senior project, I created a maze, outlined all possible motions in tape, and programmed a small VEX robot to navigate it. I discovered that most conventional mazes are composed of two pieces that fit together. Therefore, all mazes can be solved by following the left or right wall from start to finish. To give the robot the means to navigate the maze, I outlined all of the possible directions the robot could travel in black tape. The bottom of the robot was equipped with three infrared sensors. These sensors worked by shooting infrared light down at the ground and detecting the light that bounces back. Because of the light absorption of the black tape, the light detected bouncing off of the black tape will be different. I ran through many different maze designs, trying to create one that would have as many points of choice as possible that could fit on a flattened tri-fold board. It took several tries, but I finally succeeded by erasing lines on a 4 by 5 grid until I created a viable maze. After I created the code, I placed the robot on a the maze and let it run through. After observation I adjusted the speed of the robot and the code governing action at intersections. I also added additional strategically placed tape at T-junctions to ensure that the robot detects the black tape with its left or right sensor.
Autonomously Solving Mazes with Robots (1).pdf. (2017, July 21). Retrieved January 25, 2019, from https://soe.rutgers.edu/sites/default/files/imce/gov2017/Autonomously%20Solving%20Mazes%20with%20Robots.pdf
This source is an experiment done with autonomous robotic navigation of mazes done at Rutgers University done by a group of 6 graduate students. The students were attempting to figure out how to use programming techniques in order to allow robots to figure out how to find the fastest possible route through a maze. Their research was inspired by the ability of Google maps to figure out the exact fastest route to a certain location. The students believed that this software could be very useful for autonomous robots and vehicles. I would use this source to find out what exactly the programing techniques they used are and how they are applicable to the maze.
Blynel, J., & Floreano, D. blynel_evorob03.pdf. Retrieved January 24, 2019, from https://pdfs.semanticscholar.org/fc84/cf42f04d6474a9fc92117957ef695f976030.pdf
This article discusses the application continuous time recurrent neural networks as they allow robots to navigate T-mazes, which are a specific type of maze. This article describes the computational mainframe of the robot in terms of genomes and neural networks. This source also presents many different mathematical equations that can be used in order to guide the robot through the maze. This source also presents information relating to how the data from T-maze navigation can be used in order to navigate more complex mazes in the real world. This source will be used in order to find some of the math and programing techniques necessary for allowing a robot to navigate the maze.
Duchon, A. Maze Navigation Using Optical Flow. Retrieved January 24, 2019, from https://pdfs.semanticscholar.org/7360/030567921a978e1a5a7b531e57564be93992.pdf
This article is an article discussing a sensory method of navigating mazes known as optical flow. This article is written by Andrew P. Duchon, a professor in the Department of Cognitive and Linguistic Sciences at Brown University. This article details how the process of Optical flow works on a computational level in addition to describing how it can be used both in the context of small scale robotic maze navigation and in the large scale movement towards automation. The article details many different methods in which Optical flow can be used for navigational purposes. This information will be tremendously useful when coming up with navigational algorithms.
Han, K. (2007, August). COLLISION FREE PATH PLANNING ALGORITHMS FOR ROBOT NAVIGATION PROBLEM. Retrieved January 24, 2019, from https://mospace.umsystem.edu/xmlui/bitstream/handle/10355/5021/research.pdf?sequence=3
This article details a specific algorithm that can be used to allow robots to navigate mazes and obstacle courses without collision. This algorithm was used by graduate student Kyung min Han under the supervision of Dr. Robert W. McLaren at the University of Missouri Columbia. This article also discusses an algorithm known as Genetic Algorithm in which a robot can determine which possible navigation solution is the most efficient. This article also discusses how this solution is used in nature, bringing up the examples such as Ants and the Human genome. This article is useful because it provides an example of someone conducting similar research to mine, using a specific algorithm.
Harsh, S., & Bird, J. (2012). ME 597D Spring 2012, Group 2 Camera Based Maze Navigation. Retrieved January 24, 2019, from https://www.mne.psu.edu/brennan/ME545/2012/Lesson22_LAB_PathPlanning/Group3/Group2MazeNavigation.html
This source is an article written by Saurabh Harsh and John Bird of the Department of Mechanical and Nuclear Engineering at Penn State University. This source goes into great detail describing an experiment done in which they tried to get a robot to successfully navigate the maze using certain censors. This source will be used to determine ways in which the robot can use sensory information to navigate the maze. This source will also be useful for gaining insight into how the robot computationally processes the information it observed and use it. This source will be tremendously useful when trying to figure out the navigational algorithms.
Implementation of the Trémaux Maze Solving Algorithm to an Omnidirectional Mobile Robot. (2014, January). Retrieved January 24, 2019, from 328138637_Implementation_of_the_Tremaux_Maze_Solving_Algorithm_to_an_Omnidirectional_Mobile_Robot
This source is a conference paper about a specific maze solving algorithm known as the Trémaux Algorithm which can be used to allow robots to solve mazes. This source was written by Lim Kai Li a researcher at Sunway University. This source details how the robot analyzes each pathway of a maze using numerical values in order to solve the maze. I will be using this source in order to find useful aspects of the Trémaux Maze Solving Algorithm in order to find which aspects will be useful in creating my own personal algorithm. This source has many useful details about how this algorithm works.
McKinley, P., & Clark, A. Solving VEX Robot Maze. Retrieved January 24, 2019, from https://www.egr.msu.edu/future-engineer/sites/default/files/content/Payson-Charles-poster-SolvingVEX.pdf
This source is a slide detailing some experimentation that has been done with robotic navigation of various different mazes. This slide was created by Michigan State University professor Philip K. McKinley and was sponsored by the National Science Foundation. This source details a case in which students were tasked with creating a robot that could navigate various different mazes. This slide presents the evolutionary steps that their project took in addition to potential future studies that could be done on this topic. This source will be used to gain insights into the processes related to the testing robot navigation of various different mazes.
Ng, J. (2010, February). 2010-Navigation-Ng-PhD.pdf. Retrieved January 24, 2019, from http://robotics.ee.uwa.edu.au/theses/2010-Navigation-Ng-PhD.pdf
This article analyzes many different algorithms that can be used by robots in order to navigate unknown environments. This article was written by a graduate student James Ng a PhD student in the School of Electrical, Electronic and Computer Engineering at the University of South Alabama. This article discusses the bug algorithm that uses sensory information such as frequency data and scanning in order to navigate unknown environments. This source will be used to learn about a specific algorithm that could potentially be used to navigate the maze. While there are many algorithms that I could potentially use for this project, I plan to mix several together in order to make my own unique algorithm.
Pullen, W. D. (2015, November 20). Think Labyrinth: Maze Algorithms. Retrieved January 24, 2019, from www.astrolog.org/labyrnth/algrithm.htm
This source provides a list and description of many different types of mazes and many different algorithms that can be used to generate them. I believe that this source could be tremendously useful to me as I believe that maze generation algorithms could be modified in order to form maze solving algorithms. Additionally, since I am going to have to create a maze of my own for this project, I believe that it could be useful for me to research the many different types of mazes. This source will be used in order to design a useful maze and figure out how to solve particular types of mazes.
Turkar, V., & Kathe, O. (2015, September). Maze solving robot using image processing. Retrieved January 25, 2019, from file:///home/chronos/u-9659f93ab7722ecb44a2956c9fd83e3fa75bf8fe/Downloads/07456635%20(1).pdf
This source details an experiment done at MIT in which they attempted to find a way for a robotic mouse to navigate a maze. This source also talks about many of the future technological uses of this technology, particularly those that relate to automation technology such as Self Driving Cars. Such information will be incredibly useful when writing a paper and creating a presentation about the real world applications of my project. Additionally, this source provides many useful algorithms that can be used in order to allow a robot to navigate mazes. These algorithms could potentially be used in order to figure out how the robot will computationally navigate the maze.