十、兽群、鸟群和交通堵塞

原文:Chapter 10 Herds, Flocks, and Traffic Jams

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

本章的代码位于chap10.ipynb中,它是本书仓库中的 Jupyter 笔记本。使用此代码的更多信息,请参见第?节。

10.1 交通堵塞

是什么导致交通堵塞?在某些情况下,有明显的原因,如事故,车速监视或其他干扰交通的事情。 但其他时候,交通堵塞似乎没有明显的原因。

基于智能体的模型有助于解释自发性交通拥堵。 例如,我根据 Resnick,海龟,白蚁和交通堵塞模型实现了一个简单的高速路模拟。

这是代表“高速路”的类:

  1. class Highway:
  2. def __init__(self, n=10, length=1000, eps=0):
  3. self.length = length
  4. self.eps = eps
  5. # create the drivers
  6. locs = np.linspace(0, length, n, endpoint=False)
  7. self.drivers = [Driver(loc) for loc in locs]
  8. # and link them up
  9. for i in range(n):
  10. j = (i+1) % n
  11. self.drivers[i].next = self.drivers[j]

n是汽车的数量。

length是高速路的长度,默认为 1000(以任意单位)。

eps是我们将添加到系统中的随机噪声。

loc包含驾驶员的位置;最初它们沿着高速公路等距分布。

驾驶员由Driver对象表示。 每个驾驶员都包含前方驾驶员的引用。 高速公路是圆形的,所以最后的驾驶员可以引用第一个。

step方法简单;它只是移动每个驾驶员:

  1. def step(self):
  2. for driver in self.drivers:
  3. self.move(driver)

这里是move方法:

  1. def move(self, driver):
  2. d = self.distance(driver)
  3. # let the driver choose acceleration
  4. acc = driver.choose_acceleration(d)
  5. acc = min(acc, self.max_acc)
  6. acc = max(acc, self.min_acc)
  7. speed = driver.speed + acc
  8. # add random noise to speed
  9. speed *= np.random.uniform(1-self.eps, 1+self.eps)
  10. # keep it nonnegative and under the speed limit
  11. speed = max(speed, 0)
  12. speed = min(speed, self.speed_limit)
  13. # if current speed would collide, stop
  14. if speed > d:
  15. speed = 0
  16. # update speed and loc
  17. driver.speed = speed
  18. driver.loc += speed

d是驾驶员与前方驾驶员之间的距离。 这个距离被传递给choose_acceleration,它规定了驾驶员的行为。 这是司机做出的唯一决定; 其他一切都由模拟的“物理”决定。

  • acc是加速度,它受min_accmax_acc限制。 在我的实现中,汽车可以在max_acc = 1时加速,在min_acc = -10时加速。
  • speed是旧的速度加上请求的加速度,但是我们做了一些调整。 首先,我们向速度添加了随机噪音,因为这个世界并不完美。 eps决定了噪音的幅度,这是适用于速度的百分比; 例如,如果eps为 0.02,则速度乘以 98% 到 102% 之间的随机数。
  • 然后速度限制在 0 到speed_limit之间,在我的实现中为 40,所以汽车不允许后退或加速。
  • 如果请求的速度会引起与下一辆车的碰撞,则速度设置为 0。
  • 最后,我们更新驾驶员的速度和loc属性。

以下是Driver类的定义:

  1. class Driver:
  2. def __init__(self, loc, speed=0):
  3. self.loc = loc
  4. self.speed = speed
  5. def choose_acceleration(self, d):
  6. return 1

locspeed属性是驾驶员的位置和速度。

choose_acceleration的这个实现非常简单:它总是以最大速率加速。

由于汽车起步距离相等,因此我们预计它们都会加速,直到达到限速,或者直到它们的速度超过它们之间的距离。 此时,至少会发生一次“碰撞”,导致一些汽车停下来。

十、兽群、鸟群和交通堵塞 - 图1

图 10.1:三个时间点中,环形公路上的驾驶员的模拟。 点表示驾驶员的位置;十字表示驾驶员必须刹车来避开另一个驾驶员。

图?展示了该过程中的几个步骤,从 30 辆汽车和eps = 0.02开始。 左边是 16 个时间步后的状态,汽车排列成一圈。 由于随机噪音,有些汽车比其他汽车要快,并且间距变得不均匀。

在下一个时间步骤(中),两辆车相撞,用x标记表示。

在下一个时间步骤(右),两辆汽车会与已停车的汽车碰撞,我们可以看到最初形成的交通堵塞。 一旦堵塞形成,它就会持续下去,其它汽车从后面靠近并碰撞,而前面的汽车加速离开。

在某些情况下,堵塞本身会向后传播,如果你观看本章的笔记本中的动画,你可以看到它。

10.2 随机噪声

十、兽群、鸟群和交通堵塞 - 图2

图 10.2:平均速度和汽车数量的函数,带有三个大小的附加随机噪声

随着汽车数量的增加,交通堵塞变得更加严重。 图?显示了汽车能够达到的平均速度,相对于汽车数量的函数。

最上面那行显示eps = 0的结果;也就是说,速度没有随机变化。 如果汽车数量少于 25 辆,则汽车之间的间隔大于 40,这样汽车可以达到并保持 40 的最大速度。超过 25 辆汽车形成交通堵塞,平均速度迅速下降。

这种效果是仿真物理学的直接结果,所以它不应该令人惊讶。 如果道路的长度为 1000,则n个车辆之间的间距为1000 / n。 而且由于汽车的行驶速度不超过前面的空间,所以我们预计,最高平均车速为1000 / n或 40,取最小者。

但这是最好的情况。只有少量的随机性,情况会变得更糟。

图?也显示了eps = 0.001eps = 0.01的结果,其对应于 0.1% 和 1% 的速度误差。

即使有少量噪音,高速路的容量也会从 25 降至 20(“容量”是指可以达到并保持速度限制的最大车辆数量。 如果有 1% 的误差,容量会下降到 10。

作为本章结尾的练习之一,你将有机会设计出更好的驾驶员; 也就是说,你将在choose_acceleration中尝试不同的策略,并查看你是否可以找到可提高平均速度的驾驶行为。

10.3 Boids

1987 年,Craig Reynolds 发表了《兽群,鸟群和鱼群:分布式行为模型》(Flocks, herds and schools: A distributed behavioral model),描述了一个基于智能体的兽群行为模型。 你可以从 http://www.red3d.com/cwr/papers/1987/boids.html 下载他的论文。

这种模型中的智能体被称为“boids”,既是“bird-oid”的缩写,又是“bird”的口音发音(虽然 boids 也用于模拟鱼类和集中的陆生动物)。

每个智能体模拟了三种行为:

避免碰撞:

避开障碍物,包括其他鸟类。

鸟群集中:

移向鸟群的中心。

速度匹配:

将速度(速率和方向)与邻近的鸟类对齐。

Boid 只根据局部信息做出决定;每个 boid 只能看到(或注意)其视野范围内的其他 boid。

在本书的仓库中,你会发现Boids7.py,它包含我的 boids 实现,部分基于《Flake, The Computational Beauty of Nature》(雪花:自然的计算之美)中的描述。

该程序定义了两个类:Boid,实现了 boid 算法,和World,包含Boid列表和吸引Boid的“胡萝卜”列表。

boid 算法使用get_neighbors在视野中查找其他 boid:

  1. def get_neighbors(self, others, radius, angle):
  2. boids = []
  3. for other in others:
  4. if other is self:
  5. continue
  6. offset = other.pos - self.pos
  7. # if not in range, skip it
  8. if offset.mag > radius:
  9. continue
  10. # if not within viewing angle, skip it
  11. if self.vel.diff_angle(offset) > angle:
  12. continue
  13. # otherwise add it to the list
  14. boids.append(other)
  15. return boids

get_neighbors使用向量减法来计算从selfother的向量。 这个向量的们是到另一个 boid 的距离。 diff_angle计算self的速度(也是视线)与另一个 boid 之间的角度。

center寻找视野中 boid 的质心,并返回一个指向它的向量:

  1. def center(self, others):
  2. close = self.get_neighbors(others, r_center, a_center)
  3. t = [other.pos for other in close]
  4. if t:
  5. center = sum(t)/len(t)
  6. toward = vector(center - self.pos)
  7. return limit_vector(toward)
  8. else:
  9. return null_vector

同样,avoid寻找范围内任何障碍物的质心,并返回一个指向它的向量,copy将返回当前朝向和邻居的平均朝向之间的差,love计算出胡萝卜的朝向。

set_goal计算这些目标的加权总和并设定总体目标:

  1. def set_goal(self, boids, carrot):
  2. self.goal = (w_avoid * self.avoid(boids, carrot) +
  3. w_center * self.center(boids) +
  4. w_copy * self.copy(boids) +
  5. w_love * self.love(carrot))

最后move更新 boid 的速度,位置和姿势。

  1. def move(self, mu=0.1):
  2. self.vel = (1-mu) * self.vel + mu * self.goal
  3. self.vel.mag = 1
  4. self.pos += dt * self.vel
  5. self.axis = b_length * self.vel.norm()

新速度是旧速度和目标的加权和。 参数mu决定鸟类能够多快地改变速度和方向。 时间步长dt决定了 boids 移动的距离。

许多参数影响鸟群行为,包括每个行为的范围,角度和权重以及可操作性mu

这些参数决定了 boids 形成和维持鸟群的能力,以及鸟群中运动和组织的模式。 对于某些设置,boids 类似于一群鸟;其他设置类似于鱼群或一片飞虫。

10.4 涌现和自由意志

作为一个整体,许多复杂的系统具有它们的组件不具有的属性:

  • 细胞自动机规则 30 是确定性的,控制其演化的规则是完全已知的。 尽管如此,它会生成一个序列,统计上与随机无法区分。
  • 谢林模型中的智能体不是种族主义者,但他们互动的结果就好像他们是。
  • 糖域中的智能体形成对角移动的波浪,尽管智能体不能。
  • 即使汽车正在向前行驶,交通堵塞会向后移动。
  • 兽群和鸟群的行为来自其成员之间的局部互动。

这些例子提出了一个途径,用于解决几个古老而富有挑战性的问题,包括意识和自由意志的问题。

自由意志是做出选择的能力,但是如果我们的身体和大脑受到确定性物理规律的支配,我们的选择就会是确定的。 自由意志的争论无数;我只会提到两个:

  • 威廉·詹姆斯(William James)提出了一个两阶段模型,其中可能的行为由随机过程产生,然后由确定性过程选择。 在这种情况下,我们的行为基本上是不可预测的,因为生成它们的过程包含随机元素。
  • 大卫休谟(David Hume)认为,我们对于做出选择的感知是一种幻觉;在这种情况下,我们的行为是确定性的,因为产生它们的系统是确定性的。

这些论点以相反的方式调解冲突,但他们同意冲突是存在的:如果这些部分是确定性的,那么系统就不会有自由意志。

本书中的复杂系统提出了另一种选择,在选择和决策层面的自由意志,相当于神经元层面的(或更低层次)的决定论。 就像汽车向前行驶时,交通堵塞后退的方式一样,即使神经元没有,人也可以有自由意志。

10.5 练习

练习 1

在交通堵塞的模拟中,定义一个类,BetterDriver,它继承Driver并覆盖choose_acceleration。 查看你是否可以定义一个驾驶规则,比Driver中的基本实现更好的。 你可能会尝试到达更高的平均速度,或者更少的碰撞。

练习 2

注意:为了做这个练习,你必须安装 VPython,一个用于 3D 显示和动画的库。 如果你使用 Anaconda(我在第?节中推荐过),你可以执行:

  1. conda install -c vpython vpython

然后运行本书仓库中的Boids7.py。 阅读代码来查看,程序开始时定义的参数如何控制 boid 的行为。 试验不同的参数。 如果通过将权重设置为 0 来“关闭”其中一种行为,会发生什么?

为了生成更多类似鸟类的行为,Flake 建议增加第四种行为来保持清晰的视线;换句话说,如果在正前方有另一只鸟,那么它就应该从侧面移开。 你认为这个规则对鸟群的行为有什么影响? 实现它来看看。

练习 3

http://en.wikipedia.org/wiki/Free_will 上深入了解自由意志。 自由意志与决定论相容的观点被称为相容论。 相容论最大的挑战之一是“结果论证”(consequence argument)。 什么是结果论证? 根据你在本书中读到的内容,你对结果论证有什么样的反应?