基于MAS的智能公交调度系统的建模与实现*

2014-09-14王向华陈特放

计算机工程与科学 2014年5期

关键词：公交站点调度

王向华，陈特放

(中南大学交通运输工程学院，湖南长沙 410013)

基于MAS的智能公交调度系统的建模与实现*

王向华，陈特放

(中南大学交通运输工程学院，湖南长沙 410013)

城市公共交通具有结构复杂、并发性和分布性等特点，使用数学建模的方法很难有效解决其调度问题，而多Agent系统MAS是一种解决复杂系统问题的有效方式，因此应用MAS来解决公交调度问题。首先，建立了城市公交系统的概念模型；然后，根据MAS的建模思想对公交调度相关实体进行抽象，建立了智能公交调度系统的MAS模型，并给出了Dispatch Agent、Bus Agent和Stop Agent的建模方法以及知识库的构建、推理和学习的流程；最后，完成系统实现。

MAS；智能公交调度系统；建模；JADE

1 引言

城市化作为重塑现代社会的三大力量之一[1]，在推动社会进步的同时，也带来交通拥堵的城市病。交通拥堵导致交通运输效益降低、市民出行困难、汽车燃料消耗增加和环境污染日益加剧。智能公交系统APTS(Advanced Public Transportation System)作为智能交通系统ITS(Intelligent Transportation System)在城市交通管理上的具体应用，被认为是解决城市交通拥堵的一种有效方式[2]。APTS是应用全球定位技术、无线通信技术、地理信息技术和计算机等技术，实现公交车辆运营调度的智能化和可视化，同时，为乘客提供完整的出行信息服务。然而，城市公共交通系统具有结构复杂性、并发性和调度方式多样性等诸多特点，很难有效解决其调度问题。目前，我国的公交调度智能化程度还很低，对公交车辆的调度还停留在两点一线上，对公交调度的应用研究还停留在静态公交调度时刻表编制、发车频率的优化上，这种方式并不能适应动态多变的公交运行情况。MAS(Multi-Agent System)具有很强的自治性和适应性，能处理不可预测的、动态改变的环境中的问题[3～6]。因此，将MAS技术引入到公交调度系统来解决公交调度问题，针对我国城市公共交通的特点，设计了一种基于MAS的城市公交智能调度系统，该系统具有良好的自适应能力，能根据外部环境的变化，对运行中的公交车辆进行动态调度和实时诱导，从而提高公交车辆的运行效益，减少交通拥堵。

2 Agent和MAS

Agent自Minsky在1986年提出以来，在人工智能&分布式人工智能AI&DAI(Artificial Intelligence& Distributed Artificial Intelligence)、分布计算、人机交互、计算机支持协同工作CSCW(Computer Supported Collaborative Work)、虚拟现实、数据挖掘以及软件工程等领域得到了很大的发展。虽然人们从社会智能、知识处理、拟人性等角度给予了Agent 不同的定义[4～6 ]，到目前为止学术界尚未给出有关 Agent 的统一而确切的概念。尽管不同领域对Agent 理解存在一定的区别，但大多数研究者都认为Agent 是一种计算实体(Entity)，它能够为了某个意图持续、自主地进行操作，具有学习能力并且与其它Agent 并存和相互作用；多个Agent通过相互协调合作而构成的系统就叫多Agent系统MAS, MAS的问题求解能力可以大于各个 Agent个体所具有的问题求解能力的简单相加。从本文所探讨的角度而言，Agent 代表的是存在于公交调度环境中的真实或抽象的实体，每个 Agent都能够主动、自治地活动，各Agent 可以在一定的环境中相互合作，共同完成公交运输调度服务。

3 城市公共交通的概念模型

城市交通系统是由人和交通工具等组成的动态复杂系统，具有影响因素多、开放性强、随机及不确定因素多等特点。根据城市公共交通的实际运行环境，设计出如图1所示的概念模型。

整个城市公共交通系统包括如下几个模块：(1)GPS导航监控系统；(2)3G无线网络信息支撑平台；(3)智能化的公交车辆系统； (4)智能化的站台系统；(5)交通指挥中心；(6)智能化的公交调度中心。其中涉及公交调度的主要有调度系统、智能公交车和智能站台这三部分。

Figure 1 Concept model of urban public transportation图1 城市公共交通系统的概念模型

4 基于MAS的公交调度系统建模

城市公交系统是由公交车辆、公交站点和调度中心等组成的复杂系统，具有随机性影响因素多、分布式和开放性等特点，用传统的方式很难对其进行有效的建模。而Agent是比对象更高一级的抽象，它是一个主动(Active)对象，有自己信念和意愿[4～6]，多个Agent可以相互合作，组成一个社会，可以解决单个Agent无法解决的问题。

基于MAS的建模是一种自下而上的建模方法，其建模流程如下：(1)识别系统中所有反映问题域和系统责任的Agent；(2)定义Agent的结构与特征，包括内部状态(数据、变量)和行为规则(函数、方法等)；(3)确定组成MAS的Agent群体所采用的体系结构，即Agent之间的通信与协调等问题。

Agent抽象的基本原则是：从系统的物理结构出发，围绕着系统的目标来对系统进行抽象。以系统的物理结构作为抽象的基本点，即根据物理世界的实际构成来划分Agent边界。根据这个抽象原则，将上节的调度系统中的实体抽象成为三个主要Agent，即Bus Agent、Stop Agent和Dispatch Agent。建立公交智能调度系统的MAS模型如图2所示。

Figure 2 MAS model of intelligent dispatch system图2 公交智能调度系统的MAS模型

为了满足车辆调度实时性的要求，对调度过程分解为实时发车和路上实时行车诱导，分别由Dispatch Agent和Bus Agent负责各自的任务。本系统中Dispatch Agent处于主导地位，它负责某一公交线路上与发车相关的调度操作，每次发车的同时将该车的Bus Agent 注册到MAS中；Stop Agent 负责站点客流量采集以及车辆到站时间预告；Bus Agent负责车辆满载率以及车辆在线路中运行的交通信息等数据的采集，Bus Agent之间协同合作完成公交车辆的动态诱导。

4.1 Dispatch Agent建模

Dispatch Agent 是整个公交调度系统的核心部分，是实现公交调度任务的主要承担者。由于调度需要大量的计算，因此采用慎思型Agent模型(BDI Agent), 该类模型具有信念(Belief，即情景模式)、愿望(Desire，即任务目标)、意图(Intention，即为实现愿望而想做的事情)和知识库的特点。针对公交调度的实际情况，设计的Dispatch Agent结构如图3所示。

Figure 3 Structure model of Dispatch Agent图3 Dispatch Agent 的结构模型

各部分的功能如下：

信念库：用于情景模式的设定，如上班早高峰、平常时段、下班早高峰、下班高峰、低谷时段、节假日以及季节、气温等模式的定义。

愿望库：即公交调度的任务目标，各情景模式下乘客期望的最少候车时间，这些数据可来源于问卷调查和行政指标；同时也有公交运营公司经济效益的要求。

意图库：即为各种调度方案，例如：A方案，每5分钟发车一趟；B方案，每3分钟发车一趟。

知识库：包括两部分，一部分是成功案例，一部分是推理规则即信念到意图的匹配原则。

本文采用产生式(Production Rule)规则来进行知识表示，其基本形式如下：

P→Q或 IFPTHENQ

其中，P是产生式的前提或条件，用于指出该产生式是否是可用的条件；Q是一组结论或动作，用于指出该产生式的前提条件P被满足时，应该得出的结论或应该执行的操作。由于产生式具有自然性、模块性、有效性、清晰性的优点，目前产生式表示法已成为人工智能中应用最多的一种知识表示方法。

Dispatch Agent的决策和自学习流程如图4所示。

Figure 4 Decision and study of the Dispatch Agent图4 Dispatch Agent 的决策和自学习流程

(1)成功案例存在情况(即情景模式匹配)：IF(春秋常日AND上班早高峰AND各站点客流量正常)THEN(选择A方案)。

(2)成功案例不存在情况：IF(春秋常日AND上班早高峰 AND 某站点客流量超量)THEN(根据超量程度，计算发车间隔)。这个案例完成后，进行效用评估，计算此次决策的乘客满意度和运营经济效益，并给该案例评估打分，如果满足要求则将该案例存入备选案例，当下次遇到同样的情景，则在备选方案上优化，多次优化之后，选择一个最优秀的方案存入成功案例库，这就是Dispatch Agent的学习过程。

4.2 Bus Agent建模

Bus Agent 是根据实际公交线路中公交车辆的驾驶行为而抽象出来的智能实体，能获取外界环境信息，并且拥有自己的知识和决策判断能力，可根据周围的环境变化实时调整自己的驾驶行为。由于公交车辆在线运行，需要的计算能力要求不高但实时性要求比较高，针对一些特定的紧急事件需要进行快速反应，因此Bus Agent采用混合型Agent模型，如图5所示。该模型是在慎思型Agent结构的基础上增加了快速反应功能。

Figure 5 Structure model of the Bus Agent图5 Bus Agent 的的结构模型

各部分的功能如下：

信念库：用于公交车辆行驶模式的设定，如跟车模型、超车模型以及让车模型等的定义。

愿望库：即本次行车的任务目标，发车时从Dispatch Agent处获得，本文主要指本车到达各站点的预定时间以及与前车到站时间间隔，其中保证公交车辆到站时间的先后间隔是防止串车和大间隔的关键。

意图库：即为各种行驶模式的具体行驶操作，例如：方案A，加速；方案B，减速。

反应器：用于对一些紧急事件的处理，例如：车辆故障等需要进行应急处理的情况。

其知识库的构建、推理和学习流程和Dispatch Agent类似。

4.3 Stop Agent建模

由于Stop Agent的功能比较简单，只需要采集客流量、交通状况等信息，再根据公交的运行情况，发布公交到站信息，不需要知识也不需要推理，因此采用带状态的反应型Agent模型。其模型结构如图6所示。

Figure 6 Structure model of Stop Agent图6 Stop Agent 的结构模型

其行为主要有两个：一个是定时驱动的，查询某线路将到达车辆的信息，更新到达时间；另外一个是事件驱动，当车辆到站上下车服务完成后，更新自己的站点客流量信息。

5 基于MAS公交调度系统的实现

5.1 Agent之间的通信语言选择

Agent之间常见的通信语言主要有两种，一种是KQML(Knowledge Query and Manipulation Language)；另一种是FIPA(Foundation for Intelligent Physical Agents)[7]协会制定的FIPA-ACL (Agent Communication Language)。FIPA-ACL在构建新的原语方面具有很强的能力，而且FIPA-ACL的开发者可通过语义语言SL(Semantic Language)形式语言来表示一个Agent的信念、愿望和意图，以及这个Agent执行的动作。本文采用FIPA-ACL作为Agent之间的通信语言。

一个通信实例：

(inform

:sender DispatchAgent1

:receiver BusAgent2

:content Bus schedule

:language SL

)

DispatchAgent1调度Bus2发车时，将Bus2的发车时刻以及预计到达在各站点的时刻表发给BusAgent2，按时刻表运行就是Bus Agent运行的意图。

5.2 MAS中各Agent之间协作模式的选择

由于Agent之间信念、目标不同或者同时共享有限资源都有可能造成冲突，因此我们需要采用一种协调的方式来消除冲突。MAS中Agent的协作模式主要有合同网、市场机制以及黑板模型等几种。

本文选择黑板模型，其基本思想是：黑板是一个共享的问题求解工作空间，各Bus Agent都能看到黑板。当问题和初始数据记录到黑板上，如前方站点客流量信息，求解开始，即将到来的Bus Agent通过看自身状态(当前满载率)和知识推理一个解决方法，当它无法解决时，由其后方的Bus Agent继续求解，重复这一过程直到问题彻底解决，获得最终结果。

下面是一个基于黑板模型的超车实例：

提出问题：站点i，提出问题，本站客流量。

求解过程：Bus Agentj，根据本车状况(满载率等)，查询知识库，能否满足站点的运输任务，能则答复ok，否则答复no。

Bus Agentj+1，查看到前车的答复为no，根据本车状况能否满足站点的运输任务，能则答复ok，同时和前车协商，发出超车信号。

结果：超车完成后，i、j的位置信息互换，信念更新。每一趟车过站后，Stop Agent更新状态信息。

5.3 开发工具的选择

本文选择TILAB(Telecom Italia LAB)发布的开放源代码软件JADE(Java Agent Development Framework)[8]作为公交调度系统的开发工具。

JADE是一个纯Java实现的符合FIPA智能体规范的MAS软件开发框架，它提供了与FIPA兼容的Agent平台与开发Agent的软件包。

公交调度系统是一个分布式的系统，Dispatch Agent运行在调度中心的服务器上，Bus Agent运行在车载JVM上，Stop Agent则运行在电子站牌的JVM上。使用JADE可以方便快捷地进行系统的开发和部署。

5.4 公交调度系统体系结构

公交调度系统的体系结构如图7所示。

Figure 7 Architecture of bus dispatch system图7 公交调度系统的体系结构

包括如下三层：

(1)硬件层。包括硬件及其上运行的Java虚拟机JVM(Java Virtual Machine)。

(2)JADE平台层。一个平台可以有多个容器，而且这些容器可以分布在不同的主机上，在一个平台中，有且仅有一个主容器，当其他的容器启动时，必须在主容器中注册。

(3)Agent应用层。由容器上运行的各种Agent应用组成，AMS(Agent Management System)、DF(Directory Facilitator)是主容器中运行的特殊Agent，分别提供Agent管理和黄页服务，Dispatch Agent、Bus Agent、Stop Agent以及Interface Agent都在这一层运行。

6 结束语

交通系统是由道路、交通车辆、人以及相关设备等组成的动态复杂的系统，MAS理论的出现和发展为交通系统调度的研究提供了一种新的思路和方法，尽管将MAS技术引入智能交通系统进行仿真研究早就有了。但是，将MAS计算用于现实应用还少有成功案例，将MAS用于解决智能公交调度的现实问题是本研究的一种新的探索。

本文研究的基于MAS的智能公交调度系统具有一定的自适应和自学习能力，其采用自然建模的方式能较好地解决公交调度模型的抽象和表示，比传统的数学建模方式具有更好的灵活性和适应性；将调度任务分解并由分布环境中不同的Agent来完成各自的任务，比集中式的调度方式具有更好的准确性和鲁棒性。

[1] Borja J, Castells M. Local and global management of cities in the information age[M]. London:Earthscan, 1997.

[2] Yang Zhao-shing. Theories and methods of urban intelligent public transportation system[M]. Beijing:China railway Publishing House,2004. (in Chinese)

[3] Yao Jun,Lü Zhi-lin,Ye Yan.Model for bus dispatching based on satisfaction[J].Journal of Transport Information and Safety, 2009,27(4):67-69. (in Chinese)

[4] Mao Xin-jun, Hu Cui-yun, Sun Yao-kun, et al. Research on agent-oriented programming[J]. Journal of Software, 2012,23(11):2285-2904. (in Chinese)

[6] Wooldridge M. An introduction to multi-agent systems[M]. United Kingdom:John Wiley & Sons Ltd,2009.

[7] Foundation for intelligent physical agents, FIPA application specifications[EB/OL].[2013-03-02]. http://www.fipa.org/repository/applicationspecs.php.

[8] Java agent development framework[EB/OL]. [2013-03-28].http://jade.tilab.com/.

附中文参考文献:

[2] 杨兆升.城市智能公共交通系统理论与方法[M]. 北京:中国铁道出版社,2004.

[3] 姚俊，吕智林，叶嫣.基于满意度的公交车调度模型研究[J].交通信息与安全,2009,27(4):67-69.

[4] 毛新军，胡翠云，孙耀坤，等.面向Agent程序设计的研究[J].软件学报,2012,23(11):2285-2904.

WANGXiang-hua,born in 1979,PhD candidate,his research interests include software engineering，and intelligent transportation.

陈特放(1957 -),男,湖南涟源人，博士，教授，研究方向为铁路运输、自动化技术和智能交通。E-mail:ctfcyt@163.com

CHENTe-fang,born in 1957 ,PhD,professor,his research interests include railway transportation, automation technology, and intelligent transportation.

ModelingandimplementationofintelligentbusdispatchsystembasedonMAS

WANG Xiang-hua，CHEN Te-fang

(School of Transportation Engineering,Central South University,Changsha 410013,China)

Urban public transportation system features complex structure,concurrent processing and diversity, so it is difficult to solve the dispatching problem effectively.MAS is an effective method to solve complex system problems so that it is used to solve the bus dispatching problem.Firstly, a system framework of intelligent bus dispatch system is designed.Secondly,a MAS model is abstracted from the intelligent bus dispatch system framework,and the modeling method of dispatch agent, bus agent and stop agent is introduced,and the process of construction, reasoning,and learning of knowledge base. Finally,the system is implemented.

multi-agent system;intelligent bus dispatch system;modeling;JADE

1007-130X(2014)05-0986-05

2013-03-13;

：2013-07-05

国家自然科学基金资助项目(60674003)

TP182

：A

10.3969/j.issn.1007-130X.2014.05.033