{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Copy of FINAL Template_for CIS521_midterm notes.ipynb",
      "provenance": [],
      "collapsed_sections": []
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    },
    "language_info": {
      "name": "python"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "brNDGX-kvzds"
      },
      "source": [
        "# Template for Notes for CIS 521 Midterm 1\n",
        "\n",
        "The midterm exam for CIS 521 will be **open notes**. No other matierals are allowed for the exam - you may not use the textbook, the internet, a Python envionement, or communicate with anyone during the exam. \n",
        "\n",
        "This python notebook is where you should save all of your notes.  It provides a structured template that allows you to add summaries for each of the textbook sections that are part of the required reading, plus room for lecture notes and definitions.\n",
        "\n",
        "Your summaries must be written in your own words.  Do not copy and paste from the textbook.  Do not share your notes with classmates, or copy any of your classmates' notes.  "
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "aPtM8g7R0Pds"
      },
      "source": [
        "# Instructions\n",
        "\n",
        "1. Make a copy of this Google Colab file. From the colab menu, pick **File > Save a copy in Drive**.  That will save a copy of this notebook in your Google drive.\n",
        "2. Go through each section of the notebook, and fill in all the summaries for each chapter and its corresponding sections.  Be sure to save your work frequently!\n",
        "3. Read the notes below about how you can format your summaries.\n",
        "4. In addition to these notes, you are allowed 1 page (both sides) for figures or handwritten notes.\n",
        "5. Submit your version of this notebook to Gradescope before you start the exam.\n",
        "6. If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print: \n",
        "* Run the last cell of this notebook\n",
        "* Click the \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n",
        "\n",
        "## Formatting Notes\n",
        "\n",
        "1. The max length for each section's summary is 500 words / 3000 characters.\n",
        "2. You can also write a 2000 word summary of the lectures for each module.\n",
        "3. You may also write definitions of concepts for each module.  The definitions should be written in your own words (not copy and pasted), and they should be no more than 20 words long for each concept. \n",
        "2. You can use Markdown formatting for your summaries. \n",
        "3. You can use Latex formatting for equations. Put two dollar signs before and after your equation like this: \n",
        "$$ \\epsilon = \\frac{1}{mc^2} $$\n",
        "4. When you write python code or psuedocode algorithms, you should surround it with triple backticks like this:\n",
        "```\n",
        "def function():\n",
        "      print('hello world')\n",
        "```\n",
        "5. Write \\ whenever you want to keep writing on the next line without a newline being inserted."
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "cw5IpDLCZa4W"
      },
      "source": [
        "## Example summary\n",
        "\n",
        "This is a sample summary of [Section 2.1.1](https://web.stanford.edu/~jurafsky/slp3/2.pdf ) of Jurfasky and Martin's Speech and Language Processing's book\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lzaavW96tcxM",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "e72aca1c-1ea6-4839-ac5c-b77c09858850"
      },
      "source": [
        "chapter_2_1_example = \"\"\"\n",
        "Regular expressions are an algebraic notation for characterizing \\\n",
        "a set of strings that are useful for searching for a pattern or through a corpus.\\\n",
        "Only the first matching result will be shown. The search string is case sensitive, \\\n",
        "but it can consist of a single character or a sequence of characters. \\\n",
        "While square braces specify a disjunction of characters, the dash can more easily look \\\n",
        "for characters over a range. The caret specifies the non-existence of a character. \\\n",
        "Additionally, the (?) is used to for flexibility on a single character, meaning \\\n",
        "\"the preceding character or nothing\". More importantly, the Kleene star means zero or \\\n",
        "more occurrences of the immediately previous character or regular expression in square braces.\\\n",
        "...\n",
        "\"\"\"\n",
        "\n",
        "length = len(chapter_2_1_example.split(\" \"))\n",
        "print(\"The example summary is {len} words long, so you could write an additional \\\n",
        "{remaining} words.\".format(len=length, remaining=(500-length)))"
      ],
      "execution_count": 23,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The example summary is 116 words long, so you could write an additional 384 words.\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "s3Uk9gQTevcj"
      },
      "source": [
        "## Example summary length\n",
        "\n",
        "The maximum summary length for each section is 500 words / 3000 characters.  Hopefully you'll find that to be quite generous. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "8DvZ57A-djo1",
        "colab": {
          "base_uri": "https://localhost:8080/"
        },
        "outputId": "8fb0b7f8-4193-4838-e8d4-ddec743c533b"
      },
      "source": [
        "# This is an example of a 500 word placeholder\n",
        "placeholder = \"\"\"ultrices vitae auctor eu augue ut lectus arcu bibendum at varius \\\n",
        " vel pharetra vel turpis nunc eget lorem dolor sed viverra ipsum nunc aliquet \\\n",
        " bibendum enim facilisis gravida neque convallis a cras semper auctor neque vitae \\\n",
        " tempus quam pellentesque nec nam aliquam sem et tortor consequat id porta nibh \\\n",
        " venenatis cras sed felis eget velit aliquet sagittis id consectetur purus ut \\\n",
        " faucibus pulvinar elementum integer enim neque volutpat ac tincidunt vitae semper \\ \n",
        " quis lectus nulla at volutpat diam ut venenatis tellus in metus vulputate eu \\\n",
        " scelerisque felis imperdiet proin fermentum leo vel orci porta non pulvinar neque \\ \n",
        " laoreet suspendisse interdum consectetur libero id faucibus nisl tincidunt eget \\\n",
        " nullam non nisi est sit amet facilisis magna etiam tempor orci eu lobortis \\\n",
        " elementum nibh tellus molestie nunc non blandit massa enim nec dui nunc mattis \\\n",
        " enim ut tellus elementum sagittis vitae et leo duis ut diam quam nulla porttitor \\\n",
        " massa id neque aliquam vestibulum morbi blandit cursus risus at ultrices mi tempus \\\n",
        " imperdiet nulla malesuada pellentesque elit eget gravida cum sociis natoque \\\n",
        " penatibus et magnis dis parturient montes nascetur ridiculus mus mauris vitae \\\n",
        " ultricies leo integer malesuada nunc vel risus commodo viverra maecenas accumsan \\\n",
        " lacus vel facilisis volutpat est velit egestas dui id ornare arcu odio ut sem nulla \\\n",
        " pharetra diam sit amet nisl suscipit adipiscing bibendum est ultricies integer \\\n",
        " quis auctor elit sed vulputate mi sit amet mauris commodo quis imperdiet massa \\\n",
        " tincidunt nunc pulvinar sapien et ligula ullamcorper malesuada proin libero nunc \\\n",
        " consequat interdum varius sit amet mattis vulputate enim nulla aliquet porttitor \\\n",
        " lacus luctus accumsan tortor posuere ac ut consequat semper viverra nam libero \\\n",
        " justo laoreet sit amet cursus sit amet dictum sit amet justo donec enim diam \\\n",
        " vulputate ut pharetra sit amet aliquam id diam maecenas ultricies mi eget mauris \\\n",
        " pharetra et ultrices neque ornare aenean euismod elementum nisi quis eleifend quam \\\n",
        " adipiscing vitae proin sagittis nisl rhoncus mattis rhoncus urna neque viverra justo \\\n",
        " nec ultrices dui sapien eget mi proin sed libero enim sed faucibus turpis in \\\n",
        " eu mi bibendum neque egestas congue quisque egestas diam in arcu cursus euismod \\\n",
        " quis viverra nibh cras pulvinar mattis nunc sed blandit libero volutpat sed cras \\\n",
        " ornare arcu dui vivamus arcu felis bibendum ut tristique et egestas quis ipsum \\\n",
        " suspendisse ultrices gravida dictum fusce ut placerat orci nulla pellentesque \\\n",
        " dignissim enim sit amet venenatis urna cursus eget nunc scelerisque viverra mauris \\\n",
        " in aliquam sem fringilla ut morbi tincidunt augue interdum velit euismod in \\\n",
        " pellentesque massa placerat duis ultricies lacus sed turpis tincidunt id aliquet \\\n",
        " risus feugiat in ante metus dictum at tempor commodo ullamcorper a lacus vestibulum \\\n",
        " sed arcu non odio euismod lacinia at quis risus sed vulputate odio ut enim blandit \\\n",
        " volutpat maecenas volutpat blandit aliquam etiam erat velit scelerisque in \\\n",
        " dictum non consectetur a erat nam at lectus urna\"\"\"\n",
        "\n",
        "print(\"The length in words is\", len(placeholder.split(' ')))\n",
        "print(\"The length in characters is\", len(placeholder))"
      ],
      "execution_count": 24,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 25,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "GZZXyrV-xuAp"
      },
      "source": [
        "# Module 1 - Intro to AI"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Y2NfE1CKxzS-"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, Chapter 1 “Introduction”, Section 1.1 “What is AI”\n",
        "\n",
        "chapter1_1 = \"\"\"\n",
        "Two ways to define AI: intelligent behavior, human performance. \\\\\n",
        "Computers use (1) NLP to communicate human language, (2) knowledge representation to store what it knows/hears, \\\n",
        "(3) automated reasoning to answer questions and detect and extrapolate patterns\n",
        "\n",
        "Turing Test to tell if computer is intelligent - try to tell if responses are human.\n",
        "\n",
        "Total Turing Test requires a computer to have computer vision, speech recognition, and actuators to move.\n",
        "\n",
        "Human thought is learned in 3 ways: (1) introspection, (2) psychological, and (3) brain imaging\n",
        "\n",
        "*Limited Rationality* - acting appropriately when there is not enough compute resources.\n",
        "\n",
        "If we cannot get a machine to complete our objective, reformulate the problem. (Value alignment problem - provably beneficial to humans).\n",
        "\"\"\" \n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 27 “Philosophical Foundations”, Sections 27.1 “The Limits of AI” and 27.2 “Can Machines Really Think?”\n",
        "chapter27_1 = \"\"\"\n",
        "Good Old-Fashioned AI (GOFAI) - corresponds to the siplest logical agent design\n",
        "\n",
        "Qualification Problem - the difficulty to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules\n",
        "\n",
        "Gödel sentence *G(F)*:\n",
        " + *G(F)* is a sentence of *F*, but cannot be proved within *F*\n",
        " + if *F* is consistent, then *G(F)* is true \\\\\n",
        "\"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "An agent's choice of action at any given instant can depend on its built-in knowledge \\\n",
        "and on the entire percept sequence observed to date, but not on anything it hasn't perceived.\n",
        "\n",
        "*Agent Function* - describes an agent's behavior and maps any percept sequence to an action. \\\\\n",
        "*Agent Program* - How an agent program is implemented in an artificial agent.\n",
        "\"\"\"\n",
        "chapter2_2 = \"\"\"\n",
        "AI are created to help humans, so helpfulness and performance are evaluated. \n",
        "\n",
        "Rationality depends on: (1) The performance measure that defines criterion of success, \\\n",
        "(2) The agent's prior knowledge of the environment, (3) The actions that the agent can perform, \\\n",
        "and (4) The agent's percept sequence to date.\n",
        "\n",
        "*Rational Agent* - For each possible percept sequence, a rational agent should select an action \\\n",
        "that is expected to maximize its performance measure.\n",
        "\n",
        "*Omniscient Agent* - knows the actual outcome of its actions and can act accordingly \\\\\n",
        "\"\"\"\n",
        "chapter2_3 = \"\"\"\n",
        "**PEAS** (Performance, Environment, Acuators, Sensors) are part of the task environment.\n",
        "Ex: Medical diagnosis (P) healthy patients, reduced costs | (E) patients, hospital staff | \n",
        "(A) display of questions, tests, diagnoses, treatments | (S) entry of symptoms or observations\n",
        "\n",
        "Multiagent can be: *competitive* (two agents against another - chess) or *cooperative* \\\n",
        "(all players benefit from other players not failing - autonomous car)\n",
        "\n",
        "*Deterministic* - if the next state of the environment is completely determined by\n",
        "the current state and the action executed by the agent(s) \\\\\n",
        "*Stochastic* (non-deterministic) - actions are randomly determined\n",
        "\n",
        "*Episodic* - the agent's experience is divided into atomic episodes, where the agent receives\n",
        "a percept and then performs a single action.\\\\\n",
        "*Sequential* - A current decision could affect all future decisions (chess).\n",
        "\n",
        "*Static* vs *Dynamic* - environment cannot or can change while the agent is deliberating.\n",
        "A *semidynamic* environment doesn't change, but the agent's performance score might (Chess on a clock).\n",
        "\n",
        "*Discrete* vs. *Continuous* - chess discrete, taxi driving continuous\n",
        "\"\"\"\n",
        "chapter2_4 = \"\"\"\n",
        "agent = architecture + program \\\\\n",
        "1. Simple reflex agent - select actions on the basis of current percept, ignoring the rest of\n",
        "percept history \\\n",
        "condition-action rule - some processing is done on the visual input to establish the condition\n",
        " (a smart car knows to brake if the brake lights of the car in front go on) \\\\\n",
        "2. Model based reflex agent - the gaent should maintain some sort of internal state that depends on the percept\n",
        "history and thereby reflects at least some of the unobserved aspects of the current state.\n",
        "Handles partial observability. \\\\\n",
        "Transition model - knowledge of how the world works for intelligent agents \\\\\n",
        "Sensor model - information about how the state of the world is reflected in the agent's percepts \\\\\n",
        "3. Goal based agents - the agent needs some sort of goal information that describes situations\n",
        "that are desirable and a current state description. Both search and planning is used to achieve the agent's goal \\\\\n",
        "4. Utility based agents - a more general performance measure should allow a comparison of different world\n",
        "states according to exactly how 'happy' they would make the agent. \n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\n",
        "*Performance Measures* - design based on what you want to be achieved rather than how you think the agent should behave.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions of concepts from Module 1.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module1_definitions = {\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"The content an agent's sensors are perceiving\",\n",
        "\"percept sequence\": \"An agent's complete history of everything it has ever perceived\",\n",
        "\"introspection\" : \"trying to catch our own thoughts as they go by\",\n",
        "\"psychological experiements\" : \"observing a person in action\",\n",
        "\"brain imaging\" : \"observing the brain in action\",\n",
        "\"weak ai\": \"machines could act as if they were intelligent\",\n",
        "\"strong ai\" : \"machines that act as if they were intelligent, actually consciously think\",\n",
        "\"rational agent\": \"an agent that does the right thing\",\n",
        "\"consequentialism\" :\"evaluating an agent's behavior by its consequences\",\n",
        "\"fully observable\" : \"sensors have access to complete state of environment - perfect information\",\n",
        "\"partially observable\" : \"some sensors are blocked by noise or inaccurate sensors\",\n",
        "\"Expected utility\" : \"The utility the agent exptes to derive, on average, given the probabilities\",\n",
        "\n",
        "}\n",
        "\n"
      ],
      "execution_count": 26,
      "outputs": []
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "elCCgY64spuq"
      },
      "source": [
        "## Preview of your notes for Module 1\n",
        "\n",
        "Here's a preview of your how your notes will be displayed.  At the end of this Python notebook, we'll aggregate your notes for all modules together into a single display.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "gYYeNcdM_maE",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "9cab43a1-2a50-44ce-b788-c2a4b2b1dbdb"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "from IPython.display import display, Markdown, Latex\n",
        "\n",
        "module1_sections = [\n",
        "  (\"AIMA Chapter 1.1 What is AI?\", chapter1_1),\n",
        "  (\"AIMA Chapter 27.1 The Limits of AI\", chapter27_1),\n",
        "  (\"AIMA Chapter 27.1 Can Machines Really Think?\", chapter27_2),\n",
        "  (\"AIMA 2.1 Agents and Environments\", chapter2_1),\n",
        "  (\"AIMA 2.2 Good Behavior: The Concept of Rationality\", chapter2_2),\n",
        "  (\"AIMA 2.3 The Nature of Environments\", chapter2_3),\n",
        "  (\"AIMA 2.4 The Structure of Agents\", chapter2_4),\n",
        "  (\"Module 1 Lecture Notes\", module1_lecture_notes),\n",
        "]\n",
        "\n",
        "\n",
        "def length_check(sections):\n",
        "  warnings = \"\"\n",
        "  for section, summary in sections:\n",
        "    max_word_length = 500\n",
        "    max_character_length = 3000\n",
        "    if \"lecture\" in section.lower():\n",
        "      # It's OK to do longer summaries of the lectures\n",
        "      max_word_length = 2000\n",
        "      max_character_length = 12000  \n",
        "    if (len(summary) > max_character_length or len(summary.split(' ')) > max_word_length):\n",
        "      warnings += \"WARNING: Your summary of '{section}' is too long!\\n\".format(section=section)\n",
        "  return warnings\n",
        "\n",
        "def length_check_definitions(definitions):\n",
        "  warnings = \"\"\n",
        "  for concept, definition in definitions.items():\n",
        "    if(len(definition.split(' ')) > 20):\n",
        "      warnings += \"WARNING: Your definition of '{concept}' is too long!\\n\".format(concept=concept)\n",
        "  return warnings\n",
        "\n",
        "\n",
        "def format_module(module_num, title, sections, definitions, show_placeholder=False):\n",
        "  markdown = \"\"\n",
        "\n",
        "  # Check summary lengths\n",
        "  warnings = length_check(sections)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  # Check definition lengths\n",
        "  warnings = length_check_definitions(definitions)\n",
        "  if warnings != \"\":\n",
        "    markdown += \"## \" + warnings\n",
        "\n",
        "  markdown += \"# Module {num}: {title}\\n\".format(num=module_num, title=title)\n",
        "\n",
        "\n",
        "  for section, summary in sections:\n",
        "    if show_placeholder and summary == \" Your summary here \":\n",
        "      summary = placeholder\n",
        "    markdown += \"## {section}\\n{summary}\\n\\n\".format(section=section, summary=summary)\n",
        "  \n",
        "  markdown += \"## Module {num} Definitions\\n\".format(num=module_num)\n",
        "  for concept, definition in definitions.items():\n",
        "    markdown += \"* **{concept}** - {definition}\\n\".format(concept=concept.capitalize(), definition=definition)\n",
        "  return markdown\n",
        "\n",
        "\n",
        "module1_markdown = format_module(1, \"Rational Agents and Task Environments\", module1_sections, module1_definitions)\n",
        "display(Markdown(module1_markdown))"
      ],
      "execution_count": 27,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nTwo ways to define AI: intelligent behavior, human performance. \\\nComputers use (1) NLP to communicate human language, (2) knowledge representation to store what it knows/hears, (3) automated reasoning to answer questions and detect and extrapolate patterns\n\nTuring Test to tell if computer is intelligent - try to tell if responses are human.\n\nTotal Turing Test requires a computer to have computer vision, speech recognition, and actuators to move.\n\nHuman thought is learned in 3 ways: (1) introspection, (2) psychological, and (3) brain imaging\n\n*Limited Rationality* - acting appropriately when there is not enough compute resources.\n\nIf we cannot get a machine to complete our objective, reformulate the problem. (Value alignment problem - provably beneficial to humans).\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nGood Old-Fashioned AI (GOFAI) - corresponds to the siplest logical agent design\n\nQualification Problem - the difficulty to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules\n\nGödel sentence *G(F)*:\n + *G(F)* is a sentence of *F*, but cannot be proved within *F*\n + if *F* is consistent, then *G(F)* is true \\\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n\nAn agent's choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived.\n\n*Agent Function* - describes an agent's behavior and maps any percept sequence to an action. \\\n*Agent Program* - How an agent program is implemented in an artificial agent.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nAI are created to help humans, so helpfulness and performance are evaluated. \n\nRationality depends on: (1) The performance measure that defines criterion of success, (2) The agent's prior knowledge of the environment, (3) The actions that the agent can perform, and (4) The agent's percept sequence to date.\n\n*Rational Agent* - For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure.\n\n*Omniscient Agent* - knows the actual outcome of its actions and can act accordingly \\\n\n\n## AIMA 2.3 The Nature of Environments\n\n**PEAS** (Performance, Environment, Acuators, Sensors) are part of the task environment.\nEx: Medical diagnosis (P) healthy patients, reduced costs | (E) patients, hospital staff | \n(A) display of questions, tests, diagnoses, treatments | (S) entry of symptoms or observations\n\nMultiagent can be: *competitive* (two agents against another - chess) or *cooperative* (all players benefit from other players not failing - autonomous car)\n\n*Deterministic* - if the next state of the environment is completely determined by\nthe current state and the action executed by the agent(s) \\\n*Stochastic* (non-deterministic) - actions are randomly determined\n\n*Episodic* - the agent's experience is divided into atomic episodes, where the agent receives\na percept and then performs a single action.\\\n*Sequential* - A current decision could affect all future decisions (chess).\n\n*Static* vs *Dynamic* - environment cannot or can change while the agent is deliberating.\nA *semidynamic* environment doesn't change, but the agent's performance score might (Chess on a clock).\n\n*Discrete* vs. *Continuous* - chess discrete, taxi driving continuous\n\n\n## AIMA 2.4 The Structure of Agents\n\nagent = architecture + program \\\n1. Simple reflex agent - select actions on the basis of current percept, ignoring the rest of\npercept history condition-action rule - some processing is done on the visual input to establish the condition\n (a smart car knows to brake if the brake lights of the car in front go on) \\\n2. Model based reflex agent - the gaent should maintain some sort of internal state that depends on the percept\nhistory and thereby reflects at least some of the unobserved aspects of the current state.\nHandles partial observability. \\\nTransition model - knowledge of how the world works for intelligent agents \\\nSensor model - information about how the state of the world is reflected in the agent's percepts \\\n3. Goal based agents - the agent needs some sort of goal information that describes situations\nthat are desirable and a current state description. Both search and planning is used to achieve the agent's goal \\\n4. Utility based agents - a more general performance measure should allow a comparison of different world\nstates according to exactly how 'happy' they would make the agent. \n\n\n## Module 1 Lecture Notes\n\n*Performance Measures* - design based on what you want to be achieved rather than how you think the agent should behave.\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - The content an agent's sensors are perceiving\n* **Percept sequence** - An agent's complete history of everything it has ever perceived\n* **Introspection** - trying to catch our own thoughts as they go by\n* **Psychological experiements** - observing a person in action\n* **Brain imaging** - observing the brain in action\n* **Weak ai** - machines could act as if they were intelligent\n* **Strong ai** - machines that act as if they were intelligent, actually consciously think\n* **Rational agent** - an agent that does the right thing\n* **Consequentialism** - evaluating an agent's behavior by its consequences\n* **Fully observable** - sensors have access to complete state of environment - perfect information\n* **Partially observable** - some sensors are blocked by noise or inaccurate sensors\n* **Expected utility** - The utility the agent exptes to derive, on average, given the probabilities\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "9xRbdqDox2zD"
      },
      "source": [
        "#Module 2 - Python"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "DpBvu7EMx7sy"
      },
      "source": [
        "# No readings for this module.  Instead you can summarize the lecture instead.\n",
        "\n",
        "# Lecture notes \n",
        "module2_lecture_notes = \"\"\"\n",
        "Good features of Python \\\\\n",
        "Fast development:\\\\\n",
        "-Concise, intuitive syntax that is whitespace delimited\\\\\n",
        "-Garbage collected\\\\\n",
        "Portable:\\\\\n",
        "-Programs run on major platforms without change\\\\\n",
        "Various built-in types:\\\\\n",
        "-lists, dictionaries, sets: useful for AI\\\\\n",
        "Large collection of support libraries:\\\\\n",
        "-NumPy for Matlab like programming\\\\\n",
        "-Pandas for data analysis\\\\\n",
        "-Sklearn for machine learning\\\\\n",
        "-Pytorch and TensorFlow for deep learning\n",
        " \n",
        "**Objects and Types**\n",
        "All data treated as objects:\n",
        "An object is deleted (by garbage collection) once unreachable.\n",
        " \n",
        "**Strong Typing:**\n",
        "Every object has a fixed type, interpreter doesn’t allow things incompatible with\n",
        "that type (eg. “foo” + 2) \\\\\n",
        "type(object) \\\\\n",
        "isinstance(object, type)\n",
        " \n",
        "Examples of Types: \\\\\n",
        "int, float, \n",
        "str, tuple, dict, list, \n",
        "bool: True, False, \n",
        "None, generator, function\n",
        " \n",
        "Python has dynamic typing: Variables come into existence when first assigned.\n",
        "Strings are immutable, lists are mutable\n",
        " \n",
        "**Sequence Types**\n",
        "Tuple:\\\\\n",
        "-A simple immutable ordered sequence of items \\\\\n",
        "-Immutable: a tuple cannot be modified once created\\\\\n",
        "-Items can be of mixed types, including collection types\n",
        " \n",
        "Strings:\\\\\n",
        "-Immutable\\\\\n",
        "-Regular strings are Unicode and use 2-byte characters (Regular strings in\n",
        "Python 2 use 8-bit characters)\\\\\n",
        "List:\\\\\n",
        "-Mutable ordered sequence of items of mixed types\n",
        " \n",
        " \n",
        "Python allows multiple return values.\n",
        "It does not have function overloading.\n",
        "Not all arguments need to be called for the function to be called.\n",
        " \n",
        "Functions are first class\\\\\n",
        "**First class object:**\\\\\n",
        "-An entity that can be dynamically created, destroyed, passed to a function,\n",
        "returned as a value, and have all the rights as other variables in the\n",
        "programming language have\\\\\n",
        "\n",
        "Functions are “first-class citizens”:\\\\\n",
        "-Pass functions as arguments to other functions\\\\\n",
        "-Return functions as the values from other functions\\\\\n",
        "-Assign functions to variables or store them in data structures\\\\\n",
        "Higher order functions: take functions as input\\\\\n",
        " \n",
        "**Subclasses:**\\\\\n",
        "-no extend keyword\\\\\n",
        "-multiple inheritance is allowed\n",
        " \n",
        "Methods that behave like built ins:\\\\\n",
        "__init__: The constructor for the class.\\\\\n",
        "__len__ : Define how len( obj ) works.\\\\\n",
        "__copy__: Define how to copy a class.\\\\\n",
        "__cmp__ : Define how == works for class.\\\\\n",
        "__add__ : Define how + works for class\\\\\n",
        "__neg__ : Define how unary negation works for class\\\\\n",
        " \n",
        "**Iterator Objects:**//\n",
        "Iterable objects can be used in a for loop because they have an __iter__ magic\n",
        "method, which converts them to iterator objects\\\\\n",
        "- no hasNext in python\n",
        " \n",
        "**Generators:**\\\\\n",
        "-Generators are iterators (with __next()__ method)\\\\\n",
        "-Creating Generators: yield\n",
        " \n",
        "YIELD: Each time we call the __next__ method of the generator, the method runs until it\n",
        "encounters a yield statement, and then it stops and returns the value that was yielded.\n",
        "Next time, it resumes where it left off\n",
        " \n",
        "Benefits of generators:\\\\\n",
        "-Less code than writing a standard iterator\\\\\n",
        "-Maintains local state automatically\\\\\n",
        "-Values are computed one at a time, as they’re needed\\\\\n",
        "-Avoids storing the entire sequence in memory\\\\\n",
        "-Good for aggregating (summing, counting) items. One pass.\\\\\n",
        "-Crucial for infinite sequences\\\\\n",
        "-Bad if you need to inspect the individual values\\\\\n",
        "\"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"ability to change\",\n",
        "\"method\" : \"when a functioni s defined inside a class\"\n",
        "}"
      ],
      "execution_count": 28,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "48033454-afc7-4029-b3fb-4e6ffea97d02"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "\n",
        "module2_sections = [\n",
        "  (\"Module 2 Lecture Notes\", module2_lecture_notes),\n",
        "]\n",
        "\n",
        "module2_markdown = format_module(2, \"Python\", module2_sections, module2_definitions)\n",
        "display(Markdown(module2_markdown))"
      ],
      "execution_count": 29,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n\nGood features of Python \\\nFast development:\\\n-Concise, intuitive syntax that is whitespace delimited\\\n-Garbage collected\\\nPortable:\\\n-Programs run on major platforms without change\\\nVarious built-in types:\\\n-lists, dictionaries, sets: useful for AI\\\nLarge collection of support libraries:\\\n-NumPy for Matlab like programming\\\n-Pandas for data analysis\\\n-Sklearn for machine learning\\\n-Pytorch and TensorFlow for deep learning\n \n**Objects and Types**\nAll data treated as objects:\nAn object is deleted (by garbage collection) once unreachable.\n \n**Strong Typing:**\nEvery object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2) \\\ntype(object) \\\nisinstance(object, type)\n \nExamples of Types: \\\nint, float, \nstr, tuple, dict, list, \nbool: True, False, \nNone, generator, function\n \nPython has dynamic typing: Variables come into existence when first assigned.\nStrings are immutable, lists are mutable\n \n**Sequence Types**\nTuple:\\\n-A simple immutable ordered sequence of items \\\n-Immutable: a tuple cannot be modified once created\\\n-Items can be of mixed types, including collection types\n \nStrings:\\\n-Immutable\\\n-Regular strings are Unicode and use 2-byte characters (Regular strings in\nPython 2 use 8-bit characters)\\\nList:\\\n-Mutable ordered sequence of items of mixed types\n \n \nPython allows multiple return values.\nIt does not have function overloading.\nNot all arguments need to be called for the function to be called.\n \nFunctions are first class\\\n**First class object:**\\\n-An entity that can be dynamically created, destroyed, passed to a function,\nreturned as a value, and have all the rights as other variables in the\nprogramming language have\\\n\nFunctions are “first-class citizens”:\\\n-Pass functions as arguments to other functions\\\n-Return functions as the values from other functions\\\n-Assign functions to variables or store them in data structures\\\nHigher order functions: take functions as input\\\n \n**Subclasses:**\\\n-no extend keyword\\\n-multiple inheritance is allowed\n \nMethods that behave like built ins:\\\n__init__: The constructor for the class.\\\n__len__ : Define how len( obj ) works.\\\n__copy__: Define how to copy a class.\\\n__cmp__ : Define how == works for class.\\\n__add__ : Define how + works for class\\\n__neg__ : Define how unary negation works for class\\\n \n**Iterator Objects:**//\nIterable objects can be used in a for loop because they have an __iter__ magic\nmethod, which converts them to iterator objects\\\n- no hasNext in python\n \n**Generators:**\\\n-Generators are iterators (with __next()__ method)\\\n-Creating Generators: yield\n \nYIELD: Each time we call the __next__ method of the generator, the method runs until it\nencounters a yield statement, and then it stops and returns the value that was yielded.\nNext time, it resumes where it left off\n \nBenefits of generators:\\\n-Less code than writing a standard iterator\\\n-Maintains local state automatically\\\n-Values are computed one at a time, as they’re needed\\\n-Avoids storing the entire sequence in memory\\\n-Good for aggregating (summing, counting) items. One pass.\\\n-Crucial for infinite sequences\\\n-Bad if you need to inspect the individual values\\\n\n\n## Module 2 Definitions\n* **Mutability** - ability to change\n* **Method** - when a functioni s defined inside a class\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "46MQLR-Gx8dZ"
      },
      "source": [
        "#Module 3 - Search Problems"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "BN0b1eVYx-nd"
      },
      "source": [
        "# Russell and Norvig, AIMA 4th Edition, AIMA Chapter 3 “Problem Solving by Search” (3.1-3.4)\n",
        "chapter3_1 = \"\"\" \n",
        "A search problem includes:\n",
        "(1) a state space\n",
        "(2) initial state\n",
        "(3) goal states\n",
        "(4) set of actions\n",
        "(5) transition model\n",
        "(6) action cost function.\n",
        "\n",
        "The **state space** can be represented as a graph where the vertices are states and the directed edges are the actions.\n",
        "\"\"\"\n",
        "chapter3_2 = \"\"\"\n",
        "**Sliding-Tile Puzzle Example**\n",
        "\\\\\n",
        "States : all the locations of the tiles \\\\\n",
        "Initial State : any state \\\\\n",
        "Actions : tile or blank space moving *left, right, up, or down* \\\\\n",
        "Transition Model : result of taking an action (when tile is moved) \\\\\n",
        "Goal State: when the tiles are in order \\\\\n",
        "Action Cost : cost of moving a tile > all 1 in this puzzle \\\\\n",
        "\"\"\"\n",
        "chapter3_3 = \"\"\"\n",
        "Nodes of a search tree correspond to states and edges are actions. The child or successor node \\\n",
        "follows a parent node and the **frontier** represents the set of unexpanded child nodes.\n",
        "\n",
        "***Best-First Search***\n",
        "Returns some solution with minimum evaluation function=, *f(n)*. \n",
        "Each child node is added to the frontier if it has not been reached before or adjusted if it is reached\n",
        "with lower path cost. \n",
        "\n",
        "There are three kinds of queues: **priority**, **FIFO**, **LIFO**\n",
        "\n",
        "**Graph** search will check for redundant paths, while **tree** search will not.\n",
        "\n",
        "The algorithm's performance can be evaluated by completeness, cost optimality, time complexity, and space complexity.\n",
        "\n",
        "Complexity can be measured in terms of *d*, the **depth** or number of actions in the optimal solution, or\n",
        "*b*, the **branching factor** or number of successors that need to be considered.\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "***Breadth-first Search***\n",
        "All actions have the same cost and all successors of the current frontier are expanded in order. Best if there are possibly infinite paths and some solutions have short paths.\n",
        "This uses the **FIFO** queue and the set of *reached* nodes is a set of states rather than a mapping of states to nodes.\n",
        "\n",
        "*Psuedo-Code:*\n",
        "initialize NODE \\\\\n",
        "if NODE is GOAL, return \\\\\n",
        "intialize FRONTIER and REACHED (FIFO queue [list] and [set]) \\\\\n",
        "while FRONTIER not empty: pop, check if GOAL or add to REACHED and FRONTIER \\\\\n",
        "return *failure* if no solution\n",
        "\n",
        "**Time Complexity** : *O(b^d)* \\\\\n",
        "**Space Complexity** : *O(b^d)* since all nodes remain in memory \\\\\n",
        "Complete, but only cost-optimal when all actions have the same cost\n",
        "\n",
        "***Dijkstra's (Uniform-cost Search)***\n",
        "BFS in uniform depth, Dijkstra's in uniform path-cost.\n",
        "\n",
        "**Time and Space Complexity** : *O(b^(1+[C/$\\epsilon$]))$ which can potentially be more than BFS. \\\\\n",
        "Uniform-cost search is complete and cost-optimal\n",
        "\n",
        "***Depth-first Search***\n",
        "Expands to deepest node in the frontier first. Best for space restricted and many possible solutions with long paths.\n",
        "\n",
        "**Time Complexity** : *O(b^m)*\n",
        "**Space Complexity** : *O(bm)* where *m* is the max depth\n",
        "\n",
        "Not complete (unless m is bounded (limited depth)) or cost-optimal\n",
        "\n",
        "***Depth-limited Search***\n",
        "Cut off DFS at limit *l* and treat all nodes at limit was if they had no successors. Same complexity as DFS with d = l.\\\\\n",
        "If l < d, then incomplete; if l > d, then not optimal\n",
        "\n",
        "***Iterative Deepening Search***\n",
        "for depth = 0 to $\\infty$, do depth-limited search.\n",
        "*O(bd)* if there is a solution or *O(bm)* when there is not. Preferred when search state is larger than memory (can't use BFS) and depth of solution is unknown (can't use DFS).\n",
        "\n",
        "***Bidirectional Search***\n",
        "Searches from initial state and backwards from goal state(s). Has frontier (priority queue) and reached states for forward and backward search.\n",
        "\n",
        "Complete and optimal with *O(b^(d/2))* Time and Space complexity\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\"\n",
        "BFS: Complete | Optimal \\\\\n",
        "Uniform: Complete | Optimal \\\\\n",
        "DFS: Not Complete | Not Optimal \\\\\n",
        "Depth-limited: Not Complete | Not Optimal \\\\\n",
        "Iterative Deepening: Complete | Optimal \\\\\n",
        "Bidirectional: Complete | Optimal\n",
        "\n",
        "*Special Cases*: (1) BFS, Uniform, and Iterative are complete if b is finite or state space has a solution or is finite. (2) Uniform is complete if all action costs are at least $\\epsilon$ and greater than 0.\\\n",
        "(3) BFS, Iterative, and Bidrectional are cost-optimal if action costs are identical. (4) Bidirectional is complete and optimal if both directions use BFS/Uniform-cost\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Definitions of concepts from Module 3.\n",
        "# You can define any bolded term in the textbook, \n",
        "# but you most use your own words for the definitions.\n",
        "# Each definition should be at most 20 words long.\n",
        "module3_definitions = {\n",
        "\"problem-solving agent\" : \"an agent that can formulate a plan via search\",\n",
        "\"state space\" : \"set of possible states that the environment can be in\",\n",
        "\"action\" : \"set of moves that can be performed at state S\",\n",
        "\"transition model\" : \"describes what each action does (result of an action)\",\n",
        "\"action cost function\": \"numeric cost of applying action in state S to reach state S'\",\n",
        "\"solution\" : \"path from initial state to goal state\",\n",
        "\"optimal solution\": \"solution with lowest path cost\",\n",
        "\"abstraction\" : \"removing detail from a representation/model\",\n",
        "\"Frontier\" : \"set of unexpanded states that can be explored\",\n",
        "\"Search Tree\" : \"Represents paths that a search algorithm has explored\",\n",
        "\"FIFO\" : \"First-in-first-out - node that was added to the queue first is popped (BFS)\",\n",
        "\"LIFO\" : \"Last-in-first-out - pops most recently added node (DFS)\",\n",
        "\"Priority Queue\" : \"pops node with min cost (f(n)) (Best-first search)\"\n",
        "}\n",
        "\n"
      ],
      "execution_count": 30,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "642d265b-37dd-4640-bb41-28bb3e78582b"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module3_sections = [\n",
        "  (\"AIMA Chapter 3.1 Problem-Solving Agents\", chapter3_1),\n",
        "  (\"AIMA Chapter 3.2 Example Problems\", chapter3_2),\n",
        "  (\"AIMA Chapter 3.3 Search Algorithms\", chapter3_3),\n",
        "  (\"AIMA Chapter 3.4 Uninformed Search Strategies\", chapter3_4),\n",
        "  (\"Module 3 Lecture Notes\", module3_lecture_notes),\n",
        "]\n",
        "\n",
        "module3_markdown = format_module(3, \"Search Problems\", module3_sections, module3_definitions)\n",
        "display(Markdown(module3_markdown))"
      ],
      "execution_count": 31,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nA search problem includes:\n(1) a state space\n(2) initial state\n(3) goal states\n(4) set of actions\n(5) transition model\n(6) action cost function.\n\nThe **state space** can be represented as a graph where the vertices are states and the directed edges are the actions.\n\n\n## AIMA Chapter 3.2 Example Problems\n\n**Sliding-Tile Puzzle Example**\n\\\nStates : all the locations of the tiles \\\nInitial State : any state \\\nActions : tile or blank space moving *left, right, up, or down* \\\nTransition Model : result of taking an action (when tile is moved) \\\nGoal State: when the tiles are in order \\\nAction Cost : cost of moving a tile > all 1 in this puzzle \\\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nNodes of a search tree correspond to states and edges are actions. The child or successor node follows a parent node and the **frontier** represents the set of unexpanded child nodes.\n\n***Best-First Search***\nReturns some solution with minimum evaluation function=, *f(n)*. \nEach child node is added to the frontier if it has not been reached before or adjusted if it is reached\nwith lower path cost. \n\nThere are three kinds of queues: **priority**, **FIFO**, **LIFO**\n\n**Graph** search will check for redundant paths, while **tree** search will not.\n\nThe algorithm's performance can be evaluated by completeness, cost optimality, time complexity, and space complexity.\n\nComplexity can be measured in terms of *d*, the **depth** or number of actions in the optimal solution, or\n*b*, the **branching factor** or number of successors that need to be considered.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n***Breadth-first Search***\nAll actions have the same cost and all successors of the current frontier are expanded in order. Best if there are possibly infinite paths and some solutions have short paths.\nThis uses the **FIFO** queue and the set of *reached* nodes is a set of states rather than a mapping of states to nodes.\n\n*Psuedo-Code:*\ninitialize NODE \\\nif NODE is GOAL, return \\\nintialize FRONTIER and REACHED (FIFO queue [list] and [set]) \\\nwhile FRONTIER not empty: pop, check if GOAL or add to REACHED and FRONTIER \\\nreturn *failure* if no solution\n\n**Time Complexity** : *O(b^d)* \\\n**Space Complexity** : *O(b^d)* since all nodes remain in memory \\\nComplete, but only cost-optimal when all actions have the same cost\n\n***Dijkstra's (Uniform-cost Search)***\nBFS in uniform depth, Dijkstra's in uniform path-cost.\n\n**Time and Space Complexity** : *O(b^(1+[C/$\\epsilon$]))$ which can potentially be more than BFS. \\\nUniform-cost search is complete and cost-optimal\n\n***Depth-first Search***\nExpands to deepest node in the frontier first. Best for space restricted and many possible solutions with long paths.\n\n**Time Complexity** : *O(b^m)*\n**Space Complexity** : *O(bm)* where *m* is the max depth\n\nNot complete (unless m is bounded (limited depth)) or cost-optimal\n\n***Depth-limited Search***\nCut off DFS at limit *l* and treat all nodes at limit was if they had no successors. Same complexity as DFS with d = l.\\\nIf l < d, then incomplete; if l > d, then not optimal\n\n***Iterative Deepening Search***\nfor depth = 0 to $\\infty$, do depth-limited search.\n*O(bd)* if there is a solution or *O(bm)* when there is not. Preferred when search state is larger than memory (can't use BFS) and depth of solution is unknown (can't use DFS).\n\n***Bidirectional Search***\nSearches from initial state and backwards from goal state(s). Has frontier (priority queue) and reached states for forward and backward search.\n\nComplete and optimal with *O(b^(d/2))* Time and Space complexity\n\n\n## Module 3 Lecture Notes\n\nBFS: Complete | Optimal \\\nUniform: Complete | Optimal \\\nDFS: Not Complete | Not Optimal \\\nDepth-limited: Not Complete | Not Optimal \\\nIterative Deepening: Complete | Optimal \\\nBidirectional: Complete | Optimal\n\n*Special Cases*: (1) BFS, Uniform, and Iterative are complete if b is finite or state space has a solution or is finite. (2) Uniform is complete if all action costs are at least $\\epsilon$ and greater than 0.(3) BFS, Iterative, and Bidrectional are cost-optimal if action costs are identical. (4) Bidirectional is complete and optimal if both directions use BFS/Uniform-cost\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - set of possible states that the environment can be in\n* **Action** - set of moves that can be performed at state S\n* **Transition model** - describes what each action does (result of an action)\n* **Action cost function** - numeric cost of applying action in state S to reach state S'\n* **Solution** - path from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Abstraction** - removing detail from a representation/model\n* **Frontier** - set of unexpanded states that can be explored\n* **Search tree** - Represents paths that a search algorithm has explored\n* **Fifo** - First-in-first-out - node that was added to the queue first is popped (BFS)\n* **Lifo** - Last-in-first-out - pops most recently added node (DFS)\n* **Priority queue** - pops node with min cost (f(n)) (Best-first search)\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "WHREsHSSyA-h"
      },
      "source": [
        "#Module 4 - Informed Search"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "tuFC8w7CyCns"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 3 “Problem Solving by Search” (3.5-3.6)\n",
        "chapter3_5 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"g(N)\" : \"path cost function, equal to depth(N) in search tree\",   \n",
        "\"uniform cost search (USC)\": \"tree search to traverse/ search a weighted tree/graph\",\n",
        "\"informed search\": \"uses domain-specific hints (heuristics) about the goal locations\",\n",
        "\"heuristic function\": \"h(n), estimates cost of the cheapest path from current state to goal\",\n",
        "\"greedy best-first search\": \"form of best-FS, first expands node with lowest h(n); $f(n) = h(n)$\",\n",
        "\"admissible heuristic\": \"will never overestimate the cost to reach a goal, optimistic\",\n",
        "\"A* search\": \"expands nodes with minimal $f(n) = g(n) + h(n)$. Complete and optimal \\\n",
        "if admissible heuristic, space-complexity is an issue sometimes\",\n",
        "\"consistency\": \"if for every node and every successor of the node we have \\\n",
        "$h(n) \\leq c(n, a, n') + h(n')$\",\n",
        "\"triangle inequality\": \"side of a trangle can't be longer than the sum of the 2 other sides\",\n",
        "\"monotonic\": \"path cost will always increase as you go along a path since action \\\n",
        "costs are positive\",\n",
        "\"pruning\": \"removing nodes that are not needed, done by A*\",\n",
        "\"surely expanded nodes\": \"A* expands because they can be reached from the initial \\\n",
        "state on a path where every node $f(n) < C*$\",\n",
        "\"optimally efficient\": \"any alg that extends search paths from the initial state, \\\n",
        "must expand any node surely expanded by A*\",\n",
        "\"satisficing\": \"explore fewer nodes to accept solutions that are suboptimal but good enough\",\n",
        "\"weighted A* search\": \"weigh the heuristic value more heavily, eval function is \\\n",
        "$f(n) = g(n) + W * h(n)$, W > 1\",\n",
        "\"bounded suboptimal search\": \"find solution that's within a constant factor W \\\n",
        "of the optimal cost; guaranteed by weighted A*\",\n",
        "\"unbounded-cost search\": \"accept any solution as long as it can be found quickly\",\n",
        "\"speedy search\": \"unbounded-cost search, version of greedy best-first whose \\\n",
        "heuristic is the est # of actions to reach a goal (ignores cost)\",\n",
        "\"recursive best-first search\": \"recursive DFS that stops at f_limit, more efficient \\\n",
        "than IDA*, optimal with admissible heuristic, linear space\",\n",
        "\"backed-up value\": \"the best f-value of a node's children, RBFS updates each node\\\n",
        "along the path with this\",\n",
        "\"thrashing\": \"too many pages in mem causing comp to constantly \\\n",
        "swap; similar to SMA* weakness due to limited memory\",\n",
        "\"front-to-end search\": \"heuristics $h_F$ and $h_B$ to estimate distances to goal \\\n",
        "and the start respectively\",\n",
        "\"front-to-front search\": \"attempts to estimate the distance to the other frontier\",\n",
        "\"bidectional search\": \"optimal and complete with $f_2$ eval function and an \\\n",
        "admissible heuristic h\",\n",
        "\"effective branching factor (b*)\": \"characterizes quality of a heuristic\",\n",
        "\"domination\": \"if $h_2$ in A* never expands more nodes than when using $h_1$, it \\\n",
        "dominates the heuristic\",\n",
        "\"relaxed problem\": \"a problem with fewer restrictions on the actions\",\n",
        "\"pattern databases\": \"record cost of every new pattern encountered and store \\\n",
        "exact solution costs for every subproblem instance\",\n",
        "\"precomputation\": \"calculating some optimal path costs before alg is run, \\\n",
        "can be time-consuming but only has to be done once\",\n",
        "\"landmark points\": \"used for precomputation and compute and store path costs from each \\\n",
        "vertex to these points\",\n",
        "\"shortcuts\": \"artificial edges in the graph that define an optimal multi-action path\",\n",
        "\"differential heuristic\": \"$h_{DH}(n) = max_{L \\in Landmarks}|C*(n,L) - C*(goal,L)|$\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 32,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 921
        },
        "cellView": "form",
        "outputId": "21eaf40c-a325-49ce-b114-db9c288e9135"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module4_sections = [\n",
        "  (\"AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\", chapter3_5),\n",
        "  (\"AIMA Chapter 3.6 Heuristic Functions\", chapter3_6),\n",
        "  (\"Module 4 Lecture Notes\", module4_lecture_notes),\n",
        "]\n",
        "\n",
        "module4_markdown = format_module(4, \"Informed Search\", \n",
        "                         module4_sections, \n",
        "                         module4_definitions)\n",
        "display(Markdown(module4_markdown))"
      ],
      "execution_count": 33,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **G(n)** - path cost function, equal to depth(N) in search tree\n* **Uniform cost search (usc)** - tree search to traverse/ search a weighted tree/graph\n* **Informed search** - uses domain-specific hints (heuristics) about the goal locations\n* **Heuristic function** - h(n), estimates cost of the cheapest path from current state to goal\n* **Greedy best-first search** - form of best-FS, first expands node with lowest h(n); $f(n) = h(n)$\n* **Admissible heuristic** - will never overestimate the cost to reach a goal, optimistic\n* **A* search** - expands nodes with minimal $f(n) = g(n) + h(n)$. Complete and optimal if admissible heuristic, space-complexity is an issue sometimes\n* **Consistency** - if for every node and every successor of the node we have $h(n) \\leq c(n, a, n') + h(n')$\n* **Triangle inequality** - side of a trangle can't be longer than the sum of the 2 other sides\n* **Monotonic** - path cost will always increase as you go along a path since action costs are positive\n* **Pruning** - removing nodes that are not needed, done by A*\n* **Surely expanded nodes** - A* expands because they can be reached from the initial state on a path where every node $f(n) < C*$\n* **Optimally efficient** - any alg that extends search paths from the initial state, must expand any node surely expanded by A*\n* **Satisficing** - explore fewer nodes to accept solutions that are suboptimal but good enough\n* **Weighted a* search** - weigh the heuristic value more heavily, eval function is $f(n) = g(n) + W * h(n)$, W > 1\n* **Bounded suboptimal search** - find solution that's within a constant factor W of the optimal cost; guaranteed by weighted A*\n* **Unbounded-cost search** - accept any solution as long as it can be found quickly\n* **Speedy search** - unbounded-cost search, version of greedy best-first whose heuristic is the est # of actions to reach a goal (ignores cost)\n* **Recursive best-first search** - recursive DFS that stops at f_limit, more efficient than IDA*, optimal with admissible heuristic, linear space\n* **Backed-up value** - the best f-value of a node's children, RBFS updates each nodealong the path with this\n* **Thrashing** - too many pages in mem causing comp to constantly swap; similar to SMA* weakness due to limited memory\n* **Front-to-end search** - heuristics $h_F$ and $h_B$ to estimate distances to goal and the start respectively\n* **Front-to-front search** - attempts to estimate the distance to the other frontier\n* **Bidectional search** - optimal and complete with $f_2$ eval function and an admissible heuristic h\n* **Effective branching factor (b*)** - characterizes quality of a heuristic\n* **Domination** - if $h_2$ in A* never expands more nodes than when using $h_1$, it dominates the heuristic\n* **Relaxed problem** - a problem with fewer restrictions on the actions\n* **Pattern databases** - record cost of every new pattern encountered and store exact solution costs for every subproblem instance\n* **Precomputation** - calculating some optimal path costs before alg is run, can be time-consuming but only has to be done once\n* **Landmark points** - used for precomputation and compute and store path costs from each vertex to these points\n* **Shortcuts** - artificial edges in the graph that define an optimal multi-action path\n* **Differential heuristic** - $h_{DH}(n) = max_{L \\in Landmarks}|C*(n,L) - C*(goal,L)|$\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 34,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 674
        },
        "outputId": "07babaef-69b0-4728-c71d-288ffa8a5203"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module5_sections = [\n",
        "  (\"AIMA Chapter 5.1 Game Theory\", chapter5_1),\n",
        "  (\"AIMA Chapter 5.2 Optimal Decisions in Games\", chapter5_2),\n",
        "  (\"AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\", chapter5_3),\n",
        "  (\"AIMA Chapter 5.5 Stochastic Games\", chapter5_5),\n",
        "  (\"AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\", chapter16_1),\n",
        "  (\"AIMA Chapter 16.2 The Basis of Utility Theory\", chapter16_2),\n",
        "  (\"AIMA Chapter 16.3 Utility Functions\", chapter16_3),\n",
        "  (\"Module 5 Lecture Notes\", module5_lecture_notes),\n",
        "]\n",
        "\n",
        "module5_markdown = format_module(5, \"Adversarial Search and Games\", \n",
        "                         module5_sections, \n",
        "                         module5_definitions)\n",
        "display(Markdown(module5_markdown))"
      ],
      "execution_count": 35,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter6_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n"
      ],
      "execution_count": 36,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "10f0d39c-987a-4215-ee53-0213c9153fe1"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module6_sections = [\n",
        "  (\"AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\", chapter6_1),\n",
        "  (\"AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\", chapter6_2),\n",
        "  (\"AIMA Chapter 6.3 Backtracking Search for CSPs\", chapter6_3),\n",
        "  (\"AIMA Chapter 6.4 Local Search for CSPs\", chapter6_4),\n",
        "  (\"AIMA Chapter 6.5 The Structure of Problems\", chapter6_5),\n",
        "  (\"Module 6 Lecture Notes\", module6_lecture_notes),\n",
        "]\n",
        "\n",
        "module6_markdown = format_module(6, \"Constraint Satisfaction Problems\", \n",
        "                         module6_sections, \n",
        "                         module6_definitions)\n",
        "display(Markdown(module6_markdown))"
      ],
      "execution_count": 37,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "RYESi2kMybL8"
      },
      "source": [
        "#Module 7 - Logical Agents"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "qIRJ4YYCzNHL"
      },
      "source": [
        "# Russell and Norvig, AIMA Chapter 7 “Logical Agents” (Sections 7.1-7.5)\n",
        "\n",
        "chapter7_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_4 = \"\"\" Your summary here \"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 38,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 541
        },
        "outputId": "adeb801f-b69b-4501-b43c-38af5ed5f560"
      },
      "source": [
        "#@title Preview of your summary\n",
        "#@markdown You don't need to modify anything in this cell. Just press play.\n",
        "module7_sections = [\n",
        "  (\"AIMA Chapter 7.1 Knowledge-Based Agents\", chapter7_1),\n",
        "  (\"AIMA Chapter 7.2 The Wumpus World\", chapter7_2),\n",
        "  (\"AIMA Chapter 7.3 Logic\", chapter7_3),\n",
        "  (\"AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\", chapter7_4),\n",
        "  (\"AIMA 7.5 Propositional Theorem Proving\", chapter7_5),\n",
        "  (\"Module 7 Lecture Notes\", module7_lecture_notes),\n",
        "]\n",
        "\n",
        "module7_markdown = format_module(7, \"Logical Agents\", \n",
        "                         module7_sections, \n",
        "                         module7_definitions)\n",
        "display(Markdown(module7_markdown))"
      ],
      "execution_count": 39,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "vX7lbnJd4sT5"
      },
      "source": [
        "# Your Exam Notes\n",
        "\n",
        "Here are your full set of exam notes that you can use on your midterm.  Choose **Runtime > Run all**, then your notes will be displayed.\n",
        "\n",
        "If you are taking the exam in person, then you must print a copy of your notes for yourself.   Here's how to print:\n",
        "* Run the cell below. \n",
        "* Click its \"Mirror cell in tab\" button (this is located in the upper right corner of the cell, immediately to the right of the trash can).  This will open the cell.  \n",
        "* In Chrome, you can then print your notes using the **File > Print** option from the browser's menu.  \n",
        "* In the print options, change the layout from Landscape to Portrait. \n",
        "* Clicking the Save, will save a PDF that you can then print.\n"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "id": "T3cm1WV542_a",
        "outputId": "b62004fd-10c8-4450-9cae-95b4dd8cc978"
      },
      "source": [
        "# This will generate the full set of notes that you can use for your exam.\n",
        "full_markdown = \"\\n\\n\".join([module1_markdown, \n",
        "                             module2_markdown, \n",
        "                             module3_markdown, \n",
        "                             module4_markdown, \n",
        "                             module5_markdown,\n",
        "                             module6_markdown,\n",
        "                             module7_markdown,]\n",
        "                       )\n",
        "display(Markdown(full_markdown))"
      ],
      "execution_count": 40,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\nTwo ways to define AI: intelligent behavior, human performance. \\\nComputers use (1) NLP to communicate human language, (2) knowledge representation to store what it knows/hears, (3) automated reasoning to answer questions and detect and extrapolate patterns\n\nTuring Test to tell if computer is intelligent - try to tell if responses are human.\n\nTotal Turing Test requires a computer to have computer vision, speech recognition, and actuators to move.\n\nHuman thought is learned in 3 ways: (1) introspection, (2) psychological, and (3) brain imaging\n\n*Limited Rationality* - acting appropriately when there is not enough compute resources.\n\nIf we cannot get a machine to complete our objective, reformulate the problem. (Value alignment problem - provably beneficial to humans).\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\nGood Old-Fashioned AI (GOFAI) - corresponds to the siplest logical agent design\n\nQualification Problem - the difficulty to capture every contingency of appropriate behavior in a set of necessary and sufficient logical rules\n\nGödel sentence *G(F)*:\n + *G(F)* is a sentence of *F*, but cannot be proved within *F*\n + if *F* is consistent, then *G(F)* is true \\\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n\nAn agent's choice of action at any given instant can depend on its built-in knowledge and on the entire percept sequence observed to date, but not on anything it hasn't perceived.\n\n*Agent Function* - describes an agent's behavior and maps any percept sequence to an action. \\\n*Agent Program* - How an agent program is implemented in an artificial agent.\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\nAI are created to help humans, so helpfulness and performance are evaluated. \n\nRationality depends on: (1) The performance measure that defines criterion of success, (2) The agent's prior knowledge of the environment, (3) The actions that the agent can perform, and (4) The agent's percept sequence to date.\n\n*Rational Agent* - For each possible percept sequence, a rational agent should select an action that is expected to maximize its performance measure.\n\n*Omniscient Agent* - knows the actual outcome of its actions and can act accordingly \\\n\n\n## AIMA 2.3 The Nature of Environments\n\n**PEAS** (Performance, Environment, Acuators, Sensors) are part of the task environment.\nEx: Medical diagnosis (P) healthy patients, reduced costs | (E) patients, hospital staff | \n(A) display of questions, tests, diagnoses, treatments | (S) entry of symptoms or observations\n\nMultiagent can be: *competitive* (two agents against another - chess) or *cooperative* (all players benefit from other players not failing - autonomous car)\n\n*Deterministic* - if the next state of the environment is completely determined by\nthe current state and the action executed by the agent(s) \\\n*Stochastic* (non-deterministic) - actions are randomly determined\n\n*Episodic* - the agent's experience is divided into atomic episodes, where the agent receives\na percept and then performs a single action.\\\n*Sequential* - A current decision could affect all future decisions (chess).\n\n*Static* vs *Dynamic* - environment cannot or can change while the agent is deliberating.\nA *semidynamic* environment doesn't change, but the agent's performance score might (Chess on a clock).\n\n*Discrete* vs. *Continuous* - chess discrete, taxi driving continuous\n\n\n## AIMA 2.4 The Structure of Agents\n\nagent = architecture + program \\\n1. Simple reflex agent - select actions on the basis of current percept, ignoring the rest of\npercept history condition-action rule - some processing is done on the visual input to establish the condition\n (a smart car knows to brake if the brake lights of the car in front go on) \\\n2. Model based reflex agent - the gaent should maintain some sort of internal state that depends on the percept\nhistory and thereby reflects at least some of the unobserved aspects of the current state.\nHandles partial observability. \\\nTransition model - knowledge of how the world works for intelligent agents \\\nSensor model - information about how the state of the world is reflected in the agent's percepts \\\n3. Goal based agents - the agent needs some sort of goal information that describes situations\nthat are desirable and a current state description. Both search and planning is used to achieve the agent's goal \\\n4. Utility based agents - a more general performance measure should allow a comparison of different world\nstates according to exactly how 'happy' they would make the agent. \n\n\n## Module 1 Lecture Notes\n\n*Performance Measures* - design based on what you want to be achieved rather than how you think the agent should behave.\n\n\n## Module 1 Definitions\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - The content an agent's sensors are perceiving\n* **Percept sequence** - An agent's complete history of everything it has ever perceived\n* **Introspection** - trying to catch our own thoughts as they go by\n* **Psychological experiements** - observing a person in action\n* **Brain imaging** - observing the brain in action\n* **Weak ai** - machines could act as if they were intelligent\n* **Strong ai** - machines that act as if they were intelligent, actually consciously think\n* **Rational agent** - an agent that does the right thing\n* **Consequentialism** - evaluating an agent's behavior by its consequences\n* **Fully observable** - sensors have access to complete state of environment - perfect information\n* **Partially observable** - some sensors are blocked by noise or inaccurate sensors\n* **Expected utility** - The utility the agent exptes to derive, on average, given the probabilities\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n\nGood features of Python \\\nFast development:\\\n-Concise, intuitive syntax that is whitespace delimited\\\n-Garbage collected\\\nPortable:\\\n-Programs run on major platforms without change\\\nVarious built-in types:\\\n-lists, dictionaries, sets: useful for AI\\\nLarge collection of support libraries:\\\n-NumPy for Matlab like programming\\\n-Pandas for data analysis\\\n-Sklearn for machine learning\\\n-Pytorch and TensorFlow for deep learning\n \n**Objects and Types**\nAll data treated as objects:\nAn object is deleted (by garbage collection) once unreachable.\n \n**Strong Typing:**\nEvery object has a fixed type, interpreter doesn’t allow things incompatible with\nthat type (eg. “foo” + 2) \\\ntype(object) \\\nisinstance(object, type)\n \nExamples of Types: \\\nint, float, \nstr, tuple, dict, list, \nbool: True, False, \nNone, generator, function\n \nPython has dynamic typing: Variables come into existence when first assigned.\nStrings are immutable, lists are mutable\n \n**Sequence Types**\nTuple:\\\n-A simple immutable ordered sequence of items \\\n-Immutable: a tuple cannot be modified once created\\\n-Items can be of mixed types, including collection types\n \nStrings:\\\n-Immutable\\\n-Regular strings are Unicode and use 2-byte characters (Regular strings in\nPython 2 use 8-bit characters)\\\nList:\\\n-Mutable ordered sequence of items of mixed types\n \n \nPython allows multiple return values.\nIt does not have function overloading.\nNot all arguments need to be called for the function to be called.\n \nFunctions are first class\\\n**First class object:**\\\n-An entity that can be dynamically created, destroyed, passed to a function,\nreturned as a value, and have all the rights as other variables in the\nprogramming language have\\\n\nFunctions are “first-class citizens”:\\\n-Pass functions as arguments to other functions\\\n-Return functions as the values from other functions\\\n-Assign functions to variables or store them in data structures\\\nHigher order functions: take functions as input\\\n \n**Subclasses:**\\\n-no extend keyword\\\n-multiple inheritance is allowed\n \nMethods that behave like built ins:\\\n__init__: The constructor for the class.\\\n__len__ : Define how len( obj ) works.\\\n__copy__: Define how to copy a class.\\\n__cmp__ : Define how == works for class.\\\n__add__ : Define how + works for class\\\n__neg__ : Define how unary negation works for class\\\n \n**Iterator Objects:**//\nIterable objects can be used in a for loop because they have an __iter__ magic\nmethod, which converts them to iterator objects\\\n- no hasNext in python\n \n**Generators:**\\\n-Generators are iterators (with __next()__ method)\\\n-Creating Generators: yield\n \nYIELD: Each time we call the __next__ method of the generator, the method runs until it\nencounters a yield statement, and then it stops and returns the value that was yielded.\nNext time, it resumes where it left off\n \nBenefits of generators:\\\n-Less code than writing a standard iterator\\\n-Maintains local state automatically\\\n-Values are computed one at a time, as they’re needed\\\n-Avoids storing the entire sequence in memory\\\n-Good for aggregating (summing, counting) items. One pass.\\\n-Crucial for infinite sequences\\\n-Bad if you need to inspect the individual values\\\n\n\n## Module 2 Definitions\n* **Mutability** - ability to change\n* **Method** - when a functioni s defined inside a class\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n \nA search problem includes:\n(1) a state space\n(2) initial state\n(3) goal states\n(4) set of actions\n(5) transition model\n(6) action cost function.\n\nThe **state space** can be represented as a graph where the vertices are states and the directed edges are the actions.\n\n\n## AIMA Chapter 3.2 Example Problems\n\n**Sliding-Tile Puzzle Example**\n\\\nStates : all the locations of the tiles \\\nInitial State : any state \\\nActions : tile or blank space moving *left, right, up, or down* \\\nTransition Model : result of taking an action (when tile is moved) \\\nGoal State: when the tiles are in order \\\nAction Cost : cost of moving a tile > all 1 in this puzzle \\\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\nNodes of a search tree correspond to states and edges are actions. The child or successor node follows a parent node and the **frontier** represents the set of unexpanded child nodes.\n\n***Best-First Search***\nReturns some solution with minimum evaluation function=, *f(n)*. \nEach child node is added to the frontier if it has not been reached before or adjusted if it is reached\nwith lower path cost. \n\nThere are three kinds of queues: **priority**, **FIFO**, **LIFO**\n\n**Graph** search will check for redundant paths, while **tree** search will not.\n\nThe algorithm's performance can be evaluated by completeness, cost optimality, time complexity, and space complexity.\n\nComplexity can be measured in terms of *d*, the **depth** or number of actions in the optimal solution, or\n*b*, the **branching factor** or number of successors that need to be considered.\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n***Breadth-first Search***\nAll actions have the same cost and all successors of the current frontier are expanded in order. Best if there are possibly infinite paths and some solutions have short paths.\nThis uses the **FIFO** queue and the set of *reached* nodes is a set of states rather than a mapping of states to nodes.\n\n*Psuedo-Code:*\ninitialize NODE \\\nif NODE is GOAL, return \\\nintialize FRONTIER and REACHED (FIFO queue [list] and [set]) \\\nwhile FRONTIER not empty: pop, check if GOAL or add to REACHED and FRONTIER \\\nreturn *failure* if no solution\n\n**Time Complexity** : *O(b^d)* \\\n**Space Complexity** : *O(b^d)* since all nodes remain in memory \\\nComplete, but only cost-optimal when all actions have the same cost\n\n***Dijkstra's (Uniform-cost Search)***\nBFS in uniform depth, Dijkstra's in uniform path-cost.\n\n**Time and Space Complexity** : *O(b^(1+[C/$\\epsilon$]))$ which can potentially be more than BFS. \\\nUniform-cost search is complete and cost-optimal\n\n***Depth-first Search***\nExpands to deepest node in the frontier first. Best for space restricted and many possible solutions with long paths.\n\n**Time Complexity** : *O(b^m)*\n**Space Complexity** : *O(bm)* where *m* is the max depth\n\nNot complete (unless m is bounded (limited depth)) or cost-optimal\n\n***Depth-limited Search***\nCut off DFS at limit *l* and treat all nodes at limit was if they had no successors. Same complexity as DFS with d = l.\\\nIf l < d, then incomplete; if l > d, then not optimal\n\n***Iterative Deepening Search***\nfor depth = 0 to $\\infty$, do depth-limited search.\n*O(bd)* if there is a solution or *O(bm)* when there is not. Preferred when search state is larger than memory (can't use BFS) and depth of solution is unknown (can't use DFS).\n\n***Bidirectional Search***\nSearches from initial state and backwards from goal state(s). Has frontier (priority queue) and reached states for forward and backward search.\n\nComplete and optimal with *O(b^(d/2))* Time and Space complexity\n\n\n## Module 3 Lecture Notes\n\nBFS: Complete | Optimal \\\nUniform: Complete | Optimal \\\nDFS: Not Complete | Not Optimal \\\nDepth-limited: Not Complete | Not Optimal \\\nIterative Deepening: Complete | Optimal \\\nBidirectional: Complete | Optimal\n\n*Special Cases*: (1) BFS, Uniform, and Iterative are complete if b is finite or state space has a solution or is finite. (2) Uniform is complete if all action costs are at least $\\epsilon$ and greater than 0.(3) BFS, Iterative, and Bidrectional are cost-optimal if action costs are identical. (4) Bidirectional is complete and optimal if both directions use BFS/Uniform-cost\n\n\n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n* **State space** - set of possible states that the environment can be in\n* **Action** - set of moves that can be performed at state S\n* **Transition model** - describes what each action does (result of an action)\n* **Action cost function** - numeric cost of applying action in state S to reach state S'\n* **Solution** - path from initial state to goal state\n* **Optimal solution** - solution with lowest path cost\n* **Abstraction** - removing detail from a representation/model\n* **Frontier** - set of unexpanded states that can be explored\n* **Search tree** - Represents paths that a search algorithm has explored\n* **Fifo** - First-in-first-out - node that was added to the queue first is popped (BFS)\n* **Lifo** - Last-in-first-out - pops most recently added node (DFS)\n* **Priority queue** - pops node with min cost (f(n)) (Best-first search)\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **G(n)** - path cost function, equal to depth(N) in search tree\n* **Uniform cost search (usc)** - tree search to traverse/ search a weighted tree/graph\n* **Informed search** - uses domain-specific hints (heuristics) about the goal locations\n* **Heuristic function** - h(n), estimates cost of the cheapest path from current state to goal\n* **Greedy best-first search** - form of best-FS, first expands node with lowest h(n); $f(n) = h(n)$\n* **Admissible heuristic** - will never overestimate the cost to reach a goal, optimistic\n* **A* search** - expands nodes with minimal $f(n) = g(n) + h(n)$. Complete and optimal if admissible heuristic, space-complexity is an issue sometimes\n* **Consistency** - if for every node and every successor of the node we have $h(n) \\leq c(n, a, n') + h(n')$\n* **Triangle inequality** - side of a trangle can't be longer than the sum of the 2 other sides\n* **Monotonic** - path cost will always increase as you go along a path since action costs are positive\n* **Pruning** - removing nodes that are not needed, done by A*\n* **Surely expanded nodes** - A* expands because they can be reached from the initial state on a path where every node $f(n) < C*$\n* **Optimally efficient** - any alg that extends search paths from the initial state, must expand any node surely expanded by A*\n* **Satisficing** - explore fewer nodes to accept solutions that are suboptimal but good enough\n* **Weighted a* search** - weigh the heuristic value more heavily, eval function is $f(n) = g(n) + W * h(n)$, W > 1\n* **Bounded suboptimal search** - find solution that's within a constant factor W of the optimal cost; guaranteed by weighted A*\n* **Unbounded-cost search** - accept any solution as long as it can be found quickly\n* **Speedy search** - unbounded-cost search, version of greedy best-first whose heuristic is the est # of actions to reach a goal (ignores cost)\n* **Recursive best-first search** - recursive DFS that stops at f_limit, more efficient than IDA*, optimal with admissible heuristic, linear space\n* **Backed-up value** - the best f-value of a node's children, RBFS updates each nodealong the path with this\n* **Thrashing** - too many pages in mem causing comp to constantly swap; similar to SMA* weakness due to limited memory\n* **Front-to-end search** - heuristics $h_F$ and $h_B$ to estimate distances to goal and the start respectively\n* **Front-to-front search** - attempts to estimate the distance to the other frontier\n* **Bidectional search** - optimal and complete with $f_2$ eval function and an admissible heuristic h\n* **Effective branching factor (b*)** - characterizes quality of a heuristic\n* **Domination** - if $h_2$ in A* never expands more nodes than when using $h_1$, it dominates the heuristic\n* **Relaxed problem** - a problem with fewer restrictions on the actions\n* **Pattern databases** - record cost of every new pattern encountered and store exact solution costs for every subproblem instance\n* **Precomputation** - calculating some optimal path costs before alg is run, can be time-consuming but only has to be done once\n* **Landmark points** - used for precomputation and compute and store path costs from each vertex to these points\n* **Shortcuts** - artificial edges in the graph that define an optimal multi-action path\n* **Differential heuristic** - $h_{DH}(n) = max_{L \\in Landmarks}|C*(n,L) - C*(goal,L)|$\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n Your summary here \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n Your summary here \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.4 Local Search for CSPs\n Your summary here \n\n## AIMA Chapter 6.5 The Structure of Problems\n Your summary here \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Concept** - definition\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n Your summary here \n\n## AIMA Chapter 7.2 The Wumpus World\n Your summary here \n\n## AIMA Chapter 7.3 Logic\n Your summary here \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n Your summary here \n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "-OWYPxbim1nO"
      },
      "source": [
        ""
      ],
      "execution_count": null,
      "outputs": []
    }
  ]
}