Author name cluster

Tim Schmidt

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.

3 papers

2 author rows

SoCS Conference 2011 Conference Paper

Representing Pattern Databases with Succinct Data Structures

Tim Schmidt
Rong Zhou 0001

In this paper we describe novel representations for precomputed heuristics based on Level-Ordered Edge Sequence (LOES) encodings. We introduce compressed LOES, an extension to LOES that enables more aggressive compression of the state-set representation. We evaluate the novel repre- sentations against the respective perfect-hash and binary decision diagram (BDD) representations of pattern databases in a variety of STRIPS domains.

Details

AAAI Conference 2011 Conference Paper

Succinct Set-Encoding for State-Space Search

Tim Schmidt
Rong Zhou

We introduce the level-ordered edge sequence (LOES), a succinct encoding for state-sets based on preﬁx-trees. For use in state-space search, we give algorithms for member testing and element hashing with runtime dependent only on state size, as well as time and memory efﬁcient construction of and iteration over such sets. Finally we compare LOES to binary decision diagrams (BDDs) and explicitly packed setrepresentation over a range of IPC planning problems. Our results show LOES produces succinct set-encodings for a wider range of planning problems than both BDDs and explicit state representation, increasing the number of problems that can be solved cost-optimally.

PDF Details

SoCS Conference 2010 Conference Paper

Edge Partitioning in Parallel Structured Duplicate Detection

Rong Zhou 0001
Tim Schmidt
Eric A. Hansen
Minh Binh Do
Serdar Uckun

We show how edge partitioning, a technique originally developed for external-memory search, can be used to reduce the number of slow synchronization operations needed in parallel graph search. We show that edge partitioning improves on a previous technique called parallel structured duplicate detection by allowing a higher degree of concurrency, even for search problems with little or no inherent locality. For domain-independent graph search, we also show that edge partitioning significantly improves search speed by improving the efficiency of precondition checking. We demonstrate the effectiveness of this approach to parallel graph search for domain-independent STRIPS planning.

Details