Author name cluster

James Crawford

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

2 author rows

ICAPS Conference 2006 Conference Paper

Tractable Optimal Competitive Scheduling

Jeremy Frank
James Crawford
Lina Khatib
Ronen I. Brafman

In this paper we describe the problem of Optimal Competitive Scheduling, which consists of activities that compete for a shared resource. The objective is to choose a subset of activities to schedule, sequence them, and decide how much time they are allowed, in such a way that temporal and resource constraints are satisfied and overall schedule quality is maximized. While most such problems are NP-complete, very restricted versions of this problem are known to be tractable. In this work we describe tractable variations on this problem that correspond to realistic scheduling problems. The first class of tractable OCS problems arises due to limitations on the objective function that permit casting the problem as a Linear Program; with one additional assumption on activity feasibility windows, we identify a problem class where an optimal activity ordering can be found in polynomial time. The second class arises by reformulation of the problem as a Valued Constraint Satisfaction Problem and exploiting known results on tractability. We describe implementations of special-purpose algorithms designed to solve tractable OCS problems, and identify different solver performance characteristics based on properties of the problem instances.

Details

AAAI Conference 1990 Conference Paper

QPC: A Compiler from Physical Models into Qualitative Differential Equations

James Crawford

Qualitative reasoning can, and should, be decomposed into a model-buibding task, which creates a qualitative differential equation (&DE) as a model of a physical situation, and a qualitative simuhtion task, which starts with a QDE, and predicts the possible behaviors following from the model. In support of this claim, we present &PC, a model builder that takes the general approach of Qualitative Process Theory [Forbus, 19841, describing a scenario in terms of views, processes, and influences. However, &PC builds &DE s for simulation by QSIM, which gives it access to a variety of mathematical advances in qualitative simulation incorporated in QSIM. We present QPC and its approach to Qualitative Process Theory, provide an example of building and simulating a model of a non-trivial mechanism, and compare the representation and implementation decisions underlying &PC with those of QPE [Falkenhainer and Forbus, 1988; Forbus, 19901.

PDF Details