A data structure and search algorithm for efficiently finding the shortest plan of actions between an initial state and goal state. GraphPlan is a STRIPS style planner that uses a graph of actions (planning graph) that have pre-conditions and effects which alter state. The search algorithm trims the search space by pre-calculating mutually exclusive actions which makes finding a solution much faster.
See also:
- ‘Fast Planning Through Planning Graph Analysis’ by Avrim L. Blum and Merrick L. Furst, the paper that introduced GraphPlan.
- An implementation of GraphPlan written in rust (written by me) that’s pretty darn fast.
Links to this note
-
Graphrag Combines Knowledge Graphs With Retrieval
One of the biggest criticisms of LLMs is that they don’t actually know anything. Many techniques have been explored to use general purpose artificial intelligence to solve domain specific problems using information that it was not trained on. Retrieval-augmented generation (RAG) does a decent job of enabling you to “bring your own data” but can still fail on more specialized use cases.
-
A sub field of artificial intelligence (AI) concerned with helping agents generate valid and coherent plans of actions to reach a goal.
-
An algorithm used for constraining elements in a UI such as adjusting layout based on the screen size. It is designed to handle linear equality and inequality efficiently (e.g. show window to the left of the other and gracefully degrading if there isn’t space).