Author name cluster

Duke University

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.

7 papers

1 author row

AAAI Conference 1999 Conference Paper

Contingent Planning Under Uncertainty via Stochastic Satisfiability

Stephen M. Majercik
Michael L. Littman
Duke University

Wedescribe two newprobabilistic planning techniques--C-MAXPLAN and ZANDER--that generate contingent plans in probabilistic propositional domains. Both operate by transforming the planning problem into a stochastic satisfiability problem andsolving that problem instead. C-MAXPLAN encodes the problem as an E-MAJSAT instance, while ZANDER encodes the problemas an S-SATinstance. Although S-SATproblems are in a higher complexity class than E-MAJSAT problems, the problem encodings produced by ZANDER are substantially morecompactandappear to be easier to solve than the corresponding E-MAJSAT encodings. Preliminaryresults for ZANDER indicate that it is competitive with existing plannerson a variety of problems.

PDF Details

AAAI Conference 1999 Conference Paper

Initial Experiments in Stochastic Satisfiability

Michael L. Littman
Duke University

This paper looks at the rich intersection between satisfiability problems and probabilistic models, openingthe door for the use of satisfiability approaches in probabilistic domains. A generic stochastic satisfiability problemis examined, whichcan function for probabilistic domains as SAT does for deterministic domains. Thepaper defines a Davis-Putnam-Logemann-Loveland-style procedurefor solving stochastic satisfiability problems, and reports on a preliminary empirical exploration of the complexity of the algorithm for a collection of randomlygenerated probabilistic problems. Theresults exhibit the familiar easyhardest-hard pattern for the difficulty of random SAT formulae. Special cases of the stochastic satisfiability problem lie in different complexity classes, and onecounterintuitive result is that the computational complexity and the empirical complexity of the problems examineddo not track each other exactly--problems in the hardest complexityclass are not the hardest to solve.

PDF Details

AAAI Conference 1999 Short Paper

Planning under Uncertainty via Stochastic Satisfiability

Stephen M. Majercik
Duke University

A probabilistic propositional planning problem can be solved by converting it to a stochastic satisfiability problem and solving that problem instead. I have developed three planners that use this approach: maxplan , c-maxplan , and zander . maxplan , which assumes complete unobservability, converts a dynamic belief network representation of the planning problem to an instance of a stochastic satisfiability problem called E-Majsat . maxplan then solves that problem using a modified version of the Davis-Putnam-Logemann-Loveland (DPLL) procedure for determining satisfiability along with time-ordered splitting and memoization.

PDF Details

AAAI Conference 1999 Conference Paper

Proverb: The Probabilistic Cruciverbalist

Greg A. Keim
Noam M. Shazeer
Michael L. Littman
Sushant Agarwal
Catherine M. Cheves
Joseph Fitzgerald
Jason Grosland
Fan Jiang

Weattacked the problemof solving crosswordpuzzles by computer: given a set of clues and a crossword grid, try to maximizethe numberof wordscorrectly filled in. In our system, "expert modules"specialize in solving specific types of clues, drawingon ideas from information retrieval, database search, and machine learning. Eachexpert modulegenerates a (possibly empty)candidate list for each clue, andthe lists are mergedtogether andplaced into the grid by a centralized solver. Weused a probabilistic representation throughout the system as a common interchange language betweensubsystemsand to drive the search for an optimal solution. PROVERB, the complete system, averages 95. 3%wordscorrect and 98. 1%letters correct in under 15 minutesper puzzle on a sampleof 370 puzzles taken from the New YorkTimesand several other puzzle sources. This corresponds to missing roughly 3 wordsor 4 letters on a daily 15 x 15 puzzle, making PROVERB a better-than-average cruciverbalist (crosswordsolver),

PDF Details

AAAI Conference 1999 Short Paper

Robot Navigation with a Polar Neural Map

Michail G. Lagoudakis
Duke University
Anthony S. Maida
University of Southwestern Louisiana

Neural maps have been recently proposed as an alternative method for mobile robot path planning. However, these proposals are mostly theoretical and are primarily concerned with biological plausibility. Our purpose is to investigate their applicability on real robots.

PDF Details

AAAI Conference 1999 Conference Paper

Solving Crossword Puzzles as Probabilistic Constraint Satisfaction

Noam M. Shazeer
Michael L. Littman
Greg A. Keim
Duke University

Crossword puzzle solving is a classic constraint satisfaction problem, but, whensolving a real puzzle, the mapping fromclues to variable domainsis not perfectly crisp. At best, clues inducea probability distribution over viable targets, whichmust somehow be respected along with the constraints of the puzzle. Motivated by this type of problem, wedescribe a formal model of constraint satisfaction with probabilistic preferences on variable values. Twonatural optimization problems are defined for this model: maximizingthe probability of a correct solution, and maximizingthe number of correct words(variable values) in the solution. the latter, weapplyan efficient iterative approximation equivalent to turbo decodingandpresent results on a collection of real andartificial crossword puzzles.

PDF Details

AAAI Conference 1999 Conference Paper

Solving Crosswords with Proverb

Michael L. Littman
Greg A. Keim
Noam M. Shazeer
Duke University

We attacked the problem of solving crossword puzzles by computer: Given a set of clues and a crossword grid, try to maximize the number of words correctly filled in. Proverb , the probabilistic cruciverbalist, separates the problem into two, more familiar subproblems: candidate generation and grid filling. In candidate generation, each clue is treated as a type of query to an information retrieval system, and relevant words of the correct length are returned along with confidence scores. In grid filling, the candidate words are fit into the puzzle grid to maximize an overall confidence score using a combination of ideas from belief network inference and constraint satisfaction. For our demonstration, we will have an interactive version of the candidate-generation process available via the web, and will also give people an opportunity to go head-to- head against Proverb in solving complete puzzles.

PDF Details