Author name cluster

David Joslin

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.

4 papers

1 author row

AAAI Conference 1997 Conference Paper

Exploiting Symmetry in Lifted CSPs

David Joslin

When search problems have large-scale symmetric structure, detecting and exploiting that structure can greatly reduce the size of the search space. Previous work has shown how to find and exploit symmetries in propositional encodings of constraint satisfaction problems (CSPs). Here we consider problems that have more compact “lifted” (quantified) descriptions from which propositional encodings can be generated. We describe an algorithm for finding symmetries in lifted representations of CSPs, and show sufficient conditions under which these symmetries can be mapped to symmetries in the propositional encoding. Using two domains (pigeonhole problems, and a CSP encoding of planning problems), we demonstrate experimentally that the approach of finding symmetries in lifted problem representations is a significant improvement over previous approaches that find symmetries in propositional encodings.

PDF Details

AAAI Conference 1996 Conference Paper

Is “Early Commitment” in Plan Generation Ever a Good Idea?

David Joslin

Partial-Order Causal Link planners typically take a “least-commitment” approach to some decisions (notably, step ordering), postponing those decisions until constraints force them to be made. However, these planners rely to some degree on early commitments in making other types of decisions, including threat resolution and operator choice. We show why existing planners cannot support full least-commitment decisionmaking, and present an alternative approach that can. The approach has been implemented in the Descartes system, which we describe. We also provide experimental results that demonstrate that a least-commitment approach to planning can be profitably extended beyond what is done in POCL and similar planners, but that taking a least-commitment approach to every planning decision can be inefficient: early commitment in plan generation is sometimes a good idea.

PDF Details

AAAI Conference 1994 Conference Paper

Least-Cost Flaw Repair: A Plan Refinement Strategy for Partial-Order Planning

David Joslin

We describe the least-cost flaw repair (LCFR) strategy for performing flaw selection during partial-order causal link (POCL) planning. LCFR can be seen as a generalization of Peot and Smith’ s “Delay Unforced Threats” (DUnf) strategy (Peot & Smith 1993); where DUnf treats threats differently from open conditions, LCFR has a uniform mechanism for handling all flaws. We provide experimental results that demonstrate that the power of DUnf does not come from delaying threat repairs per ue, but rather from the fact that this delay has the effect of imposing a partial preference for least-cost flaw selection. Our experiments also show that extending this to a complete preference for least-cost selection reduces search-space size even further. We consider the computational overhead of employing LCFR, and discuss techniques for reducing this overhead. In particular, we describe QLCFR, a strategy that reduces computational overhead by approximating repair c0sts. l

PDF Details

AIJ Journal 1989 Journal Article

A theoretical analysis of conjunctive-goal problems

David Joslin
John Roach

Region analysis is a new technique for analyzing search problems by applying graph theory to problem state spaces. The analysis here is of search problems, not search algorithms; analyzing problems and classes of problems lets us understand the underlying structure and inherent complexity of those problems. The analysis technique is demonstrated in the domain of robot planning problems. Region analysis of conjunctive-goal planning problems gives us a characterization of subgoal interactions that is independent of the problem representation. We give a formal characterization of nonlinear planning problems, and show that nonlinearity is a weak characterization of the difficulty in planning problems.

Details DOI