7. Hierarchical Planning

7.1. Setup

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

%pip install --pre unified-planning
%pip install up-aries

7.2. Demo

In this demo, we show how to model a hierrachical planning problem using the Unified Planning Library.

7.2.1. Specifyng a (flat) planning problem

7.2.1.1. Basic imports

The basic imports we need for this demo are abstracted in the shortcuts and htn packages.

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

7.2.1.2. Logistics problem

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 = HierarchicalProblem()  # the only line that is specific to hierarchical planning in this code block

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)
Package = UserType("Package")

city = pb.add_fluent("city", City, of=Loc)
loc = pb.add_fluent("loc", PackageLoc, package=Package)
at = pb.add_fluent("at", Loc, vehicle=Vehicle)

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 = 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)

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)

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)

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)

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

def solve(pb: HierarchicalProblem):  # helper function that just invokes a planner and prints the plan
    print("Plan:", OneshotPlanner(problem_kind=pb.kind).solve(pb).plan)

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

Plan: None

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.

7.2.2. Tasks and Methods

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

# 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 target location, nothing to do
m = Method("bring-truck-noop", truck=Truck, to=Loc)
m.set_task(bring_truck, m.truck, m.to)  # declares that m achieves the `bring-truck(truck, to)` task`
m.add_precondition(Equals(at(m.truck), m.to))  # 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
pb.add_method(m)
print(m)

# Option 2: truck not at target location, move it
m = Method("bring-truck-move", truck=Truck, orig=Loc, to=Loc)
m.set_task(bring_truck, m.truck, m.to) # declares that m achieves the `bring-truck(truck, to)` task`
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.to)))        # in a different location
m.add_precondition(Equals(city(m.orig), city(m.to))) # of the same city
m.add_subtask(move, m.truck, m.orig, m.to)  # accomplishing this method requires executing a `move` action
pb.add_method(m)
print(m)

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

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

solve(pb)  # no objective tasks, empty plan

Plan: []

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: [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: []

7.2.3. 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: [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: [load(package2, truck1, loc1), move(truck1, loc1, airport1), load(package1, truck1, airport1), unload(package2, truck1, airport1), move(truck1, airport1, loc1), unload(package1, truck1, loc1)]

In the above problem the planner may achieve both tasks 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: [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: [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)]

7.2.4. Going further

Possible exercise: create the task and methods necessary to transport a package between two cities.