Objectives

The main purpose of this assignment is to get comfortable programming in Python. It will also provide a small first step in thinking about some of the issues that we will explore in this class, in particular mapping and efficient exploration.

Part 1: Warm-up

Python Basics

Get started by completing one, or both, of the following tutorials:

• https://www.programiz.com/python-programming/tutorial.
• https://www.w3schools.com/python/

Feel free to skim the tutorials above if you are already comfortable programming in Python. If you are new to Python, I strongly encourage you to work through each step carefully. It will probably take a couple of hours, but the time spent will pay dividends throughout the semester.

Type Hints

The Python language is “dynamically typed”, i.e. we don’t need to declare the types of variables when they are created, and we don’t need to specify the return types for functions. This is one of the features that makes Python code concise and uncluttered. Unfortunately, it can also make Python code error prone and difficult to read. We can optionally declare types in Python using “type hints”. These aren’t used directly by the Python interpreter, but they can be used by code analysis tools and code editors. The following tutorial provides a quick introduction to Type hints. Some of the code we see in this class will make use of Type hints.

• https://www.pythontutorial.net/python-basics/python-type-hints/

Part 2: BumperBot

For this portion of the project you will develop the control algorithm for an extremely simple robot. Here are the properties of the robot and its environment:

• The robot’s location is specified using a pair of integer coordinates.
• On each time step the robot may choose to move one step North, South, East or West.
• If the robot attempts to move into a location containing an obstacle, the movement will fail and the robot will remain in the original location.
• The robot is provided with perfect information about its location.
• Initially, the robot has no knowledge about the location of obstacles in the environment.

Your goal is to develop a control algorithm for this robot that allows it to efficiently explore its environment and record the locations of all obstacles it encounters.

The following files are provided:

• simulator.py FINISHED
• util.py FINISHED
• robot.py STUBBED - Your code goes here.

The file robot.py contains a stubbed out Robot class. You must complete the unfinished step method so that it conforms to the provided docstring. The file simulator.py is a command-line application that may be used to test your Robot implementation. You can get usage information by executing the script with the -h flag:

$ python simulator.py -h
 
 usage: simulator.py [-h] [-n NUM_STEPS] [-d] [-s SPEED] ROBOT_FILE OBSTACLE_IMG
 
 positional arguments:
   ROBOT_FILE            Name of Python file containing Robot class.
   OBSTACLE_IMG          Grayscale image. Non-zero pixels are obstacles.
 
 optional arguments:
   -h, --help            show this help message and exit
   -n NUM_STEPS, --num-steps NUM_STEPS
                         Number of simulation steps to execute. (default: 100)
   -d, --display         Show robot visualization (default: False)
   -s SPEED, --speed SPEED
                         Visualization speed (in hz) (default: 33)

The simulator uses the PyGame library to render the robot. You can install PyGame on your system using pip:

pip install --user pygame

Note that the “arena” presented to the robot is provided as a black and white image where the non-black pixels represent obstacles. Here are some images that you can use for testing:

• tiny.pgm
• small.pgm
• medium.pgm
• large.pgm

An example invocation of the program might look like the following:

$ python simulator.py robot.py small.pgm --display
 Obstacles discovered: 4/10: 40.00%

Advice

• As a first step, I would suggest implementing a completely random controller. This won’t work well as an efficient exploration algorithm, but it will allow you to confirm that your obstacle-recording code is working correctly.
• You must develop the code for this assignment independently, but you are free to discuss strategies with classmates. Don’t forget to provide an acknowledgment statement if you discuss your approach with another student.

Submission

Submit your completed solution to Gradescope. For the Gradescope tests your robot will be allowed enough steps so that an efficient search strategy could discover most or all of the obstacles. Your grade will be based on the percentage of obstacles discovered across a suite of test environments.