For some computational problems (e.g., product configuration, planning, diagnosis, query answering, phylogeny reconstruction) computing a set of similar diverse solutions may be desirable for better decision-making. With this motivation, we studied several decision optimization versions of this problem in the context of Answer Set Programming (ASP), analyzed their computational complexity, and introduced offline online methods to compute similar diverse solutions of such computational problems with respect to a given distance function. All these methods rely on the idea of computing solutions to a problem by means of finding the answer sets for an ASP program that describes the problem. The offline methods compute all solutions in advance using the ASP formulation of the problem with an ASP solver, like Clasp, and then identify similar diverse solutions using clustering methods. The online methods compute similar diverse solutions following one of the three approaches: by reformulating the ASP representation of the problem to compute similar diverse solutions at once using an ASP solver; by computing similar diverse solutions iteratively (one after other) using an ASP solver; by modifying the search algorithm of an ASP solver to compute similar diverse solutions incrementally. We modified Clasp to implement the last online method and called it Clasp-NK. In the first two online methods, the given distance function is represented in ASP; in the last one it is implemented in C++. We showed the applicability and the effectiveness of these methods on reconstruction of similar diverse phylogenies for Indo-European languages, and on several planning problems in Blocks World. We observed that in terms of computational efficiency the last online method outperforms the others; also it allows us to compute similar diverse solutions when the distance function cannot be represented in ASP.
@cite_36: The idea of synthesizing bounded length plans by compiling planning problems into a combinatorial substrate, and solving the resulting encodings has become quite popular in recent years. Most work to-date has however concentrated on compilation to satisfiability (SAT) theories and integer linear programming (ILP). In this paper we will show that CSP is a better substrate for the compilation approach, compared to both SAT and ILP. We describe GP-CSP, a system that does planning by automatically converting Graphplan's planning graph into a CSP encoding and solving it using standard CSP solvers. Our comprehensive empirical evaluation of GP-CSP demonstrates that it is superior to both the Blackbox system, which compiles planning graphs into SAT encodings, and an ILP-based planner in a wide range of planning domains. Our results show that CSP encodings outperform SAT encodings in terms of both space and time requirements in various problems. The space reduction is particularly important as it makes GP-CSP less susceptible to the memory blow-up associated with SAT compilation methods. The paper also discusses various techniques in setting up the CSP encodings, planning specific improvements to CSP solvers, and strategies for variable and value selection heuristics for solving the CSP encodings of different types of planning problems. Copyright 2001. Elsevier Science B.V.
@cite_3: We present some techniques for planning in domains specified with the recent standard language PDDL2.1, supporting "durative actions" and numerical quantities. These techiques are implemented in LPG, a domain-independent planner that took part in the 3rd International Planning Competition (IPC). LPG is an incremental, any time system producing multi-criteria quality plans. The core of the system is based on a stochastic local search method and on a graph-based representation called "Temporal Action Graphs" (TA-graphs). This paper focuses on temporal planning, introducing TA-graphs and proposing some techniques to guide the search in LPG using this representation. The experimental results of the 3rd IPC, as well as further results presented in this paper, show that our techniques can be very effective. Often LPG outperforms all other fully-automated planners of the 3rd IPC in terms of speed to derive a solution, or quality of the solutions that can be produced.
The authors study these problems considering domain-independent distance measures computable in polynomial time (such as Hamming distance or set difference). They present a method (similar to our Online Method 1), where they add global constraints to the underlying constraint satisfaction solver of the GP-CSP planner @cite_36 . As another method they present a greedy approach (similar to our Online Method 2), where they add global constraints which forces solver to compute @math -diverse solutions in each iteration until it computes @math solutions. They also present a method (similar to our Online Method 3) which modifies an existing planner's @cite_3 heuristic function and computes @math @math -similar solutions in the search level.