planning_angelic_search.ipynb

{
 "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. <br>\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. <br>\n",
    "   It is a nested list, containing sequence a of actions with their optimistic and pessimistic\n",
    "   description "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 66,
   "metadata": {},
   "outputs": [],
   "source": [
    "from planning import * "
   ]
  },
  {
   "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": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### Decompose \n",
    "-  Finds recursively the sequence of states and actions that lead us from initial state to goal.\n",
    "-  For each of the above actions we find their refinements,if they are not primitive, by calling the angelic_search function. \n",
    "   If there are not refinements return None\n",
    "   \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example\n",
    "\n",
    "Suppose that somebody wants to get to the airport. \n",
    "The possible ways to do so is either get a taxi, or drive to the airport. <br>\n",
    "Those two actions have some preconditions and some effects. \n",
    "If you get the taxi, you need to have cash, whereas if you drive you need to have a car. <br>\n",
    "Thus we define the following hierarchy of possible actions.\n",
    "\n",
    "##### hierarchy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [],
   "source": [
    "library = {\n",
    "        'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)', 'Taxi(Home, SFO)'],\n",
    "        'steps': [['Drive(Home, SFOLongTermParking)', 'Shuttle(SFOLongTermParking, SFO)'], ['Taxi(Home, SFO)'], [], [], []],\n",
    "        'precond': [['At(Home) & Have(Car)'], ['At(Home)'], ['At(Home) & Have(Car)'], ['At(SFOLongTermParking)'], ['At(Home)']],\n",
    "        'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(SFOLongTermParking) & ~At(Home)'], ['At(SFO) & ~At(LongTermParking)'], ['At(SFO) & ~At(Home) & ~Have(Cash)']] }\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "the possible actions are the following:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 68,
   "metadata": {},
   "outputs": [],
   "source": [
    "go_SFO = HLA('Go(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home)')\n",
    "taxi_SFO = HLA('Taxi(Home,SFO)', precond='At(Home)', effect='At(SFO) & ~At(Home) & ~Have(Cash)')\n",
    "drive_SFOLongTermParking = HLA('Drive(Home, SFOLongTermParking)', 'At(Home) & Have(Car)','At(SFOLongTermParking) & ~At(Home)' )\n",
    "shuttle_SFO = HLA('Shuttle(SFOLongTermParking, SFO)', 'At(SFOLongTermParking)', 'At(SFO) & ~At(LongTermParking)')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Suppose that (our preconditionds are that) we are Home and we have cash and car and  our goal is to get to SFO and maintain our cash, and our possible actions are the above. <br>\n",
    "##### Then our problem is: "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 69,
   "metadata": {},
   "outputs": [],
   "source": [
    "prob = Problem('At(Home) & Have(Cash) & Have(Car)', 'At(SFO) & Have(Cash)', [go_SFO, taxi_SFO, drive_SFOLongTermParking,shuttle_SFO])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "An agent gives us some approximate information about the plan we will follow: <br>\n",
    "(initialPlan is an Angelic Node, where: \n",
    "-    state is the initial state of the problem, \n",
    "-    parent is None \n",
    "-    action: is a list of actions (Angelic HLA's) with the optimistic estimators of effects and \n",
    "-    action_pes: is a list of actions (Angelic HLA's) with the pessimistic approximations of the effects\n",
    "##### InitialPlan"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 70,
   "metadata": {},
   "outputs": [],
   "source": [
    "angelic_opt_description = Angelic_HLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & $-At(Home)' ) \n",
    "angelic_pes_description = Angelic_HLA('Go(Home, SFO)', precond = 'At(Home)', effect ='$+At(SFO) & ~At(Home)' )\n",
    "\n",
    "initialPlan = [Angelic_Node(prob.init, None, [angelic_opt_description], [angelic_pes_description])] \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We want to find the optimistic and pessimistic reachable set of initialPlan when applied to the problem:\n",
    "##### Optimistic/Pessimistic reachable set"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[[At(Home), Have(Cash), Have(Car)], [Have(Cash), Have(Car), At(SFO), NotAt(Home)], [Have(Cash), Have(Car), NotAt(Home)], [At(Home), Have(Cash), Have(Car), At(SFO)], [At(Home), Have(Cash), Have(Car)]] \n",
      "\n",
      "[[At(Home), Have(Cash), Have(Car)], [Have(Cash), Have(Car), At(SFO), NotAt(Home)], [Have(Cash), Have(Car), NotAt(Home)]]\n"
     ]
    }
   ],
   "source": [
    "opt_reachable_set = Problem.reach_opt(prob.init, initialPlan[0])\n",
    "pes_reachable_set = Problem.reach_pes(prob.init, initialPlan[0])\n",
    "print([x for y in opt_reachable_set.keys() for x in opt_reachable_set[y]], '\\n')\n",
    "print([x for y in pes_reachable_set.keys() for x in pes_reachable_set[y]])\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Refinements"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))]\n",
      "[{'consumes': {}, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'uses': {}, 'completed': False, 'precond': [At(Home), Have(Car)], 'args': (Home, SFOLongTermParking), 'name': 'Drive', 'duration': 0}, {'consumes': {}, 'effect': [At(SFO), NotAt(LongTermParking)], 'uses': {}, 'completed': False, 'precond': [At(SFOLongTermParking)], 'args': (SFOLongTermParking, SFO), 'name': 'Shuttle', 'duration': 0}] \n",
      "\n",
      "[HLA(Taxi(Home, SFO))]\n",
      "[{'consumes': {}, 'effect': [At(SFO), NotAt(Home), NotHave(Cash)], 'uses': {}, 'completed': False, 'precond': [At(Home)], 'args': (Home, SFO), 'name': 'Taxi', 'duration': 0}] \n",
      "\n"
     ]
    }
   ],
   "source": [
    "for sequence in Problem.refinements(go_SFO, prob, library):\n",
    "    print (sequence)\n",
    "    print([x.__dict__ for x in sequence ], '\\n')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Run the angelic search\n",
    "##### Top level call"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Drive(Home, SFOLongTermParking)), HLA(Shuttle(SFOLongTermParking, SFO))] \n",
      "\n",
      "[{'consumes': {}, 'effect': [At(SFOLongTermParking), NotAt(Home)], 'uses': {}, 'completed': False, 'precond': [At(Home), Have(Car)], 'args': (Home, SFOLongTermParking), 'name': 'Drive', 'duration': 0}, {'consumes': {}, 'effect': [At(SFO), NotAt(LongTermParking)], 'uses': {}, 'completed': False, 'precond': [At(SFOLongTermParking)], 'args': (SFOLongTermParking, SFO), 'name': 'Shuttle', 'duration': 0}]\n"
     ]
    }
   ],
   "source": [
    "plan= Problem.angelic_search(prob, library, initialPlan)\n",
    "print (plan, '\\n')\n",
    "print ([x.__dict__ for x in plan])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Example 2"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "library_2 = {\n",
    "        'HLA': ['Go(Home,SFO)', 'Go(Home,SFO)', 'Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)' , 'Metro(MetroStop, SFO)', 'Metro1(MetroStop, SFO)', 'Metro2(MetroStop, SFO)'  ,'Taxi(Home, SFO)'],\n",
    "        'steps': [['Bus(Home, MetroStop)', 'Metro(MetroStop, SFO)'], ['Taxi(Home, SFO)'], [], ['Metro1(MetroStop, SFO)'], ['Metro2(MetroStop, SFO)'],[],[],[]],\n",
    "        'precond': [['At(Home)'], ['At(Home)'], ['At(Home)'], ['At(MetroStop)'], ['At(MetroStop)'],['At(MetroStop)'], ['At(MetroStop)'] ,['At(Home) & Have(Cash)']],\n",
    "        'effect': [['At(SFO) & ~At(Home)'], ['At(SFO) & ~At(Home) & ~Have(Cash)'], ['At(MetroStop) & ~At(Home)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'], ['At(SFO) & ~At(MetroStop)'] , ['At(SFO) & ~At(MetroStop)'] ,['At(SFO) & ~At(Home) & ~Have(Cash)']] \n",
    "        }"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[HLA(Bus(Home, MetroStop)), HLA(Metro1(MetroStop, SFO))] \n",
      "\n",
      "[{'consumes': {}, 'effect': [At(MetroStop), NotAt(Home)], 'uses': {}, 'completed': False, 'precond': [At(Home)], 'args': (Home, MetroStop), 'name': 'Bus', 'duration': 0}, {'consumes': {}, 'effect': [At(SFO), NotAt(MetroStop)], 'uses': {}, 'completed': False, 'precond': [At(MetroStop)], 'args': (MetroStop, SFO), 'name': 'Metro1', 'duration': 0}]\n"
     ]
    }
   ],
   "source": [
    "plan_2 = Problem.angelic_search(prob, library_2, initialPlan)\n",
    "print(plan_2, '\\n')\n",
    "print([x.__dict__ for x in plan_2])"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.5.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}