聚热点 juredian

无需预测也能解决问题,自组织算法的魔法你了解吗?

在自组织群体中,个体是愚蠢的,群体则完全不同,其相对于个体实现了智慧上的飞跃。具体的例子有很多,包括鱼群、鸟群、蚁群,甚至菌群。

前一阵子曾经时兴将一种原生生物作为宠物,现在上网购网站还能搜得到。这种生物有着神奇的群体智慧,甚至被人们用来设计交通网络。

日本科学家做过一个实验,他们将黏菌放在东京地铁路线图上,并将燕麦粒分布在地铁站的位置。数小时后,黏菌开始扩散开来寻找食物,刚开始路线是随机的。但随后黏菌的分布逐渐形成了最优化的路线,并且这些路线和东京的真实地铁路线图非常接近。

在后来的多次实验中,科学家发现每次形成的路线图都不一样,有时候甚至会优于真实的路线图。

现有的AI应用一般通过预测实现功能,也就是说,它们将某个变量作为直接的目标,并在训练中调整自己的参数,以拟合目标。

而在自组织群体中,通常不会存在一个具体的群体目标,每个个体都为了实现各自的目标而行动,最终却会在整体上涌现出惊人的秩序。这一现象在AI中也对应着相应的研究领域,即群体智能。从社会学的角度上看,人类也拥有群体智能。

群体智能(Swarm Intelligence),是指在某群体中,存在众多无智能的个体,它们通过相互之间的简单合作表现出智能行为。它由Gerardo Beni和Jing Wang于1989年在细胞机器人系统的背景下引入,相关算法有蚁群优化、粒子群优化、进化算法等。

该领域已经有了很多相关研究,比如群体机器人就是让许多简单的物理机器人进行沟通、导航和协作,美国宇航局在研究使用群体技术进行行星测绘,M. Anthony Lewis和George A. Bekey1992年撰写的论文讨论了使用群体智能来控制体内纳米机器人以杀死癌症肿瘤的可能性。

针对交通系统的相关应用,比如外卖派单,目前的落地AI算法也是预测型的。这样的系统需要收集大量的数据,进行全局规划,其中涉及的变量不计其数,包括订单信息、天气状况、交通路况、商家出餐速度等等。目前用于优化交通的城市大脑系统,走的也是预测路线。但这真的是唯一的解决方案吗?

来自墨西哥国立自治大学的Carlos Gershenson是一名已研究城市交通问题二十年的计算机科学家。针对墨西哥城的交通拥挤难题,他发现,应用复杂性研究和自组织原理,让交通系统“适应”而非“预测”潜在的交通问题,能够有效提高城市交通的流动性,解决交通阻塞、减少通勤时间。

Gershenson使用了适应性的(而非预测性的)计算机模拟,将自组织作为提高城市流动性的工具。在他的方案中,只需清楚地说明人们在上车之前应该待在哪些地方,以空出位置让车上的乘客下车 ,就消除了过程中的几乎所有冲突和麻烦,并将上车时间减少了25%。

麻省理工学院物理学教授Yaneer Bar-Yam对此大加称赞:“Carlos的工作大大提高了我们对自组织交通流的理解水平,及其对现实世界的控制和优化的影响。”

新英格兰复杂系统研究所所长在2007年至2008年期间与Gershenson合作了博士后研究,他补充说,Gershenson“已经重新构造了问题,这是他的研究中最重要的影响。”

1 研究背景

Gershenson对城市交通的研究兴趣始于大学本科。当时,他沉迷于研究高速公路的交通问题,为此还编写了有/无交通信号灯与无人驾驶汽车的模拟程序。运用他所编写的程序,他可以预测汽车何时会穿越十字路口。在Gershenson的模拟计算中,掌握了汽车穿越十字路口的时间后,即使汽车永不停车,只需要降低速度,也可以防止它们撞车。

在博士论文研究上,Gershenson第一次尝试了自组织系统的应用。他模拟鸟群的自组织例子,尝试让成排的汽车像鸟一样聚集。除了“自私”策略外,他还在模拟中实现了不同的控制策略,让多辆汽车与邻车以相同的速度前进。

椋鸟群

椋鸟群的飞行及驻留轨迹

那次模拟实验最终以失败告终:因为有些汽车会加速,随后又突然减速,造成许多麻烦的震动。但正是在这次失败的模拟中,Gershenson发现了“自私”的作用:每辆车都想要以尽可能快的速度前行。这也更符合现实的车辆行驶情况。

Gershenson的第一位博士生Luis Enrique Cortés Berrueco对“自私”进行了深入的研究。Luis使用博弈论和交通模拟,来研究自私与合作司机之间的关系。

研究证明,如果道路上的车辆密度较低,那么自私的司机将带来更高效的交通,因为司机只考虑通行效率。但这也会更危险。如果车辆密度中等,那么当一个司机减缓了另一个司机的速度时,后面所有司机也会减速,这样会降低通行的效率。如果车辆密度太高,司机的“自私”就无法发挥作用了,因为他们无法改变车道。

Gershenson认为,要解决复杂的问题,科学家需要放弃传统方法,并找到新颖的方法来研究不断变化的挑战。“科学和工程学总是假设世界是可预测的,只需要找到适当的自然法则就可以预见未来。但是对复杂系统的研究表明,这种假设是错误的。”

2 城市交通的复杂性

墨西哥城的居住人口接近2200万,汽车超过600万辆,每天上班花费两小时是许多人生活习惯的一部分。也许是因为交通时间拖延已成为大家日常生活的一部分,所以在墨西哥城,上课或开会迟到10至15分钟被认为是“司空见惯”的事情,不会受到责备。

我们可以轻松地对单个车辆的轨迹建模,因为它具有均匀的运动和加速度,只需要用到高中的基础数学。但在现实世界中,我们无法预测汽车将在两分钟前到达哪里,因为车辆的精确位置不仅取决于其自身的行驶速度,还取决于交通中所有其他车辆和行人的行为。

如果其他车辆的行驶速度变慢或变快,则根据每个人是否危险驾驶,将有更多或更少的空间,这其中存在很强的相互依赖性。我们也无法预测汽车在两分钟后到达的位置,因为这取决于前方的汽车是否及时对交通信号灯做出反应,它们是否分散了注意力,是否有公交车,是否在不应该停靠的地方停车等等。

复杂性是由相互作用决定的,在城市交通中,相互作用非常重要。而且,我们还要考虑驾驶员是否有分心、疲劳驾驶等人为因素。

如果想简单地解决交通问题,比如增加交通车道,而不考虑交互作用,那么所取得的效果将不能满足实际的交通需求。技术史学家Lewis Mumford曾提出,在城市交通领域,“增加高速公路车道以应对交通拥堵,就像放松腰带来治疗肥胖症一样。”

在接受Quanta Megazine的采访中,Gershenson提到,他之所以选择在墨西哥城进行模拟、深入研究,原因主要有以下三点:

1)Gershenson与团队住在墨西哥城,更容易开展研究。

2)根据不同的索引,墨西哥城的交通流动性是世界上最差的。

3)团队与当地政府有密切来往,有利于推进当地政府部门对交通改善与提升给出建议。(Gershenson提到,他在布鲁塞尔读博士时,想要跟当地的交通部门联系,基于交通研究提出自己的建议,但没有得到一个满意的结果。)

3 “适应”比“预测”效果更佳

在这个项目中,Gershenson使用了墨西哥城的交通灯来提高通勤速度、减少汽车排放量。

一般来说,为了提高交通效率,交通灯系统的设置是提前定时的,但每一次停在红绿灯前等候通过的车辆数目都是不一样的。假设说,我们经过调查,将通勤假设为平均每分钟有大约13辆汽车要通过,但在很多时候,每分钟可能有20辆汽车,或者0辆、6辆。

如何协调好所有提前规划好的交通灯来使汽车快速移动是一个问题。要协调的十字路口越多,对计算能力的的要求就越高,而且随着车辆数目的增减,情况也会有所变化。所以我们不可能对交通进行预测。

但即使如此,我们依然想要优化车流量与交通情况。由于优化对计算的需求较大,所以Gershenson提议使用适应(adaptation)的方法。

自组织交通灯(self-organizing traffic lights)自带传感器,可以灵活根据四面八方即将通过的车辆数量来调整红绿灯的时长。这时候,交通灯并不是在“预测”,而是在不断“适应”变化万千的车流量。但如果交通灯可以这么灵活地适应通行需求,可能也不是一件好事,因为这样的话,开车的人就没有停车“偷懒”的时间了。驾驶员只需要停下来等其他车辆通过。

之前汽车的通行是遵从交通灯的命令,现在有了传感器之后,汽车也可以给交通灯“下命令”了。因此,随着自组织交通灯的出现,“汽车列队”(platoon)也逐渐形成,因为一次协调10排“10辆汽车列队”、每个汽车列队有规定的行走轨迹,会比一次协调100辆汽车的难度更低、效率也更高。

图源:Quanta Magazine by Meghan Dhaliwal

随之出现的还有一波波的“绿色车流”:即汽车列队可以畅行多个十字路口,无需停留。你不用把“这个"绿色车流’在某个速度时会慢下来”编进系统,就能实现理想的效果。“绿色车流”是在交通过程中自发形成的。之所以说“自组织”,是因为不同十字路口的交通灯之间并没有进行直接交流。

自组织交通灯与传统的“控制系统”不同,因为后者的核心是:控制事情在何时何地准时发生。在自组织交通灯中,你不需要将解决方案告诉系统,但你会设计一些交互,让系统“自行”不断地寻找令人满意的解决方法。这是最理想的,因为我们无法预测具体的问题。

如果你希望模型做出预测,那么开发一个高度复杂性的系统非常困难,需要包括很多细节。假设我们要对墨西哥城的交通进行建模。那么,我们需要知道在一天中的每个时段有多少辆汽车沿着某个轨迹行驶,以及它们的平均加速度是多少,是否在下雨等等。许多因素都会影响交通流量,因此你需要添加尽可能多的细节。

但如果你只是希望将模型用于理解系统而不是对其进行预测,那么在很多情况下,非常抽象的模拟可能会有用。

Gershenson尝试的模拟从复杂转向简单、抽象,比如车辆具有无限的加速度,并且车辆之间的空间中存在对称性,但这在现实中是不存在的。但通过这类模拟,Gershenson发现,城市交通中存在六到十个相变:你可以看到随着车辆密度的增加,速度或流量如何急剧变化。

4 通勤时间减少25%

在模拟的过程中,Gershenson发现自组织交通灯能将通行时间缩短25%,且由于车辆在红灯前停留的时间减短,排放的废汽也减少了。这个方案为墨西哥城这样的大城市减少的汽车排放物数目,估计是:将汽车换成大约10条巴士线,但排放的废汽只是一条巴士线所排放的量。

当然,抽象的模拟也是模拟。Gershenson表示,其实他们也不能百分百确定模拟的作用,因为还涉及到墨西哥城复杂的公共交通状况、驾驶员的驾驶行为等等。交通效率也可能降低,因为当车辆通行较好时,可能会使得越来越多人想要开车。如果街上的车辆变多,那么自组织交通灯所减少的废汽可能并不足以抵消新增汽车所排放的废气量。

Gershenson认为,自组织系统将研究重点从“预测”转向“适应”,可以帮助我们掌握完全不一样的方法论。目前,他们已经在多个公共交通系统(包括火车、地铁、公交等)进行“自组织”的模拟,发现:比起主要功能为预测的控制系统,自组织系统的效率明显更高。

比方说,在地铁系统内,每次地铁到站时,在站台上等候上车的乘客数量都是不一样的。这时候,如果按传统方法来操作,那么乘客必须在该站等候一段固定的时间。而且,如果排队的乘客比较多,地铁不会停留久一点、让更多乘客能够上车;如果排队的乘客比较少,地铁也不会停留短一点、减少不必要的等候时间。如果地铁能够轻松自如地应对这些情况,那么地铁的运作效率肯定会大大提高。

谈到将自组织系统应用在墨西哥城的地铁系统时,Gershenson谈到,他们并不指望乘客会乖乖排队、有序上车。他们唯一指望的是:等候上车的乘客会留出一点空隙让准备下车的乘客能够顺利下车。他们发现,即使乘客胡乱一通地挤地铁,自组织系统也能帮助提高地铁的通行效率。

起初,他们对这项研究结果也有些意外。直到研究全过程结束后,他们才想明白原因:

之前,挤地铁的“规则”是:如果你想要挤上地铁,你就必须要“推挤”。如果你不“推挤”,你就挤不上去。所以,就算你本人非常不想“推挤”,你也必须要“推挤”,这样你才有可能挤上地铁。

Gershenson与团队对站台上的信号灯进行了改动,从而改变了挤地铁的游戏规则:现在,乘客在排队上车时,系统会规定“排在第一位的乘客也是第一位上车的人”。如果乘客还是推挤的话,就会受到系统的惩罚,旁边的人也会提醒Ta说:“你为什么要推?现在已经没有必要推了!”

这时,大家也就不再推挤了。

5 技术提升,交通仍然拥挤

Gershenson认为,要改善城市交通的流动性,最主要的阻碍是政治与社会因素,而不是科学技术。当提议改善城市交通阻塞时,大家会纷纷附和,毕竟没有人想要生活在空气污染的环境下,也不想承受高昂的交通成本,更不想把宝贵的时间浪费在通勤上。但说到解决这些问题的行动,又有很多人都不愿意配合。

Gershenson与团队想出这个点子大概有十五年了,但由于各种复杂的因素,他们在布鲁塞尔、纽约、摩洛哥、墨西哥等地方尝试应用均失败。至于失败的原因,Gershenson认为最主要的阻碍因素是政治。

Gershenson的同事Stefan Lämmer和Dirk Helbing在德国的德累斯顿进行了类似的研究与应用,效果很好。他们用了5年左右的时间推行他们的“自控制交通灯”系统。据Gershenson介绍,德累斯顿当地很赞赏他们的“自控制交通灯”系统,也投入了一定的资金,但出于各种各样的因素,系统的落地应用仍不是很顺利。

Gershenson认为,原因可能是:大多数工程师所学到的都是传统方法,这些方法是基于“预测什么要控制”的理念,所以他们的努力都是围绕着改善传统方法而进行的。但对于复杂的系统来说,预测几乎是毫无帮助的。你针对一个问题,想方设法,好不容易实现优化,结果问题的性质与内容又改变了,那你先前所想的解决措施也就一无是处了。

Gershenson与很多交通领域的科研者一样,都很喜欢骑自行车,因为骑自行车是在距离中等的道路上行驶的最佳方式。图源:Quanta Magazine by Meghan Dhaliwal

所以,我们不仅要提高技术,还要建立一套能够协调各方(包括政府、企业、学者、公众等等)的管理机制。

尽管他向各个城市提出的大多数运输系统解决方案都遇到了政治和官僚障碍,但在2016年,他的想法在墨西哥城地铁系统中得到了成功实施。

Gershenson认为,人们也可以尝试“倒退的交通方式”来解决城市交通拥挤的问题,比如骑自行车。与很多交通领域的科研者一样,Gershenson也很喜欢骑自行车,因为他认为骑自行车是大城市最好的交通方式,完全可以应付距离中等的路程。

AI如何能更好地适应人类生活,这是许多科研者的关注点。自组织系统能够使人工智能产品在保持功能的同时,提高对外界环境的适应能力。在设计系统的过程中,我们也许应该改变传统的“预测”控制论,尝试“自组织”的新理念,让系统更好地适应复杂的外界。

参考链接:

https://www.quantamagazine.org/complexity-scientist-beats-traffic-jams-through-adaptation-20200928/

搜索建议:
热传

 花呗(花呗额度越来越高)

花呗额度越来越高,借呗利率越来越低,中国经济持续向好?近来,有不少人恶意唱衰中国经济,认为中国经济形势非常严峻,不容乐观,甚至有人认为中国经济可能崩溃。我们认为...(展开)

热传

 冬日快乐初一作文

冬日快乐初一作文(精选3篇)在现实生活或工作学习中,大家都有写作文的经历,对作文很是熟悉吧,借助作文可以提高我们的语言组织能力。如何写一篇有思想、有文采的作文呢...(展开)