CS 1, Assignment 1, Problem 1: Picobot
Zach Dodds and Wynn Vonnegut
Harvey Mudd College
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.
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
-> 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.
||Picobot -- a Karel-like assignment suitable for the first problem of the first assignment of a first CS course
||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.
||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.
||The full spectrum from easy to impossible. Every student completes the first environment. No
student has ever completed the most difficult one.
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.
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.
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.
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