Managing Occurrence Branching in Qualitative Simulation

AAAI Conferences

Qualitative simulators can produce common sense abstractions of complex behaviors, however, they can also produce an intractable explosion of meaningless behaviors because they attempt to combinatorially order uncorrelated events. People who build brick walls obtain bricks, cement, and tools, and proceed to lay the wall. They don't worry about whether they obtain bricks then tools then cement, or cement, then tools, then bricks, or cement, then bricks, then tools, or cement and bricks, then tools, etc. Common sense tell them that the order in which the events are completed does not matter, what matters is that the events are completed before the wall is laid. Qualitative simulators fail the common sense challenge when confronted with similar problems. Simulators such as QSIM (Kuipers 1994) attempt to calculate all possible orderings of inherently unordered events which can lead to intractable branching in models of even modest size. This paper presents a representation (L-behavior diagrams), an algorithm (L-filter), and a simulator (LSIM) which manages this complexity.


Back to the Future for Consistency-based Trajectory Tracking

AAAI Conferences

Given a model of a physical process and a sequence of commands and observations received over time, the task of an autonomous controller is to determine the likely states of the process and the actions required to move the process to a desired configuration. We introduce a representation and algorithms for incrementally generating approximate belief states for a restricted but relevant class of partially observable Markov decision processes with very large state spaces. The algorithm incrementally generates, rather than revises, an approximate belief state at any point by abstracting and summarizing segments of the likely trajectories of the process.


A Planning Heuristic Based on Causal Graph Analysis

AAAI Conferences

In recent years, heuristic search methods for classical planning have achieved remarkable results. Their most successful representative, the FF algorithm, performs well over a wide spectrum of planning domains and still sets the state of the art for STRIPS planning. However, there are some planning domains in which algorithms like FF and HSP perform poorly because their relaxation method of ignoring the "delete lists" of STRIPS operators loses too much vital information. Planning domains which have many dead ends in the search space are especially problematic in this regard. In some domains, dead ends are readily found by the human observer yet remain undetected by all propositional planning systems we are aware of. We believe that this is partly because the STRIPS representation obscures the important causal structure of the domain, which is evident to humans. In this paper, we propose translating STRIPS problems to a planning formalism with multi-valued state variables in order to expose this underlying causal structure. Moreover, we show how this structure can be exploited by an algorithm for detecting dead ends in the search space and by a planning heuristic based on hierarchical problem decomposition. Our experiments show excellent overall performance on the benchmarks from the international planning competitions.


SAS Planning as Satisfiability

AAAI Conferences

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS formalism. The new scheme exploits the structural information in SAS, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.


SAS+ Planning as Satisfiability

Journal of Artificial Intelligence Research

Planning as satisfiability is a principal approach to planning with many eminent advantages. The existing planning as satisfiability techniques usually use encodings compiled from STRIPS. We introduce a novel SAT encoding scheme (SASE) based on the SAS+ formalism. The new scheme exploits the structural information in SAS+, resulting in an encoding that is both more compact and efficient for planning. We prove the correctness of the new encoding by establishing an isomorphism between the solution plans of SASE and that of STRIPS based encodings. We further analyze the transition variables newly introduced in SASE to explain why it accommodates modern SAT solving algorithms and improves performance. We give empirical statistical results to support our analysis. We also develop a number of techniques to further reduce the encoding size of SASE, and conduct experimental studies to show the strength of each individual technique. Finally, we report extensive experimental results to demonstrate significant improvements of SASE over the state-of-the-art STRIPS based encoding schemes in terms of both time and memory efficiency.