GraphPlan

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

• Planning AI

  A sub field of artificial intelligence (AI) concerned with helping agents generate valid and coherent plans of actions to reach a goal.

• Cassowary Constraint Solver

  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).