This paper is an experience report on the results of an industry-led collaborative project aimed at automating the control of traffic flow within a large city centre. A major focus of the automation was to deal with abnormal or unexpected events such as roadworks, road closures or excessive demand, resulting in periods of saturation of the network within some region of the city. We describe the resulting system which works by sourcing and semantically enriching urban traffic data, and uses the derived knowledge as input to an automated planning component to generate light signal control strategies in real time. This paper reports on the development surrounding the planning component, and in particular the engineering, configuration and validation issues that arose in the application. It discusses a range of lessons learned from the experience of deploying automated planning in the road transport area, under the direction of transport operators and technology developers.

A challenging Earth-observing satellite scheduling problem was recently studied in (Frank, Do and Tran 2016) for which the best resolution approach so far on the proposed benchmark is a time-indexed Mixed Integer Linear Program (MILP) formulation. This MILP formulation produces feasible solutions but is not able to prove optimality or to provide tight optimality gaps, making it difficult to assess the quality of existing solutions. In this paper, we first introduce an alternative disjunctive MILP formulation that manages to close more than half of the instances of the benchmark. This MILP formulation is then relaxed to provide good bounds on optimal values for the unsolved instances. We then propose a CP Optimizer model that consistently outperforms the original time-indexed MILP formulation, reducing the optimality gap by more than 4 times. This Constraint Programming (CP) formulation is very concise: we give its complete OPL implementation in the paper. Some improvements of this CP model are reported resulting in an approach that produces optimal or near-optimal solutions (optimality gap smaller than 1%) for about 80% of the instances. Unlike the MILP formulations, it is able to quickly produce good quality schedules and it is expected to be flexible enough to handle the changing requirements of the application.

Parking is a key component for efficient urban mobility with implications on congestion and the urban landscape. We propose planning strategies for automated, high-density parking lot systems that efficiently execute (i) selection of vehicle destination and (ii) conflict-free motion planning for vehicle input and output operations. The practical performance of the system is demonstrated through simulation using an empirical dataset. The system allows halving the space requirements for parking vehicles while providing fast access to vehicles and keeping low the in-park travel distances when comparing with conventional parking lots.

In this work, we investigate a multi-period Home Health Care Scheduling Problem (HHCSP) under stochastic service and travel times. We first model the deterministic problem as an integer linear programming model that incorporates real-world requirements, such as time windows, continuity of care, workload fairness, inter-visit temporal dependencies. We then extend the model to cope with uncertainty in durations, by introducing chance constraints into the formulation. We propose efficient solution approaches, which provide quantifiable near-optimal solutions and further handle the uncertainties by employing a sampling-based strategy. We demonstrate the effectiveness of our proposed approaches on instances synthetically generated by real-world dataset for both deterministic and stochastic scenarios.

Pruning techniques based on strong stubborn sets have recently shown their potential for SAS+ planning as heuristic search. Strong stubborn sets exploit operator independency to safely prune the search space. Like SAS+ planning, fully observable nondeterministic (FOND) planning faces the state explosion problem. However, it is unclear how stubborn set techniques carry over to the nondeterministics setting. In this paper, we introduce stubborn set pruning to FOND planning. We lift the notion of strong stubborn sets and introduce the conceptually more powerful notion of weak stubborn sets to FOND planning. Our experimental analysis shows that weak stubborn sets are beneficial to an LAO* search, and in particular show favorable performance when combined with symmetries and active operator pruning.

We investigate solvable-unsolvable phase transitions in the single-machine scheduling (SMS) problem. SMS is at the core of practical problems such as telescope and satellite scheduling and manufacturing. To study the solvability phase transition, we construct a variety of instance families param-eterized by the set of the processing times, the window size (deadline minus release time), and the horizon. We empirically establish the phase transition and look for an easy-hard- easy pattern for this family using several common solvers. While in many combinatorial problems a phase transition coincides with typically hard instances, whether or not that is the case with SMS remains an open question, and merits further study.

Recent work in multi-agent path planning has provided a number of optimal and suboptimal solvers that can efficiently find solutions to problems of growing complexity. Solvers based on Conflict-Based Search (CBS) combine single-agent solvers with shared constraints between agents to find feasible solutions. Suboptimal variants of CBS introduce alternate heuristics to avoid conflicts. In this paper we study the multi-agent planning problem in the context of non-holonomic vehicles planning on a lattice. We propose that in addition to using heuristics to avoid conflicts, we can plan using a hierarchy of movement constraints to efficiently avoid conflicts. We develop a new extension to the CBS algorithm, CBS with constraint layering (CBS+CL), which iteratively applies different movement constraint models during the CBS planning process. Our results show that this approach allows us to solve for about 2.4 times more agents in the same amount of time when compared to regular CBS without using a constraint hierarchy.

For the past 25 years, heuristic search has been used to solve domain-independent probabilistic planning problems, but with heuristics that determinise the problem and ignore precious probabilistic information. To remedy this situation, we explore the use of occupation measures, which represent the expected number of times a given action will be executed in a given state of a policy. By relaxing the well-known linear program that computes them, we derive occupation measure heuristics -- the first admissible heuristics for stochastic shortest path problems (SSPs) taking probabilities into account. We show that these heuristics can also be obtained by extending recent operator-counting heuristic formulations used in deterministic planning. Since the heuristics are formulated as linear programs over occupation measures, they can easily be extended to more complex probabilistic planning models, such as constrained SSPs (C-SSPs). Moreover, their formulation can be tightly integrated into i-dual, a recent LP-based heuristic search algorithm for (constrained) SSPs, resulting in a novel probabilistic planning approach in which policy update and heuristic computation work in unison. Our experiments in several domains demonstrate the benefits of these new heuristics and approach.

Temporal logics have been used in autonomous planning to represent and reason about temporal planning problems. However, such techniques have typically been restricted to either (1) representing actions, events, and goals with temporal properties or (2) planning for temporally-extended goals under restrictive assumptions. We introduce Mixed Propositional Metric Temporal Logic (MPMTL) where formulae are built over mixed binary and continuous real variables. We introduce a planner, MTP, that solves MPMTL problems and includes a SAT-solver, model checker for a polynomial fragment of MPMTL, and a forward search algorithm. We extend PDDL 2.1 with MPMTL syntax to create MPDDL and an associated parser. The empirical study shows that MTP outperforms the state-of-the-art PDDL+ planner SMTPlan+ on several domains it performed best on and MTP performs and scales on problem size well for challenging domains with rich temporal properties we create.

One traditional use of critical-path heuristic functions is as effective sufficient criteria for unsolvability. To employ this for dead-end detection, the heuristic function must be evaluated on every new state to be tested, incurring a substantial runtime overhead. We show herein that the exact same dead-end detector can be captured through a nogood, a formula phiOFF computed once prior to search. This is mostly of theoretical interest, as phiOFF is large. We obtain practical variants by instead incrementally generating a stronger nogood psi, that implies phiOFF, online during search, generalizing from already tested states to avoid future heuristic-function evaluations.