planning.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# Planning: planning.py; chapters 10-11"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "This notebook describes the [planning.py](https://github.com/aimacode/aima-python/blob/master/planning.py) module, which covers Chapters 10 (Classical Planning) and  11 (Planning and Acting in the Real World) of *[Artificial Intelligence: A Modern Approach](http://aima.cs.berkeley.edu)*. See the [intro notebook](https://github.com/aimacode/aima-python/blob/master/intro.ipynb) for instructions.\n",
    "\n",
    "We'll start by looking at `PDDL` and `Action` data types for defining problems and actions. Then, we will see how to use them by trying to plan a trip from *Sibiu* to *Bucharest* across the familiar map of Romania, from [search.ipynb](https://github.com/aimacode/aima-python/blob/master/search.ipynb). Finally, we will look at the implementation of the GraphPlan algorithm.\n",
    "\n",
    "The first step is to load the code:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from planning import *"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To be able to model a planning problem properly, it is essential to be able to represent an Action. Each action we model requires at least three things:\n",
    "* preconditions that the action must meet\n",
    "* the effects of executing the action\n",
    "* some expression that represents the action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Planning actions have been modelled using the `Action` class. Let's look at the source to see how the internal details of an action are implemented in Python."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%psource Action"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "It is interesting to see the way preconditions and effects are represented here. Instead of just being a list of expressions each, they consist of two lists - `precond_pos` and `precond_neg`. This is to work around the fact that PDDL doesn't allow for negations. Thus, for each precondition, we maintain a seperate list of those preconditions that must hold true, and those whose negations must hold true. Similarly, instead of having a single list of expressions that are the result of executing an action, we have two. The first (`effect_add`) contains all the expressions that will evaluate to true if the action is executed, and the the second (`effect_neg`) contains all those expressions that would be false if the action is executed (ie. their negations would be true).\n",
    "\n",
    "The constructor parameters, however combine the two precondition lists into a single `precond` parameter, and the effect lists into a single `effect` parameter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `PDDL` class is used to represent planning problems in this module. The following attributes are essential to be able to define a problem:\n",
    "* a goal test\n",
    "* an initial state\n",
    "* a set of viable actions that can be executed in the search space of the problem\n",
    "\n",
    "View the source to see how the Python code tries to realise these."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "%psource PDDL"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The `initial_state` attribute is a list of `Expr` expressions that forms the initial knowledge base for the problem. Next, `actions` contains a list of `Action` objects that may be executed in the search space of the problem. Lastly, we pass a `goal_test` function as a parameter - this typically takes a knowledge base as a parameter, and returns whether or not the goal has been reached."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now lets try to define a planning problem using these tools. Since we already know about the map of Romania, lets see if we can plan a trip across a simplified map of Romania.\n",
    "\n",
    "Here is our simplified map definition:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "from utils import *\n",
    "# this imports the required expr so we can create our knowledge base\n",
    "\n",
    "knowledge_base = [\n",
    "    expr(\"Connected(Bucharest,Pitesti)\"),\n",
    "    expr(\"Connected(Pitesti,Rimnicu)\"),\n",
    "    expr(\"Connected(Rimnicu,Sibiu)\"),\n",
    "    expr(\"Connected(Sibiu,Fagaras)\"),\n",
    "    expr(\"Connected(Fagaras,Bucharest)\"),\n",
    "    expr(\"Connected(Pitesti,Craiova)\"),\n",
    "    expr(\"Connected(Craiova,Rimnicu)\")\n",
    "    ]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Let us add some logic propositions to complete our knowledge about travelling around the map. These are the typical symmetry and transitivity properties of connections on a map. We can now be sure that our `knowledge_base` understands what it truly means for two locations to be connected in the sense usually meant by humans when we use the term.\n",
    "\n",
    "Let's also add our starting location - *Sibiu* to the map."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "knowledge_base.extend([\n",
    "     expr(\"Connected(x,y) ==> Connected(y,x)\"),\n",
    "     expr(\"Connected(x,y) & Connected(y,z) ==> Connected(x,z)\"),\n",
    "     expr(\"At(Sibiu)\")\n",
    "    ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now have a complete knowledge base, which can be seen like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[Connected(Bucharest, Pitesti),\n",
       " Connected(Pitesti, Rimnicu),\n",
       " Connected(Rimnicu, Sibiu),\n",
       " Connected(Sibiu, Fagaras),\n",
       " Connected(Fagaras, Bucharest),\n",
       " Connected(Pitesti, Craiova),\n",
       " Connected(Craiova, Rimnicu),\n",
       " (Connected(x, y) ==> Connected(y, x)),\n",
       " ((Connected(x, y) & Connected(y, z)) ==> Connected(x, z)),\n",
       " At(Sibiu)]"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "knowledge_base"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "We now define possible actions to our problem. We know that we can drive between any connected places. But, as is evident from [this](https://en.wikipedia.org/wiki/List_of_airports_in_Romania) list of Romanian airports, we can also fly directly between Sibiu, Bucharest, and Craiova.\n",
    "\n",
    "We can define these flight actions like this:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "#Sibiu to Bucharest\n",
    "precond_pos = [expr('At(Sibiu)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(Bucharest)')]\n",
    "effect_rem = [expr('At(Sibiu)')]\n",
    "fly_s_b = Action(expr('Fly(Sibiu, Bucharest)'), [precond_pos, precond_neg], [effect_add, effect_rem])\n",
    "\n",
    "#Bucharest to Sibiu\n",
    "precond_pos = [expr('At(Bucharest)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(Sibiu)')]\n",
    "effect_rem = [expr('At(Bucharest)')]\n",
    "fly_b_s = Action(expr('Fly(Bucharest, Sibiu)'), [precond_pos, precond_neg], [effect_add, effect_rem])\n",
    "\n",
    "#Sibiu to Craiova\n",
    "precond_pos = [expr('At(Sibiu)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(Craiova)')]\n",
    "effect_rem = [expr('At(Sibiu)')]\n",
    "fly_s_c = Action(expr('Fly(Sibiu, Craiova)'), [precond_pos, precond_neg], [effect_add, effect_rem])\n",
    "\n",
    "#Craiova to Sibiu\n",
    "precond_pos = [expr('At(Craiova)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(Sibiu)')]\n",
    "effect_rem = [expr('At(Craiova)')]\n",
    "fly_c_s = Action(expr('Fly(Craiova, Sibiu)'), [precond_pos, precond_neg], [effect_add, effect_rem])\n",
    "\n",
    "#Bucharest to Craiova\n",
    "precond_pos = [expr('At(Bucharest)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(Craiova)')]\n",
    "effect_rem = [expr('At(Bucharest)')]\n",
    "fly_b_c = Action(expr('Fly(Bucharest, Craiova)'), [precond_pos, precond_neg], [effect_add, effect_rem])\n",
    "\n",
    "#Craiova to Bucharest\n",
    "precond_pos = [expr('At(Craiova)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(Bucharest)')]\n",
    "effect_rem = [expr('At(Craiova)')]\n",
    "fly_c_b = Action(expr('Fly(Craiova, Bucharest)'), [precond_pos, precond_neg], [effect_add, effect_rem])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "And the drive actions like this."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "#Drive\n",
    "precond_pos = [expr('At(x)')]\n",
    "precond_neg = []\n",
    "effect_add = [expr('At(y)')]\n",
    "effect_rem = [expr('At(x)')]\n",
    "drive = Action(expr('Drive(x, y)'), [precond_pos, precond_neg], [effect_add, effect_rem])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Finally, we can define a a function that will tell us when we have reached our destination, Bucharest."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def goal_test(kb):\n",
    "    return kb.ask(expr(\"At(Bucharest)\"))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Thus, with all the components in place, we can define the planning problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": [
    "prob = PDDL(knowledge_base, [fly_s_b, fly_b_s, fly_s_c, fly_c_s, fly_b_c, fly_c_b, drive], goal_test)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": false
   },
   "outputs": [],
   "source": []
  },
  {
   "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
}