Lab 1: Picobot
Lab 1: Picobot
If you find typos or problems with the lab instructions, please let us know.
After completing this lab, you should be able to do the following:
Reason about the behavior of a simulated robot in a simple state-machine language
Methodically trace the execution of a simple state-machine program
Work with a partner using pair programming
Find and fix errors in a simple state-machine program
Write a program to control a simulated robot so that it navigates through both an empty world and a maze environment
Save and submit your files for feedback
During SPIS, most of your lab assignments will use Pair Programming. This is a system where two people collaborate on a single solution to a coding problem. When doing pair programming, you will work alongside your partner in real-time.
In this system, you have two different roles, and you will alternate between them. These roles are being the driver and being the navigator. The driver is the one typing, and the navigator provides guidance to the driver as to what to do.
Please take a moment to visit this link and learn more about Pair Programming.
To "learn the do's and don'ts" of pair programming and to see pairs in action, you may also want to check out this entertaining (if a bit corny/cheesy) video about pair programming from North Carolina State University: An Introduction to Pair Programming for Students.
In this lab, you will first do some coding individually. But just as in the previous lab, work in-sync with your partner. Then, after you have each become familiar with the basics of Picobot and have finished the first introductory assignment, you will switch to pair programming for the remainder of the lab.
You can use the work stations in the lab or your own laptop. However, when you do pair programming, we want you to be behind a single machine (either work station or laptop).
This first part of the lab is individual. However, work in-sync with your partner, and support each other. Make sure you are both finished with this individual part and are both comfortable with Picobot before moving on to the pair programming portion of the lab. Don't rush each other. It is okay to take your time. If you help each other, don't share answers, but explain principles and clear up misconceptions.
For a resource on Picobot, check out Chapter 1 of the book CS for All (or its PDF version). By the way, this is just one of the chapters of a useful online textbook that may be helpful as you start to learning coding and Python. But if you are eager to get started, and we hope you are, you can focus on this chapter on Picobot first.
Based on the information in this CS for All chapter or what you learned in class, try to answer the following questions for yourself. If you are not sure, feel free to discuss with your partner or a mentor. You don’t need to submit these answers, but make sure you are able to formulate an answer for yourself. Confer with your partner to see if they are thinking the same.
Describe the following rule in English:
1 x**x --> N 2
What is the difference between the "*" and the "x" in the description of Picobot’s surroundings?
Write a single Picobot rule that would cause Picobot to go W and crash into a wall (Picobot will report an error if you try this)
Now, let’s start writing a simple Picobot program. Click on this link for the Picobot simulator: https://www.cs.hmc.edu/picobot/
Start out by looking at the starting rules that are given to you when you first get to the simulator site. Can you figure out what Picobot will do when you enter these default rules? Run the code and verify your answer. Is it doing what you expect it to do? If not, make sure you understand why before moving on. It is an important skill not only to solve problems, but to understand exactly why your solution works (or not).
Also, feel free to play around a bit and modify the starter code. This is a great way to get going. By the way, whenever you change the code, make sure to click the Enter rules for Picobot button. Otherwise, the changes are not registered and Picobot will simply execute the previous code, confusing you to no end most likely, as it did for us when we forgot to do this :-)
As a final task before moving on to the pair-programming parts of this lab, try to create the following program. Again, you can ask your partner or the mentors for advice and help, but make an effort to solve this alone. Of course. don’t stay stuck and don’t be afraid to ask for guidance, but don’t ask for the answer. Ask for help in clearing up any concepts that trouble you, and get to the point where you can solve this problem yourself. We realize Picobot programs are not immediately intuitive, so don’t worry if it takes you some time. This is natural.
The task is to have the Picobot bounce off the walls going east-to-west and back. It should move west first until it hits the wall, then turn around and follow the same track east until it hits the wall, and then turn around and do the same thing again (always staying in the same row). Basically, Picobot should end up pinging back and forth, west to east and back, always using the same row.
Once both you and your partner are done with this and you both feel comfortable with Picobot, move on to the next section where you will work on problems together.
For the remainder of the lab, you will be doing Pair Programming. This means that you and your partner should work behind a single computer. It does not matter whose laptop you are using or if you are on a lab workstation under whose account you are working. Just close the other laptop or log out of the work station, and both sit behind the same machine. We will use GitHub (see Lab 0) to make sure you both have access to the all the code in the end, regardless of where you did the work.
Now before we get started, decide on who will be the initial navigator and who will be the initial driver. However, make sure you switch roles frequently throughout this lab.
When working with your pair partner, you will be creating code together. As mentioned before, we want you to sit together behind a single computer when you do pair programming.
As mentioned above, we will use GitHub to make sure you both have access to the code when you are done. Also, this will give your mentor access as well, so that they can provide feedback on your work.
The process will be as follows. You will do all your code development in the Picobot simulator. Then you will copy this code to GitHub so that is is shared with your partner and with us. Don't just copy the code whey you are done with the assignment. Saving the code to GitHub frequently is a good habit in general. Having your code in a central location also allows you to retrieve it from in case something goes wrong. Also if you end your session and then want to continue working on your code the next day, make sure you save it to GitHub first before you log off. You can then retrieve it from there the next day (note: the code is not saved on the Picobot site itself and when you navigate away from the page, it is gone).
So let's set things up so you can save your Picobot code to GitHub:
One of you (i.e., the driver) should log into GitHub (link: https://github.com/).
Create a new repository. Remember, you can do this by clicking the green "New" button on the left, or the plus icon near the top right corner. This will get you to the "Create a new repository page". Under "Owner" make sure you select "ucsd-cse-spis-2023". As "Repository name", put spis23-lab01-Alex-Chris (but with your first names instead of Alex and Chris, in the order listed on the pair-partner list). Make sure "Private" is selected as the option and then mark "Add a README file". Verify these settings and then click the green "Create repository" button at the bottom.
You should now see the new repo. At the moment, it just has one file, the README.md file. Click on the pencil icon (you should see it at the top right corner of the README.md). You should now be able to add new lines of text in the README. Add your names and a sentence that describes the project (e.g., "Lab 1: Picobot project"). Then on the green "Commit changes..." button and "Commit changes" in the popup.
You will now be on a page that shows the updated README file. To get back to the repo, click on your repo name (you should see it near the top as well as on the top of the file followed by /README.md).
Once you are back in your repo, you should see "Add File". Click there and select "Create new file". Where it says "Name your file ...", put the name of your new file. In this case, let's create the file emptyroom.txt. You do not need to add any text to the file yet. Click on "Commit changes ..." to commit (i.e., save) the file to GitHub.
Repeat this process to also create the file maze.txt. Once you are done, you should now see both these txt files in your repo as well. When you want to edit the content of these files later (i.e., paste your Picobot code there), you can click on the filename and then on the pencil icon to edit the file.
Finally, we need to add your pair partner as a collaborator to this repo. To do this, click on "Settings" (which as the gear icon) in the top menu bar. In the left pane, click on "Collaborators and teams". It will prompt you for your GitHub password again. On the page that appears, click on the green "Add people" button. In the search bar, add the github ID of the pair partner. Select their ID and you can keep "Admin" as the selection. Now click on the "Add ... to this repository". That should be it. Both of you should now have complete access to the repo.
To verify, log out of GitHub and switch who is driver and navigator.
Now the other driver should log into their GitHub account. Can you find the new shared repo? Note, if you click on the icon in the top right corner, a menu will appear where you can select your repositories or your organizations. You can try looking in the SPIS github organization for your partner's repo or see your own repositories.
Make sure it all makes sense and don't hesitate to ask questions.
Go back to the Picobot site on your browser. Write a program to make Picobot visit every cell in the empty room, no matter where it starts. This is the Picobot problem you see when you get to the Picobot landing page.
Hints to get you started: You both have a program to sweep the room left to right. Can you come up with a simple change to not always cover the same area, but also move north once you hit a wall? This will get you a good part of the way there, covering (on average) half the room. But you will probably get stuck in a corner at the end. You’ll need to add a rule to get you out of this situation and move you to the yet-uncovered part of the room. What would you do next? We encourage you to think carefully about what your states mean before you start implementing rules. This is true in general: think first, then code. Or, as the meme goes, "weeks of coding can save you hours of planning."
Once you are finished with this problem, save your code for the empty room solution in the file emptyroom.txt in your GitHub repo, and then move on to the next problem.
Once you have successfully covered the empty room, use the MAP –> button to find the maze, and implement the maze-covering algorithm. Think carefully about your states. You will likely want to use 4 states where each state represents a different direction in which you are currently moving.
A good way to solve this kind of maze is by using the "right hand rule." Basically, the idea is best explained if you imagine you are Picobot and you have to go through this maze with your eyes closed (so you can only feel what is directly around you). If you would keep your right hand always touching a wall on your right, and keep following that wall as it twists and turns through the maze. Eventually, you will cover the entire maze. Convince yourself that this is indeed true. Does this algorithm make sense? In what kind of maze would this break down? (Fortunately, we are given a maze where this idea will work)
Now, how can you implement this in Picobot? If you want, here are some hints to get you started: Consider carefully which wall your hand will be on if you are heading in each direction, and this will help you figure out which direction to move, and when to change states. For example, if you are heading north, your hand is on the east wall. So as long as there is a wall to your east, and no wall to the north, you keep going north, dragging your hand along the wall. If the wall to the east suddenly disappears, then you turn in that direction to follow the wall. If you suddenly hit a wall to the north, then your hand sweeps around the corner between the eastern and northern walls and you turn in the process so that you are facing west and your hand is now on the northern wall. Make sure you understand all of the possible turns and transitions before you start writing rules. If anything is unclear, ask a tutor. We repeat: do not write rules until you have a firm understanding of what each state means and how different environments affect your direction and forward progress. It’s all about keeping your right hand on the wall …
When you are done and have tested your solution thoroughly, make sure you save your code in the file maze.txt on GitHub.
Are you up for more? There are some fun challenge problems in the next section. You are highly encouraged to try these, but they are not required.
By the way, the style of coding that Picobot uses is an example of finite state machines. We will explore it further later on in SPIS. The concept of state machines is particularly useful if you are interested in robotics, for example. However, many other applications use this style as well.
When you've mastered the maze and you're ready for more, try some optional challenge problems (some of these are super challenging). You don’t need to submit these, but you could if you wanted to; just create additional files in your GitHub repo with .txt file extensions, and put an explanation for each of those files in your README.md file.
For example, you could challenge yourself with some of the following problems:
For the empty room, see if you can use only 6 rules.
For the maze, see if you can use only 8 rules.
Scroll through the different maps and see if you can write Picobot programs to solve these other rooms.
For the empty room, can you build a machine that covers each cell in the room exactly once?
Imagine Picobot is a Roomba vacuum cleaner. You might know that the edges of a room get dustier than the middle of the room (dust kicked up accumulates near the walls). Can you program Picobot to cover the cells that are adjacent to walls at least twice and cover interior cells exactly once?
Can you write a single program that works for ALL provided mazes?
Can you formulate other criteria you might want to solve? Are there unsolvable requirements?
We hope you enjoyed these Picobot puzzles...