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. 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.

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.

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 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.

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. 𝑜 𝑗 = ∑︀ 𝐷 𝑘 ∈𝐷 𝑜 𝑗,𝐷 𝑘 .

Flow conservation constraints

Every intersection has a set of flow conservation constraints -one for each incoming or one outgoing road and for each destination. That is, for an outgoing road 𝑅 𝑖 at an intersection 𝑆 ℎ , we 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 𝑜𝑢𝑡(𝑆 ℎ ).)

Intersection configurations

The total flow 𝑓 𝑅 𝑖 ,𝑅 𝑗 between roads 𝑅 𝑖 and 𝑅 𝑗 is the sum of the flows to all destinations, 𝑓 𝑅 𝑖 ,𝑅 𝑗 = ∑︀ 𝐷 𝑘 ∈𝐷 𝑓 𝑅 𝑖 ,𝑅 𝑗 ,𝐷 𝑘 . 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.

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_L h _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.)

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.

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].