软件学报ＩＳＳＮ １ ０００．９８２５，ＣＯＤＥＮ ＲＵＸＵＥＷ Ｊｏｕｒｎａｌ ｏｆＳｏｆｔｗａｒｅ，２０１２，２３（１１）：２９３７—２９４５［ｄｏｉ：１０．３７２４／ＳＰ．Ｊ．１００１．２０１２．０４３０７］ ◎中国科学院软件研究所版权所有． Ｅ－ｍａｉｌ：ｊＯＳ＠ｉｓｃａｓ．ａｃ．ｃｎ ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ １１ｅ１／Ｆａｘ：＋８６．１０．６２５６２５６３ 基于多智能体交通绿波效应分布式协同控制算法 徐杨 ，张玉林，孙婷婷，苏艳芳 （电子科技大学计算机科学与工程学院，四川成都６１ １７３１） Ａｇｅｎｔ－－Ｂａｓｅｄ Ｄｅｃｅｎｔｒａｌｉｚｅｄ Ｃｏｏｐｅｒａｔｉｖｅ Ｔｒａｆｉｃ Ｃｏｎｔｒｏｌ Ｔｏｗａｒｄ Ｇｒｅｅｎ－ｆ－Ｗａｖｅｄ Ｅｆｆｅｃｔｓ ＸＵ Ｙａｎｇ ，ＺＨＡＮＧ Ｙｕ—Ｌｉｎ，ＳＵＮ Ｔｉｎｇ－Ｔｉｎｇ，ＳＵ Ｙａｎ－Ｆａｎｇ （Ｓｃｈｏｏｌ ｏｆＣｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ ａｎｄＥｎｇｉｎｅｅｒｉｎｇ，Ｕｎｉｖｅｒｓｉｔｙ ｏｆＥｌｅｃｔｒｏｎｉｃ Ｓｃｉｅｎｃｅ ａｎｄＴｅｃｈｎｏｌｏｇｙ ｏｆＣｈｉｎａ，Ｃｈｅｎｇｄｕ ６１１７３１，Ｃｈｉｎａ） ＋Ｃｏｒｒｅｓｐｏｎｄｉｎｇ ａｕｔｈｏｒ：Ｅ－ｍａｉｌ：ｘｕｙａｎｇ＠ｕｅｓｔｃ．ｅｄｕ．ｃａ Ｘｕ Ｙ，Ｚｈａｎｇ ＹＬ，Ｓｕｎ ＴＴ，Ｓｕ ＹＦ．Ａｇｅｎｔ－Ｂａｓｅｄ ｄｅｃｅｎｔｒａｌｉｚｅｄ ｃｏｏｐｅｒａｔｉｖｅ ｔｒａｆｉｃ ｃｏｎｔｒｏｌｆ ｔｏｗａｒｄ ｇｒｅｅｎ－ｗａｖｅｄ ｅｆｆｅｃｔｓ．Ｊｏｕｒｎａｌ ｏｆＳｏｆｔｗａｒｅ，２０１２，２３（１１）：２９３７—２９４５（ｉｎ Ｃｈｉｎｅｓｅ）．ｈｔｔｐ：／／ｗｗｗ．ｊｏｓ．ｏｒｇ．ｃｎ／１０００—９８２５／４３０７．ｈｔｍ Ａｂｓｔｒａｃｔ： Ｇｒｅｅｎ—Ｗａｖｅｄ ｔｒａｆＩｉｃ ｃｏｎｔｒｏ１ ｉＳ ｏｎｅ ｏｆ ｔｈｅ ｍｏｓｔ ｅｆｆｉｃｉｅｎｔ ｓｔｒａｔｅｇｉｅｓ ｉｎ ａｌｌｏｗｉｎｇ ｃｏｎｔｉｎｕｏｕｓ ｔｒａｆｉｃ ｆｒｏｍ ｆｍａｊｏｒ ｄｉｒｅｃｔｉｏｎｓ ｌｆｏｗ ｏｖｅｒ ｍｕｌｔｉｐｌｌｅ ｉｎｔｅｒｓｅｃｔｉｏｎｓ ｔｏ ｉｍｐｒｏｖｅ ｕｒｂａｎ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｅｆｉｃｉｆｅｎｃｙ．Ｗｈｅｎ ｔｈｅ ｎｕｍｂｅｒ ｏｆ ｔｒａｆｉｃ ｌｆｉｇｈｔｓ ｓｃａｌｅｓ ｕｐ，ｔｒａｄｉｔｉｏｎａｌ ｃｅｎｔｒａｌｉｚｅｄ ｃｏｎｔｒｏｌ ｓｕｆｆｅｒｓ ａ ｂｏｔｔｌｅｎｅｃｋ ｉｎ ｂｏｔｈ ｃｏｍｍｕｎｉｃａｔｉｏｎ ａｎｄ ｃｏｍｐｕｔａｔｉｏｎ． Ｄｅｃｅｎｔｒａｌｉｚｅｄ ｃｏｎｔｒｏｌ ｉｓ ｐｏｔｅｎｔｉａｌｌｙ ｉｎｅｆｉｃｉｆｅｎｔ ｗｈｅｎ ｌｏｃａｌ ｔｒａｆｉｃ ｌｆｉｇｈｔｓ ｏｎｌｙ ｇａｉｎ ｖｅｒｙ ｌｉｍｉｔｅｄ ｏｂｓｅｒｖａｔｉｏｎｓ ｔｏ ｔｈｅ ｗｈｏｌｅ ｎｅｔｗｏｒｋ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｏｐｏｓｅｓ ａ ｄｅｃｅｎｔｒａｌｉｚｅｄ，ｍｕｌｔｉ—ａｇｅｎｔ ｂａｓｅｄ ｓｃｈｅｍａ ｔｏ ａｄａｐｔｉｖｅｌｙ ｃｏｎｔｒｏｌ ｍａｓｓｉｖｅ ｔｒａｆｉｃ ｆｌｉｇｈｔｓ，ｗｈｉｃｈ ｐｒｏｍｏｔｅｓ ｔｈｅ ｅｆｆｅｃｔｓ ｏｆ ｇｒｅｅｎ－ｗａｖｅ．Ｔｈｅ ｋｅｙ ｉｓ ｔｈａｔ ａｇｅｎｔｓ ｕｓｅ ｔｈｅ ｐｒｏｓｐｅｃｔｉｏｎ ｏｆ ｌｏｃａｌ ｓｔａｔｅ ｏｎｅ ｔｉｍｅ ａｈｅａｄ ａｓ ｅｖｉｄｅｎｃｅ ｔｏ ｓｕｐｐｏｒｔ ｄｅｃｉｓｉｏｎｓ．Ｎｏｔｉｎｇ ｔｈａｔ ｏｎｌｙ ｔｈｅ ｔｒａｆｉｃ ｆｆｒｏｍ ｔｈｅ ａｄｊａｃｅｎｔ ｉｎｔｅｒｓｅｃｔｉｏｎｓ ａｆｆｅｃｔ ｔｈｅ ｎｅｘｔ ｓｔａｔｅ ｏｆ ａ ｇｉｖｅｎ ｉｎｔｅｒｓｅｃｔｉｏｎ，ｔｈｅ ｓｔｕｄｙ ｍｏｄｅｌｓ ｔｈｅ ｉｎｔｅｒａｃｔｉｏｎｓ ａｓ ｄｅｃｅｎｔｒａｌｉｚｅｄ ａｇｅｎｔｓ ｔｏ ｃｏｏｐｅｒａｔｉｖｅｌｙ ｃｏｏｒｄｉｎａｔｅ ｅａｃｈ ｉｎｔｅｒｓｅｃｔｉｏｎ ｂｙ ｕｓｉｎｇ ｄｅｃｉｓｉｏｎ ｔｈｅｏｒｅｔｉｃａｌ ｍｏｄｅｌｓ．Ｔｈｉｓ ｐａｐｅｒ ｐｒｅｓｅｎｔｓ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｎｄ ｓｉｍｕｌａｔｉｏｎ ｒｅｓｕｌｔｓ ｔｏ ｐｒｏｖｅ ｔｈｅ ｆｅａｓｉｂｉｌｉｔｙ ｏｆ ｔｈｅ ａｐｐｒｏａｃｈ ｔｏ ｍａｓｓｉｖｅ ｕｒｂａｎ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｓｙｓｔｅｍ． Ｋｅｙ ｗｏｒｄｓ： ｍｕｌｔｉ－－ａｇｅｎｔ ｓｙｓｔｅｍ；ｇｒｅｅｎ・・ｗａｖｅｄ ｅｆｆｅｃｔ；ｔｒａｆｉｃ ｌｆｉｇｈｔ ｃｏｎｔｒｏｌ；ｄｅｃｅｎｔｒａｌｉｚｅｄ ｃｏｏｒｄｉｎａｔｉｏｎ 摘要： 基于“绿波”效应的交通控制通过实现干道上的车流不间断地经过多个交通灯路口而不停止，是目前公认 的最有效率的交通控制策略之一．然而随着城市交通规模的不断扩大，传统的集中式交通控制方法可能遇到计算和 通信上的瓶颈．而当路口交通灯只能获取城市交通网络全局有限的信息时，传统的分布式控制方法可能十分低效．提 出了一种基于多智能体的交通灯分布式绿波自适应控制方法．在该设计中，每一个交通灯路口通过一个非集中式的 协同智能体来控制．其核心是，智能体通过预测自身下一时刻的状态进行自主决策．由于只有来自邻居路口的车辆能 够直接影响当前路口下一步的状态，这一决策过程仅需要智能体通过与邻居智能体间的局部交互来完成．描述了基 于多智能体交通灯分布式“绿波”效应的控制算法，并通过仿真实验验证了该方法在大规模城市交通系统中的可 行性． 关键词： 多智能体系统；“绿波”效应；交通灯控制；分布式协同控制 中图法分类号：ＴＰ１８ 文献标识码：Ａ ・基金项目：国家自然科学基金（６０９Ｏ５Ｏ４２，６０９５０１１０３５４）；航空科学基金（２Ｏ１０Ｏ５８Ｏ００５）；高校基本科研业务费专项资金 收稿时间：２０１２．０６．０２；定稿时间：２０１２－０８—２１ （ＺＹＧＸ２０１１Ｘ０１３） ２９３８ Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ ２０１２ 随着城市人口的扩大，交通拥堵日益严重，智能交通成为现代城市发展的一个瓶颈问题【】 ］．在智能交通方 案中，“绿波”效应通过多个交通灯路口协同工作，使干道上的车辆能够顺利通过多个路口而不停止［４］，是目前最 有效的控制方法．在目前的交通灯“绿波”控制方案［４－１０】中，典型的是根据数据的统计规律［１０，１１］来进行控制，然而 这类方法无法自适应交通动态变化的特性从而无法处理突发交通状况，比如自适应地震后灾难救援所引发突 变的交通状态等．另一类控制方案根据接收到的实时数据，通过动态规划的方式来实现交通灯控制，然而这类方 案在实际应用中会产生很多瓶颈问题．例如，文献『６，１２］通过一个集中式的控制模型来管理交通灯，但随着城市 交通灯规模的扩大，控制中心必然会产生计算瓶颈．文献［１３，１４］虽然通过假设所有交通灯都能获得全局状态，并 通过分布式策略解决了计算瓶颈问题，但实际应用中的通信瓶颈问题却难以避免．另一方面，通过获取全局状态 或集中式的控制方法由于时延和瓶颈，往往无法高效地应对灾难等突发交通情况． 在非集中式“绿波”控制方法的研究中，ＲＨＯＤＥＳ［８】通过在交通网络中建立一个３层的控制模型对交通灯进 行控制，在保证响应实时交通需求的情况下对“绿波”效应进行了规划．然而，文献［８］主要针对底层交通灯的自适 应控制方案进行研究，对如何进行高层次的“绿波”效应规划的研究并没有提出相应的智能算法．Ｊｕｎｇｅｓ等人通 过ＤＣＯＰ模型［１５，１６］实现道路网络中所有路口放行方向的规划，很好地对“绿波”效应进行了规划．然而该方法主 要依赖路口之问通过消息传递的方式保证路口间的一致性，随着规模的扩大，信息传递量变大，收敛时间变慢． 同时，这种方法建模中主要考虑车辆的直行，对车辆转弯等实际交通常见模式的建模简化，降低了算法复杂度， 但也缺乏对复杂交通的白适应支持能力． 本文主要针对大规模城市交通系统中交通灯的控制问题，提出了一种基于多智能体系统的分布式交通灯 协同控制方法以实现自适应的交通网络“绿波”效应．在该方法中，每个交通灯路口由一个路口智能体控制，为了 产生“绿波”效应，我们的核心思想是，每个路口智能体能够通过预测自身下一时刻的交通状况来控制交通灯的 状态．虽然路口智能体无法获得整个道路系统的全局状态，但是由于只有来自邻居路口的车流可以直接影响当 前路口下一时刻的交通状态【ｌ 】，因此，智能体仍然可以通过与邻居路口智能体的交互，通过当前路口的状态来预 测自身下一时刻的交通情况，从而选择最优的控制策略实现“绿波”效应．在此基础上，我们为每个路口智能体建 立了基于马尔可夫的协同理论决策模型【】 ．在该模型中，每个路口智能体的状态建模都包括了邻居路口的交通 状况，从而可以通过这种局部观测估计当前路口下一时刻的交通情况．虽然理论上这种方法可被应用到大规模 的交通信号等的控制中，但是在复杂的交通环境中，由于无法预测车辆在交通环境中的行为，导致了决策模型中 状态转移具有一定的不确定性，包括：（１）给定时间内通过绿灯路口的车辆数目的不确定性；（２）车辆进入道路 后所选择下一路口转向车道的不确定性；（３）车辆通过路口后到达下一个路口的时间由道路情况和交通拥塞状 况决定．为了解决这一问题，本文通过历史统计和强化学习的方法估算这些参数，从而实现路口智能体最优策略 的选择以降低该路口车辆等待时间．最后，本文通过搭建仿真平台模拟了复杂交通系统中几种常见的模式，并比 较了不同控制策略在不同环境中的表现．通过与其他控制方法对比实验，证明了本文的控制方式可以有效地应 用到大规模的、复杂的城市交通系统控制中． １ 问题描述 给定的交通系统可以被建模成无向图Ｇ（ ，如图１所示．其中， 是路口集合，Ｅ是路口之间的道路集合．对 任意相邻路口ｖ 和ｖ『，（ｖｆ， ，）∈Ｅ表示一条连接路口ｖ 和 ，的道路．特别地，集合ｎ（ｖｆ）表示路口ｖ 所有邻居路口，并 Ｊ￣．ｉｎ（ｖ ）Ｊ是其邻居的数目．如图ｌ所示，Ｉｎ（ｖ－）Ｉ＝４，［ｎ（ｖ４）ｌ＝３．在通往路口ｖ 的道路上，共有Ｉｎ（ｖ ）Ｉ一１条不同转向的车道． 如图１所示，在开往路口ｖ１和 １３的道路中分别有３条和２条不同转向的车道．因此，在所有开往路口ｖ 的道路 中，总车道数可以表示为ｌｎ（ｖｆ）ｌｘ（Ｉｎ（ｖｆ）ｌ一１）．这里，我们用Ｌｎｉ（ｋ）表示从路口ｖ，开往ｖ 并即将转向路口ｖ 的车道． 由于开往ｖ 的车辆只能转向ｖ 的邻居路口而不能跳跃式地抵达任意路口Ｖｋ，因此，对于Ｌｎｉ（ｋ），ＶｋＥ｛ｎ（ｖ，）一ｖ 对于每个路口在当前时刻ｔ，当前在车道Ｌｎｉ（ｋ）中排队等待通行的车辆可以被安装在路口的摄像头探测到，我 们定义为 （．ｉ｝，ｆ）．由于我们无法提前探测到车道下一时刻等待的车辆数目，因此 （七，ｔ＋１）不可观测． 徐杨等：基于多智能体交通绿波效应分布式协同控制算法 ２９３９ ＾ ｚ 一 ｊ。 “。 ％ 鼍？ ａ ＿ ｜ ＿ 蕊ｆ ｌ ｜ 。 Ｆｉｇ．１ Ｇｒａｐｈ ｍｏｄｅｌ ｏｆ ｕｒｂａｎ ｔｒａｆｉｃ ｎｅｔｗｏｒｋ ｆ图ｌ 城市道路交通网络建模 在路口，每个交通灯都通过控制一个特定转向的车道的放行来改变自己车道等待车辆的数目．特别地，在ｔ 时刻，控制从路口ｖｊ经过路口ｖｆ转向ｖ 的车道上的交通灯动作可表示为￡ （后，ｔ）∈｛ｇｒｅｅｎ，ｒｅｄ｝，分别表示变红和 变绿．由于黄灯是从绿灯变为红灯时的一个中间非状态，这里不考虑其为一个可选动作．每个决策周期内， 在动作￡ （ ，ｔ）的作用下，原来等待的车辆根据交通灯指示会驶出当前车道，同时也有新的车辆驶入该车道，因 此，在采取动作￡ （．ｉ｝，ｔ）后，当前车道的等待车辆数目 （ ，ｔ）会转化为 （ ，ｔ＋１）． 在交通灯“绿波”现象中，多个交通灯可以协同合作，使得某个方向的车流可以连续地通过多个路口而不停 止．为了促进“绿波”现象，各路口应该相互协作，使更多的车辆能够在路口之间通行．为了最大化运动的车辆，则 应最小化等待在路口的车辆．由于“绿波”效应的预见性要求，交通灯的协同要求最小化下一时刻等待的车辆，因 此其效用函数定义为 ＥＵ（６，ｆ）＝∑∑ ∑ ｖｉｅＶ ｅｎ（ｖｉ）ｖｋＥ（ｎ（ｖｐ一 ） （ ，Ｈ１）． Ｇ， 是整个道路网络中什１时刻每个 在上述公式中，整个交通网络Ｇ在ｆ时刻协同工作产生的效用值 协同工作后，整个交通网络的期望效用值最小，即 ￣（ｔ）＝ａｒｇｍｉｎｊｔ口ｃｆ（Ｇ，ｆ Ｇ， 路口ｖ 等待车辆数目的总和．基于上述的期望效用函数，交通控制的优化目标是要找到最优的策略 ，使交通灯 （１） 其中 ａｃｔ（Ｇ， 是整个交通道路网络在ｔ时刻所有交通灯的动作的集合，可以表示为 Ｊｔ（Ｇ，ｆ）＝Ｕ Ｕ （ ）Ｕ 『｝￡ ，ｆ）． 由于 （ ，ｔ＋１）不可观测，直接寻找最优策略 是ＮＥＸＰ．ＣＯＭＰＬＥＴＥ． ２基于多智能体的交通控制系统框架 为实现“绿波”效应，关键要基于对当前路口下一时刻状态的预测，做出最优决策使得下一时刻路口等待车 辆数最少．然而，下一时刻路口状态既不能观测，也不能通过获得整个道路网络的全局状态来计算．在本文中，对 路口ｖ ，我们利用如下交通道路特征，实现对当前路口下一时刻状态进行估计： １）ｖ 在什１时刻的状态受其在ｔ时刻状态的影响； ２ 由于车辆只能通过邻居路口到达，ｖ 下一时刻状态仅受其邻居路口当前状态的影响． 因此，只有当前邻居路ＩＺｌ的交通状况和当前路口的车流能够影响路Ｅｌ下一时刻的决策．如果相邻路Ｅｌ之问 能够共享交通状态信息和即将采取的动作，路口可以获得足够的信息，提前做出下一时刻的决策来优化交通控 制，实现“绿波”效应． 基于以上分析，我们建立一个多智能体系统控制模型，如图２（ａ）所示．该模型主要建模了路Ｉ＝Ｉ之间的协同控 制，这里定义了智能体集合 ｛ ， …．， ，．．．｝， ＝ｆ ．其中，每个智能体 控制路口ｖ 中的所有交通灯，如图２（ｂ） 所示．因此，所有Ｄ中的智能体可以形成与路口集合 相同的网络，并且智能体 的邻居为所有控制ｖ 的邻居路 ＩＺｌ的智能体的集合，即ｎ（ｄｉ）＝｛ｄｊｌｖｊｅｎ（ｖｍ． ２９４０ Ｊｏｕｒｎａｌ ｏｆＳｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ ２０１２ 、、 ，、 ¨ ．（ａ） （ｂ） 、／ 、，吱 － 出 Ｌ 一 Ｆｉｇ．２ Ｍｕｌｔｉ－Ａｇｅｎｔ ｂａｓｅｄ ｔｒａｆｉｃ ｌｆｉｇｈｔ ｃｏｏｒｄｉｎａｔｉｏｎ ｍｏｄｅｌ 图２基于多智能体系统的交通灯协同控制模型 在ｔ时刻，智能体 可以获得路口ｖｆ的状态定义为 ｒｆ（ｖｉ，ｆ） Ｕ （ ）Ｕ 作）来预估其下一时刻的交通状况．这里可以定义 在ｔ时刻的状态： ，ｆ）・ 然而，为了实现“绿波”控制， 应该获得足够的状态信息（包括邻居路口当前的状态和ｔ时刻即将采取的动 警 （ｆ）＝ｒｆ（ｖ，，ｆ）ＵｖＪ∈ ）Ｔｆ（ｖｊ，ｆ）Ｕ （ ）￡，（ｆ） （２） 其中，￡』（ｆ）＝Ｕ ，）Ｕ ㈨ 一Ⅵ）￡ （ ，ｆ）． 在上述公式中，智能体 的状态由ｔ时刻当前路口的交通状况以及邻居路口的交通状况和即将采取的动作 ｔ 及其邻居必须提前共享自己即将采取的动作．组成．由于邻居路口ｔ时刻的动作需要提前被告知以获取Ｓｄ（），，因此，智能体之间相互决策都需要基于其邻居智能体的决策结果而形成“死锁”．为了打破这种“死锁”，本文第３ ｔ）来推导路口 节设计了一种有效的机制．并且，本模型的另一个关键点是如何根据智能体ｄｉ在ｔ时刻的状态 （ｖｆ在 １时刻的等待车辆数目 ｖ ，什１），这一问题将在第４节讨论． 算法１主要描述了路口智能体之间如何协同工作，产生下一时刻的最优策略Ｊｔ ，升１）的过程．在每一个ａｃｔ（Ｇ 决策时间段，智能体 要向邻居共享自己当前时刻的状态和即将采取的动作（第２行），并获得决策所需要的局部 环境状态（第３行Ｇｅｔｌｎｆｏ（ｎ（ｄｉ）））．根据从邻居获取的信息， 更新自己的局部状态模型（第３行）．然后， 基于自 身的局部环境状态信息提前选择最优的联合动作￡ （ｆ＋１）（第４行）．因此，通过路口之间的协同，所有路口智能 体 共同产生了交通灯道路网络中的联合动作Ｊｔ ，什１）．ａｃｔ（Ｇ 算法１．路口智能体的协作流程． １．ｆｏｒ ａｌｌ ｅＤｄｏ ２． ＳｈａｒｅＷｉｔｈＮｅｉｇｈｂｏｒｓ（Ｔｆ（ｖｉ，ｆ），￡ｆ（ｆ））； ３． Ｓｄ（ｔ）÷一 （ ，ｔ）ＵＧｅｔｌｎｆｏ（ｎ（ｄ１））； ，４． ￡ （ｆ＋１） ＤｅＪｔＤｅｃｉｓｉｏｎ（ｄｉ，Ｓｄ，（ｆ））； ５． Ｊｔ—ａｃｔ（Ｇ，ｔ＋１）＝Ｊｔ—ａｃｔ（Ｇ，ｔ＋１）Ｕ￡ｆＯ＋１）； ６．ｅｎｄｆｏｒ ７．ｒｅｔｕｒｎ Ｊｔａｃｔ（Ｇ， １） ＿３路口智能体协同控制决策算法模型 在本节中，我们主要阐述集合Ｄ中的所有路口智能体是如何进行自主决策，从而产生“绿波”效应的．由算 法１可知，在获取了局部环境状态信息 （ ）以后，智能体 ∈Ｄ要根据函数ＤｅＪｔＤｅｃｉｓｉｏｎ（ｄｉ， （ｆ））提前选择下一 时刻的最优联合动作．函数ＤｅＪｔＤｅｃｉｓｉｏｎ（ｄ￣，Ｓｄ （ｆ））可以展开为一个马尔可夫决策模型（ ，Ａ，Ｔ，Ｔｆ（ｖ３），在该模 型中． 徐杨等：基于多智能体交通绿波效应分布式协同控制算法 ２９４１ ・状态：Ｓｄ（ｔ）是ｄｉ在ｔ时刻的局部环境状态，由邻居的状态、动作和自身状态组成． ・动作： 是智能体 控制的路口ｖ 下所有交通灯的可行亮灯组合．智能体 仅从自身交通灯路口的动作 集合 中选择最优动作． ・状态转移方程Ｔ：Ｓｄ， （ｖ１）表示从当前状态 推导出路口下一时刻路口交通状况 Ｖｉ， １）． ・回报函数用升１时刻等待车辆数ｒｆ（ｖ １）表示． 这样，智能体ｄｉ的最优策略，ｒｇ 可以被表示为７／＂ ＝ａｒｇｍｉｎ ｆｆ１ｒｆ（ｖ，，ｔ＋１），并通过标准的马尔可夫决策模型 求解算法进行求解，例如可用价值迭代方法． 本模型的关键是路口智能体要将当前时刻路口中所有交通灯的联合动作提前告知邻居智能体，以帮助智 能体建立其局部环境状态．然而，路口智能体恰好需要利用这个局部环境状态来选择自己当前时刻的动作，因 此，这里出现了死锁，即智能体必须提前共享其决策结果才能做决策． 为了打破这种死锁，根据公式（２），由于向邻居共享的动作只是决策状态中很小的一部分，如果利用一个近 似的行为来代替将要进行的动作，并不会对其邻居的决策带来很大影响．因此，我们可以通过求得￡ （ｆ）的估计 值￡ （ｆ）来代替，从而得到状态定义： （ｆ）＝ｒｆ（ｖ，，ｆ）Ｕ ， ）ｒｆ（ｖ，，ｆ）Ｕ ）￡广（ｆ）・ ￡，（ｆ）可用很多方法获得，其中最直接的方法是在ｔ－１时刻根据路口的等待车辆数目 ｖｆ，ｔ－１）来估计．因此， 可通过设计一个有效的算法来求出￡，（ｆ）：ｒｆ（ ，ｔ一１） ￡，（ｆ）．尽管这个估计值并不精确且很大程度上取决于 历史状态，但是由于交通状况是连续变化的，该模型依然有效． ４转移方程的启发式预测模型 由第３节可知，对于每个路口智能体，决策模型求解的关键是如何根据路口当前的交通状况Ｓ （ｆ）求解路口 下一时刻的等待车辆数 （｜ｊ｝，ｔ＋１）．通过对大规模交通系统的观察我们发现，在求解 （ ，ｔ＋１）的过程中，状态 转移主要有以下不确定因素： １）在绿灯时，受路口交通状况的影响，可以顺利通过路口的车辆数目具有不确定性； ２）通过路口的车辆在开往下一个路口时，会选择某转向车道，而驾驶员车道的选择无法精确预测； ３１由于连接路口的道路状况的不确定性，进入车道的车辆到达路口的时间具有不确定性． 由于这些不确定因素在不同的交通状况下具有很大差异，本文中，我们的模型基于以下两个基本假设： （１）在一个绿灯周期中，每条车道最多能通过的车辆数是 踞一个预定参数，若，ｇｉＪ（ｋ，ｔ）＝ｇｒｅｅｎ，在固定 的交通灯周期Ｃｙｃｌｅ， Ｖｄ／（后，ｆ）：ｊ【 ，ｆ），ｉｆ ， ） ； ｏｔｈｅｒｗｉｓｅ ， 如果￣ｉＪ（ｋ，ｔ）＝ｒｅｄ，则ｒｄ／（ｋ，ｆ）＝０． （２）当一辆车通过路口进入下条道路时，它选择每条车道的概率可以通过统计和机器学习的方法通过历史 观测获得．车辆选择车道的概率 （尼）为Ｖｖｋ∈ｎ（ｖｉ），ｖｊ∈ｎ（ｖｉ）一Ｖｋ， （ ）＝ －『 ．，其中， √， 为历史数据获得的 常量． 根据以上假设，我们可以建立从 ，（ ，ｔ）到 ，（Ｊ］｝，ｔ＋１）的转移方程．由于进入该车道上面的车辆数目是由 上个交通灯周期中选择进入该车道的车辆数目决定的，因此有，进入该车道的车辆数目为 ）× ∑ ｖｌｓｎ（ｖｊ）ａｎｄｖｔ （ｆ，ｆ） （３） 然而，受到交通状况的影响，并非所有进入该车道的车辆都能在该交通灯周期内达到路ＶＩ．因此，我们通 过一种简单的算法，根据已知的车辆平均速度国、车道长度 （ ）、车身平均长度ｏｒ，计算在交通灯周期 ｃｌｅ内， Ｊｏｕｒｎａｌ ｏｆ Ｓｏｆｔｗａｒｅ软件学报Ｖｏ１．２３，Ｎｏ．１１，Ｎｏｖｅｍｂｅｒ ２０１２ 结果可知，在智能放行策略中，车辆疏散时间更短，其疏散能力更强． 第３组实验测试了交通拥堵时，车辆从进入城市到经过城市中心的运行时间．这种交通状况主要模拟早晨 的车流高峰期．初始情况下，８０辆车分别从网络边缘向网络中行进，其中随机采样了５辆车的运行时问，实验结果 如图５（ｄ）和图５（ｅ）．在大多数情况下，智能放行策略的效率都高于轮转法．因此，我们的放行策略可以降低拥堵．另 一方面，在车辆较多、交通拥堵时，车辆的等待时问会增加．如在下班时间，大量车辆从商业中心往外涌．为了尽快 疏散这些车辆，应该鼓励车辆向外运动．因此，在同一路口，关键是要使车辆多的车道拥有更高的绿灯优先级，但 对于疏散方向相反的车辆，其等待时间会严重增加．为了证明这个结论，我们做了第４个实验．这里，我们在道路 网络中设置了４００辆车准备从城市中心往外面疏散，采样了５辆从不同路径，由城市外面向中心运动的车辆，实 验结果如图５（０所示．正如我们所预期的，几乎所有采样车辆的等待时间都极大地增加，甚至其中～些是轮转法 的２倍多． ６总 结 本文提出了一种基于多智能体的分布式协同控制策略，通过“绿波”控制的方法，在大规模城市道路系统中 提高控制效率．为了产生“绿波”效应，我们通过提前预估下一时刻的状态来实现交通灯路口间协同优化决策．我 们通过为每个路口建立智能体，相邻智能体之问局部交互建立马尔可夫决策过程选择最优控制行为．实验结果 表明，我们的控制方案可以产生“绿波”效应，并能有效地处理交通拥塞的情况，同时，这种方案还可以疏散车辆并 且避免拥堵．另一方面，在本文中，我们通过设计抽象平台的仿真方法来验证本研究方案的可行性．虽然这一仿 真通过模拟大规模城市交通网络中车辆运行场景论证了本研究的可行性，但该仿真仍然在一定程度上简化了 城市交通的很多不确定性复杂因素．在未来的工作中，如何设计有效的智能交通仿真平台，既能有效地仿真智能 交通各方面的复杂因素，又能用于不同算法之间的横向比较，将是本研究未来工作的一个重点． Ｒｅｆｅｒｅｎｃｅｓ： 【１］Ｆｉｇｕｅｉｒｅｄｏ Ｌ，Ｊｅｓｕｓ Ｉ，Ｍａｃｈａｄｏ ＪＡＴ，Ｆｅｒｒｅｉｒａ ＪＲ，ｄｅ Ｃａｒｖａｌｈｏ ＪＬＭ．Ｔｏｗａｒｄｓ ｔｈｅ ｄｅｖｅｌｏｐｍｅｎｔ ｏｆｉｎｔｅｌｌｉｇｅｎｔ ｔｒａｎｓｐｏｒｔａｔｉｏｎ ｓｙｓｔｅｍｓ Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ Ｉｎｔｅｌｌｉｇｅｎｔ Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｓｙｓｔｅｍｓ ２００１，１２０６—１２１ １．［ｄｏｉ：１０．１ １０９／ＩＴＳＣ．２００１．９４８８３５］ 【２］ Ｒｉｃｈｔｅｒ Ｓ．Ｌｅａｒｎｉｎｇ ｒｏａｄ ｔｒａｆｉｃ ｃｏｎｔｆｒｏｌ：ｔｏｗａｒｄｓ ｐｒａｃｔｉｃａｌ ｔｒａｆｆｉｃ ｃｏｎｔｒｏｌ ｕｓｉｎｇ ｐｏｌｉｃｙ ｇｒａｄｉｅｎｔｓ．Ｄｉｐｌｏｍａｒｂｅｉｔ：Ａｌｂｅｒｔ－Ｌｕｄｗｉｇｓ— Ｕｎｉｖｅｒｓｉｔｙ Ｆｒｅｉｂｕｒｇ，２００６．ｈｔｔｐ＂ＮＷＷＷ．ｉｎｆｏｒｍａｔｉｋ．ｕｎｉ—ｆｒｏｉｂｕｒｇ ｄｅ／－ｓｒｉｃｈｔｅｒ／ｐａｐｅｒｓ／ｒｉｃｈｔｅｒＯ６ｔｈｅｓｉｓ．ｐｄｆ 【３１ ＲｏｂｅｒｔｓｏｎＤＩ．“ＴＲＡＮＳＹＴ”ｍｅｔｈｏｄｆｏｒ ａｒｅａｔｒａｆｉｃ ｆｃｏｎｔｒｏ１．ＴｒａｆｉｃＥｎｇｉｆｎｅｅｒｉｎｇ ａｎｄＣｏｎｔｒｏｌ，１９６９，ｌ１（６）：２７６－２８１． ［４］ Ｗａｒｂｅｒｇ Ａ，Ｌａｒｓｅｎ Ｊ，Ｊｏｒｇｅｎｓｅｎ ＲＭ Ｇｒｅｅｎ ｗａｖｅ ｔｒａｆｉｃ ｏｐｔｆｉｍｉｚａｔｉｏｎ－－Ａ ｓｕｒｖｅｙ．Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ，ＩＭＭ－Ｔｅｃｈｎｉｃａｌ Ｒｅｐｏｒｔ一２００８— ０１，Ｄａｎｍａｒｋｓ Ｔｅｋｎｉｓｋｅ Ｕｎｉｖｅｒｓｉｔｅｔｙ，２００８． ［５】Ｐａｐａｇｅｏｒｇｉｏｕ Ｍ，Ｄｉａｋａｋｉ Ｃ，Ｄｉｎｏｐｏｕｌｏｕ Ｖ，Ｋｏｔｓｉａｌｏｓ Ａ，Ｗａｎｇ ＹＢ．Ｒｅｖｉｅｗ ｏｆ ｒｏａｄ ｔｒａｆｉｃ ｃｏｎｔｆｒｏｌ ｓｔｒａｔｅｇｉｅｓ．Ｐｒｏｃ．ｏｆ ｔｈｅ ＩＥＥＥ， ２００３，９１（１２）：２Ｏ４３—２０６７．［ｄｏｉ：１０．１ １０９／ＪＰＲＯＣ．２００３．８１９６１０】 ［６］ Ｒｏｂｅｒｔｓｏｎ ＤＩ，Ｂｒｅｔｈｅｒｔｏｎ ＲＤ．Ｏｐｔｉｍｉｚｉｎｇ ｎｅｔｗｏｒｋｓ ｏｆ ｒｔａｆｆｉｃ ｓｉｇｎａｌｓ ｉｎ ｒｅａｌ ｔｉｍｅ—Ｔｈｅ ＳＣＯＯＴ ｍｅｔｈｏｄ．ＩＥＥＥ Ｔｒａｎｓ．ｏｎ Ｖｅｈｉｃｕｌａｒ Ｔｅｃｈｎｏｌｏｇｙ，１９９１，４０（１）：１ １－１５．【ｄｏｉ：１０．１ １０９／２５．６９９６６］ ［７】 Ｍａｒｋｏｓ Ｐ．Ｔｒａｆｉｃ ｆｃｏｎｔｒｏ１．Ｈａｎｄｂｏｏｋ ｏｆＴｒｎｓｐｏｒｔａｔａｉｏｎ Ｓｃｉｅｎｃｅ，２００３，５６（３）：２４３－２７７． ［８］ Ｍｉｒｃｈａｎｄａｎｉ Ｐ，Ｈｅａｄ Ｌ．Ａ ｒｅａｌ－ｔｉｍｅ ｔｒａｆｉｃ ｓｉｆｇｎａｌ ｃｏｎｔｒｏｌ ｓｙｓｔｅｍ：Ａｒｃｈｉｔｅｃｔｕｒｅ，ａｌｇｏｒｉｔｈｍｓ，ａｎｄ ａｎａｌｙｓｉｓ．Ｔｒａｎｓｐｏｒｔａｔｉｏｎ Ｒｅｓｅａｒｃｈ Ｐａｒｔ ｃ：Ｅｍｅｒｇｉｎｇ Ｔｅｃｈｎｏｌｏｇｉｅｓ，２００１，９（６）：４１５－４３２． 【９］ Ｇｒｅｅｎｗｏｏｄ Ｄ，Ｂｕｒｄｉｌｉａｋ Ｂ，Ｔｒｅｎｃａｎｓｋｙ Ｉ，Ａｒｍｂｒｕｓｔｅｒ Ｈ，Ｄａｎｎｅｇｇｅｒ Ｃ．Ｇｒｅｅｎ ｗａｖｅ ｄｉｓｔｒｉｂｕｔｅｄ ｔｒａｆｆｉｃ ｉｎｔｅｒｓｅｃｔｉｏｎ ｃｏｎｔｒｏ１．Ｊｏｕｒｎａｌ ｏｆＡｕｔｏｎｏｍｏｕｓ Ａｇｅｎｔｓ ａｎｄ Ｍｕｌｔｉ—Ａｇｅｎｔ Ｓｙｓｔｅｍｓ，２００９，２（８）：１４１３－１４１４． ［１０］ Ｓｈｕａｉ Ｍ，Ｘｉｅ ＫＱ，Ｐｕ Ｗ，Ｓｏｎｇ ＧＪ，Ｍａ ＸＪ．Ａｎ ｏｎｌｉｎｅ ａｐｐｒｏａｃｈ ｂａｓｅｄ Ｏｉｌ ｌｏｃａｌｌｙ ｗｅｉｇｈｔｅｄ ｌｅａｒｎｉｎｇ ｆｏｒ ｓｈｏｒｔ－ｔｅｒｍ ｔｒａｆｆｉｃ ｆｌｏｗ ｐｒｅｄｉｃｔｉｏｎ．Ｉｎ：Ｐｒｏｃ．ｏｆｔｈｅ １６ｔｈ ＡＣＭ Ｉｎｔ’１ Ｃｏｎｆ．ｏｎ Ａｄｖａｎｃｅｓ ｉｎ Ｇｅｏｇｒａｐｈｉｃ Ｉｎｆｏｒｍａｔｉｏｎ Ｓｙｓｔｅｍｓ．２００８．４５－４５［ｄｏｉ：１０．１１４５／ １４６３４３４．１４６３４９０】 ［１ １］ Ｓｈｅｎ ＧＪ，Ｘｕ ＷＭ．Ｓｔｕｄｙ ｏｎ ｔｒａｆｉｃ ｔｆｒｕｎｋ ｄｙｎａｍｉｃ ｔｗｏ—ｄｉｒｅｃｔｉｏｎ ｇｒｅｅｎ ｗａｖｅ ｃｏｎｔｒｏｌ ｔｅｃｈｎｉｑｕｅ．Ｊｏｕｒｎａｌ ｏｆ Ｚｈｅｊｉａｎｇ Ｕｎｉｖｅｒｓｉｔｙ， ２００８，４２（９）：１６２５－１６３０（ｉｎ Ｃｈｉｎｅｓｅ ｗｉｔｈ Ｅｎｇｌｉｓｈ ａｂｓｔｒａｃｔ）．
