ai_uninformed_search.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Uninformed Search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Planning agents**\n",
    "* Agents that plan ahead (a search problem)\n",
    "* Agent is suppose to achieve a goal\n",
    "* Might be different ways to achieve that goal\n",
    "* Planning agent thinks of various ways that the goal can be achieved\n",
    "* The contrasting agent is **Reflex** agent:\n",
    "    * If this do that\n",
    "    * Choose action based on current percept     \n",
    "    * May have memory or a model of the world's current state\n",
    "    * Do not consider the future consequences of their actions, concerned with what IS NOW\n",
    "    * Planning vs Reflex agents: If a bug is going to get into your eye, the reflex agent will close the eye lids due to reflex action - without thinking of the options available and why it is doing what it is doing. A Plannign agent will contemplate about the options available, determine the conequence of taking each action and then will take the one which is more favourable for the agent.\n",
    "    * Asks \"what if\"\n",
    "    * Decisions based on consequences of actions\n",
    "    * Must have a model of how the world evolves ion response to actions\n",
    "    * Must formulate a goal\n",
    "    * Considers how the world would be if ..\n",
    "    *  **Optimal**: If they return a solution, it is the least cost solution\n",
    "    *  **Complete** Finds a solution if exists\n",
    "    * Planning and Replanning\n",
    "        * You might need to do replanning because the option that you choose was expensive\n",
    "    * Rationality is a functions of the actions you take, not the computation involved behind it\n",
    "    * Planning agents do not execute the actions while planning - it rather has a model of the world and it executes the actions in a model. (Reinforcemnet learning actually executes the actions in real world) \n",
    "* Search Problems (to be formalised)\n",
    "* Uninformed Search Methods:\n",
    "    * Depth First\n",
    "    * Breadth First\n",
    "    * Uniform Cost\n",
    "    \n",
    " "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Search problem consists of:\n",
    "* State space\n",
    "* A successor function - what other states you can get to from this state, what actions can get you there, and at what cost\n",
    "* Start state, a goal state\n",
    "\n",
    "A _solution_ is a sequence of actions (a plan) which transforms the start state to the goal state\n",
    "Search problems are models\n",
    "\n",
    "World state (every detail in the world) vs Search state (keeps only the details needed for planning)\n",
    "\n",
    "Problems: Path finding, Eat-all-dots"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "State Graph vs Search Tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "|Algorithm        |Complete|Optimal|Time Complexity|Space complexity|\n",
    "|-----------------|--------|-------|---------------|----------------|\n",
    "|DFS              |Yes(*)  | No    |O(b^m)         |O(bm)           |\n",
    "|BFS              |Yes     | Yes(*) |O(b^s)         |O(b^s)          |\n",
    "|Uniform Cost|Yes|Yes||||\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "Search characteristics:\n",
    "* Single Agent\n",
    "* Deterministic Actions\n",
    "* Fully observed state\n",
    "* Discrete state space\n",
    "\n",
    "Two types:\n",
    "* Planning: The path to the goal is important. Paths have costs, depths. Heuristics give problem specific guidance.\n",
    "* Identification: assignments to variables. The goal itself is important, not the path. All paths same depth. CSP are specialized for identification problem."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "lecture notes are <a href=\"objects/SP14 CS188 Lecture 2 -- Uninformed Search.pdf\">here</a>\n"
   ]
  }
 ],
 "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.5"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}