Behavior Modeling in Transportation Networks Lecture Series #2-5 (16:20-16:50) RL model and Advanced Behavior Modeling Yuki Oyama Shibaura Institute of Technology Activity Landscape Design Lab. September 14, 2020 Recall the logit model Choice probability:
Vi    : deterministic utility of i ε į ···d· Gumbel(0, µ), ∀i    : error term C : choice set Value of choice situation (welfare):
there are over 87,000 different drink combinations at Starbucks?" Choice is often combination of elemental choices e.g., activity pattern (H, W, O), mode choice (MaaS), tour planning... Choice set can become huge and is difficult to define... MENU COFFEEHOUSE RESPONSIBILITY CARD
Espresso Beverages
Handcrafted Lattes, Cappuccinos, Macchiatos, Festive Favourites and more. Did you know there are over 87,000 different drink combinations at Starbucks. Why not try a syrup in your morning latte, or try soy in your mocha? A drizzle of buttery caramel on the top of your cappuccino? The possibilities are endless...discover your favourite. Espresso Beverages

way more than Starbucks...
What can we do ?
A = [a, 2, #, . . .] Choice Sequence of choices How to model sequences ?
Route choice probability:
p(a j+1|a j )  : Link choice probability conditional on the previous link ⇒ Seems easy…, but what is link choice probability exactly?
the outcome given by the product of link choice probabilities should be consistent with the original model, i.e.,
This is achieved by considering forward-looking mechanism Value function Myopic 1.
mechanisms of behavior v : Link choice utility V d : Value function
c.f. Shortest Path (SP) problem: Generalization
Value function is the SP cost from aj to destination
Value function is the solution to:
a system of linear equations. (Recurrence relation)
Let's check the Consistency! Link choice probability is given by:
Then we have:
⇒ Consistent with logit route choice model with the universal choice set Now you can model route choice behavior without explicitly defining choice set 1. Decompose route choice into sequential link choices: 2. Describe forward-looking behavioral mechanism by value function: computed This (efficient) computational method of modeling is called: “Recursive Logit (RL) model” Modeling sequence is something more than just dealing with the choice set problem. You can also try other sequences than route choice: . . . . Mode choice: unlinked trip choices Tour choice: sequential destination choices Timing choice: “action (do)/stay (don’t)” choice at every period etc.
Route choice can be interpreted as sequential space choice
Introducing a fixed time-interval (τ) for decision making yields: integrated modeling of route, activity place and duration choices.
Upper: pedestrian flows on streets Lower: ave. activity duration at places (Appx.) Markov decision process (MDP) To more generalize, define . Action : choice behavior (what agent does) . State: situation (where agent is in) that changes as result of action *In route choice (recursive) modeling: Action is directly choice of State

MDP
General modeling framework of sequential decisions Stochastic Dynamic Discrete Choice Model Recursive Logit Modeling action probability under RUM assumption Parameter estimation Reinforcement Learning Learn optimal action probability by a number of trials & results Inverse Reinforcement Learning Learn utility (reward) function from observed actions Action = State Gumbel

•  is computationally efficient
•  No need to explicitly define choice set •  describes dynamic sequential decisions • Not only for route choice modeling • shares common mathematical foundations with other state-of-the-art studies •  Including machine learning
RL model assigns high probabilities to overlapping paths due to IIA property of logit model . considering all feasible paths including cyclic paths . . assign flows (probabilities) on the same links many times often cause computational intractability .
U
A solution is using: . Network-GEV based model Time-space network with time constraint .
Directly translate a (state) network to a GEV network: Multilevel cross-nested structure
*system of nonlinear equations
is inherently acyclic and describes more realistic network structures. (a) Spatial network
(b) Time-space network Pair of time and node (or link)
is simply computable and restricts network states by terminal state. Input: S = {(T,d)},z(T,d) = 1 # terminal state (T, d) Output:   S, z ∈ R|S| t = T 1. While True: 2. 3. # all states at t for s ∈ S(t) for  s' ∈ B(s)  # all states connecting to s 4. 5. 6. s' # S      # if appearing for the first time if S  :=  S ∪ s'     # update the state set z(s') := 0 # initialize the solution z(s') := z(s') + α ss'W(s|s')(zs) πs # recursively update the solution end for end for t := t − 1 if t == 0: break 7. 

 
 9. 10. 11. 12. Logit
. . Counterclockwise way: more overlaps and logit overestimates the probability Without time constraint: more probabilities assigned to cycles Ran out of time… but we recently proposed an efficient dual-type algorithm for Network-GEV based SUE, which is also useful to: •  Parameter estimation •  for entropy-constrained formulation • Dynamic pricing •  based on capacity-constrained assignment formulation Markovian Traffic Equilibrium Assignment based on Network Generalized Extreme Value Model Yuki Oyama*, Yusuke Hara*, Takashi Akama baura Institute of Technology, Department of Civil Engineering, 3-7-5 Toyosu, Koto-ku, Tokyo University of Tokyo, Next Generation Artificial Intelligence Research Center, 7-3-1 Hongo, Bunkyo-ku, Tokyo *Tohoku University, Graduate School of Information Sciences 06 Aramaki-Aoba, Aoba-ku, Sendai, Miyagi
Abstract
This study establishes a novel framework of Markovian traffic equilibrium assignment based on the network generalized extreme value (NGEV) model, which we call NGEV equilibrium assign- ment . The use of the NGEV model in traffic assignment has recently been proposed and enables capturing the path correlation without explicit path enumeration. However, the NGEV equilib- rium assignment has never been investigated in the literature, which has limited the practical Questions ? oyama@shibaura-it.ac.jp . . Fosgerau, M., Frejinger, E., Karlstrom, A., 2013. A link based network route choice model with unrestricted choice set.  Transportation Research Part B: Methodological 56, 70–80. Mai, T., Fosgerau, M., Frejinger, E., 2015. A nested recursive logit model for route choice analysis. Transportation Research Part B: Methodological 75, 100–112. . . Oyama, Y., 2017. A Markovian route choice analysis for trajectory-based urban planning. PhD thesis, The University of Tokyo. Oyama, Y., Hato, E., 2019. Prism-based path set restriction for solving Markovian traffic assignment problem. Transportation Research Part B: Methodological 122, 528–546. . . . Hara, Y., Akamatsu, T., 2014. Stochastic user equilibrium traffic assignment with a network GEV based route choice model. Journal of Japan Society of Civil Engineers, Ser. D3 (Infrastructure Planning and Management) 70, 611–620. Mai, T., 2016. A method of integrating correlation structures for a generalized recursive route choice model.  Transportation Research Part B: Methodological93, 146–161. Papola, A., Marzano, V., 2013. A network generalized extreme value model for route choice allowing implicit route enumeration. Computer-Aided Civil and Infrastructure Engineering 28 (8), 560–580. . Oyama, Y., Hara, Y., Akamatsu, T., 2020. Markovian Traffic Equilibrium Assignment based on Network Generalized Extreme Value Model. arXiv:2009.02033.