Team: 16
School: Cottonwood Classic Prep
Area of Science: Behavioral and Social Sciences
Interim: Problem Definition:
Within the psychology field, mazes have been used heavily for experiments regarding decision making and cognitive processing. For example, one of the first maze experiments was conducted by Willard S. Small. Small measured the learning capacity of rats using mazes to test their intelligence and long-term memory [1]. Mazes have been used considerably ever since then to look into similar problems. Our interest in mazes was first sparked by an interest in the psychology field and human decision making within different personality types. We wanted to analyze how humans made decisions in quick-paced situations that are presented to them on the spot. However, we were unable to obtain human participants for this year and decided that in order to better understand decision making, a maze could be used as it involves a surplus of different decisions. This led us to the idea of mazes and how effective algorithms can be tested to find which algorithm can work the most efficiently in solving different types of mazes. Ultimately, these results could then be given to researchers to use with human participants.
Plan to solve the problem:
Our plan to solve this problem is to compare algorithms most effective at solving a maze which we will accomplish by running tests on different algorithms. We will accomplish this code by using pygame to design our mazes. Our code will, simply, create a maze, designed by us. It will include: twists and turns, rewards and penalties, rights and lefts from start to finish. Then, we want to simulate different maze algorithms such as the mouse junction algorithm, wall following algorithm, Dijkstra's algorithm and the Tremaux algorithm [3] [4]. These algorithms will solve the mazes in their corresponding ways. We will then use variables such as time and incentives to determine which algorithm can solve these mazes in the most efficient and time conscious way.
Progress to date:
In the beginning of the year, we wanted to investigate decision making and how psychology plays a role in how these decisions are made. This idea has been consistent throughout the year, even after we transitioned from the idea of humans and personality types, to mazes and how algorithms play a big role in solving them. Up to this point, we have worked with our mentor Flora Coleman, who is a computer engineer at Sandia Labs. She has been helping us shape our project and our program. We have researched extensively on different maze algorithms that have been used to solve various mazes and how mazes have been used in history, especially in the psychology field. This research will help us familiarize ourselves with what these algorithms will do and help us measure what it means to have a successful maze. We have also made progress with our code by building a general maze structure and player that will be able to navigate through the maze.
Expected results:
We then want to incorporate various algorithms to measure their efficiency with our constructed mazes. Through our evaluation of each algorithm and its comparison to the others, we are expecting there to be a clearly efficient algorithm. We would define efficiency as completing the given task in the shortest amount of time. Between the four algorithms we will be testing: mouse junction, wall-following, Tremaux and Dijkstras, we think Dijkstras will be the most efficient. This is simply because it would determine the quickest route, based on the value of each maze square (all being 1). It is a more refined algorithm in comparison to the wall following as it purposefully selects a route. The wall following, and other algorithms, could easily pass by the finish. In addition to this, we want to take into account if there are any patterns based on the structure of the maze and how incentives such as rewards and penalties impact the time and algorithm of the maze.
Team members:
Ayvree Urrea ayvreeurrea@gmail.com
Kiara Onomoto kiaraonomoto@gmail.com
Violet Kelly kellyviolet1111@gmail.com
School name: Multi-School CottonwoodDel Norte
Sponsoring Teachers:
Karen Glennon
Patty Meyer
Resources:
[1] Goodwin, Dr. C. James. “A-Mazing Research.†Monitor on Psychology, American Psychological Association, Feb. 2012, www.apa.org/monitor/2012/02/research.
[2] Mohseni, Fahimeh, et al. “A Review of the Historical Evolutionary Process of Dry and Water Maze Tests in Rodents.†Basic and Clinical Neuroscience, Iranian Neuroscience Society, 2020, www.ncbi.nlm.nih.gov/pmc/articles/PMC7878036/.
[3] Pullen, Walter D. “Think Labyrinth: Maze Algorithms .†Think Labyrinth: Maze Algorithms, http://www.astrolog.org/labyrnth/algrithm.htm#solve.
[4] “Maze Solution #3 - Tremaux's Algorithm.†Maze Solution #3 - Tremaux's Algorithm: V19FA Intro to Computer Science (CIS-1100-VU01), https://vsc.instructure.com/courses/6476/pages/maze-solution-number-3-tremauxs-algorithm?module_item_id=713459.
[5] “Historical Mazes.†Maze Engineers, 6 Dec. 2020, https://conductscience.com/maze/historical-mazes/.
Team Members:
Kiara Onomoto
Ayvree Urrea
Violet Kelly
Sponsoring Teacher: Karen Glennon