AI Planning is a branch of Artificial Intelligence focused on generating strategies to accomplish specific objectives. It uses autonomous methods to transition from an initial state to a target state through a series of actions. In vehicle routing, for example, each decision about the route (choosing streets, sequencing stops) is an action contingent on factors like traffic and distance.

This article covers the basics of AI Planning and how it applies to problems across different domains.

Planning for Different Domains

AI Planning can formulate strategies for specific goals in many domains. The process moves autonomously from an initial state to a goal state through a series of actions, guided by logical rules. In logistics, for instance, it can optimize vehicle routing by determining the most efficient paths given traffic and distance. The same approach applies in healthcare (managing treatment plans) or manufacturing (optimizing production sequences). Because the formalism is domain-agnostic, a planner that works for one domain can often be reused in another with only the problem definition changed.

The Role of PDDL in AI Planning

The standard way to express planning problems is the Planning Domain Definition Language (PDDL). PDDL provides a structured format for defining the components of a planning problem: actions, states, and objectives. Any planner that reads PDDL can, in principle, solve problems from any domain.

In practice, planners have evolved alongside the language, so support varies. Older planners may not handle PDDL 3 features, while newer ones may drop support for certain PDDL 2.1 syntax variants. This means you need to pick a planner that matches your problem definition.

AI Planning in Action

To see AI Planning in practice, we will use LAMA, a planner built for real-world problems. LAMA uses heuristic forward search with landmark-based strategies, multiple heuristics, and a progressively weighted A* algorithm. The full description is in its paper.

Installing LAMA

To install LAMA, we can use planutils, a toolkit designed for Linux environments to develop, execute, and assess planners. Refer to their GitHub README for complete installation guidelines.

Defining the Domain

Consider a robot navigating a two-dimensional grid. Some cells are marked with “X” as obstacles. The goal is to move the robot from a start cell to a destination. In this scenario, the robot needs to go from box 1 to box 5, but box 3 is blocked, so it must take the path 1, 2, 4, 5.

Simple Robot Domain

To define this domain in PDDL, we need to specify the following:

  • Objects: The objects are the entities in the domain.
  • Predicates: The predicates that define the state of the domain.
  • Actions: The actions that can be performed in the domain.
  • Initial State: The initial state of the domain.
  • Goal State: The goal state of the domain.

Here is the PDDL domain for this scenario:

(define (domain robot)
  (:requirements :strips :typing)
  (:types robot location)

  (:predicates
    (at ?r - robot ?l - location)
    (blocked ?l - location)
    (adjacent ?l1 ?l2 - location)
  )

  (:action move-up
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1))))

  (:action move-down
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1))))

  (:action move-left
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1))))

  (:action move-right
    :parameters (?r - robot ?l1 - location ?l2 - location)
    :precondition (and (at ?r ?l1) (adjacent ?l1 ?l2))
    :effect (and (at ?r ?l2) (not (at ?r ?l1)))))

Defining the Problem

We also need a problem file. This file lists the specific objects and describes the initial and goal states. Here is the problem file for this scenario:

(define (problem robot)
  (:domain robot)
  (:objects
    robot1 - robot
    box1 box2 box3 box4 box5 - location
  )
  (:init
    (at robot1 box1)
    (blocked box3)

    (adjacent box1 box2)
    (adjacent box1 box3)
    (adjacent box2 box4)
    (adjacent box3 box4)
    (adjacent box4 box5)
  )

  (:goal (at robot1 box5))
)

This PDDL problem file, named robot, defines a specific scenario for a robot navigating a grid:

  • Domain: The domain that the problem is defined in. In this case, the domain is robot.
  • Objects: There are two types of objects:
    • robot1, representing the robot.
    • box1, box2, box3, box4, box5, representing locations on the grid.
  • Initial State: The robot (robot1) starts at box1. box3 is marked as a blocked location. Adjacency relationships between boxes are defined, specifying which boxes are directly accessible from each other.
  • Goal State: The objective is to move robot1 to box5.

Running LAMA

With both files ready, run LAMA from the command line (make sure it is installed and on your PATH):

lama domain.pddl problem.pddl

LAMA outputs the solution as a sequence of actions. If no valid plan exists, it reports that no solution was found.

(move-down robot1 box1 box2)
(move-down robot1 box2 box4)
(move-down robot1 box4 box5)
; cost = 3 (unit cost)

This example has one robot and one goal, but the domain definition can be extended to multiple robots with separate objectives.

Final Thoughts

This article covered a simple robot domain, but the same approach scales to much harder problems. The International Planning Competition publishes benchmark problems specifically designed to push planners to their limits.

Some solvers also support numeric planning, where variables can represent quantities like delivery cost. This is useful in logistics and scheduling, where the objective is not just reaching a goal state but doing so at minimum cost.

Resources