8. Hierarchical Planning

8.1. Setup

We start by downloading the unified planning library and a hierarchical planner (aries).

%pip install unified-planning[aries]

import unified_planning as up
from unified_planning.shortcuts import *
from unified_planning.model.htn import *

8.2. Case study: Logistics problem (IPC 1998)

For this example, we are interested in logistics problem where the objective is to move packages from one location to another. Packages can be transported by truck between two locations in the same city, or by airplane between two airport locations in two distinct cities.

We start by defining the problem structure: types, fluents, objects and actions. For this we create a new HierarchicalProblem and add all those elements to it. This is done exactly as it would have been done for non-hierarchical Problem (in fact HierarchicalProblem is a subclass of Problem).

#pb = Problem()  # for a non-hierarchical problem
pb = HierarchicalProblem()  # make it hierarchical instead

Package = UserType("Package")

PackageLoc = UserType("PackageLoc")
Loc = UserType("Location", father=PackageLoc)
Airport = UserType("Airport", father=Loc)
City = UserType("City")

Vehicle = UserType("Vehicle", father=PackageLoc)
Truck = UserType("Truck", father=Vehicle)
Airplane = UserType("Airplane", father=Vehicle)

# city of location
city = pb.add_fluent("city", City, of=Loc)

# current location of package / vehicle
loc = pb.add_fluent("loc", PackageLoc, package=Package)
at = pb.add_fluent("at", Loc, vehicle=Vehicle)
print(pb)

types = [City, PackageLoc, Location - PackageLoc, Package, Vehicle - PackageLoc]

fluents = [
  City city[of=Location - PackageLoc]
  PackageLoc loc[package=Package]
  Location - PackageLoc at[vehicle=Vehicle - PackageLoc]
]

actions = [
]

objects = [
  City: []
  PackageLoc: []
  Location - PackageLoc: []
  Package: []
  Vehicle - PackageLoc: []
]

initial fluents default = [
]

initial values = [
]

goals = [
]

abstract tasks = [
]

methods = [
]

task network {
  subtasks = [
  ]
}

# city1 with a location and an airport
city1 = pb.add_object("city1", City)
loc1 = pb.add_object("loc1", Loc)
pb.set_initial_value(city(loc1), city1)
airport1 = pb.add_object("airport1", Airport)
pb.set_initial_value(city(airport1), city1)

# city2 with one location and an airport
city2 = pb.add_object("city2", City)
loc2 = pb.add_object("loc2", Loc)
pb.set_initial_value(city(loc2), city2)
airport2 = pb.add_object("airport2", Airport)
pb.set_initial_value(city(airport2), city2)

truck1 = pb.add_object("truck1", Truck)
pb.set_initial_value(at(truck1), loc1)

package1 = pb.add_object("package1", Package)
pb.set_initial_value(loc(package1), airport1)
package2 = pb.add_object("package2", Package)
pb.set_initial_value(loc(package2), loc1)

load = InstantaneousAction("load", package=Package, vehicle=Vehicle, l=Loc)
load.add_precondition(Equals(at(load.vehicle), load.l))
load.add_precondition(Equals(loc(load.package), load.l))
load.add_effect(loc(load.package), load.vehicle)  # package now in vehicle
pb.add_action(load)
print(load)

unload = InstantaneousAction("unload", package=Package, vehicle=Vehicle, l=Loc)
unload.add_precondition(Equals(at(unload.vehicle), unload.l))
unload.add_precondition(Equals(loc(unload.package), unload.vehicle))
unload.add_effect(loc(unload.package), unload.l)
pb.add_action(unload)
print(unload)

action load(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {
    preconditions = [
      (at(vehicle) == l)
      (loc(package) == l)
    ]
    effects = [
      loc(package) := vehicle
    ]
  }
action unload(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {
    preconditions = [
      (at(vehicle) == l)
      (loc(package) == vehicle)
    ]
    effects = [
      loc(package) := l
    ]
  }

move = InstantaneousAction("move", truck=Truck, src=Loc, tgt=Loc)
move.add_precondition(Equals(city(move.src), city(move.tgt)))
move.add_precondition(Equals(at(move.truck), move.src))
move.add_effect(at(move.truck), move.tgt)
pb.add_action(move)
print(move)

fly_plane = InstantaneousAction("fly-plane", plane=Airplane, src=Airport, tgt=Airport)
fly_plane.add_precondition(Equals(at(fly_plane.plane), fly_plane.src))
fly_plane.add_effect(at(fly_plane.plane), fly_plane.tgt)
pb.add_action(fly_plane)
print(fly_plane)

action move(Truck - Vehicle truck, Location - PackageLoc src, Location - PackageLoc tgt) {
    preconditions = [
      (city(src) == city(tgt))
      (at(truck) == src)
    ]
    effects = [
      at(truck) := tgt
    ]
  }
action fly-plane(Airplane - Vehicle plane, Airport - Location src, Airport - Location tgt) {
    preconditions = [
      (at(plane) == src)
    ]
    effects = [
      at(plane) := tgt
    ]
  }

If we now create and solve a new version of problem with a trivial goal statement:

# helper function that just invokes a planner and prints the plan
def solve(pb: Problem, verbose=False):
    result = OneshotPlanner(problem_kind=pb.kind).solve(pb)
    if result.plan is not None:
        print("Plan:", repr(result.plan) if verbose else str(result.plan))
    else:
        print(result.status)

pb_clone = pb.clone()
pb_clone.add_goal(Equals(at(truck1), airport1))
solve(pb_clone)

PlanGenerationResultStatus.UNSOLVABLE_INCOMPLETELY

The planner tells us that there is no solution to this problem. This might be surprising as a single move(truck1, loc1, airport1) action would have worked to bring the truck to its objective.

This highlights the most important difference between hierarchical and non-hierarchical planning. In hierarchical planning, all actions of the plan must derive from high-level objective tasks.

Until now, we haven’t defined any objective task, so no action are allowed in the plan.

8.2.1. Tasks and Methods

Let us define our first task bring-truck(truck, dest):

# Task representing the objective of getting a given truck to a particular location
bring_truck = pb.add_task("bring-truck", truck=Truck, destination=Loc)

Conceptually, a task captures an objective to be achieved. In our case, its captures the objective of bringing a truck to a given destination, both truck and destination being parameters of the task.

To specify how such a task can be achieved, we should associate the task to a set of Methods: recipes that describe how a high-level task can be achieved though lower-level actions. Hierarchical planning can be seen as a process where a high level task is iteratively decomposed into lower level tasks, each method representation one possibible decomposition.

In our case, bringing a truck to a given location has two possibilities: - if the truck is already at the target location, there is nothing to be done - if the truck is not at the right location but in the same city, it can use the move action to reach its destination

We define one Method for each such recipe:

# Option 1: truck already at destination location, nothing to do
m = Method("bring-truck-noop", truck=Truck, dest=Loc)

# declares that m achieves the `bring-truck(truck, dest)` task`
m.set_task(bring_truck, m.truck, m.dest)

# only usable if the truck is already at the right location
# no subtasks, implying that if the method is usable, there is nothing left to do
m.add_precondition(Equals(at(m.truck), m.dest))

pb.add_method(m)
print(m)

method bring-truck-noop(Truck - Vehicle truck, Location - PackageLoc dest) {
  task = bring-truck(Truck - Vehicle truck, Location - PackageLoc dest)
  preconditions = [
    (at(truck) == dest)
  ]
}

# Option 2: truck not at target location, move it
m = Method("bring-truck-move", truck=Truck, orig=Loc, dest=Loc)
# declares that m achieves the `bring-truck(truck, to)` task`
m.set_task(bring_truck, m.truck, m.dest)

m.add_precondition(Equals(at(m.truck), m.orig))      # restrict applicability to cases where the truck is
m.add_precondition(Not(Equals(m.orig, m.dest)))        # in a different location
m.add_precondition(Equals(city(m.orig), city(m.dest))) # of the same city

# accomplishing this method requires executing a `move` action
m.add_subtask(move, m.truck, m.orig, m.dest, ident="move-subtask")

pb.add_method(m)

print(pb)

types = [City, PackageLoc, Location - PackageLoc, Package, Vehicle - PackageLoc, Airport - Location, Truck - Vehicle, Airplane - Vehicle]

fluents = [
  City city[of=Location - PackageLoc]
  PackageLoc loc[package=Package]
  Location - PackageLoc at[vehicle=Vehicle - PackageLoc]
]

actions = [
  action load(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {
    preconditions = [
      (at(vehicle) == l)
      (loc(package) == l)
    ]
    effects = [
      loc(package) := vehicle
    ]
  }
  action unload(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {
    preconditions = [
      (at(vehicle) == l)
      (loc(package) == vehicle)
    ]
    effects = [
      loc(package) := l
    ]
  }
  action move(Truck - Vehicle truck, Location - PackageLoc src, Location - PackageLoc tgt) {
    preconditions = [
      (city(src) == city(tgt))
      (at(truck) == src)
    ]
    effects = [
      at(truck) := tgt
    ]
  }
  action fly-plane(Airplane - Vehicle plane, Airport - Location src, Airport - Location tgt) {
    preconditions = [
      (at(plane) == src)
    ]
    effects = [
      at(plane) := tgt
    ]
  }
]

objects = [
  City: [city1, city2]
  PackageLoc: [loc1, airport1, loc2, airport2, truck1]
  Location - PackageLoc: [loc1, airport1, loc2, airport2]
  Package: [package1, package2]
  Vehicle - PackageLoc: [truck1]
  Airport - Location: [airport1, airport2]
  Truck - Vehicle: [truck1]
  Airplane - Vehicle: []
]

initial fluents default = [
]

initial values = [
  city(loc1) := city1
  city(airport1) := city1
  city(loc2) := city2
  city(airport2) := city2
  at(truck1) := loc1
  loc(package1) := airport1
  loc(package2) := loc1
]

goals = [
]

abstract tasks = [
  bring-truck[truck=Truck - Vehicle, destination=Location - PackageLoc]
]

methods = [
  method bring-truck-noop(Truck - Vehicle truck, Location - PackageLoc dest) {
    task = bring-truck(Truck - Vehicle truck, Location - PackageLoc dest)
    preconditions = [
      (at(truck) == dest)
    ]
  }
  method bring-truck-move(Truck - Vehicle truck, Location - PackageLoc orig, Location - PackageLoc dest) {
    task = bring-truck(Truck - Vehicle truck, Location - PackageLoc dest)
    preconditions = [
      (at(truck) == orig)
      (not (orig == dest))
      (city(orig) == city(dest))
    ]
    subtasks = [
        move-subtask: move(truck, orig, dest)
    ]
  }
]

task network {
  subtasks = [
  ]
}

Now let’s try to solve this problem. Recall that curently, it has no objectives.

solve(pb)  # no objective tasks, empty plan

Plan: Hiearchical TimeTriggeredPlan:

We get an empty plan which is what we expected as the problem specifies no objectives.

Hierarchical problem have a concept of an initial task network: a partially ordered set of objective tasks that specify what should be achieved to solve the problem.

If we now add an objective task saying truck1 should be brought to airport1:

pb_clone = pb.clone()
pb_clone.task_network.add_subtask(bring_truck(truck1, airport1))

solve(pb_clone)

Plan: Hiearchical SequentialPlan:
    move(truck1, loc1, airport1)

We now get a plan with a single move action. Which the only possible plan for this problem.

Indeed, to fulfill this task, we had two possibilities: - use the bring-truck-noop method that does nothing but requires that the truck is already at the target location. Since this requirement is not fulfilled this method is not applicable for our problem. - use the bring-truck-move method that will transform our bring-truck task into a single move action. This mehtod requires the truck to be in another location of the same city (which is true in our problem).

Of the two methods only the second one was applicable.

If we now try to achieve an objective task with a task that would require the first method, we get an empty plan:

pb_clone = pb.clone()
pb_clone.task_network.add_subtask(bring_truck, truck1, loc1)
solve(pb_clone)

Plan: Hiearchical TimeTriggeredPlan:

8.2.2. Going up the hierarchy

Now that we have our first task bring-truck that allows moving trucks in cities we can leverage it to define a more complex one: transporting packages from one location to another.

# Task for transporting a given package to a given location,
# This method assumes that the package is already in the right city
transport_in_city = pb.add_task("transport-in-city", package=Package, destination=Loc)

# Method 1: handling the case where the package is already at the destination
m = Method("transport-in-city-noop", package=Package, to=Loc)
m.set_task(transport_in_city, m.package, m.to)  # set the task that this method achieve
m.add_precondition(Equals(loc(m.package), m.to))  # only allow using this method if the package is already at the destination
# note: no subtasks are added => nothing to do in this method
pb.add_method(m)

m = Method("transport-in-city-truck", package=Package, orig=Loc, to=Loc, truck=Truck)
m.set_task(transport_in_city, m.package, m.to)
m.add_precondition(Equals(loc(m.package), m.orig)) # package is at origin
m.add_precondition(Not(Equals(m.orig, m.to)))
m.add_precondition(Equals(city(m.orig), city(m.to)))  # destination is the same city

# this method decomposed into a sequence of 4 subtasks (mixing the load/unload action and the 'bring-truck' task)
t1 = m.add_subtask(bring_truck, m.truck, m.orig)  # bring truck to package location
t2 = m.add_subtask(load, m.package, m.truck, m.orig)  # load package in truck
t3 = m.add_subtask(bring_truck, m.truck, m.to)  # bring truck to target location
t4 = m.add_subtask(unload, m.package, m.truck, m.to)  # unload package at target location
m.set_ordered(t1, t2, t3, t4)  # enforce all 4 subtasks to be done in this order
pb.add_method(m)

Finally we set the objective of the problem, here transporting package1 to loc1.

pb_clone = pb.clone()
pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))
solve(pb_clone)

Plan: Hiearchical SequentialPlan:
    move(truck1, loc1, airport1)
    load(package1, truck1, airport1)
    move(truck1, airport1, loc1)
    unload(package1, truck1, loc1)

We can of course define multiple objectives for different packages.

pb_clone = pb.clone()
pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))
pb_clone.task_network.add_subtask(transport_in_city(package2, airport1))
solve(pb_clone)

Plan: Hiearchical SequentialPlan:
    load(package2, truck1, loc1)
    move(truck1, loc1, airport1)
    load(package1, truck1, airport1)
    unload(package2, truck1, airport1)
    move(truck1, airport1, loc1)
    unload(package1, truck1, loc1)

Currently tasks may be achieved in an arbitrary order. Just like we restricted the order of tasks in methods, we can also restrict them in the initial task network.

For instance, we could force package1 to be handled before package2:

pb_clone = pb.clone()
t1 = pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))
t2 = pb_clone.task_network.add_subtask(transport_in_city(package2, airport1))
pb_clone.task_network.set_ordered(t1, t2) # force t1 to be completed before starting t2
solve(pb_clone)

Plan: Hiearchical SequentialPlan:
    move(truck1, loc1, airport1)
    load(package1, truck1, airport1)
    move(truck1, airport1, loc1)
    unload(package1, truck1, loc1)
    load(package2, truck1, loc1)
    move(truck1, loc1, airport1)
    unload(package2, truck1, airport1)

We could also require that package1 be first transported to loc1 and then back to airport1.

pb_clone = pb.clone()
t1 = pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))
t2 = pb_clone.task_network.add_subtask(transport_in_city(package1, airport1))
pb_clone.task_network.set_ordered(t1, t2) # force t1 to be completed before starting t2
solve(pb_clone)

Plan: Hiearchical SequentialPlan:
    move(truck1, loc1, airport1)
    load(package1, truck1, airport1)
    move(truck1, airport1, loc1)
    unload(package1, truck1, loc1)
    load(package1, truck1, loc1)
    move(truck1, loc1, airport1)
    unload(package1, truck1, airport1)

8.2.3. Going further

• create the task and methods necessary to transport a package between two cities.

• Make actions durative

• Add optimality metrics (action costs, makespan, …)