Automated Planning for Urban Traffic Management

1 Introduction

SimplyfAI was a UK research council grant funded project 1 , recently concluded successfully, which aimed towards solving air quality problems caused by road traffic emissions [McCluskey and Vallati, 2017]. The problem areas are large urban spaces such as major cities throughout the world, where currently there are means of controlling traffic, but these controls are not being used effectively to minimise delay or traffic emissions, especially in exceptional circumstances. These problems are likely to increase with the expected rise in urbanisation this century.

AI techniques have been used in road transportation [Various, 2007], and more recently, the benefits of such planningbased approaches for supporting traffic control have been argued. For instance, Jimoh et al. (2013) introduced the idea of using automated planning in UTC as a planning aid to be used in exceptional circumstances, e.g. in situations where roads within a network of roads become blocked due to some unanticipated incident. Shah et al. (2013) provided a model for dealing with road traffic accident management. A scheduling approach (called SURTRAC) has been proposed by Xie et al. (2012). They focused on the exploitation of decentralised scheduling techniques to synchronise a group of traffic light clusters. Each intersection is controlled by a scheduling agent that communicates with neighbours to predict the future traffic demand, and to minimise predicted vehicles waiting time at the traffic signal.

1 UK NERC grant reference number NE/N007239/1

Transport studies often use microscopic models to simulate and validate off-line traffic control techniques [Treiber and Kesting, 2013]. This entails modeling at the individual vehicle level, where each vehicle is a single element. A similar microscopic representation was used in a planning approach to route vehicles to respect air quality limitations in urban networks [Chrpa et al., 2015], utilising a basic STRIPS representation. The exploitation of planning approaches on microscopic models has a number of drawbacks, however, the main one being that it has limited scalability. Also, if centralised planning is used to control individual cars, then this assumes that the position of each vehicle is known by urban traffic authorities, and they can communicate to and control each vehicle's route.

Two recent lines of research 2 showed the feasibility of using AI planning to generate actions to deal with unexpected circumstances in complex urban traffic control situations, by utilising macroscopic simulation models [Treiber and Kesting, 2013]. Gulic et al's system [Guli´c et al., 2016] involves joining together a SUMO simulator [Krajzewicz et al., 2012] to an AI Planner, via a monitoring and execution module called the "Intelligent Autonomic System". The planning representation was done using PDDL 2.1 [Fox and Long, 2003], with no explicit representation of vehicles in the planner. Instead, traffic concentrations on road links are represented by relative density descriptors, such as very-low, low, medium and high. Traffic light change actions are enumerated to cover all the ways that a particular configuration would effect the arrangements of road links. The second work [Vallati et al., 2016] was inspired by works such as [Lin, 2011; van den Berg et al., 2004], where traffic is modelled using "flows", and then analysed through model-predictive controllers. Vallati et al. exploit PDDL+ [Fox and Long, 2006] for encoding a flow model of vehicles through trafficlight controlled junctions. The length of traffic light phases are under the control of the planner, that can decide to prioritise some traffic flows, in order to reach specified goals. Goals are specified in terms of numbers of vehicles desired on some critical road links.

2 These two achievements were recognised in October 2015 as they were joint winners of the "The Second COST ARTS Competition: Increasing the Resilience of Road Traffic Support Systems by the Use of Autonomics" https://helios.hud.ac.uk/cost/comp2.php

We made the decision to follow the PDDL+ approach on the basis of the accuracy and granularity of its continuous representation: the PDDL+ encoding was closer to the representation used in traffic simulation as shown by the data sources above. Also, PDDL+'s representational accuracy supports the extension of the system to incorporate other available "interventions" (such as variable speed limits).

2 The SimplyfAI Architecture

The AI Expert encodes PDDL+ models of transport interventions - for example, traffic light changes at each junction and the flow rate of connected road links (refer to Figure 1). The expert assembles static information such as the structural layout of the road links and their capacities. When the planning function is triggered, the expected vehicle flow into the region is obtained from historical records, and initial distribution of vehicles, are automatically assembled into an initial state. A

goal triggers the running of the planning function. Currently we are using goals which specify limits on vehicles numbers on specified links in order to decongest areas of the region, although we are experimenting with more subtle goals which limit vehicle emissions on links (though these two kinds of goals are clearly related, as congestion implies greater emissions). The output of the planning is a plan (called a strategy in UTC parlance) containing green light timing changes, and its effect can be evaluated in traffic simulators such as SUMO and AIMSUN 3 . Results from the SimplyfAI project show that the planning system can generate effective strategies for dealing with exceptional situations and for reducing emissions.

The tool that will be demonstrated forms part of the SimplyfAI architecture, but is specifically aimed at traffic delay minimisation. The demonstration will show how a centralised automated planning techniques can deal with the exceptional event of road closure(s) in a network by generating an effective plan for traffic light changes to achieve this goal. Plans are generated in real time (in a matter of seconds) using the PDDL+ planner UPMurphi [Della Penna et al., 2009], improved with a domain-specific heuristic and reasoning on an automatically reformulated representation of the PDDL+ model. The human-readable PDDL+ model, which is too complex for a planning engine to reason about but allows domain experts to inspect its validity, is reformulated by grounding operators and exploiting the notion of PDDL constants. The demonstration will focus on showing how, when selected roads are closed in a large region of the Manchester metropolitan area (shown in Figure 2), the PDDL+ planning system is able to re-route vehicles efficiently by producing a plan which changes the green light phases of routes through each of the intersections. The approach exploits a heuristic approach that allows to identify the minimum number of traffic lights that need to be controlled by the planner, in order to minimise the overall impact on the rest of the region.

The demonstrated system performs, firstly, the reformulation of the PDDL+ model. Then the system performs "strategy generation": that is the generation of temporal schemes of interventions which when executed cause a change in the flows of traffic which meet some goal criteria. After that, starting from the generated strategy, a heuristic approach is exploited for improving the quality of the strategy as follows: since the generated strategy is aimed at changing light timings within a region to solve a specific goal, the overall goal of minimising delay may be compromised. The quality is increased by removing the junctions from the new strategy's control that have minimal contribution to achieving the goal, and restoring their strategies to the standard optimal strategy that they were previously assigned to.

The structure of the network, and the junctions that are affected by the strategies are shown using a directed graph representation, allowing to inspect and discuss all the aspects of the plan. In addition, a comparison between generated strategies and the manually optimised green light phases -designed by Manchester traffic experts- will be shown in a video, using the AIMSUN traffic simulator.

3 https://www.aimsun.com/