Association for the Advancement of Artificial Intelligence: AAAI Publications
Not a member yet
26155 research outputs found
Sort by
Just-In-Time Scheduling with Constraint Programming
No full textThis paper considers Just-In-Time Job-Shop Scheduling, in which each activity has an earliness and a tardiness cost with respect to a due date. It proposes a constraint programming approach, which includes a novel filtering algorithm and dedicated heuristics. The filtering algorithm uses a machine relaxation to produce a lower bound that can be obtained by solving a Just-In-Time Pert problem. It also includes pruning rules which update the variable bounds and detect precedence constraints. The paper presents experimental results which demonstrate the effectiveness of the approach over a wide range of benchmarks
Forward Constraint-Based Algorithms for Anytime Planning
No full textThis paper presents a generic anytime forward-search constraint-based algorithm for solving planning problems expressed in the CNT framework (Constraint Network on Timelines). It is generic because it allows many kinds of search to be covered, from complete tree search to greedy search. It is anytime because some parameter settings, together with domain-specific knowledge, allow high quality plans to be produced very quickly and to be further improved. It is forward because it systematically considers the decisions to be made in a chronological order. It is finally constraint-based because it is built on top of the CNT framework which is an extension of the CSP framework able to model discrete event dynamic systems and because it is implemented on top of the Choco constraint programming tool from which it inherits all the constraint handling machinery. Experimental comparisons are made in terms of quality profile with other domain-dependent and domain-independent planners
A Decision-Theoretic Approach to Dynamic Sensor Selection in Camera Networks
No full textNowadays many urban areas have been equipped with networks of surveillance cameras, which can be used for automatic localization and tracking of people. However, given the large resource demands of imaging sensors in terms of bandwidth and computing power, processing the image streams of all cameras simultaneously might not be feasible. In this paper, we consider the problem of dynamical sensor selection based on user-defined objectives, such as maximizing coverage or improved localization uncertainty. We propose a decision-theoretic approach modeled as a POMDP, which selects k sensors to consider in the next time frame, incorporating all observations made in the past. We show how, by changing the POMDP's reward function, we can change the system's behavior in a straightforward manner, fulfilling the user's chosen objective. We successfully apply our techniques to a network of 10 cameras
Computing Robust Plans in Continuous Domains
No full textWe define the robustness of a sequential plan as the probability that it will execute successfully despite uncertainty in the execution environment. We consider a rich notion of uncertainty over continuous domains that includes stochastic action effects, and changes to state variables due to unpredictable exogenous events. Given a characterization of this uncertainty in terms of probability distributions (e.g., Gaussian) our contributions are two-fold: First, we describe a novel approach to computing the robustness of a plan in the situation calculus, which (a) separates the projection problem from the problem of reasoning about probability, and (b) explicitly reveals the relevance and statistical independence of random variables and events (i.e., conditions that contain random variables). Then, building on this approach, we describe a forward search based planner that generates maximally robust plans, exploiting the revealed structure for speed-up. Preliminary empirical results demonstrate that our approach can realize exponential savings in both time and space compared to the classical sampling approach
Evaluating the Authorial Leverage of Drama Management
No full textA drama manager (DM) monitors an interactive experience, such as a computer game, and intervenes to shape the global experience so that it satisfies the author’s expressive goals without decreasing a player’s interactive agency. Most research on drama management has proposed AI architectures and provided abstract evaluations of their effectiveness; a smaller body of work has also evaluated the effect of drama management on player experience. Little attention has been paid, however, to evaluating the authorial leverage provided by a drama-management architecture: determining, for a given architecture, the additional non-linear story complexity a drama manager affords over traditional scripting methods. In this paper, we propose three criteria for evaluating the authorial leverage of a DM: (1) the script-and-trigger complexity of the DM story policy; (2) the degree of policy change given changes to story elements; and (3) the average story branching factor for DM policies versus script-and-trigger policies for stories of equivalent quality. We apply these criteria to declarative optimization-based drama management (DODM) by using decision tree learning to capture equivalent trigger logic, and show that DODM does in fact provide authorial leverag