日本ソフトウェア科学会第 36 回大会 (2019 年度) 講演論文集

Negotiation Protocol in Traﬃc Routing forPriority Vehicle
Krishna Priawan Hardinda, Yuichi Sei, Yasuyuki Tahara, Akihiko Ohsuga
自己適応システムは，ソフトウェアの複雑さを管理するアプローチの 1 つとして提案されている．経路作成問題は，
マルチエージェントシステムとしてモデル化できる複雑なソフトウェアの 1 例である．経路作成問題は，多くの場
合，不確実性に伴う課題を有する．道路の閉鎖，システムの障害，および目的地の変更は，そのような課題の例である．本論文では，優先車両に関連する経路作成問題で発生した課題を提示する．そのためにまず，実行時の不確実性を表すシナリオにおいて課題を定義する．次に，実験中に発生した問題に対処するためのネゴシエーションプロトコ
ルを提案する．都市部の現実的な交通状況を描写した交通シミュレーターを使用して実験を行い，適応のための計画
を交通管理システムが実施することにより適応を実行する．

The self-adaptive systems have been proposed by researchers as one of the approaches to manage the complexity of the software. The traﬃc routing is an example of complex software which can be modeled as amulti-agent system. The traﬃc routing often raises several problems that require a solution to tackle theuncertainties. Road closure, failures in systems, and destination changes are a few illustrations for problems
in traﬃc routing. In this paper, we present the problems occurred in traﬃc routing related to priority
vehicle. We deﬁne the problem with a number of scenarios which express the uncertainties during the runtime. Then, we propose our negotiation protocol to address the issues occurred during the experiments. We
conduct the experiments by using traﬃc simulator that portrays realistic traﬃc situation in the urban area,
then apply the adaptation plan to its traﬃc controller to adapt the adaptation plan.

self. Furthermore, self-adaptive systems have an

1 Introduction

ability to organize themselves with speciﬁed goals

The complexity of current software systems hasin advance without conscious awareness from thebrought a challenge for the researcher to be able tousers [1, 2].

manage the software in a proper way. There are

A self-adaptive system also comprises of several

several existing approaches to tackle these prob-

capabilities that support the system to achieve thelems, one of those is a self- adaptive system. Self-

goals. Those capabilities are often called as self-

adaptive systems can manage the complexity by* properties.

building more self- managed systems that trans-

conﬁguration (automatically reconﬁguring itself

forming complexity from users to the software it-when components are changed); self-optimization

The following properties are self-(constantly tuning the parameter for optimization);
優先車両の経路作成における交渉プロトコル
This is an unrefereed paper. Copyrights belong to
the Authors.

Krishna Priawan Hardinda, Yuichi Sei, Yasuyuki
Tahara, Akihiko Ohsuga, 電 気 通 信 大 学 大 学 院 情
報 理 工 学 研 究 科, Graduate School of Informatics and Engineering, The University of ElectroCommunications.

self-healing (recover from the failures); and selfprotection (protect from external attacks) [1].
Considering the capabilities of the self- adaptive
systems, it is believed that the self- adaptive systems can do automation to reconﬁguring itself in
response to changes in the environment during theruntime [2]. The core concept of self-adaptive sys-of smart cyber- physical systems requires a decen-tems relies on adaptation logic that implements a

tralized approach to handle uncertainties between

feedback structure: MAPE (Monitoring Analyzing

independent system agent. We focus on speciﬁc

Planning Execute) model.

priority vehicle, the ambulance since it carried a

One of the real problems that depict the complex-

critical mission and required fast response. In ad-

ity of software is traﬃc systems. The implementa-

dition, the ambulance has multiple goals to be sat-tion of self-adaptive systems is applicable to thisisﬁed that often has a conﬂict between other agents

problem since traﬃc systems contain numbers of(other vehicles).

large agents, limited information and large numbers

To tackle those issues, we propose an adaptationof uncertainties [4]. Speciﬁcally, the problem thatpolicy in our approach. Our approach comprises ofis used in [4], Automated Traﬃc Routing Problem

three policies: removing obstacles, overriding traf-(ATRP), has demonstrated the needs of self- adap-

ﬁc controller, and information sharing. Each policy

tive approach to tackle the problem. Then withis incorporated with MAPE feedback loop [2] suchtheir proposed approach, the problem was solvedthat actualize the concept of self- adaptive in thewith a solution and later its solution was evaluatedapproach.

along with a set of comparable dimensions.

The purpose of this paper can be elaborated into

However, the scenarios in ATRP related to pri-at least three points. Achieving the main goal ofority vehicles such as ambulance remain. To thethe ambulance: arrive at the target location of thebest of our knowledge, existing research papers thatpatient and then travel to the hospital as soon as

address this issue are limited. Speciﬁcally, we arepossible. Moreover, maintain the ﬂow of other traf-

facing the lack of techniques that has the incorpo-

ﬁc in the whole system, then manage and handle

ration between the self-adaptive approach with thethe uncertainties which might occur during the run-

ATRP in the priority vehicle problem. Althoughtime. Lastly, deﬁne the set of the adaptation plan

several types of research have been conducted re-to handle uncertainties.

lated to ambulance routing problem [3], most of

The rest of this paper is structured as follows.

them are the focus on hardware and network layer.

Section 2 highlights the motivating problem forIn the previous research [4], the priority vehicles

traﬃc routing with priority vehicle. Section 3 fea-

are not considered as the problem in the simula-tures our approach to deal with the problem and its

tion. The vehicles on simulation are not guaranteed

implementation on the simulation, Section 4 high-to arrive at the destination during the simulation.

lights our experiment with the number of scenar-

There are possibilities that those vehicles halt at

ios. Section 5 presents our results and discussion

the road due to the situation on the road such as

regarding the experiment that we have been con-road closure. The main challenge of this problem

ducted. Then, Section 6 compares our work to prioris that we aim to maintain both the objective ofresearch. Finally, Section 7 concludes our contribu-

completing the mission of priority vehicles as welltion.

as optimizing the traﬃc of other vehicles.

2 Motivating Problem

In this paper, we address a number of problems.

Traﬃc routing arises several problems in the ur-

Traﬃc congestion is one of the problems in the ur-

ban area. The vehicle must travel to one point toban area. The congestion often hinders the priority

another point by going through intersections andvehicle to travel in the area. The emerging area

traﬃc lights.

Since the traﬃc congestion is in-evitable events in this traﬃc routing, the vehicle

the ambulance when it has a force majeure such as

must ﬁnd a solution to minimize the impact of thisnatural disaster or failure of an engine in the car.

traﬃc congestion to their traveling time. Initially,

In such of scenario, the ambulance is not able tothe vehicle computes the estimated time to reachﬁnd a path to a destination then the other ambu-

the destination by calculating the distance from thelance will be dispatched to cover for that unﬁnishedinitial position to the destination. However, themission. In [4], the simulator already implemented

congestion might occur during the journey of thethe abstract deﬁnition of privacy ﬁlter. Thus, thevehicle. In response to that situation, the vehicle

routing problem related to priority vehicle remainmust recompute in every single time the vehicle fac-

unsolved and then the implementation of privacy

ing this situation.

ﬁlter function is necessary to tackle this issue.

The cause of traﬃc jam can be varied from several reasons, such as a high volume of vehicles, road

3 Approachclosures due to constructions, and traﬃc light mal-

The motivating problem we illustrated in Section

The implementation of an agent that

2 has encouraged us to propose a novel approachmonitors the causes of traﬃc jam has indicatedto this problem. The problem in traﬃc routing re-a satisfactory approach to overcome the situation

lated to a priority vehicle that we want to tackle is[4]. Nevertheless, the action that handles speciﬁcthe lack of an adaptation strategy corresponding topriority vehicle problem might require a diﬀerent

the priority vehicle in [4]. Here, we deﬁned several

approach.

adaptation plans and strategies then incorporatedfunction.

In our paper, we are addressing the issue whenwith the ADASIM simulator to support the rout-the simulator called ADASIM [4] was failed to makeing for priority vehicle. Thus, our approach on thisthe priority vehicle or ambulance to arrive at the

paper is Priority Routing Algorithm with predeter-

destination with speedy movement. The inability

mined adaption plan and strategy.

to achieve this goal has raised the problem for an
ambulance to fulﬁll the initial mission of the ambu-

3. 1 Removing obstacles

lance. Since the ambulance carries a critical mis-road. This action can be achieved by unblocking

sion for saving a life, it is mandatory to ensure thatthe road that has been closed due to constructions

the ambulance arrives at the destination on time.

or accidents. In the case of the accidents, the prior-

In addition to that, the level of uncertainties in theity vehicles become the priority to pass this road tosimulation impacts the traveling time of the am-

handle this situation. An action can be achieved bybulance to the destination. In such a situation,

monitoring the closed road during this cycle, thenthe vehicle and other agents (traﬃc agent and roadthe Road Closure Agent will open the road if theclosure agent) only have partial knowledge. The

ambulance needs to pass this road.

incapability of grasping the knowledge are drawbacks to satisfy the initial goals. In contrast, they
are expected to have an accurate decision-making
mechanism to achieve their goals.
Furthermore, the other issue is that the capability of sharing information between the ambulances.
We think this is important because it will support

Monitor: roadblock due to construction or accidents are being monitored frequently.
Analysis: the impact of unblocking the road are
calculated to give the eﬀect of enacting this action.
Planning: ﬁnding the shortest path to the destination if the road is unblocked.
Execution: recompute and update the estimatedtime arrival at the destination.

of the vehicles might not be shared to all vehicles
and it is only limited to Traﬃc Agent.

3. 2 Overriding traﬃc control
Overriding traﬃc control is a policy to reduce
traﬃc road on a speciﬁc segment of the road which

Monitor: the indicator of engine failure in theambulance and the emergency status of the city
are being watched.

is passed by the ambulance. There are two options

Analysis: we analyze the eﬀectiveness if the desti-that we apply for this simulation. First, we create

nation of the ambulance is changed or the mission

a counter-ﬂow of the traﬃc so that the ambulanceof ambulance is being taken over by other ambu-

will have easy access to pass the road. Second,lance.

the traﬃc light turns into gree immediately after
passing through the intersection. The Traﬃc Agentthen handle this action in the simulation.
Monitor: the current location of the ambulance,

Planning: a new destination and a new ambulance are set.
Execution: recompute the travel route to the newdestination.

the severity of traﬃc congestion nearby the inter-

At the implementation level, removing the obsta-

section and the number of other vehicles are super-

cle and overriding the traﬃc control are incorpo-

vised. Those factors have a signiﬁcant impact on

rated in PriorityRoutingAlgorithm class. The basecongestion.

class implementing a modiﬁed version of Dijkstra s

Analysis: After the ambulance passing the traﬃcalgorithm. This class comes with two constructors.

light, we measure the consequences if other vehicles

The zero- argument constructor (used when thisnearby the ambulance are stopped during this ac-class is instantiated from a conﬁguration ﬁle) cre-tion.

ates an instance of the strategy that will computePlanning: considering the duration of traﬃc lightshortest paths based on node weights alone and willturns into green when the ambulance is passing by

never recompute a path. The second constructor

and others vehicle turns into red.

takes two arguments: lookahead and recompute.

Execution: changing the traﬃc light into green

These two parameters determine how far away fromand red at the same time for diﬀerent sides of in-its current node a car can perceive traﬃc, and howtersections

often to recompute the path, respectively. Eachof the policy was referred to as a function in the

3. 3 Information sharing policy

PriorityRouting class.

Information sharing between ambulances andInformation sharing policy is installed into eachhospitals. This policy controls the information be-of priority vehicle. In Vehicle class, we added atween agents and their negotiation protocol. Vehi-

new criterion for privacy ﬁlter which ﬁlters only for

cle Agent operates this action by selecting whichpriority vehicle. After ﬁltering the eligible crite-

vehicle is categorized as a priority vehicle and thenrion for priority vehicle, we specify which informa-

applying the policy to the selected vehicles. In thistion should be shared between this priority vehicle.

process, we are carefully implementing this method

This function then has to store the information andsince the existing simulator already speciﬁed theshare to other priority vehicle agents. This ﬁlter isdata privacy policy on its agent. This situation wasapplied when the priority vehicle is facing an un-considered to prevent improper use of the data. For

expected situation which might lead to an unsuc-

example, the information about its current location

cessful mission of the ambulance. For example, anambulance is failed to continue the journey due toprovision of secure and eﬃcient emergency services

engine failure and the only way to transport this isin smart cities. In this work, some components into transfer the mission to the other ambulances.

traﬃc management system such as traﬃc manage-

4 Related Workment controllers (TMC), adaptive traﬃc light con-A recent survey points out that self-adaptive soft-

troller, and sensor controller are introduced to col-ware systems have been proposed in some related

lect the information about the severity of the dis-research. Research has discussed the strategic layer

aster. In case of the emergency condition occurred,for selecting the routes and adaptive learning be-

the TMC has a responsibility to control the traﬃchavior in a multi-agent framework based on JADEﬂow for the emergency service vehicle. In contrast[5]. This JADE framework interacted with traf-

to this paper, we simpliﬁed the scenario by deﬁning

ﬁc simulator called SUMO that supplies the tac-

the uncertainties with the probability factor. The

tic layer of simulation: vehicle changing the lane,

goal of this is to create a decentralized approach inbreaking, and accelerating. On the other hand, thisa self-adaptive system.

paper focus on ﬁnding the best route to reach the

Eventually, the ADASIM simulator [4] itself has

destination while monitoring the current situation

presented novel benchmark tools with a set of di-of the traﬃc. This action is necessary to maintainmensions along which solutions should be evalu-

the primary goal of the priority vehicles as well as

ated. The related challenges such as scalability,

other vehicles in the traﬃc system. Further, therobustness, and balancing the precision and per-adaptive learning process in [5] might lead to an-formance of monitoring has been highlighted. In

other computation process hence require extra time

contrast to our paper, we focus on speciﬁc traﬃcand resource consumption.

routing problem related to priority vehicle which

In addition, a Belief, Desire, and Intention (BDI)

has not been addressed by prior research. Regard-

agent have been integrated with MATSim for cre-ing the results, we have improved the mean travel

ating an agent that has a reactive response to thetime for the priority vehicles.

surrounding environment [6]. The self-adaptation
approach used in [6] has developed the static adap-

5 Conclusion

tation plan in advance to tackle its problem sce-

This paper has proposed a Priority Routing al-

nario. In contrast to our paper, we present thegorithm with a set of adaptation plans for traﬃcnumber of adaptation plan that has the capability

routing problem related to priority vehicle.

to change dynamically during the runtime.

have successfully reduced the average travel timeWe

Several adaptation approaches on dependent net-for priority vehicle. We believe that the adaptation

works also have been introduced [7], [8]. That pa-

plans we have implemented are suitable for such a

per mainly features the integration between SFINA

scenario.

framework with domain- speciﬁc modeling lan-

For future work, we will investigate more accu-

guage such as MATSim to mitigate the failures

rate travel time for an ambulance in the urban area.

in the networks.

We instead focus on the self-

We plan to create a more realistic simulation ofadaptation approach in a multi-agent system with

traﬃc that is able to model the traﬃc ﬂow in thedecentralized optimization. Moreover, an adaptive

urban area as well as traﬃc congestion. We also

traﬃc management plan has been proposed in [9].

interested to apply the machine learning techniqueThat paper features an adaptive plan to ensure theto make a ﬁner adaptive learning technique to beincorporated in the simulation process.

Urban MObility User Conference. Springer, 2013,
pp. 44–61.

References[6] L. Padgham, K. Nagel, D. Singh, and Q. Chen,[1] De Lemos, Rogério, et al. “Software engineer-

Integrating BDI agents into a Matsim simulation,

ing for self-adaptive systems: A second researchin Proceedings of the Twenty-ﬁrst European Con-roadmap.” Software Engineering for Self-Adaptive

ference on Artiﬁcial Intelligence. IOS Press, 2014,

Systems II. Springer, Berlin, Heidelberg, 2013. 1-

pp. 681–686.

32.

[7] E. Pournaras, B.-E. Brandt, M. Thapa, D.

[2] J. O. Kephart and D. M. Chess. The vision

Acharya, J. Espejo-Uribe, M. Ballandies, and D.

of autonomic computing. IEEE Computer Society

Helbing,

Press, 36:41–50, 2003.

gent network adaptations,[3] Derekenaris, Grigoris, et al. “Integrating GIS,

Practice and Theory, vol. 72, pp. 34–50, 2017.

GPS and GSM technologies for the eﬀective man-

[8] E. Pournaras, M. Ballandies, D. Acharya,

agement of ambulances.” Computers, Environment

M. Thapa, and B.-E. Brandt,

and Urban Systems 25.3 (2001): 267-278.

self-managed interdependent networks–self-healing[4] Wuttke, J., Brun, Y., Gorla, A., & Ramaswamy,

synergies against cascading failures,J. (2012).

Traﬃc routing for evaluating self-

ternational Symposium on Software Engineering

adaptation.

ICSE Workshop on Software Engi-

for Adaptive and Self-managing Systems (SEAMSSFINA-simulation framework for intelliSimulation Modelling

Prototyping

in 13th In-

neering for Adaptive and Self-Managing Systems,

2018), 2018

27–32.

[9] Djahel, Souﬁene, et al. “Adaptive traﬃc man-https://doi.org/10.1109/SEAMS.2012.62

24388

agement for secure and eﬃcient emergency services[5] G. Soares, Z. Kokkinogenis, J. L. Macedo, andin smart cities.” 2013 IEEE International Confer-

R. J. Rossetti,

Agent-based traﬃc simulation us-

ence on Pervasive Computing and Communications

ing sumo and jade: an integrated platform for ar-

Workshops (PERCOM Workshops). IEEE, 2013.

tiﬁcial transportation systems,in Simulation of