Brief Report

NOVEMBER/DECEMBER 2011 1541-1672/11/$26.00 © 2011 IEEE 77 Published by the IEEE Computer Society

I N T E L L I G E N T T R A N S P O R T A T I O N S Y S T E M S Editor: Lefei Li, Tsinghua University, [email protected]

Ag ent Recommendation for Agent-Based Urban- Transportation Systems

Cheng Chen and Shuang Shuang Li, Chinese Academy of Sciences Bo Chen, Michigan Technological University Ding Wen, National University of Defense Technology

The characteristics of mobile agents, such as au- tonomy, mobility, and adaptability, make them a good candidate for a traffi c management system because they can deal with the changes and un- certainty in dynamic traffi c environments.1 A re- view of agent-technology applications in traffi c and transportation systems shows that intelligent agent techniques and methods have been applied to many aspects of traffi c and transportation sys- tems, including modeling, simulation, dynamic routing, congestion management, and intelligent traffi c control.2 Although researchers in the fi eld have made signifi cant efforts in applying agent technology in traffi c and transportation systems, little research has looked at the dynamic selec- tion of the most appropriate control agent to cope with specifi c traffi c states in urban transportation systems.

To address this problem, we proposed a recom- mendation platform to integrate with an agent- based distributed and adaptive platform for trans- portation systems (Adapts) to provide an agent recommendation service.3 Adapts is one of the major components of parallel transportation man- agement systems (PtMS).4,5 The proposed recom- mendation system selects the most suitable con- trol agent to meet dynamic traffi c-management demands based on the control agent’s applicable environment and functions.

Agent-Recommendation Platform The agent-recommendation platform we present here is a subsystem in the Adapts organization layer. Figure 1 shows the architecture of the rec- ommendation platform and its interactions with Adapts, real-world traffi c systems, traffi c strategy developers, and traffi c managers. The platform consists of three subsystems (the performance- analysis system, traffi c-state forecasting system, and the agent-recommendation system), two data- bases (the traffi c-control agent database and traffi c- state database), and two servers (the traffi c-strategy server and systematic-state server).

Newly developed traffi c strategies are submitted to the traffi c-strategy server. Each traffi c-control strategy is implemented in a control agent, and all the control agents are stored in the traffi c-control agent database. The control agents are evaluated by the performance analysis system based on cer- tain evaluation rules. The performance-analysis system includes an artifi cial transportation system (ATS),6 which uses real traffi c data in the traffi c- state database to mimic real-world urban-traffi c scenarios. The real-time traffi c data are continu- ously collected by the sensor networks from the actual transportation systems. These traffi c data are also used by the traffi c-state forecasting sys- tem to predict the future states of the actual trans- portation system and for the systematic-state server to respond to the queries issued by the traf- fi c managers.

The role of the traffi c-state forecasting sys- tem is to counteract the infl uence of the trans- mission delays in the management system and

The agent computing paradigm has been de-veloping rapidly over the last few decades and is becoming one of the powerful technologies

in the development of large-scale complex systems.

IS-26-06-Its.indd 77 11/9/11 6:05 PM

78 www.computer.org/intelligent IEEE INTELLIGENT SYSTEMS

prevent the appearance of a large fluctuation of the traffic states. When the forecasting system pre- dicts the deterioration of a traffic state, the management system’s con- trol demand will be adjusted based on the new traffic state. A different control agent is then recommended to the hierarchical traffic-manage- ment system. This new control agent will be the most suitable agent for the new control demand based on the performance analysis system’s evaluation.

Agent Recommendation The goal of the agent-recommendation system is to determine the most suit- able control agent for a specific traf- fic state to achieve desired control objectives. The control agent includes two selection criteria. The first crite- rion is to check if a control agent is applicable to the traffic-control envi- ronment. The second criterion is to evaluate a control agent’s effective- ness to meet the demand of traffic management. To introduce the rec- ommend mechanism in detail, we first

define various traffic-management demands and the modeling of a con- trol agent.

Traffic-management demand Traffic management demands vary with the traffic environment’s state. Table 1 shows the traffic-management demands for the congestion, normal, and unobstructed traffic states. In the congestion state, a traffic-management system’s most important objective is to avoid a long waiting time or vehi- cle queue. Hence, the goal is to bal- ance the vehicle queue in all links of an intersection. In the normal state, a traffic-management system tries to shorten the travel time as much as possible. As a result, the average delay time is given the highest priority.

In the unobstructed state, there are only a few cars on the road, so it is

Figure 1. The architecture of the recommendation platform and its interactions with the traffic-management system and the real-world transportation system.

Traffic managers

Traffic-strategy developers

Hierarchical traffic-management

system

Transportation systems

Sensor networks

Traffic-control agent database

Recommendation system for control

agent Traffic-state database

Traffic-state forecasting systemSystematic

state server

Performance-analysis system for control agent

Co nt

ro l a

ge nt

s

D et

ec to

r d at

a

Traffic-strategy server

Table 1. Mutative demand of traffic management.

State of traffic environment Traffic-management demand

Congestion Balance of vehicle queue

Normal Low average delay time

Unobstructed High one-time pass rate

IS-26-06-Its.indd 78 11/9/11 6:05 PM

NOVEMBER/DECEMBER 2011 www.computer.org/intelligent 79

hard to shorten the travel time by ad- justing the control mode. In this case, we pay special attention to the energy consumption of the transportation. The high one-time pass rate is cho- sen as the demand of the traffic man- agement system to reduce the num- ber of times vehicles must restart in intersections.

Once the traffic-management de- mands at different traffic states are defined in a computer, the aims of a traffic-management system are inter- preted in a way that can be under- stood by the computer. These mea- surable traffic management demands are then used by the recommendation system for dynamic agent selection.

Agent Modeling For most existing traffic management systems, a control agent usually acts as the carrier of traffic-control algorithms or strategies.7–10 The control agent’s architecture includes two major com- ponents: the environmental-interaction module and the algorithm module (see Figure 2a). The environmental- interaction module’s main function is to allow a control agent to exchange information with the outside world. The algorithm module is a core mod- ule that processes traffic information and performs decision making.

This type of agent structure is called an algorithm-centric structure. In ad- dition to the environmental-interaction module and the algorithm module, an algorithm-centric traffic-control agent might also include modules such as a routing module for mo- bile agents. From the traffic-control point of view, there is no difference between a traffic-control agent and the control algorithms wrapped by the agent. As a result, the perfor- mance evaluation of a control agent is the same as the evaluation of con- trol algorithms carried by the agent. The typical measures of effectiveness

(MOEs) of a control agent include av- erage speed, average delay time, one- time pass rate, and so on.

Although an algorithm-centric con- trol agent can provide basic functions for traffic control and the interactions with traffic systems, additional char- acteristics are needed to achieve auton- omy. An autonomous agent is defined as a system within and part of an en- vironment that senses the environment and acts on it over time, in pursuit of its own agenda, to affect what it senses in the future.11 According to this defi- nition, an autonomous agent should be reactive, autonomous, goal-oriented, and temporally continuous. The Belief- Desire-Intention (BDI) software model is a good fit for implementing these prop- erties in a software agent.12 Figure 2b shows the architectural components of a BDI control agent, which includes three major components: beliefs, de- sires, and intentions.

Beliefs. In a BDI model, an agent’s be- liefs represent the information about its world. The beliefs of a traffic- control agent include the applicable operating environment and real-time environmental information. The first part is predefined for a specific con- trol agent where it can be applied. It includes the information of the ap- plicable intersections (the type of in- tersections or their traffic state), the minimum operational requirement,

the traffic-management system archi- tecture, and so on.

The second part represents the real- time traffic information perceived by a control agent and the communi- cation of this agent with other sys- tem components. It includes detector data (the traffic-flow data), agent- coordination information, the state of the entire traffic-management sys- tem, and the agent’s internal state.

Desire. The desires represent a BDI agent’s motivational state. It reflects the goals of a control agent. The de- sires of a traffic-control agent can have single, multiple, or subperiod objectives. These objectives corre- spond to the reference indexes of the MOEs. A control agent’s desires can be a single index or a combination of multiple indexes of the MOEs for the applied intersection or area. We expand MOEs to include some new indexes, such as the balancing vehi- cle queue in all links of an intersec- tion. The objectives of a control agent are used as the evaluation indexes in the performance analysis. We assume that a control agent with desires that match the control objectives will per- form better compared to others.

Intentions. Intentions are desires that an agent has chosen to achieve by exe- cuting plans. This component describes the details of the process an agent uses

Figure 2. Two types of agent models for control agents. (a) The control agent’s architecture includes the environmental-interaction and the algorithm module. (b) The BDI control agent includes three major components: beliefs, desires, and intentions.

Other modules: Routing strategy,

Internal state sets, Knowledge database

Algorithm-centric traffic-control agent

BDI traffic-control

agentControl algorithm

Routing strategy

Desires

Beliefs Intentions

Environmental-interaction module

Traffic environment (detectors, traffic lights, other agents, ...)

(a) (b)

IS-26-06-Its.indd 79 11/9/11 6:05 PM

80 www.computer.org/intelligent IEEE INTELLIGENT SYSTEMS

in pursuit of its certain desires. A traf- fi c-control agent’s plan is a sequence of operations defi ned by control al- gorithms. This component provides a mechanism for a control agent to act on the environment where it resides.

With a BDI model, a traffi c-control agent’s goal-oriented characteristic can be implemented with the three components we discussed earlier. The performance evaluation of a con- trol agent is based on an agent’s be- liefs and desires rather than several fi xed indexes of the MOEs. In addi- tion, only those agents with an ap- plicable operation environment and performance indexes that match the state of traffi c environment and the traffi c-management demands will be evaluated. For example, a control agent designed to handle the state of congestion on a ramp will not be evaluated for the traffi c control at a crossroad in the normal state. This approach allows more effi cient and better-targeted performance analysis of control agents.

Recommend Mechanism The recommendation system selects the most suitable control agent for a traffi c-management system by scoring control agents through a two-stage fi ltering process. The most suitable agent has the highest score among the agent candidates. Let Si denote the score of the ith agent. The value of Si is equal to S1i � S2i, where S1i is the agent score assigned from the fi rst fi l- tering stage and S2i is from the second fi ltering stage. In the fi rst stage, the actual environment is compared with the assumption and modeling of the applicable environment of a control agent defi ned in the beliefs compo- nent. The agent score in the fi rst stage only has two possible values: 0 or 1. If the agent-applicable environment matches the actual environment, the value 1 is assigned to S1i; otherwise,

0 is assigned to S1i. The same scoring rule also applies to the comparison of the management system’s demand and the control agent’s desire. If the desire module does not contain the man- agement system’s demand, the value of S1i is set to 0; otherwise, it is set to 1. If the value of S1i of a control agent is equal to 1, it will enter into the second fi ltering stage.

The second stage will score the agent’s control effectiveness based on its performance report obtained from the performance-analysis system. A control agent’s performance index can be a single index or multiple

indexes. For each index, the perfor- mance of all the agents is normalized to the best performance. The value of S2i for a control agent can be ex- pressed as follows:

S s wi ij j2 2= ∗∑ where s2ij is the normalized perfor- mance of the control agent i on the jth performance index and wj is the weight of the jth performance index. After these two stages, the most suit- able control agent is the one with the highest score. This agent will be recommended for the traffi c man- agement by the recommendation system.

The agent recommendation mech- anism and platform we present here provide a guideline to enable dy- namic selection of the most appro- priate control agents for a specifi c traffi c state in urban-transportation systems. With this recommendation platform, newly developed or legacy traffi c-control algorithms can be dy- namically incorporated into existing traffi c-management systems through mobile agent technology and the rec- ommendation system ensures that the deployed control agent has the best performance for a specifi c traffi c- management demand among avail- able control agents. Future work will focus on the integration of this rec- ommendation platform into real- world traffic-management systems and the further development of a performance-analysis system to in- clude more performance indexes and evaluation rules.

Acknowledgments This work is supported partly by the Na- tional Natural Science Foundation of China (NSFC) under grants 70890084, 60921061, and 90920305 and the Chinese Academy of Sciences (CAS) under grants 2F09N05, 2F09N06, 2F10E08, and 2F10E10. We also thank the people who contributed to this work in the CAS State Key Laboratory of Manage- ment and Control of Complex Systems.

References 1. Z-.J. Li, C. Chen, and K. Wang, “Cloud

Computing for Agent-Based Urban Transportation Systems,” IEEE Intel- ligent Systems, vol. 26, no. 1, 2011, pp. 73–79.

2. B. Chen and H.H. Cheng, “A Review of the Applications of Agent Technology in Traffi c and Transportation Systems,” IEEE Trans. Intelligent Transporta- tion Systems, vol. 11, no. 2, 2010, pp. 485–497.

3. F.-Y. Wang, “Agent-Based Control for Networked Traffi c Management

Our goal is to enable dynamic selection of the most appropriate control agents for a specifi c traffi c state in urban- transportation systems.

IS-26-06-Its.indd 80 11/9/11 6:05 PM

NOVEMBER/DECEMBER 2011 www.computer.org/intelligent 81

Systems,” IEEE Intelligent Systems, vol. 20, no. 5, 2005, pp. 92–96.

4. F.-Y. Wang, “Parallel Control and Man- agement for Intelligent Transportation Systems: Concepts, Architectures, and Applications,” IEEE Trans. Intelligent Transportation Systems, vol. 11, no. 3, 2010. pp. 1–9.

5. F.-Y. Wang, “Toward a Revolution in Transportation Operations: AI for Complex Systems,” IEEE Intelligent Systems, vol. 23, no. 6, 2008, pp. 8–13.

6. F.-Y. Wang and S. Tang, “Artificial Societies for Integrated and Sustainable Development of Metropolitan Systems,” IEEE Intelligent Systems, vol. 19, no. 4, 2004, pp. 82–87.

7. B. Chen, H.H. Cheng, and J. Palen, “Integrating Mobile Agent Technology with Multi-agent Systems for Distrib- uted Traffic Detection and Management Systems,” Transportation Research Part C: Emerging Technologies, vol. 17, no. 1, 2009, pp. 1–10.

8. B.P. Gokulan and D. Srinivasan, “Dis- tributed Geometric Fuzzy Multiagent Urban Traffic Signal Control,” IEEE Trans. Intelligent Transportation Systems, vol. 11, no. 3, 2010, pp. 714–727.

9. D. Srinivasan, M.C. Choy, and R.L. Cheu, “Neural Networks for Real-Time Traffic Signal Control,” IEEE Trans. Intelligent Transportation Systems, vol. 7, 2006, pp. 261–272.

10. P.L. Gregoire et al., “Urban Traffic Control Based on Learning Agents,” Proc. 2007 IEEE Intelligent Transpor- tation Systems Conf., IEEE CS Press, 2007, pp. 916–921.

11. S. Franklin and A. Graesser, “Is it an Agent, or just a Program?: A Taxonomy for Autonomous Agents,” Proc. 3rd Int’l Workshop on Agent Theories, Architectures, and Languages, Springer- Verlag, 1996, pp. 21–35.

12. A.S. Rao and M.P. Georgeff, “BDI- Agents: From Theory to Practice,” Proc. 1st Int’l Conf. Multiagent Sys- tems (ICMAS), 1995.

Cheng Chen is a PhD student at the State Key Laboratory of Management and Control for Complex Systems, Chinese Acad- emy of Sciences. Contact him at chengchen. [email protected].

Shuang Shuang Li is a PhD student at the State Key Laboratory of Management and Control for Complex Systems, Chinese Academy of Sciences. Contact him at [email protected].

Bo Chen is an assistant professor in the Depart- ment of Mechanical Engineering – Engineering

Mechanics and the Department of Electri- cal and Computer Engineering at the Mich- igan Technological University. Contact her at [email protected].

Ding Wen is a professor in the Center for Military Computational Experiments and Parallel Systems Technology at the National University of Defense Technology, China. Contact him at [email protected].

Selected CS articles and columns are also available for free at

http://ComputingNow.computer.org.

Focus on Your Job Search

IEEE Computer Society Jobs� OLSWZ� `V\� LHZPS`� ÄUK� H�UL^� QVI� PU� 0;��ZVM[^HYL�KL]LSVWTLU[��JVTW\[LY�LU- NPULLYPUN�� YLZLHYJO�� WYVNYHTTPUN�� HYJOP[LJ[\YL�� JSV\K� JVTW\[PUN�� JVUZ\S[PUN�� KH[HIHZLZ�� HUK� THU`� V[OLY� JVTW\[LY�YLSH[LK�HYLHZ�

New feature:�-PUK�QVIZ�YLJVTTLUKPUN�VY�YLX\PYPUN�[OL� 0,,,�*:�*:+(�VY�*:+7�JLY[PÄJH[PVUZ�

Visit www.computer.org/jobs to search technical job openings, plus internships, from employers worldwide.

http://www.computer.org/jobs

;OL�0,,,�*VTW\[LY�:VJPL[`�PZ�H�WHY[ULY�PU�[OL�(07�*HYLLY�5L[^VYR��H�JVSSLJ[PVU�VM�VUSPUL�QVI�ZP[LZ�MVY�ZJPLU[PZ[Z��LUNPULLYZ��HUK�JVT- W\[PUN�WYVMLZZPVUHSZ��6[OLY�WHY[ULYZ�PUJS\KL�7O`ZPJZ�;VKH �̀�[OL�(TLYPJHU�(ZZVJPH[PVU�VM�7O`ZPJPZ[Z�PU�4LKPJPUL��((74���(TLYPJHU� (ZZVJPH[PVU�VM�7O`ZPJZ�;LHJOLYZ��((7;���(TLYPJHU�7O`ZPJHS�:VJPL[`��(7:���(=:�:JPLUJL�HUK�;LJOUVSVN �̀�HUK�[OL�:VJPL[`�VM�7O`ZPJZ� :[\KLU[Z��:7:��HUK�:PNTH�7P�:PNTH�

IS-26-06-Its.indd 81 11/9/11 6:05 PM