{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Hierarchical Search \n",
"\n",
"Hierarchical search is a a planning algorithm in high level of abstraction.
\n",
"Instead of actions as in classical planning (chapter 10) (primitive actions) we now use high level actions (HLAs) (see planning.ipynb)
\n",
"\n",
"## Refinements\n",
"\n",
"Each __HLA__ has one or more refinements into a sequence of actions, each of which may be an HLA or a primitive action (which has no refinements by definition).
\n",
"For example:\n",
"- (a) the high level action \"Go to San Fransisco airport\" (Go(Home, SFO)), might have two possible refinements, \"Drive to San Fransisco airport\" and \"Taxi to San Fransisco airport\". \n",
"
\n",
"- (b) A recursive refinement for navigation in the vacuum world would be: to get to a\n",
"destination, take a step, and then go to the destination.\n",
"
\n",
"![title](images/refinement.png)\n",
"
\n",
"- __implementation__: An HLA refinement that contains only primitive actions is called an implementation of the HLA\n",
"- An implementation of a high-level plan (a sequence of HLAs) is the concatenation of implementations of each HLA in the sequence\n",
"- A high-level plan __achieves the goal__ from a given state if at least one of its implementations achieves the goal from that state\n",
"
\n",
"\n",
"The refinements function input is: \n",
"- __hla__: the HLA of which we want to compute its refinements\n",
"- __state__: the knoweledge base of the current problem (Problem.init)\n",
"- __library__: the hierarchy of the actions in the planning problem\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"metadata": {},
"outputs": [],
"source": [
"from planning import * \n",
"from notebook import psource"
]
},
{
"cell_type": "code",
"execution_count": 11,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"
def refinements(hla, state, library): # refinements may be (multiple) HLA themselves ...\n",
" """\n",
" state is a Problem, containing the current state kb\n",
" library is a dictionary containing details for every possible refinement. eg:\n",
" {\n",
" 'HLA': [\n",
" 'Go(Home, SFO)',\n",
" 'Go(Home, SFO)',\n",
" 'Drive(Home, SFOLongTermParking)',\n",
" 'Shuttle(SFOLongTermParking, SFO)',\n",
" 'Taxi(Home, SFO)'\n",
" ],\n",
" 'steps': [\n",
" ['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'],\n",
" ['Taxi(Home, SFO)'],\n",
" [],\n",
" [],\n",
" []\n",
" ],\n",
" # empty refinements indicate a primitive action\n",
" 'precond': [\n",
" ['At(Home) & Have(Car)'],\n",
" ['At(Home)'],\n",
" ['At(Home) & Have(Car)'],\n",
" ['At(SFOLongTermParking)'],\n",
" ['At(Home)']\n",
" ],\n",
" 'effect': [\n",
" ['At(SFO) & ~At(Home)'],\n",
" ['At(SFO) & ~At(Home)'],\n",
" ['At(SFOLongTermParking) & ~At(Home)'],\n",
" ['At(SFO) & ~At(SFOLongTermParking)'],\n",
" ['At(SFO) & ~At(Home)']\n",
" ]\n",
" }\n",
" """\n",
" e = Expr(hla.name, hla.args)\n",
" indices = [i for i, x in enumerate(library['HLA']) if expr(x).op == hla.name]\n",
" for i in indices:\n",
" actions = []\n",
" for j in range(len(library['steps'][i])):\n",
" # find the index of the step [j] of the HLA \n",
" index_step = [k for k,x in enumerate(library['HLA']) if x == library['steps'][i][j]][0]\n",
" precond = library['precond'][index_step][0] # preconditions of step [j]\n",
" effect = library['effect'][index_step][0] # effect of step [j]\n",
" actions.append(HLA(library['steps'][i][j], precond, effect))\n",
" yield actions\n",
"
def hierarchical_search(problem, hierarchy):\n",
" """\n",
" [Figure 11.5] 'Hierarchical Search, a Breadth First Search implementation of Hierarchical\n",
" Forward Planning Search'\n",
" The problem is a real-world problem defined by the problem class, and the hierarchy is\n",
" a dictionary of HLA - refinements (see refinements generator for details)\n",
" """\n",
" act = Node(problem.init, None, [problem.actions[0]])\n",
" frontier = deque()\n",
" frontier.append(act)\n",
" while True:\n",
" if not frontier:\n",
" return None\n",
" plan = frontier.popleft()\n",
" (hla, index) = Problem.find_hla(plan, hierarchy) # finds the first non primitive hla in plan actions\n",
" prefix = plan.action[:index]\n",
" outcome = Problem(Problem.result(problem.init, prefix), problem.goals , problem.actions )\n",
" suffix = plan.action[index+1:]\n",
" if not hla: # hla is None and plan is primitive\n",
" if outcome.goal_test():\n",
" return plan.action\n",
" else:\n",
" for sequence in Problem.refinements(hla, outcome, hierarchy): # find refinements\n",
" frontier.append(Node(outcome.init, plan, prefix + sequence+ suffix))\n",
"