Team: 12
School: Multi Schools-EH/NexGen
Area of Science: Mathematics
Interim: Team ID: Team #12
Schools: Eldorado High School, NexGen Academy
Area of Science: Mathematics
Project Title: The Curse of Immersive Recursive Maze Solving Algorithms
Mentors: Geoff Danielson (gcdaniel@gmail.com)
Sponsor Teacher: Karen Glennon (kglennon25@gmail.com)
Patty Meyers (pmeyer2843@gmail.com)
Team Members: Savannah Phelps (savannah22snowleopard@gmail.com)
Brendan Kuncel (bboyk2222@gmail.com)
Quentin Dye (qdye2001@gmail.com)
Problem Definition:
Our project is to create a comparison of human intelligence and machine intelligence in the scopes of iterative maze solving. We will analyze how a human and an agent-based model improve the time it takes for them to solve in terms of the number of turns they take.
It is important to note our program is not an artificial intelligence. It does not create or respond uniquely to input, it simply follows rules.
Problem Solution:
We will present the model and the human with identical computerized mazes and limit the human’s vision of the end of the maze with a blocker to even the playing field. Both will repeatedly attempt the same maze over and over again until the perfect solution is achieved. For the human’s touch screen maze, we will be using NetLogo due to its superiority in basic visual representation. For the program’s maze, we will be using Python to create an identical maze. Python was chosen here for its ability to perform a greater variety of functions. We will include an optional visual representation of the program’s maze created with the python library graphics.py.
The model will have several programmed in maze-solving algorithms to cycle through, and will use reinforcement learning equations to make decisions on which algorithm is “working†the best and should therefore be used. Reinforcement learning is a way for programs to make choices based on what option has provided the most “rewardsâ€. In this project, when an algorithm results in a fewer amount of turns than previous attempts, a reward will be given to that algorithm. The next time the robot “looks†at its options, it will want to choose the option it has been rewarded for most. If this algorithm fails too many times, rewards will be taken away, and another option may appear more favorable.
The number of turns taken for each iteration will be recorded and graphed, then compared for effectiveness.
Expected Results:
We expect to find that the model will perform better over time, even across different mazes than humans. Programs have the advantage of mathematical thought, whereas humans are subject to guesses and superstitions.
However, while we expect the model to prevail, we expect humans to be initially better at mazes in the beginning, but remain at an almost constant rate.
This is an interesting application of machine learning, and this decision-making model can be adjusted for purposes such as navigation or path optimization.
Progress to Date:
We have studied and made a list of maze solving algorithms, which we will soon apply to a python visual model. Maze-solving effectiveness was the focus of last year’s project.
Then, we created a Python program which will generate a maze for the model to solve. This superior maze generator will be the basis for a bitmap recreation using NetLogo. This maze generator starts by overlaying the visual screen with even squares to make a grid. The program notes the vertical lines in the grid and selects one. It divides this line in half in terms of the grid spaces it fills. This division causes a branch at random point. Randomly, a grid space is selected from the original line to clear so that a path can be made through it. This new horizontal line will always go left first, and record the grid spaces to the right of it in a “to do†list. This process is repeated to this new line until no further divisions are possible, the next line being formed down. This point is noticeable when a two by two grid square appears. At this point, the code addresses the first list of blocks recorded in the “to do†list, and the same process repeats.
filesystem:https://docs.google.com/persistent/docs/documents/1uXy7Ns6MzzzvtAygo9hKGhz4_daXsPDBKi4Vq7vkMYY/image/1q8Y99p-hK0Xpcvg42zekMk_oczkErI-vKkt6lXo?zx=5a15r3ips9ec
Next, we have made software for the humans to trace out a path on a maze using a touchscreen computer, but have yet to add a vision blocker and monitor turns taken. When the program starts, it fills the screen with a grid by asking each patch to surround itself with walls. A bitmap image of the maze the python maze will guide a turtle around deleting borders appropriately. The green and red squares represent start and stop respectively. The pink route represents the user’s path through the maze.
filesystem:https://docs.google.com/persistent/docs/documents/1uXy7Ns6MzzzvtAygo9hKGhz4_daXsPDBKi4Vq7vkMYY/image/1TEM2kLkrbDwt6eynkHkh5HAHdwzL87Bk7AfUTG8?zx=bcurslxo0hj
filesystem:https://docs.google.com/persistent/docs/documents/1uXy7Ns6MzzzvtAygo9hKGhz4_daXsPDBKi4Vq7vkMYY/image/1rTUfQl5YXWv0V9hnswwswuHgjBtVOVxC1VIVgJU?zx=w8s9kdb9d3d4
Citations:
Nilsson, Nils J. Principles of Artificial Intelligence. Springer Berlin, 2014.
Layton, Julia. How Robotic Vacuums Work. HowStuffWorks, 3 Nov. 2005, electronics.howstuffworks.com/gadgets/home/robotic-vacuum2.htm
“Artificial Intelligence vs Human Intelligence - 5 Useful Comparison.†EDUCBA, 5 Oct. 2018, www.educba.com/artificial-intelligence-vs-human-intelligence/.
Sutton, Richard S., and Andrew G. Barto. Reinforcement Learning: an Introduction. The MIT Press, 2018.
“Graphics Reference (graphics.py v5)â€, Wartburg College, http://mcsp.wartburg.edu/zelle/python/graphics/graphics.pdf
Team Members:
Quentin Dye
Brendan Kuncel
Savannah Phelps
Sponsoring Teacher: Karen Glennon