Planning is a really cool domain which doesn’t get enough attention. This post a nice intro to it.
It’s a very active area of research and there are different solvers which compete (on performance, solution quality etc). in the International Planning Competition. At the time I was looking into this, the leader was Fast Downward but that may have changed.
http://planning.domains/ is a nice resource, with a web editor where you can write problems in PDDL and run them on a variety of solvers.
My understanding of planning is that it’s basically graph search with some smart stuff added on. A lot of work goes in to cheaply pruning the search space and prioritising what’s left. In contrast to other AI fields, the algorithms are logical and understandable, and hence also explainable.
There’s massive untapped potential for applying planning and constraint solving to real world domains - and no GPUs are required!
There’s massive untapped potential for applying planning and constraint solving to real world domains - and no GPUs are required!
Not required maybe, but if you can represent your graph as an adjacency matrix you can probably run a bunch of these algorithms quickly on a GPU, which should help scale them up a lot.
I’ve started thinking about it the other way: there was about six years between me first hearing about logic programming and me running into a problem where it was the right tool for the job. Then I realized “ah, if I learn Picat now this’ll be a lot easier” and actually put the time in. The benefit of reading about exotic techniques is being able to recognize their usability later.
IME this is a commonish ~documentation soft spot. At least when a tool or language solves problems or meets needs that aren’t immediately evident from straightforward descriptions of what the thing is or does.
I imagine this says something good about you, or how you learned about logic programming, or both.
Without good breadcrumbs, the audience for any given project is roughly the set of people who encounter the project between encountering the problem and settling on a solution. Thinking through how someone might recognize that they need your project 6 years after they saw it on the red or orange site is probably a good intellectual exercise.
I’ve used similar approaches to Picat in the past for automating fraud detection. Like a lot of the interesting things in computer science, it is out there in the real world “somewhere”.
For me it sounds super useful but then once I express my program I find that it is way to slow. Then I have to spend my time guiding the planner. But at that point I just wonder why I don’t use an imperative language.
My experience has been various prolog implementations. I would be very interested in some sort of declarative approach that somehow could solve very open optimization problems.
When I was an undergrad I observed something like this: sometimes a slightly simpler approach is much, much faster. This is why I also didn’t go any further with logic programming languages.
The only real fit for logic languages is as a DSL for isolated parts of your system I think, or orchestration type stuff. You have to pay the FFI & build/deployment complexity tax but I’m a fan of DSLs.
Any system that relies on a SQL (or graph) database is making use of logic programming. What if we had access to that power in a less restricted form? As I see it, most enterprise software, as well as most SaaS, are thin wrappers around the capabilities of an RDBMS. I’m not saying logic programming languages is a good fit for everything, but if those capabilities were available to more programmers we would start to see their usefulness at a more fine-grained level. Not just “it’s good for search”.
At $DAYJOB we’ll have to implement an algorithm/heuristic to solve instances of the FJSP, and I think this might be a helpful tool, among others. I’ll give it a try after I do the required research.
If we look under the hood of this system, will we find that the language represents an alternative interface for selecting from a canned set of algorithms, and specifying the arguments to them – or is it something deeper than that? Said another way, is this just a DSL for a set of broadly useful algorithms?
Picat is a Prolog system under the hood, with built-in interfaces to state of the art constraint and SAT solvers and a planner. (Forget now if the planner is a separate module, or implemented using the other Picat machinery.) So it’s not a “deep” innovation in the sense of implementing some brand new constraint logic paradigm. It’s in fact based directly on the creator’s previous project, B-Prolog, which is several decades old.
But I wouldn’t say it “just a DSL”. Picat is an attempt to make logic and constraint programming more approachable by adding more language constructs and things like loops, so programmers don’t have to think only in terms of Horn clauses and recursion. To a big extent, it succeeds, although IMO it doesn’t feel fully cohesive.
UPDATE: the planner module in Picat calls directly into B-Prolog-level bytecode.
Definitely. Various types of search and model finding can usually mimic each other relatively easily, but each has different affordances and handle different problem classes with varying success. Planning problems easily lead to combinatorial explosion. Picat’s planner module implements several strategies and optimizations to cope with that. See Tabling for Planning
While originally pioneered for robotics and AI, “planning” is most-often used for video game AIs, where it’s called “Goal Oriented Action Planning” (GOAP).
I’m not sure what you’re trying to imply here, but I think it’s that GOAP is older than “planning”. If that’s your claim, it’s not true; the first International Planning Competition was in 1998.
FEAR is a game that was revolutionary for it’s GOAP AI implementation (barely paralleled since - it’s rare a game has more impressive AI), and friendlysock was just bringing it up for the core gamers: https://www.gamedevs.org/uploads/three-states-plan-ai-of-fear.pdf
Nah, nothing like that–just being smug about another case of neat technology being kept alive/improved/applied in the field of game development. Your writeup is perfectly good. :)
Planning is a really cool domain which doesn’t get enough attention. This post a nice intro to it.
It’s a very active area of research and there are different solvers which compete (on performance, solution quality etc). in the International Planning Competition. At the time I was looking into this, the leader was Fast Downward but that may have changed.
http://planning.domains/ is a nice resource, with a web editor where you can write problems in PDDL and run them on a variety of solvers.
My understanding of planning is that it’s basically graph search with some smart stuff added on. A lot of work goes in to cheaply pruning the search space and prioritising what’s left. In contrast to other AI fields, the algorithms are logical and understandable, and hence also explainable.
There’s massive untapped potential for applying planning and constraint solving to real world domains - and no GPUs are required!
Not required maybe, but if you can represent your graph as an adjacency matrix you can probably run a bunch of these algorithms quickly on a GPU, which should help scale them up a lot.
Whenever I read things like this, I think “This is interesting,” but I can never think of a way to use it for real.
I’ve started thinking about it the other way: there was about six years between me first hearing about logic programming and me running into a problem where it was the right tool for the job. Then I realized “ah, if I learn Picat now this’ll be a lot easier” and actually put the time in. The benefit of reading about exotic techniques is being able to recognize their usability later.
IME this is a commonish ~documentation soft spot. At least when a tool or language solves problems or meets needs that aren’t immediately evident from straightforward descriptions of what the thing is or does.
I imagine this says something good about you, or how you learned about logic programming, or both.
Without good breadcrumbs, the audience for any given project is roughly the set of people who encounter the project between encountering the problem and settling on a solution. Thinking through how someone might recognize that they need your project 6 years after they saw it on the red or orange site is probably a good intellectual exercise.
I’ve used similar approaches to Picat in the past for automating fraud detection. Like a lot of the interesting things in computer science, it is out there in the real world “somewhere”.
For me it sounds super useful but then once I express my program I find that it is way to slow. Then I have to spend my time guiding the planner. But at that point I just wonder why I don’t use an imperative language.
My experience has been various prolog implementations. I would be very interested in some sort of declarative approach that somehow could solve very open optimization problems.
When I was an undergrad I observed something like this: sometimes a slightly simpler approach is much, much faster. This is why I also didn’t go any further with logic programming languages.
The only real fit for logic languages is as a DSL for isolated parts of your system I think, or orchestration type stuff. You have to pay the FFI & build/deployment complexity tax but I’m a fan of DSLs.
Any system that relies on a SQL (or graph) database is making use of logic programming. What if we had access to that power in a less restricted form? As I see it, most enterprise software, as well as most SaaS, are thin wrappers around the capabilities of an RDBMS. I’m not saying logic programming languages is a good fit for everything, but if those capabilities were available to more programmers we would start to see their usefulness at a more fine-grained level. Not just “it’s good for search”.
At $DAYJOB we’ll have to implement an algorithm/heuristic to solve instances of the FJSP, and I think this might be a helpful tool, among others. I’ll give it a try after I do the required research.
If we look under the hood of this system, will we find that the language represents an alternative interface for selecting from a canned set of algorithms, and specifying the arguments to them – or is it something deeper than that? Said another way, is this just a DSL for a set of broadly useful algorithms?
Picat is a Prolog system under the hood, with built-in interfaces to state of the art constraint and SAT solvers and a planner. (Forget now if the planner is a separate module, or implemented using the other Picat machinery.) So it’s not a “deep” innovation in the sense of implementing some brand new constraint logic paradigm. It’s in fact based directly on the creator’s previous project, B-Prolog, which is several decades old.
But I wouldn’t say it “just a DSL”. Picat is an attempt to make logic and constraint programming more approachable by adding more language constructs and things like loops, so programmers don’t have to think only in terms of Horn clauses and recursion. To a big extent, it succeeds, although IMO it doesn’t feel fully cohesive.
UPDATE: the planner module in Picat calls directly into B-Prolog-level bytecode.
There was a language called Planner, introduced in 1969 by Carl Hewitt (who also designed the Actor model), in the paper “PLANNER: A Language for Proving Theorems in Robots”.
It sounds like “planner programming” originated with Planner.
I have only a passing experience with Prolog and SMT but wouldn’t that be possible with these too?
Definitely. Various types of search and model finding can usually mimic each other relatively easily, but each has different affordances and handle different problem classes with varying success. Planning problems easily lead to combinatorial explosion. Picat’s planner module implements several strategies and optimizations to cope with that. See Tabling for Planning
Should
PathbePlanhere? Seems like a typo.😏
(Made famous in FEAR just shy of 19 years ago.)
I’m not sure what you’re trying to imply here, but I think it’s that GOAP is older than “planning”. If that’s your claim, it’s not true; the first International Planning Competition was in 1998.
FEAR is a game that was revolutionary for it’s GOAP AI implementation (barely paralleled since - it’s rare a game has more impressive AI), and friendlysock was just bringing it up for the core gamers: https://www.gamedevs.org/uploads/three-states-plan-ai-of-fear.pdf
Nah, nothing like that–just being smug about another case of neat technology being kept alive/improved/applied in the field of game development. Your writeup is perfectly good. :)
I’m now really curious how you plan your vacation with picat