{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Wes_Gill__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": "81a7b3ac-ca2e-45e0-9d52-1af80e19ad75"
      },
      "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": 228,
      "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": "ee54fd25-b98f-4d16-d1b1-57d6eeeb844c"
      },
      "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": 229,
      "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 = \"Wesley Gill\"\n",
        "permission = True\n",
        "anonymous = False"
      ],
      "execution_count": 230,
      "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",
        "\n",
        "\n",
        "###  Artificial Intelligence\n",
        " - Field of understanding and building intelligent entities\n",
        "\n",
        "### Human vs. rational\n",
        " - Some AI try to act like humans\n",
        " - Others try to act \"rationally\" by doing the right thing\n",
        "\n",
        "### Turing test\n",
        " -  Human asks written questions to computer which responds with written responses\n",
        " - If human interrogator cannot distinguish computer from human, the AI passes\n",
        "\n",
        "### Methods of testing human thought\n",
        " - Intrpspection\n",
        " - Psychological experiments\n",
        " - Brain imaging\n",
        "\n",
        "### Syllogisms\n",
        " - Patterns for argument structures that always yielded corect conclusions given correct premises\n",
        "\n",
        "\"\"\" \n",
        "\n",
        "# # NOT NECESSAARY\n",
        "# chapter1_2 = \"\"\"\n",
        "\n",
        "# ### Dualism\n",
        "#  -  Concept that part of human mind is outside nature / not bound by physics\n",
        "\n",
        "# ### Materialism/Physicalism/Naturalism\n",
        "#  - Concept that brain operates based on the laws of physics\n",
        "\n",
        "# ### Logical positivism\n",
        "#  - Knowledge represented as logic theories => observation sentences\n",
        "#  - Observation sentences updated/added by sensory inputs\n",
        "\n",
        "# ### Confirmation theory\n",
        "#  - Study of how to evaluate logical sentences based on connection to observation\n",
        "\n",
        "# ### General problem solver\n",
        "#  - Old AI that would now be called a \"greedy regression planning system\"\n",
        "\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",
        "\n",
        "### Agent\n",
        " - An **agent** is anything that perceives and acts in an environment through **sensors** and **actuators**\n",
        " - **percept** : data perceived by an agent\n",
        " - **percept sequence** : complete history of percepts\n",
        " - **agent function** : function from the percept sequence to an action\n",
        " - **agent program** : implementation of the agent function in a physical system\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "chapter27_2 = \"\"\"\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\"\n",
        "\n",
        " ### Rational agent\n",
        " - An agent that works towards the best outcome or best expected outcome\n",
        "\n",
        "### Limited rationality\n",
        " - Taking good actions with limits on computation time\n",
        "\n",
        "### Value alighnment problem\n",
        " - Problem of making the goals of the machine aligned with those of the human\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter2_2 = \"\"\"\n",
        "\n",
        "### Rational agent\n",
        " - **rational agent** : selects actions to maximize performance measure based on **prior knowledge** and **current percept sequence**\n",
        "\n",
        "### Omniscience\n",
        " - **omniscience** is knowing the *actual* outcome of actions\n",
        "\n",
        "### Autonomy \n",
        " - **autonomy** is the ability of an agent to learn from its environment/percepts rather than relying on knowledge of its designer\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter2_3 = \"\"\"\n",
        "\n",
        "### Task environments\n",
        " - A rational agent solves a \"problem\" defined by a task environment\n",
        "\n",
        "### Components of task environment (PEAS)\n",
        " - Performance\n",
        "     - measured by a **performance measure**\n",
        " - Environment\n",
        "     - E.g. roads\n",
        " - Actuators\n",
        "     - e.g. control over steering and breaking\n",
        " - Sensors\n",
        "     - e.g video cameras so the autoamated taxi can see\n",
        "\n",
        "\n",
        "### Fully observable vs. partially observable\n",
        " - Noise or lack of sensors can lead to partially observable environments\n",
        "\n",
        "### Single-agent vs. Multi-agent\n",
        " - In multi-agents environment, the behavior of one agent depends on the behavior of the other \n",
        " - Multi-agent environments can be competitve or cooperative\n",
        "\n",
        "### Deterministic vs. nondeterministic\n",
        " - A deterministic environment is one in which the next state of the environment is completely determined by the current state and teh action executed by the agent(s)\n",
        " - Otherwise, it is non-deterministic\n",
        " - A partially observable environment could *appear* nondeterministic\n",
        "\n",
        "### Stochastic\n",
        " - Nondeterministic environment where the probabilities of each event are explicitly known (e.g. Poker)\n",
        "\n",
        "### Episodic vs. Sequential\n",
        " - In episodic environments, each state is completely independent of future states\n",
        " - In sequential environments an action at time $t$ can have an impact on all states/decisions at times > $t$\n",
        "\n",
        "### Static vs. Dynamic\n",
        " - A dynamic is an environment that can change *while the agent is deliberating*\n",
        " - Otherwise, it's static\n",
        " - Semidynamic environments are those where the agents **performance score** can change over time even if the environment does not\n",
        "\n",
        "### Discrete vs. continuous\n",
        " - Distinction can be made w.r.t. the state, the time, and the percepts and actions\n",
        " - Chess is discrete in terms of states, percepts, and actions\n",
        " - Taxi driving is continuous state and contintuous time problem. Input from digital cameras is *technically* discrete but we may consider it continuous\n",
        "\n",
        "### Known vs. unknown\n",
        " - Refers not to the environment itself but to the agent's (or designer's) state of knowledge about the \"laws of physics\" of the environment\n",
        " - In a known environment, the outcomes (or outcome probabilities for nondeterministic environment) for all actions is given\n",
        " - If environment is unknown the agent will have to *learn* in order to make good decisions\n",
        "\n",
        "### Environment class\n",
        " - Describes a set of environments populated by adjusting hyperparameters\n",
        " - e.g. a single class of taxi environment could be populated with different values for traffic, lighting, and weather conditions\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter2_4 = \"\"\"\n",
        "\n",
        "### Structure of agents\n",
        " - Job of AI is to implement **agent program** that implements the agent function\n",
        " - **agent architecture** is the computing device with physical sensors and actuators $$agent = architecture + program$$\n",
        " - The agent program takes only the current percept while the agent function takes entire history\n",
        " \n",
        "### Four basic kinds of agents\n",
        " - **Simple reflex agents**\n",
        "     - select actions on the *current percept* only\n",
        " - **Model-based reflex agents**\n",
        "    - maintains internal state\n",
        "    - **transition model** : updates internal state\n",
        "    - **sensor model**: encodes the state of the world from info contained in percepts\n",
        " - **Goal-based agents**\n",
        "     - Agent needs current state description + description of goal\n",
        " - **Utility-based agents**\n",
        "     - **utility function** that can evaluate eutility of different states/actions\n",
        "     - may optimize **expected utility** in non-deterministic environments\n",
        "\n",
        "### Model-free agent\n",
        " - Can learn what action is best in a particular situation without ever learning exactly how that action changes the environment\n",
        "\n",
        "### Learning agents\n",
        " - **learning agents** have four components\n",
        "     - **learning element** : responsible for making improvements\n",
        "     - **performance element** : responsible for selecting external actions\n",
        "     - ** critic ** : gives feedback to the learning element on how the agent is doing\n",
        "     - **problem generator** : responsible for suggesting actions that will lead to new and informative experiences\n",
        "\n",
        "### Representations of environments\n",
        " - **atomic representation** : each state of the world is indivisible with no structure\n",
        " - **factored representation** : splits up each state into a fixed set of **variables/attributes** each of which can have a **value**\n",
        " - **structured representation** : Relationships between pairs of objects can be described explicitly\n",
        "\n",
        "### Localist vs. distributed representation\n",
        " - **Localist representation** has one-to-one mapping of concepts and memory locations\n",
        " - In **distributeed representation**, each memory location is part of the representation of multiple different concepts\n",
        "     - Each concept represents a point in multidimensional space\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\"\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",
        "}\n",
        "\n"
      ],
      "execution_count": 231,
      "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
        },
        "outputId": "33e2f8a9-2e2c-45c7-f576-bd121afbd27a"
      },
      "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": 232,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n\n\n###  Artificial Intelligence\n - Field of understanding and building intelligent entities\n\n### Human vs. rational\n - Some AI try to act like humans\n - Others try to act \"rationally\" by doing the right thing\n\n### Turing test\n -  Human asks written questions to computer which responds with written responses\n - If human interrogator cannot distinguish computer from human, the AI passes\n\n### Methods of testing human thought\n - Intrpspection\n - Psychological experiments\n - Brain imaging\n\n### Syllogisms\n - Patterns for argument structures that always yielded corect conclusions given correct premises\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n\n### Agent\n - An **agent** is anything that perceives and acts in an environment through **sensors** and **actuators**\n - **percept** : data perceived by an agent\n - **percept sequence** : complete history of percepts\n - **agent function** : function from the percept sequence to an action\n - **agent program** : implementation of the agent function in a physical system\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n\n\n\n## AIMA 2.1 Agents and Environments\n\n\n ### Rational agent\n - An agent that works towards the best outcome or best expected outcome\n\n### Limited rationality\n - Taking good actions with limits on computation time\n\n### Value alighnment problem\n - Problem of making the goals of the machine aligned with those of the human\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n\n### Rational agent\n - **rational agent** : selects actions to maximize performance measure based on **prior knowledge** and **current percept sequence**\n\n### Omniscience\n - **omniscience** is knowing the *actual* outcome of actions\n\n### Autonomy \n - **autonomy** is the ability of an agent to learn from its environment/percepts rather than relying on knowledge of its designer\n\n\n\n## AIMA 2.3 The Nature of Environments\n\n\n### Task environments\n - A rational agent solves a \"problem\" defined by a task environment\n\n### Components of task environment (PEAS)\n - Performance\n     - measured by a **performance measure**\n - Environment\n     - E.g. roads\n - Actuators\n     - e.g. control over steering and breaking\n - Sensors\n     - e.g video cameras so the autoamated taxi can see\n\n\n### Fully observable vs. partially observable\n - Noise or lack of sensors can lead to partially observable environments\n\n### Single-agent vs. Multi-agent\n - In multi-agents environment, the behavior of one agent depends on the behavior of the other \n - Multi-agent environments can be competitve or cooperative\n\n### Deterministic vs. nondeterministic\n - A deterministic environment is one in which the next state of the environment is completely determined by the current state and teh action executed by the agent(s)\n - Otherwise, it is non-deterministic\n - A partially observable environment could *appear* nondeterministic\n\n### Stochastic\n - Nondeterministic environment where the probabilities of each event are explicitly known (e.g. Poker)\n\n### Episodic vs. Sequential\n - In episodic environments, each state is completely independent of future states\n - In sequential environments an action at time $t$ can have an impact on all states/decisions at times > $t$\n\n### Static vs. Dynamic\n - A dynamic is an environment that can change *while the agent is deliberating*\n - Otherwise, it's static\n - Semidynamic environments are those where the agents **performance score** can change over time even if the environment does not\n\n### Discrete vs. continuous\n - Distinction can be made w.r.t. the state, the time, and the percepts and actions\n - Chess is discrete in terms of states, percepts, and actions\n - Taxi driving is continuous state and contintuous time problem. Input from digital cameras is *technically* discrete but we may consider it continuous\n\n### Known vs. unknown\n - Refers not to the environment itself but to the agent's (or designer's) state of knowledge about the \"laws of physics\" of the environment\n - In a known environment, the outcomes (or outcome probabilities for nondeterministic environment) for all actions is given\n - If environment is unknown the agent will have to *learn* in order to make good decisions\n\n### Environment class\n - Describes a set of environments populated by adjusting hyperparameters\n - e.g. a single class of taxi environment could be populated with different values for traffic, lighting, and weather conditions\n\n\n\n## AIMA 2.4 The Structure of Agents\n\n\n### Structure of agents\n - Job of AI is to implement **agent program** that implements the agent function\n - **agent architecture** is the computing device with physical sensors and actuators $$agent = architecture + program$$\n - The agent program takes only the current percept while the agent function takes entire history\n \n### Four basic kinds of agents\n - **Simple reflex agents**\n     - select actions on the *current percept* only\n - **Model-based reflex agents**\n    - maintains internal state\n    - **transition model** : updates internal state\n    - **sensor model**: encodes the state of the world from info contained in percepts\n - **Goal-based agents**\n     - Agent needs current state description + description of goal\n - **Utility-based agents**\n     - **utility function** that can evaluate eutility of different states/actions\n     - may optimize **expected utility** in non-deterministic environments\n\n### Model-free agent\n - Can learn what action is best in a particular situation without ever learning exactly how that action changes the environment\n\n### Learning agents\n - **learning agents** have four components\n     - **learning element** : responsible for making improvements\n     - **performance element** : responsible for selecting external actions\n     - ** critic ** : gives feedback to the learning element on how the agent is doing\n     - **problem generator** : responsible for suggesting actions that will lead to new and informative experiences\n\n### Representations of environments\n - **atomic representation** : each state of the world is indivisible with no structure\n - **factored representation** : splits up each state into a fixed set of **variables/attributes** each of which can have a **value**\n - **structured representation** : Relationships between pairs of objects can be described explicitly\n\n### Localist vs. distributed representation\n - **Localist representation** has one-to-one mapping of concepts and memory locations\n - In **distributeed representation**, each memory location is part of the representation of multiple different concepts\n     - Each concept represents a point in multidimensional space\n\n\n\n\n## Module 1 Lecture Notes\n\n \n\n## Module 1 Definitions\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 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Each definition should be at most 20 words long.\n",
        "module2_definitions = {\n",
        "\"mutability\" : \"your definition here\",\n",
        "}"
      ],
      "execution_count": 233,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 209
        },
        "outputId": "c3788869-dfac-48b8-cc2f-fc362758152e"
      },
      "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": 234,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\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",
        "\n",
        "### Goal formulation\n",
        "  - Goals limit actions considered by agent\n",
        "\n",
        "### Problem formulation\n",
        " - Agent finds way to describe states/actions to reach their goal\n",
        "\n",
        "### Search\n",
        " - Before performing action, agent simulates outcomes of differnt actions until goal\n",
        "\n",
        "### Open-loop vs. closed-loop\n",
        " - Open loop : for correct model, agent can decide on solution then ignore percepts while executing\n",
        " - Closed-loop : agent monitors percepts while executing and adjusts future actions accordingly\n",
        "\n",
        "### Problem:\n",
        "  - A set of possible *states* that the environment can be in called *state space*\n",
        "  - Initial state\n",
        "  - One or more goal states\n",
        "  - For any state $s$, we have a set of actions $A$\n",
        "  - Transition model : takes a state $s$ and action $a$ and returns a new state $s'$\n",
        "  - Action cost function : Computes cost of applying $a$ to state $s$ to reach $s'$\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "chapter3_2 =\"\"\"\n",
        "\n",
        "### Standardized Problem\n",
        " -  Meant to demonstrate problem solving methods because the problem has an exact description\n",
        "     - Can be used for benchmarking algorithms\n",
        "  \n",
        "### Real-world problem\n",
        " - People actually use solutions to these problems\n",
        " - Formulation is idiosyncratic and not standardized\n",
        " - e.g. all robots may have slightly different sensors\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "\n",
        "chapter3_3 = \"\"\"\n",
        "\n",
        "## Performance Measures\n",
        " - COMPLETENESS\n",
        " - COST OPTIMALITY\n",
        " - TIME COMPLEXITY\n",
        " - SPACE COMPLEXITY\n",
        "\n",
        "### Tree vs. Graph Search\n",
        " - Graph search checks for redundant paths, tree search doesn't\n",
        "\n",
        "\n",
        "### Best-first search\n",
        " - Choose node $n$ with minimum value of some evaluation function $f(n)$\n",
        "\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "chapter3_4 = \"\"\"\n",
        "\n",
        "### BFS\n",
        "  - Time and space are $O(b^d)$ for branching factor b and depth d\n",
        "\n",
        "### Dijsktra\n",
        "  - Uniform-cost search \n",
        "  - Time and space complexity is $O(B^{1 + ({\\\\lfloor} C^* / \\epsilon {\\\\rfloor} }))$\n",
        "  - this can be much more than $b^d$\n",
        "\n",
        "### DFS\n",
        " - ALways expands the deepest node in the frontier\n",
        " - Usually implemnted as a tree-like search rather than graph search\n",
        " - DFS can get stuck in infinite loops and can get stuck going down an infinite path\n",
        "\n",
        "### Backtracking search\n",
        " - Generates only one successor at a time rather than all successors\n",
        " - Each partially expanded node remembers which successor to generate next\n",
        " - Successors are generated by modifying the current state description directly rather than allocation memory for a brand-new state\n",
        " - Reduces the memory requirements to just one state description and a oath of $O(m)$ actions\n",
        " - Big savings over $O(bm)$ states for DFS\n",
        "\n",
        "### Depth-limited search \n",
        " - Supply a depth limit $l$ and treat all nodes at depth $l$ as if they had no successors\n",
        " - Time complexity $O(b^l)$ and space complexity $O(bl)$\n",
        " - Fails when $l$ is too small\n",
        "\n",
        "### Iterative deepening\n",
        " - Uses depth limited described above sequentially for each $l = 0, 1, 2, \\dots$ until solution\n",
        " - Memory : $O(bd)$ when there is a solution and $O(bm)$ on finite state spaces with no soln. \n",
        " - Time complexity: $O(b^d)$ when soln. $O(b^m)$ otherwise\n",
        "\n",
        "### Bidirectional search\n",
        " - Searches forward from the initial state and backwards from goal state(s) at same time\n",
        " - Motivation: $b^{d/2} + b^{d/2} << b^d$\n",
        " - Expands the node with minimum value of the evaluation function across *either* frontier\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module3_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "}\n",
        "\n"
      ],
      "execution_count": 235,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "5f41c134-ee26-4082-befe-984252dd4cb2"
      },
      "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": 236,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n\n### Goal formulation\n  - Goals limit actions considered by agent\n\n### Problem formulation\n - Agent finds way to describe states/actions to reach their goal\n\n### Search\n - Before performing action, agent simulates outcomes of differnt actions until goal\n\n### Open-loop vs. closed-loop\n - Open loop : for correct model, agent can decide on solution then ignore percepts while executing\n - Closed-loop : agent monitors percepts while executing and adjusts future actions accordingly\n\n### Problem:\n  - A set of possible *states* that the environment can be in called *state space*\n  - Initial state\n  - One or more goal states\n  - For any state $s$, we have a set of actions $A$\n  - Transition model : takes a state $s$ and action $a$ and returns a new state $s'$\n  - Action cost function : Computes cost of applying $a$ to state $s$ to reach $s'$\n\n\n## AIMA Chapter 3.2 Example Problems\n\n\n### Standardized Problem\n -  Meant to demonstrate problem solving methods because the problem has an exact description\n     - Can be used for benchmarking algorithms\n  \n### Real-world problem\n - People actually use solutions to these problems\n - Formulation is idiosyncratic and not standardized\n - e.g. all robots may have slightly different sensors\n\n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n\n## Performance Measures\n - COMPLETENESS\n - COST OPTIMALITY\n - TIME COMPLEXITY\n - SPACE COMPLEXITY\n\n### Tree vs. Graph Search\n - Graph search checks for redundant paths, tree search doesn't\n\n\n### Best-first search\n - Choose node $n$ with minimum value of some evaluation function $f(n)$\n\n\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n\n### BFS\n  - Time and space are $O(b^d)$ for branching factor b and depth d\n\n### Dijsktra\n  - Uniform-cost search \n  - Time and space complexity is $O(B^{1 + ({\\lfloor} C^* / \\epsilon {\\rfloor} }))$\n  - this can be much more than $b^d$\n\n### DFS\n - ALways expands the deepest node in the frontier\n - Usually implemnted as a tree-like search rather than graph search\n - DFS can get stuck in infinite loops and can get stuck going down an infinite path\n\n### Backtracking search\n - Generates only one successor at a time rather than all successors\n - Each partially expanded node remembers which successor to generate next\n - Successors are generated by modifying the current state description directly rather than allocation memory for a brand-new state\n - Reduces the memory requirements to just one state description and a oath of $O(m)$ actions\n - Big savings over $O(bm)$ states for DFS\n\n### Depth-limited search \n - Supply a depth limit $l$ and treat all nodes at depth $l$ as if they had no successors\n - Time complexity $O(b^l)$ and space complexity $O(bl)$\n - Fails when $l$ is too small\n\n### Iterative deepening\n - Uses depth limited described above sequentially for each $l = 0, 1, 2, \\dots$ until solution\n - Memory : $O(bd)$ when there is a solution and $O(bm)$ on finite state spaces with no soln. \n - Time complexity: $O(b^d)$ when soln. $O(b^m)$ otherwise\n\n### Bidirectional search\n - Searches forward from the initial state and backwards from goal state(s) at same time\n - Motivation: $b^{d/2} + b^{d/2} << b^d$\n - Expands the node with minimum value of the evaluation function across *either* frontier\n\n\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via 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 = \"\"\"\n",
        "\n",
        "### Greedy best-first search\n",
        " - Expands nodes with minimal $h(n)$\n",
        "\n",
        "### A* search\n",
        " - Expands nodes with minimal $f(n) = g(n) + h(n)$ where $g(n)$ is true cost and $h(n)$ is heuristic\n",
        " - optimal for \"admissible/optimistic\" $h$ that **never overestimate** the true cost to reach goal\n",
        "\n",
        "### Consistency\n",
        " - for every node $n$ and every successor $n'$ of $n$ generated by $a$:\n",
        "   - $h(n) \\leq c(n, a, n') + h(n')$\n",
        " - form of the triangle inequality\n",
        " - consistent -> admissible but NOT vice versa\n",
        " - consistent heuristic adds states to frontier at most once\n",
        "\n",
        "Inadmissiable heuristics can still be optimal if h(n) admissible for nodes on optimal path\n",
        "OR if h(n) never overestimates cost by more than $C_2 - C^*$ where C_2 is second-best cost\n",
        "\n",
        "### Surely expanded nodes\n",
        "  - All nodes on a path with $f(n) < C^*$\n",
        "\n",
        "### Optimally efficient\n",
        "  - A* with consistent heuristic is optimally efficient\n",
        "    - Any algorithm with same heuristic info must expand all nodes that are surely expanded by A*\n",
        "\n",
        "### Inadmissible heuristics and weighted A*\n",
        " - Engineers may opt to use inadmissble heuristics that risk overestimating cost but prune more nodes\n",
        " - Weighted A* search uses $f(n) = g(n) + W * h(n)$ where W > 1, which can make the effective heuristic inadmissible\n",
        " - Other algorithms described as Weighted A*\n",
        "     - A* is $W = 1$\n",
        "     - Uniform cost is $W = 0$\n",
        "     - Greedy best-first is $W = \\infty$\n",
        " - Weighted A* is bounded suboptimal search\n",
        "\n",
        "### Bounded suboptimal search\n",
        " - Solution guarenteed to be within constant factor W of optimal cost\n",
        "\n",
        "### Unbounded-cost search\n",
        " - Cost doesn't matter as long as we can find soln. quickly\n",
        " - e.g. speedy search which is greedy best-first search that uses the heuristic \"number of actions to reach goal\"\n",
        "\n",
        "### Memory-bounded search\n",
        " - A* uses lots of memory\n",
        " - Can remove states from reached if they can be proved unusable\n",
        " - Keep counts of number of times a state has been reached, remove when it's been reached by all its incoming neighbors\n",
        "\n",
        "### Beam search\n",
        " -  Keeps only $k$ nodes with the best $f$-scores\n",
        " - Incomplete and suboptimal but good for memory and speed\n",
        "\n",
        "### Iterative-deepening A* search (IDA*)\n",
        " - Analog of IDDFS but for A* instead of DFS\n",
        " - Don't need to keep reached states in memory, slight cost of repeated states\n",
        "\n",
        "### Recursive best-first search (RBFS)\n",
        " - Similar to DFS but uses $f_{limit}$ to track the best alternative path available from ancestor\n",
        " - If we exceed the limit, recursion backtracks to the alternative path\n",
        " - As we backtrack, we remember the best f-value of the children of each node\n",
        "\n",
        "\n",
        "### MA* and SMA*\n",
        " - Allow algo to use all memory\n",
        " - SMA* expands the best leaf until memory is full then always drops the *worst* leaf node\n",
        "     - newer > older\n",
        " - experiences thrashing on hard problems. Memory constraint -> intractable runtime\n",
        "\"\"\"\n",
        "\n",
        "chapter3_6 = \"\"\"\n",
        "\n",
        "### Effective branching factor $b^*$\n",
        " - $N$ is nodes generates then tree of depth $d$ has $b^*$ defined as $$N + 1= 1 + b^* + (b^*)^2 + \\dots + (b^*)d$$\n",
        "\n",
        "### Relaxed problem\n",
        " - Problem with fewer restrictions on actions is called relaxed problem\n",
        " - New state-space graph is *supergraph*\n",
        " - Optimal soln. to a relaxed problem is admissible heuristic for original problem\n",
        "\n",
        "### Combining heuristics\n",
        " -  Given $k$ admissible heuristics $h_1, \\dots, h_k$ we can make a better heuristic $h^*$ $$h^*(n) = \\max \\{h_1(n), \\dots, h_k(n) \\}$$\n",
        "\n",
        "\n",
        "### Pattern database\n",
        " - Store the exact solution costs for every possible subproblem instance\n",
        "\n",
        "### Disjoint pattern database\n",
        " - Instead of storing the total cost of the subproblem store a meaningful value that is a disjoint fraction of the subcost\n",
        " - For example, the cost of the moves *only involving* tiles 1-2-3-4 and add this to cost only involving 4-5-6-7\n",
        " - \n",
        "\n",
        "### Landmarks\n",
        " - Most important trick to doing otherwise intractable problems (such as google maps finding route of tens of millions of vertices in milliseconds) is precomputation\n",
        " - Precomputation takes a vry long time, but we do it once and amortize it over billions of user search requests\n",
        " - Choose a few (10 or 20) landmark points from the vertices\n",
        " - For each landmark $L$ and eachother vertex $v$ in the graph, compute and store $C*(v, L)$ the exact cost of $v$ to $L$\n",
        " - Efficient (but inadmissble) heuristic: minimum over all landmarks of cost of getting from current node to landmark and then goal $$h_L(n) = \\min_{L \\in Landmarks} C^*(n, L) + C^*(L, goal)$$\n",
        " - Efficient (AND admissible) *differential heuristic*: $$h_{DH}(n) = \\max_{L \\in Landmarks} | C^*(n, L) - C^*(goal, L)| $$\n",
        " - The differential heuristic says consider the path from $n$ to landmark $L$ beyond goal, and then subtract the distance from the goal to $L$\n",
        "\n",
        "\n",
        "### Shortcuts\n",
        " - Multi-action paths described as a new single edge\n",
        " - For instance, we could create shrotcusts between all the 100 biggest cities in the US\n",
        "\n",
        "\n",
        "### Metalevel state space\n",
        " - Each state in the metalevle state space captures the internal computational state of a program that is searching in an ordinary state space\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\"\n",
        "\"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "# \"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 237,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "cellView": "form",
        "outputId": "f159e034-143f-4275-f10e-fb8ac2c950dd"
      },
      "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": 238,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n\n### Greedy best-first search\n - Expands nodes with minimal $h(n)$\n\n### A* search\n - Expands nodes with minimal $f(n) = g(n) + h(n)$ where $g(n)$ is true cost and $h(n)$ is heuristic\n - optimal for \"admissible/optimistic\" $h$ that **never overestimate** the true cost to reach goal\n\n### Consistency\n - for every node $n$ and every successor $n'$ of $n$ generated by $a$:\n   - $h(n) \\leq c(n, a, n') + h(n')$\n - form of the triangle inequality\n - consistent -> admissible but NOT vice versa\n - consistent heuristic adds states to frontier at most once\n\nInadmissiable heuristics can still be optimal if h(n) admissible for nodes on optimal path\nOR if h(n) never overestimates cost by more than $C_2 - C^*$ where C_2 is second-best cost\n\n### Surely expanded nodes\n  - All nodes on a path with $f(n) < C^*$\n\n### Optimally efficient\n  - A* with consistent heuristic is optimally efficient\n    - Any algorithm with same heuristic info must expand all nodes that are surely expanded by A*\n\n### Inadmissible heuristics and weighted A*\n - Engineers may opt to use inadmissble heuristics that risk overestimating cost but prune more nodes\n - Weighted A* search uses $f(n) = g(n) + W * h(n)$ where W > 1, which can make the effective heuristic inadmissible\n - Other algorithms described as Weighted A*\n     - A* is $W = 1$\n     - Uniform cost is $W = 0$\n     - Greedy best-first is $W = \\infty$\n - Weighted A* is bounded suboptimal search\n\n### Bounded suboptimal search\n - Solution guarenteed to be within constant factor W of optimal cost\n\n### Unbounded-cost search\n - Cost doesn't matter as long as we can find soln. quickly\n - e.g. speedy search which is greedy best-first search that uses the heuristic \"number of actions to reach goal\"\n\n### Memory-bounded search\n - A* uses lots of memory\n - Can remove states from reached if they can be proved unusable\n - Keep counts of number of times a state has been reached, remove when it's been reached by all its incoming neighbors\n\n### Beam search\n -  Keeps only $k$ nodes with the best $f$-scores\n - Incomplete and suboptimal but good for memory and speed\n\n### Iterative-deepening A* search (IDA*)\n - Analog of IDDFS but for A* instead of DFS\n - Don't need to keep reached states in memory, slight cost of repeated states\n\n### Recursive best-first search (RBFS)\n - Similar to DFS but uses $f_{limit}$ to track the best alternative path available from ancestor\n - If we exceed the limit, recursion backtracks to the alternative path\n - As we backtrack, we remember the best f-value of the children of each node\n\n\n### MA* and SMA*\n - Allow algo to use all memory\n - SMA* expands the best leaf until memory is full then always drops the *worst* leaf node\n     - newer > older\n - experiences thrashing on hard problems. Memory constraint -> intractable runtime\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n\n### Effective branching factor $b^*$\n - $N$ is nodes generates then tree of depth $d$ has $b^*$ defined as $$N + 1= 1 + b^* + (b^*)^2 + \\dots + (b^*)d$$\n\n### Relaxed problem\n - Problem with fewer restrictions on actions is called relaxed problem\n - New state-space graph is *supergraph*\n - Optimal soln. to a relaxed problem is admissible heuristic for original problem\n\n### Combining heuristics\n -  Given $k$ admissible heuristics $h_1, \\dots, h_k$ we can make a better heuristic $h^*$ $$h^*(n) = \\max \\{h_1(n), \\dots, h_k(n) \\}$$\n\n\n### Pattern database\n - Store the exact solution costs for every possible subproblem instance\n\n### Disjoint pattern database\n - Instead of storing the total cost of the subproblem store a meaningful value that is a disjoint fraction of the subcost\n - For example, the cost of the moves *only involving* tiles 1-2-3-4 and add this to cost only involving 4-5-6-7\n - \n\n### Landmarks\n - Most important trick to doing otherwise intractable problems (such as google maps finding route of tens of millions of vertices in milliseconds) is precomputation\n - Precomputation takes a vry long time, but we do it once and amortize it over billions of user search requests\n - Choose a few (10 or 20) landmark points from the vertices\n - For each landmark $L$ and eachother vertex $v$ in the graph, compute and store $C*(v, L)$ the exact cost of $v$ to $L$\n - Efficient (but inadmissble) heuristic: minimum over all landmarks of cost of getting from current node to landmark and then goal $$h_L(n) = \\min_{L \\in Landmarks} C^*(n, L) + C^*(L, goal)$$\n - Efficient (AND admissible) *differential heuristic*: $$h_{DH}(n) = \\max_{L \\in Landmarks} | C^*(n, L) - C^*(goal, L)| $$\n - The differential heuristic says consider the path from $n$ to landmark $L$ beyond goal, and then subtract the distance from the goal to $L$\n\n\n### Shortcuts\n - Multi-action paths described as a new single edge\n - For instance, we could create shrotcusts between all the 100 biggest cities in the US\n\n\n### Metalevel state space\n - Each state in the metalevle state space captures the internal computational state of a program that is searching in an ordinary state space\n\n\n\n## Module 4 Lecture Notes\n\n\n\n## Module 4 Definitions\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 = \"\"\"\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter5_2 = \"\"\"\n",
        " \n",
        "### Minimax search\n",
        " - Finds the minimax value of each state in the tree\n",
        " - Minimax value is the utility (for MAX) of being in the state assuming both players play optimally\n",
        " - Depth-first exploration \n",
        " - Can augment with a vector of utilities when the number of players exceeds 2\n",
        " \n",
        "### Alpha-beta pruning\n",
        "  - Maintains alpha which is lower bound on utility for max and beta which is upper bound\n",
        "  - Max player ignores payoffs less than alpha and min player ignores payoffs greater than beta\n",
        "  - Depth first, we traverse a single long path, then we go all teh way back to the top and propagate information\n",
        "  - Efficiency depends on order that we explore states\\\n",
        "  - Optimally $O(b^{m/2})$ instead of $O(B^m)$\n",
        "\n",
        "### Dynamic move order schemes and killer moves\n",
        " - Another improvement to alpha-beta would be to add dynamic move-ordering schemes such as trying those that were found to be best int he past\n",
        " - Past can be a previous move or a previous exploration of current move with iterative deepening\n",
        " - The best move is known as a *killer move* and trying them first is known as **killer move heuristic**\n",
        " \n",
        "\n",
        "### Transpositions\n",
        " -  Different permutations of move sequences that end up in the same position\n",
        " - Can be addressed with *transposition table*\n",
        "\n",
        "### Type A vs. Type B\n",
        " - Type A strategy considers *all* moves to a certain depth and then uses a heuristic eval function\n",
        " - Type B strategy ignores moves that look bad and follows promising lines \"as far as possible\"\n",
        " - Chess typically uses Type A while Go uses type B (though alpha-zero uses type B)\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter5_3 = \"\"\"\n",
        "\n",
        "### Heuristic ALpha-Beta Tree Search\n",
        " - Cut off search early and apply a heuristic evaluation function to states treating nonterminal nodes as terminal\n",
        " - Terminal test replaced with *cutoff test* which returns true based on some properties (but all terminal states return true)\n",
        "\n",
        "### Evaluation function\n",
        " - Heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state $s$ to player $p$\n",
        " - If p is a terminal state, EVAL(s, p) = UTILITY(s, p)\n",
        " - Most eval functions calculate various *features* of the state such as the counts of each piece for each side in chess\n",
        " - Material value in chess is a type of *weighted linear function* since we sum up the values across the state\n",
        "\n",
        "### Cutting off search\n",
        " - Replace terminal test with cutoff test\n",
        " - May also track depth d and cut off for all nodes beyond depth d (iterative deepening can help too)\n",
        "\n",
        "### Quisence\n",
        " - A state is quiescent if there are no pending moves (such as capturing a queen) that would wildly swing the evaluation\n",
        " - For nonquiescent positions, the IS-CUTOFF returns false and search continues until quiescent positions are reached\n",
        " - *quisence search* can be restricted to only consider certain moves such as captures to quickly resolve uncertainties\n",
        "\n",
        "### Horizon effect\n",
        " - Problem when we stall inevitable risk and lose more\n",
        " - A *singular extension* allows moves that are \"clearly better\" than all other moves in a given position to be played after the horizon\n",
        "     - Counters delaying tactics (that sacrifice pointlessly) because after applying these tactics we allow these \"singular extensions\" to play out\n",
        "\n",
        "\n",
        "### Forward pruning\n",
        " - Prunes moves that appear to be poor moves but might possibly be good ones\n",
        " - That is, to even be considered, a move must be at least as good as some threshold\n",
        " - One approach to forward pruning is *beam search* which is to consider a beam of only the $n$ best (according to heuristic) moves\n",
        "\n",
        "### ProbCut\n",
        " - Alpha-beta prunes moves that are *definitely* outside the window, and ProbCut removes moves that are *probably* outside the window\n",
        "\n",
        "### Table lookup\n",
        " - Employed by chess programs to play moves and the opening and ending of games\n",
        " - *Retrograde* minimax search\n",
        "     - Work backwards from the end states and figure out which states are \"forced wins\" and mark them as wins themselves\n",
        "     - Repeat\n",
        " - In chess there are lookup tables for all endings with seven or fewer pieces\n",
        "\n",
        "\n",
        "### Monte-Carlo tree search\n",
        " - Instead of a heuristic evaluation function, perform many rollouts from current state\n",
        " - The value of the heuristic is the proportion of wins for the player in question\n",
        " - *payoff policy* biases towards good moves\n",
        "     - NNs or other heuristics used\n",
        " - *Pure MCTS* performs N simulations from the current state\n",
        " - *selection policy* that focuses search on the important parts of the game tree\n",
        "     - *exploration* vs. *exploitation*\n",
        " - *UCT* has been very effective\n",
        "\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter5_5 = \"\"\"\n",
        "### Stochastic games\n",
        " - Players know what moves can be made with respect to each random outcome but do not know result of random outcome\n",
        "     - In backgammon, the moves depend on the result of the roll\n",
        " - We address this by including chance nodes in the tree between decision nodes for MAX and MIN\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\"\n",
        "\n",
        "### Decision network (AKA influence diagram)\n",
        " - Extends Bayesian networks by incorporation actions and utilities\n",
        "\n",
        "### Maximum expected utility (MEU)\n",
        " - Agent shuld choose action to maximize expected utility\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter16_2 = \"\"\"\n",
        "\n",
        "### Notation\n",
        " - $A \\succ B$  the agent prefers $A$ to $B$\n",
        " - $A \\sim B$  the agent is indifferent between $A$ and $B$\n",
        " - $A \\succeq B$ agent prefers $A$ over $B$ or is indifferent\n",
        "\n",
        "### Constraints on rational preferences\n",
        " - ORDERABILITY: Given two outcomes, an agent must prefer one or think of them as equal\n",
        " - TRANSITIVITY: Given three outcomes, if $ A \\succ B$ and $B \\succ C$ then $A \\succ C$\n",
        " - CONTINUITY: If some outcome $B$ is in between $A$ and $C$ in preference, then there exists a probability $p$ such that a rational agent will be indifferent between getting B for sure and a lottery yielding A with probability $p$ and $C$ with probability $1-p$\n",
        " - SUBSTITUTABILITY: If An egent is indifferent between $A$ and $B$, then agent also indifferent in two more complex lotteries with only differnce being $A$ sub for $B$\n",
        " - MONOTONICITY: For any pair of lotteries with only two outcomes, if an agent prefers $A$ to $B$ then they must prefer the lottery with higher probability on $A$\n",
        " - DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability\n",
        "\n",
        "\n",
        "### Existence of a utility function\n",
        " -  If an agent's preferences obey the axioms of utility, then there existsa a function $U$ such that $U(A) > U(B)$ iff $A$ is prefered to $B$, and $U(A) = U(B)$ iff agent is indiffernt between $A$ and $B$\n",
        "\n",
        "### Value function (ordinal utility function)\n",
        " - Function with enough information to convey ordered preference ranking on states\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter16_3 = \"\"\" \n",
        "\n",
        "### Preference elicitation\n",
        " - Process of presenting choices to a human to figure out their utility function\n",
        "\n",
        "### Evaluating life\n",
        " - Value of a statistical life approx $10 million\n",
        " - Micromort : a one in a million chance of death\n",
        " - QALY : quality adjusted life year\n",
        "\n",
        "### Monotonic preference (for money)\n",
        " - All other things being equal, people prefer more money to less\n",
        "\n",
        "\n",
        "### Normative vs. descriptive theory\n",
        " - Normative theory describes how agents *should* act while descriptive theory describes how agents *do* act\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\"\n",
        "\n",
        " \n",
        "\"\"\"\n",
        "\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 239,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "4e7bbeab-97be-4eac-dbbc-f3a2a04b779e"
      },
      "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": 240,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n \n### Minimax search\n - Finds the minimax value of each state in the tree\n - Minimax value is the utility (for MAX) of being in the state assuming both players play optimally\n - Depth-first exploration \n - Can augment with a vector of utilities when the number of players exceeds 2\n \n### Alpha-beta pruning\n  - Maintains alpha which is lower bound on utility for max and beta which is upper bound\n  - Max player ignores payoffs less than alpha and min player ignores payoffs greater than beta\n  - Depth first, we traverse a single long path, then we go all teh way back to the top and propagate information\n  - Efficiency depends on order that we explore states  - Optimally $O(b^{m/2})$ instead of $O(B^m)$\n\n### Dynamic move order schemes and killer moves\n - Another improvement to alpha-beta would be to add dynamic move-ordering schemes such as trying those that were found to be best int he past\n - Past can be a previous move or a previous exploration of current move with iterative deepening\n - The best move is known as a *killer move* and trying them first is known as **killer move heuristic**\n \n\n### Transpositions\n -  Different permutations of move sequences that end up in the same position\n - Can be addressed with *transposition table*\n\n### Type A vs. Type B\n - Type A strategy considers *all* moves to a certain depth and then uses a heuristic eval function\n - Type B strategy ignores moves that look bad and follows promising lines \"as far as possible\"\n - Chess typically uses Type A while Go uses type B (though alpha-zero uses type B)\n\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n### Heuristic ALpha-Beta Tree Search\n - Cut off search early and apply a heuristic evaluation function to states treating nonterminal nodes as terminal\n - Terminal test replaced with *cutoff test* which returns true based on some properties (but all terminal states return true)\n\n### Evaluation function\n - Heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state $s$ to player $p$\n - If p is a terminal state, EVAL(s, p) = UTILITY(s, p)\n - Most eval functions calculate various *features* of the state such as the counts of each piece for each side in chess\n - Material value in chess is a type of *weighted linear function* since we sum up the values across the state\n\n### Cutting off search\n - Replace terminal test with cutoff test\n - May also track depth d and cut off for all nodes beyond depth d (iterative deepening can help too)\n\n### Quisence\n - A state is quiescent if there are no pending moves (such as capturing a queen) that would wildly swing the evaluation\n - For nonquiescent positions, the IS-CUTOFF returns false and search continues until quiescent positions are reached\n - *quisence search* can be restricted to only consider certain moves such as captures to quickly resolve uncertainties\n\n### Horizon effect\n - Problem when we stall inevitable risk and lose more\n - A *singular extension* allows moves that are \"clearly better\" than all other moves in a given position to be played after the horizon\n     - Counters delaying tactics (that sacrifice pointlessly) because after applying these tactics we allow these \"singular extensions\" to play out\n\n\n### Forward pruning\n - Prunes moves that appear to be poor moves but might possibly be good ones\n - That is, to even be considered, a move must be at least as good as some threshold\n - One approach to forward pruning is *beam search* which is to consider a beam of only the $n$ best (according to heuristic) moves\n\n### ProbCut\n - Alpha-beta prunes moves that are *definitely* outside the window, and ProbCut removes moves that are *probably* outside the window\n\n### Table lookup\n - Employed by chess programs to play moves and the opening and ending of games\n - *Retrograde* minimax search\n     - Work backwards from the end states and figure out which states are \"forced wins\" and mark them as wins themselves\n     - Repeat\n - In chess there are lookup tables for all endings with seven or fewer pieces\n\n\n### Monte-Carlo tree search\n - Instead of a heuristic evaluation function, perform many rollouts from current state\n - The value of the heuristic is the proportion of wins for the player in question\n - *payoff policy* biases towards good moves\n     - NNs or other heuristics used\n - *Pure MCTS* performs N simulations from the current state\n - *selection policy* that focuses search on the important parts of the game tree\n     - *exploration* vs. *exploitation*\n - *UCT* has been very effective\n\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n### Stochastic games\n - Players know what moves can be made with respect to each random outcome but do not know result of random outcome\n     - In backgammon, the moves depend on the result of the roll\n - We address this by including chance nodes in the tree between decision nodes for MAX and MIN\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n\n### Decision network (AKA influence diagram)\n - Extends Bayesian networks by incorporation actions and utilities\n\n### Maximum expected utility (MEU)\n - Agent shuld choose action to maximize expected utility\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n\n### Notation\n - $A \\succ B$  the agent prefers $A$ to $B$\n - $A \\sim B$  the agent is indifferent between $A$ and $B$\n - $A \\succeq B$ agent prefers $A$ over $B$ or is indifferent\n\n### Constraints on rational preferences\n - ORDERABILITY: Given two outcomes, an agent must prefer one or think of them as equal\n - TRANSITIVITY: Given three outcomes, if $ A \\succ B$ and $B \\succ C$ then $A \\succ C$\n - CONTINUITY: If some outcome $B$ is in between $A$ and $C$ in preference, then there exists a probability $p$ such that a rational agent will be indifferent between getting B for sure and a lottery yielding A with probability $p$ and $C$ with probability $1-p$\n - SUBSTITUTABILITY: If An egent is indifferent between $A$ and $B$, then agent also indifferent in two more complex lotteries with only differnce being $A$ sub for $B$\n - MONOTONICITY: For any pair of lotteries with only two outcomes, if an agent prefers $A$ to $B$ then they must prefer the lottery with higher probability on $A$\n - DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability\n\n\n### Existence of a utility function\n -  If an agent's preferences obey the axioms of utility, then there existsa a function $U$ such that $U(A) > U(B)$ iff $A$ is prefered to $B$, and $U(A) = U(B)$ iff agent is indiffernt between $A$ and $B$\n\n### Value function (ordinal utility function)\n - Function with enough information to convey ordered preference ranking on states\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n\n### Preference elicitation\n - Process of presenting choices to a human to figure out their utility function\n\n### Evaluating life\n - Value of a statistical life approx $10 million\n - Micromort : a one in a million chance of death\n - QALY : quality adjusted life year\n\n### Monotonic preference (for money)\n - All other things being equal, people prefer more money to less\n\n\n### Normative vs. descriptive theory\n - Normative theory describes how agents *should* act while descriptive theory describes how agents *do* act\n\n\n\n## Module 5 Lecture Notes\n\n\n \n\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 = \"\"\"\n",
        "\n",
        "### Factored representation of a state\n",
        " - A set of **variables** each of which has a **value**\n",
        " - Problem is solved when each variable has a value that satisfies all constraints on it\n",
        "\n",
        "### CSP Components\n",
        " - $X$ is a set of variables  $\\{X_1, \\dots, X_n\\}$\n",
        " - $D$ is a set of domains, $\\{D_1, \\dots, D_n\\}$ one for each variables\n",
        " - $C$ is a set of constraints that specify allowable combinations of values \n",
        "\n",
        "### Assignments\n",
        " - Giving a value to each variable\n",
        " - **consistent** assignment is one that does not violate constraints\n",
        " - **complete** assignment assigns each variable a value\n",
        " - **solution** to a csp is a consistent, complete assignment\n",
        " - **partial assignment** is one that leaves some variables unassigned\n",
        " - **partial solution** is a partial assignment that is consistent\n",
        " - CSPs are generally NP complete but there are subclasses that can be solved fast\n",
        "\n",
        "\n",
        "### Constraint graph\n",
        " - Each variable gets a node\n",
        " - Edge between variables that have a constraint between them\n",
        " - Constraint hypergraph can capture $n$-ary constraints by having a node denoting the constraint with edges to all variable nodes associated with that constraint\n",
        " - **dual graph** : One variable for each constraint and one binary constraint for each pair of constraints in the original graph that share the same variables\n",
        "\n",
        "### Types of constraints\n",
        " - Precedence constraints\n",
        " - Disjunctive constraints\n",
        "\n",
        "### Types of CSPS\n",
        " - continuous domains e.g. real world stuff like Hubble space telescope\n",
        "     - Linear programming poroblems are the best-known category of continuous-domain CSPs\n",
        " - \n",
        "\n",
        "### Constraint optimization problem\n",
        " - We want not only a feasible solution, but an optimal one that satisfies all constraints\n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter6_2 = r\"\"\" \n",
        "\n",
        "### Constraint propagation\n",
        " - Using the constraints to reduce the number of legal values (i.e. the size of the domain) for a variable\n",
        " - Can use changes to further restrict the values on more variables, and so on\n",
        " - \n",
        "\n",
        "### Local consistency\n",
        " * Node consistency: A variable is **node-consistent** if all values in it's domain satisfy the variable's unary constraints\n",
        " * Arc consistency: A variable is **arc-consistent** if every value in its domain satisfies the variables binary constraints\n",
        "     - $X_i$ is arc-consistent w.r.t. $X_j$ if for every value for $X_i$ in $D_i$ there is some value in $D_j$ that satisfies the binary constraint $(X_i, X_j)$\n",
        " * Path consistency :\n",
        "     * A two-variable set $\\{X_i, X_j\\}$ is path-consistent w.r.t a third variable $X_m$ if, for every assignment  $\\{X_i = a, X_j = b\\}$, there is an assigment to $X_m$ that satisfies the constraints on $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$\n",
        "     - The name refers to the overall consistency of the path from $X_i$ to $X_j$ with $X_m$ in the middle\n",
        " * $k$-consistency : For any set of $k$-1 variables and any consistent assignment to those variables, a consistent value can always be assigned to any $k$th variable\n",
        " * strong $k$-consistency: $k$ consistency holds for all of $k = 1, 2, \\dots, k-1, k$\n",
        "\n",
        "### AC3 Algorithm\n",
        " - put all arcs in queue\n",
        " - pop element $(X_i, X_j)$\n",
        " - for each value in $D_i$, check if there is indeed a corresponding value in $X_j$. If not, remove it from $D_i$\n",
        " - if $D_i$ is now empty, report that the problem is unsatisfiable\n",
        " - if any changes were made to $D_i$ (and not empty), then for all $X_k$ such that there is a constraint $(X_k, X_i)$, add $(X_k, X_i)$ to the queue\n",
        " - continue until queue is empty\n",
        "\n",
        "### Global constraint\n",
        " - Involves an arbitray number of variables\n",
        " - Some global constraints can be handled by special-purpose algorithms that are more efficient\n",
        "\n",
        "### Resource constraint\n",
        " - AKA \"Atmost\" constraint \n",
        " - If we have 10 people to divide into groups, the size of each groups summed is at most 10\n",
        "\n",
        "### Bounds propagation\n",
        " - Domains are represented as upper and lower bounds\n",
        " - Flights $F_1$ and $F_2$ have cpacities 165 and 385 respectively\n",
        "     - Initial domain: $D_1 = [0, 165]$ and $D_2 = [0, 385]$\n",
        "     - New constraint: Need to fly 420 people, i.e. $F_1 + F_2 = 420$\n",
        "     - New domains: $D_1 = [35, 165]$ and $D_2 = [255, 385]$\n",
        " - CSP is *bounds consistent* if for every $X_i$ and both the lower and upper bound values, there exists a value assignment to $Y$ that satissfies the constraint for $X$ and $Y$ for all $Y$\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter6_3 = \"\"\"\n",
        "\n",
        "### Commutativity of assignment\n",
        " - In CSPs, the order that we assign the variables does not matter\n",
        " - So we can consider a single variable at each step in isolation\n",
        " - If the problem is solvable, then SOME assignment for this variable will eventually work no matter what variable we chose\n",
        " \n",
        "\n",
        "### Backtracking search\n",
        " - Choose an unassigned variable\n",
        " - Pick one of the values in its domain and assign it to the variable\n",
        " - Recursively (as in DFS) try to solve the problem under the above assignment\n",
        " - If failure, then backtrack and try a different assigned value (and remove the one we tried from domain)\n",
        "     - If there are no assignments left then return failure\n",
        " - Otherwise, we have a solution\n",
        "\n",
        "### Variable and value ordering\n",
        " - One good way to choose variables is to choose the variable with the *minimum-remaining-values* (MRV)\n",
        "     - Also referred to as \"most-constrained variable\" or \"fail-first\" heuristic because it picks variable most likely to cause a failure soon causing pruning\n",
        "     - If a variable has no legal values, MRV will immediately detect it and return failure\n",
        " - Another heuristic for choosing variables, and tie-breaking MRV is the **degree heuristic**\n",
        "     - Chooses the variable that is involved in largest number of constraints on other unassigned variables\n",
        "     - This reduces the branching factor on future choices because it shrinks the domains of a larger number of variables\n",
        " - To choose a **value** we can use the **least-constraining-value**\n",
        "     - This prefers values taht rule out the fewest choices for the neighboring variables in the constraint graph\n",
        "     - Max flexibility for subsequent assignments\n",
        " - Why is variable fail-first but value selection fail-last?\n",
        "     - Every variable has to be assigned eventually, so we want to fail early on variables to have fewer successful assignments to backtrack over\n",
        "     - For value ordering, we only need one solution, so it makes sense to look for the most likely values first\n",
        "\n",
        "### Forward checking\n",
        " - When a variable $X$ is assigned, forward checking establishes arc consistency for it\n",
        " \n",
        "### Maintaining Arc Consistency (MAC)\n",
        " - After a variable $X_i$ is assigned a value, the `INFERENCE` procedure calls AC-3, but use only arcs $(X_j, X_i)$ for unassigned $X_j$ rather than all arcs\n",
        " - Then AC-3 propagates constraints as normal, if a domain becomes empty we fail\n",
        " - MAC Is strictly more powerful than forward checking because forward checking is the same as MAC at first, but fails to recursively propagate constraints\n",
        "\n",
        "### Types of backtracking search\n",
        " - *Chronological backtracking* is the default that reverts the *most recent decision*\n",
        " - However, we can be smarter by backtracking to a variable that might fix the problem\n",
        " - Keep track of the set of assignments (that occur in search) that are in conflict with some value for $X_i$\n",
        "     - These assignments must be to variables that share a constraint involvig $X_i$\n",
        "     - Call this the **conflict set**\n",
        " - **Backjumping** backtracks to the most recent assignment *in the conflict set*\n",
        " - We can construct the conflict set while forward checking\n",
        "     - If assignment $X = x$ deletes a value from $Y$'s domain, then it should add $X=x$ to $Y$'s conflict set\n",
        "     - If the last value is deleted from $Y$'s domain, then *all* the assignments in the conflict set of Y are added to the conflict set of $X$\n",
        " - Backjumping cannot happen when doing forward checking or MAC because we check for the constraints ahead of time\n",
        " - Deeper concept of coflcit set for a variable $X$:\n",
        "     - The set of preceeding variables that caused $X$, together with any subsequent variables, to hvae no consistent solution\n",
        " - This is called *conflict-directed* backjumping\n",
        "\n",
        "### Constraint learning\n",
        " - Idea of finding a minimum set of variables from the conflict set that causes the problem\n",
        " - This set of variables + value assignments is called a **no-good**\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "chapter6_4 = \"\"\"\n",
        "\n",
        "### Local search for CSPs\n",
        " - Start with a complete but not necessarily consistent assignment\n",
        " - Change the value of a single variable to be closer to a solution\n",
        " - **min-conflict heuristic** : choose the variable/value that leads to the fewest number of conflicts with other variables\n",
        "\n",
        "### Tabu search\n",
        " - Keeping a small list of recently visited states and forbidding the algorithm to return to them\n",
        "\n",
        "### Constraint weighting\n",
        " - Concentrate search on important constraints\n",
        " - All constriants get value 1\n",
        " - At each step, algo chooses variable/value pair to change that will result in lowest total weight of all violated constriants\n",
        " - Weights are adjusted by incrementing the weight of each constraint that is violated by the current assignment\n",
        " - Adds topography to break ties and adds learning by assigning \"difficult\" constraints higher weight\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter6_5 = \"\"\"\n",
        "\n",
        "### Independent subproblems\n",
        " - Connected components of the constraint graph can be solved as independent sub problems\n",
        " \n",
        "### Directional arc consistency\n",
        " - A CSP is directionally arc-consistent for some ordering $X_1, \\dots, X_n$ iff $X_i$ is arc consistent with each $X_j$ for $j > i$.\n",
        "\n",
        "### Tree-structured CSP\n",
        " - Solving tree structured CSP:\n",
        "     - Choose any variable as root\n",
        "     - Choose an ordering of variables such that each variable appears after its parent in the constraint tree\n",
        "     - This is called a *topological sort*\n",
        " - Can make the graph directed arc consistent in $O(n)$ steps each of which compare up to $d$ possible domain values for two variables, so $O(nd^2)$\n",
        "\n",
        "### Cutset conditioning\n",
        " - One way to reduce a constraint graph to tree involves assigning values to some variables so the others form a tree\n",
        " - We need to find a set of deletable nodes that result in a tree, call this a *cycle cutset* $S$\n",
        " - For each possible assignment to variables in $S$ that satifies constraints on $S$\n",
        "     - remove values in remaining variables inconsistent values with this particular assignment\n",
        "     - if the CSP has a solution, return it along with solution for $S$\n",
        " - If cycle cutset has size $c$, then total run time is $O(d^c \\cdot (n - c)d^2)$\n",
        "     - $d^c$ combinations of values for the variables in $S$\n",
        "     - For each combination, solve a tree problem of size $n-c$\n",
        "\n",
        "### Tree decomposition\n",
        " - Alternate way is based on constructing a **tree decomposition** of the constraint graph\n",
        " - Nodes in the new tree are *sets* of variables\n",
        " - Requirements:\n",
        "     - Every variable in original problem appears in at least one node\n",
        "     - If two variables are connected by a constraint in original problem, they must appear together in at least one of the tree nodes\n",
        "     - IF a variable appears in two nodes in the tree it must appar in every node along the path connecting the nodes\n",
        " - Finally apply Tree-CSP-Solver to get solution in $O(n'(d')^2)$ time where $n'$ is number of tree nodes and $d'$ is the size of the largest domain which is a set of tuples of assignments to all variables in that node\n",
        " - **tree width** one less than the size of the largest node\n",
        " - Tree width of a graph is the minium width among all possible tree decompositions\n",
        " - If a graph has tree width $w$ then the problem can be solved in $O(nd^{w+1})$ time given the corresponding tree decomposition\n",
        " - But, finding these decompositions is NP-hard\n",
        "\n",
        "\n",
        "### Comparison\n",
        " - Cutset conditioning has $O(d^c \\cdot (n - c)d^2)$ vs.  $O(nd^{w+1})$ \n",
        " - Given cutset of size $c$, exists tree of width $w < c + 1$ and often far smaller\n",
        " - Runtime of tree decomposition is faster, but much more memory\n",
        " - Cycle-cuset can be performed in linear memory but tree decomposition requires memory exponential in $w$\n",
        "\n",
        "\n",
        "### Value Symmetry and symmetry breaking\n",
        " - *value symmetry* is when there are multiple solutions whose assignments are simply permutations of values for some set of variables\n",
        "     - If the variables were treated as indistinguishable, then all symmetric assignments would be a single assignment to the set of variables\n",
        " - *symmetry-breaking constraints* resolve value symmetry\n",
        "     - For example, we might enforce $X_i < X_j < X_k$ for three values that have value symmetry with each other\n",
        " - NP-hard to eliminate *all* symmetry, but still an important heuristic for \"obvious\" symmetry\n",
        "\"\"\"\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": 241,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "c5d0b6f2-ebdf-4478-a09f-6ba3a6294113"
      },
      "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": 242,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "## WARNING: Your summary of 'AIMA Chapter 6.3 Backtracking Search for CSPs' is too long!\nWARNING: Your summary of 'AIMA Chapter 6.5 The Structure of Problems' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n\n### Factored representation of a state\n - A set of **variables** each of which has a **value**\n - Problem is solved when each variable has a value that satisfies all constraints on it\n\n### CSP Components\n - $X$ is a set of variables  $\\{X_1, \\dots, X_n\\}$\n - $D$ is a set of domains, $\\{D_1, \\dots, D_n\\}$ one for each variables\n - $C$ is a set of constraints that specify allowable combinations of values \n\n### Assignments\n - Giving a value to each variable\n - **consistent** assignment is one that does not violate constraints\n - **complete** assignment assigns each variable a value\n - **solution** to a csp is a consistent, complete assignment\n - **partial assignment** is one that leaves some variables unassigned\n - **partial solution** is a partial assignment that is consistent\n - CSPs are generally NP complete but there are subclasses that can be solved fast\n\n\n### Constraint graph\n - Each variable gets a node\n - Edge between variables that have a constraint between them\n - Constraint hypergraph can capture $n$-ary constraints by having a node denoting the constraint with edges to all variable nodes associated with that constraint\n - **dual graph** : One variable for each constraint and one binary constraint for each pair of constraints in the original graph that share the same variables\n\n### Types of constraints\n - Precedence constraints\n - Disjunctive constraints\n\n### Types of CSPS\n - continuous domains e.g. real world stuff like Hubble space telescope\n     - Linear programming poroblems are the best-known category of continuous-domain CSPs\n - \n\n### Constraint optimization problem\n - We want not only a feasible solution, but an optimal one that satisfies all constraints\n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\n### Constraint propagation\n - Using the constraints to reduce the number of legal values (i.e. the size of the domain) for a variable\n - Can use changes to further restrict the values on more variables, and so on\n - \n\n### Local consistency\n * Node consistency: A variable is **node-consistent** if all values in it's domain satisfy the variable's unary constraints\n * Arc consistency: A variable is **arc-consistent** if every value in its domain satisfies the variables binary constraints\n     - $X_i$ is arc-consistent w.r.t. $X_j$ if for every value for $X_i$ in $D_i$ there is some value in $D_j$ that satisfies the binary constraint $(X_i, X_j)$\n * Path consistency :\n     * A two-variable set $\\{X_i, X_j\\}$ is path-consistent w.r.t a third variable $X_m$ if, for every assignment  $\\{X_i = a, X_j = b\\}$, there is an assigment to $X_m$ that satisfies the constraints on $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$\n     - The name refers to the overall consistency of the path from $X_i$ to $X_j$ with $X_m$ in the middle\n * $k$-consistency : For any set of $k$-1 variables and any consistent assignment to those variables, a consistent value can always be assigned to any $k$th variable\n * strong $k$-consistency: $k$ consistency holds for all of $k = 1, 2, \\dots, k-1, k$\n\n### AC3 Algorithm\n - put all arcs in queue\n - pop element $(X_i, X_j)$\n - for each value in $D_i$, check if there is indeed a corresponding value in $X_j$. If not, remove it from $D_i$\n - if $D_i$ is now empty, report that the problem is unsatisfiable\n - if any changes were made to $D_i$ (and not empty), then for all $X_k$ such that there is a constraint $(X_k, X_i)$, add $(X_k, X_i)$ to the queue\n - continue until queue is empty\n\n### Global constraint\n - Involves an arbitray number of variables\n - Some global constraints can be handled by special-purpose algorithms that are more efficient\n\n### Resource constraint\n - AKA \"Atmost\" constraint \n - If we have 10 people to divide into groups, the size of each groups summed is at most 10\n\n### Bounds propagation\n - Domains are represented as upper and lower bounds\n - Flights $F_1$ and $F_2$ have cpacities 165 and 385 respectively\n     - Initial domain: $D_1 = [0, 165]$ and $D_2 = [0, 385]$\n     - New constraint: Need to fly 420 people, i.e. $F_1 + F_2 = 420$\n     - New domains: $D_1 = [35, 165]$ and $D_2 = [255, 385]$\n - CSP is *bounds consistent* if for every $X_i$ and both the lower and upper bound values, there exists a value assignment to $Y$ that satissfies the constraint for $X$ and $Y$ for all $Y$\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n\n### Commutativity of assignment\n - In CSPs, the order that we assign the variables does not matter\n - So we can consider a single variable at each step in isolation\n - If the problem is solvable, then SOME assignment for this variable will eventually work no matter what variable we chose\n \n\n### Backtracking search\n - Choose an unassigned variable\n - Pick one of the values in its domain and assign it to the variable\n - Recursively (as in DFS) try to solve the problem under the above assignment\n - If failure, then backtrack and try a different assigned value (and remove the one we tried from domain)\n     - If there are no assignments left then return failure\n - Otherwise, we have a solution\n\n### Variable and value ordering\n - One good way to choose variables is to choose the variable with the *minimum-remaining-values* (MRV)\n     - Also referred to as \"most-constrained variable\" or \"fail-first\" heuristic because it picks variable most likely to cause a failure soon causing pruning\n     - If a variable has no legal values, MRV will immediately detect it and return failure\n - Another heuristic for choosing variables, and tie-breaking MRV is the **degree heuristic**\n     - Chooses the variable that is involved in largest number of constraints on other unassigned variables\n     - This reduces the branching factor on future choices because it shrinks the domains of a larger number of variables\n - To choose a **value** we can use the **least-constraining-value**\n     - This prefers values taht rule out the fewest choices for the neighboring variables in the constraint graph\n     - Max flexibility for subsequent assignments\n - Why is variable fail-first but value selection fail-last?\n     - Every variable has to be assigned eventually, so we want to fail early on variables to have fewer successful assignments to backtrack over\n     - For value ordering, we only need one solution, so it makes sense to look for the most likely values first\n\n### Forward checking\n - When a variable $X$ is assigned, forward checking establishes arc consistency for it\n \n### Maintaining Arc Consistency (MAC)\n - After a variable $X_i$ is assigned a value, the `INFERENCE` procedure calls AC-3, but use only arcs $(X_j, X_i)$ for unassigned $X_j$ rather than all arcs\n - Then AC-3 propagates constraints as normal, if a domain becomes empty we fail\n - MAC Is strictly more powerful than forward checking because forward checking is the same as MAC at first, but fails to recursively propagate constraints\n\n### Types of backtracking search\n - *Chronological backtracking* is the default that reverts the *most recent decision*\n - However, we can be smarter by backtracking to a variable that might fix the problem\n - Keep track of the set of assignments (that occur in search) that are in conflict with some value for $X_i$\n     - These assignments must be to variables that share a constraint involvig $X_i$\n     - Call this the **conflict set**\n - **Backjumping** backtracks to the most recent assignment *in the conflict set*\n - We can construct the conflict set while forward checking\n     - If assignment $X = x$ deletes a value from $Y$'s domain, then it should add $X=x$ to $Y$'s conflict set\n     - If the last value is deleted from $Y$'s domain, then *all* the assignments in the conflict set of Y are added to the conflict set of $X$\n - Backjumping cannot happen when doing forward checking or MAC because we check for the constraints ahead of time\n - Deeper concept of coflcit set for a variable $X$:\n     - The set of preceeding variables that caused $X$, together with any subsequent variables, to hvae no consistent solution\n - This is called *conflict-directed* backjumping\n\n### Constraint learning\n - Idea of finding a minimum set of variables from the conflict set that causes the problem\n - This set of variables + value assignments is called a **no-good**\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n\n### Local search for CSPs\n - Start with a complete but not necessarily consistent assignment\n - Change the value of a single variable to be closer to a solution\n - **min-conflict heuristic** : choose the variable/value that leads to the fewest number of conflicts with other variables\n\n### Tabu search\n - Keeping a small list of recently visited states and forbidding the algorithm to return to them\n\n### Constraint weighting\n - Concentrate search on important constraints\n - All constriants get value 1\n - At each step, algo chooses variable/value pair to change that will result in lowest total weight of all violated constriants\n - Weights are adjusted by incrementing the weight of each constraint that is violated by the current assignment\n - Adds topography to break ties and adds learning by assigning \"difficult\" constraints higher weight\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n\n### Independent subproblems\n - Connected components of the constraint graph can be solved as independent sub problems\n \n### Directional arc consistency\n - A CSP is directionally arc-consistent for some ordering $X_1, \\dots, X_n$ iff $X_i$ is arc consistent with each $X_j$ for $j > i$.\n\n### Tree-structured CSP\n - Solving tree structured CSP:\n     - Choose any variable as root\n     - Choose an ordering of variables such that each variable appears after its parent in the constraint tree\n     - This is called a *topological sort*\n - Can make the graph directed arc consistent in $O(n)$ steps each of which compare up to $d$ possible domain values for two variables, so $O(nd^2)$\n\n### Cutset conditioning\n - One way to reduce a constraint graph to tree involves assigning values to some variables so the others form a tree\n - We need to find a set of deletable nodes that result in a tree, call this a *cycle cutset* $S$\n - For each possible assignment to variables in $S$ that satifies constraints on $S$\n     - remove values in remaining variables inconsistent values with this particular assignment\n     - if the CSP has a solution, return it along with solution for $S$\n - If cycle cutset has size $c$, then total run time is $O(d^c \\cdot (n - c)d^2)$\n     - $d^c$ combinations of values for the variables in $S$\n     - For each combination, solve a tree problem of size $n-c$\n\n### Tree decomposition\n - Alternate way is based on constructing a **tree decomposition** of the constraint graph\n - Nodes in the new tree are *sets* of variables\n - Requirements:\n     - Every variable in original problem appears in at least one node\n     - If two variables are connected by a constraint in original problem, they must appear together in at least one of the tree nodes\n     - IF a variable appears in two nodes in the tree it must appar in every node along the path connecting the nodes\n - Finally apply Tree-CSP-Solver to get solution in $O(n'(d')^2)$ time where $n'$ is number of tree nodes and $d'$ is the size of the largest domain which is a set of tuples of assignments to all variables in that node\n - **tree width** one less than the size of the largest node\n - Tree width of a graph is the minium width among all possible tree decompositions\n - If a graph has tree width $w$ then the problem can be solved in $O(nd^{w+1})$ time given the corresponding tree decomposition\n - But, finding these decompositions is NP-hard\n\n\n### Comparison\n - Cutset conditioning has $O(d^c \\cdot (n - c)d^2)$ vs.  $O(nd^{w+1})$ \n - Given cutset of size $c$, exists tree of width $w < c + 1$ and often far smaller\n - Runtime of tree decomposition is faster, but much more memory\n - Cycle-cuset can be performed in linear memory but tree decomposition requires memory exponential in $w$\n\n\n### Value Symmetry and symmetry breaking\n - *value symmetry* is when there are multiple solutions whose assignments are simply permutations of values for some set of variables\n     - If the variables were treated as indistinguishable, then all symmetric assignments would be a single assignment to the set of variables\n - *symmetry-breaking constraints* resolve value symmetry\n     - For example, we might enforce $X_i < X_j < X_k$ for three values that have value symmetry with each other\n - NP-hard to eliminate *all* symmetry, but still an important heuristic for \"obvious\" symmetry\n\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 = \"\"\"\n",
        "\n",
        "### Knowledge-based agents\n",
        " - Use **reasoning** about an *internal representation* of info to make decisions\n",
        " - **knowledge base** or KB is a set of **sentences**\n",
        "     - each sentence is expressed in **knowledge representation languange** and represents an assertion about the world\n",
        " - **axioms** are sentences that are \"given\" rather than derived from other sentences \n",
        " - `ASK` and `TELL` are the ways to query and add sentences to KB, respectively\n",
        "\n",
        "### Agent Program\n",
        " 1. `TELL` KB what it perceives\n",
        " 2. `ASK` KB what action to perform -- KB may perform extensive reasoning about current state\n",
        " 3. `TELL` the KB which action was chosen and return it for execution\n",
        "\n",
        "### Declarative vs. Procedural\n",
        " - **declarative** approach tells agent sentences one by one until it has enough info to operate\n",
        " - **procedural** approach encodes desired behaviours directly as program code\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter7_2 = \"\"\" \n",
        "\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter7_3 = \"\"\"\n",
        "\n",
        "### Logic\n",
        " - **syntax** specifies that sentences are well formed\n",
        " - **semantics** defines the *truth* of each sentence with respect to each possible world (AKA **model**)\n",
        " - **entailment** is when one sentence follows logically from another\n",
        " \n",
        "### Logical inference\n",
        " - **model checking** is one way of logical inference that enumerates all possible models to check that $\\\\alpha$ is true in all models in which KB is true\n",
        " - An inference algorithm that derives only entailed sentences is called **sound** or **truth-preserving**\n",
        " - An inference algorithm is **complete* if it can derive any sentence that is entailed\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter7_4 = \"\"\"\n",
        "\n",
        "\n",
        "### Propositional logic\n",
        " - **syntax** of propositional logic defines the allowable sentences\n",
        " - **atomic sentences** consist of a single **propositional symbol**\n",
        " - **complex sentences** are constructed from simpler sentences using parentheses and operators called **logical connectives**\n",
        " - Conjunction - \"and\" components are called *conjuncts*\n",
        " - Disjunction - \"or\", components are called *disjuncts*\n",
        " - Implication - \"implies\", components are called **premise/antecedent** and **conclusion/consequent**\n",
        "     - Also called **rules** or **if-then** statements\n",
        " - Biconditional - two way implication\n",
        "\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "chapter7_5 = r\"\"\"\n",
        "\n",
        "### Theorem proving\n",
        " - **theorem proving** is applying the rules of inference directly to sentences in KB to construct a proof of the desired sentence\n",
        " - **logical equivalence** : two sentences are logically equivalent if they are true in the same set of models\n",
        "\n",
        "### Logical equivalences\n",
        "\n",
        "$$~~~~(\\alpha \\land \\beta) \\equiv (\\beta \\land \\alpha) ~~~~\\text{commutativity of $\\land $} $$\n",
        "$$~~~~(\\alpha \\lor \\beta) \\equiv (\\beta \\lor \\alpha)  ~~~~\\text{commutiatvity of $\\lor $} $$\n",
        "$$(\\alpha \\land \\beta) \\land \\gamma \\equiv \\alpha \\land (\\beta \\land \\gamma)  ~~~~\\text{associativity of $\\land $}$$\n",
        "$$(\\alpha \\lor \\beta) \\lor \\gamma \\equiv \\alpha \\lor (\\beta \\lor \\gamma) ~~~~\\text{associativity of $\\land $}$$\n",
        "$$~~~~~~~~~~\\neg (\\neg \\alpha) \\equiv \\alpha  ~~~~\\text{double-negation elimination$$}$$\n",
        "$$~(\\alpha \\implies \\beta) \\equiv (\\neg \\Beta \\implies \\neg \\alpha)  ~~~~\\text{contraposition}$$\n",
        "$$~~~~~~~(\\alpha \\implies \\beta) \\equiv (\\neg \\alpha \\lor \\beta)  ~~~~\\text{implication elimination}$$\n",
        "$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(\\alpha \\iff \\beta) \\equiv (\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)  ~~~~\\text{biconditional elimination}$$\n",
        "$$\\neg(\\alpha \\land \\beta) \\equiv (\\neg \\alpha \\lor \\neg \\beta) ~~~~\\text{DeMorgan}~~~~~~~~$$\n",
        "$$\\neg(\\alpha \\lor \\beta) \\equiv (\\neg \\alpha \\land \\neg \\beta) ~~~~\\text{DeMorgan}~~~~~~~~$$\n",
        "$$~~~~~~~~~~~~~~~~~~~~~~~~~~\\alpha \\land (\\beta \\lor \\gamma) \\equiv (\\alpha \\land \\beta) \\lor(\\alpha \\land \\gamma) ~~~~\\text{distributivity of $\\land$ over $\\lor$}$$\n",
        "$$~~~~~~~~~~~~~~~~~~~~~~~~~~\\alpha \\lor (\\beta \\land \\gamma) \\equiv (\\alpha \\lor \\beta) \\land (\\alpha \\lor \\gamma) ~~~~\\text{distributivity of $\\lor$ over $\\land$}$$\n",
        "\n",
        "### Validity\n",
        " - A sentence is **valid** if it is true in all models\n",
        " - Also called **tautologies**\n",
        "\n",
        "### Deduction theorem\n",
        " - For any sentences $\\alpha$ and $\\beta$, $(\\alpha$ $\\models$ $\\beta)$ if and only if $(\\alpha$ $\\implies$ $\\beta)$ is valid\n",
        "\n",
        "### Satisfiability\n",
        " - A sentence is satisfiable if it is true in, or satisfied by *some* model\n",
        " - $\\alpha$ $\\models$ $\\beta$ if and only if the sentence $(\\alpha$ $\\land$ $\\neg\\beta)$ is unsatisfiable\n",
        " - Proving $\\beta$ from $\\alpha$ by checking the unsatisfiability of  $(\\alpha$ $\\land$ $\\neg\\beta)$ corresponds exactly to the **contradiction** proof technique\n",
        "\n",
        "## Inference rules\n",
        " - **inference rules** can be applied to derive a proof\n",
        " - Best known rule is called **Modus Ponens** that is written:\n",
        " $$\n",
        " \\dfrac{\\alpha \\implies \\beta,~~ \\alpha}{\\beta}\n",
        " $$\n",
        " - And-Elimination is another rule\n",
        " $$\n",
        " \\dfrac{\\alpha \\land \\beta}{\\alpha}\n",
        " $$\n",
        "\n",
        "\"\"\"\n",
        "\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": 243,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "450b8a4b-f72a-4c41-e607-086aabbe4d52"
      },
      "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": 244,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n\n\n### Knowledge-based agents\n - Use **reasoning** about an *internal representation* of info to make decisions\n - **knowledge base** or KB is a set of **sentences**\n     - each sentence is expressed in **knowledge representation languange** and represents an assertion about the world\n - **axioms** are sentences that are \"given\" rather than derived from other sentences \n - `ASK` and `TELL` are the ways to query and add sentences to KB, respectively\n\n### Agent Program\n 1. `TELL` KB what it perceives\n 2. `ASK` KB what action to perform -- KB may perform extensive reasoning about current state\n 3. `TELL` the KB which action was chosen and return it for execution\n\n### Declarative vs. Procedural\n - **declarative** approach tells agent sentences one by one until it has enough info to operate\n - **procedural** approach encodes desired behaviours directly as program code\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n\n\n\n## AIMA Chapter 7.3 Logic\n\n\n### Logic\n - **syntax** specifies that sentences are well formed\n - **semantics** defines the *truth* of each sentence with respect to each possible world (AKA **model**)\n - **entailment** is when one sentence follows logically from another\n \n### Logical inference\n - **model checking** is one way of logical inference that enumerates all possible models to check that $\\alpha$ is true in all models in which KB is true\n - An inference algorithm that derives only entailed sentences is called **sound** or **truth-preserving**\n - An inference algorithm is **complete* if it can derive any sentence that is entailed\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n\n\n### Propositional logic\n - **syntax** of propositional logic defines the allowable sentences\n - **atomic sentences** consist of a single **propositional symbol**\n - **complex sentences** are constructed from simpler sentences using parentheses and operators called **logical connectives**\n - Conjunction - \"and\" components are called *conjuncts*\n - Disjunction - \"or\", components are called *disjuncts*\n - Implication - \"implies\", components are called **premise/antecedent** and **conclusion/consequent**\n     - Also called **rules** or **if-then** statements\n - Biconditional - two way implication\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n\n### Theorem proving\n - **theorem proving** is applying the rules of inference directly to sentences in KB to construct a proof of the desired sentence\n - **logical equivalence** : two sentences are logically equivalent if they are true in the same set of models\n\n### Logical equivalences\n\n$$~~~~(\\alpha \\land \\beta) \\equiv (\\beta \\land \\alpha) ~~~~\\text{commutativity of $\\land $} $$\n$$~~~~(\\alpha \\lor \\beta) \\equiv (\\beta \\lor \\alpha)  ~~~~\\text{commutiatvity of $\\lor $} $$\n$$(\\alpha \\land \\beta) \\land \\gamma \\equiv \\alpha \\land (\\beta \\land \\gamma)  ~~~~\\text{associativity of $\\land $}$$\n$$(\\alpha \\lor \\beta) \\lor \\gamma \\equiv \\alpha \\lor (\\beta \\lor \\gamma) ~~~~\\text{associativity of $\\land $}$$\n$$~~~~~~~~~~\\neg (\\neg \\alpha) \\equiv \\alpha  ~~~~\\text{double-negation elimination$$}$$\n$$~(\\alpha \\implies \\beta) \\equiv (\\neg \\Beta \\implies \\neg \\alpha)  ~~~~\\text{contraposition}$$\n$$~~~~~~~(\\alpha \\implies \\beta) \\equiv (\\neg \\alpha \\lor \\beta)  ~~~~\\text{implication elimination}$$\n$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(\\alpha \\iff \\beta) \\equiv (\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)  ~~~~\\text{biconditional elimination}$$\n$$\\neg(\\alpha \\land \\beta) \\equiv (\\neg \\alpha \\lor \\neg \\beta) ~~~~\\text{DeMorgan}~~~~~~~~$$\n$$\\neg(\\alpha \\lor \\beta) \\equiv (\\neg \\alpha \\land \\neg \\beta) ~~~~\\text{DeMorgan}~~~~~~~~$$\n$$~~~~~~~~~~~~~~~~~~~~~~~~~~\\alpha \\land (\\beta \\lor \\gamma) \\equiv (\\alpha \\land \\beta) \\lor(\\alpha \\land \\gamma) ~~~~\\text{distributivity of $\\land$ over $\\lor$}$$\n$$~~~~~~~~~~~~~~~~~~~~~~~~~~\\alpha \\lor (\\beta \\land \\gamma) \\equiv (\\alpha \\lor \\beta) \\land (\\alpha \\lor \\gamma) ~~~~\\text{distributivity of $\\lor$ over $\\land$}$$\n\n### Validity\n - A sentence is **valid** if it is true in all models\n - Also called **tautologies**\n\n### Deduction theorem\n - For any sentences $\\alpha$ and $\\beta$, $(\\alpha$ $\\models$ $\\beta)$ if and only if $(\\alpha$ $\\implies$ $\\beta)$ is valid\n\n### Satisfiability\n - A sentence is satisfiable if it is true in, or satisfied by *some* model\n - $\\alpha$ $\\models$ $\\beta$ if and only if the sentence $(\\alpha$ $\\land$ $\\neg\\beta)$ is unsatisfiable\n - Proving $\\beta$ from $\\alpha$ by checking the unsatisfiability of  $(\\alpha$ $\\land$ $\\neg\\beta)$ corresponds exactly to the **contradiction** proof technique\n\n## Inference rules\n - **inference rules** can be applied to derive a proof\n - Best known rule is called **Modus Ponens** that is written:\n $$\n \\dfrac{\\alpha \\implies \\beta,~~ \\alpha}{\\beta}\n $$\n - And-Elimination is another rule\n $$\n \\dfrac{\\alpha \\land \\beta}{\\alpha}\n $$\n\n\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": "d44926db-8b72-4d25-961d-9d602d20eabd"
      },
      "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": 245,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n\n\n\n###  Artificial Intelligence\n - Field of understanding and building intelligent entities\n\n### Human vs. rational\n - Some AI try to act like humans\n - Others try to act \"rationally\" by doing the right thing\n\n### Turing test\n -  Human asks written questions to computer which responds with written responses\n - If human interrogator cannot distinguish computer from human, the AI passes\n\n### Methods of testing human thought\n - Intrpspection\n - Psychological experiments\n - Brain imaging\n\n### Syllogisms\n - Patterns for argument structures that always yielded corect conclusions given correct premises\n\n\n\n## AIMA Chapter 27.1 The Limits of AI\n\n\n### Agent\n - An **agent** is anything that perceives and acts in an environment through **sensors** and **actuators**\n - **percept** : data perceived by an agent\n - **percept sequence** : complete history of percepts\n - **agent function** : function from the percept sequence to an action\n - **agent program** : implementation of the agent function in a physical system\n\n\n\n## AIMA Chapter 27.1 Can Machines Really Think?\n\n\n\n\n## AIMA 2.1 Agents and Environments\n\n\n ### Rational agent\n - An agent that works towards the best outcome or best expected outcome\n\n### Limited rationality\n - Taking good actions with limits on computation time\n\n### Value alighnment problem\n - Problem of making the goals of the machine aligned with those of the human\n\n\n\n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n\n\n### Rational agent\n - **rational agent** : selects actions to maximize performance measure based on **prior knowledge** and **current percept sequence**\n\n### Omniscience\n - **omniscience** is knowing the *actual* outcome of actions\n\n### Autonomy \n - **autonomy** is the ability of an agent to learn from its environment/percepts rather than relying on knowledge of its designer\n\n\n\n## AIMA 2.3 The Nature of Environments\n\n\n### Task environments\n - A rational agent solves a \"problem\" defined by a task environment\n\n### Components of task environment (PEAS)\n - Performance\n     - measured by a **performance measure**\n - Environment\n     - E.g. roads\n - Actuators\n     - e.g. control over steering and breaking\n - Sensors\n     - e.g video cameras so the autoamated taxi can see\n\n\n### Fully observable vs. partially observable\n - Noise or lack of sensors can lead to partially observable environments\n\n### Single-agent vs. Multi-agent\n - In multi-agents environment, the behavior of one agent depends on the behavior of the other \n - Multi-agent environments can be competitve or cooperative\n\n### Deterministic vs. nondeterministic\n - A deterministic environment is one in which the next state of the environment is completely determined by the current state and teh action executed by the agent(s)\n - Otherwise, it is non-deterministic\n - A partially observable environment could *appear* nondeterministic\n\n### Stochastic\n - Nondeterministic environment where the probabilities of each event are explicitly known (e.g. Poker)\n\n### Episodic vs. Sequential\n - In episodic environments, each state is completely independent of future states\n - In sequential environments an action at time $t$ can have an impact on all states/decisions at times > $t$\n\n### Static vs. Dynamic\n - A dynamic is an environment that can change *while the agent is deliberating*\n - Otherwise, it's static\n - Semidynamic environments are those where the agents **performance score** can change over time even if the environment does not\n\n### Discrete vs. continuous\n - Distinction can be made w.r.t. the state, the time, and the percepts and actions\n - Chess is discrete in terms of states, percepts, and actions\n - Taxi driving is continuous state and contintuous time problem. Input from digital cameras is *technically* discrete but we may consider it continuous\n\n### Known vs. unknown\n - Refers not to the environment itself but to the agent's (or designer's) state of knowledge about the \"laws of physics\" of the environment\n - In a known environment, the outcomes (or outcome probabilities for nondeterministic environment) for all actions is given\n - If environment is unknown the agent will have to *learn* in order to make good decisions\n\n### Environment class\n - Describes a set of environments populated by adjusting hyperparameters\n - e.g. a single class of taxi environment could be populated with different values for traffic, lighting, and weather conditions\n\n\n\n## AIMA 2.4 The Structure of Agents\n\n\n### Structure of agents\n - Job of AI is to implement **agent program** that implements the agent function\n - **agent architecture** is the computing device with physical sensors and actuators $$agent = architecture + program$$\n - The agent program takes only the current percept while the agent function takes entire history\n \n### Four basic kinds of agents\n - **Simple reflex agents**\n     - select actions on the *current percept* only\n - **Model-based reflex agents**\n    - maintains internal state\n    - **transition model** : updates internal state\n    - **sensor model**: encodes the state of the world from info contained in percepts\n - **Goal-based agents**\n     - Agent needs current state description + description of goal\n - **Utility-based agents**\n     - **utility function** that can evaluate eutility of different states/actions\n     - may optimize **expected utility** in non-deterministic environments\n\n### Model-free agent\n - Can learn what action is best in a particular situation without ever learning exactly how that action changes the environment\n\n### Learning agents\n - **learning agents** have four components\n     - **learning element** : responsible for making improvements\n     - **performance element** : responsible for selecting external actions\n     - ** critic ** : gives feedback to the learning element on how the agent is doing\n     - **problem generator** : responsible for suggesting actions that will lead to new and informative experiences\n\n### Representations of environments\n - **atomic representation** : each state of the world is indivisible with no structure\n - **factored representation** : splits up each state into a fixed set of **variables/attributes** each of which can have a **value**\n - **structured representation** : Relationships between pairs of objects can be described explicitly\n\n### Localist vs. distributed representation\n - **Localist representation** has one-to-one mapping of concepts and memory locations\n - In **distributeed representation**, each memory location is part of the representation of multiple different concepts\n     - Each concept represents a point in multidimensional space\n\n\n\n\n## Module 1 Lecture Notes\n\n \n\n## Module 1 Definitions\n\n\n# Module 2: Python\n## Module 2 Lecture Notes\n Your summary here \n\n## Module 2 Definitions\n* **Mutability** - your definition here\n\n\n# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n\n\n### Goal formulation\n  - Goals limit actions considered by agent\n\n### Problem formulation\n - Agent finds way to describe states/actions to reach their goal\n\n### Search\n - Before performing action, agent simulates outcomes of differnt actions until goal\n\n### Open-loop vs. closed-loop\n - Open loop : for correct model, agent can decide on solution then ignore percepts while executing\n - Closed-loop : agent monitors percepts while executing and adjusts future actions accordingly\n\n### Problem:\n  - A set of possible *states* that the environment can be in called *state space*\n  - Initial state\n  - One or more goal states\n  - For any state $s$, we have a set of actions $A$\n  - Transition model : takes a state $s$ and action $a$ and returns a new state $s'$\n  - Action cost function : Computes cost of applying $a$ to state $s$ to reach $s'$\n\n\n## AIMA Chapter 3.2 Example Problems\n\n\n### Standardized Problem\n -  Meant to demonstrate problem solving methods because the problem has an exact description\n     - Can be used for benchmarking algorithms\n  \n### Real-world problem\n - People actually use solutions to these problems\n - Formulation is idiosyncratic and not standardized\n - e.g. all robots may have slightly different sensors\n\n\n\n\n## AIMA Chapter 3.3 Search Algorithms\n\n\n## Performance Measures\n - COMPLETENESS\n - COST OPTIMALITY\n - TIME COMPLEXITY\n - SPACE COMPLEXITY\n\n### Tree vs. Graph Search\n - Graph search checks for redundant paths, tree search doesn't\n\n\n### Best-first search\n - Choose node $n$ with minimum value of some evaluation function $f(n)$\n\n\n\n\n\n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n\n\n### BFS\n  - Time and space are $O(b^d)$ for branching factor b and depth d\n\n### Dijsktra\n  - Uniform-cost search \n  - Time and space complexity is $O(B^{1 + ({\\lfloor} C^* / \\epsilon {\\rfloor} }))$\n  - this can be much more than $b^d$\n\n### DFS\n - ALways expands the deepest node in the frontier\n - Usually implemnted as a tree-like search rather than graph search\n - DFS can get stuck in infinite loops and can get stuck going down an infinite path\n\n### Backtracking search\n - Generates only one successor at a time rather than all successors\n - Each partially expanded node remembers which successor to generate next\n - Successors are generated by modifying the current state description directly rather than allocation memory for a brand-new state\n - Reduces the memory requirements to just one state description and a oath of $O(m)$ actions\n - Big savings over $O(bm)$ states for DFS\n\n### Depth-limited search \n - Supply a depth limit $l$ and treat all nodes at depth $l$ as if they had no successors\n - Time complexity $O(b^l)$ and space complexity $O(bl)$\n - Fails when $l$ is too small\n\n### Iterative deepening\n - Uses depth limited described above sequentially for each $l = 0, 1, 2, \\dots$ until solution\n - Memory : $O(bd)$ when there is a solution and $O(bm)$ on finite state spaces with no soln. \n - Time complexity: $O(b^d)$ when soln. $O(b^m)$ otherwise\n\n### Bidirectional search\n - Searches forward from the initial state and backwards from goal state(s) at same time\n - Motivation: $b^{d/2} + b^{d/2} << b^d$\n - Expands the node with minimum value of the evaluation function across *either* frontier\n\n\n\n\n## Module 3 Lecture Notes\n Your summary here \n\n## Module 3 Definitions\n* **Problem-solving agent** - an agent that can formulate a plan via search\n\n\n# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n\n\n### Greedy best-first search\n - Expands nodes with minimal $h(n)$\n\n### A* search\n - Expands nodes with minimal $f(n) = g(n) + h(n)$ where $g(n)$ is true cost and $h(n)$ is heuristic\n - optimal for \"admissible/optimistic\" $h$ that **never overestimate** the true cost to reach goal\n\n### Consistency\n - for every node $n$ and every successor $n'$ of $n$ generated by $a$:\n   - $h(n) \\leq c(n, a, n') + h(n')$\n - form of the triangle inequality\n - consistent -> admissible but NOT vice versa\n - consistent heuristic adds states to frontier at most once\n\nInadmissiable heuristics can still be optimal if h(n) admissible for nodes on optimal path\nOR if h(n) never overestimates cost by more than $C_2 - C^*$ where C_2 is second-best cost\n\n### Surely expanded nodes\n  - All nodes on a path with $f(n) < C^*$\n\n### Optimally efficient\n  - A* with consistent heuristic is optimally efficient\n    - Any algorithm with same heuristic info must expand all nodes that are surely expanded by A*\n\n### Inadmissible heuristics and weighted A*\n - Engineers may opt to use inadmissble heuristics that risk overestimating cost but prune more nodes\n - Weighted A* search uses $f(n) = g(n) + W * h(n)$ where W > 1, which can make the effective heuristic inadmissible\n - Other algorithms described as Weighted A*\n     - A* is $W = 1$\n     - Uniform cost is $W = 0$\n     - Greedy best-first is $W = \\infty$\n - Weighted A* is bounded suboptimal search\n\n### Bounded suboptimal search\n - Solution guarenteed to be within constant factor W of optimal cost\n\n### Unbounded-cost search\n - Cost doesn't matter as long as we can find soln. quickly\n - e.g. speedy search which is greedy best-first search that uses the heuristic \"number of actions to reach goal\"\n\n### Memory-bounded search\n - A* uses lots of memory\n - Can remove states from reached if they can be proved unusable\n - Keep counts of number of times a state has been reached, remove when it's been reached by all its incoming neighbors\n\n### Beam search\n -  Keeps only $k$ nodes with the best $f$-scores\n - Incomplete and suboptimal but good for memory and speed\n\n### Iterative-deepening A* search (IDA*)\n - Analog of IDDFS but for A* instead of DFS\n - Don't need to keep reached states in memory, slight cost of repeated states\n\n### Recursive best-first search (RBFS)\n - Similar to DFS but uses $f_{limit}$ to track the best alternative path available from ancestor\n - If we exceed the limit, recursion backtracks to the alternative path\n - As we backtrack, we remember the best f-value of the children of each node\n\n\n### MA* and SMA*\n - Allow algo to use all memory\n - SMA* expands the best leaf until memory is full then always drops the *worst* leaf node\n     - newer > older\n - experiences thrashing on hard problems. Memory constraint -> intractable runtime\n\n\n## AIMA Chapter 3.6 Heuristic Functions\n\n\n### Effective branching factor $b^*$\n - $N$ is nodes generates then tree of depth $d$ has $b^*$ defined as $$N + 1= 1 + b^* + (b^*)^2 + \\dots + (b^*)d$$\n\n### Relaxed problem\n - Problem with fewer restrictions on actions is called relaxed problem\n - New state-space graph is *supergraph*\n - Optimal soln. to a relaxed problem is admissible heuristic for original problem\n\n### Combining heuristics\n -  Given $k$ admissible heuristics $h_1, \\dots, h_k$ we can make a better heuristic $h^*$ $$h^*(n) = \\max \\{h_1(n), \\dots, h_k(n) \\}$$\n\n\n### Pattern database\n - Store the exact solution costs for every possible subproblem instance\n\n### Disjoint pattern database\n - Instead of storing the total cost of the subproblem store a meaningful value that is a disjoint fraction of the subcost\n - For example, the cost of the moves *only involving* tiles 1-2-3-4 and add this to cost only involving 4-5-6-7\n - \n\n### Landmarks\n - Most important trick to doing otherwise intractable problems (such as google maps finding route of tens of millions of vertices in milliseconds) is precomputation\n - Precomputation takes a vry long time, but we do it once and amortize it over billions of user search requests\n - Choose a few (10 or 20) landmark points from the vertices\n - For each landmark $L$ and eachother vertex $v$ in the graph, compute and store $C*(v, L)$ the exact cost of $v$ to $L$\n - Efficient (but inadmissble) heuristic: minimum over all landmarks of cost of getting from current node to landmark and then goal $$h_L(n) = \\min_{L \\in Landmarks} C^*(n, L) + C^*(L, goal)$$\n - Efficient (AND admissible) *differential heuristic*: $$h_{DH}(n) = \\max_{L \\in Landmarks} | C^*(n, L) - C^*(goal, L)| $$\n - The differential heuristic says consider the path from $n$ to landmark $L$ beyond goal, and then subtract the distance from the goal to $L$\n\n\n### Shortcuts\n - Multi-action paths described as a new single edge\n - For instance, we could create shrotcusts between all the 100 biggest cities in the US\n\n\n### Metalevel state space\n - Each state in the metalevle state space captures the internal computational state of a program that is searching in an ordinary state space\n\n\n\n## Module 4 Lecture Notes\n\n\n\n## Module 4 Definitions\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n\n\n\n\n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n\n \n### Minimax search\n - Finds the minimax value of each state in the tree\n - Minimax value is the utility (for MAX) of being in the state assuming both players play optimally\n - Depth-first exploration \n - Can augment with a vector of utilities when the number of players exceeds 2\n \n### Alpha-beta pruning\n  - Maintains alpha which is lower bound on utility for max and beta which is upper bound\n  - Max player ignores payoffs less than alpha and min player ignores payoffs greater than beta\n  - Depth first, we traverse a single long path, then we go all teh way back to the top and propagate information\n  - Efficiency depends on order that we explore states  - Optimally $O(b^{m/2})$ instead of $O(B^m)$\n\n### Dynamic move order schemes and killer moves\n - Another improvement to alpha-beta would be to add dynamic move-ordering schemes such as trying those that were found to be best int he past\n - Past can be a previous move or a previous exploration of current move with iterative deepening\n - The best move is known as a *killer move* and trying them first is known as **killer move heuristic**\n \n\n### Transpositions\n -  Different permutations of move sequences that end up in the same position\n - Can be addressed with *transposition table*\n\n### Type A vs. Type B\n - Type A strategy considers *all* moves to a certain depth and then uses a heuristic eval function\n - Type B strategy ignores moves that look bad and follows promising lines \"as far as possible\"\n - Chess typically uses Type A while Go uses type B (though alpha-zero uses type B)\n\n\n\n\n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n\n\n### Heuristic ALpha-Beta Tree Search\n - Cut off search early and apply a heuristic evaluation function to states treating nonterminal nodes as terminal\n - Terminal test replaced with *cutoff test* which returns true based on some properties (but all terminal states return true)\n\n### Evaluation function\n - Heuristic evaluation function EVAL(s, p) returns an estimate of the expected utility of state $s$ to player $p$\n - If p is a terminal state, EVAL(s, p) = UTILITY(s, p)\n - Most eval functions calculate various *features* of the state such as the counts of each piece for each side in chess\n - Material value in chess is a type of *weighted linear function* since we sum up the values across the state\n\n### Cutting off search\n - Replace terminal test with cutoff test\n - May also track depth d and cut off for all nodes beyond depth d (iterative deepening can help too)\n\n### Quisence\n - A state is quiescent if there are no pending moves (such as capturing a queen) that would wildly swing the evaluation\n - For nonquiescent positions, the IS-CUTOFF returns false and search continues until quiescent positions are reached\n - *quisence search* can be restricted to only consider certain moves such as captures to quickly resolve uncertainties\n\n### Horizon effect\n - Problem when we stall inevitable risk and lose more\n - A *singular extension* allows moves that are \"clearly better\" than all other moves in a given position to be played after the horizon\n     - Counters delaying tactics (that sacrifice pointlessly) because after applying these tactics we allow these \"singular extensions\" to play out\n\n\n### Forward pruning\n - Prunes moves that appear to be poor moves but might possibly be good ones\n - That is, to even be considered, a move must be at least as good as some threshold\n - One approach to forward pruning is *beam search* which is to consider a beam of only the $n$ best (according to heuristic) moves\n\n### ProbCut\n - Alpha-beta prunes moves that are *definitely* outside the window, and ProbCut removes moves that are *probably* outside the window\n\n### Table lookup\n - Employed by chess programs to play moves and the opening and ending of games\n - *Retrograde* minimax search\n     - Work backwards from the end states and figure out which states are \"forced wins\" and mark them as wins themselves\n     - Repeat\n - In chess there are lookup tables for all endings with seven or fewer pieces\n\n\n### Monte-Carlo tree search\n - Instead of a heuristic evaluation function, perform many rollouts from current state\n - The value of the heuristic is the proportion of wins for the player in question\n - *payoff policy* biases towards good moves\n     - NNs or other heuristics used\n - *Pure MCTS* performs N simulations from the current state\n - *selection policy* that focuses search on the important parts of the game tree\n     - *exploration* vs. *exploitation*\n - *UCT* has been very effective\n\n\n\n\n\n## AIMA Chapter 5.5 Stochastic Games\n\n### Stochastic games\n - Players know what moves can be made with respect to each random outcome but do not know result of random outcome\n     - In backgammon, the moves depend on the result of the roll\n - We address this by including chance nodes in the tree between decision nodes for MAX and MIN\n\n\n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n\n\n### Decision network (AKA influence diagram)\n - Extends Bayesian networks by incorporation actions and utilities\n\n### Maximum expected utility (MEU)\n - Agent shuld choose action to maximize expected utility\n\n\n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n\n\n### Notation\n - $A \\succ B$  the agent prefers $A$ to $B$\n - $A \\sim B$  the agent is indifferent between $A$ and $B$\n - $A \\succeq B$ agent prefers $A$ over $B$ or is indifferent\n\n### Constraints on rational preferences\n - ORDERABILITY: Given two outcomes, an agent must prefer one or think of them as equal\n - TRANSITIVITY: Given three outcomes, if $ A \\succ B$ and $B \\succ C$ then $A \\succ C$\n - CONTINUITY: If some outcome $B$ is in between $A$ and $C$ in preference, then there exists a probability $p$ such that a rational agent will be indifferent between getting B for sure and a lottery yielding A with probability $p$ and $C$ with probability $1-p$\n - SUBSTITUTABILITY: If An egent is indifferent between $A$ and $B$, then agent also indifferent in two more complex lotteries with only differnce being $A$ sub for $B$\n - MONOTONICITY: For any pair of lotteries with only two outcomes, if an agent prefers $A$ to $B$ then they must prefer the lottery with higher probability on $A$\n - DECOMPOSABILITY: Compound lotteries can be reduced to simpler ones using the laws of probability\n\n\n### Existence of a utility function\n -  If an agent's preferences obey the axioms of utility, then there existsa a function $U$ such that $U(A) > U(B)$ iff $A$ is prefered to $B$, and $U(A) = U(B)$ iff agent is indiffernt between $A$ and $B$\n\n### Value function (ordinal utility function)\n - Function with enough information to convey ordered preference ranking on states\n\n\n\n## AIMA Chapter 16.3 Utility Functions\n \n\n### Preference elicitation\n - Process of presenting choices to a human to figure out their utility function\n\n### Evaluating life\n - Value of a statistical life approx $10 million\n - Micromort : a one in a million chance of death\n - QALY : quality adjusted life year\n\n### Monotonic preference (for money)\n - All other things being equal, people prefer more money to less\n\n\n### Normative vs. descriptive theory\n - Normative theory describes how agents *should* act while descriptive theory describes how agents *do* act\n\n\n\n## Module 5 Lecture Notes\n\n\n \n\n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n## WARNING: Your summary of 'AIMA Chapter 6.3 Backtracking Search for CSPs' is too long!\nWARNING: Your summary of 'AIMA Chapter 6.5 The Structure of Problems' is too long!\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n\n\n### Factored representation of a state\n - A set of **variables** each of which has a **value**\n - Problem is solved when each variable has a value that satisfies all constraints on it\n\n### CSP Components\n - $X$ is a set of variables  $\\{X_1, \\dots, X_n\\}$\n - $D$ is a set of domains, $\\{D_1, \\dots, D_n\\}$ one for each variables\n - $C$ is a set of constraints that specify allowable combinations of values \n\n### Assignments\n - Giving a value to each variable\n - **consistent** assignment is one that does not violate constraints\n - **complete** assignment assigns each variable a value\n - **solution** to a csp is a consistent, complete assignment\n - **partial assignment** is one that leaves some variables unassigned\n - **partial solution** is a partial assignment that is consistent\n - CSPs are generally NP complete but there are subclasses that can be solved fast\n\n\n### Constraint graph\n - Each variable gets a node\n - Edge between variables that have a constraint between them\n - Constraint hypergraph can capture $n$-ary constraints by having a node denoting the constraint with edges to all variable nodes associated with that constraint\n - **dual graph** : One variable for each constraint and one binary constraint for each pair of constraints in the original graph that share the same variables\n\n### Types of constraints\n - Precedence constraints\n - Disjunctive constraints\n\n### Types of CSPS\n - continuous domains e.g. real world stuff like Hubble space telescope\n     - Linear programming poroblems are the best-known category of continuous-domain CSPs\n - \n\n### Constraint optimization problem\n - We want not only a feasible solution, but an optimal one that satisfies all constraints\n\n\n\n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \n\n### Constraint propagation\n - Using the constraints to reduce the number of legal values (i.e. the size of the domain) for a variable\n - Can use changes to further restrict the values on more variables, and so on\n - \n\n### Local consistency\n * Node consistency: A variable is **node-consistent** if all values in it's domain satisfy the variable's unary constraints\n * Arc consistency: A variable is **arc-consistent** if every value in its domain satisfies the variables binary constraints\n     - $X_i$ is arc-consistent w.r.t. $X_j$ if for every value for $X_i$ in $D_i$ there is some value in $D_j$ that satisfies the binary constraint $(X_i, X_j)$\n * Path consistency :\n     * A two-variable set $\\{X_i, X_j\\}$ is path-consistent w.r.t a third variable $X_m$ if, for every assignment  $\\{X_i = a, X_j = b\\}$, there is an assigment to $X_m$ that satisfies the constraints on $\\{X_i, X_m\\}$ and $\\{X_m, X_j\\}$\n     - The name refers to the overall consistency of the path from $X_i$ to $X_j$ with $X_m$ in the middle\n * $k$-consistency : For any set of $k$-1 variables and any consistent assignment to those variables, a consistent value can always be assigned to any $k$th variable\n * strong $k$-consistency: $k$ consistency holds for all of $k = 1, 2, \\dots, k-1, k$\n\n### AC3 Algorithm\n - put all arcs in queue\n - pop element $(X_i, X_j)$\n - for each value in $D_i$, check if there is indeed a corresponding value in $X_j$. If not, remove it from $D_i$\n - if $D_i$ is now empty, report that the problem is unsatisfiable\n - if any changes were made to $D_i$ (and not empty), then for all $X_k$ such that there is a constraint $(X_k, X_i)$, add $(X_k, X_i)$ to the queue\n - continue until queue is empty\n\n### Global constraint\n - Involves an arbitray number of variables\n - Some global constraints can be handled by special-purpose algorithms that are more efficient\n\n### Resource constraint\n - AKA \"Atmost\" constraint \n - If we have 10 people to divide into groups, the size of each groups summed is at most 10\n\n### Bounds propagation\n - Domains are represented as upper and lower bounds\n - Flights $F_1$ and $F_2$ have cpacities 165 and 385 respectively\n     - Initial domain: $D_1 = [0, 165]$ and $D_2 = [0, 385]$\n     - New constraint: Need to fly 420 people, i.e. $F_1 + F_2 = 420$\n     - New domains: $D_1 = [35, 165]$ and $D_2 = [255, 385]$\n - CSP is *bounds consistent* if for every $X_i$ and both the lower and upper bound values, there exists a value assignment to $Y$ that satissfies the constraint for $X$ and $Y$ for all $Y$\n\n\n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n\n\n### Commutativity of assignment\n - In CSPs, the order that we assign the variables does not matter\n - So we can consider a single variable at each step in isolation\n - If the problem is solvable, then SOME assignment for this variable will eventually work no matter what variable we chose\n \n\n### Backtracking search\n - Choose an unassigned variable\n - Pick one of the values in its domain and assign it to the variable\n - Recursively (as in DFS) try to solve the problem under the above assignment\n - If failure, then backtrack and try a different assigned value (and remove the one we tried from domain)\n     - If there are no assignments left then return failure\n - Otherwise, we have a solution\n\n### Variable and value ordering\n - One good way to choose variables is to choose the variable with the *minimum-remaining-values* (MRV)\n     - Also referred to as \"most-constrained variable\" or \"fail-first\" heuristic because it picks variable most likely to cause a failure soon causing pruning\n     - If a variable has no legal values, MRV will immediately detect it and return failure\n - Another heuristic for choosing variables, and tie-breaking MRV is the **degree heuristic**\n     - Chooses the variable that is involved in largest number of constraints on other unassigned variables\n     - This reduces the branching factor on future choices because it shrinks the domains of a larger number of variables\n - To choose a **value** we can use the **least-constraining-value**\n     - This prefers values taht rule out the fewest choices for the neighboring variables in the constraint graph\n     - Max flexibility for subsequent assignments\n - Why is variable fail-first but value selection fail-last?\n     - Every variable has to be assigned eventually, so we want to fail early on variables to have fewer successful assignments to backtrack over\n     - For value ordering, we only need one solution, so it makes sense to look for the most likely values first\n\n### Forward checking\n - When a variable $X$ is assigned, forward checking establishes arc consistency for it\n \n### Maintaining Arc Consistency (MAC)\n - After a variable $X_i$ is assigned a value, the `INFERENCE` procedure calls AC-3, but use only arcs $(X_j, X_i)$ for unassigned $X_j$ rather than all arcs\n - Then AC-3 propagates constraints as normal, if a domain becomes empty we fail\n - MAC Is strictly more powerful than forward checking because forward checking is the same as MAC at first, but fails to recursively propagate constraints\n\n### Types of backtracking search\n - *Chronological backtracking* is the default that reverts the *most recent decision*\n - However, we can be smarter by backtracking to a variable that might fix the problem\n - Keep track of the set of assignments (that occur in search) that are in conflict with some value for $X_i$\n     - These assignments must be to variables that share a constraint involvig $X_i$\n     - Call this the **conflict set**\n - **Backjumping** backtracks to the most recent assignment *in the conflict set*\n - We can construct the conflict set while forward checking\n     - If assignment $X = x$ deletes a value from $Y$'s domain, then it should add $X=x$ to $Y$'s conflict set\n     - If the last value is deleted from $Y$'s domain, then *all* the assignments in the conflict set of Y are added to the conflict set of $X$\n - Backjumping cannot happen when doing forward checking or MAC because we check for the constraints ahead of time\n - Deeper concept of coflcit set for a variable $X$:\n     - The set of preceeding variables that caused $X$, together with any subsequent variables, to hvae no consistent solution\n - This is called *conflict-directed* backjumping\n\n### Constraint learning\n - Idea of finding a minimum set of variables from the conflict set that causes the problem\n - This set of variables + value assignments is called a **no-good**\n\n\n\n## AIMA Chapter 6.4 Local Search for CSPs\n\n\n### Local search for CSPs\n - Start with a complete but not necessarily consistent assignment\n - Change the value of a single variable to be closer to a solution\n - **min-conflict heuristic** : choose the variable/value that leads to the fewest number of conflicts with other variables\n\n### Tabu search\n - Keeping a small list of recently visited states and forbidding the algorithm to return to them\n\n### Constraint weighting\n - Concentrate search on important constraints\n - All constriants get value 1\n - At each step, algo chooses variable/value pair to change that will result in lowest total weight of all violated constriants\n - Weights are adjusted by incrementing the weight of each constraint that is violated by the current assignment\n - Adds topography to break ties and adds learning by assigning \"difficult\" constraints higher weight\n\n\n## AIMA Chapter 6.5 The Structure of Problems\n\n\n### Independent subproblems\n - Connected components of the constraint graph can be solved as independent sub problems\n \n### Directional arc consistency\n - A CSP is directionally arc-consistent for some ordering $X_1, \\dots, X_n$ iff $X_i$ is arc consistent with each $X_j$ for $j > i$.\n\n### Tree-structured CSP\n - Solving tree structured CSP:\n     - Choose any variable as root\n     - Choose an ordering of variables such that each variable appears after its parent in the constraint tree\n     - This is called a *topological sort*\n - Can make the graph directed arc consistent in $O(n)$ steps each of which compare up to $d$ possible domain values for two variables, so $O(nd^2)$\n\n### Cutset conditioning\n - One way to reduce a constraint graph to tree involves assigning values to some variables so the others form a tree\n - We need to find a set of deletable nodes that result in a tree, call this a *cycle cutset* $S$\n - For each possible assignment to variables in $S$ that satifies constraints on $S$\n     - remove values in remaining variables inconsistent values with this particular assignment\n     - if the CSP has a solution, return it along with solution for $S$\n - If cycle cutset has size $c$, then total run time is $O(d^c \\cdot (n - c)d^2)$\n     - $d^c$ combinations of values for the variables in $S$\n     - For each combination, solve a tree problem of size $n-c$\n\n### Tree decomposition\n - Alternate way is based on constructing a **tree decomposition** of the constraint graph\n - Nodes in the new tree are *sets* of variables\n - Requirements:\n     - Every variable in original problem appears in at least one node\n     - If two variables are connected by a constraint in original problem, they must appear together in at least one of the tree nodes\n     - IF a variable appears in two nodes in the tree it must appar in every node along the path connecting the nodes\n - Finally apply Tree-CSP-Solver to get solution in $O(n'(d')^2)$ time where $n'$ is number of tree nodes and $d'$ is the size of the largest domain which is a set of tuples of assignments to all variables in that node\n - **tree width** one less than the size of the largest node\n - Tree width of a graph is the minium width among all possible tree decompositions\n - If a graph has tree width $w$ then the problem can be solved in $O(nd^{w+1})$ time given the corresponding tree decomposition\n - But, finding these decompositions is NP-hard\n\n\n### Comparison\n - Cutset conditioning has $O(d^c \\cdot (n - c)d^2)$ vs.  $O(nd^{w+1})$ \n - Given cutset of size $c$, exists tree of width $w < c + 1$ and often far smaller\n - Runtime of tree decomposition is faster, but much more memory\n - Cycle-cuset can be performed in linear memory but tree decomposition requires memory exponential in $w$\n\n\n### Value Symmetry and symmetry breaking\n - *value symmetry* is when there are multiple solutions whose assignments are simply permutations of values for some set of variables\n     - If the variables were treated as indistinguishable, then all symmetric assignments would be a single assignment to the set of variables\n - *symmetry-breaking constraints* resolve value symmetry\n     - For example, we might enforce $X_i < X_j < X_k$ for three values that have value symmetry with each other\n - NP-hard to eliminate *all* symmetry, but still an important heuristic for \"obvious\" symmetry\n\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\n\n### Knowledge-based agents\n - Use **reasoning** about an *internal representation* of info to make decisions\n - **knowledge base** or KB is a set of **sentences**\n     - each sentence is expressed in **knowledge representation languange** and represents an assertion about the world\n - **axioms** are sentences that are \"given\" rather than derived from other sentences \n - `ASK` and `TELL` are the ways to query and add sentences to KB, respectively\n\n### Agent Program\n 1. `TELL` KB what it perceives\n 2. `ASK` KB what action to perform -- KB may perform extensive reasoning about current state\n 3. `TELL` the KB which action was chosen and return it for execution\n\n### Declarative vs. Procedural\n - **declarative** approach tells agent sentences one by one until it has enough info to operate\n - **procedural** approach encodes desired behaviours directly as program code\n\n\n\n## AIMA Chapter 7.2 The Wumpus World\n \n\n\n\n\n## AIMA Chapter 7.3 Logic\n\n\n### Logic\n - **syntax** specifies that sentences are well formed\n - **semantics** defines the *truth* of each sentence with respect to each possible world (AKA **model**)\n - **entailment** is when one sentence follows logically from another\n \n### Logical inference\n - **model checking** is one way of logical inference that enumerates all possible models to check that $\\alpha$ is true in all models in which KB is true\n - An inference algorithm that derives only entailed sentences is called **sound** or **truth-preserving**\n - An inference algorithm is **complete* if it can derive any sentence that is entailed\n\n\n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n\n\n\n### Propositional logic\n - **syntax** of propositional logic defines the allowable sentences\n - **atomic sentences** consist of a single **propositional symbol**\n - **complex sentences** are constructed from simpler sentences using parentheses and operators called **logical connectives**\n - Conjunction - \"and\" components are called *conjuncts*\n - Disjunction - \"or\", components are called *disjuncts*\n - Implication - \"implies\", components are called **premise/antecedent** and **conclusion/consequent**\n     - Also called **rules** or **if-then** statements\n - Biconditional - two way implication\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n\n\n### Theorem proving\n - **theorem proving** is applying the rules of inference directly to sentences in KB to construct a proof of the desired sentence\n - **logical equivalence** : two sentences are logically equivalent if they are true in the same set of models\n\n### Logical equivalences\n\n$$~~~~(\\alpha \\land \\beta) \\equiv (\\beta \\land \\alpha) ~~~~\\text{commutativity of $\\land $} $$\n$$~~~~(\\alpha \\lor \\beta) \\equiv (\\beta \\lor \\alpha)  ~~~~\\text{commutiatvity of $\\lor $} $$\n$$(\\alpha \\land \\beta) \\land \\gamma \\equiv \\alpha \\land (\\beta \\land \\gamma)  ~~~~\\text{associativity of $\\land $}$$\n$$(\\alpha \\lor \\beta) \\lor \\gamma \\equiv \\alpha \\lor (\\beta \\lor \\gamma) ~~~~\\text{associativity of $\\land $}$$\n$$~~~~~~~~~~\\neg (\\neg \\alpha) \\equiv \\alpha  ~~~~\\text{double-negation elimination$$}$$\n$$~(\\alpha \\implies \\beta) \\equiv (\\neg \\Beta \\implies \\neg \\alpha)  ~~~~\\text{contraposition}$$\n$$~~~~~~~(\\alpha \\implies \\beta) \\equiv (\\neg \\alpha \\lor \\beta)  ~~~~\\text{implication elimination}$$\n$$~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~(\\alpha \\iff \\beta) \\equiv (\\alpha \\implies \\beta) \\land (\\beta \\implies \\alpha)  ~~~~\\text{biconditional elimination}$$\n$$\\neg(\\alpha \\land \\beta) \\equiv (\\neg \\alpha \\lor \\neg \\beta) ~~~~\\text{DeMorgan}~~~~~~~~$$\n$$\\neg(\\alpha \\lor \\beta) \\equiv (\\neg \\alpha \\land \\neg \\beta) ~~~~\\text{DeMorgan}~~~~~~~~$$\n$$~~~~~~~~~~~~~~~~~~~~~~~~~~\\alpha \\land (\\beta \\lor \\gamma) \\equiv (\\alpha \\land \\beta) \\lor(\\alpha \\land \\gamma) ~~~~\\text{distributivity of $\\land$ over $\\lor$}$$\n$$~~~~~~~~~~~~~~~~~~~~~~~~~~\\alpha \\lor (\\beta \\land \\gamma) \\equiv (\\alpha \\lor \\beta) \\land (\\alpha \\lor \\gamma) ~~~~\\text{distributivity of $\\lor$ over $\\land$}$$\n\n### Validity\n - A sentence is **valid** if it is true in all models\n - Also called **tautologies**\n\n### Deduction theorem\n - For any sentences $\\alpha$ and $\\beta$, $(\\alpha$ $\\models$ $\\beta)$ if and only if $(\\alpha$ $\\implies$ $\\beta)$ is valid\n\n### Satisfiability\n - A sentence is satisfiable if it is true in, or satisfied by *some* model\n - $\\alpha$ $\\models$ $\\beta$ if and only if the sentence $(\\alpha$ $\\land$ $\\neg\\beta)$ is unsatisfiable\n - Proving $\\beta$ from $\\alpha$ by checking the unsatisfiability of  $(\\alpha$ $\\land$ $\\neg\\beta)$ corresponds exactly to the **contradiction** proof technique\n\n## Inference rules\n - **inference rules** can be applied to derive a proof\n - Best known rule is called **Modus Ponens** that is written:\n $$\n \\dfrac{\\alpha \\implies \\beta,~~ \\alpha}{\\beta}\n $$\n - And-Elimination is another rule\n $$\n \\dfrac{\\alpha \\land \\beta}{\\alpha}\n $$\n\n\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": {}
        }
      ]
    }
  ]
}