Lab10-GraphPlan-Skel (1).ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Planificare; Graphplan.\n",
    "\n",
    "- Andrei Olaru\n",
    "- Tudor Berariu\n",
    "\n",
    "### Scopul laboratorului\n",
    "\n",
    "Familiarizarea cu un algoritm de planificare, în acest caz Graphplan. Concret, vezi avea de implementat construcția grafului de planificare pentru algoritm.\n",
    "\n",
    "### Graful de planificare\n",
    "\n",
    "Graful de planificare este o structură ce vine în ajutorul unui algoritm de planificare pentru a stabili ce acțiuni se pot realiza la un moment dat și care sunt posibilele acțiuni simultane și posibilele conflicte între acțiuni și fapte.\n",
    "\n",
    "Graful de planificare este un graf orientat aciclic care se organizează pe niveluri de stare / acțiuni alternative.\n",
    "\n",
    "Primul nivel are fapt ca noduri, și acestea nu au muchii de intrare. Următorul nivel are acțiuni ca noduri, și conține toate acțiunile care s-ar putea realiza având în vedere faptele de pe primul nivel. Al treilea nivel conține, ca noduri, faptele care ar putea rezulta din acțiunile de pe al doilea nivel, etc.\n",
    "\n",
    "Pe fiecare nivel pot exista relații de excludere mutuală (mutex) între noduri, în sensul că cele două noduri nu ar putea exista / nu s-ar putea realiza în același timp.\n",
    "\n",
    "Resurse:\n",
    "\n",
    "Artificial Intelligence: A Modern Approach (Russel & Norvig), Capitol 11.4 (pag 395-402)\n",
    "http://aima.cs.berkeley.edu/2nd-ed/newchap11.pdf\n",
    "\n",
    "Curs IA Planificare, slides 20-31.\n",
    "\n",
    "\n",
    "### Reprezentare\n",
    "\n",
    "Vom folosi pentru reprezentarea propozițiilor string-uri care conțin întregul literal. Literalii negativi vor începe cu `NOT_`.\n",
    "\n",
    "Vom reprezenta acțiunea de păstrare a unui literal (*persistence actions*) ca `____P`, unde `P` este reprezentarea literalului. E.g. `____EatenCake`.\n",
    "\n",
    "Vom folosi pentru reprezentarea unei liste de excluderi mutuale o listă de perechi de acțiuni sau literali.\n",
    "\n",
    "Vom reprezenta graful ca o listă de niveluri, unde un nivel este un dicționar ce conține două chei: `mutex` și `state` sau `actions`, în funcție de tipul nivelului. Pe nivelurile pare vor fi stări, cele impare acțiuni."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 89,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "NOT_Fact\n",
      "NOT_Fact\n",
      "Fact\n"
     ]
    }
   ],
   "source": [
    "# Neagă P (cu P literal pozitiv)\n",
    "def NOT(P):\n",
    "    return \"NOT_\" + P\n",
    "# calculează opusul lui P\n",
    "def opposite(P):\n",
    "    if P[0:4] == \"NOT_\":\n",
    "        return P[4:]\n",
    "    else:\n",
    "        return NOT(P)\n",
    "\n",
    "def is_opposite(P, Q):\n",
    "    return P == opposite(Q)\n",
    "\n",
    "print(NOT(\"Fact\"))\n",
    "print(opposite(\"Fact\"))\n",
    "print(opposite(NOT(\"Fact\")))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 90,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# How to have cake and eat it too?\n",
    "Cake = {}\n",
    "Cake['init'] = [\"HaveCake\", NOT(\"EatenCake\")]\n",
    "Cake['goal'] = [\"EatenCake\", \"HaveCake\"]\n",
    "Cake['actions'] = {}\n",
    "Cake['actions'][\"EatCake\"] = ([\"HaveCake\"], [NOT(\"HaveCake\"),\"EatenCake\"])\n",
    "Cake['actions'][\"BakeCake\"] = ([NOT(\"HaveCake\")], [\"HaveCake\"])\n",
    "\n",
    "# How to solve the problem of a flat tire?\n",
    "FlatTire = {}\n",
    "FlatTire['init'] = [\"At(Flat,Axle)\", \"At(Spare,Trunk)\",NOT(\"At(Flat,Ground)\"),NOT(\"At(Spare,Axle)\"),NOT(\"At(Spare,Ground)\")]\n",
    "FlatTire['goal'] = [\"At(Spare,Axle)\"]\n",
    "FA = {}\n",
    "FA[\"Remove(Spare,Trunk)\"] = ([\"At(Spare,Trunk)\"],[NOT(\"At(Spare,Trunk)\"),\"At(Spare,Ground)\"])\n",
    "FA[\"Remove(Flat,Axle)\"] = ([\"At(Flat,Axle)\"],[NOT(\"At(Flat,Axle)\"),\"At(Flat,Ground)\"])\n",
    "FA[\"PutOn(Spare,Axle)\"] = ([\"At(Spare,Ground)\",NOT(\"At(Flat,Axle)\")],[\"At(Spare,Axle)\",NOT(\"At(Spare,Ground)\")])\n",
    "FlatTire['actions'] = FA\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 91,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# returns true if the smaller set is included in the bigger set\n",
    "def included(smaller, bigger):\n",
    "    for x in smaller:\n",
    "        if not x in bigger:\n",
    "            return False\n",
    "    return True\n",
    "\n",
    "# returns true if any 2 elements in to_check are mutually exclusive, according to the list of pairs in mutex\n",
    "def not_mutex(to_check, mutex):\n",
    "    for x in to_check:\n",
    "        for y in to_check:\n",
    "            if (x, y) in mutex or (y, x) in mutex:\n",
    "                return False\n",
    "    return True\n",
    "\n",
    "# returns true if the action is a \"no operation\" action\n",
    "def isNop(act):\n",
    "    return act[0:4] == \"____\"\n",
    "\n",
    "# prints the graph. The displayed level number will start from the number specified by the optional argument.\n",
    "def print_graph(graph, startLevel = 0):\n",
    "    l = startLevel\n",
    "    for level in graph:\n",
    "        print(\"[\",l,\"]\")\n",
    "        for element in level:\n",
    "            print(\"\\t\",element,\":\",level[element])\n",
    "        l = l + 1\n",
    "#print(included(\"abc\", \"adecbf\"))\n",
    "#print(included(\"abc\", \"adecf\"))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 93,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# returns true if all the goals are found in the last level of the graph and they are not mutually exclusive\n",
    "def Maybe_completed(goals, graph):\n",
    "    lLevel = len(graph) - 1\n",
    "    state = graph[lLevel]['state']\n",
    "    mutex = graph[lLevel]['mutex']\n",
    "    return included(goals, state) and not_mutex(goals, mutex)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 99,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "# Extends the given graph with a level of actions and a level of states\n",
    "# all_actions contains the definition of the actions, as given in the problem (problem['actions'])\n",
    "# The method returns the two added levels in the graph (does not change the graph)\n",
    "def Extend_graph(all_actions, graph):\n",
    "    lastLevel = len(graph) - 1\n",
    "    # the last level in the graph\n",
    "    state = graph[lastLevel]['state']\n",
    "    mutex = graph[lastLevel]['mutex']\n",
    "    \n",
    "    # compute applicable actions: all actions whose preconditions exist in the state and are not mutually exclusive\n",
    "    # suggestion: store available actions as name -> (preconditions, effects)\n",
    "    actions = {name: tupl for name, tupl in all_actions.items() if included(tupl[0], state) and not_mutex(tupl[0], mutex)}\n",
    "    # TODO\n",
    "    print(\"state\", state)\n",
    "    print(\"actions\", actions)\n",
    "    \n",
    "    # add nop actions\n",
    "    for fact in state:\n",
    "        actions[\"____\" + fact] = ([fact], [fact])\n",
    "    \n",
    "    # compute mutexes\n",
    "    # don't add mutexes for pairs of persistence actions (no need)\n",
    "    mutex_actions = [(name1, name2) for name1, tupl1 in actions.items() for name2, tupl2 in actions.items()\n",
    "                          if name1 != name2 #and not isNop(name1) and not isNop(name2)\n",
    "                          and (any([is_opposite(a, b) for a in tupl1[1] for b in tupl2[1]])\n",
    "                            or any([is_opposite(a, b) for a in tupl1[0] for b in tupl2[0]])\n",
    "                            or any([is_opposite(a, b) for a in tupl1[0] for b in tupl2[1]])\n",
    "                            or any([is_opposite(a, b) for a in tupl1[1] for b in tupl2[0]]))]\n",
    "    print(\"mutex_actions\", mutex_actions)\n",
    "    # TODO\n",
    "    # helpful prints:\n",
    "    #print(\"add\",str((a1,a2)),\"inconsistent\",effect,\"for\",a1,\"and\",opposite(effect),\"for\",a2)\n",
    "    #print(\"add\",str((a1,a2)),\"interferring effect\",effect,\"for\",a1,\"and precond\",opposite(effect),\"for\",a2)\n",
    "    #print(\"add\",str((a1,a2)),\"competing needs on\",precond,\"for\",a1,\"and\",opposite(precond),\"for\",a2)\n",
    "    \n",
    "    # compute effects\n",
    "    # suggestion: store effects as effect -> [actions giving the effect]\n",
    "    effects = {}\n",
    "    for name, tupl in actions.items():\n",
    "        for e in tupl[1]:\n",
    "            if e not in effects:\n",
    "                effects[e] = []\n",
    "            if name not in effects[e]:\n",
    "                effects[e].append(name)\n",
    "    print(\"effects\", effects)\n",
    "    # TODO\n",
    " \n",
    "    # compute mutexes between effects\n",
    "    # 2 effects are mutex if they are opposite literals or if there is\n",
    "    # no way in which the effects could result from non-exclusive actions\n",
    "    mutex_effects = [(e1, e2) for e1, a1 in effects.items() for e2, a2 in effects.items()\n",
    "                              if is_opposite(e1, e2)\n",
    "                              or not not_mutex(a1 + a2, mutex_actions)]\n",
    "#     for \n",
    "    print(\"mutex_effects\", mutex_effects)\n",
    "    # TODO\n",
    "    \n",
    "    effects = [e for e in effects]\n",
    "    actions = [a for a in actions]\n",
    "    \n",
    "    # result\n",
    "    return ({'actions': actions, 'mutex': mutex_actions}, {'state': effects, 'mutex': mutex_effects})"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 100,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "DEBUG = False\n",
    "def printd(*args):\n",
    "    if DEBUG:\n",
    "        print(*args)\n",
    "\n",
    "# Extracts a solution, given a set of goals, a graph, and a problem\n",
    "def Extract_solution(goals, graph, problem):\n",
    "    printd(\"=== checking; goals:\", goals)\n",
    "    if DEBUG:\n",
    "        print_graph(graph)\n",
    "    if len(graph) == 1:\n",
    "        if included(goals, graph[0]['state']):\n",
    "            printd(\"## Done\")\n",
    "            return []\n",
    "        else:\n",
    "            return False\n",
    "    actions = graph[len(graph) - 2]['actions']\n",
    "    mutex = graph[len(graph) - 2]['mutex']\n",
    "    all_actions = problem['actions']\n",
    "    potential_actions = []\n",
    "    first = True\n",
    "    for g in goals:\n",
    "        for a in actions:\n",
    "            if (isNop(a) and a[4:] == g) or (not isNop(a) and g in all_actions[a][1]):\n",
    "                if first:\n",
    "                    potential_actions.append([a])\n",
    "                else:\n",
    "                    potential_actions = [aa + [a] for aa in potential_actions]\n",
    "        first = False\n",
    "    printd(\"## potential actions:\",potential_actions)\n",
    "    for comb in potential_actions:\n",
    "        new_goals = []\n",
    "        for act in comb:\n",
    "            if isNop(act):\n",
    "                if act[4:] not in new_goals:\n",
    "                    new_goals.append(act[4:])\n",
    "            else:\n",
    "                new_goals.extend([precond for precond in all_actions[act][0] if precond not in new_goals])\n",
    "        result = Extract_solution(new_goals, graph[:-2], problem)\n",
    "        printd(\"## Result:\",result)\n",
    "        if result != False:\n",
    "            return result + comb  \n",
    "    return False\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 101,
   "metadata": {
    "collapsed": false,
    "scrolled": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "first level: \n",
      "[ 0 ]\n",
      "\t state : ['HaveCake', 'NOT_EatenCake']\n",
      "\t mutex : []\n",
      "state ['HaveCake', 'NOT_EatenCake']\n",
      "actions {'EatCake': (['HaveCake'], ['NOT_HaveCake', 'EatenCake'])}\n",
      "mutex_actions [('____NOT_EatenCake', 'EatCake'), ('EatCake', '____NOT_EatenCake'), ('EatCake', '____HaveCake'), ('____HaveCake', 'EatCake')]\n",
      "effects {'NOT_EatenCake': ['____NOT_EatenCake'], 'EatenCake': ['EatCake'], 'HaveCake': ['____HaveCake'], 'NOT_HaveCake': ['EatCake']}\n",
      "mutex_effects [('NOT_EatenCake', 'EatenCake'), ('NOT_EatenCake', 'NOT_HaveCake'), ('EatenCake', 'NOT_EatenCake'), ('EatenCake', 'HaveCake'), ('HaveCake', 'EatenCake'), ('HaveCake', 'NOT_HaveCake'), ('NOT_HaveCake', 'NOT_EatenCake'), ('NOT_HaveCake', 'HaveCake')]\n",
      "new levels:\n",
      "[ 1 ]\n",
      "\t actions : ['____NOT_EatenCake', 'EatCake', '____HaveCake']\n",
      "\t mutex : [('____NOT_EatenCake', 'EatCake'), ('EatCake', '____NOT_EatenCake'), ('EatCake', '____HaveCake'), ('____HaveCake', 'EatCake')]\n",
      "[ 2 ]\n",
      "\t state : ['NOT_EatenCake', 'EatenCake', 'HaveCake', 'NOT_HaveCake']\n",
      "\t mutex : [('NOT_EatenCake', 'EatenCake'), ('NOT_EatenCake', 'NOT_HaveCake'), ('EatenCake', 'NOT_EatenCake'), ('EatenCake', 'HaveCake'), ('HaveCake', 'EatenCake'), ('HaveCake', 'NOT_HaveCake'), ('NOT_HaveCake', 'NOT_EatenCake'), ('NOT_HaveCake', 'HaveCake')]\n",
      "state ['NOT_EatenCake', 'EatenCake', 'HaveCake', 'NOT_HaveCake']\n",
      "actions {'BakeCake': (['NOT_HaveCake'], ['HaveCake']), 'EatCake': (['HaveCake'], ['NOT_HaveCake', 'EatenCake'])}\n",
      "mutex_actions [('____NOT_EatenCake', 'EatCake'), ('____NOT_EatenCake', '____EatenCake'), ('____NOT_HaveCake', 'BakeCake'), ('____NOT_HaveCake', 'EatCake'), ('____NOT_HaveCake', '____HaveCake'), ('BakeCake', '____NOT_HaveCake'), ('BakeCake', 'EatCake'), ('BakeCake', '____HaveCake'), ('EatCake', '____NOT_EatenCake'), ('EatCake', '____NOT_HaveCake'), ('EatCake', 'BakeCake'), ('EatCake', '____HaveCake'), ('____HaveCake', '____NOT_HaveCake'), ('____HaveCake', 'BakeCake'), ('____HaveCake', 'EatCake'), ('____EatenCake', '____NOT_EatenCake')]\n",
      "effects {'NOT_EatenCake': ['____NOT_EatenCake'], 'EatenCake': ['EatCake', '____EatenCake'], 'HaveCake': ['BakeCake', '____HaveCake'], 'NOT_HaveCake': ['____NOT_HaveCake', 'EatCake']}\n",
      "mutex_effects [('NOT_EatenCake', 'EatenCake'), ('NOT_EatenCake', 'HaveCake'), ('NOT_EatenCake', 'NOT_HaveCake'), ('EatenCake', 'NOT_EatenCake'), ('EatenCake', 'HaveCake'), ('EatenCake', 'NOT_HaveCake'), ('HaveCake', 'NOT_EatenCake'), ('HaveCake', 'EatenCake'), ('HaveCake', 'HaveCake'), ('HaveCake', 'NOT_HaveCake'), ('NOT_HaveCake', 'NOT_EatenCake'), ('NOT_HaveCake', 'EatenCake'), ('NOT_HaveCake', 'HaveCake'), ('NOT_HaveCake', 'NOT_HaveCake')]\n",
      "new levels:\n",
      "[ 3 ]\n",
      "\t actions : ['____NOT_EatenCake', '____NOT_HaveCake', 'BakeCake', 'EatCake', '____HaveCake', '____EatenCake']\n",
      "\t mutex : [('____NOT_EatenCake', 'EatCake'), ('____NOT_EatenCake', '____EatenCake'), ('____NOT_HaveCake', 'BakeCake'), ('____NOT_HaveCake', 'EatCake'), ('____NOT_HaveCake', '____HaveCake'), ('BakeCake', '____NOT_HaveCake'), ('BakeCake', 'EatCake'), ('BakeCake', '____HaveCake'), ('EatCake', '____NOT_EatenCake'), ('EatCake', '____NOT_HaveCake'), ('EatCake', 'BakeCake'), ('EatCake', '____HaveCake'), ('____HaveCake', '____NOT_HaveCake'), ('____HaveCake', 'BakeCake'), ('____HaveCake', 'EatCake'), ('____EatenCake', '____NOT_EatenCake')]\n",
      "[ 4 ]\n",
      "\t state : ['NOT_EatenCake', 'EatenCake', 'HaveCake', 'NOT_HaveCake']\n",
      "\t mutex : [('NOT_EatenCake', 'EatenCake'), ('NOT_EatenCake', 'HaveCake'), ('NOT_EatenCake', 'NOT_HaveCake'), ('EatenCake', 'NOT_EatenCake'), ('EatenCake', 'HaveCake'), ('EatenCake', 'NOT_HaveCake'), ('HaveCake', 'NOT_EatenCake'), ('HaveCake', 'EatenCake'), ('HaveCake', 'HaveCake'), ('HaveCake', 'NOT_HaveCake'), ('NOT_HaveCake', 'NOT_EatenCake'), ('NOT_HaveCake', 'EatenCake'), ('NOT_HaveCake', 'HaveCake'), ('NOT_HaveCake', 'NOT_HaveCake')]\n",
      "state ['NOT_EatenCake', 'EatenCake', 'HaveCake', 'NOT_HaveCake']\n",
      "actions {}\n",
      "mutex_actions [('____NOT_EatenCake', '____EatenCake'), ('____NOT_HaveCake', '____HaveCake'), ('____HaveCake', '____NOT_HaveCake'), ('____EatenCake', '____NOT_EatenCake')]\n",
      "effects {'NOT_EatenCake': ['____NOT_EatenCake'], 'EatenCake': ['____EatenCake'], 'HaveCake': ['____HaveCake'], 'NOT_HaveCake': ['____NOT_HaveCake']}\n",
      "mutex_effects [('NOT_EatenCake', 'EatenCake'), ('EatenCake', 'NOT_EatenCake'), ('HaveCake', 'NOT_HaveCake'), ('NOT_HaveCake', 'HaveCake')]\n",
      "new levels:\n",
      "[ 5 ]\n",
      "\t actions : ['____NOT_EatenCake', '____NOT_HaveCake', '____HaveCake', '____EatenCake']\n",
      "\t mutex : [('____NOT_EatenCake', '____EatenCake'), ('____NOT_HaveCake', '____HaveCake'), ('____HaveCake', '____NOT_HaveCake'), ('____EatenCake', '____NOT_EatenCake')]\n",
      "[ 6 ]\n",
      "\t state : ['NOT_EatenCake', 'EatenCake', 'HaveCake', 'NOT_HaveCake']\n",
      "\t mutex : [('NOT_EatenCake', 'EatenCake'), ('EatenCake', 'NOT_EatenCake'), ('HaveCake', 'NOT_HaveCake'), ('NOT_HaveCake', 'HaveCake')]\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "['____HaveCake',\n",
       " 'EatCake',\n",
       " 'EatCake',\n",
       " 'BakeCake',\n",
       " '____HaveCake',\n",
       " '____EatenCake',\n",
       " '____HaveCake']"
      ]
     },
     "execution_count": 101,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "LIMIT = 10\n",
    "\n",
    "def Plan(Problem):\n",
    "    global LIMIT\n",
    "    graph = []\n",
    "    graph.append({'state': Problem['init'], 'mutex': []})\n",
    "    print(\"first level: \")\n",
    "    print_graph(graph)\n",
    "    cLevel = 0\n",
    "    \n",
    "    while cLevel < LIMIT:\n",
    "        if Maybe_completed(Problem['goal'], graph):\n",
    "            solution = Extract_solution(Problem['goal'], graph, Problem)\n",
    "            if solution:\n",
    "                return solution\n",
    "        (actions_level, state_level) = Extend_graph(Problem['actions'], graph)\n",
    "        graph.append(actions_level)\n",
    "        graph.append(state_level)\n",
    "        print(\"new levels:\")\n",
    "        print_graph(graph[-2:],cLevel + 1)\n",
    "        cLevel = cLevel + 2\n",
    "    return False\n",
    "\n",
    "Plan(Cake)\n",
    "# Plan(FlatTire)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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.4.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 0
}