docs/notebooks/07-hierrachical-planning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "6nOTljC_mTMn"
   },
   "source": [
    "# Hierarchical Planning\n",
    "\n",
    "\n",
    "[![Open In GitHub](https://img.shields.io/badge/see-Github-579aca?logo=github)](https:///github.com/aiplan4eu/unified-planning/blob/master/docs/notebooks/07-hierrachical-planning.ipynb)\n",
    "[![Open In Colab](https://colab.research.google.com/assets/colab-badge.svg)](https://colab.research.google.com/github/aiplan4eu/unified-planning/blob/master/docs/notebooks/07-hierrachical-planning.ipynb)\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "t8dCcpf7mivV"
   },
   "source": [
    "## Setup\n",
    "\n",
    "We start by downloading (from github) the unified planning library and a hierarchical planner (aries)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {
    "id": "BoqALxJWdfl8",
    "tags": [
     "remove_from_CI"
    ]
   },
   "outputs": [],
   "source": [
    "%pip install --pre unified-planning\n",
    "%pip install up-aries"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "9dP5scv7nNJu"
   },
   "source": [
    "## Demo\n",
    "\n",
    "In this demo, we show how to model a hierrachical planning problem using the Unified Planning Library.\n",
    "\n",
    "### Specifyng a (flat) planning problem \n",
    "\n",
    "#### Basic imports\n",
    "The basic imports we need for this demo are abstracted in the `shortcuts` and `htn` packages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 55,
   "metadata": {
    "id": "06rETnGAfQHg"
   },
   "outputs": [],
   "source": [
    "import unified_planning\n",
    "from unified_planning.shortcuts import *\n",
    "from unified_planning.model.htn import *\n",
    "import unified_planning as up"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Logistics problem\n",
    "\n",
    "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.\n",
    "\n",
    "\n",
    "We start by defining the problem structure: types, fluents, objects and actions.\n",
    "For this we create a new `HierarchicalProblem` and add all those elements to it.\n",
    "This is done exactly as it would have been done for non-hierarchical `Problem` (in fact `HierarchicalProblem` is a subclass of `Problem`)."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 56,
   "metadata": {
    "id": "huAy2IbVn0GZ"
   },
   "outputs": [],
   "source": [
    "pb = HierarchicalProblem()  # the only line that is specific to hierarchical planning in this code block\n",
    "\n",
    "PackageLoc = UserType(\"PackageLoc\")\n",
    "Loc = UserType(\"Location\", father=PackageLoc)\n",
    "Airport = UserType(\"Airport\", father=Loc)\n",
    "City = UserType(\"City\")\n",
    "Vehicle = UserType(\"Vehicle\", father=PackageLoc)\n",
    "Truck = UserType(\"Truck\", father=Vehicle)\n",
    "Airplane = UserType(\"Airplane\", father=Vehicle)\n",
    "Package = UserType(\"Package\")\n",
    "\n",
    "city = pb.add_fluent(\"city\", City, of=Loc)\n",
    "loc = pb.add_fluent(\"loc\", PackageLoc, package=Package)\n",
    "at = pb.add_fluent(\"at\", Loc, vehicle=Vehicle)\n",
    "\n",
    "city1 = pb.add_object(\"city1\", City)\n",
    "loc1 = pb.add_object(\"loc1\", Loc)\n",
    "pb.set_initial_value(city(loc1), city1)\n",
    "airport1 = pb.add_object(\"airport1\", Airport)\n",
    "pb.set_initial_value(city(airport1), city1)\n",
    "\n",
    "city2 = pb.add_object(\"city2\", City)\n",
    "loc2 = pb.add_object(\"loc2\", Loc)\n",
    "pb.set_initial_value(city(loc2), city2)\n",
    "airport2 = pb.add_object(\"airport2\", Airport)\n",
    "pb.set_initial_value(city(airport2), city2)\n",
    "\n",
    "truck1 = pb.add_object(\"truck1\", Truck)\n",
    "pb.set_initial_value(at(truck1), loc1)\n",
    "\n",
    "package1 = pb.add_object(\"package1\", Package)\n",
    "pb.set_initial_value(loc(package1), airport1)\n",
    "package2 = pb.add_object(\"package2\", Package)\n",
    "pb.set_initial_value(loc(package2), loc1)\n",
    "\n",
    "load = InstantaneousAction(\"load\", package=Package, vehicle=Vehicle, l=Loc)\n",
    "load.add_precondition(Equals(at(load.vehicle), load.l))\n",
    "load.add_precondition(Equals(loc(load.package), load.l))\n",
    "load.add_effect(loc(load.package), load.vehicle)  # package now in vehicle\n",
    "pb.add_action(load)\n",
    "\n",
    "unload = InstantaneousAction(\"unload\", package=Package, vehicle=Vehicle, l=Loc)\n",
    "unload.add_precondition(Equals(at(unload.vehicle), unload.l))\n",
    "unload.add_precondition(Equals(loc(unload.package), unload.vehicle))\n",
    "unload.add_effect(loc(unload.package), unload.l)\n",
    "pb.add_action(unload)\n",
    "\n",
    "move = InstantaneousAction(\"move\", truck=Truck, src=Loc, tgt=Loc)\n",
    "move.add_precondition(Equals(city(move.src), city(move.tgt)))\n",
    "move.add_precondition(Equals(at(move.truck), move.src))\n",
    "move.add_effect(at(move.truck), move.tgt)\n",
    "pb.add_action(move)\n",
    "\n",
    "fly_plane = InstantaneousAction(\"fly-plane\", plane=Airplane, src=Airport, tgt=Airport)\n",
    "fly_plane.add_precondition(Equals(at(fly_plane.plane), fly_plane.src))\n",
    "fly_plane.add_effect(at(fly_plane.plane), fly_plane.tgt)\n",
    "pb.add_action(fly_plane)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "If we now create and solve a new version of problem with a trivial goal statement:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 57,
   "metadata": {
    "id": "LZUgad7ZoA2p"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plan: None\n"
     ]
    }
   ],
   "source": [
    "def solve(pb: HierarchicalProblem):  # helper function that just invokes a planner and prints the plan\n",
    "    print(\"Plan:\", OneshotPlanner(problem_kind=pb.kind).solve(pb).plan)\n",
    "\n",
    "pb_clone = pb.clone()\n",
    "pb_clone.add_goal(Equals(at(truck1), airport1))\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "rVzqSj3XoDPa"
   },
   "source": [
    "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.\n",
    "\n",
    "This highlights the most important difference between hierarchical and non-hierarchical planning.\n",
    "In hierarchical planning, all actions of the plan must derive from high-level *objective tasks*.\n",
    "\n",
    "Until now, we haven't defined any objective task, so no action are allowed in the plan."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Tasks and Methods\n",
    "\n",
    "Let us define our first task `bring-truck(truck, to)`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Task representing the objective of getting a given truck to a particular location\n",
    "bring_truck = pb.add_task(\"bring-truck\", truck=Truck, destination=Loc)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "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.\n",
    "\n",
    "\n",
    "To specify how such a task can be achieved, we should associate the task to a set of `Method`s: 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.\n",
    "\n",
    "In our case, bringing a truck to a given location has two possibilities:\n",
    " - if the truck is already at the target location, there is nothing to be done\n",
    " - if the truck is not at the right location but in the same city, it can use the `move` action to reach its destination\n",
    "\n",
    "We define one `Method` for each such recipe:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 59,
   "metadata": {
    "id": "dRfrnEOfoHD8"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "method bring-truck-noop(Truck - Vehicle truck, Location - PackageLoc to) {\n",
      "  task = bring-truck(Truck - Vehicle truck, Location - PackageLoc to)\n",
      "  preconditions = [\n",
      "    (at(truck) == to)\n",
      "  ]\n",
      "}\n",
      "method bring-truck-move(Truck - Vehicle truck, Location - PackageLoc orig, Location - PackageLoc to) {\n",
      "  task = bring-truck(Truck - Vehicle truck, Location - PackageLoc to)\n",
      "  preconditions = [\n",
      "    (at(truck) == orig)\n",
      "    (not (orig == to))\n",
      "    (city(orig) == city(to))\n",
      "  ]\n",
      "  subtasks = [\n",
      "      _t45: move(truck, orig, to)\n",
      "  ]\n",
      "}\n"
     ]
    }
   ],
   "source": [
    "# Option 1: truck already at target location, nothing to do\n",
    "m = Method(\"bring-truck-noop\", truck=Truck, to=Loc)\n",
    "m.set_task(bring_truck, m.truck, m.to)  # declares that m achieves the `bring-truck(truck, to)` task`\n",
    "m.add_precondition(Equals(at(m.truck), m.to))  # only usable if the truck is already at the right location\n",
    "# no subtasks, implying that if the method is usable, there is nothing left to do\n",
    "pb.add_method(m)\n",
    "print(m)\n",
    "\n",
    "# Option 2: truck not at target location, move it\n",
    "m = Method(\"bring-truck-move\", truck=Truck, orig=Loc, to=Loc)\n",
    "m.set_task(bring_truck, m.truck, m.to) # declares that m achieves the `bring-truck(truck, to)` task`\n",
    "m.add_precondition(Equals(at(m.truck), m.orig))      # restrict applicability to cases where the truck is \n",
    "m.add_precondition(Not(Equals(m.orig, m.to)))        # in a different location \n",
    "m.add_precondition(Equals(city(m.orig), city(m.to))) # of the same city\n",
    "m.add_subtask(move, m.truck, m.orig, m.to)  # accomplishing this method requires executing a `move` action\n",
    "pb.add_method(m)\n",
    "print(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now let's try to solve this problem. Recall that curently, it has no objectives."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plan: []\n"
     ]
    }
   ],
   "source": [
    "solve(pb)  # no objective tasks, empty plan"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "iMuggWWioJ8K"
   },
   "source": [
    "We get an empty plan which is what we expected as the problem specifies no objectives.\n",
    "\n",
    "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.\n",
    "\n",
    "If we now add an objective task saying `truck1` should be brought to `airport1`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 61,
   "metadata": {
    "id": "pgrJOj6ioMSC"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plan: [move(truck1, loc1, airport1)]\n"
     ]
    }
   ],
   "source": [
    "pb_clone = pb.clone()\n",
    "pb_clone.task_network.add_subtask(bring_truck(truck1, airport1))\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "35A3dp--oOOS"
   },
   "source": [
    "We now get a plan with a single `move` action. Which the only possible plan for this problem.\n",
    "\n",
    "Indeed, to fulfill this task, we had two possibilities:\n",
    " - 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.\n",
    " - 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).\n",
    "\n",
    "Of the two methods only the second one was applicable.\n",
    "\n",
    "If we now try to achieve an objective task with a task that would require the first method, we get an empty plan:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {
    "id": "jbwJbJv8oQ9B"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plan: []\n"
     ]
    }
   ],
   "source": [
    "pb_clone = pb.clone()\n",
    "pb_clone.task_network.add_subtask(bring_truck, truck1, loc1)\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "L-MnST4ioTKo"
   },
   "source": [
    "### Going up the hierarchy\n",
    "\n",
    "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.\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {
    "id": "t7jLGJ1xoVxq"
   },
   "outputs": [],
   "source": [
    "# Task for transporting a given package to a given location,\n",
    "# This method assumes that the package is already in the right city\n",
    "transport_in_city = pb.add_task(\"transport-in-city\", package=Package, destination=Loc)\n",
    "\n",
    "# Method 1: handling the case where the package is already at the destination\n",
    "m = Method(\"transport-in-city-noop\", package=Package, to=Loc)\n",
    "m.set_task(transport_in_city, m.package, m.to)  # set the task that this method achieve\n",
    "m.add_precondition(Equals(loc(m.package), m.to))  # only allow using this method if the package is already at the destination\n",
    "# note: no subtasks are added => nothing to do in this method\n",
    "pb.add_method(m)\n",
    "\n",
    "m = Method(\"transport-in-city-truck\", package=Package, orig=Loc, to=Loc, truck=Truck)\n",
    "m.set_task(transport_in_city, m.package, m.to)\n",
    "m.add_precondition(Equals(loc(m.package), m.orig)) # package is at origin\n",
    "m.add_precondition(Not(Equals(m.orig, m.to)))\n",
    "m.add_precondition(Equals(city(m.orig), city(m.to)))  # destination is the same city\n",
    "# this method decomposed into a sequence of 4 subtasks (mixing the load/unload action and the 'bring-truck' task)\n",
    "t1 = m.add_subtask(bring_truck, m.truck, m.orig)  # bring truck to package location\n",
    "t2 = m.add_subtask(load, m.package, m.truck, m.orig)  # load package in truck\n",
    "t3 = m.add_subtask(bring_truck, m.truck, m.to)  # bring truck to target location\n",
    "t4 = m.add_subtask(unload, m.package, m.truck, m.to)  # unload package at target location\n",
    "m.set_ordered(t1, t2, t3, t4)  # enforce all 4 subtasks to be done in this order\n",
    "pb.add_method(m)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "re1sYZHKoYx5"
   },
   "source": [
    "Finally we set the objective of the problem, here transporting `package1` to `loc1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {
    "id": "4zKqcGHlocdY"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Plan: [move(truck1, loc1, airport1), load(package1, truck1, airport1), move(truck1, airport1, loc1), unload(package1, truck1, loc1)]\n"
     ]
    }
   ],
   "source": [
    "pb_clone = pb.clone()\n",
    "pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We can of course define multiple objectives for different packages."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "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)]\n"
     ]
    }
   ],
   "source": [
    "pb_clone = pb.clone()\n",
    "pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))\n",
    "pb_clone.task_network.add_subtask(transport_in_city(package2, airport1))\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "OTDDF5M1oezl"
   },
   "source": [
    "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.\n",
    "\n",
    "For instance, we could force `package1` to be handled before `package2`:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {
    "id": "8FTO4AoTojko"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "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)]\n"
     ]
    }
   ],
   "source": [
    "pb_clone = pb.clone()\n",
    "t1 = pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))\n",
    "t2 = pb_clone.task_network.add_subtask(transport_in_city(package2, airport1))\n",
    "pb_clone.task_network.set_ordered(t1, t2) # force t1 to be completed before starting t2\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "id": "Q-Pju4K2q_bM"
   },
   "source": [
    "We could also require that `package1` be first transported to `loc1` and then back to `airport1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {
    "id": "wuTcp_xTxvTj"
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "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)]\n"
     ]
    }
   ],
   "source": [
    "pb_clone = pb.clone()\n",
    "t1 = pb_clone.task_network.add_subtask(transport_in_city(package1, loc1))\n",
    "t2 = pb_clone.task_network.add_subtask(transport_in_city(package1, airport1))\n",
    "pb_clone.task_network.set_ordered(t1, t2) # force t1 to be completed before starting t2\n",
    "solve(pb_clone)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Going further\n",
    "\n",
    "Possible exercise: create the task and methods necessary to transport a package between two cities."
   ]
  }
 ],
 "metadata": {
  "celltoolbar": "Tags",
  "colab": {
   "collapsed_sections": [],
   "name": "UP Hierarchical Planning",
   "provenance": []
  },
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.10.6"
  },
  "vscode": {
   "interpreter": {
    "hash": "e7370f93d1d0cde622a1f8e1c04877d8463912d04d973331ad4851f04de6915a"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}