Author name cluster

University of Alberta

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.

6 papers

1 author row

AAAI Conference 1999 Conference Paper

Constraint-Based Integrity Checking in Abductive and Nonmonotonic Extensions of Constraint Logic Programming

Aditya K. Ghose
University of Wollongong
Srinivas Padmanabhuni
University of Alberta
Edmonton

Recent research on the integration of the abductive and constraint logic programmingparadigms has led to systems which are both expressive and computationally efficient. This paper investigates the role of constraints in integrity checkingin the context of such systems. Providingsupport for constraints in this role leads to a framework that is significantly moreexpressive, withoutsignificant loss in efficiency. We augment the Abductive Constraint Logic Programmingframeworkwith assumedconstraints and provide model- and proof-theoretic accountsof twovariants: one whichinvolves commitment to such assumptions, and one which does not. Wealso showthat such accounts extend easily to a constraint logic programming framework which supports both negation and assumedconstraints. The gains in expressivity in these frameworks turn out to be particularly useful in a variety of application domains, including scheduling and constraint database updates.

PDF Details

AAAI Conference 1999 Conference Paper

CPlan: A Constraint Programming Approach to Planning

Peter van Beek
Xinguang Chen
University of Alberta

Constraint programming, a methodology for solving difficult combinatorial problems by representing them as constraint satisfaction problems, has shown that a general purpose search algorithm based on constraint propagation combined with an emphasis on modeling can solve large, practical scheduling problems. Given the success of constraint programming on scheduling problems and the similarity of scheduling to planning, the question arises, would a constraint programming approach work as well in planning? In this paper, we present evidencethat a constraint programming approach to planning does indeed work well and has the advantage in terms of time and space efficiency over the current state-of-the-art planners.

PDF Details

AAAI Conference 1999 Short Paper

Learning Rewrite Rules to Improve Plan Quality

Muhammad Afzal Upal
University of Alberta

This paper presents a system called REWRITE that automatically learns rewrite rules. REWRITE has three main components. The first is a partial-order causal-link planner (POP). The second component does the analytic work of identifying the replacing and to-be-replaced action sequences. The third component is a case library of plan-rewrite rules.

PDF Details

AAAI Conference 1999 Conference Paper

Point-Based Approaches to Qualitative Temporal Reasoning

J. Delgrande
A. Gupta
Simon Fraser University; T. Van Allen
University of Alberta

Weaddress the general problemof finding algorithms for efficient, qualitative, point-basedtemporalreasoning over a set of operations. Weconsider general reasonerstailored for temporaldomains that exhibit a particular structure and introduce such a reasoner based on the series-parallel graph reasoner of Delgrandeand Gupta; this reasoner is also an extension of the Time- Graphreasoner of Gerevini and Schubert. Test results indicate that for data with underlying structure, our reasoner performs better than other approaches. When there is no underlying structure in the data, our reasoner still performsbetter for query answering.

PDF Details

AAAI Conference 1999 Conference Paper

Transposition Table Driven Work Scheduling in Distributed Search

John W. Romein
Aske Plaat
Henri E. Bal
Vrije Universiteit; Jonathan Schaeffer
University of Alberta

This paper introduces a new scheduling algorithm for parallel single-agent search, transposition table driven work scheduling, that places the transposition table at the heart of the parallel work scheduling. The scheme results in less synchronization overhead, less processor idle time, and less redundant search effort. Measurements on a 128-processor parallel machine show that the scheme achieves nearly-optimal performance and scales well. The algorithm performs a factor of 2. 0 to 13. 7 times better than traditional work-stealing-based schemes.

PDF Details

AAAI Conference 1999 Conference Paper

Using Probabilistic Knowledge and Simulation to Play Poker

Darse Billings
Lourdes Peña
Jonathan Schaeffer
Duane Szafron
University of Alberta

Until recently, artificial intelligence researchers who use games as their experimental testbed have concentrated on games of perfect information. Many of these games have been amenable to so-called brute-force search techniques. In contrast, games of imperfect information, such as bridge and poker, contain hidden knowledge making similar search techniques impractical. This paper describes recent progress in developing a high-performance poker-playing program. The advances come in two forms. First, we introduce a new betting strategy that returns a probabilistic betting decision, a probability triple, that gives the likelihood of a fold, call or raise occurring in a given situation. This routine unifies all the expert knowledge used in the program, does a better job of representing the type of decision making needed to play strong poker, and improves the way information is propagated throughout the program. Second, real-time simulations are used to compute the expected values of betting decisions. The program generates an instance of the missing data, subject to any constraints that have been learned, and then simulates the rest of the game to determine a numerical result. By repeating this a sufficient number of times, a statistically meaningful sample can be obtained to be used in the program’s decision-making process. Experimental results show that these enhancements each represent major advances in the strength of computer poker programs.

PDF Details