cis32 project #1

sklar/spring-2006

  • The project is due in class on Wednesday March 22. DEADLINE EXTENDED TO FRIDAY MARCH 31.
  • Bring a hardcopy to class, which includes:
  • This project is worth 15 points in total. The distribution of points is indicated below.

    Project Description
    For this project, you will use LEGO Mindstorms robots and the NQC programming language to program a robot that can navigate around a grid.
    The grid will be composed of segments that look like this:
    		     The full course will look like this:
    The intersections between the blue and black lines will be made of gold foil, which reflects light. This means that your robot's light sensor will return values that fall within ranges like this:
       0 < black < blue < white < gold < 100

    You will write a program for a robot that can follow a blue or black line and can keep count of how many gold intersections it crosses, so that we could give it a task, say of starting at point A and ending at point J, and the robot would know how to complete this task.

    The robot needs to be able to complete the following tasks:

    1. Go from any one point to another given point, on an empty course free of obstacles.

    2. Find its way from any one point to another, on a course that has obstacles on it so that some of the intersections are blocked--meaning that the robot must backtrack in order to complete the route.

    3. Find the SHORTEST way from any one point to another, on a course that has obstacles on it so that some of the intersections are blocked--meaning that the robot must employ a search algorithm in order to determine the shortest route. Once the route has been determined, presumably by the robot following a search path from the starting point that includes backtracking to get to the ending point, the robot should then return to the starting point (from the ending point) by following the shortest path (in reverse, obviously).

     

  • Part I. Design (4 points)
    The first part of the project can be done on paper, away from the robot. You need to design algorithms that will solve each of the three problems. The algorithm(s) should be designed to work within the constraints of the NQC programming language (i.e., using 16-bit integers). You can design three separate algorithms, for each of the three tasks described above, or one algorithm that will work for all three tasks.
    This portion of the project should be written in pseudo-code with documentation explaining how your algorithm(s) work.

  • Part II. Implementation (5 points)
    The second part of the project is to take the design (from part I) and write the NQC code that implements the algorithm(s).
    This portion of the project should be written in NQC with comments explaining the code.

  • Part III. Experimentation and Results (5 points)
    The third part of the project involves running experiments to show how your algorithm(s) work. Keep a log of which things you try and the results you get. Explain what about your algorithm works and what does not work.
    Following the Hints and advice below, make a list of the sub-tasks that you tried. Document your success and failures with each sub-task. Record what you had to change to make the sub-tasks work.
    If you get the tasks working, record how long it takes the robot to complete the tasks.

  • Part IV. Group assessment (1 point)
    Describe your role in the group project. What did you do? What did your teammates do? Briefly explain how everyone contributed (or not) to the success of the project.

     

  • Hints and advice