automated planning
In plain wordsThe branch of AI that works out a sequence of actions to reach a goal, such as the steps a robot must take to assemble a part, from descriptions of what each action needs and what it changes.
The subfield of AI concerned with computing plans — sequences, partial orders or policies of actions — that transform an initial state into one satisfying a goal, given a model of the available actions. In classical planning, states are sets of logical facts and each action has preconditions and effects, written in formalisms such as STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true. or PDDLPlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them.; deciding whether a plan exists is PSPACE-complete. Domain-independent planners search forward with automatically derived heuristicsheuristic, n.: A rule of thumb: a quick, usually good-enough way to make a decision or to estimate how close you are to a goal, without any guarantee of finding the best answer. (as in the FF and Fast Downward planners), compile planning into SATBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., build planning graphs or refine partial-order plans, while hierarchical task networkhierarchical task network, n.: A planning method that breaks a big task, such as 'travel to Paris', into smaller tasks, such as 'book a flight' and 'pack', using stored recipes, until only simple actions remain. planners decompose tasks using expert recipes. Extensions handle time, resources, numbers, uncertainty (via Markov decision processesMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice.) and multiple agents. Planning runs spacecraft operations, logistics and robots; language-modellarge language model, n.: A computer program trained on enormous amounts of text to predict the words that come next. At vast scale, that simple skill lets it chat, answer questions, translate, summarize and write code. agents often pair an LLM with a symbolic planner or plan validator because LLMs alone produce unreliable long plans.
We gave the planner the PDDL domain and it returned a 37-step plan that the validator accepted.
Origin
Grew from Newell, Shaw and Simon's General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap. (1959), John McCarthy's situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions. (1963) and STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true. (1971). Partial-order planning (Earl Sacerdoti's NOAH, 1975), SAT-based planning (Henry Kautz and Bart Selman, 1992) and Graphplan (Avrim Blum and Merrick Furst, 1995) followed; the International Planning Competition began in 1998 and the ICAPS conference in 2003.
Usage note
Distinct from motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do. and path planningpath planning, n.: Finding a route for a robot or vehicle from a start to a goal that avoids obstacles, usually the shortest or safest one, much as a navigation app finds a route on a map. in robotics, which compute geometric trajectories, though task-and-motion planning combines them. In agent engineering, 'planning' often means a language model drafting steps in prose (plan-and-executeplan-and-execute, n.: An agent design that first writes out a complete step-by-step plan for a task, then carries out the steps one by one, revising the plan only when something goes wrong.), without the correctness guarantees of a formal planner.
Related
- STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true.
- Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them.
- hierarchical task networkhierarchical task network, n.: A planning method that breaks a big task, such as 'travel to Paris', into smaller tasks, such as 'book a flight' and 'pack', using stored recipes, until only simple actions remain.
- state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal.
- situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions.
- Markov decision processMarkov decision process, n.: A mathematical description of a step-by-step decision problem: each step you pick an action, receive a reward and then land in a new situation, drawn at random from odds that depend only on the current situation and your choice.
- plan-and-executeplan-and-execute, n.: An agent design that first writes out a complete step-by-step plan for a task, then carries out the steps one by one, revising the plan only when something goes wrong.
- motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do.
Sources
- Ghallab, M., Nau, D. & Traverso, P. (2004). Automated Planning: Theory and Practice. Morgan Kaufmann.
- Bylander, T. (1994). The Computational Complexity of Propositional STRIPS Planning. Artificial Intelligence 69(1–2), 165–204.
Mentioned in
artificial intelligenceartificial intelligence, n.: Computer systems that do things we would normally credit to a thinking mind, such as holding a conversation, reading an X-ray or planning a route, and the field of research that builds them., symbolic AIsymbolic AI, n.: An approach to AI that writes knowledge down as human-readable symbols and rules, such as 'every bird has wings', and reasons by manipulating them step by step instead of learning patterns from data., Boolean satisfiability problemBoolean satisfiability problem, n.: The puzzle of deciding whether a set of true-or-false conditions can all be met at once. It is famously hard in theory, yet modern solvers routinely handle millions of conditions., constraint satisfaction problemconstraint satisfaction problem, n.: A problem in which each item must be given a value so that every rule is obeyed, like filling in a Sudoku, coloring a map so no neighbors match, or building a timetable without clashes., General Problem SolverGeneral Problem Solver, prop. n.: A 1950s program meant to solve any well-defined puzzle by repeatedly comparing where it was with where it wanted to be and choosing steps that closed the gap., good old-fashioned AIgood old-fashioned AI, n.: A nickname for the classic style of AI, dominant from the 1950s to the 1980s, that tried to make computers intelligent by writing knowledge and rules down by hand., motion planningmotion planning, n.: Working out how a robot should move from where it is to where it needs to be, without hitting anything and within the limits of what its body can do., NP-completeNP-complete, adj.: Describes problems, such as solving giant Sudokus, where a proposed answer is quick to check but no known method finds one quickly; a fast method for any one of them could be turned into one for all., plan-and-executeplan-and-execute, n.: An agent design that first writes out a complete step-by-step plan for a task, then carries out the steps one by one, revising the plan only when something goes wrong., state space searchstate space search, n.: Solving a problem by treating every situation it could be in as a point on a map, with each possible move as a road between points, and searching for a route from the start to a goal., task decompositiontask decomposition, n.: Breaking a big, vague job into smaller, concrete steps that can each be done and checked — the way a recipe splits a meal into stages., belief–desire–intention modelbelief–desire–intention model, n.: A way of designing software agents around three human-like ideas: what the agent believes about the world, what it wants, and which plans it has committed to carrying out., blocks worldblocks world, n.: A simplified pretend world of toy blocks on a table that early AI researchers used to test programs for planning, seeing and understanding language, because it was simple enough to describe completely., hierarchical task networkhierarchical task network, n.: A planning method that breaks a big task, such as 'travel to Paris', into smaller tasks, such as 'book a flight' and 'pack', using stored recipes, until only simple actions remain., means–ends analysismeans–ends analysis, n.: A problem-solving method that compares where you are with where you want to be, picks an action that shrinks the biggest difference, and sets itself smaller goals when that action cannot yet be taken., Nils NilssonNils Nilsson, prop. n.: An American computer scientist who co-created the A* search algorithm and the STRIPS planner for Shakey, the first robot to plan its own moves by reasoning, and wrote standard AI textbooks., Planning Domain Definition LanguagePlanning Domain Definition Language, prop. n.: A standard computer language for describing planning problems — the available actions, the starting situation and the goal — so that any automated planner can read and solve them., Shakey the robotShakey the robot, prop. n.: A wheeled robot built at a California research institute between 1966 and 1972 that could look around, make a plan and carry it out: the first mobile robot to work out its own steps toward a goal., SHRDLUSHRDLU, prop. n.: A program from around 1970 that let people move toy blocks in a simulated world by typing ordinary English commands and questions, and that could explain what it had done and why., situation calculussituation calculus, n.: A logical language for describing how the world changes as actions happen, so that a program can work out what will be true after any sequence of actions., STRIPSSTRIPS, prop. n.: An early AI planning program, and the simple action language it introduced, in which each action lists what must be true beforehand, what becomes true and what stops being true., temporal logictemporal logic, n.: A logic for statements about time — 'eventually the light turns green', 'the door is never open while the train moves' — used to specify and check how systems must behave over time.