# 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.

## Picobot

Written in Javascript, Picobot has not yet become completely browser-independent:

## 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.