Author name cluster

David Furcy

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.

8 papers

2 author rows

TCS Journal 2021 Journal Article

On the effects of hierarchical self-assembly for reducing program-size complexity

Sarah Cannon
Erik D. Demaine
Martin L. Demaine
Sarah Eisenstat
David Furcy
Matthew J. Patitz
Robert Schweller
Scott M. Summers

In this paper we present a series of results which show separations between the standard seeded model of self-assembly, Winfree's abstract Tile Assembly Model (aTAM), and the “seedless” 2-Handed Assembly Model (2HAM), which incorporates the dynamics of hierarchical self-assembly. In particular, we focus on the problem of self-assembling various shapes while minimizing the sizes of tile sets, or “programs”, in each of these models in order to compare and contrast the models. A high-level overview of a subset of these results was presented in a paper by the authors in STACS 2013, but in this version we expand and improve the set of results related to showing separations between the two models according to their abilities to self-assemble various shapes. We exhibit classes of finite shapes that can be self-assembled more efficiently in each model. We also demonstrate infinite shapes that can self-assemble in one model but not in the other, as well as a shape which cannot self-assemble in either model.

Details DOI

TCS Journal 2021 Journal Article

Self-assembly of and optimal encoding within thin rectangles at temperature-1 in 3D

David Furcy
Scott M. Summers
Christian Wendlandt

In this paper, we study the self-assembly of rectangles in a non-cooperative, 3D version of Winfree's abstract Tile Assembly Model. We prove two results. First, we give the full details for the proof of a general construction for the efficient self-assembly of thin rectangles that was first reported by Furcy, Summers and Wendlandt (2019). This construction is non-cooperative and “just-barely” 3D in the sense that it places tiles at most one step into the third dimension. Second, we give a non-cooperative, just-barely 3D optimal encoding construction that self-assembles the bits of a given binary string along the perimeter of a thin rectangle of constant height.

Details DOI

AIJ Journal 2006 Journal Article

Maximizing over multiple pattern databases speeds up heuristic search

Robert C. Holte
Ariel Felner
Jack Newton
Ram Meshulam
David Furcy

A pattern database (PDB) is a heuristic function stored as a lookup table. This paper considers how best to use a fixed amount (m units) of memory for storing pattern databases. In particular, we examine whether using n pattern databases of size m / n instead of one pattern database of size m improves search performance. In all the state spaces considered, the use of multiple smaller pattern databases reduces the number of nodes generated by IDA*. The paper provides an explanation for this phenomenon based on the distribution of heuristic values that occur during search.

Details DOI

IJCAI Conference 2005 Conference Paper

Limited Discrepancy Beam Search

David Furcy
Sven

Beam search reduces the memory consumption of bestfirst search at the cost of finding longer paths but its memory consumption can still exceed the given memory capacity quickly. We therefore develop BULB (Beam search Using Limited discrepancy Backtracking), a complete memory-bounded search method that is able to solve more problem instances of large search problems than beam search and does so with a reasonable runtime. At the same time, BULB tends to find shorter paths than beam search because it is able to use larger beam widths without running out of memory. We demonstrate these properties of BULB experimentally for three standard benchmark domains.

PDF

IJCAI Conference 2005 Conference Paper

Scaling up WA* with Commitment and Diversity

David Furcy
Sven

Weighted A* (WA*) is a popular search technique that scales up A* while sacrificing solution quality. Recently, researchers have proposed two variants of WA*: KWA* adds diversity to WA*, and MSC-WA* adds commitment to WA*. In this paper, we demonstrate that there is benefit in combining them. The resulting MSC-KWA* scales up to larger domains than WA*, KWA* and MSC-WA*, which is rather surprising since diversity and commitment at first glance seem to be opposing concepts.

PDF

AIJ Journal 2004 Journal Article

Lifelong Planning A∗

Sven Koenig
Maxim Likhachev
David Furcy

Heuristic search methods promise to find shortest paths for path-planning problems faster than uninformed search methods. Incremental search methods, on the other hand, promise to find shortest paths for series of similar path-planning problems faster than is possible by solving each path-planning problem from scratch. In this article, we develop Lifelong Planning A∗ (LPA∗), an incremental version of A∗ that combines ideas from the artificial intelligence and the algorithms literature. It repeatedly finds shortest paths from a given start vertex to a given goal vertex while the edge costs of a graph change or vertices are added or deleted. Its first search is the same as that of a version of A∗ that breaks ties in favor of vertices with smaller g-values but many of the subsequent searches are potentially faster because it reuses those parts of the previous search tree that are identical to the new one. We present analytical results that demonstrate its similarity to A∗ and experimental results that demonstrate its potential advantage in two different domains if the path-planning problems change only slightly and the changes are close to the goal.

Details DOI

ICAPS Conference 2004 Conference Paper

Multiple Pattern Databases

Robert C. Holte
Jack Newton
Ariel Felner
Ram Meshulam
David Furcy

A patterndatabase is a heuristic function stored as a lookup table. This paper considers how best to use a fixed amount (m units) of memory for storing pattern databases. In particular, we examine whether using n pattern databases of size m=n instead of one pattern database of size m improves search performance. In all the domains considered, the use of multiple smaller pattern databases reduces the number of nodes generated by IDA*. The paper provides an explanation for this phenomenon based on the distribution of heuristic values that occur during search.

Details

ICAPS Conference 2002 Conference Paper

Heuristic Search-Based Replanning

Sven Koenig
David Furcy
Colin Bauer

Many real-world planning problems require one to solve a series of similar planning tasks. In this case, replanning can be much faster than planning from scratch. In this paper, we introduce a novel replanning method for symbolic planning with heuristic search-based planners, currently the most popular planners. Our SHERPA replanner is not only the first heuristic search-based replanner but, different from previous replanners for other planning paradigms, it also guarantees that the quality of its plans is as good as that achieved by planning from scratch. We provide an experimental feasibility study that demonstrates the promise of SHERPA for heuristic search-based replanning.

Details