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.
Urban Trafcfi Control (UTC) is the problem of managing and coordinating trafcfi signals over
an area in order to optimise trafcfi flows in a road network [
Planning with Global State Constraints (GSC) [
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.
Planning with global state constraints [
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 [
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 trafcfi 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.
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. = ∑︀∈ , .
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 (ℎ).)
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 trafcfi 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 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 [
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 [
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) [