Assembly Robot PreLab 1 – Introduction to the maze and robot

The Original Problem

The problem we will be trying to solve for the semester was originally taken from a puzzle book. Here is the problem as defined by the puzzle book.

In the forest, you will find beehives and more importantly honeycombs. Along the path are bees. The number of bees at any given location is indicated by a number. There are a few ways your bear can travel to the forest. Your aim is to teach your bear how to make his way to the forest while encountering as few bees as possible

Take a few minutes and see if you can solve the puzzle.

Figure 1: The Maze

Draw A Flowchart

Now let’s see if you can translate your path through the maze into a flowchart.

  1. Assume the hungry Bear is initially facing north with his knapsack. In the knapsack is a blank notepad with a pencil and eraser. The length of each step is exactly one square.
  2. There are certain things that the bear can do or check in the attempt to exit the maze. The bear could take a step into the next room, check to see what type of room is encountered, or decide on which way to go next. The entire list of instructions that the bear can take are listed below. Compare it with your own list of instructions that you thought of to see how close you were.

Actuators and corresponding unconditional instructions

  1. Take a step.
  2. Turn left
  3. Turn right
  4. Turn around
  5. Count and record the number of bees in your notepad.

Sensors and corresponding conditional instructions

  1. Did you hit a wall?
  2. Can your left paw touch a wall?
  3. Can your right paw touch a wall?
  4. Are you in the forest?
  5. Do you see any bees?
  6. Are you thinking of a number {not equal, less than, greater than or equal} to 0?
  7. Is the number on page N of the notepad {not equal, less than, greater than or equal} to some constant?

Notepad operations

The bear can remember 8-bit unsigned and 1-bit (binary) numbers. The bear records a number in his notepad. He can only save one number per page. You may assign a descriptive name to a page (ex. bees), simply use the page number (page1), or think of it as a variable (X). In the following example X = 0.

C++ Equivalent Instructions

  1. Erase page X.                                page0 = 0;
  2. Increment the number on a page. page0++;

Nodes

  1. Start
  2. Stop

Tips and Tricks

  • You may not need all the instructions provided.
  • Although not required, you can use subroutines.

Take a few minutes to see if you can sketch-out your flowchart. If you don’t know where to start; don’t worry, in the next few sections I will step you through how to write your own flowchart.

  1. The path through the maze can be modeled as follows. Figure 2 provides an overview of everything the bear will be doing to get out of the maze. Each block will be expanded on in future labs to describe exactly what our assembly program will be doing. For example, this prelab will focus on defining the “Which Way” block, which determines the direction the bear should face while going through the maze.

Figure 2: Top Level Flowchart of maze problem

Creating the WhichWay Flowchart

First, we need to clarify what the Which Way block will be doing. From Figure 2, we know that the bear has just entered a room in the maze and now needs to determine which direction to go. The bear will be taking another step after the Which Way block, so we only need to make sure that the bear is in the correct orientation. There are two ways the bear can decide which way to turn when entering a room. You can count how many rooms the bear has passed or identify what type of room the bear is in. We will be doing the latter for our lab. Based on this information, these are the only instructions needed for this flowchart.

  1. Turn left
  2. Turn right
  3. Turn around
  4. Did you hit a wall?
  5. Can your left paw touch a wall?
  6. Can your right paw touch a wall?
  7. Increment the number on a page
  8. Is the number on page N of the notepad {not equal, less than, greater than or equal} to some constant?

With that in mind, we need to define a way to identify the rooms the bear enters.

Square Naming Convention

Here is a standardized naming convention to help you define the decision points in any maze. In order to provide a design example, the following maze identifies the squares (i.e., intersections) where the bear needs to make a decision for the shortest path solution.

Figure 3: Shortest path solution with intersections identified

Squares are numbered by concatenating the binary values (yes = 1, no = 0) for the answers to the following three questions (sensor inputs).

Can your left paw touch a wall? – Did you hit a wall? – Can your right paw touch a wall?

The answers to these three questions provide all the information that our bear can know about any given square. Let’s look at a few examples to see how this works. After taking the first step the bear can touch a wall with his left paw (1), has not hit a wall (0), and cannot touch a wall with its right paw (0). For our convention, this would correspond to input condition 4 = 1002. As seen in the illustration I have therefore numbered this square 4. Assuming the bear turns right; after taking another step the bear finds himself in a hallway where his left and right paws touch a wall and he does not hit a wall. This corresponds to square 5 (1012). Although you could write a 5 in this square, for the sake of brevity, I left it blank (your bear walks down a lot of hallways). Notice that the numbers are based on the direction the bear is facing and not a universal reference point, like facing north. This corresponds to the fact that within the maze our bear has no idea where north, or any direction for that matter, is (our bear forgot his compass). So, let’s continue to the next intersection. Here the bear’s left paw cannot touch a wall (0), he does not hit a wall (0), and his right paw can touch a wall (1). We therefore would write a 1 (0012) in this square. Continuing in this fashion all intersections are identified for our minimum solution.

Using this notation, the only squares that need to be labeled are the intersections (1, 2, and 4). All other squares can be left blank as indicated in figure 3.

Shortest Path Solution

Using the naming convention and the shortest path through the maze presented in the last section, let’s design a solution for the shortest path.

Build a Truth Table

Table 1: Shortest Path Solution

For your minimum solution, your bear should encounter squares 1, 3, 4, 5, and 6. Once again we did not include in our illustration situations where the bear has no choice (3 = left corner, 6 = right corner, and 5 = hallway).

Draw your Flowchart – Solution for a Fully Deterministic Maze

A fully deterministic maze is one where for any given intersection the bear will always (it is predetermined) take the same action. For example; for your puzzle solution, whenever the bear encounters intersection 4 he will always turn right. For a non-deterministic maze he may turn right one time and turn left another. If you look at our shortest solution to the maze you will discover that it is fully deterministic, and so it lends itself to this simple solution.

Figure 4: Shortest Path Solution

It is always a good idea to check your answer (or mine) to see if it actually teaches the bear how to count the bees and find the shortest path out of the maze.

Once you have your flowchart, implementation in the C programming language or Assembly is fairly straightforward.

Prelab Assignment

In subsequent labs, we will be working with the same bear in the same maze; however you will all be mapping out and trying to teach your bear how to follow a different path. To help everyone plot a unique path, you will need to locate your target square. Please use the maze included at the start of this lab and “theMaze.bmp” only.

Find Your Target Square

Write down the last four digits of your student ID as two 2-digit decimal numbers. These digits will provide the coordinates (row and column) of your target square. For example, if the last four digits of your student ID were 7386, your two 2-digit numbers would be 73 and 86. Divide using long division on each number and write the remainder down. Specifically, the row will be divided by 18 and the column will be divided by 21. Those remainders are now your row and column numbers. In our example, 18 divides into 73 four times with a remainder of 1 and 21 divides into 86 four times with a remainder of 2. Next convert both numbers into a hexadecimal (base 16) number. For our example, 1 = 0x01 (where the prefix 0x signifies a number in hexadecimal) and 2 = 0x02. Your target square would therefore be in row 0x01 and column 0x02.

How to Find Your Path

Find a path through the maze such that:

  1. The bear goes through the target square.
  2. The bear must get lost at least once. Specifically, he must at some point turn-around. This is typically, but does not need to be, at a dead end.
  3. There are any number of paths that can take your bear through the target square, get lost, and into the forest, you now want to find the one that results in the numbers of bees encountered being closest to but not exceeding 15 (inclusive).
  4. Finally, the maze must be non-deterministic. This means that at some intersection along the path the bear will need to take a different action. For example, the first time he encounters a T-intersection he turns left and the second time he turns right. The good news is that, if your path meets the first three criteria, the odds are extremely high that it will be nondeterministic.

Let’s look at how you can develop a flowchart for your unique path.

Design Methodology for a Non-deterministic Maze

As previously mentioned, most maze solutions are non-deterministic. The phrase “not fully deterministic” means, while one set of input conditions in one part of the maze will determine one action (go straight), in another part of the maze the exact same conditions will require a different action (turn right). By looking at your truth-table you can recognize a “non-deterministic” path as having two or more 1’s in the same row. A quick inspection of my truth table reveals that, for the shortest path solution (Figure 4), the bear follows a fully deterministic path. Specifically, for any given intersection the bear will always take the same action. For example, if the bear’s left paw is touching a wall (1), he does not hit a wall (0), and his right paw is not touching a wall (0), then the bear will always turn right. Following is one path that I will use to illustrate how to solve a non-deterministic maze.

Figure 5: Non-deterministic path example

Let’s begin by looking at the sequential actions that must be taken as we encounter each intersection.

Table 2: Sensor Input Combinations and Actions for Non-deterministic Path Example

The good news is that with the exception of square number 1 all other actions are deterministic. The bad news is that only when we encounter room 1 after the second time do we start turning left. To solve this more difficult problem, we will create a binary tree that allows us to resolve all 8 squares, allowing us to then take any action needed. This binary tree can now be easily translated into C++ or Assembly.

Figure 6: Flowchart Showing Binary Tree Solution to Non-deterministic Path Example

A Modular Solution

A more modular solution separates the identification of the square (referred to as a room) from the action to be taken. Identification of the room is placed into a C++ or Assembly subroutine which returns the room number. The calling program must then determine the action to be taken based on the room number returned. The flowchart for the room subroutine is provided here and once again easily implemented in C++ using if or switch conditional instructions as discussed in the next lab.

Figure 7: Flowchart of Which Room Subroutine

Disclaimer – The discussion about the modular solution is to introduce you to other possible methods for approaching this problem. It is representative of how programming can be done in a variety of ways. You do not need to make a flowchart similar to this one.

Step-by-Step Instructions

Here are step-by-step instructions for solving your maze.

Begin by making a copy (electronic or paper) of the maze and drawing your bear’s path through the maze.  When you are happy with your new path, follow the methodology previously discussed to build your truth table. Verify that your path meets the design criteria (passes through target square while encountering the minimum number of bees and getting lost once). Remember, your target square may not be along the original solution path.

It is now time to teach your bear how to navigate the new path by writing a flow chart. To accomplish your goal you will need to apply everything you have learned so far plus add a few Notepad operations. The notepad pages (i.e., variables) are used to determine which path your bear should take when he enters an intersection in which more than one action is possible. For, example the first time he enters intersection 1 you may want the bear to go straight, while the second time he encounters intersection 1 you want him to turn left. To resolve this conflict you would record in your notepad how many times intersections 1 had been encountered and then check your notepad before taking any action.

In addition to previously stated conditions, your solution must also meet the following negative criteria.

  1. Your solution may not use a variable (notepad) to simply count how many steps the bear has taken in order to make a decision.
  2. Your solution should use a variable(s) and not the number of bees encountered to help it make a decision.

Deliverables for Prelab 1

Turn in the following material on the following pages (i.e., no more, no less). All work must be typed or neatly done in ink.

Title Page (Page 0)

The title page (Page 0) includes your picture (one that will allow me to match a name with a face), the lab number, your name, today’s date, and the day your lab meets.

Page 1

At the top of the page provide the last four digits of your student ID and describe how you calculated your target square. Include in your discussion how the resulting path met the design requirements defined in the pre-lab. For example how many paths did you consider before choosing your final path – how close did you come to 15.

Page 2

Next, using your favorite illustration (Visio, Illustrator, or Photoshop) program or the drawing tools included with your favorite Office program (PowerPoint, Excel, and Word) mark your target square with an X and illustrate your bear’s path through the maze (including the sensor input combinations and actions table). Also include on this page a table of “Sensor input combinations and actions” similar to Table 2. If you do not have access to any of those programs, there is a free online website called www.draw.io that works just fine.

Many drawing programs allow you to import a bitmap file, in this case the maze. You can find a bitmap and vector formatted picture of the Maze in the Lab_02 folder (theMaze.bmp and theMaze.ai). Once imported draw your path, typically using the line tool. Next, number your intersections (but not corners or hallways) as illustrated in Figure 5 “Nondeterministic path example.”

Page 3

Again using your favorite drawing program, draw the flowchart for programming problem.

Your flowchart should resemble the one included with the lab and only use the provided instructions. Artwork of the sample flowchart is included in the PreLab_01 folder.

Page 4

The goal of Lab 1 is to connect the two input object sensors with the two output PWM wires (PWMA and PWMB) in such a way that the robot will follow a black line.

IR Sensors to Motors Hi Rez

Figure 8: Object Sensor to Motor Driver

Question 1: Based on Figure 8, what relationship is needed between the input and output signals which would allow the robot to follow a line. Hint: Read Lab 1.

All labs should represent your own work – DO NOT COPY.

Checklist

  1. Your pre-lab report includes a title page (Page 0) with your picture (one that will allow me to match a name with a face). Title information includes lab number, your name, today’s date, and the day your lab meets (Monday or Tuesday)
  2. Pages are in the order specified (see Deliverable)
  3. You do not have any extra pages
  4. You describe how you arrived at your path.
  5. Maze is not copied from another student (zero points)
  6. Path is computer drawn.
  7. Maze Path meets specified requirements.
  8. Intersections are not drawn by hand and appear as shown in the example.
  9. Intersection are numbered
  10. Intersections are numbered correctly
  11. Truth table
  12. Truth table is on the same page as the maze
  13. Truth table is typed
  14. Truth table matches the maze
  15. Flowchart
  16. Flowchart matches your truth table
  17. Flowchart is correct
  18. Question(s) are answered with all work shown.