LMICSE: Lego Mindstorms in Computer Science Education

Goal

Your team will build (as per the assembly instructions you’ll get in the lab) a robot that will wander randomly around a room, being careful to avoid two kinds of obstacles: (1) anything as tall as the robot is, and (2) dark-colored squares on the floor. Whenever either of these obstacles is encountered, the robot must back away, unless both are encountered in front and in back of a robot, in which case the robot must turn 90 degrees left or right. Your robot will be expected to handle navigation for 5 minutes.

Your team will also design a navigation program for achieving this behavior. You will have to design the main thread(s) and the semaphores to coordinate all of the navigation threads.

Robot Design

In the lab, there will be a handout on the construction of the robot. Each team will work with the same standard chassis, which will have two light sensors pointed toward the floor to detect dark squares, and a third light sensor mounted above the robot’s infrared (IR) port to pick up IR reflections from tall obstacles. The robot will run on treads. A separate motor will be used to control each thread.

Navigation Program Design

You’ll need to use at least four threads to coordinate the navigation of your robot: (1) a very short thread to make the RCX’s IR port work as a proximity sensor for detecting “tall obstacles;” (2) a thread to implement the actual detection of “tall obstacles” in front of the robot; (3) a thread to implement the detection of dark squares on the floor; (4) a main thread to start up and coordinate the other threads, and to implement the “random roving” behavior.

The program is to be written in the “Not Quite C” (NQC) language. You’ll find the NQC Programmer’s Guide to be a great resource for understanding how to control motors, define loops, and use macros to define semaphore calls. Since this project’s educational goals focus on the critical section problem and not on sensor interpretation, you’ll be given the basic code for the sensor threads (#1, #2, and #3 described above), but you will have to design the main thread(s). You will also have to define your own semaphores to coordinate all of the program’s threads. These semaphores should be viewed as pairs of variables – one of which coordinates amongst the threads, and the second of which tells a thread whether or not it is ok to execute a critical section – along the same lines as Peterson’s Algorithm as defined in chapter 5 of the Silberschatz text.

Here are some guides for the design of the threads. All of your threads will be defined as infinite loops. As the program runs, your robot’s default action is to wander randomly around the room. The main thread should therefore periodically, (say, at least every 7 seconds) change the direction or speed of one or both of the motors driving the robot, as long as none of the obstacle-avoidance threads have grabbed control of the motors.

Your obstacle-avoidance threads (#2 and #3) will also be responsible for “grabbing control” of motors to avoid the obstacle – hence you’ll need to add motor manipulation code to these threads. The actions for obstacle avoidance should not run for longer than 3 seconds.

The trickiest part of the program is to make sure that the right thing happens if two obstacles are encountered at once. One example of this issue is a situation in which a dark square is behind the robot and a tall obstacle is in front of the robot. Another example is a situation in which the robot starts to roll over a dark square while avoiding a tall obstacle.

Note that there is some leeway in claiming that a robot successfully avoids obstacles! That is, because we’re using a limited number of sensors, it’s possible for a robot to roll over a corner of a square or back into a tall obstacle, yet still be labeled a successful project. However, rolling over the middle of a dark square or bumping into a tall obstacle while going forward will definitely be counted against the project’s score.

What You Need to Hand In

1. A 5-page report of how you designed your program, how you calibrated your sensors, what difficulties you encountered, and how you surmounted them. Last but not least, your report should discuss your experience with this lab project, what you feel you’ve learned about the critical section problem, possibly including pictures. Make sure you describe what goal choice you made, what sensors you used, and how you used/calibrated them. You should also discuss what difficulties you encountered in using your sensors, and how you surmounted them.
2. A printout of your program for controlling the robot, documented with comments indicating the assumptions you made.

Overall Project Hints

As described in the NQC manual, RCX motors keep running until they are told to stop. So, if you want a program to make it’s A and C motors to run forward for 2 seconds at speed 3 and then stop, in NQC you can write

Fwd(OUT_A+OUT_C,2);
Sleep(200); // make the current thread sleep for 2 seconds
Off(OUT_A+OUT_C);

The light sensors, due to inconsistencies in the manufacturing process, may not all have the same sensitivities, so you might have to change some of the threshold constants in the provided code.

You can find the code for the IR proximity detector in the NQC user manual in chapter 9, and in chapter 8 you can find code for checking whether a light sensor in raw mode has exceeded a threshold.

START OUT SIMPLE! Don’t try to get all threads working at once! First try to get the random roving to work, then add one of the obstacle avoidance threads, coordinate them, then add the other obstacle avoidance thread, and finally get all of them coordinated.

Acknowledgements

This lab was created by Frank Klassner.