MIT 6.0002 PS3: Robot Simulation

请注意，本文编写于 1565 天前，最后修改于 1059 天前，其中某些信息可能已经过时。

最近更新：2020-11-03

本文是我对 MIT 6.0002 课程（Introduction to Computational Thinking and Data Science）配套作业 Problem Set 3 的解答。

完整代码：https://github.com/Jed-Z/mit-6.0001-and-6.0002/tree/master/6.0002/6.0002_PS3

问题描述

详细的要求见原题，从 MIT OCW 下载原题：Problem Set 3: Robot Simulation (ZIP) (This ZIP file contains: 1 .pdf file, 4 .pyc files, and 4 .py files)

准备工作

本次作业需要在 Python 3.5 环境下完成（经测试，不能用目前最新的 3.7），我使用 conda 创建了一个新的虚拟环境，并且在此环境下编写代码和测试。创建好环境后，并安装好所需要的包（Matplotlib 等）后，激活该环境。本文档中的所有代码均在该环境下编写和测试。

conda create -n Python3.5 python=3.5 matplotlib
conda activate Python3.5

本文地址：https://www.jeddd.com/article/mit-6-0002-ps3.html

Problem 1: Implementing the RectangularRoom and Robot classes

RectangularRoom

RectangularRoom是一个抽象类，其中有些方法不做实现，而是留给它的子类去实现。RectangularRoom中要表示一个房间的长（width）和宽（height），还要保存房间内的每块瓷砖上的灰尘量。每块瓷砖用其横坐标和纵坐标组成的元组(m, n)表示，因此考虑用键为元组的字典来保存每一块瓷砖。构造函数如下：

def __init__(self, width, height, dirt_amount):
    self.width = int(width)
    self.height = int(height)
    self.tiles = {}  # 键：坐标元组；值：瓷砖上的灰尘量
    for i in range(self.width):
        for j in range(self.height):
            self.tiles[i, j] = dirt_amount

clean_tile_at_position方法对一块瓷砖进行清理。其参数pos是一个 Position 类型的对象，其中保存着浮点型的坐标，必须用math.floor()将其向下取整为整数才能表示房间中的瓷砖。另外，要注意一块瓷砖上的灰尘量是一个非负数，因此清理后灰尘量必须大于等于 0。

def clean_tile_at_position(self, pos, capacity):
    m = math.floor(pos.get_x())  # 瓷砖的横坐标（整数）
    n = math.floor(pos.get_y())  # 瓷砖的纵坐标（整数）
    self.tiles[m, n] -= capacity
    if self.tiles[m, n] < 0:
        self.tiles[m, n] = 0

is_tile_cleaned方法用于检查一块瓷砖是否是干净的，即瓷砖上的灰尘量是否为 0，这个方法的参数是整数 m 和 n，可以直接用于表示瓷砖的坐标。

def is_tile_cleaned(self, m, n):
    return self.tiles[m, n] == 0

get_num_cleaned_tiles方法用于统计房间中干净瓷砖的数量。通过self.tiles的values()方法可以获得字典的值，它们代表每块瓷砖上的灰尘量，然后再使用列表的count()方法统计其中值为 0 的个数即可。

def get_num_cleaned_tiles(self):
    return list(self.tiles.values()).count(0)

is_position_in_room方法用于检查一个给定的 Position 对象表示的位置是否在房间中。特别注意，房间的范围应该是一个半开半闭区间——坐标值可以恰好为 0，但不能恰好为房间的长度或宽度。也就是只有满足 $0\le x< width$、$0\le y< height$ 的坐标才是房间内的坐标。

def is_position_in_room(self, pos):
    # 注意这里是严格不等号
    return pos.get_x() >= 0 and pos.get_y() >= 0 and \
           pos.get_x() < self.width and pos.get_y() < self.height

get_dirt_amount方法直接返回给定整数坐标上的灰尘量即可。

def get_dirt_amount(self, m, n):
    return self.tiles[m, n]

此时，RectangularRoom类中剩下三个方法尚未实现，它们是抽象方法，留给子类实现。在基类的这些方法中，只有一句raise NotImplementedError。

Robot

Robot也是一个抽象类。一个机器人对象内要保存该机器人的当前位置、朝向和清理能力。初始时，随机生成一个房间内的位置，也随机生成一个方向作为机器人的初始朝向。random.uniform(0, 360)用于生成 $[0, 360]$ 内的随机浮点数，模 360 后范围变为 $[0, 360)$。构造函数如下：

def __init__(self, room, speed, capacity):
    self.room = room
    self.speed = speed
    self.capacity = capacity
    self.position = self.room.get_random_position()  # 随机起始位置
    self.direction = random.uniform(0, 360) % 360    # 随机起始方向

get_robot_position、get_robot_direction、set_robot_position、set_robot_direction是普通的 getter 和 setter，各使用一条语句实现即可。稍稍需要注意的是set_robot_direction中为direction参数对 360 取了模，这样可以把方向限制在 $[0, 360)$ 中，无论参数本身是否在此区间内。

Problem 2: Implementing EmptyRoom and FurnishedRoom

EmptyRoom

EmptyRoom是RectangularRoom的子类，它实现了在父类中尚未实现的三个方法。

get_num_tiles方法返回房间中的瓷砖数量，在空房间中，瓷砖数量就是self.tiles的元素数量。

def get_num_tiles(self):
    return len(self.tiles)

is_position_valid方法判断给定 Position 对象是否是“有效的”，在空房间中，有效的位置等价于在房间内的位置，因此可以调用已经在父类中实现好的is_position_in_room方法。

def is_position_valid(self, pos):
    return self.is_position_in_room(pos)

get_random_position方法返回一个房间内的随机位置，使用random.uniform即可。

def get_random_position(self):
    return Position(random.uniform(0, self.width), random.uniform(0, self.height))

FurnishedRoom

FurnishedRoom也是RectangularRoom的子类。在有家具的房间中，有些瓷砖上可能被家具占用，这些位置被认为是“无效的”，即机器人不能停留在这些位置上。在FurnishedRoom中，被家具占用的瓷砖的位置元组被保存在一个列表self.furniture_tiles中（详见构造函数）。

is_tile_furnished方法用于判断给定坐标是否被家具占用：

def is_tile_furnished(self, m, n):
    return (m, n) in self.furniture_tiles

is_position_furnished方法用于判定给定 Position 对象是否被家具占用。用math.floor将坐标转换为瓷砖的坐标，然后调用is_tile_furnished方法：

def is_position_furnished(self, pos):
    m = math.floor(pos.get_x())
    n = math.floor(pos.get_y())
    return self.is_tile_furnished(m, n)

is_position_valid方法判断给定 Position 对象是否是“有效的”。与空房间的同名方法不同，有家具的房间中，那些被家具占用的瓷砖位置被认为是无效的。

def is_position_valid(self, pos):
    return self.is_position_in_room(pos) and not self.is_position_furnished(pos)

get_num_tiles方法返回可以到达的瓷砖数量。可以到达的瓷砖数量等于整个房间中的瓷砖数量减去被家具占用的瓷砖数量。

def get_num_tiles(self):
    return len(self.tiles) - len(self.furniture_tiles)

get_random_position方法返回一个随机的有效位置。由于使用random.uniform产生的位置可能被家具占用而无效，因此需要用一个 while 循环来产生随机位置，直到位置有效：

def get_random_position(self):
    while True:
        pos = Position(random.uniform(0, self.width), random.uniform(0, self.height))
        if self.is_position_valid(pos):
            return pos

Problem 3: StandardRobot and Simulating a Timestep

StandardRobot

StandardRobot是Robot的子类，实现了update_position_and_clean方法，通过字面意思就能知道该方法的功能。题目中（题目 PDF 的第 7 页）已经清晰地描述了标准机器人的移动策略，只需将其用 Python 语法编写出来即可。注意，在 Problem 1 和 2 中我们已经实现了许多方法，别忘了使用它们。

def update_position_and_clean(self):
    new_pos = self.position.get_new_position(self.direction, self.speed)
    if self.room.is_position_valid(new_pos):
        self.set_robot_position(new_pos)
        self.room.clean_tile_at_position(new_pos, self.capacity)
    else:
        self.set_robot_direction(random.uniform(0, 360))

题目中已经告诉我们了，不需要考虑机器人的路径穿过家具的情况，只需要保证移动后所在的瓷砖不被家具占用即可，这大大简化了该函数。

测试 StandardRobot

测试标准机器人在空房间的移动行为：

test_robot_movement(StandardRobot, EmptyRoom)

开始与结束的截图：

关闭窗口后，终端没有报错，程序正常结束。

接下来，测试标准机器人在有家具的房间的移动行为：

test_robot_movement(StandardRobot, FurnishedRoom)

开始与结束的截图：

关闭窗口后，终端没有报错，程序正常结束。

测试完毕后，将上面两条测试语句注释掉，避免影响后续内容。

# Uncomment this line to see your implementation of StandardRobot in action!
# test_robot_movement(StandardRobot, EmptyRoom)
# test_robot_movement(StandardRobot, FurnishedRoom)

本文地址：https://www.jeddd.com/article/mit-6-0002-ps3.html

Problem 4: Implementing FaultyRobot

FaultyRobot

FaultyRobot也是Robot的子类，它是“有缺陷的机器人”，有着与标准机器人不同的移动策略，这种机器人有一定概率会不清理瓷砖而直接转向。有缺陷的机器人的清理策略为，每个单位时间首先依概率判断本次是否出错，如果出错，那么直接随机转向；如果不出错，那么就像标准机器人一样，向前移动到下一个有效位置并清理下一个位置，如果下一个位置无效，那么随机转向。

def update_position_and_clean(self):
    new_pos = self.position.get_new_position(self.direction, self.speed)
    if not self.gets_faulty() and self.room.is_position_valid(new_pos):
        self.set_robot_position(new_pos)
        self.room.clean_tile_at_position(new_pos, self.capacity)
    else:
        self.set_robot_direction(random.uniform(0, 360))

测试 FaultyRobot

仅测试有缺陷的机器人在空房间中的行为：

test_robot_movement(FaultyRobot, EmptyRoom)

开始与结束的截图：

观察机器人的运动动画，发现有些时候，机器人仅仅在一块瓷砖上转向，既不移动也不清理，这就是gets_faulty判断为“出错”的情况发生了。

关闭窗口后，终端没有报错，程序正常结束。测试完毕后，将测试语句注释掉，避免影响后续内容。

Problem 5: Creating the Simulator

本题完成一个多个机器人清理房间的模拟器，每次模拟用一个或多个机器人对同一个房间进行清理，并计算清理房间指定比例所需要的时间。由于机器人的移动策略中有一些随机的行为，因此对于每次模拟，都要进行多次试验以消除偶然性。首先，编写进行一次试验的代码，我将其写入一个单独的函数run_one_trial（这个函数原题中没有），该函数接收房间参数、机器人的列表和要求清理的比例，返回需要的单位时间数：

def run_one_trial(room, robots, min_coverage):
    steps = 0
    while room.get_num_cleaned_tiles() / room.get_num_tiles() < min_coverage:
        for robot in robots:
            robot.update_position_and_clean()
        steps += 1
    return steps

run_simulation函数负责构造房间、机器人的列表，然后在 for 循环中调用run_one_trial函数。它记录每次试验的时间，然后返回其平均值：

def run_simulation(num_robots, speed, capacity, width, height, dirt_amount, min_coverage, num_trials,
                  robot_type):
    sim_steps = []  # 保存每次模拟的时间片数

    for i in range(num_trials):
        room = EmptyRoom(width, height, dirt_amount)
        robots = []
        for j in range(num_robots):
            robots.append(robot_type(room, speed, capacity))
        sim_steps.append(run_one_trial(room, robots, min_coverage))
    return sum(sim_steps) / num_trials

使用以下语句进行测试：

print ('avg time steps: ' + str(run_simulation(1, 1.0, 1, 5, 5, 3, 1.0, 50, StandardRobot)))
print ('avg time steps: ' + str(run_simulation(1, 1.0, 1, 10, 10, 3, 0.8, 50, StandardRobot)))
print ('avg time steps: ' + str(run_simulation(1, 1.0, 1, 10, 10, 3, 0.9, 50, StandardRobot)))
print ('avg time steps: ' + str(run_simulation(1, 1.0, 1, 20, 20, 3, 0.5, 50, StandardRobot)))
print ('avg time steps: ' + str(run_simulation(3, 1.0, 1, 20, 20, 3, 0.5, 50, StandardRobot)))

结果如下，注意每次运行的结果可能不相同，但相差不会太大：

avg time steps: 311.62
avg time steps: 566.4
avg time steps: 710.4
avg time steps: 1258.22
avg time steps: 415.7

测试完毕后，将测试语句注释掉，避免影响后续内容。

测试

使用ps3_tests_f16.py对整个ps3.py进行测试，全部通过：

test_clean_tile_at_position_PosToPos (__main__.ps3_P1A)
Test if clean_tile_at_position removes all dirt ... ok
test_clean_tile_at_position_PosToZero (__main__.ps3_P1A)
Test if clean_tile_at_position removes all dirt ... ok
test_clean_tile_at_position_ZeroToZero (__main__.ps3_P1A)
Test if clean_tile_at_position removes all dirt ... ok
test_get_num_cleaned_tiles_FullIn1 (__main__.ps3_P1A)
Test get_num_cleaned_tiles for cleaning subset of room completely with 1 call ... ok
test_get_num_cleaned_tiles_FullIn2 (__main__.ps3_P1A)
Test get_num_cleaned_tiles for cleaning subset of room in two calls ... ok
test_get_num_cleaned_tiles_OverClean (__main__.ps3_P1A)
Test cleaning already clean tiles does not increment counter ... ok
test_get_num_cleaned_tiles_Partial (__main__.ps3_P1A)
Test get_num_cleaned_tiles for cleaning subset of room incompletely ... ok
test_is_position_in_room (__main__.ps3_P1A)
Test is_position_in_room ... ok
test_is_tile_cleaned_clean (__main__.ps3_P1A)
Test is_tile_cleaned ... ok
test_is_tile_cleaned_dirty (__main__.ps3_P1A)
Test is_tile_cleaned ... ok
test_room_dirt_clean (__main__.ps3_P1A) ... ok
test_room_dirt_dirty (__main__.ps3_P1A) ... ok
test_unimplemented_methods (__main__.ps3_P1A)
Test if student implemented methods in RectangularRoom abstract class that should not be implemented ... ok
test_getset_robot_direction (__main__.ps3_P1B)
Test get_robot_direction and set_robot_direction ... ok
test_unimplemented_methods (__main__.ps3_P1B)
Test if student implemented methods in Robot abstract class that should not be implemented ... ok
test_get_num_tiles (__main__.ps3_P2_ER)
test get_num_tiles method ... ok
test_get_random_position (__main__.ps3_P2_ER)
Test get_random_position ... ok
test_is_position_valid (__main__.ps3_P2_ER)
Test is_position_valid ... ok
test_get_num_tiles (__main__.ps3_P2_FR)
test get_num_tiles method ... ok
test_get_random_position (__main__.ps3_P2_FR)
Test get_random_position for FurnishedRoom ... ok
test_is_position_furnished (__main__.ps3_P2_FR)
test_is_position_furnished ... ok
test_is_position_valid (__main__.ps3_P2_FR)
Test is_position_valid ... ok
test_is_tile_furnished (__main__.ps3_P2_FR)
test is_tile_furnished ... ok
testRobot (__main__.ps3_P3)
Test StandardRobot ... ok
testSimulation1 (__main__.ps3_P5_Faulty)
Test cleaning 100% of a 5x5 room with FaultyRobot ... ok
testSimulation2 (__main__.ps3_P5_Faulty)
Test cleaning 75% of a 10x10 room with FaultyRobot ... ok
testSimulation3 (__main__.ps3_P5_Faulty)
Test cleaning 90% of a 10x10 room with FaultyRobot ... ok
testSimulation4 (__main__.ps3_P5_Faulty)
Test cleaning 100% of a 5x5 room with FaultyRobot ... oktestSimulation5 (__main__.ps3_P5_Faulty)
Test cleaning 75% of a 10x10 room with FaultyRobot ... ok
testSimulation6 (__main__.ps3_P5_Faulty)Test cleaning 90% of a 10x10 room with FaultyRobot ... ok

----------------------------------------------------------------------
Ran 43 tests in 5.980s

OK

本文地址：https://www.jeddd.com/article/mit-6-0002-ps3.html

Problem 6: Running the Simulator

Question 1

问：How does the performance of the two robot types compare when cleaning 80% of a 20x20 room?

答：无论是StandardRobot还是FaultyRobot，完成相同的清理任务所需要的时间都随着机器人数量的增加而减少。同样是清理一个 20×20 房间的 80%，在机器人数量相同的情况下，StandardRobot完成任务需要的时间略少于FaultyRobot，且二者之差随着机器人数量的增加而缩小。

Question 2

问：How does the performance of the two robot types compare when two of each robot cleans 80% of rooms with dimensions 10x30, 20x15, 25x12, and 50x6?

答：在房间面积相同但形状不同时，完成清理所需要的时间与房间形状的长宽比（width / height）有关，根据图像Figure 2可以看出，对于一个面积为300的房间，清理完它的80%所需要的的时间在形状为 20×15（比例为 1.33）时最少，当长宽比增大或减小时，清理时间都会增加。无论房间形状如何，StandardRobot完成任务的时间都要小于FaultyRobot。

Optional: Visualizing Robot Simulation

可以用ps3_visualize模块来可视化机器人清理房间的过程，只需对run_one_trial添加三行代码即可。在run_one_trial起始处，初始化可视化对象，参数的意义见原题目 PDF 文件；在每次对机器人执行了update_position_and_clean后，调用anim.update(room, robots)以更新动画；最后，使用anim.done()来结束动画。修改后的函数如下：

def run_one_trial(room, robots, min_coverage):
    anim = ps3_visualize.RobotVisualization(len(robots), room.width, room.height, False, 0.02)  # 0.02秒更新一次
    steps = 0
    while room.get_num_cleaned_tiles() / room.get_num_tiles() < min_coverage:
        for robot in robots:
            robot.update_position_and_clean()
            anim.update(room, robots)
        steps += 1
    anim.done()
    return steps

运行含有三个机器人的测试观察效果。

print ('avg time steps: ' + str(run_simulation(3, 1.0, 1, 20, 20, 3, 0.5, 50, StandardRobot)))

在运行刚开始时和模拟结束时（清理完 50%）的截图：

更换参数，进行更多模拟，截图这里已略去。完成后，注释掉测试代码，也注释掉run_one_trial中显示动画的代码。

总结

抽象类。本题中再次用到了抽象类的设计方法。在各个面向对象编程语言中都有抽象类的概念，Python 也不例外。抽象类有一个显著的特点，就是它不能被直接实例化，也就是不能用于创建对象，这是因为抽象类中有部分方法没有实现，仅仅提供了一个接口，称作“抽象方法”。在本题中，抽象方法的函数体内只有一句raise NotImplementedError。如果不小心实例化了抽象类且调用了其中的抽象方法，那么将会引发异常，从而让程序员发现错误。这些抽象方法将会由抽象类的子类进行具体实现。
当类变得复杂怎么办。本题中出现了很多类，其中有较多继承关系，每个类中又有许多成员变量方法。最重要的是，这些类并不是由我们自己设计的，而是别人写好框架让我们去实现的，这对编程造成了一定困难。因此，有必要使用图表的方式列出有哪些类，一些类之间的继承关系；还有必要将每个类中的方法及其签名（函数名、接受的参数和类型、返回值等）列成表格，并注明哪些方法是父类（如果有）实现的，哪些是子类单独实现的。只有搞清楚逻辑才能高效率地编程。
Python 中取整的各种方法。常见的取整方法有int()、math.floor()和math.round()。int()直接截断小数部分，math.floor()是向下取整，这二者对于负数的取整行为是不同的——例如int(-3.5) == -3，而math.floor(-3.5) == -4。此外，math.round()是四舍五入，math.ceil()是向上取整。
# -*- coding: utf-8 -*-的作用。注意到ps3.py文件的首行有这样的信息，这是因为 Python 中默认的编码格式是 ASCII，在文件开头加上这句话后可以使用 UTF-8 的编码格式。这句话也可以写作#coding=utf-8。
元组省略括号。适当的时候，可以不写元组的小括号，一定程度上提高代码可读性。但是注意，在传递函数参数的时候有时可能不能省略括号，否则本来作为整体的一个元组参数可能会被解释成多个不同的参数，而导致与函数签名不匹配的问题。

本文地址：https://www.jeddd.com/article/mit-6-0002-ps3.html

MIT 6.0002 PS3: Robot Simulation

问题描述

准备工作

Problem 1: Implementing the RectangularRoom and Robot classes

RectangularRoom

Robot

Problem 2: Implementing EmptyRoom and FurnishedRoom

EmptyRoom

FurnishedRoom

Problem 3: StandardRobot and Simulating a Timestep

StandardRobot

测试 StandardRobot

Problem 4: Implementing FaultyRobot

FaultyRobot

测试 FaultyRobot

Problem 5: Creating the Simulator

测试

Problem 6: Running the Simulator

Question 1

Question 2

Optional: Visualizing Robot Simulation

总结

【Python】用邻近点梯度法、交替方向乘子法、次梯度法求解 LASSO 回归模型

【Python】手写随机梯度法求解 MNIST 上的多项逻辑回归问题

此处评论已关闭