Automated planning: how AI systems choose actions toward a goal
Automated planning is a branch of AI that creates action plans to reach a goal, based on formal descriptions of the environment and actions. It uses languages like PDDL and search algorithms such as A* to find valid plans. The field has a history stretching from the Shakey robot to modern international competitions.
What is automated planning?
Automated planning is a core area of artificial intelligence that focuses on determining a sequence of actions that transforms an initial state into a goal state. The textbook Artificial Intelligence: A Modern Approach covers automated planning as part of its problem-solving chapters, indicating its foundational role in AI.
The concept gained prominence with early robotics research. SRI International describes Shakey as the first mobile robot with the ability to perceive and reason about its surroundings, and it could perform tasks that required planning and route-finding, setting a precedent for planning systems (SRI's Shakey page).
Planning differs from simple search because it explicitly models actions with preconditions and effects, enabling reasoning about complex, extended goals.
Representing planning problems: PDDL and STRIPS
To communicate planning problems to software, researchers use formal languages. The Planning Domain Definition Language (PDDL) is described on the AI planning wiki as a general-purpose language capable of specifying any planning or scheduling problem. Since its introduction, PDDL has been extended to handle temporal and other advanced features.
An earlier representation is the STRIPS system, which represented actions as preconditions and effects. Nils Nilsson, a pioneer in AI, is credited with co-inventing STRIPS and the A* algorithm, as noted on his Stanford University home page. STRIPS formed the basis for many later planning formalisms.
Search and reasoning in planning
Planners often employ heuristic search to find action sequences. The Computer History Museum explains that Shakey used search techniques to plan way points, and the researchers developed the A* algorithm, which finds optimal paths by combining cost estimates and heuristic information.
The Stanford Encyclopedia of Philosophy's entry on Logic-Based Artificial Intelligence discusses how logic is used in planning, including reasoning about action and change, and addresses challenges like the frame problem. This highlights the deep connection between planning and logical inference.
Community and competitions
The International Conference on Autonomous Planning and Scheduling (ICAPS) organizes the International Planning Competition (IPC), which has driven the development of planning systems and the PDDL language. The ICAPS competitions page lists a wide range of competition tracks over the years, including classical, temporal, probabilistic, numeric, and hierarchical task network (HTN) planning.
These competitions provide benchmarks that help researchers compare planners and improve the state of the art. They also foster a community that shares tools and knowledge, contributing to the advancement of automated planning.
| Component | Function |
|---|---|
| Cameras | Visual input for perceiving the environment |
| Touch sensors | Detect contact with objects |
| Two-way radio link | Communication with the control computer |
| Large remote computer | Processing and issuing motion commands |
Frequently asked questions
What is automated planning?
Automated planning is the AI subfield that generates a sequence of actions to transform an initial state into a goal state, given a model of the world and available actions.
What is PDDL?
PDDL is a standard language for describing planning domains and problems, allowing planners to operate on uniform input.
How did the Shakey robot contribute to planning?
Shakey demonstrated the feasibility of integrated perception, planning, and action in a mobile robot, leading to the development of early algorithms like A* and STRIPS.
What role do competitions play in planning research?
Competitions like the IPC provide standardized benchmarks that expose planners to diverse challenges and drive innovation in the field.