Stephen F. Smith

JAAMAS Journal 2026 Journal Article

Wasp-like Agents for Distributed Factory Coordination

• Vincent A. Cicirello
• Stephen F. Smith

Abstract Agent-based approaches to manufacturing scheduling and control have gained increasing attention in recent years. Such approaches are attractive because they offer increased robustness against the unpredictability of factory operations. But the specification of local coordination policies that give rise to efficient global performance and effectively adapt to changing circumstances remains an interesting challenge. In this paper, we present a new approach to this coordination problem, drawing on various aspects of a computational model of how wasp colonies coordinate individual activities and allocate tasks to meet the collective needs of the nest. We focus specifically on the problem of configuring parallel multi-purpose machines in a factory to best satisfy product demands over time. Wasp-like computational agents that we call routing wasps act as overall machine proxies. These agents use a model of wasp task allocation behavior, coupled with a model of wasp dominance hierarchy formation, to determine which new jobs should be accepted into the machine's queue. If you view our system from a market-oriented perspective, the policies that the routing wasps independently adapt for their respective machines can be likened to policies for deciding when to bid and when not to bid for arriving jobs. We benchmark the performance of our system on the real-world problem of assigning trucks to paint booths in a simulated vehicle paintshop. The objective of this problem is to minimize the number of paint color changes accrued by the system, assuming no a priori knowledge of the color sequence or color distribution of trucks arriving in the system. We demonstrate that our system outperforms the bidding mechanism originally implemented for the problem as well as another related adaptive bidding mechanism.

ICRA Conference 2024 Conference Paper

Probabilistic 3D Multi-Object Cooperative Tracking for Autonomous Driving via Differentiable Multi-Sensor Kalman Filter

• Hsu-Kuang Chiu
• Chien-Yi Wang
• Min-Hung Chen
• Stephen F. Smith

Current state-of-the-art autonomous driving vehicles mainly rely on each individual sensor system to perform perception tasks. Such a framework’s reliability could be limited by occlusion or sensor failure. To address this issue, more recent research proposes using vehicle-to-vehicle (V2V) communication to share perception information with others. However, most relevant works focus only on cooperative detection and leave cooperative tracking an underexplored research field. A few recent datasets, such as V2V4Real, provide 3D multi-object cooperative tracking benchmarks. However, their proposed methods mainly use cooperative detection results as input to a standard single-sensor Kalman Filter-based tracking algorithm. In their approach, the measurement uncertainty of different sensors from different connected autonomous vehicles (CAVs) may not be properly estimated to utilize the theoretical optimality property of Kalman Filter-based tracking algorithms. In this paper, we propose a novel 3D multi-object cooperative tracking algorithm for autonomous driving via a differentiable multi-sensor Kalman Filter. Our algorithm learns to estimate measurement uncertainty for each detection that can better utilize the theoretical property of Kalman Filter-based tracking methods. The experiment results show that our algorithm improves the tracking accuracy by 17% with only 0. 037x communication costs compared with the state-of-the-art method in V2V4Real. Our code and videos are available at the URL and the URL.

IJCAI Conference 2021 Conference Paper

Incorporating Queueing Dynamics into Schedule-Driven Traffic Control

• Hsu-Chieh Hu
• Allen M. Hawkes
• Stephen F. Smith

Key to the effectiveness of schedule-driven approaches to real-time traffic control is an ability to accurately predict when sensed vehicles will arrive at and pass through the intersection. Prior work in schedule-driven traffic control has assumed a static vehicle arrival model. However, this static predictive model ignores the fact that the queue count and the incurred delay should vary as different partial signal timing schedules (i. e. , different possible futures) are explored during the online planning process. In this paper, we propose an alternative arrival time model that incorporates queueing dynamics into this forward search process for a signal timing schedule, to more accurately capture how the intersection’s queues vary over time. As each search state is generated, an incremental queueing delay is dynamically projected for each vehicle. The resulting total queueing delay is then considered in addition to the cumulative delay caused by signal operations. We demonstrate the potential of this approach through microscopic traffic simulation of a real-world road network, showing a 10-15% reduction in average wait times over the schedule-driven traffic signal control system in heavy traffic scenarios.

ICAPS Conference 2020 Conference Paper

Learning Model Parameters for Decentralized Schedule-Driven Traffic Control

• Hsu-Chieh Hu
• Stephen F. Smith

Model-based intersection optimization strategies that produce signal timings over a specified optimization horizon have been widely investigated for urban traffic signal control, and recent work in this area produced a scalable approach to real-time traffic control based on a decentralized schedule-driven optimization model. In this approach, a scheduling agent is associated with each intersection. Each agent senses the traffic approaching its intersection through local sensors and in real-time constructs a schedule that minimizes the cumulative wait time of vehicles approaching the intersection over the current look-ahead horizon. Intersections then exchange schedule information with their neighbors to achieve network level coordination. Although the approach is general and has demonstrated substantial success, its effectiveness in a given road network depends on the extent to which various parameters of the model, e. g, maximum green time, are adjusted to match that network's actual flow conditions over time. To address this problem, we propose a two-stage hierarchical structure that combines online planning and reinforcement learning. Reinforcement learning is applied to adjust the parameters of the model over a longer time-scale. On the other hand, online planning is used to compute the schedule for managing the traffic signals in the shorter term. We demonstrate how this hybrid approach outperforms the original approach in real-time traffic signal control problems.

IROS Conference 2019 Conference Paper

Cooperative Schedule-Driven Intersection Control with Connected and Autonomous Vehicles

• Hsu-Chieh Hu
• Stephen F. Smith
• Rick Goldstein

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to improve the efficiency of traffic flow in complex urban road networks. In this approach, a scheduling agent is associated with each intersection. Each agent senses the traffic approaching its intersection and in real-time constructs a schedule that minimizes the cumulative wait time of vehicles approaching the intersection over the current look-ahead horizon. In this paper, we propose a cooperative algorithm that utilizes both connected and autonomous vehicles (CAV) and schedule-driven traffic control to create better traffic flow in the city. The algorithm enables an intersection scheduling agent to adjust the arrival time of an approaching platoon through use of wireless communication to control the velocity of vehicles. The sequence of approaching platoons is thus shifted toward a new shape that has smaller cumulative delay. We demonstrate how this algorithm outperforms the original approach in a real-time traffic signal control problem.

SoCS Conference 2019 Conference Paper

Learning and Utilizing Interaction Patterns among Neighborhood-Based Heuristics

• Chung-Yao Chuang
• Stephen F. Smith

This paper proposes a method for learning and utilizing potentially useful interaction patterns among neighborhood-based heuristics. It is built upon a previously proposed framework designed for facilitating the task of combining multiple neighborhood-based heuristics. Basically, an algorithm derived from this framework will operate by chaining the heuristics in a pipelined fashion. Conceptually, we can view this framework as an algorithmic template that contains two user-defined components: 1) the policy H for selecting heuristics, and 2) the policy L for choosing the length of the pipeline that chains the selected heuristics. In this paper, we will develop a method that automatically derives a policy H by analyzing the experience collected from running a baseline algorithm. This analysis will distill potentially useful patterns of interactions among heuristics, and give an estimate for the frequency of using each pattern. The empirical results on three problem domains show the effectiveness of the proposed approach.

ICAPS Conference 2019 Conference Paper

Using Bi-Directional Information Exchange to Improve Decentralized Schedule-Driven Traffic Control

• Hsu-Chieh Hu
• Stephen F. Smith

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to improve the efficiency of traffic flow in complex urban road networks. In this approach, a scheduling agent is associated with each intersection. Each agent senses the traffic approaching its intersection and in real-time constructs a schedule that minimizes the cumulative wait time of vehicles approaching the intersection over the current look-ahead horizon. In order to achieve network level coordination in a scalable manner, scheduling agents communicate only with their direct neighbors. Each time an agent generates a new intersection schedule it communicates its expected outflows to its downstream neighbors as a prediction of future demand and these outflows are appended to the downstream agent’s locally perceived demand. In this paper, we extend this basic coordination algorithm to additionally incorporate the complementary flow of information reflective of an intersection’s current congestion level to its upstream neighbors. We present an asynchronous decentralized algorithm for updating intersection schedules and congestion level estimates based on these bi-directional information flows. By relating this algorithm to the self-optimized decision making of the basic operation, we are able to approach network-wide optimality and reduce inefficiency due to strictly self-interested intersection control decisions.

AAMAS Conference 2018 Conference Paper

Bi-Directional Information Exchange in Decentralized Schedule-Driven Traffic Control

• Hsu-Chieh Hu
• Stephen F. Smith

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to improve the efficiency of traffic flow in complex urban road networks. In this approach, each time an agent generates a new intersection schedule it communicates its expected outflows to its downstream neighbors as a prediction of future demand and these outflows are appended to the downstream agent’s locally perceived demand. In this paper, we extend this basic coordination protocol to additionally incorporate the complementary flow of information reflective of an intersection’s current congestion level to its upstream neighbors. We present an asynchronous decentralized algorithm for updating intersection schedules and congestion level estimates based on these bi-directional information flows. By relating this algorithm to the self-optimized decision making of the basic protocol, we are able to approach networkwide optimality and reduce inefficiency due to myopic intersection control decisions.

ICAPS Conference 2017 Conference Paper

Coping with Large Traffic Volumes in Schedule-Driven Traffic Signal Control

• Hsu-Chieh Hu
• Stephen F. Smith

Recent work in decentralized, schedule-driven traffic control has demonstrated the ability to significantly improve traffic flow efficiency in complex urban road networks. However, in situations where vehicle volumes increase to the point that the physical capacity of a road network reaches or exceeds saturation, it has been observed that the effectiveness of a schedule-driven approach begins to degrade, leading to progressively higher network congestion. In essence, the traffic control problem becomes less of a scheduling problem and more of a queue management problem in this circumstance. In this paper we propose a composite approach to real-time traffic control that uses sensed information on queue lengths to influence scheduling decisions and gracefully shift the signal control strategy to queue management in high volume/high congestion settings. Specifically, queue-length information is used to establish weights for the sensed vehicle clusters that must be scheduled through a given intersection at any point, and hence bias the wait time minimization calculation. To compute these weights, we develop a model in which successive movement phases are viewed as different states of an Ising model, and parameters quantify strength of interactions. To ensure scalability, queue information is only exchanged between direct neighbors and the asynchronous nature of local intersection scheduling is preserved. We demonstrate the potential of the approach through microscopic traffic simulation of a real-world road network, showing a 60% reduction in average wait times over the baseline schedule-driven approach in heavy traffic scenarios. We also report initial field test results, which show the ability to reduce queues during heavy traffic periods.

IJCAI Conference 2017 Conference Paper

Softpressure: A Schedule-Driven Backpressure Algorithm for Coping with Network Congestion

• Hsu-Chieh Hu
• Stephen F. Smith

We consider the problem of minimizing the the delay of jobs moving through a directed graph of service nodes. In this problem, each node may have several links and is constrained to serve one link at a time. As jobs move through the network, they can pass through a node only after they have been serviced by that node. The objective is to minimize the delay jobs incur sitting on queues waiting to be serviced. Two popular approaches to this problem are backpressure algorithm and schedule-driven control. In this paper, we present a hybrid approach of those two methods that incorporates the stability of queuing theory into the schedule-driven control. We then demonstrate how this hybrid method outperforms the other two in a real-time traffic signal control problem, where the nodes are traffic lights, the links are roads, and the jobs are vehicles. We show through simulations that, in scenarios with heavy congestion, the hybrid method results in 50% and 15% reductions in delay over schedule-driven control and backpressure respectively. A theoretical analysis also justifies our results.

ICAPS Conference 2017 Conference Paper

Tackling Large-Scale Home Health Care Delivery Problem with Uncertainty

• Cen Chen 0001
• Zachary B. Rubinstein
• Stephen F. Smith
• Hoong Chuin Lau

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.

IJCAI Conference 2016 Conference Paper

Distributed Decoupling of Multiagent Simple Temporal Problems

• Jayanth Krishna Mogali
• Stephen F. Smith
• Zachary B. Rubinstein

We propose a new distributed algorithm for decoupling the Multiagent Simple Temporal Network (MaSTN) problem. The agents cooperatively decouple the MaSTN while simultaneously optimizing a sum of concave objectives local to each agent. Several schedule flexibility measures are applicable in this framework. We pose the MaSTN decoupling problem as a distributed convex optimization problem subject to constraints having a block angular structure; we adapt existing variants of Alternating Direction Method of Multiplier (ADMM) type methods to perform decoupling optimally. The resulting algorithm is an iterative procedure that is guaranteed to converge. Communication only takes place between agents with temporal inter-dependences and the information exchanged between them is carried out in a privacy preserving manner. We present experimental results for the proposed method on problems of varying sizes, and demonstrate its effectiveness in terms of solving quality and computational cost.

JAAMAS Journal 2016 Journal Article

Robust allocation of RF device capacity for distributed spectrum functions

• Stephen F. Smith
• Zachary B. Rubinstein
• John Chapin

Abstract Real-time awareness of radio spectrum use across frequency, geography and time is crucial to effective communications and information gathering in congested airway environments, yet acquiring this awareness presents a challenging sensing and data integration problem. A recent proposal has argued that real-time generation of spectrum usage maps might be possible through the use of existing radios in the area of interest, by exploiting their sensing capacity when they are not otherwise being used. In this paper, we assume this approach and consider the task allocation problem that it presents. We focus specifically on the development of a network-level middleware for task management, that assigns resources to prospective mapping applications based on a distributed model of device availability, and allows mapping applications (and other related RF applications) to specify what is required without worrying about how it will be accomplished. A distributed, auction-based framework is specified for task assignment and coordination, and instantiated with a family of minimum set cover algorithms for addressing “coverage” tasks. An experimental analysis is performed to investigate and quantify two types of performance benefits: (1) the basic advantage gained by exploiting knowledge of device availability, and (2) the additional advantage gained by adding redundancy in subregions where the probability of availability of assigned devices is low. To assess the effectiveness of our minimum set cover algorithms, we compute optimal solutions to a static version of the real-time coverage problem and compare performance of the algorithms to these upper bound solutions.

ICRA Conference 2015 Conference Paper

Mobile manufacturing of large structures

• David A. Bourne
• Howie Choset
• Humphrey Hu
• George Kantor
• Chris Niessl
• Zachary B. Rubinstein
• Reid G. Simmons
• Stephen F. Smith

Assembly of large structures requires large fixtures, often referred to as monuments. Their cost and massive size limit flexibility and scalability of the manufacturing process. Numerous small mobile robots can replace these large structures and, therefore, replicate the efficiency of the assembly line with far more flexibility. An assembly line made up of mobile manipulators can easily and rapidly be reconfigured to support scalability and a varied product mix, while allowing for near optimal resource assignment. The challenge to using small robots in place of monuments is making their joint behavior precise enough to accomplish the task and efficient enough to execute subtasks in a reasonable period of time. In this paper, we describe a set of techniques that we combine to achieve the necessary precision and overall efficiency to build a large structure. We describe and demonstrate these techniques in the context of a testbed we implemented for assembling a wing ladder.

ICAPS Conference 2013 Conference Paper

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

• Stephen F. Smith
• Gregory J. Barlow
• Xiao-Feng Xie 0001
• Zachary B. Rubinstein

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.

ICAPS Conference 2012 Conference Paper

Iterative Improvement Algorithms for the Blocking Job Shop

• Angelo Oddi
• Riccardo Rasconi
• Amedeo Cesta
• Stephen F. Smith

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.

ICAPS Conference 2012 Conference Paper

Schedule-Driven Coordination for Real-Time Traffic Network Control

• Xiao-Feng Xie 0001
• Stephen F. Smith
• Gregory J. Barlow

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.

KER Journal 2012 Journal Article

Scheduling safe movement of air traffic in crowded air spaces

• David W. Hildum
• Stephen F. Smith

Abstract This paper considers the problem of generating conflict-free movement schedules for a set of vehicles that are operating simultaneously in a common airspace. In both civilian air traffic management and military air campaign planning contexts, it is crucial that the movements of different vehicles be coordinated so as to avoid collisions and near misses. Our approach starts from a view of airspace management as a 4D resource allocation problem, where the space in which vehicles must maneuver is itself managed as a capacitated resource. We introduce a linear octree representation of airspace capacity to index vector-based vehicle routes and efficiently detect regions of potential conflict. Generalizing the notion of contention-based search heuristics, we next define a scheduling algorithm that proceeds by first solving a relaxed version of the problem to construct a spatial capacity profile (represented as an octree), and then using spatio-temporal regions where demand exceeds capacity to make conflict-avoiding vehicle routing and scheduling decisions. We illustrate the utility of this basic representation and search algorithm in two ways. First, to demonstrate the overall viability of the approach, we present experimental results using data representing a realistically sized air campaign planning domain. Second, we define a more abstract notion of ‘encounter set’, which tolerates some amount of conflict on the assumption that on-board deconfliction processes can take appropriate avoidance maneuvers at execution time, and show that generation of this more abstract form of predictive guidance can be obtained without loss in computational efficiency.

IJCAI Conference 2011 Conference Paper

Iterative Flattening Search for the Flexible Job Shop Scheduling Problem

• Angelo Oddi
• Riccardo Rasconi
• Amedeo Cesta
• Stephen F. Smith

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.

IJCAI Conference 2009 Conference Paper

• Laura M. Hiatt
• Terry L. Zimmerman
• Stephen F. Smith
• Reid Simmons

In this paper, we describe an approach to scheduling under uncertainty that achieves scalability through a coupling of deterministic and probabilistic reasoning. Our specific focus is a class of oversubscribed scheduling problems where the goal is to maximize the reward earned by a team of agents in a distributed execution environment. There is uncertainty in both the duration and outcomes of executed activities. To ensure scalability, our solution approach takes as its starting point an initial deterministic schedule for the agents, computed using expected duration reasoning. This initial agent schedule is probabilistically analyzed to find likely points of failure, and then selectively strengthened based on this analysis. For each scheduled activity, the probability of failing and the impact that failure would have on the schedule’s overall reward are calculated and used to focus schedule strengthening actions. Such actions generally entail fundamental trade-offs; for example, modifications that increase the certainty that a high-reward activity succeeds may decrease the schedule slack available to accommodate uncertainty during execution. We describe a principled approach to handling these trade-offs based on the schedule’s “expected reward, ” using it as a metric to ensure that all schedule modifications are ultimately beneficial. Finally, we present experimental results obtained using a multi-agent simulation environment, which confirm that executing schedules strengthened in this way result in significantly higher rewards than are achieved by executing the corresponding initial schedules.

EAAI Journal 2008 Journal Article

Airlift mission monitoring and dynamic rescheduling

• David E. Wilkins
• Stephen F. Smith
• Laurence A. Kramer
• Thomas J. Lee
• Timothy W. Rauenbusch

We describe the Flight Manager Assistant (FMA), a prototype system, designed to support real-time management of airlift operations at the USAF Air Mobility Command (AMC). In current practice, AMC flight managers are assigned to manage individual air missions. They tend to be overburdened with associated data monitoring and constraint checking, and generally react to detected problems in a local, myopic fashion. Consequently, decisions taken for one mission can often have deleterious effects on others. FMA combines two key capabilities for overcoming these problems: (1) intelligent monitoring of incoming information (for example, weather, airport operations, aircraft status) and recognition of those situations that require corrective action and (2) dynamic rescheduling of missions in response to detected problems, both to understand the global implications of changed circumstances and to determine appropriate rescheduling actions. FMA builds on two existing technologies: an execution-monitoring framework previously applied to small-unit operations and control of robots, and a dynamic scheduling tool that is transitioning into operational use in AMC's Tanker/Airlift Control Center. FMA's dynamic-mediation module provides for collaborative mission management by different planning and execution offices by structuring communication for decision making.

EAAI Journal 2008 Journal Article

Combining variants of iterative flattening search

• Angelo Oddi
• Amedeo Cesta
• Nicola Policella
• Stephen F. Smith

Iterative flattening search (ifs) is an iterative improvement heuristic schema for makespan minimization in scheduling problems. Given an initial solution, ifs iteratively interleaves a relaxation-step, which randomly retracts some search decisions, and an incremental solving step (or flattening-step) to recompute a new solution. The process continues until a stop condition is met and the best solution found is returned. In recent work we have created a uniform software framework to analyze component techniques that have been proposed in ifs approaches. In this paper we combine basic components to obtain hybrid variants and perform a detailed experimental evaluation of their performance. Specifically, we examine the utility of: (1) operating with different relaxation strategies and (2) using different searching strategies to built a new solution. We present a two-step experimental evaluation: (a) an extensive explorative evaluation with a spectrum of parameter combination; (b) a time-intensive evaluation of the best ifs combinations emerged from the previous. The experimental results shed light on weaknesses and strengths of the different variants improving the current understanding of this family of meta-heuristics.

ICAPS Conference 2008 Conference Paper

Linear Relaxation Techniques for Task Management in Uncertain Settings

• Pradeep Varakantham
• Stephen F. Smith

In this paper, we consider the problem of assisting a busy user in managing her workload of pending tasks. We assume that our user is typically oversubscribed, and is invariably juggling multiple concurrent streams of tasks (or work flows) of varying importance and urgency. There is uncertainty with respect to the duration of a pending task as well as the amount of follow-on work that may be generated as a result of executing the task. The user's goal is to be as productive as possible; i. e., to execute tasks that realize the maximum cumulative payoff. This is achieved by enabling the assistant to provide advice about where and how to shed load when all tasks cannot be done. A simple temporal problem with uncertainty and preferences (called an STPPU) provides a natural framework for representing the user's current set of tasks. However, current STPPU solution techniques are inadequate as a basis for generating advice in this context, since they are applicable only in the restrictive case where all pending tasks can be accomplished within time constraints and our principal concern is support in oversubscribed circumstances. We present two techniques that are based on linear relaxation for solving the this oversubscribed problem. Given an ordering of tasks, these algorithms identify which tasks to ignore, which to compress and by how much, to maximize quality. We show experimentally that our approaches perform significantly better than techniques adapted from prior research in oversubscribed scheduling.

UAI Conference 2008 Conference Paper

New Techniques for Algorithm Portfolio Design

• Matthew J. Streeter
• Stephen F. Smith

We present and evaluate new techniques for designing algorithm portfolios. In our view, the problem has both a scheduling aspect and a machine learning aspect. Prior work has largely addressed one of the two aspects in isolation. Building on recent work on the scheduling aspect of the problem, we present a technique that addresses both aspects simultaneously and has attractive theoretical guarantees. Experimentally, we show that this technique can be used to improve the performance of state-of-the-art algorithms for Boolean satisfiability, zero-one integer programming, and A.I. planning.

ICAPS Conference 2007 Conference Paper

Constructing Conflict-Free Schedules in Space and Time

• David W. Hildum
• Stephen F. Smith

This paper addresses the problem of constructing plans and schedules for resources that must obey spatial constraints in addition to time and capacity constraints. Spatial constraints are relevant in environments that involve mobile resources whose movements must be coordinated to avoid collisions and near-misses. In air-campaign planning, for example, aircraft are allocated to missions that must be flown concurrently within a localized and often heavily populated environment. Mission routes tend to be generated dynamically and must ensure that sufficient spatial separation is maintained at all times among all aircraft. We present a solution to this class of problems that treats the standard resource-allocation problem as a four-dimensional one, where the space in which resources must maneuver is itself managed as a capacitated resource. Underlying our approach is a representation of spatial capacity that uses a linear octree structure for indexing vector-based vehicle routes. Generalizing the notion of contention-based search heuristics, we present an algorithm that first solves a relaxed version of the problem to construct a spatial capacity profile (represented as an octree), and then uses spatio-temporal regions where demand exceeds capacity to make conflict-avoiding vehicle routing and scheduling decisions. To demonstrate the viability of the approach we present experimental results using data from a realistically sized air-campaign planning domain.

AAMAS Conference 2007 Conference Paper

Distributed Management of Flexible Times Schedules

• Stephen F. Smith
• Anthony Gallagher
• Terry Zimmerman
• Laura Barbulescu
• Zachary Rubinstein

We consider the problem of managing schedules in an uncertain, distributed environment. We assume a team of collaborative agents, each responsible for executing a portion of a globally pre-established schedule, but none possessing a global view of either the problem or solution. The goal is to maximize the joint quality obtained from the activities executed by all agents, given that, during execution, unexpected events will force changes to some prescribed activities and reduce the utility of executing others. We describe an agent architecture for solving this problem that couples two basic mechanisms: (1) a "flexible times" representation of the agent's schedule (using a Simple Temporal Network) and (2) an incremental rescheduling procedure. The former hedges against temporal uncertainty by allowing execution to proceed from a set of feasible solutions, and the latter acts to revise the agent's schedule when execution is forced outside of this set of solutions or when execution events reduce the expected value of this feasible solution set. Basic coordination with other agents is achieved simply by communicating schedule changes to those agents with inter-dependent activities. Then, as time permits, the core local problem solving infra-structure is used to drive an inter-agent option generation and query process, aimed at identifying opportunities for solution improvement through joint change. Using a simulator to model the environment, we compare the performance of our multi-agent system with that of an expected optimal (but non-scalable) centralized MDP solver.

ICAPS Conference 2007 Conference Paper

Using Decision Procedures Efficiently for Optimization

• Matthew J. Streeter
• Stephen F. Smith

Optimization problems are often solved by making repeated calls to a decision procedure that answers questions of the form "Does there exist a solution with cost at most k? ". In general the time required by the decision procedure varies widely as a function of k, so it is natural to seek a query strategy that minimizes the time required to find an (approximately) optimal solution. We present a simple query strategy with attractive theoretical guarantees. In case the same decision procedure is used for multiple optimization problems, we discuss how to tailor the query strategy to the sequence of problems encountered. We demonstrate the power of our query strategy by using it to create (i) a modified version of SatPlan that finds provably approximately optimal plans quickly and (ii) a modified branch and bound algorithm for job shop scheduling that yields improved upper and lower bounds.

AAAI Conference 2006 Conference Paper

An Asymptotically Optimal Algorithm for the Max k-Armed Bandit Problem

• Matthew J. Streeter
• Stephen F. Smith

We present an asymptotically optimal algorithm for the max variant of the k-armed bandit problem.

ICAPS Conference 2006 Conference Paper

Exploiting the Power of Local Search in a Branch and Bound Algorithm for Job Shop Scheduling

• Matthew J. Streeter
• Stephen F. Smith

This paper presents three techniques for using an iterated local search algorithm to improve the performance of a state-of-the-art branch and bound algorithm for job shop scheduling. We use iterated local search to obtain (i) sharpened upper bounds, (ii) an improved branch-ordering heuristic, and (iii) and improved variable-selection heuristic. On randomly-generated instances, our hybrid of iterated local search and branch and bound outperforms either algorithm in isolation by more than an order of magnitude, where performance is measured by the median amount of time required to find a globally optimal schedule. We also demonstrate performance gains on benchmark instances from the OR library.

ICAPS Conference 2006 Conference Paper

Incremental Scheduling to Maximize Quality in a Dynamic Environment

• Anthony Gallagher
• Terry L. Zimmerman
• Stephen F. Smith

We present techniques for incrementally managing schedules in domains where activities accrue quality as a function of the time and resources allocated to them and the goal is to maximize the overall quality of actions executed over time. The scheduling problem of interest is both over-subscribed and dynamic; there is generally more to do than is possible within imposed deadlines, and opportunities to execute new, potentially higher payoff activities continually arrive. Like other dynamic domains, schedule stability and computational cost concerns argue for the use of incremental techniques in this context. The novel emphasis on maintaining schedules that produce "high value" results when faced with a changing environment differentiates this problem focus from that of previous research. We develop and evaluate methods for incrementally maintaining schedules that maximize the quality (or utility) of executed activities. We contrast the performance of our incremental techniques to that of comparable schedule (re)generation techniques with respect to quality, stability and cost considerations. The results clearly favor incremental scheduling in this context, and suggest opportunities for broader schedule improvement search.

ICAPS Conference 2006 Conference Paper

Resource Contention Metrics for Oversubscribed Scheduling Problems

• Laurence A. Kramer
• Stephen F. Smith

We investigate a task insertion heuristic for oversubscribed scheduling problems, max-availability, that uses a simple estimate of resource contention to assign tasks to intervals expected to have the best worst case resource availability. Prior research in value and variable ordering heuristics for scheduling problems indicated that sophisticated, but more costly measures of resource contention can outperform simpler ones by more reliably pruning the search space. We demonstrate that for oversubscribed, priority-based problems where a feasible, optimal solution may not even exist, max-availability generates schedules of similar quality to other contention based heuristics with much less computational overhead.

ICAPS Conference 2005 Conference Paper

Charecterizing the Distribution of Low-Makespan Schedules in the Job Shop Scheduling Problem

• Matthew J. Streeter
• Stephen F. Smith

We characterize the search landscape of the job shop scheduling problem (JSSP), with a focus on schedules whose makespan is optimal or near-optimal. Building on previous work on the 'big valley' distribution of local optima, we use special branch and bound algorithms to examine in greater detail the extent to which JSSP search spaces conform to the intuitive picture conveyed by the words 'big valley'. We also examine how this changes as a function of the job: machine ratio. We find that for square JSSPs, low-makespan schedules are tightly clustered in a small region of the search space, and the size of this region decreases as the makespan gets closer to optimality. As the job: machine ratio increases beyond 1, however, low-makespan schedules become dispersed throughout the search space. We discuss the reasons for this and provide analytical results for two limiting cases. We close with an examination of neighborhood exactness in the JSSP, which illustrates some limitations of the big valley picture for JSSP landscapes.

AAAI Conference 2005 Conference Paper

Exploiting Temporal Flexibility to Obtain High Quality Schedules

• Nicola Policella
• Stephen F. Smith

We consider a schedule optimization problem where each activity to be scheduled has a duration-dependent quality profile, and activity durations must be determined that maximize overall quality within given deadline and resource constraints. To solve this quality maximization problem, prior work has proposed a hybrid search scheme, where a linear programming solver for optimally setting the durations of temporally related activities is embedded within a larger search procedure that incrementally posts sequencing constraints to resolve resource conflicts. Under this approach, dual concerns of establishing feasibility and optimizing quality are addressed in an integrated fashion. In this paper, we propose an alternative approach, where feasibility and optimization concerns are treated separately: first, we establish a resource-feasible partial order schedule, assuming minimum durations for all activities; second, these fixed duration constraints are relaxed and quality optimal durations are determined. Experimental results indicate a tradeoff: when resource capacity constraints are loose, the integrated hybrid approach performs comparably to the separated scheme. However, in problems with tighter capacity constraints we find that separation of concerns enables both better solving capability and higher quality results. Following from these results, we discuss potential synergy between problem objectives of maintaining temporal flexibility and maximizing quality.

ICAPS Conference 2005 Conference Paper

Maximizing Availability: A Commitment Heuristic for Oversubscribed Scheduling Problems

• Laurence A. Kramer
• Stephen F. Smith

In this paper we reconsider a "task-swapping" procedure for improving schedules in the face of resource oversubscription. Prior work has demonstrated that use of a retraction heuristic to determine which tasks to rearrange in an existing schedule allows for addition of new tasks which would otherwise fail to be scheduled. The existing task swap procedure employs a variable ordering heuristic for task insertion that is the same as the retraction heuristic, but scored in the reverse. That is, the least constrained tasks are retracted, and of these the most constrained are committed first. Value selection for commitment is defaulted to a task’s earliest feasible start time. We have found that by applying a value selection heuristic, max-availability, to the choice of where to assignthe retracted tasks, both solution quality and runtime performance of task swap can be improved greatly. Max-availability considers resource contention for an unassigned task and places it where availability is predicted to be maximal over the range of that task. This heuristic is applicable not only in a repair context, but can also promote resource levelling in the context of constructive task allocation. Finally, we show that use of max-availability in task swapping promotes schedule stability when compared to the prior greedy task insertion policy.

ICAPS Conference 2005 Conference Paper

Retaining Flexibility to Maximize Quality: When the Scheduler Has the Right to Decide Activity Durations

• Xiaofang Wang
• Stephen F. Smith

In many resource constrained scheduling applications, the ability to vary task durations provides another degree of freedom for resolving resource conflicts. Furthermore, when each task is associated with a duration-dependent quality profile, activity durations must be determined to maximize overall quality while respecting process deadlines and resource capacity constraints. In this paper, we formulate this type of scheduling problem, which we refer to generally as quality maximization. We develop and empirically evaluate a new precedence constraint posting (PCP) algorithm, along with a number of search control heuristics for solving this class of problems. Our PCP algorithm incorporates linear optimization to set activity durations at each step, and search control heuristics direct the search toward resource feasibility. A central concept in the heuristics we define is use of a measure that combines an activity’s reducible duration with its quality profile as a basis for determining how to resolve resource conflicts. This concept is found to yield heuristics that exhibit superior performance. Surprisingly, we also find that use of a simple local estimation of quality degradation at each posting step leads to better performance than use of an exact computation at dramatically reduced computation expense. Overall, the experimental analysis indicates that a good heuristic must strike the right balance between minimizing quality loss at each step and retaining flexibility for future duration reduction.

AAAI Conference 2004 System Paper

CMRadar: A Personal Assistant Agent for Calendar Management

• Pragnesh Jay Modi
• Stephen F. Smith

One of the more compelling visions for agents research is the development of “personal assistant agents” that are tasked with making people and organizations more efficient by autonomously handling routine tasks on behalf of their users. Most recently, several researchers including ourselves have embarked on a large research project, called The Radar Project, whose overall goal is to develop a personalized agent that is able to assist its user in a wide range of everyday tasks. Within this larger project, we are concerned with the more focused task of managing a user’s calendar. While isolated aspects of calendar management have been investigated before, in this paper, we present CMRadar, a complete agent with capabilities ranging across the full spectrum of calendar management, from natural language processing of incoming scheduling-related emails, to making autonomous scheduling decisions, to negotiating with other users, to user interfacing and visualization. Although many research issues remain, we believe CMRadar is the first end-to-end agent for automated calendar management.

ICAPS Conference 2004 Conference Paper

Generating Robust Schedules through Temporal Flexibility

• Nicola Policella
• Stephen F. Smith
• Amedeo Cesta
• Angelo Oddi

This paper considers the problem of generating partial order schedules (POS), that is, schedules which retain temporal flexibility and thus provide some degree of robustness the face of unpredictable execution circumstances. We begin by proposing a set of measures for assessing and comparing the robustness properties of alternative POSs. Then, using common solving framework, we develop two orthogonal procedures for constructing a POS. The first, which we call the resource envelope based approach, uses computed bounds on cumulative resource usage (i. e., a resource envelope) to identify potential resource conflicts, and progressively winnows the total set of temporally feasible solutions into a smaller set of resource feasible solutions by resolving detected conflicts. The second, referred to as the earliest start time approach, instead uses conflict analysis of a specific (i. e., earliest start time) solution to generate an initial fixed-time schedule, and then expands this solution to a set of resource feasible solutions in a post-processing step. We evaluate the relative effectiveness of these two procedures on a set of project scheduling benchmark problems. As might be expected, the second approach, by virtue of its more focused analysis, is found be a more efficient POS generator. Somewhat counterintuitively, however, it is also found to produce POSs that are more robust.

ECAI Conference 2004 Conference Paper

Local Search for Heuristic Guidance in Tree Search

• Alexander Nareyek
• Stephen F. Smith
• Christian M. Ohler

ICAPS Conference 2004 Conference Paper

Task Swapping for Schedule Improvement: A Broader Analysis

• Laurence A. Kramer
• Stephen F. Smith

In this paper we analyze and extend a recently developed "task-swapping procedure" for improving schedules in oversubscribed situations. In such situations, there are tasks which cannot be directly added to the current schedule without introducing capacity conflicts. A schedule is improved if one or more of these tasks can be feasibly included, and the goal of task swapping is to rearrange some portion of the current schedule to make this possible. Key to effective task swapping is an ability to exploit the scheduling flexibility inherent in the constraints associated with various scheduled tasks, and previous work has shown that the use of retraction heuristics that favor tasks with greater rescheduling flexibility can give rise to strong schedule improvement capabilities. We extend this work by developing and evaluating several improvements to the core task swapping procedure. We introduce three pruning techniques and show that each significantly improves computational efficiency while maintaining solution quality. We then investigate the possibility of improving the "end" solutions by stochastically exploring the "neighborhood" around them, and demonstrate that improved solutions are possible given the ability to spend additional time.

ICAPS Conference 2000 Conference Paper

Mixed-Initiative Resource Management: The AMC Barrel Allocator

• Marcel A. Becker
• Stephen F. Smith

! n Ill[,. palwr, we drscrib,. Ihe Barr’<l..lll:,, ’a£of,:’..,.cheduling Leo[ drvt: lopt-d for day-to-day allocation m’d m", Jatagemrtlt of airlift and tmhker l’t’, ’.,. OllrC, ’. ’.., ilt the [’SAI". ’kit" Mobility {’<)lrllll~. ~lld (AMt’j. The syat, en. i utilizes ml illcrenmnt+~l arid configura[~i, z con~trailit-l, a. -, cd ~carch frameworkto pi’O~, iduar.;ttlgc of &UtOl|l, tt. t: d;.u|d ~t: mi-, J. lit,)tltated -whrduhng c; l, pabilities, including generating an initial solution It) the fleet assignmenl problrm, selL. clive re-optimize! ion el resource allocations uo i: lcorporare new higher priority missions while nlininlizing sohlt. ion C]lallge, mergingo[" previously planned mission. -, t. o reduce non-productive flying t, ime, attd generation and synchronization of tanker missions to satisfy air refueling requiremerits. In situations where all mission requirements calulot b(! incL. the system can generate mlcl compareel. It ernalive constraint relaxation eel ions. The currrnt version of Barrel Allocator will ¯ t as a module of go illto operational use el. AMC (-~[{Please 2. 0 of AM. s Consolidated Air Mobility Planning System (CAMPS) in early 2000.

ICAPS Conference 1998 Conference Paper

Profile-Based Algorithms to Solve Multiple Capacitated Metric Scheduling Problems

• Amedeo Cesta
• Angelo Oddi
• Stephen F. Smith

Though CSP scheduling models have tended to assumefairly general representations of temporal constraints, most work has restricted attention to problems that require allocation of simple, unit-capacity r~=, ources. This paper considers an extendedclass of scheduling problems where resources have capacity to simultaneously support more than one activity, and resource availability at any point in time is consequently a function of whether sufficient unallocated capacity remains. Wepresent a progression of algorithms for solving such multiple-capacitated scheduling problems, and evaluate the performance of each with respect to problemsolving ability and quality of solutions generated. A previously reported algorithm, namedtheConflict FreeSolution Algorithm (CFSA), is first evaluatedagainst a set of problemsof increasing dimensionand is shownto be of limited effectiveness. Twovariations of this algorithm are then introduced which incorporate measuresof temporal flexibility as an alternative heuristic basis for directing the search, and the variant makingbroadest use of these search heuristics is showntoyieldsignificant performance improvement. Observations aboutthetendency of theCFSAsolution approach to produce unnecessarilyoverconstrained solutions thenleadtodevelopment of a second heuristic algorithm, namedEarliest Start Time Algorithm (ESTA). ESTAis shown to be the most effective of the set, both in terms of its ability to efficiently solve problemsof increasing scale and its ability to produceschedules that minimizeoverall completiontime while retaining solution robustness.

ICAPS Conference 1996 Conference Paper

A Constraint Satisfaction Approach to Makespan Scheduling

• Cheng-Chung Cheng
• Stephen F. Smith

In this paper, we consider the application a constraint satisfaction problem solving (CSP) framework recently developed for deadline scheduling to more commonly studied problems of schedule optimization. Our hypothesis is two-fold: (1) that CSP scheduling techniques can provide a basis for developing high-performance approximate solution procedures in optimization contexts, and (2) that the representational assumptions underlying CSP models allow these procedures to naturally accommodate the idiosyncratic constraints that complicate most real-world applications. We focus specifically on the objective criterion of makespan minimization, which has received the most attention within the job shop scheduling literature. We define an extended solution procedure somewhat unconventionally by reformulating the makespan problem as one of solving a series of different but related deadline scheduling problems, and embedding a simple CSP procedure as the subproblem solver. We summarize results of an empirical evaluation of our procedure performed on a range of previously studied benchmark problems. Our procedure is found to provide strong cost/performance, producing solutions competitive with those obtained using recently reported shifting bottleneck search procedures at reduced computational expense. To demonstrate generality, we also consider application of our procedure to a more complicated, multi-product hoist scheduling problem. With only minor adjustments, our procedure is found to significantly outperform previously published procedures for solving this problem across a range of input assumptions.

ECAI Conference 1994 Conference Paper

A High Performance Scheduler for an Automated Chemistry Workstation

• Robert J. Aarts
• Stephen F. Smith

AAAI Conference 1993 Conference Paper

Slack-Based Heuristics for Constraint Satisfaction Scheduling

• Stephen F. Smith

In this paper, we define and empirically evaluate new heuristics for solving the job shop scheduling problem with non-relaxable time windows. The hypothesis underlying our approach is that by approaching the problem as one of establishing sequencing constraints between pairs of operations requiring the same resource (as opposed to a problem of assigning start times to each operation) and by exploiting previously developed analysis techniques for limiting search through the space of possible sequencing decisions, simple, localized look-ahead techniques can yield problem solving performance comparable to currently dominating techniques that rely on more sophisticated analysis of resource contention. We define a series of attention focusing heuristics based on simple analysis of the temporal flexibility associated with different sequencing decisions, and a similarly motivated heuristic for determining how to sequence a given operation pair. Performance results are reported on a suite of benchmark problems previously investigated by two advanced approaches, and our simplified look-ahead analysis techniques are shown to provide comparable problem solving leverage at reduced computational cost.

ICRA Conference 1991 Conference Paper

Coordinating Space Telescope operations in an integrated planning and scheduling architecture

• Nicola Muscettola
• Stephen F. Smith
• Amedeo Cesta
• Daniela D'Aloisi

The authors describe HSTS, an integrated planning and scheduling architecture that has been applied to the problem of generating observation schedules for the Hubble Space Telescope. HSTS deals with the problem of the interaction of resource allocation and auxiliary task expansion during schedule development by viewing planning and scheduling as two complementary aspects in the construction of the behavior of a system. The authors first describe how HSTS specifies the dynamics of a system, how it represents schedules at multiple levels of abstraction, and the specific problem solving machinery it provides. An example of the use of the architecture in the Hubble Space Telescope domain is given. Performance results that indicate the practicality of the HSTS approach are presented. >

ICAPS Conference 1990 Conference Paper

An evaluation function to compare alternative commitments during manufacturing planning and scheduling

• A. Safavi
• Stephen F. Smith

IJCAI Conference 1985 Conference Paper

The Use of Multiple Problem Decompositions in Time Constrained Planning Tasks

• Stephen F. Smith
• Peng Si Ow

IJCAI Conference 1983 Conference Paper

Flexible Learning of Problem Solving Heuristics Through Adaptive Search

• Stephen F. Smith