CS 1, Assignment 1, Problem 1: Picobot

Zach Dodds and Wynn Vonnegut
Harvey Mudd College
dodds@cs.hmc.edu
http://www.cs.hmc.edu/~dodds

YAK !?

That is to say, Yet-Another-Karel !? Surely such a thing is redundant in 2010 -- right?

This assignment, Picobot, is why we don't think so.

Simulator

Written in Javascript, Picobot runs entirely client-side:

Picobot's World!

Overview

This assignment has been used as part of Assignment 1 of CS 1 for the past several years at Harvey Mudd College. As such, it is the first exposure to computer science for most of our students.

Picobot's basic idea

Students are challenged to specify rules that will guide Picobot within its environment, which can be any of several grids of square cells. Picobot can sense the occupancy of neighboring cells to its N, E, W, and S. It can move to the N, E, W, or S -- or stay in place. Picobot also has the ability to remember a single number from 0 to 99: this number is called its "state." Picobot starts in state 0.

A Picobot program is simply a list of rules of the form

0 xxxx -> N 0

which says, "If Picobot is in state 0 (the first piece of the rule) and has no walls to its N, E, W, or S (the xxxx of the rule), then (the arrow) move to the north (the N of the rule) and switch to state 0 (the final piece of the rule)." Every rule follows this pattern of

startingState NEWSsurroundings -> moveDirection nextState

Each step, the rule list is considered anew from the top.

The students' task is to create rules that guide Picobot to traverse every empty cell in its environment. Their rules need to work regardless of starting position, though we encourage them to work incrementally, which may at first include constraints on the starting position.

The environments we require are the empty room and the maze, shown here. As an option, we offer more challenging environments to provide a sense of how open-ended -- and computationally sophisticated -- this model is. To see these, click the MAP buttons in the Picobot environment for non-IE browsers.

Picobot requires less than 20 minutes to present thoroughly; we do so in the first lecture of CS 1. The problem it solves is both real (iRobot has made millions of Roombas that solve the continuous version) and extensively studied by the algorithms community (we mention the undecidability results that are known for this automaton). It requires no background nor infrastructure beyond a browser. As such, it is a good "equalizer" among students of widely varying backgrounds.

Materials

A local copy of the Picobot assignment description is here.
The HMC-hosted Picobot assignment description is linked here.
Our Picobot-specific Powerpoint slides are here, including the pair-and-share activity we use.
Our first lecture in CS 1 This shows the context in which Picobot appears.
The Picobot environment appears at this link for all browsers except IE and this link for IE.
Picobot's Javascript source is readily available from the source of either of the above pages.

Metadata

Summary	Picobot -- a Karel-like assignment suitable for the first problem of the first assignment of a first CS course
Topics	Computer science, broadly construed: (0) the algorithmic essence of an everyday application: the vacuum-coverage problem, (1) building, refining, and using a mental model of a computational system, (2) programming creatively within that mental model, (3) the quantitatively-measured complexity of software, and (4) computability.
Audience	An advantage of requiring no CS background at all is that this activity can be used with almost any audience. We have used it in orientation activities, in high-school outreach programs, and in hands-on recruiting sessions when we want students to walk away feeling challenged in ways they had not anticipated.
Difficulty	The full spectrum from easy to impossible. Every student completes the first environment. No student has ever completed the most difficult one.
Strengths	We feel Picobot retains the fundamental advantages of Karel: Picobot is simple enough to explain and practice in-class -- in less than 20 minutes. It lends itself to pencil-and-paper thinking, which we use as a "pair-and-share" activity with the 75 students in our very first lecture of CS 1. Picobot is a true computer science activity: students not only program, but more importantly, they build and refine a mental model of a computational system and creatively interact with it. Picobot has a graphical interface that needs only a browser, similar to some Karel simulators. The development and simulation environments fit into a single-screen webpage. We find this helps early in the term, because every student can access and complete the assignment, even if they have no computer or, more common, are struggling in getting their computer(s) set up. (They simply borrow a friend's.) But the additional value that we have seen Picobot provide lies in its differences from other Karel-like approaches: It is language-independent: it does not use Python, C, C++, Java, Scheme, or any other language. Because of this language-independence, Picobot is background-independent: feedback indicates that it challenges equally students with no background at all and students with extensive background. Because of this background-independence, it reduces the "show-off" factor that we have found can creep into early CS 1 lectures among certain students. Because CS 1 is required, every student at the college, regardless of major, takes this class and does this assignment. Picobot provides natural hooks into many facets of CS. In the first lecture, we use Picobot to motivate CS as a crucial link in real-life applications: Picobot's task is exactly a discretized version of the task of iRobot's Roomba line of vacuums. CS as the study of complexity: the number of Picobot rules and the number of Picobot states are quantitative measures of complexity that students with no CS background at all intuitively grasp. CS as the study of computability: there are environments that Picobot provably cannot cover. We note this and point out how the computational model can be increased to handle such environments. Unlike more sophisticated Karel-like simulators, Picobot is simple enough that as a final CS 1 project at the end of the semester, CS 1 students can and do succeed in creating - from scratch - Picobot's parser, execution engine, and graphical simulator. This brings the CS 1 experience full-circle and emphasizes to the students how much understanding and computational savvy they have gained. Like Picobot itself, this final project has consistently been rated as one of the most "worthwhile" assignments in evaluations by students.
Weaknesses	One weakness of Picobot might be that it seems "off the primary path" of the CS 1 course that it introduces. This is true -- but only when the course is considered very narrowly as an introduction to programming with Python (or Java or Clojure...). Yet it is that narrow view that we want to discourage. In that sense, Picobot helps us with our desired message -- namely, that CS is a field both accessible and intellectually challenging that happens to contain programming as a subset. Students have also suggested various syntactic shortcuts that would enable them to write Picobot programs more efficiently. We have not implemented any of these. However, we use such suggestions to encourage students to write their own Picobot -- and many do, as a final project in the course.
Dependencies	None Well, at the moment, the support is better in non-IE browsers than IE browsers. But it does work in both - unfortunately, it's different for IE than the rest of the browser world.
Variants	The primary variant was mentioned above, i.e., writing the parser, execution engine, and simulation environment that is Picobot. This is one of four options for our CS 1 students' final projects -- and is a popular one. A second variant, built into our non-IE simulator but not advertised, is the ability to drop and pickup markers (red "pebbles") in the environment. This enables any environment at all to be cleared.