Author name cluster
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.
ECAI Conference 2012 Conference Paper
Until recently, game-tree pathology (in which a deeper game-tree search results in worse play) has been thought to be quite rare. We provide an analysis that shows that every game should have some sections that are locally pathological, assuming that both players can potentially win the game.
AIJ Journal 2010 Journal Article
There is now extensive interest in reasoning about moving objects. A probabilistic spatio-temporal (PST) knowledge base (KB) contains atomic statements of the form “Object o is/was/will be in region r at time t with probability in the interval [ ℓ, u ] ”. In this paper, we study mechanisms for belief revision in PST KBs. We propose multiple methods for revising PST KBs. These methods involve finding maximally consistent subsets and maximal cardinality consistent subsets. In addition, there may be applications where the user has doubts about the accuracy of the spatial information, or the temporal aspects, or about the ability to recognize objects in such statements. We study belief revision mechanisms that allow changes to the KB in each of these three components. Finally, there may be doubts about the assignment of probabilities in the KB. Allowing changes to the probability of statements in the KB yields another belief revision mechanism. Each of these belief revision methods may be epistemically desirable for some applications, but not for others. We show that some of these approaches cannot satisfy AGM-style axioms for belief revision under certain conditions. We also perform a detailed complexity analysis of each of these approaches. Simply put, all belief revision methods proposed that satisfy AGM-style axioms turn out to be intractable with the exception of the method that revises beliefs by changing the probabilities (minimally) in the KB. We also propose two hybrids of these basic approaches to revision and analyze the complexity of these hybrid methods.
AIJ Journal 2010 Journal Article
In situations where one needs to make a sequence of decisions, it is often believed that looking ahead will help produce better decisions. However, it was shown 30 years ago that there are “pathological” situations in which looking ahead is counterproductive. Two long-standing open questions are (a) what combinations of factors have the biggest influence on whether lookahead pathology occurs, and (b) whether it occurs in real-world decision-making. This paper includes simulation results for several synthetic game-tree models, and experimental results for three well-known board games: two chess endgames, kalah (with some modifications to facilitate experimentation), and the 8-puzzle. The simulations show the interplay between lookahead pathology and several factors that affect it; and the experiments confirm the trends predicted by the simulation models. The experiments also show that lookahead pathology is more common than has been thought: all three games contain situations where it occurs.
AAAI Conference 2008 Conference Paper
There is now extensive interest in reasoning about moving objects. A PST knowledge base is a set of PST-atoms which are statements of the form “Object o is/was/will be at location L at time t with probability in the interval [L, U]”. In this paper, we study mechanisms for belief revision in PST- KBs. We propose multiple methods for revising PST-KBs. These methods involve finding maximally consistent subsets, as well as changing the spatial, temporal, and probabilistic components of the atoms. We show that some methods cannot satisfy the AGM axioms for belief revision, while others do but are coNP-hard. Finally we present an algorithm for revision through probability change which runs in polynomial time and satisfies the AGM axioms.
IJCAI Conference 2007 Conference Paper
There are numerous cases where we need to reason about vehicles whose intentions and itineraries are not known in advance to us. For example, Coast Guard agents tracking boats don't always know where they are headed. Likewise, in drug enforcement applications, it is not always clear where drug-carrying airplanes (which do often show up on radar) are headed, and how legitimate planes with an approved flight manifest can avoid them. Likewise, traffic planners may want to understand how many vehicles will be on a given road at a given time. Past work on reasoning about vehicles (such as the "logic of motion" by Yaman et. al. ) only deals with vehicles whose plans are known in advance and don't capture such situations. In this paper, we develop a formal probabilistic extension of their work and show that it captures both vehicles whose itineraries are known, and those whose itineraries are not known. We show how to correctly answer certain queries against a set of statements about such vehicles. A prototype implementation shows our system to work efficiently in practice.
AAAI Conference 2006 Conference Paper
We derive a recursive formula for expected utility values in imperfect- information game trees, and an imperfectinformation game tree search algorithm based on it. The formula and algorithm are general enough to incorporate a wide variety of opponent models. We analyze two opponent models. The “paranoid” model is an information-set analog of the minimax rule used in perfect-information games. The “overconfident” model assumes the opponent moves randomly. Our experimental tests in the game of kriegspiel chess (an imperfect-information variant of chess) produced surprising results: (1) against each other, and against one of the kriegspiel algorithms presented at IJCAI-05, the overconfident model usually outperformed the paranoid model; (2) the performance of both models depended greatly on how well the model corresponded to the opponent’s behavior. These results suggest that the usual assumption of perfect-information game tree search—that the opponent will choose the best possible move—isn’t as useful in imperfect-information games.
IJCAI Conference 2005 Conference Paper
In games such as kriegspiel chess (a chess variant where players have no direct knowledge of the opponent’s pieces’ locations) the belief state’s sizes dwarf those of other partial information games like bridge, scrabble, and poker–and there is no easy way to generate states satisfying the given observations. We show that statistical sampling approaches can be developed to do well in such games. We show that it is not necessary for the random sample to consist only of game boards that satisfy each and every one of a player’s observations. In fact, we win 24% more often by beginning with such completely consistent boards and gradually switching (as the game progressed) to boards that are merely consistent with the latest observation. This surprising result is explained by noting that as the game progresses, a board that is consistent with the last move becomes more and more likely to be consistent with the entire set of observations, even if we have no idea what sequence of moves might have actually generated this board.