{ "cells": [ { "cell_type": "markdown", "metadata": { "id": "6nOTljC_mTMn", "slideshow": { "slide_type": "slide" } }, "source": [ "# Hierarchical Planning\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-hierarchical-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-hierarchical-planning.ipynb)" ] }, { "cell_type": "markdown", "metadata": { "id": "t8dCcpf7mivV", "slideshow": { "slide_type": "slide" } }, "source": [ "## Setup\n", "\n", "We start by downloading the unified planning library and a hierarchical planner (aries)." ] }, { "cell_type": "code", "execution_count": null, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.277967428Z", "start_time": "2023-07-07T08:26:01.671820250Z" }, "id": "BoqALxJWdfl8", "tags": [ "remove_from_CI" ] }, "outputs": [], "source": [ "%pip install unified-planning[aries]" ] }, { "cell_type": "code", "execution_count": 2, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.277967428Z", "start_time": "2023-07-07T08:26:01.671820250Z" }, "id": "BoqALxJWdfl8", "tags": [] }, "outputs": [], "source": [ "import unified_planning as up\n", "from unified_planning.shortcuts import *\n", "from unified_planning.model.htn import *" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "## Case study: Logistics problem (IPC 1998)\n", "\n", "![logistics](https://homepages.laas.fr/abitmonnot/files/img/logistics.png)\n", "\n" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "skip" } }, "source": [ "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": 3, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.318700483Z", "start_time": "2023-07-07T08:26:03.314367160Z" }, "id": "huAy2IbVn0GZ", "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "#pb = Problem() # for a non-hierarchical problem\n", "pb = HierarchicalProblem() # make it hierarchical instead\n", "\n", "Package = UserType(\"Package\")\n", "\n", "PackageLoc = UserType(\"PackageLoc\")\n", "Loc = UserType(\"Location\", father=PackageLoc)\n", "Airport = UserType(\"Airport\", father=Loc)\n", "City = UserType(\"City\")\n", "\n", "Vehicle = UserType(\"Vehicle\", father=PackageLoc)\n", "Truck = UserType(\"Truck\", father=Vehicle)\n", "Airplane = UserType(\"Airplane\", father=Vehicle)" ] }, { "cell_type": "code", "execution_count": 3, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.318700483Z", "start_time": "2023-07-07T08:26:03.314367160Z" }, "id": "huAy2IbVn0GZ", "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "types = [City, PackageLoc, Location - PackageLoc, Package, Vehicle - PackageLoc]\n", "\n", "fluents = [\n", " City city[of=Location - PackageLoc]\n", " PackageLoc loc[package=Package]\n", " Location - PackageLoc at[vehicle=Vehicle - PackageLoc]\n", "]\n", "\n", "actions = [\n", "]\n", "\n", "objects = [\n", " City: []\n", " PackageLoc: []\n", " Location - PackageLoc: []\n", " Package: []\n", " Vehicle - PackageLoc: []\n", "]\n", "\n", "initial fluents default = [\n", "]\n", "\n", "initial values = [\n", "]\n", "\n", "goals = [\n", "]\n", "\n", "abstract tasks = [\n", "]\n", "\n", "methods = [\n", "]\n", "\n", "task network {\n", " subtasks = [\n", " ]\n", "}\n" ] } ], "source": [ "# city of location\n", "city = pb.add_fluent(\"city\", City, of=Loc) \n", "\n", "# current location of package / vehicle\n", "loc = pb.add_fluent(\"loc\", PackageLoc, package=Package)\n", "at = pb.add_fluent(\"at\", Loc, vehicle=Vehicle)\n", "print(pb)" ] }, { "cell_type": "code", "execution_count": 4, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.318700483Z", "start_time": "2023-07-07T08:26:03.314367160Z" }, "id": "huAy2IbVn0GZ", "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# city1 with a location and an airport\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 with one location and an airport\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)" ] }, { "cell_type": "code", "execution_count": 5, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.318700483Z", "start_time": "2023-07-07T08:26:03.314367160Z" }, "id": "huAy2IbVn0GZ", "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "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)" ] }, { "cell_type": "code", "execution_count": 6, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.318700483Z", "start_time": "2023-07-07T08:26:03.314367160Z" }, "id": "huAy2IbVn0GZ", "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "action load(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {\n", " preconditions = [\n", " (at(vehicle) == l)\n", " (loc(package) == l)\n", " ]\n", " effects = [\n", " loc(package) := vehicle\n", " ]\n", " }\n", "action unload(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {\n", " preconditions = [\n", " (at(vehicle) == l)\n", " (loc(package) == vehicle)\n", " ]\n", " effects = [\n", " loc(package) := l\n", " ]\n", " }\n" ] } ], "source": [ "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", "print(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", "print(unload)" ] }, { "cell_type": "code", "execution_count": 7, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.318700483Z", "start_time": "2023-07-07T08:26:03.314367160Z" }, "id": "huAy2IbVn0GZ", "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "action move(Truck - Vehicle truck, Location - PackageLoc src, Location - PackageLoc tgt) {\n", " preconditions = [\n", " (city(src) == city(tgt))\n", " (at(truck) == src)\n", " ]\n", " effects = [\n", " at(truck) := tgt\n", " ]\n", " }\n", "action fly-plane(Airplane - Vehicle plane, Airport - Location src, Airport - Location tgt) {\n", " preconditions = [\n", " (at(plane) == src)\n", " ]\n", " effects = [\n", " at(plane) := tgt\n", " ]\n", " }\n" ] } ], "source": [ "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", "print(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)\n", "print(fly_plane)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "If we now create and solve a new version of problem with a trivial goal statement:" ] }, { "cell_type": "code", "execution_count": 8, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369134769Z", "start_time": "2023-07-07T08:26:03.314575334Z" }, "id": "LZUgad7ZoA2p" }, "outputs": [], "source": [ "# helper function that just invokes a planner and prints the plan\n", "def solve(pb: Problem, verbose=False): \n", " result = OneshotPlanner(problem_kind=pb.kind).solve(pb)\n", " if result.plan is not None:\n", " print(\"Plan:\", repr(result.plan) if verbose else str(result.plan))\n", " else:\n", " print(result.status)" ] }, { "cell_type": "code", "execution_count": 9, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369134769Z", "start_time": "2023-07-07T08:26:03.314575334Z" }, "id": "LZUgad7ZoA2p" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "PlanGenerationResultStatus.UNSOLVABLE_INCOMPLETELY\n" ] } ], "source": [ "pb_clone = pb.clone()\n", "pb_clone.add_goal(Equals(at(truck1), airport1))\n", "solve(pb_clone)" ] }, { "cell_type": "markdown", "metadata": { "id": "rVzqSj3XoDPa", "slideshow": { "slide_type": "skip" } }, "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": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Tasks and Methods\n", "\n", "Let us define our first task `bring-truck(truck, dest)`:" ] }, { "cell_type": "code", "execution_count": 10, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369444377Z", "start_time": "2023-07-07T08:26:03.358334675Z" }, "slideshow": { "slide_type": "-" } }, "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": { "slideshow": { "slide_type": "skip" } }, "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": "markdown", "metadata": { "slideshow": { "slide_type": "fragment" } }, "source": [ "\n", "![Bring truck](https://homepages.laas.fr/abitmonnot/files/img/bring-truck.png)" ] }, { "cell_type": "code", "execution_count": 11, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369756021Z", "start_time": "2023-07-07T08:26:03.358476153Z" }, "id": "dRfrnEOfoHD8", "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# Option 1: truck already at destination location, nothing to do\n", "m = Method(\"bring-truck-noop\", truck=Truck, dest=Loc)" ] }, { "cell_type": "code", "execution_count": 12, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369756021Z", "start_time": "2023-07-07T08:26:03.358476153Z" }, "id": "dRfrnEOfoHD8", "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# declares that m achieves the `bring-truck(truck, dest)` task`\n", "m.set_task(bring_truck, m.truck, m.dest) " ] }, { "cell_type": "code", "execution_count": 13, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369756021Z", "start_time": "2023-07-07T08:26:03.358476153Z" }, "id": "dRfrnEOfoHD8", "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# 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", "m.add_precondition(Equals(at(m.truck), m.dest)) " ] }, { "cell_type": "code", "execution_count": 14, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369756021Z", "start_time": "2023-07-07T08:26:03.358476153Z" }, "id": "dRfrnEOfoHD8", "slideshow": { "slide_type": "fragment" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "method bring-truck-noop(Truck - Vehicle truck, Location - PackageLoc dest) {\n", " task = bring-truck(Truck - Vehicle truck, Location - PackageLoc dest)\n", " preconditions = [\n", " (at(truck) == dest)\n", " ]\n", "}\n" ] } ], "source": [ "pb.add_method(m)\n", "print(m)" ] }, { "cell_type": "code", "execution_count": 15, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369993732Z", "start_time": "2023-07-07T08:26:03.358552246Z" }, "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# Option 2: truck not at target location, move it\n", "m = Method(\"bring-truck-move\", truck=Truck, orig=Loc, dest=Loc)\n", "# declares that m achieves the `bring-truck(truck, to)` task`\n", "m.set_task(bring_truck, m.truck, m.dest) " ] }, { "cell_type": "code", "execution_count": 16, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.369993732Z", "start_time": "2023-07-07T08:26:03.358552246Z" }, "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "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.dest))) # in a different location\n", "m.add_precondition(Equals(city(m.orig), city(m.dest))) # of the same city" ] }, { "cell_type": "code", "execution_count": 17, "metadata": { "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# accomplishing this method requires executing a `move` action\n", "m.add_subtask(move, m.truck, m.orig, m.dest, ident=\"move-subtask\") \n", "\n", "pb.add_method(m)" ] }, { "cell_type": "code", "execution_count": 18, "metadata": { "scrolled": true, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "types = [City, PackageLoc, Location - PackageLoc, Package, Vehicle - PackageLoc, Airport - Location, Truck - Vehicle, Airplane - Vehicle]\n", "\n", "fluents = [\n", " City city[of=Location - PackageLoc]\n", " PackageLoc loc[package=Package]\n", " Location - PackageLoc at[vehicle=Vehicle - PackageLoc]\n", "]\n", "\n", "actions = [\n", " action load(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {\n", " preconditions = [\n", " (at(vehicle) == l)\n", " (loc(package) == l)\n", " ]\n", " effects = [\n", " loc(package) := vehicle\n", " ]\n", " }\n", " action unload(Package package, Vehicle - PackageLoc vehicle, Location - PackageLoc l) {\n", " preconditions = [\n", " (at(vehicle) == l)\n", " (loc(package) == vehicle)\n", " ]\n", " effects = [\n", " loc(package) := l\n", " ]\n", " }\n", " action move(Truck - Vehicle truck, Location - PackageLoc src, Location - PackageLoc tgt) {\n", " preconditions = [\n", " (city(src) == city(tgt))\n", " (at(truck) == src)\n", " ]\n", " effects = [\n", " at(truck) := tgt\n", " ]\n", " }\n", " action fly-plane(Airplane - Vehicle plane, Airport - Location src, Airport - Location tgt) {\n", " preconditions = [\n", " (at(plane) == src)\n", " ]\n", " effects = [\n", " at(plane) := tgt\n", " ]\n", " }\n", "]\n", "\n", "objects = [\n", " City: [city1, city2]\n", " PackageLoc: [loc1, airport1, loc2, airport2, truck1]\n", " Location - PackageLoc: [loc1, airport1, loc2, airport2]\n", " Package: [package1, package2]\n", " Vehicle - PackageLoc: [truck1]\n", " Airport - Location: [airport1, airport2]\n", " Truck - Vehicle: [truck1]\n", " Airplane - Vehicle: []\n", "]\n", "\n", "initial fluents default = [\n", "]\n", "\n", "initial values = [\n", " city(loc1) := city1\n", " city(airport1) := city1\n", " city(loc2) := city2\n", " city(airport2) := city2\n", " at(truck1) := loc1\n", " loc(package1) := airport1\n", " loc(package2) := loc1\n", "]\n", "\n", "goals = [\n", "]\n", "\n", "abstract tasks = [\n", " bring-truck[truck=Truck - Vehicle, destination=Location - PackageLoc]\n", "]\n", "\n", "methods = [\n", " method bring-truck-noop(Truck - Vehicle truck, Location - PackageLoc dest) {\n", " task = bring-truck(Truck - Vehicle truck, Location - PackageLoc dest)\n", " preconditions = [\n", " (at(truck) == dest)\n", " ]\n", " }\n", " method bring-truck-move(Truck - Vehicle truck, Location - PackageLoc orig, Location - PackageLoc dest) {\n", " task = bring-truck(Truck - Vehicle truck, Location - PackageLoc dest)\n", " preconditions = [\n", " (at(truck) == orig)\n", " (not (orig == dest))\n", " (city(orig) == city(dest))\n", " ]\n", " subtasks = [\n", " move-subtask: move(truck, orig, dest)\n", " ]\n", " }\n", "]\n", "\n", "task network {\n", " subtasks = [\n", " ]\n", "}\n" ] } ], "source": [ "print(pb)" ] }, { "cell_type": "markdown", "metadata": { "slideshow": { "slide_type": "slide" } }, "source": [ "Now let's try to solve this problem. Recall that curently, it has no objectives." ] }, { "cell_type": "code", "execution_count": 19, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.447951312Z", "start_time": "2023-07-07T08:26:03.358638957Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical TimeTriggeredPlan:\n" ] } ], "source": [ "solve(pb) # no objective tasks, empty plan" ] }, { "cell_type": "markdown", "metadata": { "id": "iMuggWWioJ8K", "slideshow": { "slide_type": "skip" } }, "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": 20, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.448372725Z", "start_time": "2023-07-07T08:26:03.402594258Z" }, "id": "pgrJOj6ioMSC", "scrolled": true, "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical SequentialPlan:\n", " move(truck1, loc1, airport1)\n" ] } ], "source": [ "pb_clone = pb.clone()\n", "pb_clone.task_network.add_subtask(bring_truck(truck1, airport1))\n", "\n", "solve(pb_clone)" ] }, { "cell_type": "markdown", "metadata": { "id": "35A3dp--oOOS", "slideshow": { "slide_type": "skip" } }, "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": 21, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.448945016Z", "start_time": "2023-07-07T08:26:03.402954723Z" }, "id": "jbwJbJv8oQ9B", "slideshow": { "slide_type": "slide" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical TimeTriggeredPlan:\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", "slideshow": { "slide_type": "slide" } }, "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", "![Transport](https://homepages.laas.fr/abitmonnot/files/img/transport.png)\n" ] }, { "cell_type": "code", "execution_count": 22, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.449316846Z", "start_time": "2023-07-07T08:26:03.432375118Z" }, "id": "t7jLGJ1xoVxq", "slideshow": { "slide_type": "-" } }, "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)" ] }, { "cell_type": "code", "execution_count": 23, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.449316846Z", "start_time": "2023-07-07T08:26:03.432375118Z" }, "id": "t7jLGJ1xoVxq", "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "# 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)" ] }, { "cell_type": "code", "execution_count": 24, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.449316846Z", "start_time": "2023-07-07T08:26:03.432375118Z" }, "id": "t7jLGJ1xoVxq", "slideshow": { "slide_type": "slide" } }, "outputs": [], "source": [ "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" ] }, { "cell_type": "code", "execution_count": 25, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.449316846Z", "start_time": "2023-07-07T08:26:03.432375118Z" }, "id": "t7jLGJ1xoVxq", "slideshow": { "slide_type": "fragment" } }, "outputs": [], "source": [ "# 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", "slideshow": { "slide_type": "slide" } }, "source": [ "Finally we set the objective of the problem, here transporting `package1` to `loc1`." ] }, { "cell_type": "code", "execution_count": 26, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.521398297Z", "start_time": "2023-07-07T08:26:03.438698913Z" }, "id": "4zKqcGHlocdY" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical SequentialPlan:\n", " move(truck1, loc1, airport1)\n", " load(package1, truck1, airport1)\n", " move(truck1, airport1, loc1)\n", " 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": { "slideshow": { "slide_type": "slide" } }, "source": [ "We can of course define multiple objectives for different packages." ] }, { "cell_type": "code", "execution_count": 27, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.533219405Z", "start_time": "2023-07-07T08:26:03.490224379Z" } }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical SequentialPlan:\n", " load(package2, truck1, loc1)\n", " move(truck1, loc1, airport1)\n", " load(package1, truck1, airport1)\n", " unload(package2, truck1, airport1)\n", " move(truck1, airport1, loc1)\n", " 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", "slideshow": { "slide_type": "slide" } }, "source": [ "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.\n", "\n", "For instance, we could force `package1` to be handled before `package2`:" ] }, { "cell_type": "code", "execution_count": 28, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.575363573Z", "start_time": "2023-07-07T08:26:03.530770930Z" }, "id": "8FTO4AoTojko" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical SequentialPlan:\n", " move(truck1, loc1, airport1)\n", " load(package1, truck1, airport1)\n", " move(truck1, airport1, loc1)\n", " unload(package1, truck1, loc1)\n", " load(package2, truck1, loc1)\n", " move(truck1, loc1, airport1)\n", " 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", "slideshow": { "slide_type": "slide" } }, "source": [ "We could also require that `package1` be first transported to `loc1` and then back to `airport1`." ] }, { "cell_type": "code", "execution_count": 29, "metadata": { "ExecuteTime": { "end_time": "2023-07-07T08:26:03.623184318Z", "start_time": "2023-07-07T08:26:03.574925362Z" }, "id": "wuTcp_xTxvTj" }, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Plan: Hiearchical SequentialPlan:\n", " move(truck1, loc1, airport1)\n", " load(package1, truck1, airport1)\n", " move(truck1, airport1, loc1)\n", " unload(package1, truck1, loc1)\n", " load(package1, truck1, loc1)\n", " move(truck1, loc1, airport1)\n", " 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": { "slideshow": { "slide_type": "slide" } }, "source": [ "### Going further\n", "\n", "- create the task and methods necessary to transport a package between two cities.\n", "- Make actions durative\n", "- Add optimality metrics (action costs, makespan, ...)" ] } ], "metadata": { "celltoolbar": "Slideshow", "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.12" }, "vscode": { "interpreter": { "hash": "e7370f93d1d0cde622a1f8e1c04877d8463912d04d973331ad4851f04de6915a" } } }, "nbformat": 4, "nbformat_minor": 1 }