mp_racing

Radical Racing Robots

Due: Sep 15, 23:59 PM

Learning Objectives

  • Practice fundamentals of formal logic
  • Experience processing multiple data streams and using ‘black-boxed’ code
  • Review basics of conditionals, loops, the basics of file I/O and state-based decision-making
  • Explore useful Python control structures (continue, break, is)

Getting set up

From your CS 277 git directory, run the following:

git fetch release
git merge release/mp_racing -m "Merging initial mp_racing files"

You will find the relevant code and data as sub-folders within mp_racing.

Assignment Description

The year is 20XX and robot racing is the up-and-coming sports sensation. You and your friends have gathered together to show that you have what it takes to be the champion – and while your friends have built a functional frame for your racingBot, it is up to you to write (most) of the code! In this MP, you will be working to complete the necessary code to build a racing robot capable of autonomously traveling a racetrack and making decisions about where to move based on its current and past position as well as an input list of cargo.

Building up the racingBot class

The first part of this mp is defining all the variables and support functions necessary for your robot to track its current state and make decisions about it’s next move. While significant parts of this code have been provided to you, in order to accomplish this task you must implement the following class functions:

loadTrack()

None loadTrack(string fileName)
# loadTrack reads in fileName line by line
# The first line contains the starting position as (row, column) coordinates [0, 0 is top left here]
# The rest of the file contains the racetrack information as a text encoding of a 2D grid
# loadTrack should set the current position (self.curr) based on the first line as a (row, col) tuple.
# loadTrack should create a 2D array (self.map) based on the second line

At the start of the race, your robot is provided with a ‘data packet’ (a text file) containing the robot’s start location and a two-dimensional map of the racetrack. The default racetrack is represented by a numeric text grid where 1s represent valid track and 0s represent out-of-bounds areas. Write a function loadTrack which takes as input a text file of unknown size and stores the start position as a tuple and the map as a two-dimensional array. The coordinate system here may seem unusual but makes the loading of the track easier to code – the top left corner corresponds to position (0,0) and position (2,0) is the third row first column. Stated another way, you can picture the coordinate system as (y,x) or (row, column).

You may assume all rows are equal length but you should be able to handle an arbitrary number of rows and an arbitrary row length. While for parts 1 the map will exclusively have 0s and 1s, in part 2 we introduce ‘special’ squares which are defined by other single digit numbers (ex: 2-9). Your solution should be able to handle all possible single digit numeric inputs.

HINT: Take a look at RacingBot’s constructor (__init__) when writing loadTrack. All necessary variables have been provided.

loadCargo()

None loadCargo(string fileName)
# loadCargo reads in inFile line by line
# Each line of the file contains a cargo object (see cargoObj class -- which takes in a single int)
# loadCargo should append each object in the file to the cargo list

At the start of the race, your robot is provided a second ‘data packet’ (a text file) containing a collection of cargo the robot is required to carry. Write a function loadCargo which reads in each line of the file and stores each one as a cargoObj. Note that it is possible for the file to be empty (contain no cargo), to contain more objects than the racingBot can store (MAXCARGO=5), or for the file to contain duplicates of cargo (the same number multiple times). Your solution must store each line as a separate object, regardless of the value of that cargo and should store the first five objects in the file.

getPos(), getMap(), and getCargo()

<class 'tuple'> getPos()
# Accessor function returns a tuple of the current location of the robot
List[List[int]] getMap()
# getMap should return a two dimensional list of integers
# The list should be indexed first by row then by column
# Ex: getMap()[2][3] would look up the second row, third column
List[<class 'cargoObj'>] getCargo()
# getCargo should return a list of cargoObj objects 
# If your robot has no cargo, return the empty list

At the start of the race, your robot is provided with a starting position and the input map. For this particular MP, all necessary variables for the class have been given. However it is good programming practice to provide clear access to the value of key variables without providing direct access to them. After all, you may choose to name a variable very differently from someone else or store a dataset in a very different way!

To ensure that your code is ‘compatabile’ with other functions and reusable in other contexts, you should get in the habit of writing accessor functions. These functions, getPos, getMap and getCargo take no input and returns some value stored in the racingBot [its current position as a tuple, the loaded map as a 2D array, and the list of cargo as a list of objects of type cargoObj].

checkAvail() and checkSquare()

List[Tuples] checkAvail()
# checkAvail has no input parameters
# checkAvail returns all available positions for movement as an ordered list of tuples
# The return order should always be clockwise
bool checkSquare(<class 'tuple'> pos)
# checkSquare takes in a tuple storing a (row, col) position of the racetrack (the map)
# It should return True if the input position is available for movement and False if not
# It should check and be aware of the physical boundaries of the track (Ex: Position (-1,-1) is never valid)
# (If necessary) it should check and be aware if the square being checked is a distance of one away.
# Outside of that, a valid square is any square which has a non-zero value.

As your robot is fully autonomous, it will have to frequently check the available paths to move towards. Make the necessary modifications to the function checkAvail and write the function checkSquare to enable basicMovement for the racingBot.

Both functions together work as a set of predicates defining what an ‘available’ space is. Specifically, given \( row \in [0,…, len(row)-1] and col \in [0,…, len(col)-1] \), both of which must be True:

  1. (row, col) must be a distance of one from the racingBot’s current position.
  2. The value in the map at position (row, col) must be non-zero.

To make error detection, auto-grading, and several other functions in this assignment easier, your list of available squares should always proceed in a clockwise direction. That is to say check if 12:00 (North or row-1) is available, followed by 3:00 (East or col+1), then 6:00 (South or row+1), then 9:00 (West or col-1)).

Note: Your list of available squares MUST include the previous square you are in (even though your robot is not allowed to move backwards). The logic on making that movement decision is made later – see basicMovement and objMovement for details.

Running the racingBot

The core functionality of your racing bot is straightforward: given a two-dimensional map of the racetrack and a starting position, your robot should traverse the racetrack until it receives the signal to stop racing. To assist you in implementing this, a function runRobot has been provided (described below) to handle the logic behind taking steps and recording the movement to a file. Your task is to ‘fill in’ the missing parts of the racingBot code by implenting both basicMovement and puzzleMovement.

runRobot()

None runRobot(int numSteps, string outFile)
# runRobot takes as input an integer (steps) and an output filename (outFile)
# The robot should begin by writing its current [starting] position to outFile
# For each step (while the robot continues to run), the robot should run makeMove()
# After running makeMove(), it should write its new position to outFile
# If the robot fails to move to a new square after makeMove(), the robot should stop running

You do not need to edit runRobot but knowledge of how it works is important for both writing and testing this MP. runRobot takes as input an integer specifying the number of steps the robot should take before stopping and an output filename. This output file records the path the robot took from its starting location to its final location as a line-separated list of positions. That is to say, if the robot starts at (1,1) then the first line of the file is “1 1” followed by whatever location the robot moved to during the first step.

It’s important that your robot not get damaged during the race. Accordingly, when the robot gets ‘stuck’ (the previous and current square are the same), racingBot immediately terminates after printing the current square. So for example if the robot gets stuck at position (1,3) the outFile’s last two lines would both be “1 3”.

Note Unless the robot gets stuck, there should be a total of N+1 lines for N iterations, as the first line is the starting position.

Consider If the robot did not terminate when ‘previous’ is equal to ‘current’, what would happen to the robot the next time racingBot tries to take a move?

basicMovement()

None basicMovement(List[Tuples] avail)
# basicMovement takes in a list of available spaces (as tuples) and returns nothing
# Instead, it updates the previous and current position of the robot based on the available list of spaces.
# If there are multiple options, basicMovement should prioritize moving in a clockwise direction.
# If there is no available movement, the racingBot should choose to 'move' in place by setting the previous square
# equal to the current square. This will automatically stop robot movement (see runRobot for details)

The racingBot should move one square in a cardinal direction (either row increases or decreases by one or col increases or decreases by one but not both) away from its current position but cannot move backwards.

When deciding on a direction to move, if multiple moves are available and valid, then prioritize movement in a clockwise priority. That is to say, if north-facing movement is available, move north; else if east facing movement is available, move east; else if south facing movement is available, move south; else if west facing movement is available, move west.

If there are no valid moves, racingBot should stay in place by setting it’s previous position to its current position. This will stop the racingBot on the next iteration (see runRobot).

Extra Credit: puzzleMovement()

None puzzleMovement(int mval)
# puzzleMovement takes in an integer which stores the value of racingBot's current position in the stored map
# puzzleMovement does not return any value but must update the previous and current position of racingBot
# Based on the value of this square, it should run through a series of logic statements to determine movement
# Unlike basicMovement, puzzleMovement is allowed to move backwards and you may assume all four directions
# are 'available' for movement.

At the highest difficulty for the competition, squares on the track have been modified to contain logic puzzles that the robot must solve in order to determine its next move. If there is a logic puzzle in a square, then it is guaranteed to be a four way intersection. (Logic pop quiz: Is the converse true?)

As your robot must come to a complete stop to ‘solve’ each puzzle, these squares – and these squares alone – allow the robot to turn around and move in any direction. For all definitions below, let \( C \) be the list of objects carried by the racingBot and let \(x, y, z \in C \). It is possible for multiple logic statements to be true – to preserve a single unique path you should prioritize the statements in the order in which they are listed here. Note that this may not always follow clockwise order.

Note Some rules may not be resolvable – for example a rule using three objects (x, y != x, and z != x, y) should always evaluate as ‘False’ if there are not three distinct objects. But be careful how you interpret certain logic statements. For example, \( \exists x \exists y \) is valid with a single object (x=y) while \( \exists x \exists y \neq x \) is not valid.

IMPORTANT! It is entirely possible for two objects to have the same value (in fact some tests look for this) despite being different objects. Note the distinction between the object and its value. \(\forall x, \forall y \neq x P(x,y) \) is a statement that P(x,y) is true for all objects x and all objects y (that are not object x). \( x.v == y.v\) a statement that the value of x and the value of y are equal.

Reminder RacingBots can move backwards inside of a puzzle square! The logic here does not use the previous square as a variable. Likewise a list of available spaces is not a part of the logic either – you may assume that puzzle squares always have available squares in all four cardinal directions.

Squares labeled 2 have the following logic:

(South) \( \forall x \exists y \neq x \mbox{ , } (x.v == y.v) \)

(North) \( \exists x \mbox{ , } (x.v == 1) \)

(East) \( \forall x \mbox{ , } (x.v > 5) \)

(West) \( \exists x \mbox{ }\forall y \neq x \mbox{ }\forall z \neq x, y \mbox{ , } (x.v > y.v + z.v) \)

Squares labeled 3 have the following logic:

(North) \( \exists x \mbox{ , } (x.v == 2) \)

(South) \( \forall x \mbox{ }\forall y \mbox{ , } (x.v \neq y.v) \)

(East) \( \forall x \mbox{ , } (x.v < 3) \)

(West) \( \forall x \mbox{ }\forall y \neq x \mbox{ }\forall z \neq x \mbox{ , } (x.v < y.v + z.v) \)

NOTE: Unlike basicMovement, the provided data does not include an exhaustive set of files for you to test locally. You can either modify some existing tracks or rely exclusively on the autograder. The former is recommended – track 6s, 7w, and 8s all give a minimally relevant test case for moving in a specific direction for squares 2 or 3. By modifying the cargo loaded into the robot, you can figure out what contents for a racingBot would make any of the above expressions true.