J. Christopher Beck

AIJ Journal 2026 Journal Article

Domain-independent dynamic programming

• Ryo Kuroiwa
• J. Christopher Beck

For combinatorial optimization problems, model-based paradigms such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the `holy grail' of declarative problem solving. We propose domain-independent dynamic programming (DIDP), a novel model-based paradigm based on dynamic programming (DP). While DP is not new, it has typically been implemented as a problem-specific method. We introduce Dynamic Programming Description Language (DyPDL), a formalism to define DP models based on a state transition system, inspired by artificial intelligence (AI) planning. we show that heuristic search algorithms can be used to solve DyPDL models and propose seven DIDP solvers. We experimentally compare our DIDP solvers with commercial MIP and CP solvers (solving MIP and CP models, respectively) on common benchmark instances of eleven combinatorial optimization problem classes. We show that DIDP outperforms MIP in nine problem classes, CP also in nine problem classes, and both MIP and CP in seven. DIDP also achieves superior performance to existing state-based solvers including domain-independent AI planners.

AAAI Conference 2024 Conference Paper

Parallel Beam Search Algorithms for Domain-Independent Dynamic Programming

• Ryo Kuroiwa
• J. Christopher Beck

Domain-independent dynamic programming (DIDP), a model-based paradigm based on dynamic programming, has shown promising performance on multiple combinatorial optimization problems compared with mixed integer programming (MIP) and constraint programming (CP). The current DIDP solvers are based on heuristic search, and the state-of-the-art solver, complete anytime beam search (CABS), uses beam search. However, the current DIDP solvers cannot utilize multiple threads, unlike state-of-the-art MIP and CP solvers. In this paper, we propose three parallel beam search algorithms and develop multi-thread implementations of CABS. With 32 threads, our multi-thread DIDP solvers achieve 9 to 39 times speedup on average and significant performance improvement over the sequential solver, finding the new best solutions for two instances of the traveling salesperson problem with time windows. In addition, our solvers outperform multi-thread MIP and CP solvers in four of the six combinatorial optimization problems evaluated.

AAAI Conference 2024 Conference Paper

PRP Rebooted: Advancing the State of the Art in FOND Planning

• Christian Muise
• Sheila A. McIlraith
• J. Christopher Beck

Fully Observable Non-Deterministic (FOND) planning is a variant of classical symbolic planning in which actions are nondeterministic, with an action's outcome known only upon execution. It is a popular planning paradigm with applications ranging from robot planning to dialogue-agent design and reactive synthesis. Over the last 20 years, a number of approaches to FOND planning have emerged. In this work, we establish a new state of the art, following in the footsteps of some of the most powerful FOND planners to date. Our planner, PR2, decisively outperforms the four leading FOND planners, at times by a large margin, in 17 of 18 domains that represent a comprehensive benchmark suite. Ablation studies demonstrate the impact of various techniques we introduce, with the largest improvement coming from our novel FOND-aware heuristic.

ICAPS Conference 2023 Conference Paper

Domain-Independent Dynamic Programming: Generic State Space Search for Combinatorial Optimization

• Ryo Kuroiwa 0002
• J. Christopher Beck

For combinatorial optimization problems, model-based approaches such as mixed-integer programming (MIP) and constraint programming (CP) aim to decouple modeling and solving a problem: the `holy grail

ECAI Conference 2023 Conference Paper

Extracting and Exploiting Bounds of Numeric Variables for Optimal Linear Numeric Planning

• Ryo Kuroiwa 0002
• Alexander Shleyfman
• J. Christopher Beck

In numeric AI planning, a state is represented by propositions and numeric variables, actions change the values of numeric variables in addition to adding and deleting propositions, and goals and preconditions of actions may include conditions over numeric variables. While domains of numeric variables are rational numbers in general, upper and lower bounds on variables affected only by constant increase and decrease can sometimes be determined and exploited by a heuristic function. In this paper, we generalize the existing method to variables that are changed by linear effects. We exploit the extracted bounds to improve the numeric LM-cut heuristic, a state-of-the-art admissible heuristic for linear numeric planning. Empirical evaluation shows that our method improves the performance of LM-cut in multiple domains. The proposed method can also detect unsolvability of some numeric tasks in polynomial time.

AAAI Conference 2023 Conference Paper

Privacy Attacks on Schedule-Driven Data

• Stephan A. Fahrenkrog-Petersen
• Arik Senderovich
• Alexandra Tichauer
• Ali Kaan Tutak
• J. Christopher Beck
• Matthias Weidlich

Schedules define how resources process jobs in diverse domains, reaching from healthcare to transportation, and, therefore, denote a valuable starting point for analysis of the underlying system. However, publishing a schedule may disclose private information on the considered jobs. In this paper, we provide a first threat model for published schedules, thereby defining a completely new class of data privacy problems. We then propose distance-based measures to assess the privacy loss incurred by a published schedule, and show their theoretical properties for an uninformed adversary, which can be used as a benchmark for informed attacks. We show how an informed attack on a published schedule can be phrased as an inverse scheduling problem. We instantiate this idea by formulating the inverse of a well-studied single-machine scheduling problem, namely minimizing the total weighted completion times. An empirical evaluation for synthetic scheduling problems shows the effectiveness of informed privacy attacks and compares the results to theoretical bounds on uninformed attacks.

ICAPS Conference 2023 Conference Paper

Solving Domain-Independent Dynamic Programming Problems with Anytime Heuristic Search

• Ryo Kuroiwa 0002
• J. Christopher Beck

Domain-independent dynamic programming (DIDP) is a recently proposed model-based paradigm for combinatorial optimization where a problem is formulated as dynamic programming (DP) and solved by a generic solver. In this paper, we develop anytime heuristic search solvers for DIDP, which quickly find a feasible solution and continuously improve it to prove optimality. We implement six anytime heuristic search algorithms previously used as problem-specific methods and evaluate them on nine different problem classes. Our experimental results show that most of the anytime DIDP solvers outperform an existing A*-based solver, mixed-integer programming, and constraint programming in proving optimality, solution quality, and primal integral across multiple problem classes. In particular, complete anytime beam search (CABS) performs the best, improving on the best-known solution for one instance of traveling salesman problem with time windows and closing five instances of one-to-one multi-commodity pick-and-delivery traveling salesman problems.

ICAPS Conference 2023 Conference Paper

Symmetry Detection and Breaking in Linear Cost-Optimal Numeric Planning

• Alexander Shleyfman
• Ryo Kuroiwa 0002
• J. Christopher Beck

One of the main challenges of domain-independent numeric planning is the complexity of the search problem. The exploitation of structural symmetries in a search problem can constitute an effective method of pruning search branches that may lead to exponential improvements in performance. For over a decade, symmetry breaking techniques have been successfully used within both optimal and satisficing classical planning. In this work, we show that symmetry detection methods applied in classical planning with some effort can be modified to detect symmetries in linear numeric planning. The detected symmetry group, thereafter, can be used almost directly in the A*-based symmetry breaking algorithms such as DKS and Orbit Space Search. We empirically validate that symmetry pruning can yield a substantial reduction in the search effort, even if algorithms are equipped with a strong heuristic, such as LM-cut.

ICAPS Conference 2022 Conference Paper

Biased Exploration for Satisficing Heuristic Search

• Ryo Kuroiwa 0002
• J. Christopher Beck

Satisficing heuristic search such as greedy best-first search (GBFS) suffers from local minima, regions where heuristic values are inaccurate and a good node has a worse heuristic value than other nodes. Search algorithms that incorporate exploration mechanisms in GBFS empirically reduce the search effort to solve difficult problems. Although some of these methods entirely ignore the guidance of a heuristic during their exploration phase, intuitively, a good heuristic should have some bound on its inaccuracy, and exploration mechanisms should exploit this bound. In this paper, we theoretically analyze what a good node is for satisficing heuristic search algorithms and show that the heuristic value of a good node has an upper bound if a heuristic satisfies a certain property. Then, we propose biased exploration mechanisms which select lower heuristic values with higher probabilities. In the experiments using synthetic graph search problems and classical planning benchmarks, we show that the biased exploration mechanisms can be useful. In particular, one of our methods, Softmin-Type(h), significantly outperforms other GBFS variants in classical planning and improves the performance of Type-LAMA, a state-of-the-art classical planner.

ICAPS Conference 2022 Conference Paper

LM-Cut Heuristics for Optimal Linear Numeric Planning

• Ryo Kuroiwa 0002
• Alexander Shleyfman
• J. Christopher Beck

While numeric variables play an important, sometimes central, role in many planning problems arising from real world scenarios, most of the currently available heuristic search planners either do not support such variables or impose heavy restrictions on them. In particular, most admissible heuristics are restricted to domains where actions can only change numeric variables by predetermined constants. In this work, we consider the setting of optimal numeric planning with linear effects, where actions can have numeric effects that assign the result of the evaluation of a linear formula. We extend a recent formulation of Numeric LM-cut for simple effects by adding conditional effects and second-order simple effects, allowing the heuristic to produce admissible estimates for tasks with linear numeric effects. Empirical comparison shows that the proposed LM-cut heuristics favorably compete with the currently available state-of-the-art heuristics and achieve significant improvement in coverage in the domains with second-order simple effects.

ICAPS Conference 2022 Conference Paper

Solving Job-Shop Scheduling Problems with QUBO-Based Specialized Hardware

• Jiachen Zhang
• Giovanni Lo Bianco
• J. Christopher Beck

The emergence of specialized hardware, such as quantum computers and Digital/CMOS annealers, and the slowing of performance growth of general-purpose hardware raises an important question for our community: how can the high-performance, specialized solvers be used for planning and scheduling problems? In this work, we focus on the job-shop scheduling problem (JSP) and Quadratic Unconstrained Binary Optimization (QUBO) models, the mathematical formulation shared by a number of novel hardware platforms. We study two direct QUBO models of JSP and propose a novel large neighborhood search (LNS) approach, that hybridizes a QUBO model with constraint programming (CP). Empirical results show that our LNS approach significantly outperforms classical CP-based LNS methods and a mixed integer programming model, while being competitive with CP for large problem instances. This work is the first approach that we are aware of that can solve non-trivial JSPs using QUBO hardware, albeit as part of a hybrid algorithm.

JAIR Journal 2022 Journal Article

The LM-Cut Heuristic Family for Optimal Numeric Planning with Simple Conditions

• Ryo Kuroiwa
• Alexander Shleyfman
• Chiara Piacentini
• Margarita P. Castro
• J. Christopher Beck

The LM-cut heuristic, both alone and as part of the operator counting framework, represents one of the most successful heuristics for classical planning. In this paper, we generalize LM-cut and its use in operator counting to optimal numeric planning with simple conditions and simple numeric effects, i.e., linear expressions over numeric state variables and actions that increase or decrease such variables by constant quantities. We introduce a variant of hmaxhbd (a previously proposed numeric hmax heuristic) based on the delete-relaxed version of such planning tasks and show that, although inadmissible by itself, our variant yields a numeric version of the classical LM-cut heuristic which is admissible. We classify the three existing families of heuristics for this class of numeric planning tasks and introduce the LM-cut family, proving dominance or incomparability between all pairs of existing max and LM-cut heuristics for numeric planning with simple conditions. Our extensive empirical evaluation shows that the new LM-cut heuristic, both on its own and as part of the operator counting framework, is the state-of-the-art for this class of numeric planning problem.

IJCAI Conference 2021 Conference Paper

Counterfactual Explanations for Optimization-Based Decisions in the Context of the GDPR

• Anton Korikov
• Alexander Shleyfman
• J. Christopher Beck

The General Data Protection Regulations (GDPR) entitle individuals to explanations for automated decisions. The form, comprehensibility, and even existence of such explanations remain open problems, investigated as part of explainable AI. We adopt the approach of counterfactual explanations and apply it to decisions made by declarative optimization models. We argue that inverse combinatorial optimization is particularly suited for counterfactual explanations but that the computational difficulties and relatively nascent literature make its application a challenge. To make progress, we address the case of counterfactual explanations that isolate the minimal differences for an individual. We show that under two common optimization functions, full inverse optimization is unnecessary. In particular, we show that for functions of the form of the sum of weighted binary variables, which includes frameworks such as weighted MaxSAT, a solution can be found by solving a slightly modified version of the original optimization model. In contrast, the sum of weighted integer variables can be solved with a binary search over a series of modifications to the original model.

ICAPS Conference 2021 Conference Paper

LM-cut and Operator Counting Heuristics for Optimal Numeric Planning with Simple Conditions

• Ryo Kuroiwa 0002
• Alexander Shleyfman
• Chiara Piacentini
• Margarita P. Castro
• J. Christopher Beck

We consider optimal numeric planning with numeric conditions consisting of linear expressions of numeric state variables and actions that increase or decrease numeric state variables by constant quantities. We build on previous research to introduce a new variant of the numeric hmax heuristic based on the delete-relaxed version of such planning tasks. Although our hmax heuristic is inadmissible, it yields a numeric version of the classical LM-cut heuristic which is admissible. Further, we prove that our LM-cut heuristic neither dominates nor is dominated by the existing numeric heuristic hmax(hbd). We show that admissibility also holds when integrating the numeric cuts into the operator-counting (OC) heuristic producing an admissible numeric version of the OC heuristic. Through experiments, we demonstrate that both these heuristics compete favorably with the state-of-the-art heuristics: in particular, while sometimes expanding more nodes than other heuristics, numeric OC solves 19 more problem instances than the next closest heuristic.

JAIR Journal 2020 Journal Article

Solving Delete Free Planning with Relaxed Decision Diagram Based Heuristics

• Margarita Paz Castro
• Chiara Piacentini
• Andre Augusto Cire
• J. Christopher Beck

We investigate the use of relaxed decision diagrams (DDs) for computing admissible heuristics for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of two novel DD encodings for a DFP task: a multivalued decision diagram that includes the sequencing aspect of the problem and a binary decision diagram representation of its sequential relaxation. We present construction algorithms for each DD that leverage these different perspectives of the DFP task and provide theoretical and empirical analyses of the associated heuristics. We further show that relaxed DDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while DD-based heuristics trail the state of the art, even small relaxed DDs are competitive with the linear programming heuristic for the DFP task, thus, revealing novel ways of designing admissible heuristics.

JAIR Journal 2019 Journal Article

Autonomous Target Search with Multiple Coordinated UAVs

• Chiara Piacentini
• Sara Bernardini
• J. Christopher Beck

Search and tracking is the problem of locating a moving target and following it to its destination. In this work, we consider a scenario in which the target moves across a large geographical area by following a road network and the search is performed by a team of unmanned aerial vehicles (UAVs). We formulate search and tracking as a combinatorial optimization problem and prove that the objective function is submodular. We exploit this property to devise a greedy algorithm. Although this algorithm does not offer strong theoretical guarantees because of the presence of temporal constraints that limit the feasibility of the solutions, it presents remarkably good performance, especially when several UAVs are available for the mission. As the greedy algorithm suffers when resources are scarce, we investigate two alternative optimization techniques: Constraint Programming (CP) and AI planning. Both approaches struggle to cope with large problems, and so we strengthen them by leveraging the greedy algorithm. We use the greedy solution to warm start the CP model and to devise a domain-dependent heuristic for planning. Our extensive experimental evaluation studies the scalability of the different techniques and identifies the conditions under which one approach becomes preferable to the others.

AAAI Conference 2019 Conference Paper

Congestion Graphs for Automated Time Predictions

• Arik Senderovich
• J. Christopher Beck
• Avigdor Gal
• Matthias Weidlich

Time prediction is an essential component of decision making in various Artificial Intelligence application areas, including transportation systems, healthcare, and manufacturing. Predictions are required for efficient resource allocation and scheduling, optimized routing, and temporal action planning. In this work, we focus on time prediction in congested systems, where entities share scarce resources. To achieve accurate and explainable time prediction in this setting, features describing system congestion (e. g. , workload and resource availability), must be considered. These features are typically gathered using process knowledge, (i. e. , insights on the interplay of a system’s entities). Such knowledge is expensive to gather and may be completely unavailable. In order to automatically extract such features from data without prior process knowledge, we propose the model of congestion graphs, which are grounded in queueing theory. We show how congestion graphs are mined from raw event data using queueing theory based assumptions on the information contained in these logs. We evaluate our approach on two real-world datasets from healthcare systems where scarce resources prevail: an emergency department and an outpatient cancer clinic. Our experimental results show that using automatic generation of congestion features, we get an up to 23% improvement in terms of relative error in time prediction, compared to common baseline methods. We also detail how congestion graphs can be used to explain delays in the system.

AAAI Conference 2019 Conference Paper

Efficient Temporal Planning Using Metastates

• Amanda Coles
• Andrew Coles
• J. Christopher Beck

When performing temporal planning as forward state-space search, effective state memoisation is challenging. Whereas in classical planning, two states are equal if they have the same facts and variable values, in temporal planning this is not the case: as the plans that led to the two states are subject to temporal constraints, one might be extendable into at temporally valid plan, while the other might not. In this paper, we present an approach for reducing the state space explosion that arises due to having to keep many copies of the same ‘classically’ equal state – states that are classically equal are aggregated into metastates, and these are separated lazily only in the case of temporal inconsistency. Our evaluation shows that this approach, implemented in OPTIC and compared to existing state-of-the-art memoisation techniques, improves performance across a range of temporal domains.

ICML Conference 2019 Conference Paper

Empirical Analysis of Beam Search Performance Degradation in Neural Sequence Models

• Eldan Cohen
• J. Christopher Beck

Beam search is the most popular inference algorithm for decoding neural sequence models. Unlike greedy search, beam search allows for non-greedy local decisions that can potentially lead to a sequence with a higher overall probability. However, work on a number of applications has found that the quality of the highest probability hypothesis found by beam search degrades with large beam widths. We perform an empirical study of the behavior of beam search across three sequence synthesis tasks. We find that increasing the beam width leads to sequences that are disproportionately based on early, very low probability tokens that are followed by a sequence of tokens with higher (conditional) probability. We show that, empirically, such sequences are more likely to have a lower evaluation score than lower probability sequences without this pattern. Using the notion of search discrepancies from heuristic search, we hypothesize that large discrepancies are the cause of the performance degradation. We show that this hypothesis generalizes the previous ones in machine translation and image captioning. To validate our hypothesis, we show that constraining beam search to avoid large discrepancies eliminates the performance degradation.

ICAPS Conference 2019 Conference Paper

Learning Scheduling Models from Event Data

• Arik Senderovich
• Kyle E. C. Booth
• J. Christopher Beck

A significant challenge in declarative approaches to scheduling is the creation of a model: the set of resources and their capacities and the types of activities and their temporal and resource requirements. In practice, such models are developed manually by skilled consultants and used repeatedly to solve different problem instances. For example, in a factory, the model may be used each day to schedule the current customer orders. In this work, we aim to automate the creation of such models by learning them from event data. We introduce a novel methodology that combines process mining, timed Petri nets (TPNs), and constraint programming (CP). The approach learns a sub-class of TPN from event logs of executions of past schedules and maps the TPN to a broad class of scheduling problems. We show how any problem of the scheduling class can be converted to a CP model. With new instance data (e. g. , the day’s orders), the CP model can then be solved by an off-the-shelf solver. Our approach provides an end-to-end solution, going from event logs to model-based optimal schedules. To demonstrate the value of the methodology we conduct experiments in which we learn and solve scheduling models from two types of data: logs generated from job-shop scheduling benchmarks and real-world event logs from an outpatient hospital.

ICAPS Conference 2019 Conference Paper

Relaxed BDDs: An Admissible Heuristic for Delete-Free Planning Based on a Discrete Relaxation

• Margarita P. Castro
• Chiara Piacentini
• André A. Ciré
• J. Christopher Beck

We investigate the use of relaxed binary decision diagrams (BDDs) as an alternative to linear programming (LP) for computing an admissible heuristic for the cost-optimal delete-free planning (DFP) problem. Our main contributions are the introduction of a novel BDD encoding, a construction algorithm for the sequential relaxation of a DFP task and a study of the effectiveness of relaxed BDD heuristics, both from a theoretical and practical perspective. We further show that relaxed BDDs can be used beyond heuristic computation to extract delete-free plans, find action landmarks, and identify redundant actions. Our empirical analysis shows that while BDD-based heuristics trail the state of the art, even small relaxed BDDs are competitive with the LP heuristic for the DFP task.

ICAPS Conference 2018 Conference Paper

Comparing and Integrating Constraint Programming and Temporal Planning for Quantum Circuit Compilation

• Kyle E. C. Booth
• Minh Do
• J. Christopher Beck
• Eleanor Gilbert Rieffel
• Davide Venturelli
• Jeremy Frank

Recently, the makespan-minimization problem of compiling a general class of quantum algorithms into near-term quantum processors has been introduced to the AI community. The research demonstrated that temporal planning is a strong approach for a class of quantum circuit compilation (QCC) problems. In this paper, we explore the use of constraint programming (CP) as an alternative and complementary approach to temporal planning. We extend previous work by introducing two new problem variations that incorporate important characteristics identified by the quantum computing community. We apply temporal planning and CP to the baseline and extended QCC problems as both stand-alone and hybrid approaches. Our hybrid methods use solutions found by temporal planning to warm start CP, leveraging the ability of the former to find satisficing solutions to problems with a high degree of task optionality, an area that CP typically struggles with. The CP model, benefiting from inferred bounds on planning horizon length and task counts provided by the warm start, is then used to find higher quality solutions. Our empirical evaluation indicates that while stand-alone CP is only competitive for the smallest problems, CP in our hybridization with temporal planning out-performs stand-alone temporal planning in the majority of problem classes.

ICAPS Conference 2018 Conference Paper

Compiling Optimal Numeric Planning to Mixed Integer Linear Programming

• Chiara Piacentini
• Margarita P. Castro
• André A. Ciré
• J. Christopher Beck

Compilation techniques in planning reformulate a problem into an alternative encoding for which efficient, off-the-shelf solvers are available. In this work, we present a novel mixed-integer linear programming (MILP) compilation for cost-optimal numeric planning with instantaneous actions. While recent works on the problem are restricted to actions that modify variables present in simple numeric conditions, our MILP formulation, in addition, handles linear conditions and linear action effects on numeric state variables. Such problems are particularly challenging due to the state-dependency of the action effects. Experiments show that our approach, in addition to being the state of the art for the more general problem class, is competitive with heuristic search-based planners on domains with only simple numeric conditions.

AAAI Conference 2018 Conference Paper

Fat- and Heavy-Tailed Behavior in Satisficing Planning

• Eldan Cohen
• J. Christopher Beck

In this work, we study the runtime distribution of satisficing planning in ensembles of random planning problems and in multiple runs of a randomized heuristic search on a single planning instance. Using common heuristic functions (such as FF) and six benchmark problem domains from the IPC, we find a heavy-tailed behavior, similar to that found in CSP and SAT. We investigate two notions of constrainedness, often used in the modeling of planning problems, and show that the heavy-tailed behavior tends to appear in relatively relaxed problems, where the required effort is, on average, low. Finally, we show that as with randomized restarts in CSP and SAT solving, recent search enhancements that incorporate randomness in the search process can help mitigate the effect of the heavy tail.

AAAI Conference 2018 Conference Paper

Linear and Integer Programming-Based Heuristics for Cost-Optimal Numeric Planning

• Chiara Piacentini
• Margarita Castro
• Andre Cire
• J. Christopher Beck

Linear programming has been successfully used to compute admissible heuristics for cost-optimal classical planning. Although one of the strengths of linear programming is the ability to express and reason about numeric variables and constraints, their use in numeric planning is limited. In this work, we extend linear programming-based heuristics for classical planning to support numeric state variables. In particular, we propose a model for the interval relaxation, coupled with landmarks and state equation constraints. We consider both linear programming models and their harder-tosolve, yet more informative, integer programming versions. Our experimental analysis shows that considering an NP- Hard heuristic often pays off and that A∗ search using our integer programming heuristics establishes a new state of the art in cost-optimal numeric planning.

IJCAI Conference 2018 Conference Paper

Local Minima, Heavy Tails, and Search Effort for GBFS

• Eldan Cohen
• J. Christopher Beck

Problem difficulty for greedy best first search (GBFS) is not entirely understood, though existing work points to deep local minima and poor correlation between the h-values and the distance to goal as factors that have significant negative effect on the search effort. In this work, we show that there is a very strong exponential correlation between the depth of the single deepest local minima encountered in a search and the overall search effort. Furthermore, we find that the distribution of local minima depth changes dramatically based on the constrainedness of problems, suggesting an explanation for the previously observed heavy-tailed behavior in GBFS. In combinatorial search, a similar result led to the use of randomized restarts to escape deep subtrees with no solution and corresponding significant speed-ups. We adapt this method and propose a randomized restarting GBFS variant that improves GBFS performance by escaping deep local minima, and does so even in the presence of other, randomization-based, search enhancements.

SAT Conference 2017 Conference Paper

(I Can Get) Satisfaction: Preference-Based Scheduling for Concert-Goers at Multi-venue Music Festivals

• Eldan Cohen
• Guoyu Huang
• J. Christopher Beck

Abstract With more than 30 million attendees each year in the U. S. alone, music festivals are a fast-growing source of entertainment, visited by both fans and industry professionals. Popular music festivals are large-scale events, often spread across multiple venues and lasting several days. The largest festivals exceed 600 shows per day across dozens of venues. With many artists performing at overlapping times in distant locations, preparing a personal schedule for a festival-goer is a challenging task. In this work, we present an automated system for building a personal schedule that maximizes the utility of the shows attended based on the user preferences, while taking into account travel times and required breaks. Our system leverages data mining and machine learning techniques together with combinatorial optimization to provide optimal personal schedules in real time, over a web interface. We evaluate MaxSAT and Constraint Programming formulations on a large set of real festival timetables, demonstrating that MaxSAT can provide optimal solutions in about 10 s on average, making it a suitable technology for such an online application.

SoCS Conference 2017 Conference Paper

Cost-Based Heuristics and Node Re-Expansions across the Phase Transition

• Eldan Cohen
• J. Christopher Beck

Recent work aimed at developing a deeper understanding of suboptimal heuristic search has demonstrated that the use of a cost-based heuristic function in the presence of large operator cost ratio and the decision to allow re-opening of visited nodes can have a significant effect on search effort. In parallel research, phase transitions in problem solubility have proved useful in the study of problem difficulty for many computational problems and have recently been shown to exist in heuristic search problems. In this paper, we show that the impact on search effort associated with a larger operator cost ratio and the number of node re-expansions is concentrated almost entirely in the phase transition region. Combined with previous work connecting local minima in the search space with such behavior, these observations lead us to hypothesize a relationship between the phase transition and the existence of local minima.

AAAI Conference 2017 Conference Paper

Problem Difficulty and the Phase Transition in Heuristic Search

• Eldan Cohen
• J. Christopher Beck

In the recent years, there has been significant work on the difficulty of heuristic search problems, identifying different problem instance characteristics that can have a significant impact on search effort. Phase transitions in the solubility of random problem instances have proved useful in the study of problem difficulty for other classes of computational problems, notably SAT and CSP, and it has been shown that the hardest problems typically occur during this rapid transition. In this work, we perform the first empirical investigation of the phase transition phenomena for heuristic search. We establish the existence of a rapid transition in the solubility of an abstract model of heuristic search problems and show that, for greedy best first search, the hardest instances are associated with the phase transition region. We then perform a novel investigation of the behavior of heuristics of different strength across the solubility spectrum. Finally, we demonstrate that the behavior of our abstract model carries over to commonly used benchmark problems including the Pancake Problem, Grid Navigation, TopSpin, and the Towers of Hanoi. An interesting deviation is observed and explained in the Sliding Puzzle.

JAIR Journal 2017 Journal Article

Robots in Retirement Homes: Applying Off-the-Shelf Planning and Scheduling to a Team of Assistive Robots

• Tony T. Tran
• Tiago Vaquero
• Goldie Nejat
• J. Christopher Beck

This paper investigates three different technologies for solving a planning and scheduling problem of deploying multiple robots in a retirement home environment to assist elderly residents. The models proposed make use of standard techniques and solvers developed in AI planning and scheduling, with two primary motivations. First, to find a planning and scheduling solution that we can deploy in our real-world application. Second, to evaluate planning and scheduling technology in terms of the ``model-and-solve'' functionality that forms a major research goal in both domain-independent planning and constraint programming. Seven variations of our application are studied using the following three technologies: PDDL-based planning, time-line planning and scheduling, and constraint-based scheduling. The variations address specific aspects of the problem that we believe can impact the performance of the technologies while also representing reasonable abstractions of the real world application. We evaluate the capabilities of each technology and conclude that a constraint-based scheduling approach, specifically a decomposition using constraint programming, provides the most promising results for our application. PDDL-based planning is able to find mostly low quality solutions while the timeline approach was unable to model the full problem without alterations to the solver code, thus moving away from the model-and-solve paradigm. It would be misleading to conclude that constraint programming is ``better'' than PDDL-based planning in a general sense, both because we have examined a single application and because the approaches make different assumptions about the knowledge one is allowed to embed in a model. Nonetheless, we believe our investigation is valuable for AI planning and scheduling researchers as it highlights these different modelling assumptions and provides insight into avenues for the application of AI planning and scheduling for similar robotics problems. In particular, as constraint programming has not been widely applied to robot planning and scheduling in the literature, our results suggest significant untapped potential in doing so.

IJCAI Conference 2017 Conference Paper

Robots in Retirement Homes: Applying Off-the-Shelf Planning and Scheduling to a Team of Assistive Robots (Extended Abstract)

• Tony T. Tran
• Tiago Vaquero
• Goldie Nejat
• J. Christopher Beck

We investigate Constraint Programming and Planning Domain Definition Language-based technologies for planning and scheduling multiple robots in a retirement home environment to assist elderly residents. Our robotics problem and investigation into proposed solution approaches provide a real world application of planning and scheduling, while highlighting the different modeling assumptions required to solve such a problem. This information is valuable to the planning and scheduling community as it provides insight into potential application avenues, in particular for robotics problems. Based on empirical results, we conclude that a constraint-based scheduling approach, specifically a decomposition using constraint programming, provides the most promising results for our application.

IS Journal 2017 Journal Article

Robots in Retirement Homes: Person Search and Task Planning for a Group of Residents by a Team of Assistive Robots

• Kyle E.C. Booth
• Sharaf C. Mohamed
• Sanjif Rajaratnam
• Goldie Nejat
• J. Christopher Beck

The authors present a general multirobot task planning and execution architecture for a team of heterogeneous mobile robots that interact with multiple human users. The designed architecture is implemented in an environment where such robots provide daily assistance to residents in a retirement home setting. The robots are able to allocate and schedule activities throughout the day and find the appropriate residents with whom to engage in assistive activities. Upon finding users, the robot queries each user for his or her availability and interest in various activities. The authors then use constraint programming within a multirobot task allocation and scheduling system to plan and schedule the robot team to facilitate individual and group activities, ensuring consistency with user-expressed availability and activity preferences. The authors test the components of the architecture on a physical multirobot system to verify the utility of the design. Experiments indicate the design can effectively plan and execute assistive activities for multiple users.

SoCS Conference 2016 Conference Paper

A Hybrid Quantum-Classical Approach to Solving Scheduling Problems

• Tony T. Tran
• Minh Do
• Eleanor Gilbert Rieffel
• Jeremy Frank
• Zhihui Wang 0012
• Bryan O'Gorman
• Davide Venturelli
• J. Christopher Beck

An effective approach to solving complex problems is to decompose them and integrate dedicated solvers for those subproblems. We introduce a hybrid decomposition that incorporates: (1) a quantum annealer that samples from the configuration space of a relaxed problem to obtain strong candidate solutions, and (2) a classical processor that maintains a global search tree and enforces constraints on the relaxed components of the problem. Our framework is the first to use quantum annealing as part of a complete search. We consider variants of our approach with differing amounts of guidance from the quantum annealer. We empirically test our algorithm and compare the variants on problems from three scheduling domains: graph-coloring-type scheduling, simplified Mars Lander task scheduling, and airport runway scheduling. While we were only able to test on problems of small sizes, due to the limitation of currently available quantum annealing hardware, the empirical results show that results obtained from the quantum annealer can be used for more effective search node pruning and to improve node selection heuristics when compared to a standard classical approach.

ECAI Conference 2016 Conference Paper

Mathematical Programming Models for Optimizing Partial-Order Plan Flexibility

• Buser Say
• André A. Ciré
• J. Christopher Beck

A partial-order plan (POP) compactly encodes a set of sequential plans that can be dynamically chosen by an agent at execution time. One natural measure of the quality of a POP is its flexibility, which is defined to be the total number of sequential plans it embodies (i. e. , its linearizations). As this criteria is hard to optimize, existing work has instead optimized proxy functions that are correlated with the number of linearizations. In this paper, we develop and strengthen mixed-integer linear programming (MILP) models for three proxy functions: two from the POP literature and a third novel function based on the temporal flexibility criteria from the scheduling literature. We show theoretically and empirically that none of the three proxy measures dominate the others in terms of number of sequential plans. Compared to the state-of-the-art MaxSAT model for the problem, we empirically demonstrate that two of our MILP models result in equivalent or slightly better solution quality with savings of approximately one order of magnitude in computation time.

JAIR Journal 2016 Journal Article

Optimal Partial-Order Plan Relaxation via MaxSAT

• Christian Muise
• J. Christopher Beck
• Sheila A. McIlraith

Partial-order plans (POPs) are attractive because of their least-commitment nature, which provides enhanced plan flexibility at execution time relative to sequential plans. Current research on automated plan generation focuses on producing sequential plans, despite the appeal of POPs. In this paper we examine POP generation by relaxing or modifying the action orderings of a sequential plan to optimize for plan criteria that promote flexibility. Our approach relies on a novel partial weighted MaxSAT encoding of a sequential plan that supports the minimization of deordering or reordering of actions. Using a similar technique, we further demonstrate how to remove redundant actions from the plan, and how to combine this criterion with the objective of maximizing a POP's flexibility. Our partial weighted MaxSAT encoding allows us to compute a POP from a sequential plan effectively. We compare the efficiency of our approach to previous methods for POP generation via sequential-plan relaxation. Our results show that while an existing heuristic approach consistently produces the optimal deordering of a sequential plan, our approach has greater flexibility when we consider reordering the actions in the plan while also providing a guarantee of optimality. We also investigate and confirm the accuracy of the standard flex metric typically used to predict the true flexibility of a POP as measured by the number of linearizations it represents.

ICRA Conference 2014 Conference Paper

An autonomous assistive robot for planning, scheduling and facilitating multi-user activities

• Wing-Yue Geoffrey Louie
• Tiago Vaquero
• Goldie Nejat
• J. Christopher Beck

In this paper we present the development of a novel multi-user human-robot interaction (HRI) system architecture to allow the social robot Tangy to autonomously plan, schedule and facilitate multi-user activities while considering the users' schedules. During scheduled activities, the robot is able to interact with a group of users by providing both group-based and individualized assistance based on the current state of the activity and the needs of the individual users engaged in the social interactions. Such planning and scheduling of daily activities of a social robot while reasoning about multiple user schedules has not yet been addressed in the literature. Herein, the HRI multi-user activities we consider are a series of Bingo games. System performance experiments presented in the paper validate the use of the proposed multiuser system architecture in: 1) planning and scheduling daily Bingo games for Tangy to facilitate while considering the individual schedules of the users, and 2) determining the appropriate behaviors of the robot with respect to individuals and groups of people while providing game reminders prior to a Bingo game starting and also while facilitating the game itself.

IJCAI Conference 2013 Conference Paper

Flexible Execution of Partial Order Plans with Temporal Constraints

• Christian Muise
• J. Christopher Beck
• Sheila A. McIlraith

We propose a unified approach to plan execution and schedule dispatching that converts a plan, which has been augmented with temporal constraints, into a policy for dispatching. Our approach generalizes the original plan and temporal constraints so that the executor need only consider the subset of state that is relevant to successful execution of valid plan fragments. We can accommodate a variety of calamitous and serendipitous changes to the state of the world by supporting the seamless re-execution or omission of plan fragments, without the need for costly replanning. Our methodology for plan generalization and online dispatching is a novel combination of plan execution and schedule dispatching techniques. We demonstrate the effectiveness of our method through a prototype implementation and a series of experiments.

ICAPS Conference 2013 Conference Paper

Hybrid Queueing Theory and Scheduling Models for Dynamic Environments with Sequence-Dependent Setup Times

• Tony T. Tran
• Daria Terekhov
• Douglas G. Down
• J. Christopher Beck

Classically, scheduling research in artificial intelligence has concentrated on the combinatorial challenges arising in a large, static domain where the set of jobs, resource capacities, and other problem parameters are known with certainty and do not change. In contrast, queueing theory has focused primarily on the stochastic arrival and resource requirements of new jobs, de-emphasizing the combinatorics. We study a dynamic parallel scheduling problem with sequence-dependent setup times: arriving jobs must be assigned (online) to one of a set of resources. The jobs have different service times on different resources and there exist setup times that are required to elapse between jobs, depending on both the resource used and the job sequence. We investigate four models that hybridize a scheduling model with techniques from queueing theory to address the dynamic problem. We demonstrate that one of the hybrid models can significantly reduce observed mean flow time performance when compared to the pure scheduling and queueing theory methods. More specifically, at high system loads, our hybrid model achieves a 15% to 60% decrease in mean flow time compared to the pure methodologies. This paper illustrates the advantages of integrating techniques from queueing theory and scheduling to improve performance in dynamic problems with complex combinatorics.

SoCS Conference 2013 Conference Paper

Invited Speakers

• J. Christopher Beck
• Gene Cooperman

Abstracts of the invited speaker talks Modeling, Global Constraints, and Decomposition by J. Christopher Beck and Applications of Graph Search in Group Theory and Proteomics by Gene Cooperman, presented that the 2013 SoCS Symposium.

KER Journal 2013 Journal Article

itSIMPLE: towards an integrated design system for real planning applications

• Tiago S. Vaquero
• José R. Silva
• Flavio Tonidandel
• J. Christopher Beck

Abstract Since the end of the 1990s, there has been an increasing interest in the application of artificial intelligence (AI) planning techniques to solve real-life problems. In addition to characteristics of academic problems, such as the need to reason about actions, real-life problems require detailed knowledge elicitation, engineering, and management. A systematic design process in which Knowledge and Requirements Engineering tools play a fundamental role is necessary in such applications. One of the main challenges in such design process, and consequently in the study of Knowledge Engineering in AI planning, has been the analysis of requirements and their subsequent transformation into an input-ready model for planners. itSIMPLE is a research project dedicated to the study of a project process to support the design phases of real-life planning models. In this paper, we give an overview of itSIMPLE focusing on the main translation processes among a minimal set of representations: from requirements represented in Unified Modeling Language (UML) to Petri Nets and from UML models to planning domain definition language for problem solving.

EAAI Journal 2013 Journal Article

Post-design analysis for building and refining AI planning systems

• Tiago Stegun Vaquero
• José Reinaldo Silva
• J. Christopher Beck

The growth of industrial applications of artificial intelligence has raised the need for design tools to aid in the conception and implementation of such complex systems. The design of automated planning systems faces several engineering challenges including the proper modeling of the domain knowledge: the creation of a model that represents the problem to be solved, the world that surrounds the system, and the ways the system can interact with and change the world in order to solve the problem. Knowledge modeling in AI planning is a hard task that involves acquiring the system requirements and making design decisions that can determine the behavior and performance of the resulting system. In this paper we investigate how knowledge acquired during a post-design phase of modeling can be used to improve the prospective model. A post-design framework is introduced which combines a knowledge engineering tool and a virtual prototyping environment for the analysis and simulation of plans. This framework demonstrates that post-design analysis supports the discovery of missing requirements and can guide the model refinement cycle. We present three case studies using benchmark domains and eight state-of-the-art planners. Our results demonstrate that significant improvements in plan quality and an increase in planning speed of up to three orders of magnitude can be achieved through a careful post-design process. We argue that such a process is critical for the deployment of AI planning technology in real-world engineering applications.

ICAPS Conference 2012 Conference Paper

Improved Non-Deterministic Planning by Exploiting State Relevance

• Christian J. Muise
• Sheila A. McIlraith
• J. Christopher Beck

We address the problem of computing a policy for fully observable non-deterministic (FOND) planning problems. By focusing on the relevant aspects of the state of the world, we introduce a series of improvements to the previous state of the art and extend the applicability of our planner, PRP, to work in an online setting. The use of state relevance allows our policy to be exponentially more succinct in representing a solution to a FOND problem for some domains. Through the introduction of new techniques for avoiding deadends and determining sufficient validity conditions, PRP has the potential to compute a policy up to several orders of magnitude faster than previous approaches. We also find dramatic improvements over the state of the art in online replanning when we treat suitable probabilistic domains as FOND domains.

ECAI Conference 2012 Conference Paper

Logic-based Benders Decomposition for Alternative Resource Scheduling with Sequence Dependent Setups

• Tony T. Tran
• J. Christopher Beck

We study an unrelated parallel machines scheduling problem with sequence and machine dependent setup times. A logic-based Benders decomposition approach is proposed to minimize the makespan. This approach is a hybrid model that makes use of a mixed integer programming master problem and a specialized solver for travelling salesman subproblems. The master problem is used to assign jobs to machines while the subproblems obtain optimal schedules on each machine given the master problem assignments. Computational results show that the Benders model is able to find optimal solutions up to six orders of magnitude faster as well as solving problems six times the size previously possible with a mixed integer programming model in the literature and twice the size that a branchand-bound algorithm can solve for similar problems. We further relax the Benders decomposition to accept suboptimal schedules and demonstrate the ability to parameterize solution quality while out-performing state-of-the-art metaheuristics both in terms of solution quality and mean run-time.

ICAPS Conference 2012 Conference Paper

Long-Run Stability in Dynamic Scheduling

• Daria Terekhov
• Tony T. Tran
• Douglas G. Down
• J. Christopher Beck

Stability analysis consists of identifying conditions under which the number of jobs in a system is guaranteed to remain bounded over time. To date, such long-run performance guarantees have not been available for periodic approaches to dynamic scheduling problems. However, stability has been extensively studied in queueing theory. In this paper, we introduce stability to the dynamic scheduling literature and demonstrate that stability guarantees can be obtained for methods that build the schedule for a dynamic problem by periodically solving static deterministic sub-problems. Specifically, we analyze the stability of two dynamic environments: a two-machine flow shop, which has received significant attention in scheduling research, and a polling system with a flow-shop server, an extension of systems typically considered in queueing. We demonstrate that, among stable policies, methods based on periodic optimization of static schedules may achieve better mean flow times than traditional queueing approaches.

ICAPS Conference 2012 Conference Paper

Optimally Relaxing Partial-Order Plans with MaxSAT

• Christian J. Muise
• Sheila A. McIlraith
• J. Christopher Beck

Partial-order plans (POPs) are attractive because of their least commitment nature, providing enhanced plan flexibility at execution time relative to sequential plans. Despite the appeal of POPs, most of the recent research on automated plan generation has focused on sequential plans. In this paper we examine the task of POP generation by relaxing or modifying the action orderings of a plan to optimize for plan criteria that promotes flexibility in the POP. Our approach relies on a novel partial weighted MaxSAT encoding of a plan that supports the minimization of deordering or reordering of actions. We further extend the classical least commitment criterion for a POP to consider the number of actions in a solution, and provide an encoding to achieve least commitment plans with respect to this criterion. We compare the effectiveness of our approach to a previous approach for POP generation via sequential-plan relaxation. Our results show that while the previous approach is proficient at heuristically finding the optimal deordering of a plan, our approach gains greater flexibility with the optimal reordering.

ICAPS Conference 2012 Conference Paper

Planning Modulo Theories: Extending the Planning Paradigm

• Peter Gregory
• Derek Long
• Maria Fox 0001
• J. Christopher Beck

Considerable effort has been spent extending the scope of planning beyond propositional domains to include, for example, time and numbers. Each extension has been designed as a separate specific semantic enrichment of the underlying planning model, with its own syntax and customised integration into a planning algorithm. Inspired by work on SAT Modulo Theories (SMT) in the SAT community, we develop a modelling language and planner that treat arbitrary first order theories as parameters. We call the approach Planning Modulo Theories (PMT). We introduce a modular language to represent PMT problems and demonstrate its benefits over PDDL in expressivity and compactness. We present a generalisation of the $h_{max}$ heuristic that allows our planner, PMTPlan, to automatically reason about arbitrary theories added as modules. Over several new and existing benchmarks, exploiting different theories, we show that PMTPlan can significantly out-perform an existing planner using PDDL models.

JAAMAS Journal 2011 Journal Article

A negotiation framework for linked combinatorial optimization problems

• Lei Duan
• Mustafa K. Doğru
• J. Christopher Beck

Abstract We tackle the challenge of applying automated negotiation to self-interested agents with local but linked combinatorial optimization problems. Using a distributed production scheduling problem, we propose two negotiation strategies for making concessions in a joint search space of agreements. In the first strategy, building on Lai and Sycara (Group Decis Negot 18(2): 169–187, 2009), an agent concedes on local utility in order to achieve an agreement. In the second strategy, an agent concedes on the distance in an attribute space while maximizing its local utility. Lastly, we introduce a Pareto improvement phase to bring the final agreement closer to the Pareto frontier. Experimental results show that the new attribute-space negotiation strategy outperforms its utility-based counterpart on the quality of the agreements and the Pareto improvement phase is effective in approaching the Pareto frontier. This article presents the first study of applying automated negotiation to self-interested agents each with a local, but linked, combinatorial optimization problem.

IJCAI Conference 2011 Conference Paper

Monitoring the Execution of Partial-Order Plans via Regression

• Christian Muise
• Sheila A. McIlraith
• J. Christopher Beck

Partial-order plans (POPs) have the capacity to compactly represent numerous distinct plan linearizations and as a consequence are inherently robust. We exploit this robustness to do effective execution monitoring. We characterize the conditions under which a POP remains viable as the regression of the goal through the structure of a POP. We then develop a method for POP execution monitoring via a structured policy, expressed as an ordered algebraic decision diagram. The policy encompasses both state evaluation and action selection, enabling an agent to seamlessly switch between POP linearizations to accommodate unexpected changes during execution. We demonstrate the effectiveness of our approach by comparing it empirically and analytically to a standard technique for execution monitoring of sequential plans. On standard benchmark planning domains, our approach is 2 to 17 times faster and up to 2. 5 times more robust than comparable monitoring of a sequential plan. On POPs that have few ordering constraints among actions, our approach is significantly more robust, with the ability to continue executing in up to an exponential number of additional states.

ICAPS Conference 2011 Conference Paper

Scheduling an Aircraft Repair Shop

• Maliheh Aramon Bajestani
• J. Christopher Beck

We address a scheduling problem in the context of military aircraft maintenance where the goal is to meet the aircraft requirements for a number of missions in the presence of breakdowns. The assignment of aircraft to a mission must consider the requirements for the mission, the probability of aircraft failure, and capacity of the repair shop that maintains the aircraft. Therefore, a solution both assigns aircraft to missions and schedules the repair shop to meet the assignments. We propose a dispatching heuristic algorithm; three complete approaches based on mixed integer programming, constraint programming, and logic-based Benders decomposition; and a hybrid heuristic-complete approach. Experiments demonstrate that the logic-based Benders variation combining mixed integer programming and constraint programming outperforms the other approaches, that the dispatching heuristic can feasibly schedule the repair shop in a very short time, and that using the dispatching solution as a bound marginally improves the complete approaches.

EAAI Journal 2008 Journal Article

A global constraint for total weighted completion time for cumulative resources

• András Kovács
• J. Christopher Beck

The criterion of total weighted completion time occurs as a sub-problem of combinatorial optimization problems in such diverse areas as scheduling, container loading and storage assignment in warehouses. These applications often necessitate considering a rich set of requirements and preferences, which makes constraint programming (CP) an effective modeling and solving approach. On the other hand, basic CP techniques can be inefficient in solving models that require inference over sum type expressions. In this paper, we address increasing the solution efficiency of constraint-based approaches to cumulative resource scheduling with the above criterion. Extending previous results for unary capacity resources, we define the COMPLETION m global constraint for propagating the total weighted completion time of activities that require the same cumulative resource. We present empirical results in two different problem domains: scheduling a single cumulative resource, and container loading with constraints on the location of the center of gravity. In both domains, the proposed constraint propagation algorithm out-performs existing propagation techniques.

IJCAI Conference 2007 Conference Paper

• Julien Bidot
• Thierry Vidal
• Philippe Laborie
• J. Christopher Beck

There are many systems and techniques that address stochastic scheduling problems, based on distinct and sometimes opposite approaches, especially in terms of how scheduling and schedule execution are combined, and if and when knowledge about the uncertainties are taken into account. In many real-life problems, it appears that all these approaches are needed and should be combined, which to our knowledge has never been done. Hence it it first desirable to define a thorough classification of the techniques and systems, exhibiting relevant features: in this paper, we propose a tree-dimension typology that distinguishes between proactive, progressive, and revision techniques. Then a theoretical representation model integrating those three distinct approaches is defined. This model serves as a general template within which parameters can be tuned to implement a system that will fit specific application needs: we briefly introduce in this paper our first experimental prototypes which validate our model.

ICAPS Conference 2006 Conference Paper

An Empirical Study of Multi-Point Constructive Search for Constraint-Based Scheduling

• J. Christopher Beck

Multi-point constructive search (MPCS) performs a series of resource-limited backtracking searches where each search begins either from an empty solution (as in randomized restart) or from a solution that has been encountered during the search. We perform a systematic study of MPCS to evaluate the performance impact of various parameter settings. Results using job shop scheduling instances with two different optimization criteria, demonstrate that MPCS-based search is significantly better than standard chronological backtracking and randomized restart while raising a number of questions as to the underlying reasons for the observed performance.

IJCAI Conference 2005 Conference Paper

Proactive Algorithms for Scheduling with Probabilistic Durations

• J. Christopher Beck
• Nic

Proactive scheduling seeks to generate high quality solutions despite execution time uncertainty. Building on work in [Beck and Wilson, 2004], we conduct an empirical study of a number of algorithms for the job shop scheduling problem with probabilistic durations. The main contributions of this paper are: the introduction and empirical analysis of a novel constraint-based search technique that can be applied beyond probabilistic scheduling problems, the introduction and empirical analysis of a number of deterministic filtering algorithms for probabilistic job shop scheduling, and the identification of a number of problem characteristics that contribute to algorithm performance.

ECAI Conference 2004 Conference Paper

Failing First: An Update

• J. Christopher Beck
• Patrick Prosser
• Richard J. Wallace

ECAI Conference 2004 Conference Paper

Job Shop Scheduling with Probabilistic Durations

• J. Christopher Beck
• Nic Wilson

AAAI Conference 2004 Conference Paper

Low-Knowledge Algorithm Control

• Tom Carchrae
• J. Christopher Beck

This paper addresses the question of allocating computational resources among a set of algorithms in order to achieve the best performance on a scheduling problem instance. Our primary motivation in addressing this problem is to reduce the expertise needed to apply constraint technology. Therefore, we investigate algorithm control techniques that make decision based only on observations of the improvement in solution quality achieved by each algorithm. We call our approach “low-knowledge” since it does not rely on complex prediction models. We show that such an approach results in a system that achieves significantly better performance than all of the pure algorithms without requiring additional human expertise. Furthermore the low knowledge approach achieves performance equivalent to a perfect high-knowledge classification approach.

ICAPS Conference 2003 Conference Paper

Vehicle Routing and Job Shop Scheduling: What's the Difference?

• J. Christopher Beck
• Patrick Prosser
• Evgeny Selensky

Despite a number of similarities, vehicle routing problems and scheduling problems are typically solved with different techniques. In this paper, we undertake a systematic study of problem characteristics that differ between vehicle routing and scheduling problems in order to identify those that are important for the performance of typical vehicle routing and scheduling techniques. In particular, we find that the addition of temporal constraints among visits or the addition of tight vehicle specialization constraints significantly improves the performance of scheduling techniques relative to vehicle routing techniques.

ICAPS Conference 2000 Conference Paper

Heuristics for Constraint-Directed Scheduling with Inventory

• J. Christopher Beck

A Simple Inventory Scheduling Problem Despite the importance of the management of inventory in industrial scheduling applications, there has been little research that has addressed reasoning about inventory directly as part of a scheduling problem. In this paper, we represent inventory, inventory storage constraints, and inventory production and consumption in a constraint-directed scheduling framework. Inventory scheduling is then used to investigate heuristic commitment techniques based on the understanding and the exploitation of problem structure. A technique for the estimation of probability of breakage for resource and inventory constraints is presented together with a heuristic commitment technique based on the estimate of constraint criticality. It is empirically demonstrated that a heuristic commitment technique that exploits dynamic constraint criticality achieves superior overall performance. An n ✕ m inventory scheduling problem consists of n jobs and m resources. Each job is composed of m activities, each using a different resource. Each activity, Aij, in job, j: • has a constant duration, durij. • uses one resource, Rij, with no interruption, for its entire duration. • is completely ordered with the other activities in job j. If Aij is before Akj in the complete ordering, Aij must finish executing before Akj can begin executing. • may consume some amount of one or more inventories. Consumption is assumed to happen instantaneously at the start of execution. • may produce some amount of one or more inventories. Production is assumed to happen instantaneously at the end of execution. In addition to the precedence constraints among activities in the same job, there are two additional types of constraints: 1. Unary resource constraints – each resource can be used by at most one activity at any time point. 2. Inventory constraints – each inventory has a maximum and minimum constraint which specify, respectively, the maximum and minimum amount of each type of inventory that can exist at any time point. The jobs, activities, activity characteristics (duration, resource usage, inventory production/consumption), resources, and inventories are all given in the problem definition. A solution consists of a sequence of activities on each resource such that all constraints (precedence, resource, and inventory) are satisfied. This problem definition represents the minimal addition of inventory representation to the job shop scheduling problem (Garey and Johnson, 1979; Blazewicz et al., 1996). While real-world inventory problems contain more complex inventory requirements (Beck, 1999), the relative lack of research literature addressing such requirements mandates a simple problem definition so that we can begin to systematically investigate inventory scheduling.

AAAI Conference 1999 Conference Paper

Scheduling Alternative Activities

• J. Christopher Beck
• ILOG
• S.A.
• Mark S. Fox
• University of Toronto

In realistic scheduling problems, there may be choices among resources or among process plans. We formulate a constraint-based representation of alternative activities to model problems containing such choices. We extend existing constraint-directed scheduling heuristic commitment techniques and propagators to reason directly about the fact that an activity does not necessarily have to exist in a final schedule. Experimental results show that an algorithm using a novel texture-based heuristic commitment technique together with extended edge-finding propagators achieves the best overall performance of the techniques tested.

AAAI Conference 1997 Conference Paper

Beyond Contention: Extending Texture-Based Scheduling Heuristics

• J. Christopher Beck
• Edward M. Sitarski

In order to apply texture measurement based heuristic commitment techniques beyond the unary capacity resource constraints of job shop scheduling, we extend the contention texture measurement to a measure of the probability that a constraint will be broken. We define three methods for the estimation of this probability and show that they perform as well or better than existing heuristics on job shop scheduling problems. Empirical insight into the performance is provided and we sketch how we have extended probability-based heuristics to more complicated scheduling constraints. the “probability of breakage” of a constraint will allow us to directly compare the criticality of different types of constraints. We present three new techniques for estimating the probability of breakage of the resource constraint in job shop scheduling and compare the performance of heuristics based on these estimations against earlier texture-based and non-texture-based heuristics for scheduling. We also describe how our estimation techniques can be extended to more complicated scheduling domains.

AAAI Conference 1997 Conference Paper

Texture-Based Heuristics for Scheduling Revisited

• J. Christopher Beck
• Edward M. Sitarski

Recent scheduling work has challenged the need for sophisticated heuristics such as those based on texture measurements. This paper examines these claims in the light of advances in scheduling technology. We compare a number of current heuristic commitment techniques against a texture-based heuristic. Our results demonstrate that texture-based heuristics can outperform these widely-used heuristic commitment techniques. tics with the same consistency techniques (Nuijten, 1994). In this paper we re-evaluate texture-based heuristics in light of recent advances in scheduling technology and show that on two job shop scheduling problem sets (a widely used set of Operations Research benchmark problems and a set of randomly generated, hard problems) a texture-based heuristic outperforms heuristic commitment techniques found in the literature.