CSE 151 Final Project

Discussion of Results and Findings

Matthew Solnit
Paul Brinkmann
J.P. Patil

return Home

    The topic of artificial intelligence covers an amazingly vast amount of material.  AI can assist in almost any situation that requires good decision-making with limited information.  Concepts of robotics are especially compatible with AI, because they involve high levels of interaction with the complex, real world.  Robotics is also a challenging arena for many theories of computing.  The unpredictability of life and the physical world serves as a worthy opponent to these theories.  This paper will explore our attempt to apply theories of computer science to a physical robot making decisions in a physical environment.

    The experiment we chose was to create a maze, and to try to give our robot the skills to find a way through it.  We chose this because the topic of maze escaping is a good example of something physical that is commonly simulated on a computer.  This process of simulation allows designers to ignore many of the problems that are central to a real-life solution.  We predicted that theoretical solutions could be applied to a real maze with relative ease, once the robot was provided with the same information and abilities that are given “for free” in simulations.

    We began our experiment by creating a C++ program which finds the way out of any maze that has a solution.  It does this using a recursive branching algorithm.  From the starting point, each possible path is checked until either an exit is found or all paths have been searched.  Our intent was to use this same algorithm with a robot.

    Our robot was created using the Lego MindStorms product.  This package allowed us to easily create both movement and a crude awareness of the world, via light and touch sensors.  The light sensor can examine a tiny spot and determine how reflective it is.  This effectively allows distinction between white, black, and shades in between.  The touch sensor is a small button, which is aware of how deeply it has been pressed.  These sensors were all that was available to us for input of data.  Thus, their nature dramatically affected how we designed our environment.

    Because the light sensor, our only real “sight”, is not sufficient to discern actual walls and pathways, we decided that the maze would have to be divided into discrete areas, so that each could be dealt with individually.  In other words, if we created a maze where only certain locations were acceptable for a wall or a path, then the robot could examine each location in turn.  We predicted this would be much more manageable than trying to make the robot aware of random turns and branches.

    To implement our idea, we created a grid of squares.  Our intent was that the robot would be able to enter a square and see what choices were available from there.  By examining each direction, the robot could determine whether a new path existed.  Thus, the robot would have a finite set of possible decisions, and would always be able to try each one if necessary.  If maze had a solution, using this idea of grids the robot was theoretically guaranteed to find it.

    Once this environment had been conceptualized, we could drop our algorithm right in: simply try every path until we either escape, or determine for certain that we have tried every path and no solution exists to be found.  All that remained was to implement our robot’s movement through the maze.

    This was ultimately the portion of the experiment that was the most troublesome, completely unforeseen to us.  In retrospect, we really should have predicted that motion in the real world would be inexact, difficult and time-consuming.  The two main issues we had to deal with were traveling in a straight line and turning in the correct direction.

    Our robot cannot make a correct 90-degree turn unassisted.  The turns needed to be exactly 90 degrees.  If there were even the slightest variation, over time the robot’s representation of itself in the maze would become out of synch with it’s actual position in the maze, and it would become confused and crash into walls. We attempted to use timers, but this did not give reliable results.  Small errors added up over time.  We needed an infallible way of telling the robot that it had reached the correct angle.  Since our only ways of communication were via color and touch, it made sense to depend on these.  Touch was quickly eliminated from the solution because it would require objects strewn around the maze.  However, aided by gray lines every 90 degrees within the square, our robot was able to form an awareness of how far it had turned.  Thus, we again tailored the environment to accommodate the needs of the robot.

    Our robot also cannot travel in a straight line unassisted.  Small frictional forces on the surface and in the motor would eventually cause uneven travel, even though both motors were being told to do the same action.  Again, color inputs seemed to be the only answer.  We quickly realized that our gray turning lines formed consistent lines through the centers of squares.  These could be followed, to insure straight travel.

    Eventually, our solution to these problems created new difficulties.  For example, if the robot cast a shadow before itself, it could mistake this grayness for the gray lines vital to its performance.  Also, the paint that we used to make the lines was slightly sticky after drying, and would occasionally snare the robot.

    What we were constantly aware of was that we were spending the majority of our time dealing with issues of interacting with the environment, rather than making correct decisions.  Once we had succeeded in providing our robot with the tools it needed to understand its surroundings, it was able to accomplish its goal.  In fact, when we finally reached the point of testing our decision-making process, we discovered that it was nearly perfect to begin with.  Very few changes had to be made, and most involved absent-minded errors.

    Thus, our prediction was correct.  We were able to directly apply a theoretical solution to reality.  This theoretical solution required almost no modification during the process.  The bulk of the difficulty lay in gathering the same information from the real world that we computer programmers take for granted in the computing world.

return Home