Smith, Stephen F.


Tackling Large-Scale Home Health Care Delivery Problem with Uncertainty

AAAI Conferences

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.


Scalable Approaches to Home Health Care Scheduling Problems with Uncertainty

AAAI Conferences

In this work, we consider the weekly home health care scheduling problem with time windows, continuity of care, workload fairness, and inter-visit temporal dependency, and service/travel time uncertainties. We formulate the problem as a chance constrained mathematical model. We further apply Lagrangian relaxation, exploit the separable structure of the problem, and handle the uncertainties by employing a sampling-based strategy. Experiments have been conducted on a real-world dataset to demonstrate the effectiveness and efficiency of our proposed approaches.


Viewing Traffic Signal Control as a Market-Driven Economy

AAAI Conferences

In this paper, economic principles and the paradigm of a game are used to create a signal control strategy. The game structure is not formal (as in game theory), but the idea of a game is used nonetheless. That is, instead of using the standard techniques of minimum greens, maximum greens, and gaps to control the signal indications, an economically based game structure is employed. The intersection’s space is viewed as a scarce commodity whose use is determined through a bidding process. Movement Managers manage the vehicle departures for specific turning movements. Arriving motorists pay the Movement Managers an initial fee, and make voluntary contributions as they perceive necessary to arrange times of entry for them. Movement Managers submit bids for use of the intersection’s space and the highest bidders win. Distributed processing and connected vehicle technology are seen as the mechanisms by which implementation would be feasible. The value in such an idea is that one can study and reach an understanding of the economics that underlie effective traffic control.


Smart Urban Signal Networks: Initial Application of the SURTRAC Adaptive Traffic Signal Control System

AAAI Conferences

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.


Incremental Management of Oversubscribed Vehicle Schedules in Dynamic Dial-A-Ride Problems

AAAI Conferences

In this paper, we consider the problem of feasibly integrating new pick-up and delivery requests into existing vehicle itineraries in a dynamic, dial-a-ride problem (DARP) setting. Generalizing from previous work in oversubscribed task scheduling, we define a controlled iterative repair search procedure for finding an alternative set of vehicle itineraries in which the overall solution has been feasibly extended to include newly received requests. We first evaluate the performance of this technique on a set of DARP feasibility benchmark problems from the literature. We then consider its use on a real-world DARP problem, where it is necessary to accommodate all requests and constraints must be relaxed when a request cannot be feasibly integrated. For this latter analysis, we introduce a constraint relaxation post processing step and consider the performance impact of using our controlled iterative search over the current greedy search approach.


Iterative Improvement Algorithms for the Blocking Job Shop

AAAI Conferences

This paper provides an analysis of the efficacy of a known iterative improvement meta-heuristic approach from the AI area in solving the Blocking Job Shop Scheduling Problem (BJSSP) class of problems. The BJSSP is known to have significant fallouts on practical domains, and differs from the classical Job Shop Scheduling Problem (JSSP) in that it assumes that there are no intermediate buffers for storing a job as it moves from one machine to another; according to the BJSSP definition, each job has to wait on a machine until it can be processed on the next machine. In our analysis, two specific variants of the iterative improvement meta-heuristic are evaluated: (1) an adaptation of an existing scheduling algorithm based on the Iterative Flattening Search and (2) an off-the-shelf optimization tool, the IBM ILOG CP Optimizer, which implements Self-Adapting Large Neighborhood Search. Both are applied to a reference benchmark problem set and comparative performance results are presented. The results confirm the effectiveness of the iterative improvement approach in solving the BJSSP; both variants perform well individually and together succeed in improving the entire set of benchmark instances.


Schedule-Driven Coordination for Real-Time Traffic Network Control

AAAI Conferences

Real-time optimization of the dynamic flow of vehicle traffic through a network of signalized intersections is an important practical problem. In this paper, we take a decentralized, schedule-driven coordination approach to address the challenge of achieving scalable network-wide optimization. To be locally effective, each intersection is controlled independently by an on-line scheduling agent. At each decision point, an agent constructs a schedule that optimizes movement of the observable traffic through the intersection, and uses this schedule to determine the best control action to take over the current look-ahead horizon. Decentralized coordination mechanisms, limited to interaction among direct neighbors to ensure scalability, are then layered on top of these asynchronously operating scheduling agents to promote overall performance. As a basic protocol, each agent queries for newly planned output flows from its upstream neighbors to obtain an optimistic projection of future demand. This projection may incorporate non-local influence from indirect neighbors depending on horizon length. Two additional mechanisms are then introduced to dampen ``nervousness'' and dynamic instability in the network, by adjusting locally determined schedules to better align with those of neighbors. We present simulation results on two traffic networks of tightly-coupled intersections that demonstrate the ability of our approach to establish traffic flows with lower average vehicle wait times than both a simple isolated control strategy and other contemporary coordinated control strategies that use moving average forecast or traditional offset calculation.


Reports of the AAAI 2011 Conference Workshops

AI Magazine

The AAAI-11 workshop program was held Sunday and Monday, August 7–18, 2011, at the Hyatt Regency San Francisco in San Francisco, California USA. The AAAI-11 workshop program included 15 workshops covering a wide range of topics in artificial intelligence. The titles of the workshops were Activity Context Representation: Techniques and Languages; Analyzing Microtext; Applied Adversarial Reasoning and Risk Modeling; Artificial Intelligence and Smarter Living: The Conquest of Complexity; AI for Data Center Management and Cloud Computing; Automated Action Planning for Autonomous Mobile Robots; Computational Models of Natural Argument; Generalized Planning; Human Computation; Human-Robot Interaction in Elder Care; Interactive Decision Theory and Game Theory; Language-Action Tools for Cognitive Artificial Agents: Integrating Vision, Action and Language; Lifelong Learning; Plan, Activity, and Intent Recognition; and Scalable Integration of Analytics and Visualization. This article presents short summaries of those events.


Reports of the AAAI 2011 Conference Workshops

AI Magazine

The AAAI-11 workshop program was held Sunday and Monday, August 7–18, 2011, at the Hyatt Regency San Francisco in San Francisco, California USA. The AAAI-11 workshop program included 15 workshops covering a wide range of topics in artificial intelligence. The titles of the workshops were Activity Context Representation: Techniques and Languages; Analyzing Microtext; Applied Adversarial Reasoning and Risk Modeling; Artificial Intelligence and Smarter Living: The Conquest of Complexity; AI for Data Center Management and Cloud Computing; Automated Action Planning for Autonomous Mobile Robots; Computational Models of Natural Argument; Generalized Planning; Human Computation; Human-Robot Interaction in Elder Care; Interactive Decision Theory and Game Theory; Language-Action Tools for Cognitive Artificial Agents: Integrating Vision, Action and Language; Lifelong Learning; Plan, Activity, and Intent Recognition; and Scalable Integration of Analytics and Visualization. This article presents short summaries of those events.


Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

AAAI Conferences

This paper presents a meta-heuristic algorithm for solving the Flexible Job Shop Scheduling Problem (FJSSP). This strategy, known as Iterative Flattening Search (IFS), iteratively applies a relaxation-step, in which a subset of scheduling decisions are randomly retracted from the current solution; and a solving-step, in which a new solution is incrementally recomputed from this partial schedule. This work contributes two separate results: (1) it proposes a constraint-based procedure extending an existing approach previously used for classical Job Shop Scheduling Problem; (2) it proposes an original relaxation strategy on feasible FJSSP solutions based on the idea of randomly breaking the execution orders of the activities on the machines and opening the resource options for some activities selected at random. The efficacy of the overall heuristic optimization algorithm is demonstrated on a set of well-known benchmarks.