Distributed Reinforcement Learning using
Bi-directional Decision Making for Multicriteria Control of Multi-Stage Flow Systems
Kei Aoki, Hajime Kimura, Shigenobu Kobayashi
Tokyo Institute of Technology, 4259 Nagatsuda midori Yokohana Kanagawa Japan
Abstract. Autonomous control systems have been requested recently for large-scale
real systems. Distributed reinforcement learning is attracting attention specifically incontrol of physical flow systems such as lifelines. In this paper, we will introduce amodel of Multi-Stage Flow System (MSFS). MSFS is a framework which can describe
various physical flow systems. Furthermore, it is effective in handling multi-criteria,
multiple constraints under uncertainty and so on that are difficult to solve in conventional methods because of its features. We propose a new bi-directional decision
making algorithm based on a least commitment strategy. We apply our method to controlling of real sewerage systems. The simulation results show that only our method
satisfies permissible levels and attains the performance within an acceptance level.

1 Introduction
A method of autonomous control has been requested recently for large-scale real system andhas been researched extensively. It is requested to lifeline systems such as sewerage systems
especially because they are necessary and indispensable to our modern day life.
Real systems have an uncertainty and a time lag, etc., and approaches using Dynamic
Programming or Reinforcement Learning (RL) are known[7]. The lifeline systems are of alarge-scale and have a wide-area network composed of service centers. Distributed control
within the framework of Multi Agent System (MAS) is promising[6]. Thus, approaches thatuse distributed RL (DRL) are attracting attention. However, the example of applying DRL to
the real systems is not common practice. Moreover, the targeted problem class rarely considers multi-criteria and multiple constraints, etc.
We should target a realistic problem class for consideration in the application of the acquired control policy, and clarify features of the real systems that are multi-criteria, multiple
constraints, handling of constraints under uncertainty, interactions and so on. Therefore, we
model Multi-Stage Flow Systems (MSFS) which can describe various physical flow systems
as a new problem class based on these features. However, conventional DRL cannot addressthese features directly. Therefore, we propose an approach that acquires an appropriate control policy by addressing them directly.
We propose new DRL using Bi-directional Decision Making (BDM) based on the leastcommitment strategy[8] in order to address multi-criteria of MSFS which treats a smoothing
control at the root of MSFS and satisfies constraints of each agent. As opposed to conventional DRL in which each agent makes a decision independently, our method shares decision
making among agents bi-directionally by using a tree structure of MSFS. Firstly each agent
presents a feasible action set selected in terms of constraint satisfaction, subsequently in theKei Aoki, Hajime Kimura, Shigenobu Kobayashi

2
SCr
Customers

plant
SCm

SCm
Customers

SCt

SCt
Customers

SCt
Customers

Customers

SCt
Customers

Customers

Figure 1: Image of MSFS. Symbol of chevron in circle is a flow controller (e.g. pump).

Lower(i)Customer's Service Center : i
Demand:LiMAX
d i(t)
Li(t)Outflow: b i(t)Upper(i)inflow:a i(t)iL
MIN

Figure 2: Model of a Service Center in MSFS.

direction of the agent of the root node from the agents of the leaf node. Then, each agent
decides unique action in terms of smoothing, subsequently in the direction of the leaf nodefrom the root node. Moreover, we propose a selecting method of the action sets to satisfy thegiven permissible levels by using value functions to address multi-criteria and multiple constraints. We apply our method to a real sewerage system, and aim to achieve a control policythat fulfills a practicable acceptance level of smoothing while satisfying the given permissiblelevels of constraint satisfactions.
Conventional methods give the trade-off rates explicitly, and achieve a co-operative behavior within the framework of DRL using a linearly weighted sum (LWS) of value functions[5, 6]. MAXQ[2] hierarchizes a complex task by defining subtasks, and improves the efficiency of learning. However, multiple constraints of MSFS are satisfied by appropriate interactions of agents. In addition, it needs to balance with the purpose of smoothing. Therefore,
an appropriate design of weights where such a complex policy is achieved by the approximation of the value function using LWS is complicated. The division of the task into the subtask
is also difficult. Our method aims to achieve an appropriate balance not by the trade-off rates
that are given by the designer but by BDM and the selection of action sets which satisfy
permissible levels. Incidentally, there exists methods using lexicographical optimal policy[3]and policy of handling the risk[4] from the viewpoint of handling constraints our method issimilar, though no MAS. In addition, there exists researches which treat distributed constraint
satisfaction problems[9], though no RL of control.
In Section 2, we investigate MSFS and how it is modeled and formulated. Section 3
presents our approach and proposal method. Experimental results in a sewerage system show
its effectiveness in Section 4. Section 5 concludes this paper.
2 Multi-Stage Flow Systems
2.1 The outline of Multi-Stage Flow Systems
MSFS describe various physical flow systems that target applications such as water supply
and sewerage systems, power grids, gas grids, distribution systems and so on.
MSFS is a multi-stage tree structure whose node is the service center (SC) in Fig.1.1 SCsof the leaf node of tree structure are called terminal SC (SCt), SC of the root is called root SC(SCr) and the rest are called middle SC (SCm). SCr is connected with a special plant suchas power plants, production plants, treatment plants and so on. Each SC provides service forcustomers in the newsbeat by controlling the flow received from the upper SC or the plant.
Flow is a continuous or discrete variable such as water or products. Service is to supply thedemand for customers. A main purpose of MSFS is to provide service in just proportion byappropriately controlling flow.
Each SC has to absorb the uncertainty of customer’s demand using a buffer such as a
1

There exists bypasses for emergency, etc. and we exclude them in this paper.

Distributed Reinforcement Learning using Bi-directional Decision Making for MSFS

3

warehouse and a reservoir. However, because a stock level has a bound pair constraint2due
to limitation of capacity etc., controlling flow that is kept within its range in advance is necessary for a good service.3 However, it is difficult to completely guarantee the constraint
satisfactions under demands with uncertainty. Therefore, a permissible level is set to each
SC in general as a permissible rate of the operational constraint violations under the safetymargin. A permissible level of each SC is decided beforehand depending on a fluctuation ofdemand and a capacity of a buffer, etc.
On the other hand, a supply of plant to MSFS should be as constant as possible froman economical and operational viewpoint.4 Therefore, SCs have to absorb the fluctuations ofcustomer’s demands by cooperatively controlling flow. And, SCr connected with plant has tocontrol the flow as constant as possible.
Therefore, MSFS is a multi-criteria control problem concerning a smoothing of flow of
SCr and multiple constraint satisfactions of stock level of each SC.
2.2 Modelling Multi-Stage Flow Systems
Fig.2 shows the model of SC of MSFS. MSFS consists of N service centers, and the ith SC is
described as SCi (i=0,· · · ,N −1). Lower(i) denotes the set of SC connected with the lower
position of SCi , and Upper(i) denotes SC connected with the upper position of SCi . SC0 is
SCr, and Upper(0)=∅ because upper facility is a plant. SCi is called SCm when i>0 and
Lower(i)=∅. It is called SCt when Lower(i)=∅. Each SCi has a buffer with the bound pairconstraint (LiM AX , LiM IN ).
Each SCi is characterized by parameters as follows.
• Li (t) is a stock level of SCi at t. Below exists as the following constraint conditions.
LiM AX > Li (t) > LiM IN .

(1)

• di (t) is the demand of customers of SCi at t.
• ai (t) is the inflow that SCi receives at t, and is a control variable.
• bi (t) is the outflow of SCi , and is the sum of the total inflow of Lower(i) and di (t).
bi (t) = j aj (t) + di (t), SC j ∈ Lower(i).

(2)

The stock level at t+1 is updated by a function F i(·) which depends on the buffer.
Li (t + 1) = Li (t) + F i bi (t) − ai (t) .

(3)

Negative rewards (penalty) are defined for the control performance as follows.
• rci (Li (t)) is penalty of constraint violations where Li (t) gets out of Eq.1.
2

Operational constraint is decided by setting a safety margin so as not to arrive at a physical limit in thebuffer. Though the system does not break down owing to its violations, the system should be operated keeping
it as effective as possible.
3
For instance in a water supply system, a water level of a pumping plant may arrive at the lower limit if alarge demand is generated when the water level is low. It may interfere with providing service. If such a large
demand is expected, it is necessary to keep it high by controlling flow in advance.
4
For instance in a sewerage system, changing an amount of treatment processing is costly because of thebiochemistry processing, etc. Thus, smoothing of an inflow is requested of the sewage treatment process. Thisis similar to the purification process in a water supply system. In a distribution system, smoothing a production
volume is requested for reasonable scale of the production line which meets demand under seasonal variations.
In a power grid and a gas grid, it is advantageous to suppress the fluctuation of production volume for reasonable
scale of plant and a raw procurement.

4

Kei Aoki, Hajime Kimura, Shigenobu Kobayashi• rs (a0 (t), a0 (t − 1)) is the penalty where SCr changes its flow. In regard to flow of SCr,the minimization of a change is equal to the achievement of the smoothing.
Therefore, MSFS is modeleddimension multi-criteria problem.
  ias (N+1)
ir (L (t)) ,i = 0, · · · , N − 1.
(4)min t c 0
0
r
(a
(t),
a
(t
−
1))
,
A
t s


where A= (a(0), · · · ,a(t), · · · ); a(t) = a0 (t), · · · , aN −1 (t) is a combination of ai (t) of
all SCi (i=0,· · · ,N -1) at all time.
2.3 Formulation to Distributed Reinforcement Learning
MSFS is a distributed system whose each SCi has the function of a sensor and an actuator as
shown by Fig.1 and Section 2.2. The method using the distributed control is considered highly
probable in terms of RL[6]. In this paper, MSFS is assumed to be MAS which considers each
SCi to be an agent. We formulate a state-action space and rewards, and approach MSFS withthe framework of DRL.
• ai (t) is an amount of flow and the action of SCi at t. Flow is a discrete variable, and acontinuous value makes it discrete appropriately in this paper.
• si (t) is a state of SCi at t, and is defined as a vector according to the position.
s0 (t) = (Time (t), L0 (t), j aj (t), a0 (t − 1)) ; SCr , SC j ∈ Lower(i).
si (t) = (Time (t), Li (t), j aj (t)); SCm , SC j ∈ Lower(i).
(5)
si (t) = (Time (t), Li (t)); SCt , Lower(i) = ∅.
Time (t) = t (mod τ ) is a periodic function at cycle τ concerning t, and denotes the time,
the season and so on of an environment. di (t) synchronizes at a constant cycle in general,though it cannot be observed beforehand.5 SCr measures the change of flow (smoothing)
Each SCi attempts the satisfaction of constraint
by observing a0 (t − 1) according to Eq.4.

condition in Eq.1 by observing Li (t), j aj (t) (however at SCt, Lower(i) = ∅) and Time (t)in place of di (t) according to Eq.2, 3.
• r i (t) is a reward of SCi at t, and is defined as r 0 is a vector and the rest are a scalar
according to Eq.4.
r 0 (t) = (rc0 (L0 (t)), rs (a0 (t), a0 (t − 1))) ; SCr.
; SCm, SCt.
r i (t) = rci (Li (t))(6)

• Qi (si (t), ai (t)) is a value function corresponding to r i (t), and denotes the total discounted
expected reward based on a certain policy. The value function of SCr is defined as a vector
as well as r 0 (t). It is calculated by an update rule enhanced based on the SARSA learning[7] (cf. Section 3.5).
Q0 (t) = (Q0c (s0 (t), a0 (t)), Qs (s0 (t), a0 (t))) ; SCr.
(7)
; SCm, SCt.
Qi (t) = Qic (si (t), ai (t))• piv (t) is a constraint violations rate during [t−∆t, t]. ∆t is an arbitrary fixed period.
• pip is a permissible constraint violations rate during ∆t. It is called a permissible level,
and is given beforehand according to the safety management, etc.
We aim to acquire the control policy of MSFS which achieves a smoothing of the flow of
SCr as effective as possible satisfying piv (t) ≤ pip under the formulation above.
5
For instance, customer’s necessities that include electricity and water supply increase in the mornings andevenings, then decrease at midnight because of the customer’s life cycle.

Distributed Reinforcement Learning using Bi-directional Decision Making for MSFSa2 a3 a4 with a = ( a2l1 , a3l 2 )Present toa2 a4 with a = ( al31 , a3l 2 )Upper SC

FAS
a2 a3

a1 a5 a4

Lower(l1)'s FAS

FAS

Present to Upper SC
from Bottom Upwarda3(a) at SCt5al21 , a 3l1
Lower(l2)'s FAS

a3l 2
a1 a5
a1 a5 a3a2
Qc(s,a)a3 a4 a2
a4 a2

l

l

Qc with a = (a21 , a32 )ll
Qc with a = (a31 , a32 )(b) at SCr, SCm

Figure 3: Bottom-up FAS selection. aik is a kth action of SCi . If Lower(i)=∅, Qi is represented with reference
to the combination of the lower SC’s actions a; Lower(i)={l1 , l2 } in (b).

3 Bi-directional Decision Making
3.1 Our ApproachA new method is needed to address MSFS appropriately because of multi-criteria, multiple
constraint and so on shown in Section 2. The following points conflict by dividing the stateaction space and the rewards into each SCi as shown in Section 2.3.
• It is necessary to select actions of Lower(i) for selecting action of SCi beforehand fromthe definition of si (t) in view of the constraint satisfaction. Thus, the decision making
process is requested to perform from bottom upwards from SCt to SCr.
• A penalty for smoothing is given to SCr from the definition of rs (a0 (t), a0 (t − 1)). WhenSCr selects the action which leads to smoothing, to that end, it is necessary that Lower(i)select accommodative actions. Thus, the decision making process is requested to performfrom the top downwards from SCr to SCt.
To settle this competition, we introduce Least Commitment Strategy (LCS) based on thealgorithm that Waltz used to understand line drawings[8]. When existing information canbe used for decision making locally, this strategy sets aside a part of the decision by only
deciding the partial and minimal solution without deciding completely. Then, a complete
solution can be obtained based on all partial solutions and interactions.
Our approach based on LCS is as follows. If the actions of Lower(i) are decided, each
SCi can envisage the transition of Li (t) according to Eq.3 and Eq.5 independently of otherSC’s. However, each SCi selects the set of actions estimated to satisfy piv (t) ≤ pip according
to Qic without deciding the action uniquely as described below, because it cannot address asmoothing at this stage. This set is called Feasible Action Set (FASi (t)), and FAS of Upper(i)is selected subsequently by presenting FASi (t) to Upper(i). After all FASi (t) are selected,
SCr uniquely selects a0 (t) from FAS0 (t) in view of a smoothing. Decision making is propagated to Lower(i) subsequently, and ai (t) of each SCi is decided uniquely. Because eachai (t) is chosen from FASi (t), the satisfaction of piv (t) ≤ pip can be expected.
Our approach uses Qic to select FASi (t) appropriately. We introduce the threshold Ωi (t)of Qic of each SCi , and choose the action sets with a high possibility to satisfy the permissiblelevels by adjusting these thresholds. Ωi (t) is used to classify ai (t) in terms of whether ai (t)in si (t) satisfies piv (t) ≤ pip from the viewpoint of Qic (si (t), ai (t)). Each SCi updates Qi
according to r i (t), and improves the control policy.
Therefore, the bi-directional action selection based on LCS and the selection of FAS
which uses Ω are the main ideas of BDM. The proposed method consists of the following 4
steps (cf. Section 3.2-3.5), and their steps are performed repeatedly in its algorithm.

Kei Aoki, Hajime Kimura, Shigenobu Kobayashi

6
Upper

FAS of SCr (r)

Upper

Lower

Qs(s,a) = a4r
argmaxra

FAS of SCm(m)a m4 with a = ( a2t1,a3t2 )a m4 with a = ( a3t1,a3t 2)

t t2
argmax Qcm(s,a m4 )=( a31, a3 )Lower

FAS of SCt(t1)at21 at31...

a2r with a = (a m2 ,... )a4r with a = (a m4 ,... )FASs of Other SC

FAS of SCt(t2 )

at32

a

Figure 4: Top-down action selection using FAS. Underlined parts are selected actions. Boxes of broken lines
show combinations of actions of the lower SCs related to the selected action. Instruction of actions is indicatedby broken line arrows.

3.2 Bottom-up selection of Feasible Action Sets
FASi (t) is selected according to Qic concerning the constraints along the following lines. This
step performs subsequently from SCt to SCr from the bottom upwards.
• SCi observes state si (t).
• Because of Lower(i) = ∅ at SCt, ai (t) are sorted according to Qic (si (t), ai (t)) and ai (t)which satisfy Ωi (t) < Qic are added to FASi (t) as shown in Fig.3(a).
• Because SCm and SCr have SCj ∈ Lower(i), j aj (t) is calculable according to a
combination a= (aj (t)) ; aj (t) ∈ F AS j (t) that consists of actions that are taken out one
by one among each FASj (t) that SCj presents. Thus, the variation of si (t) is recognized,
and Qic corresponding to each a is addressed as shown in Fig.3(b). Then, ai (t) which
satisfy Ωi (t) < Qic as well as SCt are added to FASi (t). And, each a is also memorized
because Qic depends on a.
• When FASi (t) becomes an empty set because all actions are excluded by Ωi (t), argmaxa Qic
is added to FASi (t) .
• If Upper(i)=∅, FASi (t) is presented in Upper(i), otherwise this step ends.
3.3 Top-down Selection of Actions
After all SCi decides FASi (t), all actions are decided uniquely subsequently from SCr forsmoothing. SCr selects argmaxa0 (t) Qs (s0 (t), a0 (t)) from FAS0 (t) first (a left of Fig.4). Because this a0 (t) accompanies the actions of Lower(0), these actions are instructed to Lower(0)as the broken line shows. Then, SCm (i=m) decides am (t) according to Upper(m)’s instruction, and gives Lower(m) instructions of their actions similarly. If the action am (t)instructed from Upper(m) is a plural in FASm (t), the actions of Lower(m) which maximizemmQmc (s (t), a (t)) are instructed (a center of Fig.4). The action of SCt is decided according
to the given instruction (a right of Fig.4).
Therefore, in SCm and SCt which do not obtain a reward of smoothing directly, it ispossible to contribute to smoothing as effective as possible satisfying a permissible level.
After selecting all actions, each SCi performs the action concurrently.
3.4 Threshold Adjustment
It is necessary to adjust the threshold Ωi (t) appropriately to select the action set to which
the FAS selection satisfies a permissible level pip . In this paper, to become piv (t) = pip bycomparing an obtained piv (t) with a given pip , Ωi (t) is adjusted by a slight value . Therefore,
because the constraint satisfaction has not been achieved then the piv (t) > pip , Ωi (t) is severelyDistributed Reinforcement Learning using Bi-directional Decision Making for MSFS

7

adjusted. Conversely, because the constraint satisfaction has been achieved then the piv (t) <pip , Ωi (t) is eased to contribute to smoothing.
 iΩ (t) +  , piv (t) > pip ,iΩ (t + 1) =(8)
Ωi (t) −  , piv (t) < pip .
Therefore, Ωi (t) is adjusted to the maximum value that piv (t) is suppressed to pip . All ai (t)that are expected to satisfy piv (t) ≤ pip in view of Qic are added to FASi (t).
3.5 Updating Value Functions
The SARSA learning (SARSA)[7] is a method for learning the value function of state-action
pairs according to trial and error based on a certain policy. In this paper, to update our valuefunctions, we enhance SARSA.
• The update of Q0 of SCr uses SARSA in each (Qs , Q0c ). Below, o is s or c.

Q0o (s(t), a(t)) = (1 − α)Q0o (s(t), a(t)) + α ro + γQ0o (s(t + 1), a(t + 1)) .
(9)• To update the value function Qi at SCi ; i > 0, we enhance SARSA as follows in view ofusing FASi (t) for the decision making.
(10)
Qi (s(t), a(t)) = (1 − α)Qi (s(t), a(t)) + α(r + γVfi ).

1
Q(s(t + 1), a(t + 1) ),
(11)
Vfi =
i
|FAS (t + 1)| a(t+1)
where a(t + 1) ∈ FASi (t + 1) and |FASi (t + 1)| is the number of a(t + 1) .
Update rule (Eq.9) of SARSA is based on value function Qi (si (t+1), ai (t+1)) of action
ai (t+1) selected at t+1. Update rule (Eq.10) of our method is based on value function Vfi ofaction set FASi (t+1) selected at t+1. Upper(i) can give SCi the instruction of an arbitrary
action from among FASi as stated above. Considering this arbitrariness, the value function
Vfi of FASi (t+1) should reflect the value function Qi (s(t+1), a(t+1)) of the action a(t+1)
that is included in FASi (t+1). In this paper, we define the mean value as the value function Vfi
of FASi (t+1) (Eq.11). Therefore, our update rule (Eq.10) which uses FAS is an appropriate
extension of the update rule of SARSA (Eq.9).
4 Application to Sewerage System
We take up the control problem of a sewerage system, and confirm utility and availability by
the comparison with conventional methods. The target that consists of 5 SC as shown in Fig.5
is modeled on a real sewerage system with large-scale processing in Kawasaki, Japan. The
system supplies service of collecting sewage from customers, carrying it through the pumpplants, and purifying it in the treatment process. Because of collecting flow, we can model
it as MSFS by handling a reverse flow in Fig.1 and Fig.2. The flow ai (t) can be controlled
in about 10 discrete levels by switching several pumps with hourly decisions. The demand
we input data of real demands of about one monthdi (t) for sewage disposal is uncertain so
repeatedly. Total of the permissible level i pip is given by 0.015 that is total of the pip of each
SCi at ∆t = 24.
The performance evaluation index of the control policy is defined as the number of pumpswitches Sw of SCr. It can be considered that the fewer Sw is, the more smoothing will beachieved, because Sw shows the frequency per day in which the amount of processing ischanged. The applicable standard that is clarified by the sewerage experts is Sw≤2 in thisreal system. This target performance is called an Acceptance Level.

Kei Aoki, Hajime Kimura, Shigenobu Kobayashi

8
4.1 Design of Compared Methods

To confirm the effectiveness of the proposal method, we choose the method of Schneider [6]and Guestrin [5] as comparison methods. To be able to apply these methods, a part of theformulation is changed as follows.
Because the method of Schneider cannot treat the reward of the vector directly, the rewardof SCr of Eq.6 is linearly summed with weight β 0 . And, it becomes single-criteria. r i ; i =1, · · · ,N−1 of SCm and SCt are the same as Eq.6.
r 0 (t) = rc0 (L0 (t)) + β 0 rs (a0 (t), a0 (t − 1)) ; SCr.
(12)
; SCm, SCt.
r i (t) = rci (Li (t))
The following methods are explained based on [6] under Eq.12 above. In these methods, each
SCi independently decides the action.
• The Local Reward DRL (LRDRL) setting: Each SCi independently decides the action
according to the local reward shown in Eq.12.
• The Global Reward DRL (GRDRL) like setting: All SCi share the reward rs concerninga smoothing of SCr.
r i (t) = rci (Li (t)) + β i rs (a0 (t), a0 (t − 1)) ; i = 0, · · · , N − 1.
(13)
• The Distributed Reward Function (DRF) setting: The reward is shared with connected
SCj . r j (t) denotes the reward in Eq.12.

r i (t) = j β j r j (t) ; SC j ∈ SCi ∪ Upper(i) ∪ Lower(i), i = 0, · · · , N − 1. (14)• The Distributed Value Function (DVF) setting: The value functions are shared with connected SCj by using the following update rule under Eq.12. (refer to [6], in detail.)



i
i
i
j
Q (s, a) = (1 − α)Q (s, a) + α r + γ j f (i, j) maxaj Q (sj , aj ) .
(15)
Next, for Coordinated Reinforcement Learning (CRL) of Guestrin[5], we consider thecoordination graph that is comprised of connected relationships which can be seen in Fig.5.
The pair of SCi and SCj is described as SCij , the system is addressed by (i,j)={(0,1), (0,2),(0,3), (1,4)}, and we formulate it as follows.
• Though the state is given as follows according to Eq.5, j aj (t) is excepted because SCijcontains the interaction.
s0i (t) = (Time (t), L0 (t), Li (t), a0 (t − 1)) ; SC0i , i = 1, 2, 3.
(16)
s14 (t) = (Time (t), L1 (t), L4 (t)); SC14 .
• The action aij (t)=(ai (t), aj (t)) is a combination of the flow of SCi and SCj . The numberof actions becomes the min of 48 and the max of 88 in this system.
• The rewards are defined by a linearly weighted sum as follows according to Eq.6.
r 0i (t) = β 0i rc0 (L0 (t)) + β irci (Li (t)) + rs (a0 (t), a0 (t − 1)) ; SC0i , i = 1, 2, 3.
(17); SC14 .
r 14 (t) = β 14 rc1 (L1 (t)) + β 4 rc4 (L4 (t))• The global value function Q is approximated by the sum of local Qij correspond to r ij .
The CRL selects the combination of the actions which maximizes Q(t).

Qij sij (t), aij (t) ; (i, j) = {(0, 1), (0, 2), (0, 3), (1, 4)}.
(18)
Q(t) =(i,j)

Distributed Reinforcement Learning using Bi-directional Decision Making for MSFS
Table 1: Performance of the pump switches (Sw) and the constraint violations (Method
 Swi
i pv (t)BDM
1.848
0.0144LRDRL
5.266
0.0341

GRDRL
3.293
0.0154

Pumping
Pumping
Plant 4 (SC4 ) Plant 1 (SC1 )Sewage Treatment Plant(plant)(SC0 )(SC2 )

SewageTreatment
Process

sewagePumping Plant 2(SC3 )

sewagesewageNumber of pump switches (day)Learning Curve on 5 plant sewerage system
BDM
GRDRL
DRF

4

CRL
3.459
0.0552

DVF
CRL

0.0
-1.0
-2.0

i
i pv (t)).
i
i pp



–
0.015
b i(t)
SC0 (SCr)

L0(t)

5000

MIN

3000
1000

Amount of
the sewage

MAX
0.0
-1.0
-2.0

SC1 (SCm)

L1(t)

3000
2000 Amount of1000 the sewage

MIN

MAX
0.0
-1.0
-2.0

SC2 (SCt)

L2(t)

1400
1000 Amount of
500 the sewage

MIN

MAX
0.0
-1.0
-2.0

L3(t)

SC3 (SCt)
1000

MIN

3



d i(t)a i(t)

Pumping Plant 3

Figure 5: 5 plant Sewerage System.
5

DVF
2.598
0.0230L i(t)

MAX

sewagesewageDRF
3.593
0.03079Amount of

500 the sewage

Acceptance Level

2

MAX
0.0
-1.0
-2.0

SC4 (SCt)

L4(t)

1400
1000 Amount of
500 the sewage

MIN

1
0

200
400
600
800
1000
Number of Steps (X10,000 steps)

Figure 6: The learning curve on a 5 plant seweragesystem. Each is an average of 10 trials. LRDRL is not
drawn because its performance is worse than Sw = 5.

0

3

6

9

12

hour

15

18

21

24

Figure 7: Behaviors of a sewerage system for24hours based on an average day.

4.2 Experimental Results and Discussion
The learning curve is shown in Fig.6. The plots are an average performance of 10000 steps of
10 trials, and are an average of the best value up to the step. The daily average performancesof the control of each method are shown in Table 1. Each weight of the compared methods(β, f (i, j)) is appropriately set in consideration of permissible levels.
LRGRL hardly achieves smoothing as seen in Sw=5.266. It is suggested that the cooperation of the SCs is indispensable in smoothing the flow of SCr and that it may not be acquiredby pursuing a local reward. Though the system using GRDRL and DRF behaves more reasonably than LRGRL that only uses local rewards, neither enough smoothing is achieved.
It is suggested that cooperated behavior necessary for smoothing may not be appropriately
acquired because the interactions cannot be controlled directly. In GRDRL, the constraint
violation as well as Sw is less than LRDRL. Pumping plants stabilize the amount of inflow
into SCr by the smoothing reward, and it is suggested that it mitigates the violations of SCr.
Though DVF acquires a tolerable performance, it does not arrive at the performance target. The difficulty in DVF which depends on the linear weighted sum is the selection of a risky
action to contribute to smoothing. It is suggested that such a selection may not be achieved
according to the fixed trade-off rates.
Though CRL that acquires better performance than DVF has been reported, the target performance is not acquired here. Because the state-action space of SCij is large, it is consideredthat the learning steps are insufficient. Therefore, with the state-action space where each SCi
is as large as this real sewerage system, it is suggested that the distributed control of each

10

Kei Aoki, Hajime Kimura, Shigenobu KobayashiiSC isi effective. Moreover, the performance when CRL learns until 100M steps is Sw = 3.3,
i pp = 0.0216. Thus, it is suggested that approximation of the global value function to
obtain expected behaviors is difficult.
The proposal method (BDM) is an only method that acquires the control policy which
satisfies an Acceptance Level. Though the permissible levels might not be satisfied at the
opening of learning because the FAS selection has not enough accuracy, they are graduallysatisfied by adjusting the thresholds along with a learning process.
Fig.7 shows the behaviors of a certain 24 hours of the control policy provided by the
proposal method. Each SCi keeps Li (t) within the range of the bound pair constraints byappropriately controlling ai (t). On the other hand, a0 (t) is switched only twice at 0900 and
2100 hours in SCr, that is, a smoothing is achieved. The reason is that L0 (t) is stabilized byadjusting b0 (t) giving Lower(i) instructions of the actions appropriately along a0 (t). Especially, in the behaviors at 0500 hours, co-operated control of SC2 and SC3 counterbalances
the low flow of SC1 selected so that SC1 may keep its water level.

5 Conclusions
We showed and modeled MSFS in relation to various physical flow systems which suitedreal problems. Our proposed model of MSFS is effective in handling the multi-criteria andthe multiple constraints that are difficult to solve in conventional methods. We proposed the
new DRL using the BDM which can address these features directly for MSFS.
We applied the BDM to the control problem of the sewerage system, and confirmed it
fulfilled an acceptance level satisfying permissible levels. Though the BDM is fundamentally
applicable to arbitrary MSFS, it becomes inefficient in cases where a certain SCi connects
a lot of SCj ∈Lower(i). The connection of about 5 SC per one node seems limited in thissewerage system though it depends on the number of actions of each SC.
Because the value function is calculated with FAS, the optimum of BDM is unexplained.
Future works will show theoretical analysis of rationality of BDM. Moreover, we will show
the generality of our method by applying it to other applications.
References[1] K. Aoki, H. Kimura, A. Nagaiwa and S. Kobayashi. Adaptive control of Sewerage Systems using Distributed Reinforcement Learning, IEE Japan 123-D-4, 462–469, 2003, (in Japanese).
[2] T. Dietterich. The MAXQ Method for Hierarchical Reinforcement Learning, Proceedings of the 15th
International Conference on Machine Learning, 118–126, 1998.
[3] Z. Gabor, Z. Kalmar and C. Szepesvari. Multi-criteria Reinforcement Learning, Proceedings of the 15th
International Conference on Machine Learning, 197–205, 1998.
[4] P. Geibel. Reinforcement Learning with Bounded Risk, Proceedings of the 18th International Conference
on Machine Learning, 162–169, 2001.
[5] C. Guestrin, M. Lagoudakis and R. Parr. Coordinated Reinforcement Learning, Proceedings of 19th International Conference on Machine Learning, 227–234, 2002.
[6] J. G. Schneider, W. K. Wong, A. Moore and M. Riedmiller. Distributed Value Functions, Proceedings ofthe 16th International Conference on Machine Learning, 371–378, 1999.
[7] R.S.Sutton, and A.Barto. Reinforcement Learning: An Introduction, A Bradford Book, The MIT Press,1998.
[8] D. Waltz. Understanding Line Drawings of Scenes with Shadows in The psychology of Computer Vision,
McGraw-Hill Book, 1975.
[9] M. Yokoo, K. Hirayama. Distributed Constraint Satisfaction Algorithm for Complex Local Problems,
Journals of The Japanese Society for Artificial Intelligence, Vol.15, No.2, pp.348–354, 2000, (in Japanese).