{
"cells": [
{
"cell_type": "markdown",
"metadata": {},
"source": [
"# Angelic Search \n",
"\n",
"Search using angelic semantics (is a hierarchical search), where the agent chooses the implementation of the HLA's.
\n",
"The algorithms input is: problem, hierarchy and initialPlan\n",
"- problem is of type Problem \n",
"- hierarchy is a dictionary consisting of all the actions. \n",
"- initialPlan is an approximate description(optimistic and pessimistic) of the agents choices for the implementation.
\n",
" initialPlan contains a sequence of HLA's with angelic semantics"
]
},
{
"cell_type": "code",
"execution_count": 1,
"metadata": {},
"outputs": [],
"source": [
"from planning import * \n",
"from notebook import psource"
]
},
{
"cell_type": "markdown",
"metadata": {},
"source": [
"The Angelic search algorithm consists of three parts. \n",
"- Search using angelic semantics\n",
"- Decompose\n",
"- a search in the space of refinements, in a similar way with hierarchical search\n",
"\n",
"### Searching using angelic semantics\n",
"- Find the reachable set (optimistic and pessimistic) of the sequence of angelic HLA in initialPlan\n",
" - If the optimistic reachable set doesn't intersect the goal, then there is no solution\n",
" - If the pessimistic reachable set intersects the goal, then we call decompose, in order to find the sequence of actions that lead us to the goal. \n",
" - If the optimistic reachable set intersects the goal, but the pessimistic doesn't we do some further refinements, in order to see if there is a sequence of actions that achieves the goal. \n",
" \n",
"### Search in space of refinements\n",
"- Create a search tree, that has root the action and children it's refinements\n",
"- Extend frontier by adding each refinement, so that we keep looping till we find all primitive actions\n",
"- If we achieve that we return the path of the solution (search tree), else there is no solution and we return None.\n",
"\n",
" \n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"metadata": {},
"outputs": [
{
"data": {
"text/html": [
"\n",
"\n",
"\n",
"
def angelic_search(problem, hierarchy, initialPlan):\n",
" """\n",
"\t[Figure 11.8] A hierarchical planning algorithm that uses angelic semantics to identify and\n",
"\tcommit to high-level plans that work while avoiding high-level plans that don’t. \n",
"\tThe predicate MAKING-PROGRESS checks to make sure that we aren’t stuck in an infinite regression\n",
"\tof refinements. \n",
"\tAt top level, call ANGELIC -SEARCH with [Act ] as the initialPlan .\n",
"\n",
" initialPlan contains a sequence of HLA's with angelic semantics \n",
"\n",
" The possible effects of an angelic HLA in initialPlan are : \n",
" ~ : effect remove\n",
" $+: effect possibly add\n",
" $-: effect possibly remove\n",
" $$: possibly add or remove\n",
"\t"""\n",
" frontier = deque(initialPlan)\n",
" while True: \n",
" if not frontier:\n",
" return None\n",
" plan = frontier.popleft() # sequence of HLA/Angelic HLA's \n",
" opt_reachable_set = Problem.reach_opt(problem.init, plan)\n",
" pes_reachable_set = Problem.reach_pes(problem.init, plan)\n",
" if problem.intersects_goal(opt_reachable_set): \n",
" if Problem.is_primitive( plan, hierarchy ): \n",
" return ([x for x in plan.action])\n",
" guaranteed = problem.intersects_goal(pes_reachable_set) \n",
" if guaranteed and Problem.making_progress(plan, initialPlan):\n",
" final_state = guaranteed[0] # any element of guaranteed \n",
" #print('decompose')\n",
" return Problem.decompose(hierarchy, problem, plan, final_state, pes_reachable_set)\n",
" (hla, index) = Problem.find_hla(plan, hierarchy) # there should be at least one HLA/Angelic_HLA, otherwise plan would be primitive.\n",
" prefix = plan.action[:index]\n",
" suffix = plan.action[index+1:]\n",
" outcome = Problem(Problem.result(problem.init, prefix), problem.goals , problem.actions )\n",
" for sequence in Problem.refinements(hla, outcome, hierarchy): # find refinements\n",
" frontier.append(Angelic_Node(outcome.init, plan, prefix + sequence+ suffix, prefix+sequence+suffix))\n",
"
def decompose(hierarchy, s_0, plan, s_f, reachable_set):\n",
" solution = [] \n",
" i = max(reachable_set.keys())\n",
" while plan.action_pes: \n",
" action = plan.action_pes.pop()\n",
" if (i==0): \n",
" return solution\n",
" s_i = Problem.find_previous_state(s_f, reachable_set,i, action) \n",
" problem = Problem(s_i, s_f , plan.action)\n",
" angelic_call = Problem.angelic_search(problem, hierarchy, [Angelic_Node(s_i, Node(None), [action],[action])])\n",
" if angelic_call:\n",
" for x in angelic_call: \n",
" solution.insert(0,x)\n",
" else: \n",
" return None\n",
" s_f = s_i\n",
" i-=1\n",
" return solution\n",
"