基于MDP的多智能体交通信号灯控制的设计与研究

蒋耀基

摘要：智能交通系统作为21世纪交通运输体系的发展方向，受到了世界各国的广泛重视，它是解决现代交通拥挤、有效提高道路利用率的有效途径。通常的智能交通系统未能很高效的解决交通堵塞问题，但多智能体系统是人工智能学科的一个新兴热门研究领域，本文提出了用多智能体系统解决交通主干道信号灯的配饰系统，从而提高了车辆通行效率。

针对路口信号灯配时优化问题，本研究提出一种采用多智能体协作求解问题的分布式方法，并将信号灯配时优化问题建模成最优约束满足问题（OCSP）进行求解。这使得单个路口的优化运算量大大下降，处理实际交通中的实时动态情况的能力得到提高，获得了较为显著的优化效果。由于采用了分布式求解，系统的稳定性也得到了保证。

1、智能体的协作关系建立

根据实际道路的特点不难发现，任意路口的到达车辆是通过该路口的相邻路口放行所产生的，我们将这些路口的“邻居”称为邻接路口。显然，如果邻接路口的放行策略不得当，使得路口车辆的到达率超过了路口的流出率，就会产生拥堵。为了避免路口拥堵现象的产生，路口智能体之间必须进行适当的“交流与协作”，控制各个路口做出合适的信号灯决策。

（1）主干道路口节点之间的逻辑关系网络建立

多智能体系统协作控制的基础是个体智能体之间的逻辑网络关系。既然我们将实际道路网中的路口抽象成智能体网络拓扑结构的节点，那么将路口之间的物理连接关系抽象成网络拓扑结构的边，即可形成了路口智能体节点的通信基础。

我们通过示路口节点智能体之间的逻辑网络关系。针对路口智能体网络中的任一节点用集合来表示与路口节点的“邻居”，其中每一个元素代表一个与逻辑相连的路口节点，由此不难得出：代表邻接节点数目（即是“边”数），当然正常情况下，对于实际道路，与节点相邻接的节点数一般为3或4个。

路口智能体节点之间完成了逻辑关系网络的建立之后，将具备一定的信息共享能力，为路口智能体节点之间协作，提供数据基础

（2）信号灯优化问题的求解

根据之前对于问题的描述及建模可知，我们将整个城市主干道路口设计为一个多智能体系统，每个路口拥有一个智能体节点，那么，可以将路口的各个车道的放行优化控制看作是单个智能体（Agent）占用资源求解问题。根据交通运行的特点，我们可以将任意路口的各个车道放行优化问题应用于最优约束满足问题（DCSP）框架下进行求解。

在本优化方案中，我们将最优约束满足问题分成两个部分：

1.获得满足约束条件的解全集；

2.通过适当的方式从解的全集中选取最优解。

2、通过MDP决策寻找最优解

在完成了问题的建模，获得了约束满足的解全集以后，就将进行最重要的环节——寻找信号灯配时优化问题的最优求解。随着人工智能技术的不断发展，产生了很多寻找最优解的模型，较为典型的有 BDI，MDP 等。结合城市主干道路口信号灯配时优化问题的特点，由于问题的初始状态S（即是原始车辆数目），可以通过传感器实时获取，同时信号灯的决策行为具有无后效性，即是其只取决于当前状态，不受之前状态的影响，因此选取 MDP 决策模型来作为寻找最优解的方案较为合适。MDP 决策模型（马尔可夫决策模型）包括：1.初始状态 S；2.行为方案集合 A；3.效用函数R（s，a）；4.转移模型T=表示 S 状态通过行为方案 A达到了新的状态S。

根据MDP的数学模型，结合本系统：初始状态S即是各自车道的初

始车辆数目；系统的行为A即是各自执行智能体的动作；转移模型 T=，即是各个执行智能体的运算过程；效用函数R即是根据执行智能体的独立计算，选取能使下个时刻路口车辆数目最少的行为。决策时序模拟图如下图3-3所示：

3、配时优化系统的智能体系统建立

在完成了信号灯配时优化系统的工作平台搭建以后，就将进行配时优化系统的本质——智能体系统的建立。为了使路口智能体系统之间能够达成协作，实现信号灯配时优化，本系统将在每个路口节点上，将设置一个智能体系统，并进行分层，具体划为：管理智能体与执行智能体两类：

整个系统的运行流程，定时获取所有邻接路口的各车道车辆数目情况；路口管理智能体通过邻接路口共享的车辆数目信息，对邻接路口将要作出的信号灯决策进行预估，并通过预估的结果，计算获得自身路口各个车道的输入车辆数目；路口各个车道对应的执行智能体，均以自身控制的车道信号灯为绿灯为前提，通过交叉冲突规则，生成各自的交叉冲突列表并比照交叉冲突列表，将产生冲突的车道对应的信号灯设置为红灯；管理智能体收集所有执行智能体各自运算出的下个时刻路口车辆总数，选取数目最小的结果所对应的车道，设置此车道对应信号灯为绿灯，再比照此车道的交叉冲突列表，将导致交叉冲突的车道信号灯设置为红灯，其余为绿灯，生成信号灯决策结果。

4、结论

将城市交通主干道问题进行了抽象描述，并用建立了路口的数学模型，根据智能体间的协作关系，建立了主干道路口节点间的逻辑网络关系，并通过信号灯的约束满足问题进行信号灯控制求解，通过 MDP 决策算法进行解的最优化处理，在理论上实现了多智能体协作控制城市主干道信号灯。

参考文献：

[1]Nationwide Personal Transportation Survey. US Department of Transportation .1980Vergil G.Stover and Frank J.Koepke. Transportation and Land Development.Institute ofTransportation Engineers. Washington DC.1998

[2] 王煒，过秀成，交通工程学.南京：东南大学出版社，2000

[3] 全永，城市交通控制.北京：人民交通出版社，1989

[4] 何显慈等，交通系统工程.武汉：华中理工大学出版社，1989

[5] Wooldridge M， Dunne P E，On the computational complexity of coalitional resource games.Artilicial Intelligence， 2006， 170：835-87