I learned just enough Picat to do the book Constraint Solving and Planning with Picat. That was in 2022. Then I started translating the exercises to Scryer Prolog (lots of them were very similar). It was so much fun that I got the opportunity to do a talk at my job about that! I have a recording if someone is interested but it’s in Spanish: https://www.youtube.com/watch?v=c_yP_kr7DxI
Is there a name for the algorithm that the planner module is doing? This solves an exact problem that I have (finding a path to a target state given an initial state and set of actions), and I’ve been looking for a solution to it.
In gamedev, some AI are implemented using “GOAP” (Goal Oriented Action Planning), where you have a bunch of “actions” which have a “cost” and an “outcome”. You then use path finding (A*, Djikstra, whatever) to find a sequence of actions that goes from an initial state to your “goal” (which maximize some outcome while minimizing the global cost of the action sequence).
When I read about the planner module, I could not not think of that, but maybe I’m wrong.
This is classic search-based AI. “AI: A modern approach” by Russell and Norvig is a commonly used textbook that covers these techniques (in sections II and III). Keywords are “automated planning”, “backtracking”, “search”.
From the picat manual, the planner module sounds like it does an A*-style search of the state space (breadth-first with costs and a heuristic), but it could also be using a generic constraint solver with support for heuristics.
I’ve always felt that Prolog (and many other paradigmatic languages) was severely hampered by not providing an easy way to temporarily switch to imperative programming when more grunt-level tasks needed to get done. Its commitment to its one model kept it in the realm of academia/pedagogy. (Some versions of Prolog addressed this, of course, but at the cost of portability.)
I would absolutely love to see the Picat source code for such a problem. I often find myself wanting to plan out my day or vacations similarly (with various constraints). I’m always curious to see how complex problems are solved by these newer languages – people tend to only post their <10 line solutions.
Here ya go. Top one is my initial attempt, bottom is my improved attempt. Next version will prob assign a cost to each activity instead of having a binary allday predicate
That “imperative escape hatch” is intriguing. I wonder if it’s actually syntactic sugar for a relation, between the old and new state. You could do some magic like update an array “imperatively”, then set its final state, and derive the initial state!
query:
Z = Zinit,
foreach (I in 1..Z.len)
Z[I] := Z[I] * 2
end,
{2, 4} ++ {6, 8} = Z.
expected result:
Zinit = {1,2,3,4}.
This would be kind of like DCGs in Prolog, which are supposed to be for parsing, but can be used to thread any old+new state through a bunch of clauses.
I learned just enough Picat to do the book Constraint Solving and Planning with Picat. That was in 2022. Then I started translating the exercises to Scryer Prolog (lots of them were very similar). It was so much fun that I got the opportunity to do a talk at my job about that! I have a recording if someone is interested but it’s in Spanish: https://www.youtube.com/watch?v=c_yP_kr7DxI
Is there a name for the algorithm that the
plannermodule is doing? This solves an exact problem that I have (finding a path to a target state given an initial state and set of actions), and I’ve been looking for a solution to it.In gamedev, some AI are implemented using “GOAP” (Goal Oriented Action Planning), where you have a bunch of “actions” which have a “cost” and an “outcome”. You then use path finding (A*, Djikstra, whatever) to find a sequence of actions that goes from an initial state to your “goal” (which maximize some outcome while minimizing the global cost of the action sequence).
When I read about the
plannermodule, I could not not think of that, but maybe I’m wrong.This is classic search-based AI. “AI: A modern approach” by Russell and Norvig is a commonly used textbook that covers these techniques (in sections II and III). Keywords are “automated planning”, “backtracking”, “search”.
From the picat manual, the planner module sounds like it does an A*-style search of the state space (breadth-first with costs and a heuristic), but it could also be using a generic constraint solver with support for heuristics.
I got curious too and looked, I think they’re just called “planner” languages
The description that made it click for me was: https://artint.info/3e/html/ArtInt3e.Ch3.html. In particular: https://artint.info/3e/html/ArtInt3e.Ch3.S4.html. This a very elegant description of a generic search algorithm that can be customised to get different flavours, e.g., DFS, BFS, A*.
I’ve always felt that Prolog (and many other paradigmatic languages) was severely hampered by not providing an easy way to temporarily switch to imperative programming when more grunt-level tasks needed to get done. Its commitment to its one model kept it in the realm of academia/pedagogy. (Some versions of Prolog addressed this, of course, but at the cost of portability.)
I would absolutely love to see the Picat source code for such a problem. I often find myself wanting to plan out my day or vacations similarly (with various constraints). I’m always curious to see how complex problems are solved by these newer languages – people tend to only post their <10 line solutions.
Here ya go. Top one is my initial attempt, bottom is my improved attempt. Next version will prob assign a cost to each activity instead of having a binary
alldaypredicateThanks so much! I’m excited to give this a try next time I run into a similar vacation planning problem!
Advent of Code.
That “imperative escape hatch” is intriguing. I wonder if it’s actually syntactic sugar for a relation, between the old and new state. You could do some magic like update an array “imperatively”, then set its final state, and derive the initial state!
query:
expected result:
This would be kind of like DCGs in Prolog, which are supposed to be for parsing, but can be used to thread any old+new state through a bunch of clauses.