Monday, August 18, 2014

Traveling Pro-Bot: Finding the shortest path

The Traveling Salesman Problem is one of the most famous and one of the most complex in Computer Science. The problem can be cited as the following: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the starting city? 

This problem in its various forms has a variety of applications in multiple fields for optimization purposes. For example, a school district would like to find the best route for a school bus to pick up kids in the morning. The courier company would like to determine the best route to drop off packages, with minimum fuel costs. In a factory assembly line, if you can find a way to visit all the required stations in minimal time, you can manufacture more units in a day. There are several more instances of the application of this problem and the “cities” in the original problem will denote various points in those instances. As the number of “cities” increases, the complexity of the problem also increases.

We shall work on a very simple instance of the above problem, involving a maximum of just 5 cities. Pro-Bot shall represent our salesman, driving between the various cities.


Computer Science concepts involved:  Sequential programming, A peek into optimization techniques

Math concepts involved:  Using data given for creating a graph, Measuring distances and directions on a map, Finding shortest path, Cost comparison, Measuring angles, Scaling quantities 

Grade levels:  4, 5

Hours required:   2 or more



Distance between cities in miles
The distances between the various cities are given in the table below in miles. Note that these are straight line distances between the cities (as the crow flies) and not driving distances. 


                     City Name                            City Name                      Distance in miles



















On a map of USA, locate the various cities given in the table above. 




Task 1
We shall start with a very simple route. Let’s consider the three cities of San Diego, Austin and Denver. Pro-Bot has to visit all three cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled is minimized?

Remember that the minimum distance Pro-Bot can draw is 1cm. Given the distances in the table above and using a scale of 1 cm to represent 100 miles, can you round the distances so that they can be used by Pro-Bot?  Draw a small graphical representation of your cities and distances between them as shown below. This might be helpful for you to visualize the problem. 



















Using  a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all three cities, starting and ending at San Diego?

If gas costs $3 a gallon and Pro-Bot uses one gallon per 10 miles, how much did it cost for the trip?


Task 2
We shall move on to a route that involves 4 cities now: San Diego, Austin, Denver and Chicago. Pro-Bot has to visit all four cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled by Pro-Bot is minimized? 

Remember that the minimum distance Pro-Bot can draw is 1cm. Given the distances in the table above and using a scale of 1 cm to represent 100 miles, can you round the distances so that they can be used by Pro-Bot?  Draw a small graphical representation of your cities and distances between them as we did in the previous task. This might be helpful to visualize the problem.

Using  a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all four cities, starting and ending at San Diego, so that the total distance traveled is kept to a minimum?

If gas costs $3 a gallon and Pro-Bot uses one gallon per 10 miles, how much did it cost for the trip?


Task 3
We shall work on a route that involves 5 cities now: San Diego, Austin, Denver, Chicago and Las Vegas. Pro-Bot has to visit all five cities, starting from San Diego and returning to San Diego. No city other than San Diego should be visited more than once. What order should the cities be visited in so that the total distance traveled by Pro-Bot is minimized? 

Remember that the minimum distance Pro-Bot can draw is 1cm. Given the distances in the table above and using a scale of 1 cm to represent 100 miles, can you round the distances so that they can be used by Pro-Bot?  

Using  a map of the USA and a protractor, try to find out the angular measurements between the various cities (approximate values are fine). Using the distance and angular information, as well as the location of the various cities on the map, can you write a program for Pro-Bot to visit all four cities, starting and ending at San Diego, so that the total distance traveled can be kept to a minimum?

If gas costs $3 a gallon and Pro-Bot uses one gallon per 10 miles, how much did it cost for the trip?



A few points to think about:
  • As you worked on the above 3 tasks, did you notice that as the number of cities increased, your job of finding the route with minimum cost also became more complex?
  • Was there a particular technique that you used for finding the  minimum cost route in each case? 
  • Or did you evaluate all possible routes in each task and then choose the best one to write your program for? Do you think that it would be a good solution for a large number of cities, say 1000 or 10,000 or so?
  • Can a change in constraints lead to a change in the routes that you found? Check the next section for an example.


A Different Condition & A Different Route:

Now, imagine that Pro-Bot is a rental car that you picked up at the San Diego airport. You shall use Pro-Bot to visit various cities starting from San Diego. We would still like to keep our distance and gas costs to a minimum and visit each city only once. But this time, Pro-Bot does not need to return to San Diego after visiting all the cities. You can it drop off at the last city that you visit. 

For each of the tasks above, does this change in the conditions cause a change in the route?


Task 4:
Pro-Bot visits San Diego, Austin and Denver, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 1?

Task 5:
Pro-Bot visits San Diego, Austin, Denver and Chicago, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 2?

Task 6:
Pro-Bot visits San Diego, Austin, Denver, Chicago and Las Vegas, starting from San Diego. The distances between the cities and the gas prices are the same as before. You do not have to return to San Diego. Can you write a program for Pro-Bot’s route that involves the minimum gas cost? Is it the same route as in Task 3?





Sensors in Pro-Bot: Relay Driving by Pro-Bots using Sensors

Pro-Bot has three kinds of sensors built into it: touch, light and sound sensors. Before we start writing programs for Pro-Bot that use the sensors, let’s see what purpose these sensors serve and what “sensing” means.

Sensing 


When someone taps your shoulder, how do you know you were touched? When the light bulb goes on in a dark room, how do you know the room suddenly got bright? When you put a candy in your mouth, how do you know that it is sweet? Because your skin sensed the touch, or your eyes sensed the light, or your tongue sensed the taste… Once you sense something, you typically react to it, don’t you? When you sense the touch, you may turn around to see who tapped your shoulder; when you sense the light coming on in the dark room, you may squint your eyes and try to figure out what is in that room; when you sense the sweetness on your tongue, you may feel happy and say “yummy”…

Your skin, eyes, tongue, etc., have “sensors” that sense some “stimulus” like touch, light, taste, etc., and enable you to respond to it. You may have also noticed that you have different sensors for different functions. Sensors are made to detect very specific stimuli. For example: your skin doesn’t see, you have eyes to do that; your eyes don’t taste the sweetness of the candy, you have taste buds on your tongue to do that.

Now what if a robot could behave similarly (it may not behave in exactly the same ways as you do)? A robot can be fitted with sensors and programmed to respond in a certain way when the sensor senses a stimulus.

Pro-Bot has 3 kinds of sensors - one senses light, one senses contact (or touch) on its front and rear bumpers and the other senses sound. Pro-Bot’s sensors must be turned on, if you want them to detect stimuli and respond to them (they are switched off by default). Think of it as needing your eyes to be open to see the light. The sensors detect only the specific stimuli that they are designed for. For example, the touch sensor or the light sensor on Pro-Bot will not detect or respond to sounds. They will respond only to touch and light stimuli respectively. However, short sharp sounds (like a loud clap or a short yell) may be detected by the sound sensor and you can program the robot to respond to it.

Now, how does Pro-Bot react when these sensors sense something? Consider the touch sensors on Pro-Bot’s front and rear bumpers. You can program Pro-Bot to do something when those sensors sense a contact (such as bumping into something, or getting bumped by something). Similarly, the light sensor on Pro-Bot can be programmed to do something when it detects a change in lighting.

Pro-Bot has 5 specialized Procedures that correspond to inputs from its sensors. These are 
33 FRONT
34 REAR
35 DARK
36 LIGHT
37 SOUND

You can access and modify the above Procedures via the Menu button on the control pad. The instructions in each of these Procedures will be executed when the the corresponding sensor detects a stimulus. If the Procedure corresponding to the sensor is empty (if you decide not to react to a stimulus), Pro-Bot does not respond to changes in the sensor condition. 
So, what happens after Pro-Bot has responded to a stimulus? Before you answer that question, consider this scenario: Imagine that you are sitting in your chair and reading a book. Your friend comes over, taps you on the shoulder and asks you something. Your skin’s touch sensor senses the tap, and your ears (another of your sensors), sense the spoken words. Maybe your friend was asking you to join her in a game. Let us say you respond saying “Later”. What do you do next? You would continue reading that interesting book, right? 
Let’s analyze what just happened. You were doing something… then you got “interrupted” by your friend… you “handled” that interruption… and then you got back to doing your reading… A computer or a robot can react the same way. When its sensor detects a stimulus, Pro-Bot can react to it by running a specific program, and after it is done, Pro-Bot continues with what it was doing before the interrupt happened. For example, if Pro-Bot was driving and midway, it entered a dark tunnel, it would detect the change in light and may turn on the headlights (if you programmed it to respond that way) and after that, it would continue driving along. After it is done with the response to the stimulus, Pro-Bot resumes the steps in the main program. 

What you have learned above is a fundamental behavior in Computer Science and Robotics: handling interrupts

Let us test our understanding now with an assignment that uses sensors.



Relay Driving by Pro-Bots using Touch Sensors:


Computer Science Concepts involved:   Procedures, Sensors to detect and react to stimuli, a quick peek into Interrupt handling

Math Concepts Involved:   Linear measurements, Solving real world problems by modeling with mathematics

Grade Levels:   3, 4, 5

Hours Required:   1

Materials Required:   A pre-set path drawn for the Pro-Bot to drive on, preferably marked with blue tape. Optionally, a shoebox with one vertical side cut open to act as a garage for Pro-Bot


Programming Assignment:


Let’s look at a simple task to start off with, involving 2 Pro-Bots. The steps are listed below.
  1. Mark a path on the floor with blue tape that is about 40 cm long. You can also mark a target finish line at the end of the path.
  2. Place one Pro-Bot at the beginning of the path, facing forward and ready to drive along the path. 
  3. Place the second Pro-Bot at approximately the midpoint of the path, 20 cm away from the start point, facing forward and ready to start driving. (Both cars face the same direction.)
  4. Optionally, place a ‘garage’ (made out of an upside down shoe box with one side cut for the car to enter) at the very end of the path.
  5. Make sure that the sensors are set to "On" from the Menu button on Pro-Bot.
  6. Program your Pro-Bots so that the first car starts driving along the path while the second car is waiting. The first car hits the back of the second car, makes a beep sound and stops. The second car now starts driving. It drives all the way into the finish line/ garage. It makes a beep sound and stops. (Optional step: when it gets inside the garage, it switches its headlights on.)


Now, how can we program the two Pro-Bots to do this?
  • For the first Pro-Bot, the task involves driving forward, say 20 cm, to reach the second car and then reacting to a touch on the front bumper when it hits the second Pro-Bot. So, your program for the first Pro-Bot has to be split up into two parts - the Main program that handles the driving forward part and Procedure 33 FRONT that handles the contact to the front sensor. You will have to edit Procedure 33 FRONT to make the beep sound & add in a few Pause instructions to make the car stop.
  • For the second car, driving starts only when it gets hit on the rear bumper. To make the car wait, your Main program shall have a few Pause instructions in a loop. You would also need to modify Procedure 34 REAR to make the car react to the hit on the rear bumper and drive to the finish line/ garage. Optionally, once inside the garage, the light sensor can detect the darkness and respond to it; for this modify the procedure 35 DARK to switch on the lights.

Once the two Pro-Bots have been programmed, press the GO button on both cars at the same time and watch the relay race happen! Here is a sample set of programs, for two Pro-Bots kept at a distance of 20 cm from each other and the finish line at a distance of 20 cm from the second Pro-Bot:



Pro-Bot 1:

  • Main - Fd 20

  • 33 FRONT -  Sound 3
                              Rpt 20 [
                              Ps
                              ]

Pro-Bot 2:

  • Main - Rpt 20 [
                   Ps
                   ]

  • 34 REAR -  Fd 20
                           Sound 3

  • Optionally, 35 DARK - Light On

Note:   This project can be easily extended to include more cars and more complicated paths. Since we do not have a Stop instruction available, we can make the car stop by using the Pause instruction in a loop. 


Extension


If working on the relay race project with 3 or more cars, all the cars other than the first and last ones would need to handle both their front and rear touch sensors. Let’s look at an example with 3 cars, assuming they are kept at a distance of 20 cm each. In this case, the first car would behave as Pro-Bot 1 above and the last car would behave as Pro-Bot 2 above. Here is a sample set of programs for the 3 car relay race:


First  Pro-Bot :

  • Main - Fd 20

  • 33 FRONT -  Sound 3
                              Rpt 20 [
                              Ps
                              ]

Middle Pro-Bot:

  • Main: Rpt 20 [
                  Ps
                  ]

  • 34 REAR -  Fd 20
                           Sound 3
                                
  • 33 FRONT -  Sound 3
                              Rpt 20 [
                              Ps
                              ]

Last Pro-Bot :

  • Main - Rpt 50 [                     // Remember to make the Pro-Bot wait longer 
Ps // here to allow for the other two cars to catch up.
                   ]

  • 34 REAR -  Fd 20
                           Sound 3

  • Optionally, 35 DARK - Light On




Sunday, August 17, 2014

Nets of 3D Shapes Part 2 - Prisms & Pyramids: More Practice with Procedures using Pro-Bot

This programming assignment is intended to provide more practice with Procedures using Pro-Bot. We shall use Procedures to store programs for various polygons. We shall then write programs for Pro-Bot to draw nets of some 3-Dimensional figures using these Procedures. 
We already worked on the nets of cubes in our previous assignment,  Nets of 3D Shapes Part 1 - Cubes. This is a follow-up to that work, involving more complex polyhedrons. 


Computer Science concepts involved:   Sequential programming, Repeat loops, Procedures

Math concepts involved:   Polyhedrons (prisms, pyramids), Nets of 3D figures (visualizing 3D figures on a 2D plane, identifying multiple nets, properties of nets), Polygons (triangles, quadrilaterals, pentagons), Measurement, Angles

Material required:  Card paper/thin cardboard to draw the nets on

Extension activity:   Make the 3D figures by cutting out the net from the card paper and folding along the edges 

Grade levels:   5

Hours required:   2 or more



Nets of 3-Dimensional Figures


A 3-Dimensional (3D) shape is a shape that has length, width and depth. They are also called solid figures or solid shapes. The length, width and depth are the three dimensions. Most of the objects that we see around us are 3-Dimensional. For example: your books, school bag, a box of crayons, Pro-Bot, table, chairs, water bottle, soccer ball, even yourselves are all 3D shapes.

How do these shapes differ from 2-Dimensional (2D)  figures, like the ones that you draw on paper? Think about how a cube or a sphere differs from a square or a circle drawn on paper. Well, the difference is that they have depth, unlike the 2D figures drawn on paper, which have only length and width. 3D shapes do not lie flat on a plane surface and they are difficult to draw on a piece of paper. 

But what if we could open up the 3D shapes and lay them out flat on paper? This would show us exactly how these solid shapes are made. A net can help us convert a 3D shape to a 2D figure. Nets are the flattened shapes of 3D objects. The net shows every edge and every face of the 3D figures laid out flat on paper. The net has only length and width; it does not have depth. It makes it easier for us to study and analyze some of the properties of a 3D object. You can cut out the net from the paper and fold it along the edges to create the 3D object. The same 3D object may be flattened into more than one net.

Let’s look at a few 3D shapes and draw their nets. We shall use Pro-Bot to draw the nets on thin cardboard. You can then cut out the nets and fold them to create the 3D shapes.



Nets of Prisms:


A prism is a solid object whose bases (or ends) have the same size and shape and are parallel to each other. The sides of the prism are parallelograms. A prism has the same cross-section all along its length. The shape of the bases (or ends) give the prism its name. We shall look at two types of prisms here:
  • Rectangular prisms
  • Triangular prisms


Nets of Rectangular Prisms:


Rectangular prisms are very commonly seen in our daily lives; for example, boxes, books, buildings, etc. A rectangular prism has 6 rectangular faces, 12 edges and 8 vertices. Opposite faces are congruent and have the same dimensions.  All faces of the rectangular prism are rectangles. A cube is a rectangular prism where all rectangular faces have equal edges.

Given below is a rectangular prism and one of its nets. The bases of this prism are square in shape. Hence it is also called a square prism






















  1. Write a program for Pro-Bot to draw the net given in the figure. Store the program for each rectangular face as a Procedure. (If there is a procedure for the 6 cm side square that you have already written, it can be used in this program as well.) 
  2. Can you come up with more nets for the above prism. Try at least one other net and write a program for Pro-Bot to draw it. 
  3. Once you are done drawing each net using the Pro-Bot, cut out the net from the paper. You can fold the paper along the edges and create the prism.
  4. Given below is another rectangular prism. Write a program for Pro-Bot to draw a net for this prism. 
  



Nets of a Triangular Prism:


In the figure below, you can see a triangular prism, with a shape that resembles a camping tent. It has 5 faces, two of which are equilateral triangles and three are rectangles. 




















  1. Write a program for Pro-Bot to draw an equilateral triangle of sides 6 cm and store it as a Procedure on Pro-Bot. Remember to use Repeat Loops when you are working with regular polygons (polygons with all edges equal and all angles equal).
  2. Next, construct a net for this triangular prism. Write a program for Pro-Bot to draw the net, using the Procedures for the rectangle and the triangle that you previously wrote.
  3. How many different nets can you draw for this triangular prism? Write a program for Pro-Bot to draw each net that you can identify for this prism.


Nets of Pyramids:


The word “pyramid” immediately brings to mind the royal tombs of ancient Egypt. The pyramids of Egypt are square pyramids, with a square base and triangular sides. There are various types of pyramids; they are named according to the shape of the base. A pyramid is made by connecting the base to the apex (top point where all the triangular sides meet). 

In this assignment we shall look at three regular pyramids, which have regular polygons as their base: 

  • Triangular Pyramid
  • Square Pyramid
  • Pentagonal Pyramid

Net of a Triangular Pyramid/Tetrahedron:


A triangular pyramid is also known as a tetrahedron ("having 4 faces"). A tetrahedron has 4 triangular faces, 4 vertices and 6 edges. Three triangular faces meet at each vertex. 

In the figure below, a tetrahedron with 6 cm edges is given. All the triangular faces are equilateral triangles, with sides of 6 cm. 





















  1. Can you write a program for Pro-Bot to draw a net for the tetrahedron, using the Procedure for the equilateral triangle of sides 6 cm that you wrote earlier? 
  2. How many nets can you create for the tetrahedron?
  3. After drawing the net using Pro-Bot, you can cut the net out of the paper and fold it along the edges to build the 3D tetrahedron. 

Net of a Square Pyramid:


A square pyramid has 5 faces, 5 vertices and 8 edges. The base is a square and the other faces are triangles. In the figure below, a square pyramid with all edges measuring 6 cm is given. 






















  1. Can you write a program for Pro-Bot to draw a net for this pyramid, using some of the Procedures that you wrote earlier? 
  2. How many nets can you create for the square pyramid?
  3. After drawing the net using Pro-Bot, you can cut the net out of the paper and fold it along the edges to build the pyramid. 

Net of a Pentagonal Pyramid:


A pentagonal pyramid has 6 faces, 6 vertices and 10 edges. The base is a pentagon and the other faces are triangles. In the figure below, a pentagonal pyramid with all edges measuring 6 cm is given. 




















  1. Can you write a program for Pro-Bot to draw a net for this pyramid, using some of the Procedures that you wrote earlier? Remember to use Repeat Loops while writing the program for the pentagon. 
  2. How many nets can you create for this pyramid?
  3. After drawing the net using Pro-Bot, you can cut the net out of the paper and fold it along the edges to build the pyramid. 

Nets of 3D Shapes Part 1- Cubes: More practice with Procedures using Pro-Bot

This programming assignment is intended to provide more practice with Procedures using Pro-Bot. We shall use a Procedure to store the program for a square. We shall then write programs for Pro-Bot to draw nets of a 3-Dimensional object, a cube in this case, using the Procedure. 


Computer Science concepts involved:   Sequential programming, Repeat loops, Nested Loops, Procedures

Math concepts involved:   Cubes; Nets of 3D objects: visualizing cubes on a 2D plane, identifying multiple nets per cube, properties of nets of a cube; Squares, Measurement, Angles

Material required:  Card paper/thin cardboard to draw the nets on

Extension activity:   Make the cube by cutting out the net from the card paper and folding along the edges 

Grade levels:   3, 4

Hours required:   2 (or more)


Nets of 3-Dimensional Figures


A 3-Dimensional (3D) shape is a shape that has length, width and depth. They are also called solid figures or solid shapes. The length, width and depth are the three dimensions. Most of the objects that we see around us are 3-Dimensional. For example: your books, school bag, a box of crayons, Pro-Bot, table, chairs, water bottle, soccer ball, even yourselves are all 3D shapes.

How do these shapes differ from 2-Dimensional (2D)  figures, like the ones that you draw on paper? Think about how a cube or a sphere differs from a square or a circle drawn on paper. Well, the difference is that they have depth, unlike the 2D figures drawn on paper, which have only length and width. 3D shapes do not lie flat on a plane surface and they are difficult to draw on a piece of paper. 

But what if we could open up the 3D shapes and lay them out flat on paper? This would show us exactly how these solid shapes are made. A net can help us convert a 3D shape to a 2D figure. Nets are the flattened shapes of 3D objects. The net shows every edge and every face of the 3D figures laid out flat on paper. The net has only length and width; it does not have depth. It makes it easier for us to study and analyze some of the properties of a 3D object. You can cut out the net from the paper and fold it along the edges to create the 3D object. The same 3D object may be flattened into more than one net.

Let’s look at a very common 3D shape, a cube, and draw its nets. We shall use Pro-Bot to draw the nets on thin cardboard. You can then cut out the nets and fold them to create the 3D object.


Nets for a Cube


Have you seen the dice that you use for board games? It has the shape of a cube. A cube is one of the most common 3D figures, with 6 square faces, 12 edges and 8 vertices. 

What would the cube look like if you cut it open along some of its edges and laid it out flat on a piece of paper, so that you can see every face and every edge? The flattened version of the cube would be its net. There can be more than one net for a given 3D shape. Can you guess how many nets exist for a cube?

In the figure below are a couple of nets for a cube of sides 6 cm each. 




















You can see from the figure that each net is made up of multiple squares; each square representing a face of the cube. All the squares are similar, with edges measuring 6 cm each. If you fold the above nets along the edges/lines drawn in the figure, you would end up with a cube.



Programming Assignment


  1. Write a program to draw a 6 cm side square. Remember to use Repeat Loops in your program for the square. Store your program as a Procedure.   (Since the same square is used multiple times in each net, it would be easier for you as the programmer, to write the program for the square just once, store it in a Procedure and then call that Procedure from your main program whenever you need it.) 
  2. Write the programs for Pro-Bot to draw the nets for the cube as given in the figure above. Use the Procedure for the square that you previously wrote while writing the programs.
  3. There are 11 possible nets for a cube, two of which are given above. Can you identify the other 9 nets for the cube as well? 
  4. Write a program for Pro-Bot to draw each net that you identify, using the Procedure for the square in your program.
  5. Once you are done drawing each net using Pro-Bot, cut out the nets from the paper. Fold the paper along the lines drawn and create a cube from each net.You could even draw the numbers/dots on the six squares as seen on a pair of dice. 
  6. List the properties that seem to be common for the various nets that you came up with.
  7. Compare the area and perimeter of the different nets.