Automated Planning in a Nutshell

What is planning?

“Planning is a discipline of Artificial Intelligence that aims at the development of generic algorithms allowing autonomous systems to choose and organize their actions to achieve a goal by anticipating their effects (Ghallab, M. and al., 2004)”

Automated Planning

A classical example: robot dockers

Imagine a system where robots have to transport containers and store them. In this system, every event and action could be predefined and hard-coded but this approach has many shortcomings: complexity, combinatory explosion of the possible scenarios, vulnerability to failures and unexpected events etc.

Another approach is to bet on autonomy technologies such as AI planning and let the robots make their own decisions according to their perceptions and the state of the world.

In the situation above, the goal is to stack container c2 on container c1 at location p2. Automated planning allows to compute a sequence of actions (plan) that will allow the autonomous robots r1, crane1, crane2 to achieve this task from the initial state (c1 is on c2 at p1).

A classical example: robot dockers


What is important to understand here is that if the initial state were different (due to an unexpected event or failure), the system would be able to compute another plan to fulfill the task.

The planning model

conceptual model of automated planning
The conceptual model of planning is made of three components:
  • A state transition system that models the evolution of the environment,

  • A controller that chooses the next action to execute and controls its execution,

  • A planner that, from the specification of a problem in PDDL, synthesizes a plan, i.e., a set of ordered actions, to achieve a goal.

Model Assumptions

Often, planning models do many simplifying assumptions about the real world:
  • The environment is finished

  • The environment is completely observable

  • The environment is deterministics

  • The solution plans are sequential

  • The notion of time is implicit, e.g., actions have no duration

  • Planning does not interleave action execution

  • Planning is a centralized procedure etc.

Simplifying assumptions allow to avoid the combinatorial explosion of the search procedure.

A set of techniques

Classical representations of planning problems are based on logical representations, e.g., PDDL, OPL, etc. or state variables which are often more compact.

Planning algorithms can be classified in different approaches:
  • State space planning

  • Plan space planning

  • SAT and CSP techniques

  • Hierarchical planning techniques (HTN)

  • Planning Graph techniques

  • Markov Decision Process techniques

  • Model Checking techniques

  • etc.