Potassco: The Answer Set Solving Collection
potassco.org
potassco.org
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 negation) and not just negation-as-failure as in Prolog (a.k.a. the closed-world assumption).
To be honest, I never though that's particularly interesting. But it turns out that there is a much more interesting motivation for ASP: nomonotonic reasoning, and the ability to represent uncertainty in a purely logical framework, a kind of proof-theoretical framework of reasoning with uncertainty.
This paper is what changed my mind:
Automating commonsense reasoning with ASP and s(CASP)
https://personal.utdallas.edu/~gupta/csr-scasp.pdf
And while I cringe a bit whenever anyone says the words "commonsense reasoning" (because it's typically neither common sense, nor much reasoning; in humans, let alone modelled by machines) the first few sections in the paper are a simple, plain-worded, straight-forward explanation of what ASP is really about that I think will speak to the heart of every logician who has ever looked at Baye's rule, looked at a gigantic, noisy dataset, and couldn't help thinking of the Mogwai and how you should never feed them after midnight lest they turn into Gremlins (like probabilities turn to statistics when you try to instantiate those random variables with actual, you know, numbers).
See https://swish.swi-prolog.org/p/non-monotonic_ilp.swinb
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.
But the scasp finds the two potential rules that cover both positive examples but not the negative example.
i.e.
flies(X,h8):-not penguin(X).
and
flies(X,h17):-bird(X),not penguin(X).
Which is cool.
>> 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. Or, of course, there's always Well-Founded Semantics (https://www.swi-prolog.org/pldoc/man?section=WFS).
What's hyp_gen.pl?
You are right about it being more than just a "modeling language to solve combinatorial problems", I agree that description sells it a bit short. As you pointed out, it is well suited for problems involving non-monotonic reasoning and uncertainty. You can encode reasoning that is more reality-hardened, with logical rules to deal with imperfect information.
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.
Since then I have been dreaming of using it to actually power puzzle software, where a single logic program could be used for both puzzle generation and validation. But that's not even the only "power couple" I can think of with respect to clingo/ASP integration. There are a number of hard problems that benefit from the declarative approach and could leverage the power and speed of a solver like clingo. And with libclingo this is now a feasible option to transform your problem into an ASP program, call clingo, then transform the answer set into your solution.
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?
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)
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.