This is a recent paper I thought was really intriguing using Answer Set Programming for a synthesis problem with some very promising sounding results compared to an SMT based approach.
http://www.weaselhat.com/2022/11/07/asp/
Potassco: The Answer Set Solving Collection
11–18 of 18 posts
Re: Potassco: The Answer Set Solving Collection
#12Still trying to understand exactly what this is. It seems like its like a declarative DSL for interacting with an SMT solver? Is this supposed to be for different use cases than an SMT solver? Does it solve different classes of problems, or is it just a different "interface" to the same basic capabilities?
Re: Potassco: The Answer Set Solving Collection
#13Still trying to understand exactly what this is. It seems like its like a declarative DSL for interacting with an SMT solver? Is this supposed to be for different use cases than an SMT solver? Does it solve different classes of problems, or is it just a different "interface" to the same basic capabilities?
It's its own brand of constraint solving, distinct from SAT/CP/SMT/MIP. Like the others it is particularly good at certain classes of problems, despite theoretically them all being "equivalent" and most of them just using a SAT solver underneath.
ASP is best viewed as Datalog++, in that it's a fully declarative logic programming language with some restrictions to allow for efficient solving. It is more expressive than datalog but in turn the solving tech required is a lot more computationally expensive.
Re: Potassco: The Answer Set Solving Collection
#14I don't see it. All the examples in this thread are trivial. I looked up the paper. All it does is answer trivial logic puzzles.
penguin(pingu).
bird(X):-penguin(X).
that kind of thing. I downloaded the examples.zip from the website. It is a long list of undocumented examples. I sampled a few, but they are all of this nature. So I guess my question is:
Why is this impressive?
Re: Potassco: The Answer Set Solving Collection
#15Earlier quoted context omitted.
Thanks, that's a nice example. >> For an example. The potential hypothesis here are pre generated, but you can imagine an algorithm or adapt an existing one with a tight generalise/specialise loop. Yes! I'm thinking of how to adapt Louise ( https://github.com/stassa/louise ) to do that. The fact that s(CASP) is basically a Prolog-y version of ASP (with constraints) could make it a very natural sort of modification. O…
And adapting Louise would be an interesting thing to work on for sure. Why is it called Louise?
There was an earlier system called Thelma (https://github.com/stassa/thelma), an acronym for "Theory Learning Machine". Then I created a new system and, well, I couldn't resist a bad pun. They're a bit of a tradition in ILP.
Re: Potassco: The Answer Set Solving Collection
#16>> Answer Set Programming (ASP) offers a simple and powerful modeling language to solve combinatorial problems. I wonder if this isn't the completely wrong way to explain what ASP is for. I'm saying this because until recently I used to think of ASP just like that, a logic programming language that's good for optimisation problems and that is "more declarative" because it implements classical negation (a.k.a. default…
ASP has both classical negation and negation-as-failure, but that is not quite why I'd say it is "more declarative". Prolog is capable of performing "imperative" tasks (by this I really mean side effects), while ASP solvers exclusively find stable models (answer sets) that may (or may not) exist for a given logic program. In ASP you can only declare a model with your input, and the output is either one or more stable…
>> ASP has both classical negation and negation-as-failure, but that is not quite why I'd say it is "more declarative". Prolog is capable of performing "imperative" tasks (by this I really mean side effects), while ASP solvers exclusively find stable models (answer sets) that may (or may not) exist for a given logic program. In ASP you can only declare a model with your input, and the output is either one or more stable model(s), or the knowledge that the model was unsatisfiable.
Thanks for the insight. I must confess I still don't have a lot of experience with ASP, mainly because of my initial misunderstanding of it.
To clarify, I'm not interested in the declarative aspect of logic programming so Prolog's side-effect-ness doesn't bother me. I prefer it in fact that Prolog is pragmatic that way and allows itself to be used to do practical work, that would otherwise have to be delegated to another language or tool. Prolog is a big, dirty ball of cheating but I've kind of made my home in it and I'm comfortable there.
But my research interest is in machine learning of logic programs (Inductive Logic Programming, ILP). A big part of that is dealing with noise and uncertainty, which traditional approaches to ILP aren't very good at. In recent years there has been a flurry of work in learning either ASP, or with ASP, and I guess I feel a bit like an idiot to finally realise why. My hope now is that I can find a way to reuse the ideas in ASP with the learning framework I studied in my PhD, where first-order programs are learned by a form of higher-order SLD-Resolution. I think the combination of a sound and refutation-complete inductive algorithm with an elegant treatment of uncertainty could produce something really unique.
Re: Potassco: The Answer Set Solving Collection
#17I don't see it. All the examples in this thread are trivial. I looked up the paper. All it does is answer trivial logic puzzles. penguin(pingu). bird(X):-penguin(X). that kind of thing. I downloaded the examples.zip from the website. It is a long list of undocumented examples. I sampled a few, but they are all of this nature. So I guess my question is: Why is this impressive?
It scales to much bigger problems, that's the impressive part. You can solve a small SAT problem with simple backtracking search, but try to solve a problem with millions of variables and tens of millions of constraints and suddenly your backtracking search is laughably slow.
This is like that but at a higher level of expressivity. Having both classical negation and negation as failure allows for easy modelling of uncertainty for example.
We don't know if P=NP but with how efficient these tools are in practice, maybe it doesn't matter that much x)
Re: Potassco: The Answer Set Solving Collection
#18Potassco is a wonderful collection of software. I have used clingo recently to prototype some puzzle ideas that I had. After encoding the rules in ASP I could quickly produce a single model through clingo to see if the puzzle design was feasible or not. (I also decided to use clingo to enumerate the solution space, but it turned out to be much bigger than I anticipated and after ten days I terminated the process with…
I used generic programming to automatically generate puzzles for a puzzle game. It worked really well. I still needed to play each generated puzzle to see if it was interesting/fun. But most of them were great. I can imagine that ASP would be really good for that kind of thing.