{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "Kara_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": "f85c18cc-e16e-4071-ab7d-85b5c2c1c9a8"
      },
      "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": 72,
      "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": "f954ea83-279c-4881-b645-9ba98790cab3"
      },
      "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": 73,
      "outputs": [
        {
          "output_type": "stream",
          "name": "stdout",
          "text": [
            "The length in words is 500\n",
            "The length in characters is 3030\n"
          ]
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "5yG3-YncJfTB"
      },
      "source": [
        "# Permissions to use your summaries\n",
        "\n",
        "We'd like to use your summaries to help develop better educational resources like [remember.school](https://remember.school) or a question-answering system about the textbook.  \n",
        "\n",
        "1. Please enter your name.  \n",
        "\n",
        "2. If you grant permission for us to use your summaries under a [Creative Commons License](https://creativecommons.org/licenses/by/4.0/), please set ```permission = True```.  If you do not grant permission, please set it to false. Your answer won't affect your grade.\n",
        "\n",
        "3. If you grant us permission, and you'd like to remain anonymous, set ```anonymous = True```.  We'll remove your name before sharing your summaries with anyone. "
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "2RECnJArJew4"
      },
      "source": [
        "name = \"\"\n",
        "permission = True\n",
        "anonymous = True"
      ],
      "execution_count": 74,
      "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 = \"\"\" Chapter 1.1 summary. \"\"\" \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter27_2 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA 4th Edition, Chapter 2 “Intelligent Agents” (whole chapter)\n",
        "chapter2_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter2_4 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module1_lecture_notes = \"\"\" Your summary here \"\"\"\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",
        "    \"rationality\": \"doing the right thing\",\n",
        "\"agent\" : \"anything that can perceive and act in an environment\",\n",
        "\"percept\" : \"your definitions here\",\n",
        "\"other concept\" : \"your definitions here\",\n",
        "\"etc.\": \"your definitions here\",\n",
        "}\n",
        "\n"
      ],
      "execution_count": 75,
      "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": 730
        },
        "cellView": "form",
        "outputId": "3c5f3a5a-e527-49a6-d8c7-807d242de738"
      },
      "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": 76,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationality** - doing the right thing\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\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": 77,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ydOK__lwWgdp",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 207
        },
        "outputId": "d4671f7f-69bb-49c6-fc2a-7f10876c3eb0"
      },
      "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": 78,
      "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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_4 = \"\"\" Your summary here \"\"\"\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": 79,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "lvtN3p7ET3Tx",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 468
        },
        "outputId": "5b0cae32-b649-4e6a-81ff-f499e0792dcc"
      },
      "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": 80,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 3: Search Problems\n## AIMA Chapter 3.1 Problem-Solving Agents\n Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \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 = \"\"\" Your summary here \"\"\"\n",
        "chapter3_6 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module4_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module4_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 81,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "vqtEs0gHs9sO",
        "cellView": "form",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 337
        },
        "outputId": "8b4699c9-9ca9-46ff-97d8-4b1316da05ca"
      },
      "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\", module3_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": 82,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 4: Informed Search\n## AIMA Chapter 3.5 Informed (Heuristic) Search Strategies\n Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "F3FPMzG9yUls"
      },
      "source": [
        "#Module 5 - Adversarial Search and Games"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "iEIOpL7vyWcc"
      },
      "source": [
        "# Russell and Norvig, AIMA chapter 5 \"Adversarial Search\"”\" (5.1-5.3, and 5.5).\n",
        "chapter5_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_3 = \"\"\" Your summary here \"\"\"\n",
        "chapter5_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Russell and Norvig, AIMA Chapter 16 “Making Simple Decisions” (16.1-16.3)\n",
        "chapter16_1 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_2 = \"\"\" Your summary here \"\"\"\n",
        "chapter16_3 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module5_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module5_definitions = {\n",
        "\"concept\" : \"definition\",    \n",
        "}\n",
        "\n"
      ],
      "execution_count": 83,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "KUc_LgzDvWf-",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 664
        },
        "outputId": "30b58381-0381-4ee8-cd77-7c8305507995"
      },
      "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": 84,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    },
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "qVSQhTVSyYYO"
      },
      "source": [
        "#Module 6 - \"Constraint Satisfaction Problems\""
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "Wm4mfW82yaRH"
      },
      "source": [
        "# Russell and Norvig, AIMA, Chapter 6 “Constraint Satisfaction Problems” (6.1-6.5)\n",
        "chapter6_1 = \"\"\" \n",
        "Csp has (1) set of variables (2) set of domains, 1 for each variable w/ allowable values for that variable (3) set of constraints specifying allowable combos of vals.\n",
        "Solving is NP-complete in general (though important subclasses can be solved efficiently)\n",
        "Why formulate problems as CSPs? (1) easy, natural representation (2) lots of work into making solves fast/efficient (3) solve can quickly prune large parts of the search space (vs atomic state-space searcher - can only ask if specific state is goal).\n",
        "Ex. coloring Australian states, job-shop scheduling (precedence/disjunctive constraints).\n",
        "Can transform every finite-domain constraint to a set of binary constraint if enough auxiliary variables are introduced, makes algorithm design easier.\n",
        "Can use dual graph transformation n-ary --> binary csp, though may prefer global constraint b/c (1) easier/less error-prone to write problem description (2) can design more efficient special-purpose interface algorithms.\n",
        " \"\"\"\n",
        "chapter6_2 = \"\"\" \n",
        "CSP algorithm can generate successors by choosing new variable assignment or constraint propogation. Idea of constraint propogation is that it will leave fewer choices to consider when making next choice of a variable assignment; \n",
        "can be intertwined w/ search or as preprocessing step; can sometimes solve the whole problem. Key idea is that enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.\n",
        "$X_i$ arc-consistent wrt $X_j$ if for all values in $D_i$, there's some value in $D_j$ that safisfies binary constraint $(X_i, X_j)$. \n",
        "AC-3 is most popular algorithm for enforcing arc consistency; maintains queue of arcs to consider (initially all arcs, w/ each binary constraint = two arcs); pops off arbitrary arc $(X_i, X_j)$ from queue and makes $X_i$ arc-consistent wrt $X_j$. \n",
        "AC-3 complexity: n variables, each with domain size at most d, w/ c binary constraints. Each edge ($X_k, X_i)$ can be inserted into queue at most $d$ times b/c $X_i$ has at most $d$ values to delete. Checking consistency of arc is $O(d^2)$ time.\n",
        "Total: $O(cd^3)$ time. Path consistency tightenes binary constraints using implicit constraints inferred by triplets; refers to overall consistency of the path from $X_i$ to $X_m$ to $X_j$.\n",
        "1-consisstency = node consistency; 2-consistency = arc consistncy; 3-consistency = path consistency. If graph is k-consistent, can solve in $O(n^2d)$ time b/c for each variable $X_i$, only need to search through $d$ values in domain to find value consistent w/ $X_1, .., X_{i-1}$.\n",
        "Establishing n-consistency is NP-complete, requiring exponential space and time. For global constraints, can detect inconsistency if $m$ variables involed in constraint w/ n possible distinct values altogether, and $m>n$ --> unsatsifiable constraint; \n",
        "then algorithm: (1) remove any variable in constraint w/ single value in domain (2) delete that variable's value form domains of remaining variables (3) repeat as long as singleton variables; if ever empty domain or # variables > # domain values left, then detected inconsistency.\n",
        "Resource constraints: can detect inconsistency checking sum of min values of current domains; can enforce consistency by deleting max value of any domain not consistent w/ min values of the other domains.\n",
        "Power of CSP formalism is that for each new problem area, we only need to define the problem in terms of constraints and then general constraint-solving mechanisms can take over.\n",
        " \"\"\"\n",
        "chapter6_3 = \"\"\" \n",
        "Standard depth-limited search for csp w/ n vars of domain size $d$=$n!d^n$ leaves, but only $d^n$ possible complete assignments (branching factor would be $nd$, $(n-1)d$, .... for $n$ levels).\n",
        "Bc of commutativity, only need consider 1 var at each node in search tree --> $d^n$ leaves. Backtracking search only keeps 1 representation of a state/assignment & alters instead creating new ones.\n",
        "Backtracking search improved w/ domain-independent heruistics (vs domain-specific heruistics w/ uninformed search), taking advantage of factored representation.\n",
        "(1) Which var assigned next? Order should its values be tried?\n",
        "Simple strategies: static or random ordering.\n",
        "Minimum-remaining-values (MRV) heuristic can prune pointless searches by detecting failure early; usually better than random/static ordering.\n",
        "When every region has same # legal values, degree heuristic attempts to reduce branching factor. MRV usually more powerful, but degree good as tie-breaker.\n",
        "Which order to examine values: least-constraining-value heruistic - tries to leave the maximum flexibility for subsequent var assignments.\n",
        "Var selection fail-1st, but value selection fail-last b/c every var needs assignment eventually, so failing first --> less assignments to backtrack over; \n",
        "look for most likely value first (if wanted all solutions instead of just 1, value ordering then irrelevant).\n",
        "(2)What inferences should be performed at each step in the search?\n",
        "Powerful during search; everytime make value choice for var, opportunity to infer new domain reductions on neighbors.\n",
        "Forward checking: for each unassigned neighbor, delete any values inconsistent w/ chosen value; can eliminate branching by propogating info/detect inconsistent partial assignments so can backtrack immediately.\n",
        "But doesn't look ahead far enough\n",
        "Combo MRV + forward checking together very effective.\n",
        "MAC: after var $X_i$ assigned a value, INFERENCE procedure calls AC-3, but instead of queue of all arcs in CSP, start with arcs $(X_i, X_i)$ for all $X_j$ that are unassigned variables that are neighbors of $X_i$.\n",
        "Then AC-3 constraint propogates; if any var's domain becomes empty, call to AC-3 fails & know to backtrack immediately. \n",
        "MAC strictly more powerful than forward checking (which does same thing on initial arcs but doesn't recursively propogate constraints when var's domain changes).\n",
        "(3) BACKTRACK >1 step when appropriate?\n",
        "Approach: backtrack to var that might fix problem; Keep track of conflict set. Can use bacakjumping. Every branch pruned by backjumping also pruned by forward checking.\n",
        "Conflict-directed backjumping approach: $X_j$ current var, $conf(X_j)$ its conflict set; if every possible value for $X_j$ fails, backjump to most recent variable $X_i$ in $conf(X_j)$ and recompute $conf(X_i)$ <-- $conf(X_i) \\cup conf(X_j) - \\{X_i\\}$\n",
        "(4) Save/reuse partial results from the search?\n",
        "Avoid same probs w/ constraint learning; record no-goods by adding new constraint or keeping cache\n",
        " \"\"\"\n",
        "chapter6_4 = \"\"\" \n",
        "Local search algs use complete-state formulation where each state assigned a val to every var & the search changes the val of 1 var at a time (randomly cosen conflicted var) to val that brings us close to solution (min-conflict heuristic).\n",
        "Min-conflicts very effective. Landscape of a CSP under the min-conflicts heuristic usually has a series of plateaus (many assignments only 1 conflict away from a solution).\n",
        "Plateau search (allowing sideways moves to another state w/ same score) can help local search off plateau (tabu search).\n",
        "Constraint weighting: each constraints given numeric weight, initally 1. each step, alg chooses variable/value pair to change resulting in lowest total weight of all violated constraints; weights adjusted by incrementing weight of each constraint violated by the current assignment.\n",
        "2 benefits: (1) adds topography to plateaus, making sure it's possible to improve from current state (2) adds learning, over time difficult constraints assigned higher weights.\n",
        "Local search can be used in online setting where problem changes.\n",
        " \"\"\"\n",
        "chapter6_5 = \"\"\" \n",
        "Independence can be found by finding connected components of the constraint graph; each component corresponds to a subproblem CSP. \n",
        "If n/c subproblems, ecah takes at most $d^c$ work to solve, total work $O(d^c n/c)$, linear in $n$ (compared to $O(d^n)$).\n",
        "Any tree-structured CSP can be solved in time linear in the number of variables; key is directional arc consistency, topo sort in $O(nd^2)$ time; $O(n)$ steps, each comparing up to $d$ possible domain values for 2 variables, don't need to backtrack.\n",
        "Cutset conditioning: reduce constraint graph to tree by assigning values to some variables so the remaining variables form a tree. For general case, val chosen could be wrong, so need to try each possible val.\n",
        "General alg:\n",
        "(1) chose cycel cutset\n",
        "(2) For each possible assignment to the variables in $S$ that satisfies all constraints on $S$ (a) remove from domains of remaining vars any vals that are inconsistent w/ assignment $S$ (b) if remaining CSP has solution, return it together w/ the assignment for $S$\n",
        "If cutset has size $c$, then total runtime $O(d^c \\cdot (n-c)d^2)$; have to try each of $d^c$ combos of vals for vars in $S$ and for each combo, must solve tree problem of size $n-c$.\n",
        "If graph is \"nearly a tree\", then $c$ will be small abd savings over backtracking are huge, but worst case $c=n-2$. Finding smallest cycle cutset is NP-hard, but several efficient approximation algs.\n",
        "Tree decomposition requirements:\n",
        "(1) every var in original problem appears in at least 1 of the tree nodes\n",
        "(2) if 2 vars connected by a constraint in original problem, they must appear together (along w/ constraint) in at least one of the tree nodes\n",
        "(3) if var appears in 2 nodes in the tree, must appear in every node along the path connecting those nodes\n",
        "1st 2 ensure all variables/constraints represented; 3rd so any variable from original problem must have same value wherever it appears\n",
        "Once have tree-structured graph, can get solution in $O(nd^2)$ time, $d$ is size of largest domain, but in tree, domain is set of tuples of values, not individual values.\n",
        "A graph admits many tree decomps, chose one to make the subproblems as small as possible. If graph has width $w$ then can be solved $O(nd^{w+1})$.\n",
        "So CSP's w/ cnstraint graphs of bounded tree width are solvable in polytime, though finding decomp w/ width is NP-hard (but heuristic methods).\n",
        "Cutset vs Tree decomp: whenever cycle-cutset of size $c$, also tree width of size $w < c + 1$ and can be far smaller.\n",
        "(1) Time: $O(d^c \\cdot (n-c)d^2)$ vs $O(nd^{w+1})$; favors tree\n",
        "(2) Space: cycle-cutset linear memory, while tree exponential in $w$\n",
        "Value symmetry - introduce symmetry-breaking constraint; can impose arbitrary order for coloring. NP-hard in general to elimate all symmetry, but breaking value symmetry proven important/effective on wide range of problems\n",
        "\n",
        " \"\"\"\n",
        "\n",
        "\n",
        "# Lecture notes \n",
        "module6_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module6_definitions = {\n",
        "\"csp (constraint satisfaction problem)\" : \"set of variables, each with a value (solved when value satisfies all constraints on the vairable\",\n",
        "\"assignment\" : \"e.g. $\\{ X_i = v_i, X_j = v_j, ...\\}$\",\n",
        "\"consistent/legal assignment\" : \"assignment of values to variables that doesn't violate any constraints\",\n",
        "\"complete assignment\" : \"every variable is assigned a value\",\n",
        "\"solution (to csp)\" : \"consistent, complete assignemtn\",\n",
        "\"partial assignment\" : \"leaves some unassigned variables\",\n",
        "\"partial solution\" : \"consistent, partial assignment\", \n",
        "\"constraint graph\" : \"nodes = variables, edges = b/t any 2 variables participating in a constraint\",\n",
        "\"precedence constraints\" : \"task1 $T_1$ taking duration $d_1$ has to happen before task2 $T_2$ --> constraint $T_1 + d_1 \\leq T_2$\",\n",
        "\"disjunctive constraint\" : \"two tasks can't overlap in time $T_1 + $d_1$ \\leq T_2$ or $T_2 + d_2 \\leq T_1$\",\n",
        "\"discrete domain\" : \"domain w/ discrete values\", \n",
        "\"finite domain\" : \"domain w/ finite number of values\",\n",
        "\"infinite\" : \"domain w/ infinite number of values (e.g set of integers/strings), use implicit constraints ($T_1 + d_1 \\leq T_2$)\",\n",
        "\"linear constraints\" : \"constraints where each variable only appears in linear form (e.g. $T_1 + d_1 \\leq T_2$)\",\n",
        "\"nonlinear constraints\" : \"opposite of linear, no algorithm exists for solving on integer variables, undecidable problem\",\n",
        "\"continuous domains\" : \"common in real world, widely studied in operations research\",\n",
        "\"linear programming problems\" : \"constraints must be linear equalities/inequalities (best-known category of continuous-domain CSPs) can be solved in poly-time\",\n",
        "\"urnary constraint\" : \"restrict value of 1 varable\",\n",
        "\"binary constraint\" : \"relates 2 variables\",\n",
        "\"binary csp\" :\"only urnary and binary constraints, can be represented as consistent graph\",\n",
        "\"global constraint\" : \"involves arbitrary number of variables (not necessarily all) (e.g. Alldi ff - all involves variables must have different values)\",\n",
        "\"cryptarithmetic\" : \"each letter represents different digit (e.g. TWO + TWO = FOUR, Alldi ff and n-ary constraints)\",\n",
        "\"constraint hypergraph\" : \"ordinary nodes and hypernodes (represent n-ary constraints)\",\n",
        "\"dual graph\" : \"new graph w/ 1 variable/constraint in original, 1 binary constraint for each pair of constraints sharing variables\",\n",
        "\"preference constraints\" : \"indicate which solutions are preferred (vs absolute constraints - violation rules out potential solution)\",\n",
        "\"constrained optimization problem\" : \"problems solved with optimization search methods, preference constraints can be encoded as costs on individual variable assignments\",\n",
        "\"constraint propogation\": \"using constraints to reduce # legal values for variable, which in turn reduces for another etc\",\n",
        "\"local consistency\": \"treat variables as nodes, binary constraints as edges\",\n",
        "\"node consistency\" : \"(for single variable/node) all values in domain satisfy its urnary constraints; (for graph) every variable is node-consistent\",\n",
        "\"arc consistency\" : \"(variable) every value in domain satisfies its binary constraints; (graph) every variable is arc-consistent\",\n",
        "\"path consistency\" : \"$\\{X_i,X_j\\}$ wrt $X_m$: for every $\\{X_i=a,X_j=b\\}$ consistent w/ contraints on $\\{X_i,X_j \\}$, there's $X_m$ assignment satisfying $\\{X_i,X_m\\}$ and $\\{X_i,X_j\\}$ constraints\",\n",
        "\"k-consistency\" : \"for any consistent assignmenet to any set of $k-1$ variables, any kth value can always be assigned a consistent value\",\n",
        "\"strongly k-consistent\" : \"k-consistent, (k-1) consistent, ..., 1-consistent\",\n",
        "\"resource constraint\" : \"aka Atmost constraint; e.g. scheduling, at most 10 personnel assigned total to tasks\",\n",
        "\"bounds propagation\" : \"for large resource-limited problems w/ integer values (e.g. ariline scheduling - plane capacities)\",\n",
        "\"bounds-consistent\" : \"for every variable $X$ and its lower/upper bound values, $\\exist$ value of $Y$ satisfying constraint b/t $X$/$Y$ for every $Y$\",\n",
        "\"Sudoku\" : \"27 different Alldi ff constraints (1 per row/col/box)\",\n",
        "\"(Sudoku) unit\" : \"a row, column, or box\",\n",
        "\"commutativity\" : \"if the order of application of any given set of actions doesn't matter\",\n",
        "\"minimum-remaining-values\" : \"heuristic for which variables to choose next, aka most constraint variable or fail first\",\n",
        "\"degree heuristic\" : \"heuristic selecting variable involved in largest number of constraints on other unassigned variables\",\n",
        "\"least-constrainting value\" : \"heuristic preferring value that rules out fewest choices for neighboring variables in constraint graph\",\n",
        "\"forward checking\" : \"form of inference, whenever variable $X$ assigned, establishes arc consistency for it\",\n",
        "\"maintaining arc consistency\" : \"MAC algorithm; can detect inconsistencies missed by foward checking\",\n",
        "\"chronological backtracking\" : \"when branch of search fails, back up to preceding variable and try different value; most recent decision point revisited\",\n",
        "\"conflict set\" : \"set of assignments in conflict with some value for a variable, supplied by forward checking (elements deleted should be added)\",\n",
        "\"backjumping\" : \"mothod that backtracks to most recent assignment in conflict set\",\n",
        "\"conflict-directed backjumping\" : \"conflict set is of preceding variables that caused X together w/ any subsequent variables to have no consistent solution\",\n",
        "\"constraint learning\" : \"idea of finding a min set of variables from conflict set that causes the problem\",\n",
        "\"no-good\" : \"set of variables in constraint learning w/ their corresponding values; can be effectively used by forward checking or backjumping\",\n",
        "\"min-conflicts\" : \"value selection that results in the min number of conflicts w/ other variables\",\n",
        "\"tabu search\" : \"keeping small list of recently visited states and forbidding algorithm to return to those states; directs plateau wandering\",\n",
        "\"constraint weighting\" : \"aims to concentrate search on the important constraints\",\n",
        "\"independent subproblems\": \"if assignment $S_i$ solves $CSP_i$, then union of all $S_i$ solves of union of all $CSP_i$; rare\",\n",
        "\"connected component\" : \"\",\n",
        "\"directional arc consistency (DAC)\" : \"consistent under ordering $X_1,X_2,...,X_n$ iff every $X_i$ is arc-consistent with each $X_j$ for $j>i$\",\n",
        "\"topological sort\" : \"ordering of variables in rooted tree s.t. each variable appears after its parent in the tree\",\n",
        "\"cycle cutset\" : \"choosing subset $S$ of CSP's variables s.t. the constraint graph becomes a tree after removal\",\n",
        "\"cutset conditioning\" : \"algorithmic approach (described in summary)\",\n",
        "\"tree decomposition\" : \"transformation of original graph into a tree where each node consists of set of variables satisfying 3 requirements\",\n",
        "\"tree width\" : \"of tree decomposition is (size of largest node - 1); of graph is min width among its decomps\",\n",
        "\"value symmetry\" : \"consistent solutions that are permutations of themselves (e.g. coloring)\",\n",
        "\"symmetry-breaking constraint\" : \"to reduce search space of factor $d!$ by breaking symmetry in assignments\",\n",
        "}"
      ],
      "execution_count": 85,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "kKWbCsbfxL3R",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "6079b655-e019-450b-d9d3-4dd7e614d0cb"
      },
      "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": 86,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCsp has (1) set of variables (2) set of domains, 1 for each variable w/ allowable values for that variable (3) set of constraints specifying allowable combos of vals.\nSolving is NP-complete in general (though important subclasses can be solved efficiently)\nWhy formulate problems as CSPs? (1) easy, natural representation (2) lots of work into making solves fast/efficient (3) solve can quickly prune large parts of the search space (vs atomic state-space searcher - can only ask if specific state is goal).\nEx. coloring Australian states, job-shop scheduling (precedence/disjunctive constraints).\nCan transform every finite-domain constraint to a set of binary constraint if enough auxiliary variables are introduced, makes algorithm design easier.\nCan use dual graph transformation n-ary --> binary csp, though may prefer global constraint b/c (1) easier/less error-prone to write problem description (2) can design more efficient special-purpose interface algorithms.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nCSP algorithm can generate successors by choosing new variable assignment or constraint propogation. Idea of constraint propogation is that it will leave fewer choices to consider when making next choice of a variable assignment; \ncan be intertwined w/ search or as preprocessing step; can sometimes solve the whole problem. Key idea is that enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.\n$X_i$ arc-consistent wrt $X_j$ if for all values in $D_i$, there's some value in $D_j$ that safisfies binary constraint $(X_i, X_j)$. \nAC-3 is most popular algorithm for enforcing arc consistency; maintains queue of arcs to consider (initially all arcs, w/ each binary constraint = two arcs); pops off arbitrary arc $(X_i, X_j)$ from queue and makes $X_i$ arc-consistent wrt $X_j$. \nAC-3 complexity: n variables, each with domain size at most d, w/ c binary constraints. Each edge ($X_k, X_i)$ can be inserted into queue at most $d$ times b/c $X_i$ has at most $d$ values to delete. Checking consistency of arc is $O(d^2)$ time.\nTotal: $O(cd^3)$ time. Path consistency tightenes binary constraints using implicit constraints inferred by triplets; refers to overall consistency of the path from $X_i$ to $X_m$ to $X_j$.\n1-consisstency = node consistency; 2-consistency = arc consistncy; 3-consistency = path consistency. If graph is k-consistent, can solve in $O(n^2d)$ time b/c for each variable $X_i$, only need to search through $d$ values in domain to find value consistent w/ $X_1, .., X_{i-1}$.\nEstablishing n-consistency is NP-complete, requiring exponential space and time. For global constraints, can detect inconsistency if $m$ variables involed in constraint w/ n possible distinct values altogether, and $m>n$ --> unsatsifiable constraint; \nthen algorithm: (1) remove any variable in constraint w/ single value in domain (2) delete that variable's value form domains of remaining variables (3) repeat as long as singleton variables; if ever empty domain or # variables > # domain values left, then detected inconsistency.\nResource constraints: can detect inconsistency checking sum of min values of current domains; can enforce consistency by deleting max value of any domain not consistent w/ min values of the other domains.\nPower of CSP formalism is that for each new problem area, we only need to define the problem in terms of constraints and then general constraint-solving mechanisms can take over.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nStandard depth-limited search for csp w/ n vars of domain size $d$=$n!d^n$ leaves, but only $d^n$ possible complete assignments (branching factor would be $nd$, $(n-1)d$, .... for $n$ levels).\nBc of commutativity, only need consider 1 var at each node in search tree --> $d^n$ leaves. Backtracking search only keeps 1 representation of a state/assignment & alters instead creating new ones.\nBacktracking search improved w/ domain-independent heruistics (vs domain-specific heruistics w/ uninformed search), taking advantage of factored representation.\n(1) Which var assigned next? Order should its values be tried?\nSimple strategies: static or random ordering.\nMinimum-remaining-values (MRV) heuristic can prune pointless searches by detecting failure early; usually better than random/static ordering.\nWhen every region has same # legal values, degree heuristic attempts to reduce branching factor. MRV usually more powerful, but degree good as tie-breaker.\nWhich order to examine values: least-constraining-value heruistic - tries to leave the maximum flexibility for subsequent var assignments.\nVar selection fail-1st, but value selection fail-last b/c every var needs assignment eventually, so failing first --> less assignments to backtrack over; \nlook for most likely value first (if wanted all solutions instead of just 1, value ordering then irrelevant).\n(2)What inferences should be performed at each step in the search?\nPowerful during search; everytime make value choice for var, opportunity to infer new domain reductions on neighbors.\nForward checking: for each unassigned neighbor, delete any values inconsistent w/ chosen value; can eliminate branching by propogating info/detect inconsistent partial assignments so can backtrack immediately.\nBut doesn't look ahead far enough\nCombo MRV + forward checking together very effective.\nMAC: after var $X_i$ assigned a value, INFERENCE procedure calls AC-3, but instead of queue of all arcs in CSP, start with arcs $(X_i, X_i)$ for all $X_j$ that are unassigned variables that are neighbors of $X_i$.\nThen AC-3 constraint propogates; if any var's domain becomes empty, call to AC-3 fails & know to backtrack immediately. \nMAC strictly more powerful than forward checking (which does same thing on initial arcs but doesn't recursively propogate constraints when var's domain changes).\n(3) BACKTRACK >1 step when appropriate?\nApproach: backtrack to var that might fix problem; Keep track of conflict set. Can use bacakjumping. Every branch pruned by backjumping also pruned by forward checking.\nConflict-directed backjumping approach: $X_j$ current var, $conf(X_j)$ its conflict set; if every possible value for $X_j$ fails, backjump to most recent variable $X_i$ in $conf(X_j)$ and recompute $conf(X_i)$ <-- $conf(X_i) \\cup conf(X_j) - \\{X_i\\}$\n(4) Save/reuse partial results from the search?\nAvoid same probs w/ constraint learning; record no-goods by adding new constraint or keeping cache\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search algs use complete-state formulation where each state assigned a val to every var & the search changes the val of 1 var at a time (randomly cosen conflicted var) to val that brings us close to solution (min-conflict heuristic).\nMin-conflicts very effective. Landscape of a CSP under the min-conflicts heuristic usually has a series of plateaus (many assignments only 1 conflict away from a solution).\nPlateau search (allowing sideways moves to another state w/ same score) can help local search off plateau (tabu search).\nConstraint weighting: each constraints given numeric weight, initally 1. each step, alg chooses variable/value pair to change resulting in lowest total weight of all violated constraints; weights adjusted by incrementing weight of each constraint violated by the current assignment.\n2 benefits: (1) adds topography to plateaus, making sure it's possible to improve from current state (2) adds learning, over time difficult constraints assigned higher weights.\nLocal search can be used in online setting where problem changes.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nIndependence can be found by finding connected components of the constraint graph; each component corresponds to a subproblem CSP. \nIf n/c subproblems, ecah takes at most $d^c$ work to solve, total work $O(d^c n/c)$, linear in $n$ (compared to $O(d^n)$).\nAny tree-structured CSP can be solved in time linear in the number of variables; key is directional arc consistency, topo sort in $O(nd^2)$ time; $O(n)$ steps, each comparing up to $d$ possible domain values for 2 variables, don't need to backtrack.\nCutset conditioning: reduce constraint graph to tree by assigning values to some variables so the remaining variables form a tree. For general case, val chosen could be wrong, so need to try each possible val.\nGeneral alg:\n(1) chose cycel cutset\n(2) For each possible assignment to the variables in $S$ that satisfies all constraints on $S$ (a) remove from domains of remaining vars any vals that are inconsistent w/ assignment $S$ (b) if remaining CSP has solution, return it together w/ the assignment for $S$\nIf cutset has size $c$, then total runtime $O(d^c \\cdot (n-c)d^2)$; have to try each of $d^c$ combos of vals for vars in $S$ and for each combo, must solve tree problem of size $n-c$.\nIf graph is \"nearly a tree\", then $c$ will be small abd savings over backtracking are huge, but worst case $c=n-2$. Finding smallest cycle cutset is NP-hard, but several efficient approximation algs.\nTree decomposition requirements:\n(1) every var in original problem appears in at least 1 of the tree nodes\n(2) if 2 vars connected by a constraint in original problem, they must appear together (along w/ constraint) in at least one of the tree nodes\n(3) if var appears in 2 nodes in the tree, must appear in every node along the path connecting those nodes\n1st 2 ensure all variables/constraints represented; 3rd so any variable from original problem must have same value wherever it appears\nOnce have tree-structured graph, can get solution in $O(nd^2)$ time, $d$ is size of largest domain, but in tree, domain is set of tuples of values, not individual values.\nA graph admits many tree decomps, chose one to make the subproblems as small as possible. If graph has width $w$ then can be solved $O(nd^{w+1})$.\nSo CSP's w/ cnstraint graphs of bounded tree width are solvable in polytime, though finding decomp w/ width is NP-hard (but heuristic methods).\nCutset vs Tree decomp: whenever cycle-cutset of size $c$, also tree width of size $w < c + 1$ and can be far smaller.\n(1) Time: $O(d^c \\cdot (n-c)d^2)$ vs $O(nd^{w+1})$; favors tree\n(2) Space: cycle-cutset linear memory, while tree exponential in $w$\nValue symmetry - introduce symmetry-breaking constraint; can impose arbitrary order for coloring. NP-hard in general to elimate all symmetry, but breaking value symmetry proven important/effective on wide range of problems\n\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp (constraint satisfaction problem)** - set of variables, each with a value (solved when value satisfies all constraints on the vairable\n* **Assignment** - e.g. $\\{ X_i = v_i, X_j = v_j, ...\\}$\n* **Consistent/legal assignment** - assignment of values to variables that doesn't violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Solution (to csp)** - consistent, complete assignemtn\n* **Partial assignment** - leaves some unassigned variables\n* **Partial solution** - consistent, partial assignment\n* **Constraint graph** - nodes = variables, edges = b/t any 2 variables participating in a constraint\n* **Precedence constraints** - task1 $T_1$ taking duration $d_1$ has to happen before task2 $T_2$ --> constraint $T_1 + d_1 \\leq T_2$\n* **Disjunctive constraint** - two tasks can't overlap in time $T_1 + $d_1$ \\leq T_2$ or $T_2 + d_2 \\leq T_1$\n* **Discrete domain** - domain w/ discrete values\n* **Finite domain** - domain w/ finite number of values\n* **Infinite** - domain w/ infinite number of values (e.g set of integers/strings), use implicit constraints ($T_1 + d_1 \\leq T_2$)\n* **Linear constraints** - constraints where each variable only appears in linear form (e.g. $T_1 + d_1 \\leq T_2$)\n* **Nonlinear constraints** - opposite of linear, no algorithm exists for solving on integer variables, undecidable problem\n* **Continuous domains** - common in real world, widely studied in operations research\n* **Linear programming problems** - constraints must be linear equalities/inequalities (best-known category of continuous-domain CSPs) can be solved in poly-time\n* **Urnary constraint** - restrict value of 1 varable\n* **Binary constraint** - relates 2 variables\n* **Binary csp** - only urnary and binary constraints, can be represented as consistent graph\n* **Global constraint** - involves arbitrary number of variables (not necessarily all) (e.g. Alldi ff - all involves variables must have different values)\n* **Cryptarithmetic** - each letter represents different digit (e.g. TWO + TWO = FOUR, Alldi ff and n-ary constraints)\n* **Constraint hypergraph** - ordinary nodes and hypernodes (represent n-ary constraints)\n* **Dual graph** - new graph w/ 1 variable/constraint in original, 1 binary constraint for each pair of constraints sharing variables\n* **Preference constraints** - indicate which solutions are preferred (vs absolute constraints - violation rules out potential solution)\n* **Constrained optimization problem** - problems solved with optimization search methods, preference constraints can be encoded as costs on individual variable assignments\n* **Constraint propogation** - using constraints to reduce # legal values for variable, which in turn reduces for another etc\n* **Local consistency** - treat variables as nodes, binary constraints as edges\n* **Node consistency** - (for single variable/node) all values in domain satisfy its urnary constraints; (for graph) every variable is node-consistent\n* **Arc consistency** - (variable) every value in domain satisfies its binary constraints; (graph) every variable is arc-consistent\n* **Path consistency** - $\\{X_i,X_j\\}$ wrt $X_m$: for every $\\{X_i=a,X_j=b\\}$ consistent w/ contraints on $\\{X_i,X_j \\}$, there's $X_m$ assignment satisfying $\\{X_i,X_m\\}$ and $\\{X_i,X_j\\}$ constraints\n* **K-consistency** - for any consistent assignmenet to any set of $k-1$ variables, any kth value can always be assigned a consistent value\n* **Strongly k-consistent** - k-consistent, (k-1) consistent, ..., 1-consistent\n* **Resource constraint** - aka Atmost constraint; e.g. scheduling, at most 10 personnel assigned total to tasks\n* **Bounds propagation** - for large resource-limited problems w/ integer values (e.g. ariline scheduling - plane capacities)\n* **Bounds-consistent** - for every variable $X$ and its lower/upper bound values, $\\exist$ value of $Y$ satisfying constraint b/t $X$/$Y$ for every $Y$\n* **Sudoku** - 27 different Alldi ff constraints (1 per row/col/box)\n* **(sudoku) unit** - a row, column, or box\n* **Commutativity** - if the order of application of any given set of actions doesn't matter\n* **Minimum-remaining-values** - heuristic for which variables to choose next, aka most constraint variable or fail first\n* **Degree heuristic** - heuristic selecting variable involved in largest number of constraints on other unassigned variables\n* **Least-constrainting value** - heuristic preferring value that rules out fewest choices for neighboring variables in constraint graph\n* **Forward checking** - form of inference, whenever variable $X$ assigned, establishes arc consistency for it\n* **Maintaining arc consistency** - MAC algorithm; can detect inconsistencies missed by foward checking\n* **Chronological backtracking** - when branch of search fails, back up to preceding variable and try different value; most recent decision point revisited\n* **Conflict set** - set of assignments in conflict with some value for a variable, supplied by forward checking (elements deleted should be added)\n* **Backjumping** - mothod that backtracks to most recent assignment in conflict set\n* **Conflict-directed backjumping** - conflict set is of preceding variables that caused X together w/ any subsequent variables to have no consistent solution\n* **Constraint learning** - idea of finding a min set of variables from conflict set that causes the problem\n* **No-good** - set of variables in constraint learning w/ their corresponding values; can be effectively used by forward checking or backjumping\n* **Min-conflicts** - value selection that results in the min number of conflicts w/ other variables\n* **Tabu search** - keeping small list of recently visited states and forbidding algorithm to return to those states; directs plateau wandering\n* **Constraint weighting** - aims to concentrate search on the important constraints\n* **Independent subproblems** - if assignment $S_i$ solves $CSP_i$, then union of all $S_i$ solves of union of all $CSP_i$; rare\n* **Connected component** - \n* **Directional arc consistency (dac)** - consistent under ordering $X_1,X_2,...,X_n$ iff every $X_i$ is arc-consistent with each $X_j$ for $j>i$\n* **Topological sort** - ordering of variables in rooted tree s.t. each variable appears after its parent in the tree\n* **Cycle cutset** - choosing subset $S$ of CSP's variables s.t. the constraint graph becomes a tree after removal\n* **Cutset conditioning** - algorithmic approach (described in summary)\n* **Tree decomposition** - transformation of original graph into a tree where each node consists of set of variables satisfying 3 requirements\n* **Tree width** - of tree decomposition is (size of largest node - 1); of graph is min width among its decomps\n* **Value symmetry** - consistent solutions that are permutations of themselves (e.g. coloring)\n* **Symmetry-breaking constraint** - to reduce search space of factor $d!$ by breaking symmetry in assignments\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",
        "TELL: add new sentences to KB; ASK: query what is known. Inference must obey requirement that when one ASKS question of KB, answer should follow from what has been TELLed previously.\n",
        "AKA inference shouldn't make up things as it goes along. Like other agents, KB-agent takes precept and returns an action.\n",
        "Each time agent program called: \n",
        "(1) TELLS KB what it perceives \n",
        "(2) ASKS KB what action it should perform; extensive reasoning may be done about current state of world/outcomes of possible action sequences etc \n",
        "(3) TELLS KB what action was chosen and returns action so it can be executed\n",
        "MAKE-PRECEPT-SENTENCE construct a sentence asserting that the agent perceived the given precept at the given time.\n",
        "MAKE-ACTION-QUERY constructs a sentence that asks what action should be done at the current time.\n",
        "MAKE-ACTION-SENTENCE constructs a sentence asserting that the chosen action was executed.\n",
        "KB-agent amendable to a description at knowledge level; only need specify what agent knows/its gals to determine KB-agent's behavior\n",
        "Successful agent often combines declarative + procedural elements in its design & that declarative knowledge can often be compiled into more efficeint procedural code.\n",
        "Can provide mechanisms that allow to learn for itself, creating general knowledge about envrionment from series of precepts; learning agent can be fully autonomous.\n",
        " \"\"\"\n",
        "chapter7_2 = \"\"\" \n",
        "Def of task envrionment:\n",
        "(1) performance measure: +1000 for climbing out w/ gold, -1000 falling into pit/eaten by wampu, -1/action taken, -10 using arrow; ends when agent dies/climbs out\n",
        "(2) envrionment: 4x4 grid of rooms, walls surroudnign grid, starts $\\[1, 1\\]$, gold/wampus locations chosen uniformly at random; pit w/p .2\n",
        "(3) actualtor: agent can move Forward, Turn Left/Right; dies if enters square w/ pit/live wumpus; bumps wall then doesn't move, grab can pick up gold, shoot to fire arrow (until hit wumpus/wall), climb out of cave only from [1,1]\n",
        "(4) sensors: [stench, breeze, glitter, bump, scream (wumpus killed)]\n",
        "Wumpus envrionment: deterministic, discrete, static, single-agent (wampus doesn't move). Sequential: rewards only after many actions taken. Partially observable: some aspects of state not directly perceivable\n",
        "Main challenge is overcoming initial ignorance, requires logical reasoning. \n",
        "In each case for which agent draws a conclusion from available info, conclusion guaranteed to be correct if available info is correct = fundamental property of logical reasoning\n",
        " \"\"\"\n",
        "chapter7_3 = \"\"\" \n",
        "$M(\\alpha)$ is set of all models of $\\alpha$.\n",
        "Entailment formal def: if alpha emtails beta iff $M(\\alpha) \\subseteq M(\\Beta)$.\n",
        "KB like set of sentences, false if contradicts agent knowledge. Entailment can be applied to carry out logical inference.\n",
        "$KB \\vdash _i \\lpha$ alpha is derived from KB by i, i derives alpha from KB.\n",
        "If KB is true in the real world, then any sentence alpha derives form KB by a sound inference procedure is also true in the real world.\n",
        "grounding: meaning/truth of precept sentences defined by processes of sensing and sentence construction that produce them \n",
        " \"\"\"\n",
        "chapter7_4 = \"\"\" \n",
        "operator precedent: not, and, or, implies, biconditional.\n",
        "\"\"\"\n",
        "chapter7_5 = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Lecture notes \n",
        "module7_lecture_notes = \"\"\" Your summary here \"\"\"\n",
        "\n",
        "# Definitions\n",
        "module7_definitions = {\n",
        "\"knowledge-based agents\" : \"decides what actions to take using reasoning over internal representation of knowledge\",\n",
        "\"reasoning\" : \"definition\",\n",
        "\"representation\" : \"definition\",\n",
        "\"knowledge base\" : \"KB, central component of a knowledge-based agent\",\n",
        "\"sentence\" : \"make up knowledge base, expressed in a knowledge representation language and represents some about the world\",\n",
        "\"knowledge representation language\" : \"definition\",\n",
        "\"axiom\" : \"when sentence taken as given, not derived from other sentences\",\n",
        "\"inference\" : \"deriving new sentences from old\",\n",
        "\"background knowledge\" : \"initial info in knowledge base\",\n",
        "\"knowledge level\" : \"info about actions b/c it knows that it will achieve its goal (independent from implementation)\",\n",
        "\"implementation level\" : \"e.g. how a taxei works (geographical knowledge implemented as linked lists, pixel maps etc\",\n",
        "\"declarative\" : \"approach where TELL sentences 1 by 1 until agent knows how to operate in its envrionment\",\n",
        "\"procedural\" : \"approach encodes desired behaviors directly as program code\",\n",
        "\"wumpus world\" : \"cave of rooms connected by passageways; wumpus (beast), agent (w/ 1 arrow), bottomless pits, gold\",\n",
        "\"syntax\" : \"specifies well formed sentences of the representation language\",\n",
        "\"semantics\" : \"meaning of sentences, defines truth wrt each possible world\",\n",
        "\"truth\" : \"only true/false\",\n",
        "\"possible world\" : \"definition\",\n",
        "\"model\" : \"aka possible world, math abstraction, each w/ fixed truth value for every relevant sentence\",\n",
        "\"satisfaction\" : \"alpha satisfies m same m satisfies alpha same m is a model of alpha\",\n",
        "\"entailment\" : \"sentences flowing logically from one another (vertical bar equals sign)\",\n",
        "\"logical inference\" : \"derive conclusions\",\n",
        "\"model checking\" : \"enumerates all model possibilities to check $M(KB) \\subseteq M(\\alpha)$, works if finite model space\",\n",
        "\"sound\" : \"derives only entailed sentences\",\n",
        "\"truth-preserving\" : \"same as sound\",\n",
        "\"completeness\" : \"derives all sound sentences\",\n",
        "\"grounding\" : \"connects logical reasoning processes and real envrionment in which the agent exists, simplest: agent's sensors\",\n",
        "\"learning\" : \"sentence construction process that produces general rules\",\n",
        "\"propositional logic\" : \"definition\",\n",
        "\"atomic sentences\" : \"single prop symbol\",\n",
        "\"proposition symbol\" : \"stands for prop that's true or false\",\n",
        "\"complex sentences\" : \"simpler sentences connected by parathesees/logical connectives\",\n",
        "\"logical connectives\" : \"definition\",\n",
        "\"negation\" : \"definition\",\n",
        "\"literal\" : \"atomic sentence or negated atomic sentence (pos/neg)\",\n",
        "\"conjunction\" : \"parts are conjucts\",\n",
        "\"disjunction\" : \"parts are disjuncts\",\n",
        "\"implication\" : \"premise/antecedent implies conclusion/consequent, rules, if-then statements\",\n",
        "\"premise\" : \"definition\",\n",
        "\"conclusion\" : \"definition\",\n",
        "\"rules\" : \"definition\",\n",
        "\"biconditional\" : \"definition\",\n",
        "\"truth value\" : \"true/false assigned to every propositional symbol\",\n",
        "\"truth table\" : \"specify truth value of complex sentence for all possible component assignments\",\n",
        "\"theorem proving\" : \"definition\",\n",
        "\"logical equivalence\" : \"definition\",\n",
        "\"validity\" : \"definition\",\n",
        "\"tautology\" : \"definition\",\n",
        "\"deduction theorem\" : \"definition\",\n",
        "\"satisfiability\" : \"definition\",\n",
        "\"SAT\" : \"definition\",\n",
        "\"reductio ad absurdum\" : \"definition\",\n",
        "\"refutation\" : \"definition\",\n",
        "\"contradiction\" : \"definition\",\n",
        "\"inference rules\" : \"definition\",\n",
        "\"proof\" : \"definition\",\n",
        "\"modus pomens\" : \"definition\",\n",
        "\"and-elimination\" : \"definition\",\n",
        "\"monotonicity\" : \"definition\",\n",
        "\"resolvent\" : \"definition\",\n",
        "\"unit resolution\" : \"definition\",\n",
        "\"complementary literals\" : \"definition\",\n",
        "\"clause\" : \"definition\",\n",
        "\"unit clause\" : \"definition\",\n",
        "\"resolution\" : \"definition\",\n",
        "\"factoring\" : \"definition\",\n",
        "\"conjunctive normal form / CNF\" : \"definition\",\n",
        "\"resolution closure\" : \"definition\",\n",
        "\"ground resolution theorem\" : \"definition\",\n",
        "\"definite clause\" : \"definition\",\n",
        "\"horn clause\" : \"definition\",\n",
        "\"goal clauses\" : \"definition\",\n",
        "\"body\" : \"definition\",\n",
        "\"head\" : \"definition\",\n",
        "\"fact\" : \"definition\",\n",
        "\"forward-chaining\" : \"definition\",\n",
        "\"backward-chaining\" : \"definition\",\n",
        "\"data-driven\" : \"definition\",\n",
        "\"goal-directed reasoning\" : \"definition\",   \n",
        "}\n",
        "\n"
      ],
      "execution_count": 87,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "cellView": "form",
        "id": "lXNcHuKjyNXa",
        "colab": {
          "base_uri": "https://localhost:8080/",
          "height": 1000
        },
        "outputId": "76b6cee0-b3bb-4b03-f57d-eab86843fe8b"
      },
      "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": 88,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nTELL: add new sentences to KB; ASK: query what is known. Inference must obey requirement that when one ASKS question of KB, answer should follow from what has been TELLed previously.\nAKA inference shouldn't make up things as it goes along. Like other agents, KB-agent takes precept and returns an action.\nEach time agent program called: \n(1) TELLS KB what it perceives \n(2) ASKS KB what action it should perform; extensive reasoning may be done about current state of world/outcomes of possible action sequences etc \n(3) TELLS KB what action was chosen and returns action so it can be executed\nMAKE-PRECEPT-SENTENCE construct a sentence asserting that the agent perceived the given precept at the given time.\nMAKE-ACTION-QUERY constructs a sentence that asks what action should be done at the current time.\nMAKE-ACTION-SENTENCE constructs a sentence asserting that the chosen action was executed.\nKB-agent amendable to a description at knowledge level; only need specify what agent knows/its gals to determine KB-agent's behavior\nSuccessful agent often combines declarative + procedural elements in its design & that declarative knowledge can often be compiled into more efficeint procedural code.\nCan provide mechanisms that allow to learn for itself, creating general knowledge about envrionment from series of precepts; learning agent can be fully autonomous.\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \nDef of task envrionment:\n(1) performance measure: +1000 for climbing out w/ gold, -1000 falling into pit/eaten by wampu, -1/action taken, -10 using arrow; ends when agent dies/climbs out\n(2) envrionment: 4x4 grid of rooms, walls surroudnign grid, starts $\\[1, 1\\]$, gold/wampus locations chosen uniformly at random; pit w/p .2\n(3) actualtor: agent can move Forward, Turn Left/Right; dies if enters square w/ pit/live wumpus; bumps wall then doesn't move, grab can pick up gold, shoot to fire arrow (until hit wumpus/wall), climb out of cave only from [1,1]\n(4) sensors: [stench, breeze, glitter, bump, scream (wumpus killed)]\nWumpus envrionment: deterministic, discrete, static, single-agent (wampus doesn't move). Sequential: rewards only after many actions taken. Partially observable: some aspects of state not directly perceivable\nMain challenge is overcoming initial ignorance, requires logical reasoning. \nIn each case for which agent draws a conclusion from available info, conclusion guaranteed to be correct if available info is correct = fundamental property of logical reasoning\n \n\n## AIMA Chapter 7.3 Logic\n \n$M(\u0007lpha)$ is set of all models of $\u0007lpha$.\nEntailment formal def: if alpha emtails beta iff $M(\u0007lpha) \\subseteq M(\\Beta)$.\nKB like set of sentences, false if contradicts agent knowledge. Entailment can be applied to carry out logical inference.\n$KB \u000bdash _i \\lpha$ alpha is derived from KB by i, i derives alpha from KB.\nIf KB is true in the real world, then any sentence alpha derives form KB by a sound inference procedure is also true in the real world.\ngrounding: meaning/truth of precept sentences defined by processes of sensing and sentence construction that produce them \n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \noperator precedent: not, and, or, implies, biconditional.\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - decides what actions to take using reasoning over internal representation of knowledge\n* **Reasoning** - definition\n* **Representation** - definition\n* **Knowledge base** - KB, central component of a knowledge-based agent\n* **Sentence** - make up knowledge base, expressed in a knowledge representation language and represents some about the world\n* **Knowledge representation language** - definition\n* **Axiom** - when sentence taken as given, not derived from other sentences\n* **Inference** - deriving new sentences from old\n* **Background knowledge** - initial info in knowledge base\n* **Knowledge level** - info about actions b/c it knows that it will achieve its goal (independent from implementation)\n* **Implementation level** - e.g. how a taxei works (geographical knowledge implemented as linked lists, pixel maps etc\n* **Declarative** - approach where TELL sentences 1 by 1 until agent knows how to operate in its envrionment\n* **Procedural** - approach encodes desired behaviors directly as program code\n* **Wumpus world** - cave of rooms connected by passageways; wumpus (beast), agent (w/ 1 arrow), bottomless pits, gold\n* **Syntax** - specifies well formed sentences of the representation language\n* **Semantics** - meaning of sentences, defines truth wrt each possible world\n* **Truth** - only true/false\n* **Possible world** - definition\n* **Model** - aka possible world, math abstraction, each w/ fixed truth value for every relevant sentence\n* **Satisfaction** - alpha satisfies m same m satisfies alpha same m is a model of alpha\n* **Entailment** - sentences flowing logically from one another (vertical bar equals sign)\n* **Logical inference** - derive conclusions\n* **Model checking** - enumerates all model possibilities to check $M(KB) \\subseteq M(\u0007lpha)$, works if finite model space\n* **Sound** - derives only entailed sentences\n* **Truth-preserving** - same as sound\n* **Completeness** - derives all sound sentences\n* **Grounding** - connects logical reasoning processes and real envrionment in which the agent exists, simplest: agent's sensors\n* **Learning** - sentence construction process that produces general rules\n* **Propositional logic** - definition\n* **Atomic sentences** - single prop symbol\n* **Proposition symbol** - stands for prop that's true or false\n* **Complex sentences** - simpler sentences connected by parathesees/logical connectives\n* **Logical connectives** - definition\n* **Negation** - definition\n* **Literal** - atomic sentence or negated atomic sentence (pos/neg)\n* **Conjunction** - parts are conjucts\n* **Disjunction** - parts are disjuncts\n* **Implication** - premise/antecedent implies conclusion/consequent, rules, if-then statements\n* **Premise** - definition\n* **Conclusion** - definition\n* **Rules** - definition\n* **Biconditional** - definition\n* **Truth value** - true/false assigned to every propositional symbol\n* **Truth table** - specify truth value of complex sentence for all possible component assignments\n* **Theorem proving** - definition\n* **Logical equivalence** - definition\n* **Validity** - definition\n* **Tautology** - definition\n* **Deduction theorem** - definition\n* **Satisfiability** - definition\n* **Sat** - definition\n* **Reductio ad absurdum** - definition\n* **Refutation** - definition\n* **Contradiction** - definition\n* **Inference rules** - definition\n* **Proof** - definition\n* **Modus pomens** - definition\n* **And-elimination** - definition\n* **Monotonicity** - definition\n* **Resolvent** - definition\n* **Unit resolution** - definition\n* **Complementary literals** - definition\n* **Clause** - definition\n* **Unit clause** - definition\n* **Resolution** - definition\n* **Factoring** - definition\n* **Conjunctive normal form / cnf** - definition\n* **Resolution closure** - definition\n* **Ground resolution theorem** - definition\n* **Definite clause** - definition\n* **Horn clause** - definition\n* **Goal clauses** - definition\n* **Body** - definition\n* **Head** - definition\n* **Fact** - definition\n* **Forward-chaining** - definition\n* **Backward-chaining** - definition\n* **Data-driven** - definition\n* **Goal-directed reasoning** - 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": "95afe992-1795-46f1-db74-b965c1c278b7"
      },
      "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": 89,
      "outputs": [
        {
          "output_type": "display_data",
          "data": {
            "text/markdown": "# Module 1: Rational Agents and Task Environments\n## AIMA Chapter 1.1 What is AI?\n Chapter 1.1 summary. \n\n## AIMA Chapter 27.1 The Limits of AI\n Your summary here \n\n## AIMA Chapter 27.1 Can Machines Really Think?\n Your summary here \n\n## AIMA 2.1 Agents and Environments\n Your summary here \n\n## AIMA 2.2 Good Behavior: The Concept of Rationality\n Your summary here \n\n## AIMA 2.3 The Nature of Environments\n Your summary here \n\n## AIMA 2.4 The Structure of Agents\n Your summary here \n\n## Module 1 Lecture Notes\n Your summary here \n\n## Module 1 Definitions\n* **Rationality** - doing the right thing\n* **Agent** - anything that can perceive and act in an environment\n* **Percept** - your definitions here\n* **Other concept** - your definitions here\n* **Etc.** - your definitions here\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 Your summary here \n\n## AIMA Chapter 3.2 Example Problems\n Your summary here \n\n## AIMA Chapter 3.3 Search Algorithms\n Your summary here \n\n## AIMA Chapter 3.4 Uninformed Search Strategies\n Your summary here \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 Your summary here \n\n## AIMA Chapter 3.6 Heuristic Functions\n Your summary here \n\n## Module 4 Lecture Notes\n Your summary here \n\n## Module 4 Definitions\n* **Concept** - definition\n\n\n# Module 5: Adversarial Search and Games\n## AIMA Chapter 5.1 Game Theory\n Your summary here \n\n## AIMA Chapter 5.2 Optimal Decisions in Games\n Your summary here \n\n## AIMA Chapter 5.3 Heuristic Alpha–Beta Tree Search\n Your summary here \n\n## AIMA Chapter 5.5 Stochastic Games\n Your summary here \n\n## AIMA Chapter 16.1 Combining Beliefs and Desires under Uncertainty\n Your summary here \n\n## AIMA Chapter 16.2 The Basis of Utility Theory\n Your summary here \n\n## AIMA Chapter 16.3 Utility Functions\n Your summary here \n\n## Module 5 Lecture Notes\n Your summary here \n\n## Module 5 Definitions\n* **Concept** - definition\n\n\n# Module 6: Constraint Satisfaction Problems\n## AIMA Chapter 6.1 Defining Constraint Satisfaction Problems\n \nCsp has (1) set of variables (2) set of domains, 1 for each variable w/ allowable values for that variable (3) set of constraints specifying allowable combos of vals.\nSolving is NP-complete in general (though important subclasses can be solved efficiently)\nWhy formulate problems as CSPs? (1) easy, natural representation (2) lots of work into making solves fast/efficient (3) solve can quickly prune large parts of the search space (vs atomic state-space searcher - can only ask if specific state is goal).\nEx. coloring Australian states, job-shop scheduling (precedence/disjunctive constraints).\nCan transform every finite-domain constraint to a set of binary constraint if enough auxiliary variables are introduced, makes algorithm design easier.\nCan use dual graph transformation n-ary --> binary csp, though may prefer global constraint b/c (1) easier/less error-prone to write problem description (2) can design more efficient special-purpose interface algorithms.\n \n\n## AIMA Chapter 6.2 Constraint Propagation: Inference in CSPs\n \nCSP algorithm can generate successors by choosing new variable assignment or constraint propogation. Idea of constraint propogation is that it will leave fewer choices to consider when making next choice of a variable assignment; \ncan be intertwined w/ search or as preprocessing step; can sometimes solve the whole problem. Key idea is that enforcing local consistency in each part of the graph causes inconsistent values to be eliminated throughout the graph.\n$X_i$ arc-consistent wrt $X_j$ if for all values in $D_i$, there's some value in $D_j$ that safisfies binary constraint $(X_i, X_j)$. \nAC-3 is most popular algorithm for enforcing arc consistency; maintains queue of arcs to consider (initially all arcs, w/ each binary constraint = two arcs); pops off arbitrary arc $(X_i, X_j)$ from queue and makes $X_i$ arc-consistent wrt $X_j$. \nAC-3 complexity: n variables, each with domain size at most d, w/ c binary constraints. Each edge ($X_k, X_i)$ can be inserted into queue at most $d$ times b/c $X_i$ has at most $d$ values to delete. Checking consistency of arc is $O(d^2)$ time.\nTotal: $O(cd^3)$ time. Path consistency tightenes binary constraints using implicit constraints inferred by triplets; refers to overall consistency of the path from $X_i$ to $X_m$ to $X_j$.\n1-consisstency = node consistency; 2-consistency = arc consistncy; 3-consistency = path consistency. If graph is k-consistent, can solve in $O(n^2d)$ time b/c for each variable $X_i$, only need to search through $d$ values in domain to find value consistent w/ $X_1, .., X_{i-1}$.\nEstablishing n-consistency is NP-complete, requiring exponential space and time. For global constraints, can detect inconsistency if $m$ variables involed in constraint w/ n possible distinct values altogether, and $m>n$ --> unsatsifiable constraint; \nthen algorithm: (1) remove any variable in constraint w/ single value in domain (2) delete that variable's value form domains of remaining variables (3) repeat as long as singleton variables; if ever empty domain or # variables > # domain values left, then detected inconsistency.\nResource constraints: can detect inconsistency checking sum of min values of current domains; can enforce consistency by deleting max value of any domain not consistent w/ min values of the other domains.\nPower of CSP formalism is that for each new problem area, we only need to define the problem in terms of constraints and then general constraint-solving mechanisms can take over.\n \n\n## AIMA Chapter 6.3 Backtracking Search for CSPs\n \nStandard depth-limited search for csp w/ n vars of domain size $d$=$n!d^n$ leaves, but only $d^n$ possible complete assignments (branching factor would be $nd$, $(n-1)d$, .... for $n$ levels).\nBc of commutativity, only need consider 1 var at each node in search tree --> $d^n$ leaves. Backtracking search only keeps 1 representation of a state/assignment & alters instead creating new ones.\nBacktracking search improved w/ domain-independent heruistics (vs domain-specific heruistics w/ uninformed search), taking advantage of factored representation.\n(1) Which var assigned next? Order should its values be tried?\nSimple strategies: static or random ordering.\nMinimum-remaining-values (MRV) heuristic can prune pointless searches by detecting failure early; usually better than random/static ordering.\nWhen every region has same # legal values, degree heuristic attempts to reduce branching factor. MRV usually more powerful, but degree good as tie-breaker.\nWhich order to examine values: least-constraining-value heruistic - tries to leave the maximum flexibility for subsequent var assignments.\nVar selection fail-1st, but value selection fail-last b/c every var needs assignment eventually, so failing first --> less assignments to backtrack over; \nlook for most likely value first (if wanted all solutions instead of just 1, value ordering then irrelevant).\n(2)What inferences should be performed at each step in the search?\nPowerful during search; everytime make value choice for var, opportunity to infer new domain reductions on neighbors.\nForward checking: for each unassigned neighbor, delete any values inconsistent w/ chosen value; can eliminate branching by propogating info/detect inconsistent partial assignments so can backtrack immediately.\nBut doesn't look ahead far enough\nCombo MRV + forward checking together very effective.\nMAC: after var $X_i$ assigned a value, INFERENCE procedure calls AC-3, but instead of queue of all arcs in CSP, start with arcs $(X_i, X_i)$ for all $X_j$ that are unassigned variables that are neighbors of $X_i$.\nThen AC-3 constraint propogates; if any var's domain becomes empty, call to AC-3 fails & know to backtrack immediately. \nMAC strictly more powerful than forward checking (which does same thing on initial arcs but doesn't recursively propogate constraints when var's domain changes).\n(3) BACKTRACK >1 step when appropriate?\nApproach: backtrack to var that might fix problem; Keep track of conflict set. Can use bacakjumping. Every branch pruned by backjumping also pruned by forward checking.\nConflict-directed backjumping approach: $X_j$ current var, $conf(X_j)$ its conflict set; if every possible value for $X_j$ fails, backjump to most recent variable $X_i$ in $conf(X_j)$ and recompute $conf(X_i)$ <-- $conf(X_i) \\cup conf(X_j) - \\{X_i\\}$\n(4) Save/reuse partial results from the search?\nAvoid same probs w/ constraint learning; record no-goods by adding new constraint or keeping cache\n \n\n## AIMA Chapter 6.4 Local Search for CSPs\n \nLocal search algs use complete-state formulation where each state assigned a val to every var & the search changes the val of 1 var at a time (randomly cosen conflicted var) to val that brings us close to solution (min-conflict heuristic).\nMin-conflicts very effective. Landscape of a CSP under the min-conflicts heuristic usually has a series of plateaus (many assignments only 1 conflict away from a solution).\nPlateau search (allowing sideways moves to another state w/ same score) can help local search off plateau (tabu search).\nConstraint weighting: each constraints given numeric weight, initally 1. each step, alg chooses variable/value pair to change resulting in lowest total weight of all violated constraints; weights adjusted by incrementing weight of each constraint violated by the current assignment.\n2 benefits: (1) adds topography to plateaus, making sure it's possible to improve from current state (2) adds learning, over time difficult constraints assigned higher weights.\nLocal search can be used in online setting where problem changes.\n \n\n## AIMA Chapter 6.5 The Structure of Problems\n \nIndependence can be found by finding connected components of the constraint graph; each component corresponds to a subproblem CSP. \nIf n/c subproblems, ecah takes at most $d^c$ work to solve, total work $O(d^c n/c)$, linear in $n$ (compared to $O(d^n)$).\nAny tree-structured CSP can be solved in time linear in the number of variables; key is directional arc consistency, topo sort in $O(nd^2)$ time; $O(n)$ steps, each comparing up to $d$ possible domain values for 2 variables, don't need to backtrack.\nCutset conditioning: reduce constraint graph to tree by assigning values to some variables so the remaining variables form a tree. For general case, val chosen could be wrong, so need to try each possible val.\nGeneral alg:\n(1) chose cycel cutset\n(2) For each possible assignment to the variables in $S$ that satisfies all constraints on $S$ (a) remove from domains of remaining vars any vals that are inconsistent w/ assignment $S$ (b) if remaining CSP has solution, return it together w/ the assignment for $S$\nIf cutset has size $c$, then total runtime $O(d^c \\cdot (n-c)d^2)$; have to try each of $d^c$ combos of vals for vars in $S$ and for each combo, must solve tree problem of size $n-c$.\nIf graph is \"nearly a tree\", then $c$ will be small abd savings over backtracking are huge, but worst case $c=n-2$. Finding smallest cycle cutset is NP-hard, but several efficient approximation algs.\nTree decomposition requirements:\n(1) every var in original problem appears in at least 1 of the tree nodes\n(2) if 2 vars connected by a constraint in original problem, they must appear together (along w/ constraint) in at least one of the tree nodes\n(3) if var appears in 2 nodes in the tree, must appear in every node along the path connecting those nodes\n1st 2 ensure all variables/constraints represented; 3rd so any variable from original problem must have same value wherever it appears\nOnce have tree-structured graph, can get solution in $O(nd^2)$ time, $d$ is size of largest domain, but in tree, domain is set of tuples of values, not individual values.\nA graph admits many tree decomps, chose one to make the subproblems as small as possible. If graph has width $w$ then can be solved $O(nd^{w+1})$.\nSo CSP's w/ cnstraint graphs of bounded tree width are solvable in polytime, though finding decomp w/ width is NP-hard (but heuristic methods).\nCutset vs Tree decomp: whenever cycle-cutset of size $c$, also tree width of size $w < c + 1$ and can be far smaller.\n(1) Time: $O(d^c \\cdot (n-c)d^2)$ vs $O(nd^{w+1})$; favors tree\n(2) Space: cycle-cutset linear memory, while tree exponential in $w$\nValue symmetry - introduce symmetry-breaking constraint; can impose arbitrary order for coloring. NP-hard in general to elimate all symmetry, but breaking value symmetry proven important/effective on wide range of problems\n\n \n\n## Module 6 Lecture Notes\n Your summary here \n\n## Module 6 Definitions\n* **Csp (constraint satisfaction problem)** - set of variables, each with a value (solved when value satisfies all constraints on the vairable\n* **Assignment** - e.g. $\\{ X_i = v_i, X_j = v_j, ...\\}$\n* **Consistent/legal assignment** - assignment of values to variables that doesn't violate any constraints\n* **Complete assignment** - every variable is assigned a value\n* **Solution (to csp)** - consistent, complete assignemtn\n* **Partial assignment** - leaves some unassigned variables\n* **Partial solution** - consistent, partial assignment\n* **Constraint graph** - nodes = variables, edges = b/t any 2 variables participating in a constraint\n* **Precedence constraints** - task1 $T_1$ taking duration $d_1$ has to happen before task2 $T_2$ --> constraint $T_1 + d_1 \\leq T_2$\n* **Disjunctive constraint** - two tasks can't overlap in time $T_1 + $d_1$ \\leq T_2$ or $T_2 + d_2 \\leq T_1$\n* **Discrete domain** - domain w/ discrete values\n* **Finite domain** - domain w/ finite number of values\n* **Infinite** - domain w/ infinite number of values (e.g set of integers/strings), use implicit constraints ($T_1 + d_1 \\leq T_2$)\n* **Linear constraints** - constraints where each variable only appears in linear form (e.g. $T_1 + d_1 \\leq T_2$)\n* **Nonlinear constraints** - opposite of linear, no algorithm exists for solving on integer variables, undecidable problem\n* **Continuous domains** - common in real world, widely studied in operations research\n* **Linear programming problems** - constraints must be linear equalities/inequalities (best-known category of continuous-domain CSPs) can be solved in poly-time\n* **Urnary constraint** - restrict value of 1 varable\n* **Binary constraint** - relates 2 variables\n* **Binary csp** - only urnary and binary constraints, can be represented as consistent graph\n* **Global constraint** - involves arbitrary number of variables (not necessarily all) (e.g. Alldi ff - all involves variables must have different values)\n* **Cryptarithmetic** - each letter represents different digit (e.g. TWO + TWO = FOUR, Alldi ff and n-ary constraints)\n* **Constraint hypergraph** - ordinary nodes and hypernodes (represent n-ary constraints)\n* **Dual graph** - new graph w/ 1 variable/constraint in original, 1 binary constraint for each pair of constraints sharing variables\n* **Preference constraints** - indicate which solutions are preferred (vs absolute constraints - violation rules out potential solution)\n* **Constrained optimization problem** - problems solved with optimization search methods, preference constraints can be encoded as costs on individual variable assignments\n* **Constraint propogation** - using constraints to reduce # legal values for variable, which in turn reduces for another etc\n* **Local consistency** - treat variables as nodes, binary constraints as edges\n* **Node consistency** - (for single variable/node) all values in domain satisfy its urnary constraints; (for graph) every variable is node-consistent\n* **Arc consistency** - (variable) every value in domain satisfies its binary constraints; (graph) every variable is arc-consistent\n* **Path consistency** - $\\{X_i,X_j\\}$ wrt $X_m$: for every $\\{X_i=a,X_j=b\\}$ consistent w/ contraints on $\\{X_i,X_j \\}$, there's $X_m$ assignment satisfying $\\{X_i,X_m\\}$ and $\\{X_i,X_j\\}$ constraints\n* **K-consistency** - for any consistent assignmenet to any set of $k-1$ variables, any kth value can always be assigned a consistent value\n* **Strongly k-consistent** - k-consistent, (k-1) consistent, ..., 1-consistent\n* **Resource constraint** - aka Atmost constraint; e.g. scheduling, at most 10 personnel assigned total to tasks\n* **Bounds propagation** - for large resource-limited problems w/ integer values (e.g. ariline scheduling - plane capacities)\n* **Bounds-consistent** - for every variable $X$ and its lower/upper bound values, $\\exist$ value of $Y$ satisfying constraint b/t $X$/$Y$ for every $Y$\n* **Sudoku** - 27 different Alldi ff constraints (1 per row/col/box)\n* **(sudoku) unit** - a row, column, or box\n* **Commutativity** - if the order of application of any given set of actions doesn't matter\n* **Minimum-remaining-values** - heuristic for which variables to choose next, aka most constraint variable or fail first\n* **Degree heuristic** - heuristic selecting variable involved in largest number of constraints on other unassigned variables\n* **Least-constrainting value** - heuristic preferring value that rules out fewest choices for neighboring variables in constraint graph\n* **Forward checking** - form of inference, whenever variable $X$ assigned, establishes arc consistency for it\n* **Maintaining arc consistency** - MAC algorithm; can detect inconsistencies missed by foward checking\n* **Chronological backtracking** - when branch of search fails, back up to preceding variable and try different value; most recent decision point revisited\n* **Conflict set** - set of assignments in conflict with some value for a variable, supplied by forward checking (elements deleted should be added)\n* **Backjumping** - mothod that backtracks to most recent assignment in conflict set\n* **Conflict-directed backjumping** - conflict set is of preceding variables that caused X together w/ any subsequent variables to have no consistent solution\n* **Constraint learning** - idea of finding a min set of variables from conflict set that causes the problem\n* **No-good** - set of variables in constraint learning w/ their corresponding values; can be effectively used by forward checking or backjumping\n* **Min-conflicts** - value selection that results in the min number of conflicts w/ other variables\n* **Tabu search** - keeping small list of recently visited states and forbidding algorithm to return to those states; directs plateau wandering\n* **Constraint weighting** - aims to concentrate search on the important constraints\n* **Independent subproblems** - if assignment $S_i$ solves $CSP_i$, then union of all $S_i$ solves of union of all $CSP_i$; rare\n* **Connected component** - \n* **Directional arc consistency (dac)** - consistent under ordering $X_1,X_2,...,X_n$ iff every $X_i$ is arc-consistent with each $X_j$ for $j>i$\n* **Topological sort** - ordering of variables in rooted tree s.t. each variable appears after its parent in the tree\n* **Cycle cutset** - choosing subset $S$ of CSP's variables s.t. the constraint graph becomes a tree after removal\n* **Cutset conditioning** - algorithmic approach (described in summary)\n* **Tree decomposition** - transformation of original graph into a tree where each node consists of set of variables satisfying 3 requirements\n* **Tree width** - of tree decomposition is (size of largest node - 1); of graph is min width among its decomps\n* **Value symmetry** - consistent solutions that are permutations of themselves (e.g. coloring)\n* **Symmetry-breaking constraint** - to reduce search space of factor $d!$ by breaking symmetry in assignments\n\n\n# Module 7: Logical Agents\n## AIMA Chapter 7.1 Knowledge-Based Agents\n \nTELL: add new sentences to KB; ASK: query what is known. Inference must obey requirement that when one ASKS question of KB, answer should follow from what has been TELLed previously.\nAKA inference shouldn't make up things as it goes along. Like other agents, KB-agent takes precept and returns an action.\nEach time agent program called: \n(1) TELLS KB what it perceives \n(2) ASKS KB what action it should perform; extensive reasoning may be done about current state of world/outcomes of possible action sequences etc \n(3) TELLS KB what action was chosen and returns action so it can be executed\nMAKE-PRECEPT-SENTENCE construct a sentence asserting that the agent perceived the given precept at the given time.\nMAKE-ACTION-QUERY constructs a sentence that asks what action should be done at the current time.\nMAKE-ACTION-SENTENCE constructs a sentence asserting that the chosen action was executed.\nKB-agent amendable to a description at knowledge level; only need specify what agent knows/its gals to determine KB-agent's behavior\nSuccessful agent often combines declarative + procedural elements in its design & that declarative knowledge can often be compiled into more efficeint procedural code.\nCan provide mechanisms that allow to learn for itself, creating general knowledge about envrionment from series of precepts; learning agent can be fully autonomous.\n \n\n## AIMA Chapter 7.2 The Wumpus World\n \nDef of task envrionment:\n(1) performance measure: +1000 for climbing out w/ gold, -1000 falling into pit/eaten by wampu, -1/action taken, -10 using arrow; ends when agent dies/climbs out\n(2) envrionment: 4x4 grid of rooms, walls surroudnign grid, starts $\\[1, 1\\]$, gold/wampus locations chosen uniformly at random; pit w/p .2\n(3) actualtor: agent can move Forward, Turn Left/Right; dies if enters square w/ pit/live wumpus; bumps wall then doesn't move, grab can pick up gold, shoot to fire arrow (until hit wumpus/wall), climb out of cave only from [1,1]\n(4) sensors: [stench, breeze, glitter, bump, scream (wumpus killed)]\nWumpus envrionment: deterministic, discrete, static, single-agent (wampus doesn't move). Sequential: rewards only after many actions taken. Partially observable: some aspects of state not directly perceivable\nMain challenge is overcoming initial ignorance, requires logical reasoning. \nIn each case for which agent draws a conclusion from available info, conclusion guaranteed to be correct if available info is correct = fundamental property of logical reasoning\n \n\n## AIMA Chapter 7.3 Logic\n \n$M(\u0007lpha)$ is set of all models of $\u0007lpha$.\nEntailment formal def: if alpha emtails beta iff $M(\u0007lpha) \\subseteq M(\\Beta)$.\nKB like set of sentences, false if contradicts agent knowledge. Entailment can be applied to carry out logical inference.\n$KB \u000bdash _i \\lpha$ alpha is derived from KB by i, i derives alpha from KB.\nIf KB is true in the real world, then any sentence alpha derives form KB by a sound inference procedure is also true in the real world.\ngrounding: meaning/truth of precept sentences defined by processes of sensing and sentence construction that produce them \n \n\n## AIMA Chapter 7.4 Propositional Logic: A Very Simple Logic\n \noperator precedent: not, and, or, implies, biconditional.\n\n\n\n## AIMA 7.5 Propositional Theorem Proving\n Your summary here \n\n## Module 7 Lecture Notes\n Your summary here \n\n## Module 7 Definitions\n* **Knowledge-based agents** - decides what actions to take using reasoning over internal representation of knowledge\n* **Reasoning** - definition\n* **Representation** - definition\n* **Knowledge base** - KB, central component of a knowledge-based agent\n* **Sentence** - make up knowledge base, expressed in a knowledge representation language and represents some about the world\n* **Knowledge representation language** - definition\n* **Axiom** - when sentence taken as given, not derived from other sentences\n* **Inference** - deriving new sentences from old\n* **Background knowledge** - initial info in knowledge base\n* **Knowledge level** - info about actions b/c it knows that it will achieve its goal (independent from implementation)\n* **Implementation level** - e.g. how a taxei works (geographical knowledge implemented as linked lists, pixel maps etc\n* **Declarative** - approach where TELL sentences 1 by 1 until agent knows how to operate in its envrionment\n* **Procedural** - approach encodes desired behaviors directly as program code\n* **Wumpus world** - cave of rooms connected by passageways; wumpus (beast), agent (w/ 1 arrow), bottomless pits, gold\n* **Syntax** - specifies well formed sentences of the representation language\n* **Semantics** - meaning of sentences, defines truth wrt each possible world\n* **Truth** - only true/false\n* **Possible world** - definition\n* **Model** - aka possible world, math abstraction, each w/ fixed truth value for every relevant sentence\n* **Satisfaction** - alpha satisfies m same m satisfies alpha same m is a model of alpha\n* **Entailment** - sentences flowing logically from one another (vertical bar equals sign)\n* **Logical inference** - derive conclusions\n* **Model checking** - enumerates all model possibilities to check $M(KB) \\subseteq M(\u0007lpha)$, works if finite model space\n* **Sound** - derives only entailed sentences\n* **Truth-preserving** - same as sound\n* **Completeness** - derives all sound sentences\n* **Grounding** - connects logical reasoning processes and real envrionment in which the agent exists, simplest: agent's sensors\n* **Learning** - sentence construction process that produces general rules\n* **Propositional logic** - definition\n* **Atomic sentences** - single prop symbol\n* **Proposition symbol** - stands for prop that's true or false\n* **Complex sentences** - simpler sentences connected by parathesees/logical connectives\n* **Logical connectives** - definition\n* **Negation** - definition\n* **Literal** - atomic sentence or negated atomic sentence (pos/neg)\n* **Conjunction** - parts are conjucts\n* **Disjunction** - parts are disjuncts\n* **Implication** - premise/antecedent implies conclusion/consequent, rules, if-then statements\n* **Premise** - definition\n* **Conclusion** - definition\n* **Rules** - definition\n* **Biconditional** - definition\n* **Truth value** - true/false assigned to every propositional symbol\n* **Truth table** - specify truth value of complex sentence for all possible component assignments\n* **Theorem proving** - definition\n* **Logical equivalence** - definition\n* **Validity** - definition\n* **Tautology** - definition\n* **Deduction theorem** - definition\n* **Satisfiability** - definition\n* **Sat** - definition\n* **Reductio ad absurdum** - definition\n* **Refutation** - definition\n* **Contradiction** - definition\n* **Inference rules** - definition\n* **Proof** - definition\n* **Modus pomens** - definition\n* **And-elimination** - definition\n* **Monotonicity** - definition\n* **Resolvent** - definition\n* **Unit resolution** - definition\n* **Complementary literals** - definition\n* **Clause** - definition\n* **Unit clause** - definition\n* **Resolution** - definition\n* **Factoring** - definition\n* **Conjunctive normal form / cnf** - definition\n* **Resolution closure** - definition\n* **Ground resolution theorem** - definition\n* **Definite clause** - definition\n* **Horn clause** - definition\n* **Goal clauses** - definition\n* **Body** - definition\n* **Head** - definition\n* **Fact** - definition\n* **Forward-chaining** - definition\n* **Backward-chaining** - definition\n* **Data-driven** - definition\n* **Goal-directed reasoning** - definition\n",
            "text/plain": [
              "<IPython.core.display.Markdown object>"
            ]
          },
          "metadata": {}
        }
      ]
    }
  ]
}