财新传媒
位置:博客 > 集智俱乐部 > Science重磅: 蚂蚁的智慧——懒惰竟能让交通流输运效率最高

Science重磅: 蚂蚁的智慧——懒惰竟能让交通流输运效率最高

导语
来自美国乔治亚理工大学和德国马斯克·普朗克研究所的研究者,在研究入侵红火蚁挖掘隧道的过程中,发现个体的“懒惰”与有选择的返回行为,能够有效避免因群体数量上升导致的拥塞,使得挖掘过程中搬运泥土的交通流处于最优状态。本文是对这项研究成果的介绍。
 
论文题目:
Collective clog control: Optimizing traffic flow in confined biological and robophysical excavation 
论文作者:
J. Aguilar , D. Monaenkova , V. Linevich , W. Savoie,  B. Dutta, H .-S. Kuan , M. D. Betterton , M. A. D. Goodisman , D. I. Goldman
论文地址:
http://science.sciencemag.org/content/361/6403/672
 
相互作用的活性粒子群、昆虫群体以及人群均可形成包含众多个体的“团簇”,很多时候,这些团簇会阻碍群体协作完成某一特定任务,比如危险情况下的逃生,如果人们都聚集在逃生出口附近就会形成拥堵,使得逃生成功率大大降低。
 
因此,探索、开发能够减少、避免这类拥塞出现的策略就显得十分必要,特别是在空间有限的环境中,如何有效避免拥塞甚至事关生命安全。
 
研究者通过入侵红火蚁的隧道挖掘实验以及相应的理论模型,发现了一个有趣而反直观的结论:在有限、狭窄的隧道空间中,当个体采取“懒惰”以及选择性的返回策略时,隧道挖掘的效率反而大大提高。
 
具体而言,个体的“懒惰”能够减少阻断搬运泥土交通流的拥塞现象的出现,而选择性的退出则能够缩短“团簇”消解的时间,从而减少拥塞的持续时间。
 
更进一步地,研究人员将这一策略用于具有搬运功能的小型机器人,成功地使机器人的交通流达到了近似最优的状态,为解决实际的工程问题提供了支撑。
 
这一研究成果证实了有限空间中的集群协作任务,并不需要复杂的感知、计划以及对群体的全局控制,蚂蚁等社会性动物的高效集群协作表明,简单、局部、分布式的控制策略可使群体涌现出良好的性质。
 
一、入侵红火蚁——高效挖掘隧道的秘籍
 
本文研究者在之前的研究工作中发现,在构造巢穴的初期,蚂蚁喜欢挖掘一些狭窄的隧道。由于在向下挖掘的过程中,需要不断地将泥土从地下搬运到地面,因此,狭窄的隧道有助于蚂蚁身体的借力,从而减少搬运过程中的滑动,降低能量损耗。但随之而来的问题是,隧道狭窄会提高堵塞的可能性,那么蚂蚁是如何解决这一问题的呢?
 
研究人员首先设计了实验用于观察入侵红火蚁的挖掘行为。实验装置是一个透明的圆柱形玻璃容器,其中装入直径为0.25毫米的玻璃颗粒,并且按照0.01与0.1两种土壤湿度加入水以模拟真实的土壤环境。每次实验中,30只入侵红火蚁向下挖掘隧道,不断地将地面以下的玻璃颗粒搬运到地面上。图1展示了蚂蚁巢穴隧道示意图以及隧道挖掘过程。 
 
 
通过对实验过程进行分析,研究人员发现了一些有趣的现象。
 
30只红火蚁中的很大一部分十分“懒惰”(土壤湿度为0.01时比例为22%,土壤湿度为0.1时比例为31%),自始至终都不进入隧道工作。研究人员把这些懒惰的个体称作“假访客(nonvisitor )”,而那些进入隧道工作的蚂蚁则称为“访客(visitor)”。实际上,虽然访客都在干活,但它们的活跃程度也各不相同,根据进入隧道的频率,可以对访客的活跃程度排序(图2C)。
 
访客的活跃程度反映了工作量的大小,那么,每个访客工作量之间的差异会很大吗?这一问题可以由洛伦兹曲线和基尼系数来描述。
 
洛伦兹曲线是1905年由经济学家马克斯·洛伦兹所提出的表示收入分配的曲线,经常被用来描述收入的分配情况。当收入分配完全平等时,每个人的收入相同,洛伦兹曲线是一条斜率为45度的直线;而当收入分配完全不平等时,社会财富集中在一个人手中,洛伦兹曲线变为一条折线。| 维基百科,百度百科
 
洛伦兹曲线给出了访客红火蚁工作量分布情况的直观描述(图2 D),即红火蚁的工作量存在较大的差异,而具体的差异程度则可由基尼系数刻画。
 
基尼系数(Gini coefficient),是20世纪初意大利学者科拉多·基尼根据劳伦茨曲线所定义的判断年收入分配公平程度的指标。在民众收入中,如基尼系数最大为“1”,最小为“0”。前者表示居民之间的年收入分配绝对不平均(即该年所有收入都集中在一个人手里,其余的国民没有收入),而后者则表示居民之间的该年收入分配绝对平均,即人与人之间收入绝对平等,这基尼系数的实际数值只能介于这两种极端情况,即0~1之间。
基尼系数越小,年收入分配越平均,基尼系数越大,年收入分配越不平均。| 维基百科
 
经过计算,红火蚁工作量的基尼系数为0.75,表明即使是在访客中,工作量的分布也很不平等,少数红火蚁承担了大多数的工作量。进一步地,研究者发现,这种工作量的分配方式会随着个体懒惰性的变化进行调整,使得分配方式保持稳定。如图2 D中的插图所示,在去掉访客中最为活跃的红火蚁后,工作量的分配方式保持稳定。这一现象说明,访客懒惰程度的变化对于适应性地调节狭窄隧道中红火蚁的拥挤程度起到了重要作用。
 
除了“懒惰怠工”外,红火蚁还有另一种策略来避免拥塞的出现——选择性的返回。这一行为是指红火蚁进入隧道但是没有搬运泥土就从隧道中退出来,图2 E 对返回行为做了形象的描述。当一只红火蚁进入隧道后,如果在前进的过程中遇到一只向出口运动的红火蚁,那么它也会停止前进,向出口运动。在土壤湿度为0.1与0.01条件下进行的多次观察,返回运动占总旅程的18%与26%。可见返回运动的频繁。同时如图2 F所示,返回次数与蚂蚁数量呈正相关。
 
直观来说,蚂蚁数量越多,在隧道内形成团簇的可能越多,隧道被阻塞的可能性越高,这时如果更多的蚂蚁都采取返回的策略,那么隧道内泥土的运输就不会被中断,从而缓解了阻塞。
 
二、理论模型——视角下挖掘行为的优化
 
1、元胞自动机模型
 
元胞自动机模型在阐释生物动力学以及交通流方面十分有效。研究人员在模型中采用了选择性返回策略,模型中的“蚂蚁”可以移动、改变运动方向、搬运以及放置泥土、休息,与红火蚁的行为方式一致。隧道以二维网格平面表示,不同颜色的网格代表不同的区域与行为,如图3 A所示,红色表示蚂蚁向隧道内运动,黑色则表示向隧道出口运动,灰色区域为待挖掘的泥土,白色则为挖掘好的隧道。 
 
 
元胞自动机(Cellular automaton),又称格状自动机、元胞自动机,是一种离散模型,在可算性理论、数学及理论生物学都有相关研究。它是由无限个有规律、坚硬的方格组成,每格均处于一种有限状态。整个格网可以是任何有限维的。同时也是离散的。每格于t时的态由t-1时的一集有限格(这集叫那格的邻域)的态决定。每一格的“邻居”都是已被固定的。(一格可以是自己的邻居。)每次演进时,每格均遵从同一规矩一齐演进。
就形式而言,元胞自动机有三个特征:(1)平行计算(parallel computation):每一个细胞个体都同时同步的改变(2)局部的(local):细胞的状态变化只受周遭细胞的影响。(3)一致性的(homogeneous):所有细胞均受同样的规则所支配 | 维基百科
 
在模拟过程中,蚂蚁工作量的分配方式采用完全平等(活跃蚂蚁)与不完全平等(洛伦兹蚂蚁)两种。洛伦兹蚂蚁以一定的概率进入隧道,这一概率来自于实际生物实验。两种分配方式下,每个个体都有一定的概率实施返回行为。
 
如图2B所示,经过长时间的模拟,洛伦兹蚂蚁的挖掘隧道的速度与红火蚁的实验结果符合很好,活跃蚂蚁的挖掘速度则与实验相差很远。那么,这一挖掘速度是否是最优的呢?这一问题可以用遗传算法来解决。
 
遗传算法(genetic algorithm (GA) )是计算数学中用于解决最优化的搜索算法,是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的,这些现象包括遗传、突变、自然选择以及杂交等。| 维基百科
 
经过遗传算法的优化,不论开始时蚂蚁进入隧道的概率如何变化,模型模拟得出的蚂蚁工作量分布的基尼系数均收敛为相同值(图3B),证明选择性退出策略下的挖掘行为确实是最优的。同时,优化结果也说明,洛伦兹蚂蚁所采用的工作量分配方式优势显著(图3D)。
 
隧道宽度同样也是影响挖掘速度的重要因素。直观而言,通道的宽度对于拥塞的形成不可忽视。通过蒙特卡洛模拟的方法,可以获取多种满足上述洛伦兹蚂蚁工作量分配的方式,从而研究隧道宽度的作用。如图3C所示, 当隧道宽度为2倍蚂蚁体长时,挖掘长度存在明显的峰值。而当隧道宽度增加时,隧道长度峰值右移,挖掘长度对于工作分配不平等程度的敏感性下降。宽度较窄的隧道实际上促进了洛伦兹蚂蚁挖掘通道的能力。
 
对于隧道挖掘来说,个体在隧道内搬运泥土形成的交通流是反映挖掘效率最为本质的标准。如图3F所示,研究人员将交通流定义为单位时间内单位面积内搬运泥土的蚂蚁数量,发现洛伦兹蚂蚁交通流峰值出现在较低的群体密度时期,而实验观测到的红火蚁的交通流恰恰也是在相应的群体密度时产生,模型与实验很好的符合。 
 
小结
 
通过理论模型与实验结果的对照,证明了红火蚁“懒惰”与选择性退出相结合的策略使得隧道挖掘的效率达到了最优,出现拥塞的可能性大大降低。
 
2、OAT(one-at-a-time)模型
 
红火蚁群体通过自身行为的调节使得运输交通流处于最优状态,且调节方式可以根据群体数量以及隧道宽度适应性地进行,表现出自适应系统的特征。研究人员认为,红火蚁集群行为的背后隐含着简单的控制规则。
 
复杂适应系统理论的核心是适应产生复杂性。复杂系统中的成员被称为有适应性的主体。所谓具有适应性是指它能够与环境以及其他主体进行交互作用。主体在这种持续不断的交互作用的过程中,不断地“学习”或者“积累经验”,并且根据学习到的经验改变自身结构和行为方式。整个宏观系统的演变或进化,包括新层次的产生,分化和多样性的出现,新的、聚合而成的、更大的主体的出现等等,都是在这个基础上逐步派生出来的。| 百度百科
 
OAT模型旨在分析在不同的工作量分配策略下,隧道挖掘的速率如何随着蚂蚁进入隧道的速率变化。模型中,蚂蚁可以进入隧道,在遇到隧道底部或一只向其他方向运动的蚂蚁时就改变运动方向,朝隧道出口运动。
 
图3E中的黄色实线为OAT模型的模拟结果,表明隧道宽度是影响交通流的重要因素,将隧道宽度限制在每单位体长容纳一只蚂蚁时,泥土搬运的交通流可以实现最优。这一结论也与红火蚁实验结果相符合。
 
小结
 
与本文开始所介绍的背景相对应,在巢穴构造的初期,红火蚁挖掘出的隧道宽度很窄,几乎只能容纳单只蚂蚁,通过理论模型的分析与计算,研究人员发现,这种狭窄的隧道不仅有助于蚂蚁身体的借力,更是搬运交通流达到最优的基础。这种长期进化衍生出的智慧令人惊叹。
 
三、机器人挖掘行为控制——仿生智慧的应用
 
在掌握红火蚁隧道挖掘的秘籍后,研究人员将这些挖掘策略应用于机器人的挖掘行为控制,以检验其工程应用的可行性。
 
实际上,在真实环境下的机器人移动控制与生物系统差异很大,物理碰撞等因素并未反应在元胞自动机模型与OAT模型中,因此,红火蚁的隧道挖掘策略能否在机器人系统中获得成功仍有待检验。而将生物集群运动规则运用于集群机器人控制是现阶段以及今后发展的重要方向。
 
研究人员设计制造了一种小型机器人,体型为椭圆形,由车载传感器感应环境并进行运动控制。与红火蚁隧道挖掘实验相类似,研究人员设计了长方形通道作为隧道,并在其中放置可被机器人吸附的磁性颗粒作为泥土(图4A)。
 
1、工作量平等分配时的挖掘性能
 
机器人首先采取工作量平等分配的策略进行挖掘,通过实验发现,随着机器人数量增长,交通流相应增长直到机器人的数量过多开始拥挤。这与理论结果在定型上相符合。
 
2、工作量平等分配时团簇对挖掘效率的影响
 
当多个机器人中心之间的距离小于一个机器人体长时,它们就形成了一个团簇。通过统计团簇出现的频率可以分析团簇的形成对挖掘效率产生的影响。在实验过程中,研究人员通过摄像装置记录了机器人位置的时间累积分布,发现团簇最容易在泥土堆积处产生,意味着机器人密度较高时将产生拥塞。
 
 
3、团簇弛豫时间(relaxation time)
 
弛豫时间可以用于描述团簇形成的级联效应。例如,根据团簇的定义,两个机器人形成的团簇很难被破坏,需要加入第三个机器人作为干扰,但是加入第三个机器人后却可能形成新的团簇,而这个团簇则必须引入第四个机器人才可能被破坏,解除阻塞。以此类推,就成生了团簇形成的级联效应。
 
 
实验表明,采取工作量平等分配策略时,弛豫时间产生突增,团簇产生且不容易被破坏,而洛伦兹分配方式以及选择性返回策略下弛豫时间相对小,变化较为缓慢,不易形成团簇。
 
 
4、懒惰与选择性返回策略对挖掘效率的影响
 
在采用4个机器人进行挖掘时,两种策略下隧道挖掘的效率高于工作量平等分配策略,与前述的理论模型结论相符合。 
 
四、总结
 
正如本文开篇所提到的,不论是存在相互作用的粒子群,还是包括人类在内的社会性动物群体,在空间有限的环境下,个体数量的不断增加势必导致团簇的形成,而很多时候,这种团簇会阻碍群体协作完成特定任务,拥挤导致的踩踏事件就是其中一个典型事例。发展有效的拥塞控制方法,使得拥塞现象被有效避免、及时缓解显得尤为重要。
 
作为典型的社会性动物,蚂蚁在群体协作完成觅食、筑巢、防御与攻击等特定任务时表现出惊人的“智慧”,它们数量庞大却又井井有条,以自组织的方式形成系统,不需要复杂的交流,不需要知道所有同伴的状态,更不需要有统一的指挥官,就可高效完成任务,表现出对环境的高度适应性,是复杂适应性系统的杰出代表。
 
本文所介绍的研究工作正是破解了入侵红火蚁高效挖掘隧道的秘籍,发现了其看似反直观的策略,阐释了懒惰与选择性返回相结合的策略对挖掘效率提高至关重要的影响。在此基础上,通过机器人挖掘实验论证了这两种策略的可行性,为进一步的工程应用奠定了基础。
 
这一研究工作充分说明,生物集群运动的研究成果运用于集群机器人控制将成为现阶段以及今后机器人研究与工程应用的重要方向,为解决更多的实际问题提供有力的支撑。
 
作者:王伟嘉
编辑:王怡蔺
推荐 0