Problem Set 6

# Problem Set 6: Simulating robots
# Name: Niki Castle
# Collaborators: none
# Time: ~8hrs + testing time

import math
import random

import ps6_visualize
import pylab

# === Provided classes

class Position(object):
    """
    A Position represents a location in a two-dimensional room.
    """
    def __init__(self, x, y):
        """
        Initializes a position with coordinates (x, y).
        """
        self.x = x
        self.y = y
    def getX(self):
        return self.x
    def getY(self):
        return self.y
    def getNewPosition(self, angle, speed):
        """
        Computes and returns the new Position after a single clock-tick has
        passed, with this object as the current position, and with the
        specified angle and speed.

        Does NOT test whether the returned position fits inside the room.

        angle: float representing angle in degrees, 0 <= angle < 360
        speed: positive float representing speed

        Returns: a Position object representing the new position.
        """
        old_x, old_y = self.getX(), self.getY()
        # Compute the change in position
        delta_y = speed * math.cos(math.radians(angle))
        delta_x = speed * math.sin(math.radians(angle))
        # Add that to the existing position
        new_x = old_x + delta_x
        new_y = old_y + delta_y
        return Position(new_x, new_y)

# === Problems 1

class RectangularRoom(object):
    """
    A RectangularRoom represents a rectangular region containing clean or dirty
    tiles.

    A room has a width and a height and contains (width * height) tiles. At any
    particular time, each of these tiles is either clean or dirty.
    """
    def __init__(self, width, height):
        """
        Initializes a rectangular room with the specified width and height.

        Initially, no tiles in the room have been cleaned.

        width: an integer > 0
        height: an integer > 0
        """

        self.width = width
        self.height = height
        #create an empty list for clean tiles in this room
        self.cleanTiles = []

    def cleanTileAtPosition(self, pos):
        """
        Mark the tile under the position POS as cleaned.

        Assumes that POS represents a valid position inside this room.

        pos: a Position
        """
        #add tile (as a tuple of integers) to the list of cleaned ones
        #use int instead of round because that's how the tiles are numbered
        self.cleanTiles.append((int(pos.getX()), int(pos.getY())))

    def isTileCleaned(self, m, n):
        """
        Return True if the tile (m, n) has been cleaned.

        Assumes that (m, n) represents a valid tile inside the room.

        m: an integer
        n: an integer
        returns: True if (m, n) is cleaned, False otherwise
        """
        #check the list of clean tiles
        if (m, n) in self.cleanTiles:
            return True
        else:
            return False

    def getNumTiles(self):
        """
        Return the total number of tiles in the room.

        returns: an integer
        """
        return self.width*self.height

    def getNumCleanedTiles(self):
        """
        Return the total number of clean tiles in the room.

        returns: an integer
        """
        cleanTiles = 0
        #check all tiles in room
        for i in range(self.width):
            for j in range(self.height):
                if self.isTileCleaned(i, j):
                    #tally clean tiles
                    cleanTiles += 1
        return cleanTiles

    def getRandomPosition(self):
        """
        Return a random position inside the room.

        returns: a Position object.
        """
        #because we're taking integer positions (e.g. on a tile), range for the
        #randint function must be 0 to (measurement-1)
        return Position(random.randint(0,self.width-1), random.randint(0,self.height-1))

    def isPositionInRoom(self, pos):
        """
        Return True if pos is inside the room.

        pos: a Position object.
        returns: True if pos is in the room, False otherwise.
        """
        if (pos.getX() <= width) and (pos.getY() <= height):
            return True
        else:
            return False


class Robot(object):
    """
    Represents a robot cleaning a particular room.

    At all times the robot has a particular position and direction in the room.
    The robot also has a fixed speed.

    Subclasses of Robot should provide movement strategies by implementing
    updatePositionAndClean(), which simulates a single time-step.
    """
    def __init__(self, room, speed):
        """
        Initializes a Robot with the given speed in the specified room. The
        robot initially has a random direction and a random position in the
        room. The robot cleans the tile it is on.

        room:  a RectangularRoom object.
        speed: a float (speed > 0)
        """
        self.room = room
        self.speed = speed

    def getRobotPosition(self):
        """
        Return the position of the robot.

        returns: a Position object giving the robot's position.
        """
        return self.position

    def getRobotDirection(self):
        """
        Return the direction of the robot.

        returns: an integer d giving the direction of the robot as an angle in
        degrees, 0 <= d < 360.
        """
        return self.dir

    def setRobotPosition(self, position):
        """
        Set the position of the robot to POSITION.

        position: a Position object.
        """
        self.position = position

    def setRobotDirection(self, direction):
        """
        Set the direction of the robot to DIRECTION.

        direction: integer representing an angle in degrees
        """
        self.dir = direction

    def updatePositionAndClean(self):
        """
        Simulate the raise passage of a single time-step.

        Move the robot to a new position and mark the tile it is on as having
        been cleaned.
        """
        raise NotImplementedError


# === Problem 2
class StandardRobot(Robot):
    """
    A StandardRobot is a Robot with the standard movement strategy.

    At each time-step, a StandardRobot attempts to move in its current direction; when
    it hits a wall, it chooses a new direction randomly.
    """
    def __init__(self ,room, speed):
        Robot.__init__(self, room, speed)

    def updatePositionAndClean(self):
        """
        Simulate the passage of a single time-step.

        Move the robot to a new position and mark the tile it is on as having
        been cleaned.
        """
        #NOTE:
        #based on the coordinates of the example given at the beginning of
        #the problem set, it seems that the robot cleans a tile each time it
        #stops, not every tile it moves over; this reflects that,
        #as does the code for RandomWalkRobot.

        #get original position, mark tile cleaned
        pos1 = self.getRobotPosition()
        self.room.cleanTileAtPosition(pos1)
        pos2 = pos1.getNewPosition(self.dir, self.speed)
        #test whether projected position is within room before moving
        if pos2.getX() <= self.room.width and pos2.getX() >= 0 and \
           pos2.getY() <= self.room.height and pos2.getY() >= 0:
            self.setRobotPosition(pos2)
        #if not, set a new random direction and try again
        else:
            self.setRobotDirection(random.randint(0,360))
            self.updatePositionAndClean

# === Problem 3

def runSimulation(num_robots, speed, width, height, min_coverage, num_trials,
                  robot_type):
    """
    Runs NUM_TRIALS trials of the simulation and returns the mean number of
    time-steps needed to clean the fraction MIN_COVERAGE of the room.

    The simulation is run with NUM_ROBOTS robots of type ROBOT_TYPE, each with
    speed SPEED, in a room of dimensions WIDTH x HEIGHT.

    num_robots: an int (num_robots > 0)
    speed: a float (speed > 0)
    width: an int (width > 0)
    height: an int (height > 0)
    min_coverage: a float (0 <= min_coverage <= 1.0)
    num_trials: an int (num_trials > 0)
    robot_type: class of robot to be instantiated (e.g. Robot or
                RandomWalkRobot)
    """


    timeStepsNeeded = 0
    times = []
    for trial in xrange(0,num_trials):
        #create new set of robots for each trial
        robotlist = []
        ###anim = ps6_visualize.RobotVisualization(num_robots, width, height)
        #create new room for each trial
        room = RectangularRoom(width, height)
        #create num_robots robots, add to list
        for i in xrange(num_robots):
            robot = robot_type(room, speed)
            robot.setRobotPosition(room.getRandomPosition())
            robot.setRobotDirection(random.randint(0,360))
            robotlist.append(robot)
        #go until minimum coverage is reached
        while (float(room.getNumCleanedTiles())/room.getNumTiles() < min_coverage):
            #move each robot
            for i in xrange(len(robotlist)):
                robotlist[i].updatePositionAndClean()
            #increment total time needed; doesn't need to be reset
            timeStepsNeeded += 1
            ###anim.update(room, robotlist)
    #return average
    return (timeStepsNeeded/num_trials)




# === Problem 4
#
# 1) How long does it take 1, 2, 3, 4, and 5 robots to clean 80% of a
#    20x20 room?
#
# 2) Howlong does it take two robots to clean 80% of rooms with
#    dimensions 20x20, 25x16, 50x8, 80x5, and 100x4?

def showPlot1():
    """
    Produces a plot showing dependence of cleaning time on number of robots.
    """
    #make lists for average times and number of robots
    times = []
    num_robots = [1,2,3,4,5,6,7,8,9,10]
    #find the average time for each number of robots
    for number in num_robots:
        average = runSimulation(number, 1.0, 20, 20, 0.8, 10, StandardRobot)
        times.append(average)
    #plot times with regard to number of robots
    pylab.plot(num_robots, times)
    pylab.title('Time to Clean 80% of a 20x20 Room')
    pylab.xlabel('Number of Robots')
    pylab.ylabel('Average Cleaning Time')
    pylab.show()

def showPlot2():
    """
    Produces a plot showing dependence of cleaning time on room shape.
    """
    #make lists for average times, dimensions of rooms, and width:length ratios
    times = []
    widths = [20, 25, 40, 50, 80, 100]
    lengths = [20, 16, 10, 8, 5, 4]
    ratios = []
    #run simulation on each room
    for i in xrange(len(widths)):
        average = runSimulation(2, 1.0, widths[i], lengths[i], 0.8, 10, StandardRobot)
        times.append(average)
        ratios.append(float(widths[i])/lengths[i])
    #plot times with regard to width:length ratios
    pylab.plot(ratios, times)
    pylab.title('Time for 2 Robots to Clean 80% of a Room (area 400 units)')
    pylab.xlabel('Ratio of Width to Length')
    pylab.ylabel('Average Cleaning Time')
    pylab.show()


# === Problem 5

class RandomWalkRobot(Robot):
    """
    A RandomWalkRobot is a robot with the "random walk" movement strategy: it
    chooses a new direction at random after each time-step.
    """
    def __init__(self, room, speed):
        Robot.__init__(self, room, speed)

    def updatePositionAndClean(self):
        #get original position, mark tile cleaned
        pos1 = self.getRobotPosition()
        #get a new direction
        self.setRobotDirection(random.randint(0,360))
        self.room.cleanTileAtPosition(pos1)
        pos2 = pos1.getNewPosition(self.dir, self.speed)
        #test whether projected position is within room before moving
        if pos2.getX() <= self.room.width and pos2.getX() >= 0 and \
           pos2.getY() <= self.room.height and pos2.getY() >= 0:
            self.setRobotPosition(pos2)
        #if not, set a new random direction and try again
        else:
            self.setRobotDirection(random.randint(0,360))
            self.updatePositionAndClean


# === Problem 6

# For the parameters tested below (cleaning 80% of a 20x20 square room),
# RandomWalkRobots take approximately twice as long to clean the same room as
# StandardRobots do.
def showPlot3():
    """
    Produces a plot comparing the two robot strategies.
    """
    #make lists for average times and number of robots
    StandardTimes = []
    RandomWalkTimes = []
    num_robots = [1,2,3,4,5,6,7,8,9,10]
    #find the average time for each number of robots
    for number in num_robots:
        average = runSimulation(number, 1.0, 20, 20, 0.8, 10, StandardRobot)
        StandardTimes.append(average)
        average = runSimulation(number, 1.0, 20, 20, 0.8, 10, RandomWalkRobot)
        RandomWalkTimes.append(average)
    #plot times with regard to number of robots
    pylab.plot(num_robots, StandardTimes)
    pylab.plot(num_robots, RandomWalkTimes)
    pylab.title('RandomWalkRobot vs. StandardRobot')
    pylab.xlabel('Number of Robots')
    pylab.ylabel('Time to Clean 20x20 Room')
    pylab.legend('StandardRobot', 'RandomWalkRobot')
    pylab.show()

    #Unsurprisingly, the RandomWalkRobots consistently take significantly longer
    #to satisfactorily clean the room than do the StandardRobots.
    #At lower values of min_coverage, the gap between times is not as large;
    #this is probably also true for less square rooms.