=Paper=
{{Paper
|id=Vol-2987/paper1
|storemode=property
|title=Planning with Global State Constraints for Urban Traffic Control
|pdfUrl=https://ceur-ws.org/Vol-2987/paper1.pdf
|volume=Vol-2987
|authors=Franc Ivankovic,Marco Roveri
|dblpUrl=https://dblp.org/rec/conf/gandalf/IvankovicR21
}}
==Planning with Global State Constraints for Urban Traffic Control==
<pdf width="1500px">https://ceur-ws.org/Vol-2987/paper1.pdf</pdf>
<pre>
Planning with Global State Constraints for Urban
Traffic Control
Franc Ivankovic, Marco Roveri
Department of Information Engineering and Computer Science - University of Trento


                                      Abstract
                                      Planning with global state constraints is an extension of classical planning in which some properties of
                                      each state are derived via a set of constraints. This approach allows us to apply planning techniques in
                                      domains involving interconnected physical systems. The crucial feature of such domains is that a single
                                      discrete action affects the state of the entire system in a way that is dependent on the global state. Urban
                                      Traffic Control refers to coordinating traffic signals over an area in order to reduce congestion and delays.
                                      Here we show how this domain can be modelled as a planning problem with global state constraints.

                                      Keywords
                                      Urban traffic control, Automated planning, Global state constraints




1. Introduction and related work
Urban Traffic Control (UTC) is the problem of managing and coordinating traffic signals over
an area in order to optimise traffic flows in a road network [1]. The UTC problem has been
traditionally approached either with complex mathematical models or with simple model of traffic
(see [1] for details). More recently, have been discussed approaches to solve UTC problems
leveraging on state-of-the-art planning and scheduling techniques. The work [2] provides a
detailed survey of the approaches of planning and scheduling for UTC. In [1, 3] it has been
discussed an approach based on PDDL+ [4]: continuous processes are used to control flows of
cars; and traffic light green phases are the control variables to be modified by actions to achieve
the goal of reducing congestions in specific roads. [5] provides a pure PDDL [6] encoding where
each road is associated a discrete density level. Actions operate on the traffic lights to enable
flows and change density levels.
   Planning with Global State Constraints (GSC) [7, 8] is an extension of classical planning
in which some properties of states are determined by a set of constraints common to all states.
This formalism is well suited for applying classical planning methods on domains that involve
a network of interconnected physical systems [9] controlled by discrete controllable variables
(noticeable examples are power networks). The crucial feature of such domains is that a single
discrete action (to change controllable variables), such as opening or closing a switch somewhere,
affects the entire network in a way that is dependent on the global state of the system.

OVERLAY 2021: 3rd Workshop on Artificial Intelligence and Formal Verification, Logic, Automata, and Synthesis,
September 22, 2021, Padova, Italy
" franc.ivankovic@unitn.it (F. Ivankovic); marco.roveri@unitn.it (M. Roveri)
 0000-0001-9483-3940 (M. Roveri)
                                    © 2021 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
 CEUR
 Workshop
 Proceedings
               http://ceur-ws.org
               ISSN 1613-0073       CEUR Workshop Proceedings (CEUR-WS.org)
   We make the following contributions. First, we observe several similarities between the power
network re-configurations problems and the UTC problem: actions like closing/opening of a road,
changing the duration of green light, or redirecting traffic, can potentially affect traffic flow rates
throughout the city in a complex way similarly to corresponding operations in a power network.
Second, we provide an encoding of the UTC problem into the framework of planning with GSC.
Third, we witness the feasibility of the approach by a preliminary experimentation on a small
UTC scenario.


2. Background
Planning with global state constraints [7] allows us to model some properties of states as derived
from so called constraints. These can take a variety of forms depending on the modeled system,
e.g., logical axioms [10] or a system of equations and inequalities [7] This has been shown to
be well suited for domains that involve interconnected physical systems, such as power grids.
These domains are such that each discrete action can change the state of the whole network in a
way that depends on the entire current configuration (e.g., opening/closing a switch may change
power flow in all lines).
   Here we will briefly present a (somewhat simplified) formulation of planning with GSC. The
framework distinguishes primary variables that the planner has direct control over (such as
states of the switches) and secondary variables whose value is computed by so called switched
constraints. The former behave like in classical planning – their domains are finite and discrete,
their values are assigned in the initial state and they persist unless modified by action effects.
Secondary variables can be of any type (in this instance, they are real numbers), and their values
are recomputed in each state. Switched constraints have the form 𝜑 → 𝛾 where 𝜑 is assignment to
a subset of the primary variables, and 𝛾 is an expression over secondary variables. The assignment
to primary variables determines whether a switched constraint is active in a given state. For a state
to be valid, an assignment to secondary variables must exist such that the set of all 𝛾-parts of all
active switched constraints is satisfiable. A plan can only pass through valid states. Consequently,
to be able to apply an action in state 𝑠 i. its preconditions must be satisfiable in 𝑠 and ii. the
resulting state must be valid. For a thorough discussion of the framework refer to [7, 9]. In [9]
it has been shown how to combine GSCs constraints and state-dependent action costs (SDAC)
and how to incorporate them into pattern database (PDB) heuristics. In this framework the cost
of applying an action can be a function of all primary and secondary variables. For instance, in
the the power network reconfiguration domain SDAC account for the fact that it is preferable to
reduce the unsupplied load (consumers without power) over the total time span.


3. Traffic model and encoding in Planning with GSC
We model the traffic network as a directed graph ⟨𝑁, 𝑅⟩, such that 𝑁 = 𝑂 ∪ 𝐷 ∪ 𝑆 and 𝑂, 𝐷, 𝑆
are pairwise disjoint set of nodes. Nodes 𝑂 (for origin) being sources; nodes 𝐷 (for destinations)
being sinks, and nodes 𝑆 (for switches) being intersections. Each edge 𝑅𝑖 ∈ 𝑅 ⊆ 𝑁 × 𝑁 ,
denotes a road (a two way road is modeled with two different edges with opposite directions).
For a node 𝑁𝑖 ∈ 𝑁 we denote with 𝑖𝑛(𝑁𝑖 ) (resp. 𝑜𝑢𝑡(𝑁𝑖 )) the set of incoming (resp. outgoing)
roads.
   Each source generates some number of vehicles that
move towards different sinks. We denote with 𝑟𝑖,𝐷𝑗 ≥ 0
the flow of vehicles on road 𝑅𝑖 with destination 𝐷𝑗 . We
denote with 𝑜𝑖,𝐷𝑘 ≥ 0 the flow of vehicles generated by
source 𝑂𝑖 with the destination 𝐷𝑘 .
   For instance, Fig. 1 shows a simple traffic network
with three sources (𝑂1 , 𝑂2 , 𝑂3 ), one sink (𝐷1 ), three    Figure 1: A simple traffic network.
switches with traffic lights (𝐴, 𝐵, and 𝐶), and 8 roads
(𝑅1 ,...,𝑅5 and abusing notation 𝑂1 ,𝑂2 , 𝑂3 to refer to the edges between the sources and the
switches).
   The values of traffic flows are determined by three types of constraints: i) capacity constraints
associated with roads and intersections, ii) flow conservation constraints, and iii) constraints
associated with different modes of operation of the intersections.

3.1. Capacity constraints
Each road 𝑅𝑖 has a capacity 𝑐𝑅𝑖 ≥ 0, and  ∑︀ the sum 𝑟𝑖 of all flows of vehicles through the road
cannot exceed its capacity, i.e. 𝑟𝑖 =        𝑑𝑘 ∈𝐷 𝑟𝑖,𝑑𝑘 ≤ 𝑐𝑅𝑖 . The total number 𝑑∑︀𝑗 of vehicles
entering the destination 𝐷𝑗 must be equal the number generated at all sources 𝑑𝑗 = 𝑂𝑖 ∈𝑂 𝑜𝑖,𝐷𝑗 .
The total number 𝑜𝑗 of vehicles generated at source  ∑︀ 𝑂𝑗 must be equal the sum of the vehicles
generated at 𝑂𝑗 for all the destinations, i.e. 𝑜𝑗 = 𝐷𝑘 ∈𝐷 𝑜𝑗,𝐷𝑘 .

3.2. Flow conservation constraints
Every intersection has a set of flow conservation constraints – one for each incoming or one
              and for each destination. That is, for an outgoing road 𝑅𝑖 at an intersection 𝑆ℎ , we
outgoing road∑︀
have 𝑟𝑖,𝐷𝑘 = 𝑅𝑗 ∈𝑖𝑛(𝑆ℎ ) 𝑓𝑅𝑖 ,𝑅𝑗 ,𝐷𝑘 where 𝑓𝑅𝑖 ,𝑅𝑗 ,𝐷𝑘 is the traffic flow moving from the road 𝑅𝑖
to the road 𝑅𝑗 towards sink 𝐷𝑘 . (The constraints for incoming roads have the same form except
the sum is over 𝑜𝑢𝑡(𝑆ℎ ).)

3.3. Intersection configurations
           flow 𝑓𝑅𝑖 ,𝑅𝑗 between roads 𝑅𝑖 and 𝑅𝑗 is the sum of the flows to all destinations,
The total ∑︀
𝑓𝑅𝑖 ,𝑅𝑗 = 𝐷𝑘 ∈𝐷 𝑓𝑅𝑖 ,𝑅𝑗 ,𝐷𝑘 . This number is limited by the product of the total cycle length 𝑇 ,
the portion 𝑡𝑅𝑖 ,𝑅𝑗 ,𝑘 of the cycle during which the light between roads 𝑅𝑖 and 𝑅𝑗 is green under
configuration 𝑘, and the capacity 𝑐𝑅𝑖 ,𝑅𝑗 of the switch. The value of 𝑡𝑅𝑖 ,𝑅𝑗 ,𝑘 depends on the
configuration of the intersection 𝑆ℎ which is modelled as a primary variable 𝐿ℎ , with the domain
𝒟(𝐿ℎ ) = [0 . . . 𝑁ℎ ] (with 𝑁ℎ ≥ 0). Denoting the primary variable 𝐿ℎ and the value 𝑘 ∈ 𝒟(𝐿ℎ )
the switched constraint is 𝐿ℎ = 𝑘 → 𝑓𝑅𝑖 ,𝑅𝑗 ≤ 𝑐𝑅𝑖 ,𝑅𝑗 𝑇 𝑡𝑅𝑖 ,𝑅𝑗 ,𝑘 . For each of the configurations,
there is one such constraint associated with each pair of roads. (We remark that, that the values
of 𝑇 and 𝑐𝑅𝑖 ,𝑅𝑗 are the same in all constraints.) When defining the configurations, we need to
make sure that the resulting combination of green/red lights or open/closed roads is compatible
(e.g. if traffic cannot flow between 𝑅𝑖 and 𝑅𝑗 at the same time as between 𝑅𝑚 and 𝑅𝑛 , then
𝑡𝑅𝑚 ,𝑅𝑛 ≤ 𝑇 − 𝑡𝑅𝑖 ,𝑅𝑗 ).
   A complete assignment to the different secondary variables 𝑟𝑖,𝑅𝑗 , 𝑐𝑅𝑘 ,𝑅𝑙 and 𝑡𝑅𝑚 ,𝑅𝑛 , defined
above satisfying the different respective constraints, represents one possible traffic situation of
the traffic network at a given time instant.

3.4. Actions, initial condition, goal and the plan cost
Actions change the configurations of intersections by assigning values to primary variables. For
each intersections 𝑆ℎ ∈ 𝑆 and for each 𝑘 ∈ 𝒟(𝐿ℎ ) we have an action switch_Lh _to_k
whose only effect is to enforce 𝐿ℎ = 𝑘. Such actions therefore activate/de-activate a subset of the
switched constraints.
  The initial state is an assignment to the primary variables only (that in turn activate respective
switched constraints). The goal in this domain is typically to remove a congestion on a given
road. As such it might have the form of 𝑟𝑖 ≤ 𝑣, where 𝑣 is some value of the vehicle flow that we
want to achieve.
  If we employ state-dependent action costs, we can also    ∑︀ assign additional costs to having
congested roads. The cost of every action becomes 𝑐𝑎 = 𝑅𝑖 ∈𝑅 max (𝑟𝑖 − 𝑣𝑖 , 0), where 𝑣𝑖 is
some traffic congestion threshold for road 𝑅𝑖 . (This is similar to previous work on applying
planning to UTC [11] that adds penalties for road congestions.)


4. Experimental evaluation
In order to show the feasibility of the proposed encoding we encoded the simple traffic network
illustrated in Figure 1 in the specification language of the GSC Planner [7, 8] available from
https://github.com/patrikhaslum/gscplanner, configured to leverage on the Gurobi® (https://www.
gurobi.com/) optimization solver to deal with the GSC constraints. We run the GSC Planner on a
Linux Laptop equipped with an Intel i5 processor and 16Gb of RAM. The GSC Planner was able
to solve this small instance in less than a second.


5. Conclusions and Future Work
In this paper we have shown how to encode the UTC problem in the framework of planning with
global constraints. The encoding has been experimented on a simple traffic network witnessing
the feasibility of the approach.
   We envision several possible directions for future work. First, we intend to carry out a more
thorough experimental evaluation considering large networks and possibly different encodings.
The previous experience in solving power network domains (that have many similarities with
the UTC problem) [9] suggest that the approach may scale up to larger instances. We want also
investigate how to enrich this encoding to integrate additional constraints and state-dependent
action costs [9, 11]. Finally, we also intend to carry out a more thorough comparison with the
approaches based on PDDL+ [1, 3, 11].
Acknowledgments
This work is partially funded by the grant MOSES, Bando interno 2020 Università di Trento
"Covid 19".


References
 [1] L. Chrpa, D. Magazzeni, K. McCabe, T. L. McCluskey, M. Vallati, Automated planning for
     urban traffic control: Strategic vehicle routing to respect air quality limitations, Intelligenza
     Artificiale 10 (2016) 113–128.
 [2] I. Cenamor, L. Chrpa, F. Jimoh, T. McCluskey, M. Vallati, Planning & scheduling applica-
     tions in urban traffic management, The UK Planning and Scheduling Special Interest Group
     (UK PlanSIG), 2014. http://eprints.hud.ac.uk/id/eprint/22801/.
 [3] T. L. McCluskey, M. Vallati, Embedding automated planning within urban traffic manage-
     ment operations, in: ICAPS 2017, AAAI Press, 2017, pp. 391–399.
 [4] M. Fox, D. Long, Modelling mixed discrete-continuous domains for planning, J. Artif.
     Intell. Res. 27 (2006) 235–297.
 [5] A. Pozanco, S. Fernández, D. Borrajo, Urban traffic control assisted by AI planning and
     relational learning, in: A. L. C. Bazzan, F. Klügl, S. Ossowski, G. Vizzari (Eds.), Agents
     in Traffic and Transportation (ATT 2016), volume 1678 of CEUR Workshop Proceedings,
     CEUR-WS.org, 2016.
 [6] D. V. McDermott, The 1998 AI planning systems competition, AI Mag. 21 (2000) 35–55.
 [7] F. Ivankovic, P. Haslum, S. Thiébaux, V. Shivashankar, D. S. Nau, Optimal planning with
     global numerical state constraints, in: ICAPS 2014, 2014.
 [8] P. Haslum, F. Ivankovic, M. Ramírez, D. Gordon, S. Thiébaux, V. Shivashankar, D. S.
     Nau, Extending classical planning with state constraints: Heuristics and search for optimal
     planning, J. Artif. Intell. Res. 62 (2018) 373–431.
 [9] F. Ivankovic, D. Gordon, P. Haslum, Planning with global state constraints and state-
     dependent action costs, in: ICAPS 2018, AAAI Press, 2019, pp. 232–236.
[10] S. Thiébaux, J. Hoffmann, B. Nebel, In defense of PDDL axioms, Artif. Intell. 168 (2005)
     38–69.
[11] M. Vallati, E. Scala, L. Chrpa, A hybrid automated planning approach for urban real-
     time routing of connected vehicles, in: 24th IEEE International Conference on Intelligent
     Transportation - ITSC2021, IEEE, 2021. To appear.

</pre>