In this paper, we describe a pilot implementation and field test of a recently developed approach to real-time adaptive traffic signal control. The pilot system, called SURTRAC (Scalable Urban Traffic Control), follows the perspective of recent work in multi-agent planning and implements a decentralized, schedule-driven approach to traffic signal control. Under this approach, each intersection independently (and asynchronously) computes a schedule that optimizes the flow of currently approaching traffic through that intersection, and uses this schedule to decide when to switch green phases. The traffic outflows projected by this schedule are then communicated to the intersection's downstream neighbors, to increase visibility of vehicles entering their respective planning horizons. This process is repeated as frequently as once per second in rolling horizon fashion, to provide real-time responsiveness to changing traffic conditions and coordinated signal network behavior. After summarizing this basic approach to adaptive traffic signal control and the domain challenges it is intended to address, we describe the pilot implementation of SURTRAC and its application to a nine-intersection road network in Pittsburgh, Pennsylvania. Both the SURTRAC architecture for interfacing with the detection equipment, hardware controller and communication network at a given intersection and the extensions required to account for unreliable sensor data are discussed. Finally, we present the results of a pilot test of the system, where SURTRAC is seen to achieve major reductions in travel times and vehicle emissions over pre-existing signal timings.

We address efficient planning of maintenance activities in infrastructural networks, inspired by the real-world problem of servicing a highway network. A road authority is responsible for the quality, throughput and maintenance costs of the network, while the actual maintenance is performed by autonomous, third-party contractors. From a (multi-agent) planning and scheduling perspective, many interesting challenges can be identified. First, planned maintenance activities might have an uncertain duration due to unexpected delays. Second, since maintenance activities influence the traffic flow in the network, careful coordination of the planned activities is required in order to minimise their impact on the network throughput. Third, as we are dealing with selfish agents in a private-values setting, the road authority faces an incentive-design problem to truthfully elicit agent costs, complicated by the fact that it needs to balance multiple objectives. The main contributions of this work are: 1) multi-agent coordination on a network level through a novel combination of planning under uncertainty and dynamic mechanism design, applied to real-world problems, 2) accurate modelling and solving of maintenance-planning problems and 3) empirical exploration of the complexities that arise in these problems. We introduce a formal model of the problem domain, present experimental insights and identify open challenges for both the planning and scheduling as well as the mechanism design communities.

Mining companies have complex supply chains that start from the mining location and stretch thousands of kilometers to the end customer in a different country and continent. The logistics of moving the materials from mines to ship is composed of series of optimization problems like berth allocation , ship scheduling , stockyard scheduling , and rail scheduling , which are individually NP-hard. In this paper, we present a scheduling application, called as IBM Optimization: Mine to Ship , for end-to-end integrated operations scheduling. The application is built on IBM ILOG ODM Enterprise with advanced features like rescheduling under deviations and disturbances, and maintenance scheduling. The modeling and computational complexity of integrated scheduling optimization is tamed using hybrid optimization technique that leverages mathematical programming and constraint programming. The application will benefit the mining companies with increased resource usage, higher throughput, reduced cost of operations, and higher revenue.

The electricity network balancing problem consists of ensuring that the electricity demands of the consumers are met by the committed supply. Constraints are imposed on the different elements of the network, so that damage to the equipment is prevented when transformers are stepped up or down, or generation is increased. We consider this problem within zones, which are sub-networks constructed using carefully chosen decomposition principles. The automation of decision making in electricity networks is a step forward in their management which is necessary for coping with the increase in power system complexity that we expect in the near term. In this paper we explore the deployment of planning techniques to solve the zone-balancing problem. Embedding electricity networks in a domain description presents new challenges for planning. The key point is that the propagation of information requires complex updates to the state when an action is applied. We have developed a method in which the computation of the critical numeric quantities is performed calling an external power flow equation solver, demonstrating a clean interface between the planner and this domain-specific computation. This solver allows us to move the power flow computations outside of the planning process and update the values efficiently. We also examine a second important feature of this problem, which is the interaction between exogenous events and constraints over the entire plan trajectory within a zone.

A robot coexisting with humans must not only be able to perform physical tasks, but must also be able to interact with humans in a socially appropriate manner. In many social settings, this involves the use of social signals like gaze, facial expression, and language. In this paper, we describe an application of planning to task-based social interaction using a robot that must interact with multiple human agents in a simple bartending domain. We show how social states are inferred from low-level sensors, using vision and speech as input modalities, and how we use the knowledge-level PKS planner to construct plans with task, dialogue, and social actions, as an alternative to current mainstream methods of interaction management. The resulting system has been evaluated in a real-world study with human subjects.

In this paper, we consider the problem of designing personalised museum visits. Given a set of preferences and constraints a visitor might express on her visit, the aim is to compute the tour that best matches her requirements. The museum visits problem can be expressed as a planning problem, with cost optimization. We show how to bound the number of steps required to find an optimal solution, via the resolution of an instance of the shortest complete walk problem. We also point out an alternative encoding of the museum visits problem as an optimization problem with pseudo-Boolean constraints and a linear objective function. We have evaluated several constraints solvers, a planner and a tailored solver on a number of benchmarks, representing various instances of the museum visits problem corresponding to real museums. Our empirical results show the feasibility of both the planning and the constraint programming approaches. Optimal solutions can be computed for short visits and ``practically good'' solutions for much longer visits.

Search And Tracking (SAT) is the problem of searching for a mobile target and tracking it after it is found. As this problem has important applications in search-and-rescue and surveillance operations, recently there has been increasing interest in equipping unmanned aerial vehicles (UAVs) with autonomous SAT capabilities. State-of-the-art approaches to SAT rely on estimating the probability density function of the target's state and solving the search control problem in a greedy fashion over a short planning horizon (typically, a one-step lookahead). These techniques suffer high computational cost, making them unsuitable for complex problems. In this paper, we propose a novel approach to SAT, which allows us to handle big geographical areas, complex target motion models and long-term operations. Our solution is to track the target reactively while it is in view and to plan a recovery strategy that relocates the target every time it is lost, using a high-performing automated planning tool. The planning problem consists of deciding where to search and which search patterns to use in order to maximise the likelihood of recovering the target. We show experimental results demonstrating the potential of our approach.

This paper describes the design and implementation of a planning-based socially intelligent agent built to help young children with Autism Spectrum Conditions acquire social communication skills. We explain how planning technology allowed us to satisfy the requirements relating to the agent's design that we identified through our consultations with children and carers as well as our review of best practices for autism intervention. We discuss the design principles we implemented, the engineering challenges we faced and the lessons we learned in building the pedagogical agent. We conclude by presenting extensive experimental results concerning the agent's efficacy.

In large and complex planning problems, there will almost inevitably be aspects that are not relevant to a specific problem instance. Thus, identifying and removing irrelevant parts from an instance is one of the most important techniques for scaling up automated planning. We examine the path-based relevance analysis method, which is safe (preserves plan existence and cost) and powerful but has exponential time complexity, and show how to make it run in polynomial time with only a minimal loss of pruning power.

The problem of searching for a plan with cost at most equal to a given absolute bound has attracted interest recently, and several search algorithms tailored specifically to this problem have been proposed. We investigate instead how to adapt planning heuristics to this setting. A few of the resulting heuristics, used in a greedy bounded-cost search, perform better than previous and baseline methods, but only by a small margin. Making effective use of the cost bound in bounded-cost planning, it appears, remains a challenge.