<|start_filename|>_site/nlp-english-exercises/index.html<|end_filename|>
<!DOCTYPE html>
<html lang="en-us">
  <head>
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
  <title>
    
      Natural Language For Communication &middot; AIMA Exercises 
    
  </title>
  <!-- CSS -->
  <link rel="stylesheet" href="/aima-exercises/public/css/poole.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/syntax.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/lanyon.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/style.css">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">
  <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="<KEY>" crossorigin="anonymous">

      <!-- Bootstrap CSS -->
      <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="<KEY>" crossorigin="anonymous">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/aima-exercises/public/apple-touch-icon-precomposed.png">
  <link rel="shortcut icon" href="/aima-exercises/public/aima_logo.ico">

  <!-- RSS -->
  <link rel="alternate" type="application/rss+xml" title="RSS" href="/atom.xml">
</head>

  <body>
    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="/aima-exercises/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="/aima-exercises/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="/aima-exercises/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="/aima-exercises/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="/aima-exercises/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="/aima-exercises/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="/aima-exercises/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="/aima-exercises/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="/aima-exercises/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="/aima-exercises/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="/aima-exercises/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="/aima-exercises/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="/aima-exercises/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="/aima-exercises/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v1.0.0</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; 2019. All rights reserved.
    </p>
  </div>
</div>

    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="/aima-exercises/" title="Home">Artificial Intelligence</a>
            <small>AIMA Exercises </small>
          </h3>
          <br>
          <center>
            <form class="form-inline active-pink-3 active-pink-4" action="/aima-exercises/search" id="site_search" autocomplete="off" method="GET">
              <i class="fas fa-search" aria-hidden="true"></i>
            <input class="form-control form-control-sm ml-3 w-75" type="text" placeholder="Search within AIMA Exercises" aria-label="Search" name="query">
            <input type="submit" value="Go!" class="search-btn">
            </form>
            <br>
            </center>
            



<ul class="breadcrumbb" id="bbreadcrumb">

  <label for="toggletoc" class="toc-icon">
    <span></span>
    <span></span>
    <span></span>
  </label>

   
   
    <li><a class="breadcrumb-text" href="/aima-exercises/"><i class="fa fa-home"></i></a>  </li>
   


</ul>

      </div>
    </div>
      <div class="container content">
        <article class="post">

  <div class="entry">
    <script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    TeX: {
      equationNumbers: {
        autoNumber: "AMS"
      }
    },
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true,
    },
    "HTML-CSS": { 
      preferredFont: "TeX", 
      availableFonts: ["STIX","TeX"], 
      styles: {".MathJax": {}} 
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<h1 id="23-natural-language-for-communication">23. Natural Language for Communication</h1>

<div class="card">
<div class="card-header p-2">
<a href="ex_1/" class="p-2">Exercise 1 (washing-clothes-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex1');" href="#"><i id="ch23ex1" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.1);" href="#"><i id="ch23ex1" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Read the following text once for
understanding, and remember as much of it as you can. There will be a
test later.<br />

&gt; The procedure is actually quite simple. First you arrange things into
different groups. Of course, one pile may be sufficient depending on how
much there is to do. If you have to go somewhere else due to lack of
facilities that is the next step, otherwise you are pretty well set. It
is important not to overdo things. That is, it is better to do too few
things at once than too many. In the short run this may not seem
important but complications can easily arise. A mistake is expensive as
well. At first the whole procedure will seem complicated. Soon, however,
it will become just another facet of life. It is difficult to foresee
any end to the necessity for this task in the immediate future, but then
one can never tell. After the procedure is completed one arranges the
material into different groups again. Then they can be put into their
appropriate places. Eventually they will be used once more and the whole
cycle will have to be repeated. However, this is part of life.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_2/" class="p-2">Exercise 2 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex2');" href="#"><i id="ch23ex2" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.2);" href="#"><i id="ch23ex2" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

An <i>HMM grammar</i> is essentially a standard HMM whose state
variable is $N$ (nonterminal, with values such as $Det$, $Adjective$,
$Noun$ and so on) and whose evidence variable is $W$ (word, with values
such as $is$, $duck$, and so on). The HMM model includes a prior
${\textbf{P}}(N_0)$, a transition model
${\textbf{P}}(N_{t+1}|N_t)$, and a sensor model
${\textbf{P}}(W_t|N_t)$. Show that every HMM grammar can be
written as a PCFG. [Hint: start by thinking about how the HMM prior can
be represented by PCFG rules for the sentence symbol. You may find it
helpful to illustrate for the particular HMM with values $A$, $B$ for
$N$ and values $x$, $y$ for $W$.]
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_3/" class="p-2">Exercise 3 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex3');" href="#"><i id="ch23ex3" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.3);" href="#"><i id="ch23ex3" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following PCFG for simple verb phrases:<br />

&gt; 0.1: VP $\rightarrow$ Verb<br />

&gt; 0.2: VP $\rightarrow$ Copula Adjective<br />

&gt; 0.5: VP $\rightarrow$ Verb the Noun<br />

&gt; 0.2: VP $\rightarrow$ VP Adverb<br />

&gt; 0.5: Verb $\rightarrow$ is<br />

&gt; 0.5: Verb $\rightarrow$ shoots<br />

&gt; 0.8: Copula $\rightarrow$ is<br />

&gt; 0.2: Copula $\rightarrow$ seems<br />

&gt; 0.5: Adjective $\rightarrow$ <b>unwell</b><br />

&gt; 0.5: Adjective $\rightarrow$ <b>well</b><br />

&gt; 0.5: Adverb $\rightarrow$ <b>well</b><br />

&gt; 0.5: Adverb $\rightarrow$ <b>badly</b><br />

&gt; 0.6: Noun $\rightarrow$ <b>duck</b><br />

&gt; 0.4: Noun $\rightarrow$ <b>well</b><br />

1.  Which of the following have a nonzero probability as a VP? (i)
    shoots the duck well well well(ii) seems the well well(iii) shoots
    the unwell well badly<br />

2.  What is the probability of generating “is well well”?<br />

3.  What types of ambiguity are exhibited by the phrase in (b)?<br />

4.  Given any PCFG, is it possible to calculate the probability that the
    PCFG generates a string of exactly 10 words?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_4/" class="p-2">Exercise 4 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex4');" href="#"><i id="ch23ex4" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.4);" href="#"><i id="ch23ex4" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following simple PCFG for noun phrases:<br />

&gt; 0.6: NP $\rightarrow$ Det\ AdjString\ Noun<br />

&gt; 0.4: NP $\rightarrow$ Det\ NounNounCompound<br />

&gt; 0.5: AdjString $\rightarrow$ Adj\ AdjString<br />

&gt; 0.5: AdjString $\rightarrow$ $\Lambda$<br />

&gt; 1.0: NounNounCompound $\rightarrow$ Noun<br />

&gt; 0.8: Det $\rightarrow$ <b>the</b><br />

&gt; 0.2: Det $\rightarrow$ <b>a</b><br />

&gt; 0.5: Adj $\rightarrow$ <b>small</b><br />

&gt; 0.5: Adj $\rightarrow$ <b>green</b><br />

&gt; 0.6: Noun $\rightarrow$ <b>village</b><br />

&gt; 0.4: Noun $\rightarrow$ <b>green</b><br />

where $\Lambda$ denotes the empty string.<br />

1.  What is the longest NP that can be generated by this grammar? (i)
    three words(ii) four words(iii) infinitely many words<br />

2.  Which of the following have a nonzero probability of being generated
    as complete NPs? (i) a small green village(ii) a green
    green green(iii) a small village green<br />

3.  What is the probability of generating “the green green”?<br />

4.  What types of ambiguity are exhibited by the phrase in (c)?<br />

5.  Given any PCFG and any finite word sequence, is it possible to
    calculate the probability that the sequence was generated by the
    PCFG?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_5/" class="p-2">Exercise 5 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex5');" href="#"><i id="ch23ex5" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.5);" href="#"><i id="ch23ex5" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Outline the major differences between Java (or any other computer
language with which you are familiar) and English, commenting on the
“understanding” problem in each case. Think about such things as
grammar, syntax, semantics, pragmatics, compositionality,
context-dependence, lexical ambiguity, syntactic ambiguity, reference
finding (including pronouns), background knowledge, and what it means to
“understand” in the first place.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_6/" class="p-2">Exercise 6 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex6');" href="#"><i id="ch23ex6" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.6);" href="#"><i id="ch23ex6" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

This exercise concerns grammars for very simple languages.<br />

1.  Write a context-free grammar for the language $a^n b^n$.<br />

2.  Write a context-free grammar for the palindrome language: the set of
    all strings whose second half is the reverse of the first half.<br />

3.  Write a context-sensitive grammar for the duplicate language: the
    set of all strings whose second half is the same as the first half.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_7/" class="p-2">Exercise 7 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex7');" href="#"><i id="ch23ex7" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.7);" href="#"><i id="ch23ex7" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the sentence “Someone walked slowly to the supermarket” and a
lexicon consisting of the following words:<br />

$Pronoun \rightarrow \textbf{someone} \quad Verb \rightarrow \textbf{walked}$<br />

$Adv \rightarrow \textbf{slowly} \quad Prep \rightarrow \textbf{to}$<br />

$Article \rightarrow \textbf{the} \quad Noun \rightarrow \textbf{supermarket}$<br />

Which of the following three grammars, combined with the lexicon,
generates the given sentence? Show the corresponding parse tree(s).<br />

$$
\quad\quad\quad\quad (A):\quad\quad\quad\quad  \quad\quad\quad\quad(B):\quad\quad\quad\quad  \quad\quad\quad\quad(C):\\
\quad\quad\quad\quad S \rightarrow NP \space VP \quad\quad\quad\quad \quad\quad\quad\quad S\rightarrow NP\space VP \quad\quad\quad\quad S\rightarrow NP\space VP\\
\quad\quad\quad\quad NP\rightarrow Pronoun \quad\quad\quad\quad  NP\rightarrow Pronoun \quad\quad\quad\quad  NP\rightarrow Pronoun\\
\quad\quad\quad\quad NP\rightarrow Article\space Noun \quad\quad\quad\quad  NP\rightarrow Noun \quad\quad\quad\quad  NP\rightarrow Article\space NP\\
\quad\quad\quad\quad VP\rightarrow VP\space PP \quad\quad\quad\quad NP\rightarrow Article\space NP \quad\quad\quad\quad  VP\rightarrow Verb\space Adv\\
\quad\quad\quad\quad  VP\rightarrow VP\space Adv\space Adv \quad\quad\quad\quad  VP\rightarrow Verb\space Vmod \quad\quad\quad\quad  Adv\rightarrow Adv\space Adv\\
\quad\quad\quad\quad  VP\rightarrow Verb \quad\quad\quad\quad  Vmod\rightarrow Adv\space Vmod \quad\quad\quad\quad   Adv\rightarrow PP\\
\quad\quad\quad\quad PP\rightarrow Prep\space NP \quad\quad\quad\quad Vmod\rightarrow Adv \quad\quad\quad\quad PP\rightarrow Prep\space NP\\
\quad\quad\quad\quad NP\rightarrow Noun \quad\quad\quad\quad Adv\rightarrow PP \quad\quad\quad\quad NP\rightarrow Noun\\
\quad\quad\quad\quad\quad \quad\quad\quad\quad PP\rightarrow Prep\space NP \quad\quad\quad\quad \quad\quad\quad\quad

$$

For each of the preceding three grammars, write down three sentences of
English and three sentences of non-English generated by the grammar.
Each sentence should be significantly different, should be at least six
words long, and should include some new lexical entries (which you
should define). Suggest ways to improve each grammar to avoid generating
the non-English sentences.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_8/" class="p-2">Exercise 8 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex8');" href="#"><i id="ch23ex8" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.8);" href="#"><i id="ch23ex8" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Collect some examples of time expressions, such as “two o’clock,”
“midnight,” and “12:46.” Also think up some examples that are
ungrammatical, such as “thirteen o’clock” or “half past two fifteen.”
Write a grammar for the time language.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_9/" class="p-2">Exercise 9 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex9');" href="#"><i id="ch23ex9" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.9);" href="#"><i id="ch23ex9" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Some linguists have argued as follows:<br />
<br />
 Children learning a language hear only <i>positive
 examples</i> of the language and no <i>negative
 examples</i>. Therefore, the hypothesis that “every possible
 sentence is in the language” is consistent with all the observed
 examples. Moreover, this is the simplest consistent hypothesis.
 Furthermore, all grammars for languages that are supersets of the true
 language are also consistent with the observed data. Yet children do
 induce (more or less) the right grammar. It follows that they begin
 with very strong innate grammatical constraints that rule out all of
 these more general hypotheses <i>a priori</i>.<br />

Comment on the weak point(s) in this argument from a statistical
learning viewpoint.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_10/" class="p-2">Exercise 10 (chomsky-form-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex10');" href="#"><i id="ch23ex10" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.10);" href="#"><i id="ch23ex10" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

In this exercise you will transform $\large \varepsilon_0$  into
Chomsky Normal Form (CNF). There are five steps: (a) Add a new start
symbol, (b) Eliminate $\epsilon$ rules, (c) Eliminate multiple words on
right-hand sides, (d) Eliminate rules of the form
(${\it X} \rightarrow$${\it Y}$),
(e) Convert long right-hand sides into binary rules.<br />

1.  The start symbol, $S$, can occur only on the left-hand side in CNF.
    Replace ${\it S}$ everywhere by a new symbol
    ${\it S'}$ and add a rule of the form
    ${\it S}$
    $\rightarrow$${\it S'}$.<br />

2.  The empty string, $\epsilon$ cannot appear on the right-hand side
    in CNF. $\large \varepsilon_0$ does not have any rules with $\epsilon$, so this is not
    an issue.<br />

3.  A word can appear on the right-hand side in a rule only of the form
    (${\it X}$
    $\rightarrow$<i>word</i>).
    Replace each rule of the form (${\it X}$
    $\rightarrow$…<i>word</i> …)
    with (${\it X}$
    $\rightarrow$…${\it W'}$ …)
    and (${\it W'}$
    $\rightarrow$<i>word</i>),
    using a new symbol ${\it W'}$.<br />

4.  A rule (${\it X}$
    $\rightarrow$${\it Y}$)
    is not allowed in CNF; it must be (${\it X}$
    $\rightarrow$${\it Y}$
    ${\it Z}$) or (${\it X}$
    $\rightarrow$<i>word</i>).
    Replace each rule of the form (${\it X}$
    $\rightarrow$${\it Y}$)
    with a set of rules of the form (${\it X}$
    $\rightarrow$…), one
    for each rule (${\it Y}$
    $\rightarrow$…),
    where (…) indicates one or more symbols.<br />

5.  Replace each rule of the form (${\it X}$
    $\rightarrow$${\it Y}$
    ${\it Z}$ …) with two rules, (${\it X}$
    $\rightarrow$${\it Y}$
    ${\it Z'}$) and (${\it Z'}$
    $\rightarrow$${\it Z}$
    …), where ${\it Z'}$ is a new symbol.<br />

Show each step of the process and the final set of rules.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_11/" class="p-2">Exercise 11 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex11');" href="#"><i id="ch23ex11" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.11);" href="#"><i id="ch23ex11" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following toy grammar:<br />

&gt; $S \rightarrow NP\space VP$<br />

&gt; $NP \rightarrow Noun$<br />

&gt; $NP \rightarrow NP\space and\space NP$<br />

&gt; $NP \rightarrow NP\space PP$<br />

&gt; $VP \rightarrow Verb$<br />

&gt; $VP \rightarrow VP\space and \space VP$<br />

&gt; $VP \rightarrow VP\space PP$<br />

&gt; $PP \rightarrow Prep\space NP$<br />

&gt; $Noun \rightarrow Sally\space; pools\space; streams\space; swims$<br />

&gt; $Prep \rightarrow in$<br />

&gt; $Verb \rightarrow pools\space; streams\space; swims$<br />

1.  Show all the parse trees in this grammar for the sentence “Sally
    swims in streams and pools.”<br />

2.  Show all the table entries that would be made by
    a (non-probabalistic) CYK parser on this sentence.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_12/" class="p-2">Exercise 12(exercise-subj-verb-agree) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex12');" href="#"><i id="ch23ex12" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.12);" href="#"><i id="ch23ex12" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Using DCG notation, write a grammar for a
language that is just like $\large \varepsilon_1$, except that it enforces agreement between
the subject and verb of a sentence and thus does not generate
ungrammatical sentences such as “I smells the wumpus.”
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_13/" class="p-2">Exercise 13 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex13');" href="#"><i id="ch23ex13" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.13);" href="#"><i id="ch23ex13" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following PCFG:<br />

&gt; $S \rightarrow NP \space VP[1.0] $<br />

&gt; $NP \rightarrow \textit{Noun}[0.6] \space|\space \textit{Pronoun}[0.4] $<br />

&gt; $VP \rightarrow \textit{Verb} \space NP[0.8] \space|\space \textit{Modal}\space \textit{Verb}[0.2]$<br />

&gt; $\textit{Noun} \rightarrow \textbf{can}[0.1] \space|\space \textbf{fish}[0.3] \space|\space ...$<br />

&gt; $\textit{Pronoun} \rightarrow \textbf{I}[0.4] \space|\space ...$<br />

&gt; $\textit{Verb} \rightarrow \textbf{can}[0.01] \space|\space \textbf{fish}[0.1] \space|\space ...$<br />

&gt; $\textit{Modal} \rightarrow \textbf{can}[0.3] \space|\space ...$<br />

The sentence “I can fish” has two parse trees with this grammar. Show
the two trees, their prior probabilities, and their conditional
probabilities, given the sentence.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_14/" class="p-2">Exercise 14 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex14');" href="#"><i id="ch23ex14" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.14);" href="#"><i id="ch23ex14" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

An augmented context-free grammar can represent languages that a regular
context-free grammar cannot. Show an augmented context-free grammar for
the language $a^nb^nc^n$. The allowable values for augmentation
variables are 1 and $SUCCESSOR(n)$, where $n$ is a value. The rule for a sentence
in this language is<br />
$$S(n) \rightarrow A(n) B(n) C(n) \ .$$
Show the rule(s) for each of ${\it A}$,
${\it B}$, and ${\it C}$.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_15/" class="p-2">Exercise 15 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex15');" href="#"><i id="ch23ex15" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.15);" href="#"><i id="ch23ex15" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Augment the $\large \varepsilon_1$ grammar so that it handles article–noun agreement. That is,
make sure that “agents” and “an agent” are ${\it NP}$s, but
“agent” and “an agents” are not.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_16/" class="p-2">Exercise 16 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex16');" href="#"><i id="ch23ex16" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.16);" href="#"><i id="ch23ex16" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the following sentence (from <i>The New York Times,</i>
July 28, 2008):<br />

&gt; Banks struggling to recover from multibillion-dollar loans on real
&gt; estate are curtailing loans to American businesses, depriving even
&gt; healthy companies of money for expansion and hiring.

1.  Which of the words in this sentence are lexically ambiguous?<br />

2.  Find two cases of syntactic ambiguity in this sentence (there are
    more than two.)<br />

3.  Give an instance of metaphor in this sentence.<br />

4.  Can you find semantic ambiguity?
<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_17/" class="p-2">Exercise 17 (washing-clothes2-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex17');" href="#"><i id="ch23ex17" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.17);" href="#"><i id="ch23ex17" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Without looking back at
Exercise <a class="exerciseRef" href="/aima-exercises/nlp-english-exercises/ex_1/">washing-clothes-exercise</a>, answer the following
questions:<br />

1.  What are the four steps that are mentioned?<br />

2.  What step is left out?<br />

3.  What is “the material” that is mentioned in the text?<br />

4.  What kind of mistake would be expensive?<br />

5.  Is it better to do too few things or too many? Why?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_18/" class="p-2">Exercise 18 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex18');" href="#"><i id="ch23ex18" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.18);" href="#"><i id="ch23ex18" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Select five sentences and submit them to an online translation service.
Translate them from English to another language and back to English.
Rate the resulting sentences for grammaticality and preservation of
meaning. Repeat the process; does the second round of iteration give
worse results or the same results? Does the choice of intermediate
language make a difference to the quality of the results? If you know a
foreign language, look at the translation of one paragraph into that
language. Count and describe the errors made, and conjecture why these
errors were made.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_19/" class="p-2">Exercise 19 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex19');" href="#"><i id="ch23ex19" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.19);" href="#"><i id="ch23ex19" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The $D_i$ values for the sentence in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/mt-alignment-figure.png">mt-alignment-figure</a> sum to 0. Will that be true
of every translation pair? Prove it or give a counterexample.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_20/" class="p-2">Exercise 20 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex20');" href="#"><i id="ch23ex20" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.20);" href="#"><i id="ch23ex20" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

(Adapted from [<a class="paperRef" title="" href="">Knight:1999</a>].) Our translation model assumes that, after the phrase
translation model selects phrases and the distortion model permutes
them, the language model can unscramble the permutation. This exercise
investigates how sensible that assumption is. Try to unscramble these
proposed lists of phrases into the correct order:<br />

1.  have, programming, a, seen, never, I, language, better<br />

2.  loves, john, mary<br />

3.  is the, communication, exchange of, intentional, information
    brought, by, about, the production, perception of, and signs, from,
    drawn, a, of, system, signs, conventional, shared<br />

4.  created, that, we hold these, to be, all men, truths, are, equal,
    self-evident<br />

Which ones could you do? What type of knowledge did you draw upon? Train
a bigram model from a training corpus, and use it to find the
highest-probability permutation of some sentences from a test corpus.
Report on the accuracy of this model.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_21/" class="p-2">Exercise 21 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex21');" href="#"><i id="ch23ex21" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.21);" href="#"><i id="ch23ex21" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Calculate the most probable path through the HMM in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/sr-hmm-figure.png">sr-hmm-figure</a> for the output sequence
$[C_1,C_2,C_3,C_4,C_4,C_6,C_7]$. Also give its probability.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_22/" class="p-2">Exercise 22 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch23ex22');" href="#"><i id="ch23ex22" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex23.22);" href="#"><i id="ch23ex22" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

We forgot to mention that the text in
Exercise <a class="exerciseRef" href="/aima-exercises/nlp-english-exercises/ex_1/">washing-clothes-exercise</a> is entitled “Washing
Clothes.” Reread the text and answer the questions in
Exercise <a class="exerciseRef" href="/aima-exercises/nlp-english-exercises/ex_17/">washing-clothes2-exercise</a>. Did you do better
this time? Bransford and Johnson [<a class="paperRef" title="" href="">Bransford+Johnson:1973</a>] used this
text in a controlled experiment and found that the title helped
significantly. What does this tell you about how language and memory
works?
</p>
</div>
</div>
<p><br /></p>

  </div>

<!--   <div class="date">
    Written on 
  </div>
 -->
  
</article>


      </div>
    <label for="sidebar-checkbox" class="sidebar-toggle"></label>
    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');
        document.addEventListener('click', function(e) {
          var target = e.target;
          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;
          checkbox.checked = false;
        }, false);
      })(document);
    </script>
        <script src="/aima-exercises/js/main.js"></script>
        <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
        <script src="/aima-exercises/js/answer.js"></script>
        <script src="/aima-exercises/js/commsol.js"></script>
        <script src="/aima-exercises/js/forms.js"></script>
        <script src="/aima-exercises/js/crossref.js"></script>
        <script src="/aima-exercises/js/bookmark.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
  </body>
</html>


<|start_filename|>_site/bayes-nets-exercises/index.html<|end_filename|>
<!DOCTYPE html>
<html lang="en-us">
  <head>
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
  <title>
    
      Probabilistic Reasoning &middot; AIMA Exercises 
    
  </title>
  <!-- CSS -->
  <link rel="stylesheet" href="/aima-exercises/public/css/poole.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/syntax.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/lanyon.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/style.css">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">
  <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="<KEY>" crossorigin="anonymous">

      <!-- Bootstrap CSS -->
      <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="<KEY>" crossorigin="anonymous">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/aima-exercises/public/apple-touch-icon-precomposed.png">
  <link rel="shortcut icon" href="/aima-exercises/public/aima_logo.ico">

  <!-- RSS -->
  <link rel="alternate" type="application/rss+xml" title="RSS" href="/atom.xml">
</head>

  <body>
    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="/aima-exercises/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="/aima-exercises/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="/aima-exercises/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="/aima-exercises/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="/aima-exercises/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="/aima-exercises/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="/aima-exercises/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="/aima-exercises/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="/aima-exercises/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="/aima-exercises/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="/aima-exercises/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="/aima-exercises/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="/aima-exercises/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="/aima-exercises/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v1.0.0</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; 2019. All rights reserved.
    </p>
  </div>
</div>

    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="/aima-exercises/" title="Home">Artificial Intelligence</a>
            <small>AIMA Exercises </small>
          </h3>
          <br>
          <center>
            <form class="form-inline active-pink-3 active-pink-4" action="/aima-exercises/search" id="site_search" autocomplete="off" method="GET">
              <i class="fas fa-search" aria-hidden="true"></i>
            <input class="form-control form-control-sm ml-3 w-75" type="text" placeholder="Search within AIMA Exercises" aria-label="Search" name="query">
            <input type="submit" value="Go!" class="search-btn">
            </form>
            <br>
            </center>
            



<ul class="breadcrumbb" id="bbreadcrumb">

  <label for="toggletoc" class="toc-icon">
    <span></span>
    <span></span>
    <span></span>
  </label>

   
   
    <li><a class="breadcrumb-text" href="/aima-exercises/"><i class="fa fa-home"></i></a>  </li>
   


</ul>

      </div>
    </div>
      <div class="container content">
        <article class="post">

  <div class="entry">
    <script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    TeX: {
      equationNumbers: {
        autoNumber: "AMS"
      }
    },
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true,
    },
    "HTML-CSS": { 
      preferredFont: "TeX", 
      availableFonts: ["STIX","TeX"], 
      styles: {".MathJax": {}} 
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<h1 id="14-probabilistic-reasoning">14. Probabilistic Reasoning</h1>

<div class="card">
<div class="card-header p-2">
<a href="ex_1/" class="p-2">Exercise 1 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex1');" href="#"><i id="ch14ex1" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.1);" href="#"><i id="ch14ex1" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

We have a bag of three biased coins $a$, $b$, and $c$ with probabilities
of coming up heads of 20%, 60%, and 80%, respectively. One coin is drawn
randomly from the bag (with equal likelihood of drawing each of the
three coins), and then the coin is flipped three times to generate the
outcomes $X_1$, $X_2$, and $X_3$.<br />

1.  Draw the Bayesian network corresponding to this setup and define the
    necessary CPTs.<br />

2.  Calculate which coin was most likely to have been drawn from the bag
    if the observed flips come out heads twice and tails once.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_2/" class="p-2">Exercise 2 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex2');" href="#"><i id="ch14ex2" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.2);" href="#"><i id="ch14ex2" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

We have a bag of three biased coins $a$, $b$, and $c$ with probabilities
of coming up heads of 30%, 60%, and 75%, respectively. One coin is drawn
randomly from the bag (with equal likelihood of drawing each of the
three coins), and then the coin is flipped three times to generate the
outcomes $X_1$, $X_2$, and $X_3$.<br />

1.  Draw the Bayesian network corresponding to this setup and define the
    necessary CPTs.<br />

2.  Calculate which coin was most likely to have been drawn from the bag
    if the observed flips come out heads twice and tails once.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_3/" class="p-2">Exercise 3(cpt-equivalence-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex3');" href="#"><i id="ch14ex3" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.3);" href="#"><i id="ch14ex3" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Equation (<a href="#">parameter-joint-repn-equation</a> on
page <a class="pageRef" title="" href="#">parameter-joint-repn-equation</a> defines the joint distribution represented by a
Bayesian network in terms of the parameters
$\theta(X_i{Parents}(X_i))$. This exercise asks you to derive
the equivalence between the parameters and the conditional probabilities
${\textbf{ P}}(X_i{Parents}(X_i))$ from this definition.<br />

1.  Consider a simple network $X\rightarrow Y\rightarrow Z$ with three
    Boolean variables. Use
    Equations (<a class="equationRef" title="" href="#">conditional-probability-equation</a> and (<a class="pageRef" title="" href="#">marginalization-equation</a>
    (pages <a href="#">conditional-probability-equation</a> and <a href="#">marginalization-equation</a>)
    to express the conditional probability $P(zy)$ as the ratio of two sums, each over entries in the
    joint distribution ${\textbf{P}}(X,Y,Z)$.<br />

2.  Now use Equation (<a class="equationRef" title="" href="#">parameter-joint-repn-equation</a> to
    write this expression in terms of the network parameters
    $\theta(X)$, $\theta(YX)$, and $\theta(ZY)$.<br />

3.  Next, expand out the summations in your expression from part (b),
    writing out explicitly the terms for the true and false values of
    each summed variable. Assuming that all network parameters satisfy
    the constraint
    $\sum_{x_i} \theta(x_i{parents}(X_i))1$, show
    that the resulting expression reduces to $\theta(zy)$.<br />

4.  Generalize this derivation to show that
    $\theta(X_i{Parents}(X_i)) = {\textbf{P}}(X_i{Parents}(X_i))$
    for any Bayesian network.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_4/" class="p-2">Exercise 4 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex4');" href="#"><i id="ch14ex4" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.4);" href="#"><i id="ch14ex4" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The <b>arc reversal</b> operation of in a Bayesian network allows us to change the direction
of an arc $X\rightarrow Y$ while preserving the joint probability
distribution that the network represents <a class="paperRef" title="" href="">Shachter:1986</a>. Arc reversal
may require introducing new arcs: all the parents of $X$ also become
parents of $Y$, and all parents of $Y$ also become parents of $X$.<br />

1.  Assume that $X$ and $Y$ start with $m$ and $n$ parents,
    respectively, and that all variables have $k$ values. By calculating
    the change in size for the CPTs of $X$ and $Y$, show that the total
    number of parameters in the network cannot decrease during
    arc reversal. (<i>Hint</i>: the parents of $X$ and $Y$ need
    not be disjoint.)<br />

2.  Under what circumstances can the total number remain constant?<br />

3.  Let the parents of $X$ be $\textbf{U} \cup \textbf{V}$ and the parents of $Y$ be
    $\textbf{V} \cup \textbf{W}$, where $\textbf{U}$ and $\textbf{W}$ are disjoint. The formulas for the
    new CPTs after arc reversal are as follows: $$\begin{aligned}
    {\textbf{P}}(Y | \textbf{U},\textbf{V},\textbf{W}) &amp;=&amp; \sum_x {\textbf{P}}(Y | \textbf{V},\textbf{W}, x) {\textbf{P}}(x | \textbf{U}, \textbf{V}) \\
    {\textbf{P}}(X | \textbf{U},\textbf{V},\textbf{W}, Y) &amp;=&amp; {\textbf{P}}(Y | X, \textbf{V}, \textbf{W}) {\textbf{P}}(X | \textbf{U}, \textbf{V}) / {\textbf{P}}(Y | \textbf{U},\textbf{V},\textbf{W})\ .\end{aligned}$$
    Prove that the new network expresses the same joint distribution
    over all variables as the original network.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_5/" class="p-2">Exercise 5 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex5');" href="#"><i id="ch14ex5" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.5);" href="#"><i id="ch14ex5" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the Bayesian network in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/burglary-figure.png">burglary-figure.</a><br />

1.  If no evidence is observed, are ${Burglary}$ and ${Earthquake}$
    independent? Prove this from the numerical semantics and from the
    topological semantics.<br />

2.  If we observe ${Alarm}{true}$, are ${Burglary}$ and
    ${Earthquake}$ independent? Justify your answer by calculating
    whether the probabilities involved satisfy the definition of
    conditional independence.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_6/" class="p-2">Exercise 6 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex6');" href="#"><i id="ch14ex6" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.6);" href="#"><i id="ch14ex6" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Suppose that in a Bayesian network containing an unobserved variable
$Y$, all the variables in the Markov blanket ${MB}(Y)$ have been
observed.<br />

1.  Prove that removing the node $Y$ from the network will not affect
    the posterior distribution for any other unobserved variable in
    the network.<br />

2.  Discuss whether we can remove $Y$ if we are planning to use (i)
    rejection sampling and (ii) likelihood weighting.<br />


    <figure>
      <img src="https://aimacode.github.io/aima-exercises/figures/handedness1.svg" alt="handedness-figure" id="handedness-figure" style="width:100%" />
      <figcaption><center><b>Three possible structures for a Bayesian network describing genetic inheritance of handedness.</b></center></figcaption>
    </figure>
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_7/" class="p-2">Exercise 7 (handedness-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex7');" href="#"><i id="ch14ex7" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.7);" href="#"><i id="ch14ex7" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Let $H_x$ be a random variable denoting the
handedness of an individual $x$, with possible values $l$ or $r$. A
common hypothesis is that left- or right-handedness is inherited by a
simple mechanism; that is, perhaps there is a gene $G_x$, also with
values $l$ or $r$, and perhaps actual handedness turns out mostly the
same (with some probability $s$) as the gene an individual possesses.
Furthermore, perhaps the gene itself is equally likely to be inherited
from either of an individual’s parents, with a small nonzero probability
$m$ of a random mutation flipping the handedness.<br />

1.  Which of the three networks in
    Figure <a class="insideExercisesFigRef" href="#handedness-figure">handedness-figure</a> claim that
    $ {\textbf{P}}(G_{father},G_{mother},G_{child}) = {\textbf{P}}(G_{father}){\textbf{P}}(G_{mother}){\textbf{P}}(G_{child})$?<br />

2.  Which of the three networks make independence claims that are
    consistent with the hypothesis about the inheritance of handedness?<br />

3.  Which of the three networks is the best description of the
    hypothesis?<br />

4.  Write down the CPT for the $G_{child}$ node in network (a), in
    terms of $s$ and $m$.<br />

5.  Suppose that
    $P(G_{father}l)=P(G_{mother}l)=q$. In
    network (a), derive an expression for $P(G_{child}l)$
    in terms of $m$ and $q$ only, by conditioning on its parent nodes.<br />

6.  Under conditions of genetic equilibrium, we expect the distribution
    of genes to be the same across generations. Use this to calculate
    the value of $q$, and, given what you know about handedness in
    humans, explain why the hypothesis described at the beginning of
    this question must be wrong.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_8/" class="p-2">Exercise 8 (markov-blanket-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex8');" href="#"><i id="ch14ex8" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.8);" href="#"><i id="ch14ex8" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">The <b>Markov
blanket</b> of a variable is defined on page <a href="#">markov-blanket-page</a>.
Prove that a variable is independent of all other variables in the
network, given its Markov blanket and derive
Equation (<a class="equationRef" title="" href="#">markov-blanket-equation</a>)
(page <a class="pageRef" title="" href="#">markov-blanket-equation</a>).
<figure>
  <img src="https://aimacode.github.io/aima-exercises/figures/car-starts.svg" alt="car-starts-figure" id="car-starts-figure" style="width:100%" />
    <figcaption><center><b>A Bayesian network describing some features of a car's electrical system and engine. Each variable is Boolean, and the <i>true</i> value indicates that the corresponding aspect of the vehicle is in working order.</b></center></figcaption>
</figure>
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_9/" class="p-2">Exercise 9 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex9');" href="#"><i id="ch14ex9" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.9);" href="#"><i id="ch14ex9" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the network for car diagnosis shown in
Figure <a class="insideExercisesFigRef" href="#car-starts-figure">car-starts-figure</a><br />.

1.  Extend the network with the Boolean variables ${IcyWeather}$ and
    ${StarterMotor}$.<br />

2.  Give reasonable conditional probability tables for all the nodes.<br />

3.  How many independent values are contained in the joint probability
    distribution for eight Boolean nodes, assuming that no conditional
    independence relations are known to hold among them?<br />

4.  How many independent probability values do your network tables
    contain?<br />

5.  The conditional distribution for ${Starts}$ could be described as
    a <b>noisy-AND</b> distribution. Define this
    family in general and relate it to the noisy-OR distribution.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_10/" class="p-2">Exercise 10 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex10');" href="#"><i id="ch14ex10" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.10);" href="#"><i id="ch14ex10" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider a simple Bayesian network with root variables ${Cold}$,
${Flu}$, and ${Malaria}$ and child variable ${Fever}$, with a
noisy-OR conditional distribution for ${Fever}$ as described in
Section <a class="sectionRef" title="" href="#">canonical-distribution-section</a>. By adding
appropriate auxiliary variables for inhibition events and fever-inducing
events, construct an equivalent Bayesian network whose CPTs (except for
root variables) are deterministic. Define the CPTs and prove
equivalence.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_11/" class="p-2">Exercise 11 (LG-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex11');" href="#"><i id="ch14ex11" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.11);" href="#"><i id="ch14ex11" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the family of linear Gaussian networks, as
defined on page <a class="pageRef" title="" href="#">LG-network-page</a><br />.

1.  In a two-variable network, let $X_1$ be the parent of $X_2$, let
    $X_1$ have a Gaussian prior, and let
    ${\textbf{P}}(X_2X_1)$ be a linear
    Gaussian distribution. Show that the joint distribution $P(X_1,X_2)$
    is a multivariate Gaussian, and calculate its covariance matrix.<br />

2.  Prove by induction that the joint distribution for a general linear
    Gaussian network on $X_1,\ldots,X_n$ is also a
    multivariate Gaussian.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_12/" class="p-2">Exercise 12 (multivalued-probit-exercise)</a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex12');" href="#"><i id="ch14ex12" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.12);" href="#"><i id="ch14ex12" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The probit distribution defined on
page <a class="pageRef" title="" href="#">probit-page</a> describes the probability distribution for a Boolean
child, given a single continuous parent.<br />

1.  How might the definition be extended to cover multiple continuous
    parents?<br />

2.  How might it be extended to handle a <i>multivalued</i>
    child variable? Consider both cases where the child’s values are
    ordered (as in selecting a gear while driving, depending on speed,
    slope, desired acceleration, etc.) and cases where they are
    unordered (as in selecting bus, train, or car to get to work).
    (<i>Hint</i>: Consider ways to divide the possible values
    into two sets, to mimic a Boolean variable.)
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_13/" class="p-2">Exercise 13 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex13');" href="#"><i id="ch14ex13" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.13);" href="#"><i id="ch14ex13" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

In your local nuclear power station, there is an alarm that senses when
a temperature gauge exceeds a given threshold. The gauge measures the
temperature of the core. Consider the Boolean variables $A$ (alarm
sounds), $F_A$ (alarm is faulty), and $F_G$ (gauge is faulty) and the
multivalued nodes $G$ (gauge reading) and $T$ (actual core temperature).<br />

1.  Draw a Bayesian network for this domain, given that the gauge is
    more likely to fail when the core temperature gets too high.<br />

2.  Is your network a polytree? Why or why not?<br />

3.  Suppose there are just two possible actual and measured
    temperatures, normal and high; the probability that the gauge gives
    the correct temperature is $x$ when it is working, but $y$ when it
    is faulty. Give the conditional probability table associated with
    $G$.<br />

4.  Suppose the alarm works correctly unless it is faulty, in which case
    it never sounds. Give the conditional probability table associated
    with $A$.<br />

5.  Suppose the alarm and gauge are working and the alarm sounds.
    Calculate an expression for the probability that the temperature of
    the core is too high, in terms of the various conditional
    probabilities in the network.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_14/" class="p-2">Exercise 14 (telescope-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex14');" href="#"><i id="ch14ex14" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.14);" href="#"><i id="ch14ex14" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">Two astronomers in different parts of the world
make measurements $M_1$ and $M_2$ of the number of stars $N$ in some
small region of the sky, using their telescopes. Normally, there is a
small possibility $e$ of error by up to one star in each direction. Each
telescope can also (with a much smaller probability $f$) be badly out of
focus (events $F_1$ and $F_2$), in which case the scientist will
undercount by three or more stars (or if $N$ is less than 3, fail to
detect any stars at all). Consider the three networks shown in
Figure <a class="insideExercisesFigRef" href="#telescope-nets-figure">telescope-nets-figure</a>.<br />

1.  Which of these Bayesian networks are correct (but not
    necessarily efficient) representations of the preceding information?<br />

2.  Which is the best network? Explain.<br />

3.  Write out a conditional distribution for
    ${\textbf{P}}(M_1N)$, for the case where
    $N\{1,2,3\}$ and $M_1\{0,1,2,3,4\}$. Each
    entry in the conditional distribution should be expressed as a
    function of the parameters $e$ and/or $f$.<br />

4.  Suppose $M_11$ and $M_23$. What are the
    <i>possible</i> numbers of stars if you assume no prior
    constraint on the values of $N$?<br />

5.  What is the <i>most likely</i> number of stars, given these
    observations? Explain how to compute this, or if it is not possible
    to compute, explain what additional information is needed and how it
    would affect the result.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_15/" class="p-2">Exercise 15 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex15');" href="#"><i id="ch14ex15" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.15);" href="#"><i id="ch14ex15" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the network shown in
Figure <a class="insideExercisesFigRef" href="#telescope-nets-figure">telescope-nets-figure</a>(ii), and assume that the
two telescopes work identically. $N\{1,2,3\}$ and
$M_1,M_2\{0,1,2,3,4\}$, with the symbolic CPTs as described
in Exercise <a class="exerciseRef" href="/aima-exercises/bayes-nets-exercises/ex_14/">telescope-exercise</a>. Using the enumeration
algorithm (Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/enumeration-algorithm.png">enumeration-algorithm</a> on
page <a class="pageRef" id="pageref" title="" href="#">enumeration-algorithm</a>), calculate the probability distribution
${\textbf{P}}(NM_12,M_22)$.<br />


<figure>
  <img src="https://aimacode.github.io/aima-exercises/figures/telescope-nets.svg" alt="telescope-nets-figure" id="telescope-nets-figure" style="width:100%" />
  <figcaption><center><b>Three possible networks for the telescope problem.</b></center></figcaption>
</figure>


</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_16/" class="p-2">Exercise 16 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex16');" href="#"><i id="ch14ex16" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.16);" href="#"><i id="ch14ex16" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the Bayes net shown in Figure <a class="insideExercisesFigRef" href="#politics-figure">politics-figure</a><br />.

1.  Which of the following are asserted by the network
    <i>structure</i>?<br />

    1.  ${\textbf{P}}(B,I,M) = {\textbf{P}}(B){\textbf{P}}(I){\textbf{P}}(M)$.<br />

    2.  ${\textbf{P}}(J|G) = {\textbf{P}}(J|G,I)$.<br />

    3.  ${\textbf{P}}(M|G,B,I) = {\textbf{P}}(M|G,B,I,J)$.<br />

2.  Calculate the value of $P(b,i,\lnot m,g,j)$.<br />

3.  Calculate the probability that someone goes to jail given that they
    broke the law, have been indicted, and face a politically
    motivated prosecutor.<br />

4.  A <b>context-specific independence</b> (see
    page <a class="pageRef" title="" href="#">CSI-page</a>) allows a variable to be independent of some of
    its parents given certain values of others. In addition to the usual
    conditional independences given by the graph structure, what
    context-specific independences exist in the Bayes net in
    Figure <a class="insideExercisesFigRef" href="#politics-figure">politics-figure</a>?<br />

5.  Suppose we want to add the variable
    $P={PresidentialPardon}$ to the network; draw the new
    network and briefly explain any links you add.<br />
<figure>
  <img src="https://aimacode.github.io/aima-exercises/figures/politics.svg" alt="politics-figure" id="politics-figure" style="width:100%" />
  <figcaption><center><b>A simple Bayes net with
  Boolean variables B = {BrokeElectionLaw}, I = {Indicted}, M = {PoliticallyMotivatedProsecutor}, G= {FoundGuilty}, J = {Jailed}.</b></center></figcaption>
</figure></p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_17/" class="p-2">Exercise 17 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex17');" href="#"><i id="ch14ex17" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.17);" href="#"><i id="ch14ex17" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the Bayes net shown in Figure <a class="insideExercisesFigRef" href="#politics-figure">politics-figure</a><br />.

1.  Which of the following are asserted by the network
    <i>structure</i>?<br />

    1.  ${\textbf{P}}(B,I,M) = {\textbf{P}}(B){\textbf{P}}(I){\textbf{P}}(M)$.<br />

    2.  ${\textbf{P}}(J|G) = {\textbf{P}}(J|G,I)$.<br />

    3.  ${\textbf{P}}(M|G,B,I) = {\textbf{P}}(M|G,B,I,J)$.<br />

2.  Calculate the value of $P(b,i,\lnot m,g,j)$.<br />

3.  Calculate the probability that someone goes to jail given that they
    broke the law, have been indicted, and face a politically
    motivated prosecutor.<br />

4.  A <b>context-specific independence</b> (see
    page <a class="pageRef" id="pageref" title="" href="#">CSI-page</a>) allows a variable to be independent of some of
    its parents given certain values of others. In addition to the usual
    conditional independences given by the graph structure, what
    context-specific independences exist in the Bayes net in
    Figure <a class="insideExercisesFigRef" id="insideexercisesfigref" href="#politics-figure">politics-figure</a>?<br />

5.  Suppose we want to add the variable
    $P={PresidentialPardon}$ to the network; draw the new
    network and briefly explain any links you add.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_18/" class="p-2">Exercise 18 (VE-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex18');" href="#"><i id="ch14ex18" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.18);" href="#"><i id="ch14ex18" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the variable elimination algorithm in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/elimination-ask-algorithm.png">elimination-ask-algorithm</a> (page <a class="pageRef" title="" href="#">elimination-ask-algorithm</a>).<br />

1.  Section <a class="sectionRef" title="" href="#">exact-inference-section</a> applies variable
    elimination to the query
    $${\textbf{P}}({Burglary}{JohnCalls}{true},{MaryCalls}{true})\ .$$
    Perform the calculations indicated and check that the answer
    is correct.<br />

2.  Count the number of arithmetic operations performed, and compare it
    with the number performed by the enumeration algorithm.<br />

3.  Suppose a network has the form of a <i>chain</i>: a sequence
    of Boolean variables $X_1,\ldots, X_n$ where
    ${Parents}(X_i)\{X_{i-1}\}$ for $i2,\ldots,n$.
    What is the complexity of computing
    ${\textbf{P}}(X_1X_n{true})$ using
    enumeration? Using variable elimination?<br />

4.  Prove that the complexity of running variable elimination on a
    polytree network is linear in the size of the tree for any variable
    ordering consistent with the network structure.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_19/" class="p-2">Exercise 19 (bn-complexity-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex19');" href="#"><i id="ch14ex19" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.19);" href="#"><i id="ch14ex19" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Investigate the complexity of exact inference
in general Bayesian networks:<br />

1.  Prove that any 3-SAT problem can be reduced to exact inference in a
    Bayesian network constructed to represent the particular problem and
    hence that exact inference is NP-hard. (<i>Hint</i>:
    Consider a network with one variable for each proposition symbol,
    one for each clause, and one for the conjunction of clauses.)<br />

2.  The problem of counting the number of satisfying assignments for a
    3-SAT problem is \#P-complete. Show that exact inference is at least
    as hard as this.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_20/" class="p-2">Exercise 20 (primitive-sampling-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex20');" href="#"><i id="ch14ex20" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.20);" href="#"><i id="ch14ex20" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the problem of generating a
random sample from a specified distribution on a single variable. Assume
you have a random number generator that returns a random number
uniformly distributed between 0 and 1.<br />

1.  Let $X$ be a discrete variable with
    $P(Xx_i)p_i$ for
    $i\{1,\ldots,k\}$. The <b>cumulative distribution</b> of $X$ gives the probability
    that $X\{x_1,\ldots,x_j\}$ for each possible $j$. (See
    also Appendix [math-appendix].) Explain how to
    calculate the cumulative distribution in $O(k)$ time and how to
    generate a single sample of $X$ from it. Can the latter be done in
    less than $O(k)$ time?<br />

2.  Now suppose we want to generate $N$ samples of $X$, where $N\gg k$.
    Explain how to do this with an expected run time per sample that is
    <i>constant</i> (i.e., independent of $k$).<br />

3.  Now consider a continuous-valued variable with a parameterized
    distribution (e.g., Gaussian). How can samples be generated from
    such a distribution?<br />

4.  Suppose you want to query a continuous-valued variable and you are
    using a sampling algorithm such as LIKELIHOODWEIGHTING to do the inference. How would
    you have to modify the query-answering process?
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_21/" class="p-2">Exercise 21 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex21');" href="#"><i id="ch14ex21" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.21);" href="#"><i id="ch14ex21" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider the query
${\textbf{P}}({Rain}{Sprinkler}{true},{WetGrass}{true})$
in Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/rain-clustering-figure.png">rain-clustering-figure</a>(a)
(page <a class="pageRef" title="" href="#">rain-clustering-figure</a>) and how Gibbs sampling can answer it.<br />

1.  How many states does the Markov chain have?<br />

2.  Calculate the <b>transition matrix</b>
    ${\textbf{Q}}$ containing
    $q({\textbf{y}}$ $\rightarrow$ ${\textbf{y}}')$
    for all ${\textbf{y}}$, ${\textbf{y}}'$.<br />

3.  What does ${\textbf{ Q}}^2$, the square of the
    transition matrix, represent?<br />

4.  What about ${\textbf{Q}}^n$ as $n\to \infty$?<br />

5.  Explain how to do probabilistic inference in Bayesian networks,
    assuming that ${\textbf{Q}}^n$ is available. Is this a
    practical way to do inference?
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_22/" class="p-2">Exercise 22 (gibbs-proof-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex22');" href="#"><i id="ch14ex22" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.22);" href="#"><i id="ch14ex22" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

This exercise explores the stationary
distribution for Gibbs sampling methods.<br />

1.  The convex composition $[\alpha, q_1; 1-\alpha, q_2]$ of $q_1$ and
    $q_2$ is a transition probability distribution that first chooses
    one of $q_1$ and $q_2$ with probabilities $\alpha$ and $1-\alpha$,
    respectively, and then applies whichever is chosen. Prove that if
    $q_1$ and $q_2$ are in detailed balance with $\pi$, then their
    convex composition is also in detailed balance with $\pi$.
    (<i>Note</i>: this result justifies a variant of GIBBS-ASK in which
    variables are chosen at random rather than sampled in a
    fixed sequence.)<br />

2.  Prove that if each of $q_1$ and $q_2$ has $\pi$ as its stationary
    distribution, then the sequential composition
    $q q_1 \circ q_2$ also has $\pi$ as its
    stationary distribution.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_23/" class="p-2">Exercise 23 (MH-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex23');" href="#"><i id="ch14ex23" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.23);" href="#"><i id="ch14ex23" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The <b>Metropolis--Hastings</b> algorithm is a member of the MCMC family; as such,
it is designed to generate samples $\textbf{x}$ (eventually) according to target
probabilities $\pi(\textbf{x})$. (Typically we are interested in sampling from
$\pi(\textbf{x})P(\textbf{x}\textbf{e})$.) Like simulated annealing,
Metropolis–Hastings operates in two stages. First, it samples a new
state $\textbf{x'}$ from a <b>proposal distribution</b> $q(\textbf{x'}\textbf{x})$, given the current state $\textbf{x}$.
Then, it probabilistically accepts or rejects $\textbf{x'}$ according to the <b>acceptance probability</b>
$$\alpha(\textbf{x'}\textbf{x}) = \min\ \left(1,\frac{\pi(\textbf{x'})q(\textbf{x}\textbf{x'})}{\pi(\textbf{x})q(\textbf{x'}\textbf{x})}  \right)\ .$$
If the proposal is rejected, the state remains at $\textbf{x}$.<br />

1.  Consider an ordinary Gibbs sampling step for a specific variable
    $X_i$. Show that this step, considered as a proposal, is guaranteed
    to be accepted by Metropolis–Hastings. (Hence, Gibbs sampling is a
    special case of Metropolis–Hastings.)<br />

2.  Show that the two-step process above, viewed as a transition
    probability distribution, is in detailed balance with $\pi$.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_24/" class="p-2">Exercise 24 (soccer-rpm-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch14ex24');" href="#"><i id="ch14ex24" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex14.24);" href="#"><i id="ch14ex24" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Three soccer teams $A$, $B$, and $C$, play each
other once. Each match is between two teams, and can be won, drawn, or
lost. Each team has a fixed, unknown degree of quality—an integer
ranging from 0 to 3—and the outcome of a match depends probabilistically
on the difference in quality between the two teams.<br />

1.  Construct a relational probability model to describe this domain,
    and suggest numerical values for all the necessary
    probability distributions.<br />

2.  Construct the equivalent Bayesian network for the three matches.<br />

3.  Suppose that in the first two matches $A$ beats $B$ and draws with
    $C$. Using an exact inference algorithm of your choice, compute the
    posterior distribution for the outcome of the third match.<br />

4.  Suppose there are $n$ teams in the league and we have the results
    for all but the last match. How does the complexity of predicting
    the last game vary with $n$?<br />

5.  Investigate the application of MCMC to this problem. How quickly
    does it converge in practice and how well does it scale?<br />
</p>
</div>
</div>
<p><br /></p>

  </div>

<!--   <div class="date">
    Written on 
  </div>
 -->
  
</article>


      </div>
    <label for="sidebar-checkbox" class="sidebar-toggle"></label>
    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');
        document.addEventListener('click', function(e) {
          var target = e.target;
          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;
          checkbox.checked = false;
        }, false);
      })(document);
    </script>
        <script src="/aima-exercises/js/main.js"></script>
        <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
        <script src="/aima-exercises/js/answer.js"></script>
        <script src="/aima-exercises/js/commsol.js"></script>
        <script src="/aima-exercises/js/forms.js"></script>
        <script src="/aima-exercises/js/crossref.js"></script>
        <script src="/aima-exercises/js/bookmark.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
  </body>
</html>


<|start_filename|>js/main.js<|end_filename|>

function myFunction() {
var x = document.getElementById("hideandviewanswers");
if (x.style.display === "none") {
  x.style.display = "block";
} else {
  x.style.display = "none";
}
};

function myFunction2() {
var y = document.getElementById("hideandviewcommunitysolution");
if (y.style.display === "none") {
  y.style.display = "block";
} else {
  y.style.display = "none";
}
};
function myFunction4()  {
  var z = document.getElementById("hideandviewusersolution");
  if (z.style.display === "none") {
    z.style.display = "block";
  } else {
    z.style.display = "none";
  }
};



<|start_filename|>markdown/answersubmittedd.html<|end_filename|>
---
layout: answersubmitted
permalink: /answersubmitted/
---
<h1>Thank You</h1>
<p>Your answer has been submitted. The answer will be visible after approval from an admin under the Student answers section.</p>
<a href="javascript:history.back()">Go Back</a>

<|start_filename|>_includes/sidebar2.html<|end_filename|>
<!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item{% if page.url == site.baseurl %} active{% endif %}" href="{{ site.baseurl }}/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="{{ site.baseurl }}/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v{{ site.version }}</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; {{ site.time | date: '%Y' }}. All rights reserved.
    </p>
  </div>
</div>


<|start_filename|>_site/knowledge-logic-exercises/index.html<|end_filename|>
<!DOCTYPE html>
<html lang="en-us">
  <head>
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
  <title>
    
      Logical Agents &middot; AIMA Exercises 
    
  </title>
  <!-- CSS -->
  <link rel="stylesheet" href="/aima-exercises/public/css/poole.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/syntax.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/lanyon.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/style.css">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">
  <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="<KEY>" crossorigin="anonymous">

      <!-- Bootstrap CSS -->
      <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="<KEY>" crossorigin="anonymous">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/aima-exercises/public/apple-touch-icon-precomposed.png">
  <link rel="shortcut icon" href="/aima-exercises/public/aima_logo.ico">

  <!-- RSS -->
  <link rel="alternate" type="application/rss+xml" title="RSS" href="/atom.xml">
</head>

  <body>
    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="/aima-exercises/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="/aima-exercises/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="/aima-exercises/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="/aima-exercises/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="/aima-exercises/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="/aima-exercises/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="/aima-exercises/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="/aima-exercises/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="/aima-exercises/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="/aima-exercises/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="/aima-exercises/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="/aima-exercises/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="/aima-exercises/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="/aima-exercises/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v1.0.0</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; 2019. All rights reserved.
    </p>
  </div>
</div>

    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="/aima-exercises/" title="Home">Artificial Intelligence</a>
            <small>AIMA Exercises </small>
          </h3>
          <br>
          <center>
            <form class="form-inline active-pink-3 active-pink-4" action="/aima-exercises/search" id="site_search" autocomplete="off" method="GET">
              <i class="fas fa-search" aria-hidden="true"></i>
            <input class="form-control form-control-sm ml-3 w-75" type="text" placeholder="Search within AIMA Exercises" aria-label="Search" name="query">
            <input type="submit" value="Go!" class="search-btn">
            </form>
            <br>
            </center>
            



<ul class="breadcrumbb" id="bbreadcrumb">

  <label for="toggletoc" class="toc-icon">
    <span></span>
    <span></span>
    <span></span>
  </label>

   
   
    <li><a class="breadcrumb-text" href="/aima-exercises/"><i class="fa fa-home"></i></a>  </li>
   


</ul>

      </div>
    </div>
      <div class="container content">
        <article class="post">

  <div class="entry">
    <script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    TeX: {
      equationNumbers: {
        autoNumber: "AMS"
      }
    },
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true,
    },
    "HTML-CSS": { 
      preferredFont: "TeX", 
      availableFonts: ["STIX","TeX"], 
      styles: {".MathJax": {}} 
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<h1 id="7-logical-agents">7. Logical Agents</h1>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_1/" class="p-2">Exercise 1 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex1');" href="#"><i id="ch7ex1" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.1');" href="#"><i id="ch7ex1" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Suppose the agent has progressed to the point shown in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/wumpus-seq35-figure.png">wumpus-seq35-figure</a>(a), page <a class="pageRef" title="" href="#">wumpus-seq35-figure</a>,
having perceived nothing in [1,1], a breeze in [2,1], and a stench
in [1,2], and is now concerned with the contents of [1,3], [2,2],
and [3,1]. Each of these can contain a pit, and at most one can
contain a wumpus. Following the example of
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/wumpus-entailment-figure.png">wumpus-entailment-figure</a>, construct the set of
possible worlds. (You should find 32 of them.) Mark the worlds in which
the KB is true and those in which each of the following sentences is
true:<br />

$\alpha_2$ = “There is no pit in [2,2].”<br />

$\alpha_3$ = “There is a wumpus in [1,3].”<br />

Hence show that ${KB} {\models}\alpha_2$ and
${KB} {\models}\alpha_3$.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_2/" class="p-2">Exercise 2 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex2');" href="#"><i id="ch7ex2" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.2');" href="#"><i id="ch7ex2" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

(Adapted from <a class="paperRef" title="" href="">Barwise+Etchemendy:1993</a> .) Given the following, can you prove that the unicorn is
mythical? How about magical? Horned?<br />

Note: If the unicorn is mythical, then it is immortal, but if it is not
 mythical, then it is a mortal mammal. If the unicorn is either
 immortal or a mammal, then it is horned. The unicorn is magical if it
 is horned.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_3/" class="p-2">Exercise 3 (truth-value-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex3');" href="#"><i id="ch7ex3" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.3');" href="#"><i id="ch7ex3" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the problem of deciding whether a
propositional logic sentence is true in a given model.<br />

1.  Write a recursive algorithm PL-True?$ (s, m )$ that returns ${true}$ if and
    only if the sentence $s$ is true in the model $m$ (where $m$ assigns
    a truth value for every symbol in $s$). The algorithm should run in
    time linear in the size of the sentence. (Alternatively, use a
    version of this function from the online code repository.)<br />

2.  Give three examples of sentences that can be determined to be true
    or false in a <i>partial</i> model that does not specify a
    truth value for some of the symbols.<br />

3.  Show that the truth value (if any) of a sentence in a partial model
    cannot be determined efficiently in general.<br />

4.  Modify your algorithm so that it can sometimes judge truth from
    partial models, while retaining its recursive structure and linear
    run time. Give three examples of sentences whose truth in a partial
    model is <i>not</i> detected by your algorithm.<br />

5.  Investigate whether the modified algorithm makes $TT-Entails?$ more efficient.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_4/" class="p-2">Exercise 4 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex4');" href="#"><i id="ch7ex4" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.4');" href="#"><i id="ch7ex4" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Which of the following are correct?<br />

1.  ${False} \models {True}$.<br />

2.  ${True} \models {False}$.<br />

3.  $(A\land B)  \models (A{\;\;{\Leftrightarrow}\;\;}B)$.<br />

4.  $A{\;\;{\Leftrightarrow}\;\;}B \models A \lor B$.<br />

5.  $A{\;\;{\Leftrightarrow}\;\;}B \models \lnot A \lor B$.<br />

6.  $(A\land B){\:\;{\Rightarrow}\:\;}C \models (A{\:\;{\Rightarrow}\:\;}C)\lor(B{\:\;{\Rightarrow}\:\;}C)$.<br />

7.  $(C\lor (\lnot A \land \lnot B)) \equiv ((A{\:\;{\Rightarrow}\:\;}C) \land (B {\:\;{\Rightarrow}\:\;}C))$.<br />

8.  $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B)$.<br />

9.  $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B) \land (\lnot D\lor E)$.<br />

10. $(A\lor B) \land \lnot(A {\:\;{\Rightarrow}\:\;}B)$ is satisfiable.<br />

11. $(A{\;\;{\Leftrightarrow}\;\;}B) \land (\lnot A \lor B)$
    is satisfiable.<br />

12. $(A{\;\;{\Leftrightarrow}\;\;}B) {\;\;{\Leftrightarrow}\;\;}C$ has
    the same number of models as $(A{\;\;{\Leftrightarrow}\;\;}B)$ for
    any fixed set of proposition symbols that includes $A$, $B$, $C$.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_5/" class="p-2">Exercise 5 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex5');" href="#"><i id="ch7ex5" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.5');" href="#"><i id="ch7ex5" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Which of the following are correct?<br />

1.  ${False} \models {True}$.<br />

2.  ${True} \models {False}$.<br />

3.  $(A\land B)  \models (A{\;\;{\Leftrightarrow}\;\;}B)$.<br />

4.  $A{\;\;{\Leftrightarrow}\;\;}B \models A \lor B$.<br />

5.  $A{\;\;{\Leftrightarrow}\;\;}B \models \lnot A \lor B$.<br />

6.  $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B\lor C) \land (B\land C\land D{\:\;{\Rightarrow}\:\;}E)$.<br />

7.  $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B) \land (\lnot D\lor E)$.<br />

8.  $(A\lor B) \land \lnot(A {\:\;{\Rightarrow}\:\;}B)$ is satisfiable.<br />

9.  $(A\land B){\:\;{\Rightarrow}\:\;}C \models (A{\:\;{\Rightarrow}\:\;}C)\lor(B{\:\;{\Rightarrow}\:\;}C)$.<br />

10. $(C\lor (\lnot A \land \lnot B)) \equiv ((A{\:\;{\Rightarrow}\:\;}C) \land (B {\:\;{\Rightarrow}\:\;}C))$.<br />

11. $(A{\;\;{\Leftrightarrow}\;\;}B) \land (\lnot A \lor B)$
    is satisfiable.<br />

12. $(A{\;\;{\Leftrightarrow}\;\;}B) {\;\;{\Leftrightarrow}\;\;}C$ has
    the same number of models as $(A{\;\;{\Leftrightarrow}\;\;}B)$ for
    any fixed set of proposition symbols that includes $A$, $B$, $C$.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_6/" class="p-2">Exercise 6 (deduction-theorem-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex6');" href="#"><i id="ch7ex6" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.6');" href="#"><i id="ch7ex6" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Prove each of the following assertions:<br />

1.  $\alpha$ is valid if and only if ${True}{\models}\alpha$.<br />

2.  For any $\alpha$, ${False}{\models}\alpha$.<br />

3.  $\alpha{\models}\beta$ if and only if the sentence
    $(\alpha {\:\;{\Rightarrow}\:\;}\beta)$ is valid.<br />

4.  $\alpha \equiv \beta$ if and only if the sentence
    $(\alpha{\;\;{\Leftrightarrow}\;\;}\beta)$ is valid.<br />

5.  $\alpha{\models}\beta$ if and only if the sentence
    $(\alpha \land \lnot \beta)$ is unsatisfiable.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_7/" class="p-2">Exercise 7 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex7');" href="#"><i id="ch7ex7" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.7');" href="#"><i id="ch7ex7" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Prove, or find a counterexample to, each of the following assertions:<br />

1.  If $\alpha\models\gamma$ or $\beta\models\gamma$ (or both) then
    $(\alpha\land \beta)\models\gamma$<br />

2.  If $(\alpha\land \beta)\models\gamma$ then $\alpha\models\gamma$ or
    $\beta\models\gamma$ (or both).<br />

3.  If $\alpha\models (\beta \lor \gamma)$ then $\alpha \models \beta$
    or $\alpha \models \gamma$ (or both).<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_8/" class="p-2">Exercise 8 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex8');" href="#"><i id="ch7ex8" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.8');" href="#"><i id="ch7ex8" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Prove, or find a counterexample to, each of the following assertions:<br />

1.  If $\alpha\models\gamma$ or $\beta\models\gamma$ (or both) then
    $(\alpha\land \beta)\models\gamma$<br />

2.  If $\alpha\models (\beta \land \gamma)$ then $\alpha \models \beta$
    and $\alpha \models \gamma$.<br />

3.  If $\alpha\models (\beta \lor \gamma)$ then $\alpha \models \beta$
    or $\alpha \models \gamma$ (or both).<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_9/" class="p-2">Exercise 9 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex9');" href="#"><i id="ch7ex9" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.9');" href="#"><i id="ch7ex9" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider a vocabulary with only four propositions, $A$, $B$, $C$, and
$D$. How many models are there for the following sentences?<br />

1.  $B\lor C$.<br />

2.  $\lnot A\lor \lnot B \lor \lnot C \lor \lnot D$.<br />

3.  $(A{\:\;{\Rightarrow}\:\;}B) \land A \land \lnot B \land C \land D$.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_10/" class="p-2">Exercise 10 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex10');" href="#"><i id="ch7ex10" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.10');" href="#"><i id="ch7ex10" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

We have defined four binary logical connectives.<br />

1.  Are there any others that might be useful?<br />

2.  How many binary connectives can there be?<br />

3.  Why are some of them not very useful?<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_11/" class="p-2">Exercise 11 (logical-equivalence-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex11');" href="#"><i id="ch7ex11" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.11');" href="#"><i id="ch7ex11" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Using a method of your choice, verify
each of the equivalences in
Table <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/logical-equivalence-table.png">logical-equivalence-table</a> (page <a class="pageRef" title="" href="#">logical-equivalence-table</a>).
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_12/" class="p-2">Exercise 12 (propositional-validity-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex12');" href="#"><i id="ch7ex12" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.12');" href="#"><i id="ch7ex12" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Decide whether each of the following
sentences is valid, unsatisfiable, or neither. Verify your decisions
using truth tables or the equivalence rules of
Table <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/logical-equivalence-table.png">logical-equivalence-table</a> (page <a class="pageRef" title="" href="#">logical-equivalence-table</a>).

1.  ${Smoke} {\:\;{\Rightarrow}\:\;}{Smoke}$<br />

2.  ${Smoke} {\:\;{\Rightarrow}\:\;}{Fire}$<br />

3.  $({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) {\:\;{\Rightarrow}\:\;}(\lnot {Smoke} {\:\;{\Rightarrow}\:\;}\lnot {Fire})$<br />

4.  ${Smoke} \lor {Fire} \lor \lnot {Fire}$<br />

5.  $(({Smoke} \land {Heat}) {\:\;{\Rightarrow}\:\;}{Fire})
            {\;\;{\Leftrightarrow}\;\;}(({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) \lor ({Heat} {\:\;{\Rightarrow}\:\;}{Fire}))$<br />

6.  $({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) {\:\;{\Rightarrow}\:\;}(({Smoke} \land {Heat}) {\:\;{\Rightarrow}\:\;}{Fire}) $<br />

7.  ${Big} \lor {Dumb} \lor ({Big} {\:\;{\Rightarrow}\:\;}{Dumb})$<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_13/" class="p-2">Exercise 13 (propositional-validity-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex13');" href="#"><i id="ch7ex13" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.13');" href="#"><i id="ch7ex13" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Decide whether each of the following
sentences is valid, unsatisfiable, or neither. Verify your decisions
using truth tables or the equivalence rules of
Table <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/logical-equivalence-table.png">logical-equivalence-table</a> (page <a class="pageRef" title="" href="#">logical-equivalence-table</a>).<br />

1.  ${Smoke} {\:\;{\Rightarrow}\:\;}{Smoke}$<br />

2.  ${Smoke} {\:\;{\Rightarrow}\:\;}{Fire}$<br />

3.  $({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) {\:\;{\Rightarrow}\:\;}(\lnot {Smoke} {\:\;{\Rightarrow}\:\;}\lnot {Fire})$<br />

4.  ${Smoke} \lor {Fire} \lor \lnot {Fire}$<br />

5.  $(({Smoke} \land {Heat}) {\:\;{\Rightarrow}\:\;}{Fire})
            {\;\;{\Leftrightarrow}\;\;}(({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) \lor ({Heat} {\:\;{\Rightarrow}\:\;}{Fire}))$<br />

6.  ${Big} \lor {Dumb} \lor ({Big} {\:\;{\Rightarrow}\:\;}{Dumb})$<br />

7.  $({Big} \land {Dumb}) \lor \lnot {Dumb}$<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_14/" class="p-2">Exercise 14 (cnf-proof-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex14');" href="#"><i id="ch7ex14" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.14');" href="#"><i id="ch7ex14" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Any propositional logic sentence is logically
equivalent to the assertion that each possible world in which it would
be false is not the case. From this observation, prove that any sentence
can be written in CNF.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_15/" class="p-2">Exercise 15 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex15');" href="#"><i id="ch7ex15" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.15');" href="#"><i id="ch7ex15" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Use resolution to prove the sentence $\lnot A \land \lnot B$ from the
clauses in Exercise <a class="exerciseRef" href="/aima-exercises/knowledge-logic-exercises/ex_25/">convert-clausal-exercise</a>.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_16/" class="p-2">Exercise 16 (inf-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex16');" href="#"><i id="ch7ex16" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.16');" href="#"><i id="ch7ex16" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

This exercise looks into the relationship between
clauses and implication sentences.<br />

1.  Show that the clause $(\lnot P_1 \lor \cdots \lor \lnot P_m \lor Q)$
    is logically equivalent to the implication sentence
    $(P_1 \land \cdots \land P_m) {\;{\Rightarrow}\;}Q$.<br />

2.  Show that every clause (regardless of the number of
    positive literals) can be written in the form
    $(P_1 \land \cdots \land P_m) {\;{\Rightarrow}\;}(Q_1 \lor \cdots \lor Q_n)$,
    where the $P$s and $Q$s are proposition symbols. A knowledge base
    consisting of such sentences is in implicative normal form or <b>Kowalski
    form</b> <a class="paperRef" title="" href="">Kowalski:1979</a>.<br />

3.  Write down the full resolution rule for sentences in implicative
    normal form.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_17/" class="p-2">Exercise 17 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex17');" href="#"><i id="ch7ex17" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.17');" href="#"><i id="ch7ex17" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">
According to some political pundits, a person who is radical ($R$) is
electable ($E$) if he/she is conservative ($C$), but otherwise is not
electable.<br />

1.  Which of the following are correct representations of this
    assertion?<br />

    1.  $(R\land E)\iff C$<br />

    2.  $R{\:\;{\Rightarrow}\:\;}(E\iff C)$<br />

    3.  $R{\:\;{\Rightarrow}\:\;}((C{\:\;{\Rightarrow}\:\;}E) \lor \lnot E)$<br />

2.  Which of the sentences in (a) can be expressed in Horn form?
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_18/" class="p-2">Exercise 18 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex18');" href="#"><i id="ch7ex18" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.18');" href="#"><i id="ch7ex18" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

This question considers representing satisfiability (SAT) problems as
CSPs.<br />

1.  Draw the constraint graph corresponding to the SAT problem
    $$(\lnot X_1 \lor X_2) \land (\lnot X_2 \lor X_3) \land \ldots \land (\lnot X_{n-1} \lor X_n)$$
    for the particular case $n5$.<br />

2.  How many solutions are there for this general SAT problem as a
    function of $n$?<br />

3.  Suppose we apply {Backtracking-Search} (page <a class="pageRef" title="" href="#">backtracking-search-algorithm</a>) to find <i>all</i>
    solutions to a SAT CSP of the type given in (a). (To find
    <i>all</i> solutions to a CSP, we simply modify the basic
    algorithm so it continues searching after each solution is found.)
    Assume that variables are ordered $X_1,\ldots,X_n$ and ${false}$
    is ordered before ${true}$. How much time will the algorithm take
    to terminate? (Write an $O(\cdot)$ expression as a function of $n$.)<br />

4.  We know that SAT problems in Horn form can be solved in linear time
    by forward chaining (unit propagation). We also know that every
    tree-structured binary CSP with discrete, finite domains can be
    solved in time linear in the number of variables
    (Section <a class="sectionRef" title="" href="#">csp-structure-section</a>). Are these two
    facts connected? Discuss.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_19/" class="p-2">Exercise 19 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex19');" href="#"><i id="ch7ex19" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.19');" href="#"><i id="ch7ex19" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

This question considers representing satisfiability (SAT) problems as
CSPs.<br />

1.  Draw the constraint graph corresponding to the SAT problem
    $$(\lnot X_1 \lor X_2) \land (\lnot X_2 \lor X_3) \land \ldots \land (\lnot X_{n-1} \lor X_n)$$
    for the particular case $n4$.<br />

2.  How many solutions are there for this general SAT problem as a
    function of $n$?<br />

3.  Suppose we apply {Backtracking-Search} (page <a class="pageRef" title="" href="#">backtracking-search-algorithm</a>) to find <i>all</i>
    solutions to a SAT CSP of the type given in (a). (To find
    <i>all</i> solutions to a CSP, we simply modify the basic
    algorithm so it continues searching after each solution is found.)
    Assume that variables are ordered $X_1,\ldots,X_n$ and ${false}$
    is ordered before ${true}$. How much time will the algorithm take
    to terminate? (Write an $O(\cdot)$ expression as a function of $n$.)<br />

4.  We know that SAT problems in Horn form can be solved in linear time
    by forward chaining (unit propagation). We also know that every
    tree-structured binary CSP with discrete, finite domains can be
    solved in time linear in the number of variables
    (Section <a class="sectionRef" title="" href="#">csp-structure-section</a>). Are these two
    facts connected? Discuss.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_20/" class="p-2">Exercise 20 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex20');" href="#"><i id="ch7ex20" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.20');" href="#"><i id="ch7ex20" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Explain why every nonempty propositional clause, by itself, is
satisfiable. Prove rigorously that every set of five 3-SAT clauses is
satisfiable, provided that each clause mentions exactly three distinct
variables. What is the smallest set of such clauses that is
unsatisfiable? Construct such a set.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_21/" class="p-2">Exercise 21 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex21');" href="#"><i id="ch7ex21" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.21');" href="#"><i id="ch7ex21" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

A propositional <i>2-CNF</i> expression is a conjunction of
clauses, each containing <i>exactly 2</i> literals, e.g.,
$$(A\lor B) \land (\lnot A \lor C) \land (\lnot B \lor D) \land (\lnot
  C \lor G) \land (\lnot D \lor G)\ .$$<br />

1.  Prove using resolution that the above sentence entails $G$.<br />

2.  Two clauses are <i>semantically distinct</i> if they are not
    logically equivalent. How many semantically distinct 2-CNF clauses
    can be constructed from $n$ proposition symbols?<br />

3.  Using your answer to (b), prove that propositional resolution always
    terminates in time polynomial in $n$ given a 2-CNF sentence
    containing no more than $n$ distinct symbols.<br />

4.  Explain why your argument in (c) does not apply to 3-CNF.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_22/" class="p-2">Exercise 22 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex22');" href="#"><i id="ch7ex22" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.2');" href="#"><i id="ch7ex22" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Prove each of the following assertions:<br />

1.  Every pair of propositional clauses either has no resolvents, or all
    their resolvents are logically equivalent.<br />

2.  There is no clause that, when resolved with itself, yields
    (after factoring) the clause $(\lnot P \lor \lnot Q)$.<br />

3.  If a propositional clause $C$ can be resolved with a copy of itself,
    it must be logically equivalent to $ True $.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_23/" class="p-2">Exercise 23 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex23');" href="#"><i id="ch7ex23" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.23');" href="#"><i id="ch7ex23" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the following sentence:<br />
$$[ ({Food} {\:\;{\Rightarrow}\:\;}{Party}) \lor ({Drinks} {\:\;{\Rightarrow}\:\;}{Party}) ] {\:\;{\Rightarrow}\:\;}[ ( {Food} \land {Drinks} )  {\:\;{\Rightarrow}\:\;}{Party}]\ .$$<br />

1.  Determine, using enumeration, whether this sentence is valid,
    satisfiable (but not valid), or unsatisfiable.<br />

2.  Convert the left-hand and right-hand sides of the main implication
    into CNF, showing each step, and explain how the results confirm
    your answer to (a).<br />

3.  Prove your answer to (a) using resolution.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_24/" class="p-2">Exercise 24 (dnf-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex24');" href="#"><i id="ch7ex24" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.24');" href="#"><i id="ch7ex24" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

A sentence is in disjunctive normal form(DNF) if it is the disjunction of
conjunctions of literals. For example, the sentence
$(A \land B \land \lnot C) \lor (\lnot A \land C) \lor (B \land \lnot C)$
is in DNF.<br />

1.  Any propositional logic sentence is logically equivalent to the
    assertion that some possible world in which it would be true is in
    fact the case. From this observation, prove that any sentence can be
    written in DNF.<br />

2.  Construct an algorithm that converts any sentence in propositional
    logic into DNF. (<i>Hint</i>: The algorithm is similar to
    the algorithm for conversion to CNF iven in
    Sectio <a class="sectionRef" title="" href="#">pl-resolution-section</a>.)<br />

3.  Construct a simple algorithm that takes as input a sentence in DNF
    and returns a satisfying assignment if one exists, or reports that
    no satisfying assignment exists.<br />

4.  Apply the algorithms in (b) and (c) to the following set of
    sentences:<br />

 $A {\Rightarrow} B$<br />

 $B {\Rightarrow} C$<br />

 $C {\Rightarrow} A$<br />

5.  Since the algorithm in (b) is very similar to the algorithm for
    conversion to CNF, and since the algorithm in (c) is much simpler
    than any algorithm for solving a set of sentences in CNF, why is
    this technique not used in automated reasoning?
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_25/" class="p-2">Exercise 25 (convert-clausal-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex25');" href="#"><i id="ch7ex25" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.25');" href="#"><i id="ch7ex25" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Convert the following set of sentences to
clausal form.<br />

1.  S1: $A {\;\;{\Leftrightarrow}\;\;}(B \lor E)$.<br />

2.  S2: $E {\:\;{\Rightarrow}\:\;}D$.<br />

3.  S3: $C \land F {\:\;{\Rightarrow}\:\;}\lnot B$.<br />

4.  S4: $E {\:\;{\Rightarrow}\:\;}B$.<br />

5.  S5: $B {\:\;{\Rightarrow}\:\;}F$.<br />

6.  S6: $B {\:\;{\Rightarrow}\:\;}C$<br />

Give a trace of the execution of DPLL on the conjunction of these
clauses.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_2/" class="p-2">Exercise 26 (convert-clausal-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex26');" href="#"><i id="ch7ex26" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.26');" href="#"><i id="ch7ex26" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Convert the following set of sentences to
clausal form.<br />

1.  S1: $A {\;\;{\Leftrightarrow}\;\;}(B \lor E)$.<br />

2.  S2: $E {\:\;{\Rightarrow}\:\;}D$.<br />

3.  S3: $C \land F {\:\;{\Rightarrow}\:\;}\lnot B$.<br />

4.  S4: $E {\:\;{\Rightarrow}\:\;}B$.<br />

5.  S5: $B {\:\;{\Rightarrow}\:\;}F$.<br />

6.  S6: $B {\:\;{\Rightarrow}\:\;}C$<br />

Give a trace of the execution of DPLL on the conjunction of these
clauses.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_27/" class="p-2">Exercise 27 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex27');" href="#"><i id="ch7ex27" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.27');" href="#"><i id="ch7ex27" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Is a randomly generated 4-CNF sentence with $n$ symbols and $m$ clauses
more or less likely to be solvable than a randomly generated 3-CNF
sentence with $n$ symbols and $m$ clauses? Explain.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_28/" class="p-2">Exercise 28 (minesweeper-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex28');" href="#"><i id="ch7ex28" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.28');" href="#"><i id="ch7ex28" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">Minesweeper, the well-known computer game, is
closely related to the wumpus world. A minesweeper world is
a rectangular grid of $N$ squares with $M$ invisible mines scattered
among them. Any square may be probed by the agent; instant death follows
if a mine is probed. Minesweeper indicates the presence of mines by
revealing, in each probed square, the <i>number</i> of mines
that are directly or diagonally adjacent. The goal is to probe every
unmined square.

1.  Let $X_{i,j}$ be true iff square $[i,j]$ contains a mine. Write down
    the assertion that exactly two mines are adjacent to \[1,1\] as a
    sentence involving some logical combination of
    $X_{i,j}$ propositions.

2.  Generalize your assertion from (a) by explaining how to construct a
    CNF sentence asserting that $k$ of $n$ neighbors contain mines.

3.  Explain precisely how an agent can use {DPLL} to prove that a given square
    does (or does not) contain a mine, ignoring the global constraint
    that there are exactly $M$ mines in all.

4.  Suppose that the global constraint is constructed from your method
    from part (b). How does the number of clauses depend on $M$ and $N$?
    Suggest a way to modify {DPLL} so that the global constraint does not need
    to be represented explicitly.

5.  Are any conclusions derived by the method in part (c) invalidated
    when the global constraint is taken into account?

6.  Give examples of configurations of probe values that induce
    <i>long-range dependencies</i> such that the contents of a
    given unprobed square would give information about the contents of a
    far-distant square. (<i>Hint</i>: consider an
    $N\times 1$ board.)
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_29/" class="p-2">Exercise 29 (known-literal-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex29');" href="#"><i id="ch7ex29" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.29');" href="#"><i id="ch7ex29" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

How long does it take to prove
${KB}{\models}\alpha$ using {DPLL} when $\alpha$ is a literal <i>already
contained in</i> ${KB}$? Explain.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_30/" class="p-2">Exercise 30 (dpll-fc-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex30');" href="#"><i id="ch7ex30" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.30');" href="#"><i id="ch7ex30" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Trace the behavior of {DPLL} on the knowledge base in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/pl-horn-example-figure.png">pl-horn-example-figure</a> when trying to prove $Q$,
and compare this behavior with that of the forward-chaining algorithm.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_31/" class="p-2">Exercise 31 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex31');" href="#"><i id="ch7ex31" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.31');" href="#"><i id="ch7ex31" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Write a successor-state axiom for the ${Locked}$ predicate, which
applies to doors, assuming the only actions available are ${Lock}$ and
${Unlock}$.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_32/" class="p-2">Exercise 32 </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex32');" href="#"><i id="ch7ex32" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.32');" href="#"><i id="ch7ex32" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Discuss what is meant by <i>optimal</i> behavior in the wumpus
world. Show that the {Hybrid-Wumpus-Agent} is not optimal, and suggest ways to improve it.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_3/" class="p-2">Exercise 33  </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex33');" href="#"><i id="ch7ex33" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.33');" href="#"><i id="ch7ex33" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Suppose an agent inhabits a world with two states, $S$ and $\lnot S$,
and can do exactly one of two actions, $a$ and $b$. Action $a$ does
nothing and action $b$ flips from one state to the other. Let $S^t$ be
the proposition that the agent is in state $S$ at time $t$, and let
$a^t$ be the proposition that the agent does action $a$ at time $t$
(similarly for $b^t$).<br />

1.  Write a successor-state axiom for $S^{t+1}$.<br />

2.  Convert the sentence in (a) into CNF.<br />

3.  Show a resolution refutation proof that if the agent is in $\lnot S$
    at time $t$ and does $a$, it will still be in $\lnot S$ at time
    $t+1$.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_34/" class="p-2">Exercise 34 (ss-axiom-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex34');" href="#"><i id="ch7ex34" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.34');" href="#"><i id="ch7ex34" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Section <a class="sectionRef" title="" href="#">successor-state-section</a>
provides some of the successor-state axioms required for the wumpus
world. Write down axioms for all remaining fluent symbols.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_35/" class="p-2">Exercise 35 (hybrid-wumpus-exercise) </a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch7ex35');" href="#"><i id="ch7ex35" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex7.35');" href="#"><i id="ch7ex35" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Modify the {Hybrid-Wumpus-Agent} to use the 1-CNF logical state
estimation method described on page <a class="pageRef" title="" href="#">1cnf-belief-state-page</a>. We noted on that page
that such an agent will not be able to acquire, maintain, and use more
complex beliefs such as the disjunction $P_{3,1}\lor P_{2,2}$. Suggest a
method for overcoming this problem by defining additional proposition
symbols, and try it out in the wumpus world. Does it improve the
performance of the agent?
</p>
    </div>
</div>

<p><br /></p>

  </div>

<!--   <div class="date">
    Written on 
  </div>
 -->
  
</article>


      </div>
    <label for="sidebar-checkbox" class="sidebar-toggle"></label>
    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');
        document.addEventListener('click', function(e) {
          var target = e.target;
          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;
          checkbox.checked = false;
        }, false);
      })(document);
    </script>
        <script src="/aima-exercises/js/main.js"></script>
        <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
        <script src="/aima-exercises/js/answer.js"></script>
        <script src="/aima-exercises/js/commsol.js"></script>
        <script src="/aima-exercises/js/forms.js"></script>
        <script src="/aima-exercises/js/crossref.js"></script>
        <script src="/aima-exercises/js/bookmark.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
  </body>
</html>


<|start_filename|>search_data.json<|end_filename|>
---
layout: null
---
{
  "_":{
	"title":"",
	"content":"",
	"url":""  	
  }	
  {% for page in site.pages %}
    {% if page.url != "/404.html" and page.url != "/search_data.json" and page.url!= "/assets/css/style.css" and page.url != "/" and page.url != "/style.css" and page.title and page.breadcrumb and page.title != "Main"%},
      "{{ page.url | slugify }}":  {
        "title": "{{ page.title | xml_escape }}",
        "breadcrumb": "{{ page.breadcrumb }}",
      	"content"  : "{{page.content | strip_html | strip_newlines | escape | remove: "\"}}",
        "url": " {{ page.url | xml_escape }}"
      }
    {% endif %}
  {% endfor %}
}

<|start_filename|>js/answer.js<|end_filename|>
document.addEventListener("DOMContentLoaded", function(event) {
    document.getElementById("viewusersolution").addEventListener("click", function(){
      url = document.getElementById("link").innerHTML
      console.log(url)
      document.getElementById("content").innerHTML = "No user answers available yet!"
      httpGetAsync(url, parseResponse)
      document.getElementById("link").innerHTML = ""
    });
    
    function parseResponse(o){
      files=  JSON.parse(o)
      console.log(files)
      for (file of files){
        f = file["download_url"]
        g = file["name"]
        console.log(f)
        console.log(g)
        if(g=="communityanswer.md")
        {
          console.log("Won't render")
        }
        else{
          httpGetAsync(f, renderContent)
        }
       
      }
    }
    
    function renderContent(data){
      console.log(data)
      contentArea = document.getElementById("content");
      
      var node = document.createElement("div");// Create a <div> node
      node.setAttribute("id", "answeridstyle");
      node.setAttribute("markdown","1");
      node.setAttribute("onclick","myFunc()");
      node.innerHTML = marked(data)    //Set inner HTML
      contentArea.appendChild(node);
      
    }
    
    function httpGetAsync(theUrl, callback){
      var xmlHttp = new XMLHttpRequest();
      xmlHttp.onreadystatechange = function() { 
          if (xmlHttp.readyState == 4 && xmlHttp.status == 200)
              callback(xmlHttp.responseText);
      }
      xmlHttp.open("GET", theUrl, true); // true for asynchronous 
      xmlHttp.send(null);
    }
  });
  

<|start_filename|>search/index.html<|end_filename|>
---
layout: default
title: Main
permalink: /search/
breadcrumb: Search Results
---
{% include mathjax_support %}

<div class="search_container">
<ul id="search_results"></ul>
</div>
<script type="text/javascript">
	window.aimaBaseURL = "{{ site.baseurl }}"
</script>
<script src="{{ site.baseurl }}/js/lib/lunr.js"></script>
<script src="{{ site.baseurl }}/js/lib/jquery.js"></script>
<script src="{{ site.baseurl }}/js/search.js"></script>

<|start_filename|>js/commsol.js<|end_filename|>
document.addEventListener("DOMContentLoaded", function(event) {
    document.getElementById("viewusersolution").addEventListener("click", function(){
      url = document.getElementById("link2").innerHTML
      console.log(url)
      document.getElementById("content2").innerHTML ="No Community answer available yet!";
      httpGetAsync(url, parseResponse)
      document.getElementById("link2").innerHTML = ""
    });
    
    function parseResponse(o)
    {
      files=  JSON.parse(o)
      console.log(files)
      present=false;
      for (file of files)
      {
        f = file["download_url"]
        g = file["name"]
        
        if(g=="communityanswer.md")
        {
          present=true;
          document.getElementById("content2").innerHTML ="";
        }
       }
       if(present == true)
       {
           for(file of files)
           {
               f = file["download_url"]
               g = file["name"]
               if(g=="communityanswer.md")
               {
                   httpGetAsync(f,renderContent)
               }
           }
       }
       if(present == false)
       {
        document.getElementById("content2").innerHTML=" No Community answer available yet!";
       }
     
    }
    
    function renderContent(data){
      console.log(data)
      contentArea = document.getElementById("content2");
      
      var node = document.createElement("div");// Create a <div> node
      node.innerHTML = marked(data)    //Set inner HTML
      contentArea.appendChild(node);
      
    }
    function httpGetAsync(theUrl, callback){
      var xmlHttp = new XMLHttpRequest();
      xmlHttp.onreadystatechange = function() { 
          if (xmlHttp.readyState == 4 && xmlHttp.status == 200)
              callback(xmlHttp.responseText);
      }
      xmlHttp.open("GET", theUrl, true); // true for asynchronous 
      xmlHttp.send(null);
    }
  });
  

<|start_filename|>_site/search-exercises/index.html<|end_filename|>
<!DOCTYPE html>
<html lang="en-us">
  <head>
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
  <title>
    
      Search Exercises &middot; AIMA Exercises 
    
  </title>
  <!-- CSS -->
  <link rel="stylesheet" href="/aima-exercises/public/css/poole.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/syntax.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/lanyon.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/style.css">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">
  <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="<KEY>" crossorigin="anonymous">

      <!-- Bootstrap CSS -->
      <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="<KEY>" crossorigin="anonymous">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/aima-exercises/public/apple-touch-icon-precomposed.png">
  <link rel="shortcut icon" href="/aima-exercises/public/aima_logo.ico">

  <!-- RSS -->
  <link rel="alternate" type="application/rss+xml" title="RSS" href="/atom.xml">
</head>

  <body>
    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="/aima-exercises/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="/aima-exercises/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="/aima-exercises/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="/aima-exercises/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="/aima-exercises/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="/aima-exercises/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="/aima-exercises/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="/aima-exercises/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="/aima-exercises/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="/aima-exercises/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="/aima-exercises/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="/aima-exercises/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="/aima-exercises/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="/aima-exercises/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v1.0.0</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; 2019. All rights reserved.
    </p>
  </div>
</div>

    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="/aima-exercises/" title="Home">Artificial Intelligence</a>
            <small>AIMA Exercises </small>
          </h3>
          <br>
          <center>
            <form class="form-inline active-pink-3 active-pink-4" action="/aima-exercises/search" id="site_search" autocomplete="off" method="GET">
              <i class="fas fa-search" aria-hidden="true"></i>
            <input class="form-control form-control-sm ml-3 w-75" type="text" placeholder="Search within AIMA Exercises" aria-label="Search" name="query">
            <input type="submit" value="Go!" class="search-btn">
            </form>
            <br>
            </center>
            



<ul class="breadcrumbb" id="bbreadcrumb">

  <label for="toggletoc" class="toc-icon">
    <span></span>
    <span></span>
    <span></span>
  </label>

   
   
    <li><a class="breadcrumb-text" href="/aima-exercises/"><i class="fa fa-home"></i></a>  </li>
   


</ul>

      </div>
    </div>
      <div class="container content">
        <article class="post">

  <div class="entry">
    <script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    TeX: {
      equationNumbers: {
        autoNumber: "AMS"
      }
    },
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true,
    },
    "HTML-CSS": { 
      preferredFont: "TeX", 
      availableFonts: ["STIX","TeX"], 
      styles: {".MathJax": {}} 
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<h1 id="3-solving-problems-by-searching">3. Solving Problems By Searching</h1>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_1/" class="p-2">Exercise 1</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex1');" href="#"><i id="ch3ex1" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.1');" href="#"><i id="ch3ex1" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Explain why problem formulation must follow goal formulation.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_2/" class="p-2">Exercise 2</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex2');" href="#"><i id="ch3ex2" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.2');" href="#"><i id="ch3ex2" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Give a complete problem formulation for each of the following problems.
Choose a formulation that is precise enough to be implemented.<br />

1.  There are six glass boxes in a row, each with a lock. Each of the
    first five boxes holds a key unlocking the next box in line; the
    last box holds a banana. You have the key to the first box, and you
    want the banana.<br />

2.  You start with the sequence ABABAECCEC, or in general any sequence
    made from A, B, C, and E. You can transform this sequence using the
    following equalities: AC = E, AB = BC, BB = E, and E$x$ = $x$ for
    any $x$. For example, ABBC can be transformed into AEC, and then AC,
    and then E. Your goal is to produce the sequence E.<br />

3.  There is an $n \times n$ grid of squares, each square initially
    being either unpainted floor or a bottomless pit. You start standing
    on an unpainted floor square, and can either paint the square under
    you or move onto an adjacent unpainted floor square. You want the
    whole floor painted.<br />

4.  A container ship is in port, loaded high with containers. There 13
    rows of containers, each 13 containers wide and 5 containers tall.
    You control a crane that can move to any location above the ship,
    pick up the container under it, and move it onto the dock. You want
    the ship unloaded.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_3/" class="p-2">Exercise 3</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex3');" href="#"><i id="ch3ex3" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.3');" href="#"><i id="ch3ex3" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Your goal is to navigate a robot out of a maze. The robot starts in the
center of the maze facing north. You can turn the robot to face north,
east, south, or west. You can direct the robot to move forward a certain
distance, although it will stop before hitting a wall.<br />

1.  Formulate this problem. How large is the state space?<br />

2.  In navigating a maze, the only place we need to turn is at the
    intersection of two or more corridors. Reformulate this problem
    using this observation. How large is the state space now?<br />

3.  From each point in the maze, we can move in any of the four
    directions until we reach a turning point, and this is the only
    action we need to do. Reformulate the problem using these actions.
    Do we need to keep track of the robot’s orientation now?<br />

4.  In our initial description of the problem we already abstracted from
    the real world, restricting actions and removing details. List three
    such simplifications we made.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_4/" class="p-2">Exercise 4</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex4');" href="#"><i id="ch3ex4" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.4');" href="#"><i id="ch3ex4" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

You have a $9 \times 9$ grid of squares, each of which can be colored
red or blue. The grid is initially colored all blue, but you can change
the color of any square any number of times. Imagining the grid divided
into nine $3 \times 3$ sub-squares, you want each sub-square to be all
one color but neighboring sub-squares to be different colors.<br />

1.  Formulate this problem in the straightforward way. Compute the size
    of the state space.<br />

2.  You need color a square only once. Reformulate, and compute the size
    of the state space. Would breadth-first graph search perform faster
    on this problem than on the one in (a)? How about iterative
    deepening tree search?<br />

3.  Given the goal, we need consider only colorings where each
    sub-square is uniformly colored. Reformulate the problem and compute
    the size of the state space.<br />

4.  How many solutions does this problem have?<br />

5.  Parts (b) and (c) successively abstracted the original problem (a).
    Can you give a translation from solutions in problem (c) into
    solutions in problem (b), and from solutions in problem (b) into
    solutions for problem (a)?<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_5/" class="p-2">Exercise 5 (two-friends-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex5');" href="#"><i id="ch3ex5" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.5');" href="#"><i id="ch3ex5" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Suppose two friends live in different cities on
a map, such as the Romania map shown in . On every turn, we can
simultaneously move each friend to a neighboring city on the map. The
amount of time needed to move from city $i$ to neighbor $j$ is equal to
the road distance $d(i,j)$ between the cities, but on each turn the
friend that arrives first must wait until the other one arrives (and
calls the first on his/her cell phone) before the next turn can begin.
We want the two friends to meet as quickly as possible.<br />

1.  Write a detailed formulation for this search problem. (You will find
    it helpful to define some formal notation here.)<br />

2.  Let $D(i,j)$ be the straight-line distance between cities $i$ and
    $j$. Which of the following heuristic functions are admissible? (i)
    $D(i,j)$; (ii) $2\cdot D(i,j)$; (iii) $D(i,j)/2$. <br />

3.  Are there completely connected maps for which no solution exists? <br />

4.  Are there maps in which all solutions require one friend to visit
    the same city twice?
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_6/" class="p-2">Exercise 6 (8puzzle-parity-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex6');" href="#"><i id="ch3ex6" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.6');" href="#"><i id="ch3ex6" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Show that the 8-puzzle states are divided
into two disjoint sets, such that any state is reachable from any other
state in the same set, while no state is reachable from any state in the
other set. (<i>Hint:</i> See <a class="paperRef" title="" href="#">Berlekamp+al:1982</a>) Devise a procedure to decide
which set a given state is in, and explain why this is useful for
generating random states.
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_7/" class="p-2">Exercise 7 (nqueens-size-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex7');" href="#"><i id="ch3ex7" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.7');" href="#"><i id="ch3ex7" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the $n$-queens problem using the
“efficient” incremental formulation given on page <a class="pageRef" title="" href="#">nqueens-page</a>. Explain why the state
space has at least $\sqrt[3]{n!}$ states and estimate the largest $n$
for which exhaustive exploration is feasible. (<i>Hint</i>:
Derive a lower bound on the branching factor by considering the maximum
number of squares that a queen can attack in any column.)
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_8/" class="p-2">Exercise 8</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex8');" href="#"><i id="ch3ex8" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.8');" href="#"><i id="ch3ex8" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Give a complete problem formulation for each of the following. Choose a
formulation that is precise enough to be implemented.<br />

1.  Using only four colors, you have to color a planar map in such a way
    that no two adjacent regions have the same color.<br />

2.  A 3-foot-tall monkey is in a room where some bananas are suspended
    from the 8-foot ceiling. He would like to get the bananas. The room
    contains two stackable, movable, climbable 3-foot-high crates.<br />

3.  You have a program that outputs the message “illegal input record”
    when fed a certain file of input records. You know that processing
    of each record is independent of the other records. You want to
    discover what record is illegal.<br />

4.  You have three jugs, measuring 12 gallons, 8 gallons, and 3 gallons,
    and a water faucet. You can fill the jugs up or empty them out from
    one to another or onto the ground. You need to measure out exactly
    one gallon.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_9/" class="p-2">Exercise 9 (path-planning-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex1');" href="#"><i id="ch3ex9" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.9');" href="#"><i id="ch3ex9" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the problem of finding the shortest
path between two points on a plane that has convex polygonal obstacles
as shown in . This is an idealization of the problem that a robot has to
solve to navigate in a crowded environment.<br />

1.  Suppose the state space consists of all positions $(x,y)$ in
    the plane. How many states are there? How many paths are there to
    the goal?<br />

2.  Explain briefly why the shortest path from one polygon vertex to any
    other in the scene must consist of straight-line segments joining
    some of the vertices of the polygons. Define a good state space now.
    How large is this state space?<br />

3.  Define the necessary functions to implement the search problem,
    including an function that takes a vertex as input and returns a set
    of vectors, each of which maps the current vertex to one of the
    vertices that can be reached in a straight line. (Do not forget the
    neighbors on the same polygon.) Use the straight-line distance for
    the heuristic function.<br />

4.  Apply one or more of the algorithms in this chapter to solve a range
    of problems in the domain, and comment on their performance.<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_10/" class="p-2">Exercise 10 (negative-g-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex10');" href="#"><i id="ch3ex10" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.10');" href="#"><i id="ch3ex10" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

On page <a class="pageRef" title="" href="#">non-negative-g</a>, we said that we would not consider problems
with negative path costs. In this exercise, we explore this decision in
more depth.<br />

1.  Suppose that actions can have arbitrarily large negative costs;
    explain why this possibility would force any optimal algorithm to
    explore the entire state space.<br />

2.  Does it help if we insist that step costs must be greater than or
    equal to some negative constant $c$? Consider both trees and graphs.<br />

3.  Suppose that a set of actions forms a loop in the state space such
    that executing the set in some order results in no net change to
    the state. If all of these actions have negative cost, what does
    this imply about the optimal behavior for an agent in such an
    environment?<br />

4.  One can easily imagine actions with high negative cost, even in
    domains such as route finding. For example, some stretches of road
    might have such beautiful scenery as to far outweigh the normal
    costs in terms of time and fuel. Explain, in precise terms, within
    the context of state-space search, why humans do not drive around
    scenic loops indefinitely, and explain how to define the state space
    and actions for route finding so that artificial agents can also
    avoid looping.<br />

5.  Can you think of a real domain in which step costs are such as to
    cause looping?<br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_11/" class="p-2">Exercise 11 (mc-problem)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex11');" href="#"><i id="ch3ex11" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.11');" href="#"><i id="ch3ex11" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

The problem is usually stated as follows. Three
missionaries and three cannibals are on one side of a river, along with
a boat that can hold one or two people. Find a way to get everyone to
the other side without ever leaving a group of missionaries in one place
outnumbered by the cannibals in that place. This problem is famous in AI
because it was the subject of the first paper that approached problem
formulation from an analytical viewpoint <a href="#" class="paperRef" title="">Amarel:1968</a>. <br />

1.  Formulate the problem precisely, making only those distinctions
    necessary to ensure a valid solution. Draw a diagram of the complete
    state space.<br />

2.  Implement and solve the problem optimally using an appropriate
    search algorithm. Is it a good idea to check for repeated states? <br />

3.  Why do you think people have a hard time solving this puzzle, given
    that the state space is so simple? <br />
</p>
    </div>
</div>

<p><br /></p>

<div class="card">
    <div class="card-header p-2">
        <a href="ex_1/" class="p-2">Exercise 12</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex12');" href="#"><i id="ch3ex12" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.12');" href="#"><i id="ch3ex12" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Define in your own words the following terms: state, state space, search
tree, search node, goal, action, transition model, and branching factor.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_13/" class="p-2">Exercise 13</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex13');" href="#"><i id="ch3ex13" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.13');" href="#"><i id="ch3ex13" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

What’s the difference between a world state, a state description, and a
search node? Why is this distinction useful?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_14/" class="p-2">Exercise 14</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex14');" href="#"><i id="ch3ex14" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.14');" href="#"><i id="ch3ex14" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

An action such as really consists of a long sequence of finer-grained
actions: turn on the car, release the brake, accelerate forward, etc.
Having composite actions of this kind reduces the number of steps in a
solution sequence, thereby reducing the search time. Suppose we take
this to the logical extreme, by making super-composite actions out of
every possible sequence of actions. Then every problem instance is
solved by a single super-composite action, such as . Explain how search
would work in this formulation. Is this a practical approach for
speeding up problem solving?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_15/" class="p-2">Exercise 15</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex15');" href="#"><i id="ch3ex15" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.15');" href="#"><i id="ch3ex15" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Does a finite state space always lead to a finite search tree? How about
a finite state space that is a tree? Can you be more precise about what
types of state spaces always lead to finite search trees? (Adapted from
, 1996.)
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_16/" class="p-2">Exercise 16 (graph-separation-property-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex16');" href="#"><i id="ch3ex16" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.16');" href="#"><i id="ch3ex16" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Prove that satisfies the graph
separation property illustrated in . (<i>Hint</i>: Begin by
showing that the property holds at the start, then show that if it holds
before an iteration of the algorithm, it holds afterwards.) Describe a
search algorithm that violates the property.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_17/" class="p-2">Exercise 17</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex17');" href="#"><i id="ch3ex17" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.17');" href="#"><i id="ch3ex17" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Which of the following are true and which are false? Explain your
answers.<br />

1.  Depth-first search always expands at least as many nodes as A search
    with an admissible heuristic. <br />

2.  $h(n)=0$ is an admissible heuristic for the 8-puzzle. <br />

3.  A is of no use in robotics because percepts, states, and actions
    are continuous.<br />

4.  Breadth-first search is complete even if zero step costs
    are allowed. <br />

5.  Assume that a rook can move on a chessboard any number of squares in
    a straight line, vertically or horizontally, but cannot jump over
    other pieces. Manhattan distance is an admissible heuristic for the
    problem of moving the rook from square A to square B in the smallest
    number of moves.<br />
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_18/" class="p-2">Exercise 18</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex18');" href="#"><i id="ch3ex18" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.18');" href="#"><i id="ch3ex18" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider a state space where the start state is number 1 and each state
$k$ has two successors: numbers $2k$ and $2k+1$. <br />

1.  Draw the portion of the state space for states 1 to 15. <br />

2.  Suppose the goal state is 11. List the order in which nodes will be
    visited for breadth-first search, depth-limited search with limit 3,
    and iterative deepening search. <br />

3.  How well would bidirectional search work on this problem? What is
    the branching factor in each direction of the bidirectional search?<br />

4.  Does the answer to (c) suggest a reformulation of the problem that
    would allow you to solve the problem of getting from state 1 to a
    given goal state with almost no search? <br />

5.  Call the action going from $k$ to $2k$ Left, and the action going to
    $2k+1$ Right. Can you find an algorithm that outputs the solution to
    this problem without any search at all?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_19/" class="p-2">Exercise 19 (brio-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex19');" href="#"><i id="ch3ex19" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.19');" href="#"><i id="ch3ex19" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

A basic wooden railway set contains the pieces shown in
. The task is to connect these pieces into a railway that has no
overlapping tracks and no loose ends where a train could run off onto
the floor.<br />

1.  Suppose that the pieces fit together <i>exactly</i> with no
    slack. Give a precise formulation of the task as a search problem.<br />

2.  Identify a suitable uninformed search algorithm for this task and
    explain your choice.<br />

3.  Explain why removing any one of the “fork” pieces makes the
    problem unsolvable. <br />

4.  Give an upper bound on the total size of the state space defined by
    your formulation. (<i>Hint</i>: think about the maximum
    branching factor for the construction process and the maximum depth,
    ignoring the problem of overlapping pieces and loose ends. Begin by
    pretending that every piece is unique.)
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_20/" class="p-2">Exercise 20</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex20');" href="#"><i id="ch3ex20" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.20');" href="#"><i id="ch3ex20" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Implement two versions of the function for the 8-puzzle: one that copies
and edits the data structure for the parent node $s$ and one that
modifies the parent state directly (undoing the modifications as
needed). Write versions of iterative deepening depth-first search that
use these functions and compare their performance.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_21/" class="p-2">Exercise 21 (iterative-lengthening-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex21');" href="#"><i id="ch3ex21" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.21');" href="#"><i id="ch3ex21" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

On page <a class="pageRef" title="" href="#">iterative-lengthening-page</a>,
we mentioned <b>iterative lengthening search</b>,
an iterative analog of uniform cost search. The idea is to use increasing limits on
path cost. If a node is generated whose path cost exceeds the current
limit, it is immediately discarded. For each new iteration, the limit is
set to the lowest path cost of any node discarded in the previous
iteration.<br />

1.  Show that this algorithm is optimal for general path costs.<br />

2.  Consider a uniform tree with branching factor $b$, solution depth
    $d$, and unit step costs. How many iterations will iterative
    lengthening require?<br />

3.  Now consider step costs drawn from the continuous range
    $[\epsilon,1]$, where $0 &lt; \epsilon &lt; 1$. How many iterations are
    required in the worst case? <br />

4.  Implement the algorithm and apply it to instances of the 8-puzzle
    and traveling salesperson problems. Compare the algorithm’s
    performance to that of uniform-cost search, and comment on
    your results. <br />
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_22/" class="p-2">Exercise 22</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex22');" href="#"><i id="ch3ex22" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.22');" href="#"><i id="ch3ex22" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Describe a state space in which iterative deepening search performs much
worse than depth-first search (for example, $O(n^{2})$ vs. $O(n)$).
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_23/" class="p-2">Exercise 23</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex23');" href="#"><i id="ch3ex23" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.23');" href="#"><i id="ch3ex23" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Write a program that will take as input two Web page URLs and find a
path of links from one to the other. What is an appropriate search
strategy? Is bidirectional search a good idea? Could a search engine be
used to implement a predecessor function?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_24/" class="p-2">Exercise 24 (vacuum-search-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex24');" href="#"><i id="ch3ex24" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.24');" href="#"><i id="ch3ex24" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the vacuum-world problem defined in .<br />

1.  Which of the algorithms defined in this chapter would be appropriate
    for this problem? Should the algorithm use tree search or graph
    search?<br />

2.  Apply your chosen algorithm to compute an optimal sequence of
    actions for a $3\times 3$ world whose initial state has dirt in the
    three top squares and the agent in the center.<br />

3.  Construct a search agent for the vacuum world, and evaluate its
    performance in a set of $3\times 3$ worlds with probability 0.2 of
    dirt in each square. Include the search cost as well as path cost in
    the performance measure, using a reasonable exchange rate.<br />

4.  Compare your best search agent with a simple randomized reflex agent
    that sucks if there is dirt and otherwise moves randomly.<br />

5.  Consider what would happen if the world were enlarged to
    $n \times n$. How does the performance of the search agent and of
    the reflex agent vary with $n$? <br />
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_25/" class="p-2">Exercise 25 (search-special-case-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex25');" href="#"><i id="ch3ex25" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.25');" href="#"><i id="ch3ex25" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Prove each of the following statements,
or give a counterexample: <br />

1.  Breadth-first search is a special case of uniform-cost search.<br />

2.  Depth-first search is a special case of best-first tree search.<br />

3.  Uniform-cost search is a special case of A search.<br />
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_26/" class="p-2">Exercise 26</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex26');" href="#"><i id="ch3ex26" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.26');" href="#"><i id="ch3ex26" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Compare the performance of A and RBFS on a set of randomly generated
problems in the 8-puzzle (with Manhattan distance) and TSP (with MST—see
) domains. Discuss your results. What happens to the performance of RBFS
when a small random number is added to the heuristic values in the
8-puzzle domain?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_27/" class="p-2">Exercise 27</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex27');" href="#"><i id="ch3ex27" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.27');" href="#"><i id="ch3ex27" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Trace the operation of A search applied to the problem of getting to
Bucharest from Lugoj using the straight-line distance heuristic. That
is, show the sequence of nodes that the algorithm will consider and the
$f$, $g$, and $h$ score for each node.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_28/" class="p-2">Exercise 28</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex28');" href="#"><i id="ch3ex28" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.28');" href="#"><i id="ch3ex28" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">
Sometimes there is no good evaluation function for a problem but there
is a good comparison method: a way to tell whether one node is better
than another without assigning numerical values to either. Show that
this is enough to do a best-first search. Is there an analog of A for
this setting?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_29/" class="p-2">Exercise 29 (failure-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex29');" href="#"><i id="ch3ex29" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.29');" href="#"><i id="ch3ex29" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Devise a state space in which A using returns a
suboptimal solution with an $h(n)$ function that is admissible but
inconsistent.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_30/" class="p-2">Exercise 30</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex30');" href="#"><i id="ch3ex30" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.30');" href="#"><i id="ch3ex30" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Accurate heuristics don’t necessarily reduce search time in the worst
case. Given any depth $d$, define a search problem with a goal node at
depth $d$, and write a heuristic function such that $|h(n) - h^\*(n)|  \le O(\log h^\*(n))$ but $A^*$ expands all nodes of depth less
than $d$.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_31/" class="p-2">Exercise 31</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex31');" href="#"><i id="ch3ex31" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.31');" href="#"><i id="ch3ex31" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

The <b>heuristic path algorithm</b> <a class="paperRef" title="" href="#">Pohl:1977</a> is a best-first search in which the evaluation function
is $f(n) =
(2-w)g(n) + wh(n)$. For what values of $w$ is this complete? For what
values is it optimal, assuming that $h$ is admissible? What kind of
search does this perform for $w=0$, $w=1$, and $w=2$?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_1/" class="p-2">Exercise 32</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex32');" href="#"><i id="ch3ex32" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.32');" href="#"><i id="ch3ex32" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the unbounded version of the regular 2D grid shown in . The
start state is at the origin, (0,0), and the goal state is at $(x,y)$.<br />

1.  What is the branching factor $b$ in this state space?<br />

2.  How many distinct states are there at depth $k$ (for $k&gt;0$)?<br />

3.  What is the maximum number of nodes expanded by breadth-first tree
    search?<br />

4.  What is the maximum number of nodes expanded by breadth-first graph
    search?<br />

5.  Is $h = |u-x| + |v-y|$ an admissible heuristic for a state at
    $(u,v)$? Explain.<br />

6.  How many nodes are expanded by A graph search using $h$?<br />

7.  Does $h$ remain admissible if some links are removed?<br />

8.  Does $h$ remain admissible if some links are added between
    nonadjacent states?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_33/" class="p-2">Exercise 33</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex33');" href="#"><i id="ch3ex33" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.33');" href="#"><i id="ch3ex33" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

$n$ vehicles occupy squares $(1,1)$ through $(n,1)$ (i.e., the bottom
row) of an $n\times n$ grid. The vehicles must be moved to the top row
but in reverse order; so the vehicle $i$ that starts in $(i,1)$ must end
up in $(n-i+1,n)$. On each time step, every one of the $n$ vehicles can
move one square up, down, left, or right, or stay put; but if a vehicle
stays put, one other adjacent vehicle (but not more than one) can hop
over it. Two vehicles cannot occupy the same square. <br />

1.  Calculate the size of the state space as a function of $n$.<br />

2.  Calculate the branching factor as a function of $n$.<br />

3.  Suppose that vehicle $i$ is at $(x_i,y_i)$; write a nontrivial
    admissible heuristic $h_i$ for the number of moves it will require
    to get to its goal location $(n-i+1,n)$, assuming no other vehicles
    are on the grid.<br />

4.  Which of the following heuristics are admissible for the problem of
    moving all $n$ vehicles to their destinations? Explain.<br />

    1.  $\sum_{i= 1}^{n} h_i$.<br />

    2.  $\max\{h_1,\ldots,h_n\}$.<br />

    3.  $\min\{h_1,\ldots,h_n\}$.<br />
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_34/" class="p-2">Exercise 34</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex34');" href="#"><i id="ch3ex34" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.34');" href="#"><i id="ch3ex34" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Consider the problem of moving $k$ knights from $k$ starting squares
$s_1,\ldots,s_k$ to $k$ goal squares $g_1,\ldots,g_k$, on an unbounded
chessboard, subject to the rule that no two knights can land on the same
square at the same time. Each action consists of moving <i>up
to</i> $k$ knights simultaneously. We would like to complete the
maneuver in the smallest number of actions.<br />

1.  What is the maximum branching factor in this state space, expressed
    as a function of $k$?<br />

2.  Suppose $h_i$ is an admissible heuristic for the problem of moving
    knight $i$ to goal $g_i$ by itself. Which of the following
    heuristics are admissible for the $k$-knight problem? Of those,
    which is the best?<br />

    1.  $\min\{h_1,\ldots,h_k\}$.<br />

    2.  $\max\{h_1,\ldots,h_k\}$.<br />

    3.  $\sum_{i= 1}^{k} h_i$.<br />

3.  Repeat (b) for the case where you are allowed to move only one
    knight at a time.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_35/" class="p-2">Exercise 35</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex35');" href="#"><i id="ch3ex35" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.35');" href="#"><i id="ch3ex35" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">
We saw on page <a class="pageRef" title="" href="#">I-to-F</a> that the straight-line distance heuristic leads greedy
best-first search astray on the problem of going from Iasi to Fagaras.
However, the heuristic is perfect on the opposite problem: going from
Fagaras to Iasi. Are there problems for which the heuristic is
misleading in both directions?
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_36/" class="p-2">Exercise 36</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex36');" href="#"><i id="ch3ex36" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.36');" href="#"><i id="ch3ex36" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

Invent a heuristic function for the 8-puzzle that sometimes
overestimates, and show how it can lead to a suboptimal solution on a
particular problem. (You can use a computer to help if you want.) Prove
that if $h$ never overestimates by more than $c$, A using $h$ returns a
solution whose cost exceeds that of the optimal solution by no more than
$c$.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_37/" class="p-2">Exercise 37 (consistent-heuristic-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex37');" href="#"><i id="ch3ex37" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.37');" href="#"><i id="ch3ex37" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">Prove that if a heuristic is
consistent, it must be admissible. Construct an admissible heuristic
that is not consistent.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_38/" class="p-2">Exercise 38 (tsp-mst-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex38');" href="#"><i id="ch3ex38" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.38');" href="#"><i id="ch3ex38" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">The traveling salesperson problem (TSP) can be
solved with the minimum-spanning-tree (MST) heuristic, which estimates
the cost of completing a tour, given that a partial tour has already
been constructed. The MST cost of a set of cities is the smallest sum of
the link costs of any tree that connects all the cities.<br />

1.  Show how this heuristic can be derived from a relaxed version of
    the TSP.<br />

2.  Show that the MST heuristic dominates straight-line distance.<br />

3.  Write a problem generator for instances of the TSP where cities are
    represented by random points in the unit square.<br />

4.  Find an efficient algorithm in the literature for constructing the
    MST, and use it with A graph search to solve instances of the TSP.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_39/" class="p-2">Exercise 39 (Gaschnig-h-exercise)</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex39');" href="#"><i id="ch3ex39" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.39');" href="#"><i id="ch3ex39" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

On page <a class="pageRef" title="" href="#">Gaschnig-h-page</a> , we defined the relaxation of the 8-puzzle in
which a tile can move from square A to square B if B is blank. The exact
solution of this problem defines <b>Gaschnig's heuristic</b> <a class="paperRef" title="" href="#">Gaschnig:1979</a>. Explain why Gaschnig’s
heuristic is at least as accurate as $h_1$ (misplaced tiles), and show
cases where it is more accurate than both $h_1$ and $h_2$ (Manhattan
distance). Explain how to calculate Gaschnig’s heuristic efficiently.
</p>
    </div>
</div>

<p><br /></p>
<div class="card">
    <div class="card-header p-2">
        <a href="ex_40/" class="p-2">Exercise 40</a>
        <button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch3ex40');" href="#"><i id="ch3ex40" class="fas fa-bookmark" style="color:white"></i></button>
        <button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex3.40');" href="#"><i id="ch3ex40" class="fas fa-thumbs-up" style="color:white"></i></button>
    </div>
    <div class="card-body">
        <p class="card-text">

We gave two simple heuristics for the 8-puzzle: Manhattan distance and
misplaced tiles. Several heuristics in the literature purport to improve
on this—see, for example, <a class="paperRef" title="" href="#">Nilsson:1971</a>,
<a class="paperRef" title="" href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.75.3333&amp;rep=rep1&amp;type=pdf">Mostow+Prieditis:1989</a>, and <a href="https://europepmc.org/abstract/med/1534722" title="" class="paperRef">Hansson+al:1992</a>. Test these claims by implementing
the heuristics and comparing the performance of the resulting
algorithms.
</p>
    </div>
</div>

<p><br /></p>

  </div>

<!--   <div class="date">
    Written on 
  </div>
 -->
  
</article>


      </div>
    <label for="sidebar-checkbox" class="sidebar-toggle"></label>
    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');
        document.addEventListener('click', function(e) {
          var target = e.target;
          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;
          checkbox.checked = false;
        }, false);
      })(document);
    </script>
        <script src="/aima-exercises/js/main.js"></script>
        <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
        <script src="/aima-exercises/js/answer.js"></script>
        <script src="/aima-exercises/js/commsol.js"></script>
        <script src="/aima-exercises/js/forms.js"></script>
        <script src="/aima-exercises/js/crossref.js"></script>
        <script src="/aima-exercises/js/bookmark.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
  </body>
</html>


<|start_filename|>_site/planning-exercises/index.html<|end_filename|>
<!DOCTYPE html>
<html lang="en-us">
  <head>
  <link href="http://gmpg.org/xfn/11" rel="profile">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta http-equiv="content-type" content="text/html; charset=utf-8">
  <!-- Enable responsiveness on mobile devices-->
  <meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1">
  <title>
    
      Classical Planning &middot; AIMA Exercises 
    
  </title>
  <!-- CSS -->
  <link rel="stylesheet" href="/aima-exercises/public/css/poole.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/syntax.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/lanyon.css">
  <link rel="stylesheet" href="/aima-exercises/public/css/style.css">
  <link rel="stylesheet" href="https://fonts.googleapis.com/css?family=PT+Serif:400,400italic,700%7CPT+Sans:400">
  <link rel="stylesheet" href="https://use.fontawesome.com/releases/v5.8.1/css/all.css" integrity="<KEY>" crossorigin="anonymous">

      <!-- Bootstrap CSS -->
      <link rel="stylesheet" href="https://stackpath.bootstrapcdn.com/bootstrap/4.3.1/css/bootstrap.min.css" integrity="<KEY>" crossorigin="anonymous">

  <!-- Icons -->
  <link rel="apple-touch-icon-precomposed" sizes="144x144" href="/aima-exercises/public/apple-touch-icon-precomposed.png">
  <link rel="shortcut icon" href="/aima-exercises/public/aima_logo.ico">

  <!-- RSS -->
  <link rel="alternate" type="application/rss+xml" title="RSS" href="/atom.xml">
</head>

  <body>
    <!-- Target for toggling the sidebar `.sidebar-checkbox` is for regular
     styles, `#sidebar-checkbox` for behavior. -->
<input type="checkbox" class="sidebar-checkbox" id="sidebar-checkbox">

<!-- Toggleable sidebar -->
<div class="sidebar" id="sidebar">
  <div class="sidebar-item">
    <p>Artificial Intelligence : A Modern Approach</p>
  </div>

  <nav class="sidebar-nav">
    <a class="sidebar-nav-item" href="/aima-exercises/">Home</a>
    <span class="sidebar-nav-item">Part - I Artificial Intelligence</span>
  <a class="sidebar-nav-item" href="/aima-exercises/intro-exercises/">Chapter 1 - Introduction</a>
  <a class="sidebar-nav-item" href="/aima-exercises/agents-exercises/">Chapter 2 - Intelligent Agents</a>
  <span class="sidebar-nav-item">Part - II Problem Solving</span>
  <a class="sidebar-nav-item" href="/aima-exercises/search-exercises/">Chapter 3 - Solving Problems By Searching</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-search-exercises">Chapter 4 - Beyond Classical Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/game-playing-exercises">Chapter 5 - Adversarial Search</a>
  <a class="sidebar-nav-item" href="/aima-exercises/csp-exercises">Chapter 6 - Constraint Satisfaction Problems</a>
  <span class="sidebar-nav-item">Part - III Knowledge, Reasoning and Planning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/knowledge-logic-exercises">Chapter 7 - Logical Agents</a>
  <a class="sidebar-nav-item" href="/aima-exercises/fol-exercises">Chapter 8 - First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/logical-inference-exercises">Chapter 9 - Inference in First Order Logic</a>
  <a class="sidebar-nav-item" href="/aima-exercises/planning-exercises">Chapter 10 - Classical Planning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/advanced-planning-exercises">Chapter 11 - Planning and Acting in Real Life</a>
  <a class="sidebar-nav-item" href="/aima-exercises/kr-exercises">Chapter 12 - Knowledge Representation</a>
  <span class="sidebar-nav-item">Part - IV Uncertaing Knowledge and Reasoning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/probability-exercises">Chapter 13 - Quantifying Uncertainty</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayes-nets-exercises">Chapter 14 - Probabilistic Reasoning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/dbn-exercises">Chapter 15 - Probabilistic Reasoning Over Time</a>
  <a class="sidebar-nav-item" href="/aima-exercises/decision-theory-exercises">Chapter 16 - Making-Simple Decisions</a>
  <a class="sidebar-nav-item" href="/aima-exercises/complex-decisions-exercises">Chapter 17 - Making Complex Decisions</a>
  <span class="sidebar-nav-item">Part - V Lerning</span>
  <a class="sidebar-nav-item" href="/aima-exercises/concept-learning-exercises">Chapter 18 - Learning From Examples</a>
  <a class="sidebar-nav-item" href="/aima-exercises/ilp-exercises">Chapter 19 - Knowledge In Learning</a>
  <a class="sidebar-nav-item" href="/aima-exercises/bayesian-learning-exercises">Chapter 20 - Learning Probabilistic Models</a>
  <a class="sidebar-nav-item" href="/aima-exercises/reinforcement-learning-exercises">Chapter 21 - Reinforcement Learning</a>
  <span class="sidebar-nav-item">Part - VI Communicating, Perceiving and Acting</span>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-communicating-exercises">Chapter 22 - Natural Language Processing</a>
  <a class="sidebar-nav-item" href="/aima-exercises/nlp-english-exercises">Chapter 23 - Natural Language For Communication</a>
  <a class="sidebar-nav-item" href="/aima-exercises/perception-exercises">Chapter 24 - Perception</a>
  <a class="sidebar-nav-item" href="/aima-exercises/robotics-exercises">Chapter 25 - Robotics</a>
  <span class="sidebar-nav-item">Part - VII Conclusions</span>
  <a class="sidebar-nav-item" href="/aima-exercises/philosophy-exercises">Chapter 26 - Philosophical Foundations</a>
  <a class="sidebar-nav-item" href="/aima-exercises/#/">Chapter 27 - AI The Present And Future</a>
    <span class="sidebar-nav-item">Currently v1.0.0</span>
  </nav>

  <div class="sidebar-item">
    <p>
      &copy; 2019. All rights reserved.
    </p>
  </div>
</div>

    <div class="wrap">
      <div class="masthead">
        <div class="container">
          <h3 class="masthead-title">
            <a href="/aima-exercises/" title="Home">Artificial Intelligence</a>
            <small>AIMA Exercises </small>
          </h3>
          <br>
          <center>
            <form class="form-inline active-pink-3 active-pink-4" action="/aima-exercises/search" id="site_search" autocomplete="off" method="GET">
              <i class="fas fa-search" aria-hidden="true"></i>
            <input class="form-control form-control-sm ml-3 w-75" type="text" placeholder="Search within AIMA Exercises" aria-label="Search" name="query">
            <input type="submit" value="Go!" class="search-btn">
            </form>
            <br>
            </center>
            



<ul class="breadcrumbb" id="bbreadcrumb">

  <label for="toggletoc" class="toc-icon">
    <span></span>
    <span></span>
    <span></span>
  </label>

   
   
    <li><a class="breadcrumb-text" href="/aima-exercises/"><i class="fa fa-home"></i></a>  </li>
   


</ul>

      </div>
    </div>
      <div class="container content">
        <article class="post">

  <div class="entry">
    <script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    TeX: {
      equationNumbers: {
        autoNumber: "AMS"
      }
    },
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true,
    },
    "HTML-CSS": { 
      preferredFont: "TeX", 
      availableFonts: ["STIX","TeX"], 
      styles: {".MathJax": {}} 
    }
  });
</script>

<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.0/MathJax.js?config=TeX-AMS-MML_HTMLorMML">
</script>

<h1 id="10-classical-planning">10. Classical Planning</h1>
<div class="card">
<div class="card-header p-2">
<a href="ex_1/" class="p-2">Exercise 1 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex1');" href="#"><i id="ch10ex1" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.1);" href="#"><i id="ch10ex1" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider a robot whose operation is described by the following PDDL
operators:<br />

$$
Op({Go(x,y)},{At(Robot,x)},{\lnot At(Robot,x) \land At(Robot,y)})
$$
$$
Op({Pick(o)},{At(Robot,x)\land At(o,x)},{\lnot At(o,x) \land Holding(o)})
$$
$$
Op({Drop(o)},{At(Robot,x)\land Holding(o)},{At(o,x) \land \lnot Holding(o)}
$$

1.  The operators allow the robot to hold more than one object. Show how
    to modify them with an $EmptyHand$ predicate for a robot that can
    hold only one object.<br />

2.  Assuming that these are the only actions in the world, write a
    successor-state axiom for $EmptyHand$.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_2/" class="p-2">Exercise 2 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex2');" href="#"><i id="ch10ex2" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.2);" href="#"><i id="ch10ex2" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Describe the differences and similarities between problem solving and
planning.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_3/" class="p-2">Exercise 3 (strips-airport-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex3');" href="#"><i id="ch10ex3" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.3);" href="#"><i id="ch10ex3" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">Given the action schemas and initial state
from Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/airport-pddl-algorithm.png">airport-pddl-algorithm</a>, what are all the
applicable concrete instances of ${Fly}(p,{from},{to})$ in the
state described by<br />

$$
At(P_1,JFK) \land At(P_2,SFO) \land Plane(P_1) \land Plane(P_2) \land Airport(JFK) \land Airport(SFO)?
$$
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_4/" class="p-2">Exercise 4 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex4');" href="#"><i id="ch10ex4" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.4);" href="#"><i id="ch10ex4" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The monkey-and-bananas problem is faced by a monkey in a laboratory with
some bananas hanging out of reach from the ceiling. A box is available
that will enable the monkey to reach the bananas if he climbs on it.
Initially, the monkey is at $A$, the bananas at $B$, and the box at $C$.
The monkey and box have height ${Low}$, but if the monkey climbs onto
the box he will have height ${High}$, the same as the bananas. The
actions available to the monkey include ${Go}$ from one place to
another, ${Push}$ an object from one place to another, ${ClimbUp}$
onto or ${ClimbDown}$ from an object, and ${Grasp}$ or ${Ungrasp}$
an object. The result of a ${Grasp}$ is that the monkey holds the
object if the monkey and object are in the same place at the same
height.<br />

1.  Write down the initial state description.<br />

2.  Write the six action schemas.<br />

3.  Suppose the monkey wants to fool the scientists, who are off to tea,
    by grabbing the bananas, but leaving the box in its original place.
    Write this as a general goal (i.e., not assuming that the box is
    necessarily at C) in the language of situation calculus. Can this
    goal be solved by a classical planning system?<br />

4.  Your schema for pushing is probably incorrect, because if the object
    is too heavy, its position will remain the same when the ${Push}$
    schema is applied. Fix your action schema to account for
    heavy objects.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_5/" class="p-2">Exercise 5 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex5');" href="#"><i id="ch10ex5" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.5);" href="#"><i id="ch10ex5" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The original {Strips} planner was designed to control Shakey the robot.
Figure <a class="insideExercisesFigRef" href="#shakey-figure">shakey-figure</a> shows a version of Shakey’s world
consisting of four rooms lined up along a corridor, where each room has
a door and a light switch. The actions in Shakey’s world include moving from place to place,
pushing movable objects (such as boxes), climbing onto and down from
rigid objects (such as boxes), and turning light switches on and off.
The robot itself could not climb on a box or toggle a switch, but the
planner was capable of finding and printing out plans that were beyond
the robot’s abilities. Shakey’s six actions are the following:<br />

-   ${Go}(x,y,r)$, which requires that Shakey be ${At}$ $x$ and that
    $x$ and $y$ are locations ${In}$ the same room $r$. By convention
    a door between two rooms is in both of them.<br />

-   Push a box $b$ from location $x$ to location $y$ within the same
    room: ${Push}(b,x,y,r)$. You will need the predicate ${Box}$ and
    constants for the boxes.<br />

-   Climb onto a box from position $x$: ${ClimbUp}(x, b)$; climb down
    from a box to position $x$: ${ClimbDown}(b, x)$. We will need the
    predicate ${On}$ and the constant ${Floor}$.<br />

-   Turn a light switch on or off: ${TurnOn}(s,b)$;
    ${TurnOff}(s,b)$. To turn a light on or off, Shakey must be on top
    of a box at the light switch’s location.<br />

Write PDDL sentences for Shakey’s six actions and the initial state from
Construct a plan for Shakey to
get ${Box}{}_2$ into ${Room}{}_2$.<br />

  <figure>
    <img src="https://aimacode.github.io/aima-exercises/figures/shakey2.svg" alt="shakey-figure" id="shakey-figure" style="width:100%" />
    <figcaption><center><b>Shakey's world. Shakey can move between landmarks within a room, can pass through the door between rooms, can climb climbable objects and push pushable objects, and can flip light switches.</b></center></figcaption>
  </figure>
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_6/" class="p-2">Exercise 6 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex6');" href="#"><i id="ch10ex6" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.6);" href="#"><i id="ch10ex6" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

A finite Turing machine has a finite one-dimensional tape of cells, each
cell containing one of a finite number of symbols. One cell has a read
and write head above it. There is a finite set of states the machine can
be in, one of which is the accept state. At each time step, depending on
the symbol on the cell under the head and the machine’s current state,
there are a set of actions we can choose from. Each action involves
writing a symbol to the cell under the head, transitioning the machine
to a state, and optionally moving the head left or right. The mapping
that determines which actions are allowed is the Turing machine’s
program. Your goal is to control the machine into the accept state.<br />
<br />
Represent the Turing machine acceptance problem as a planning problem.
If you can do this, it demonstrates that determining whether a planning
problem has a solution is at least as hard as the Turing acceptance
problem, which is PSPACE-hard.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_7/" class="p-2">Exercise 7 (negative-effects-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex7');" href="#"><i id="ch10ex7" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.7);" href="#"><i id="ch10ex7" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Explain why dropping negative effects from
every action schema results in a relaxed problem, provided that
preconditions and goals contain only positive literals.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_8/" class="p-2">Exercise 8 (sussman-anomaly-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex8');" href="#"><i id="ch10ex8" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.8);" href="#"><i id="ch10ex8" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/sussman-anamoly-figure.png">sussman-anomaly-figure</a>
(page <a class="pageRef" title="" href="#">sussman-anomaly-figure</a>) shows a blocks-world problem that is known as the {Sussman anomaly}.
The problem was considered anomalous because the noninterleaved planners
of the early 1970s could not solve it. Write a definition of the problem
and solve it, either by hand or with a planning program. A
noninterleaved planner is a planner that, when given two subgoals
$G_{1}$ and $G_{2}$, produces either a plan for $G_{1}$ concatenated
with a plan for $G_{2}$, or vice versa. Can a noninterleaved planner
solve this problem? How, or why not?
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_9/" class="p-2">Exercise 9 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex9');" href="#"><i id="ch10ex9" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.9);" href="#"><i id="ch10ex9" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Prove that backward search with PDDL problems is complete.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_10/" class="p-2">Exercise 10 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex10');" href="#"><i id="ch10ex10" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.10);" href="#"><i id="ch10ex10" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Construct levels 0, 1, and 2 of the planning graph for the problem in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/airport-pddl-algorithm.png">airport-pddl-algorithm</a>
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_11/" class="p-2">Exercise 11 (graphplan-proof-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex11');" href="#"><i id="ch10ex11" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.11);" href="#"><i id="ch10ex11" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Prove the following assertions about
planning graphs:<br />

1.  A literal that does not appear in the final level of the graph
    cannot be achieved.<br />

2.  The level cost of a literal in a serial graph is no greater than the
    actual cost of an optimal plan for achieving it.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_12/" class="p-2">Exercise 12 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex12');" href="#"><i id="ch10ex12" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.12);" href="#"><i id="ch10ex12" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

We saw that planning graphs can handle only propositional actions. What
if we want to use planning graphs for a problem with variables in the
goal, such as ${At}(P_{1}, x)
    \land {At}(P_{2}, x)$, where $x$ is assumed to be bound by an
existential quantifier that ranges over a finite domain of locations?
How could you encode such a problem to work with planning graphs?
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_13/" class="p-2">Exercise 13 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex13');" href="#"><i id="ch10ex13" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.13);" href="#"><i id="ch10ex13" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

The set-level heuristic (see page <a class="pageRef" title="" href="#">set-level-page</a> uses a planning graph
to estimate the cost of achieving a conjunctive goal from the current
state. What relaxed problem is the set-level heuristic the solution to?
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_14/" class="p-2">Exercise 14 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex14');" href="#"><i id="ch10ex14" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.14);" href="#"><i id="ch10ex14" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Examine the definition of <b>bidirectional search</b> in Chapter <a class="chapterRef" title="" href="/aima-exercises/search-exercises/">search-chapter</a>.<br />

1.  Would bidirectional state-space search be a good idea for planning?<br />

2.  What about bidirectional search in the space of partial-order plans?<br />

3.  Devise a version of partial-order planning in which an action can be
    added to a plan if its preconditions can be achieved by the effects
    of actions already in the plan. Explain how to deal with conflicts
    and ordering constraints. Is the algorithm essentially identical to
    forward state-space search?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_15/" class="p-2">Exercise 15 </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex15');" href="#"><i id="ch10ex15" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.15);" href="#"><i id="ch10ex15" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

We contrasted forward and backward state-space searchers with
partial-order planners, saying that the latter is a plan-space searcher.
Explain how forward and backward state-space search can also be
considered plan-space searchers, and say what the plan refinement
operators are.
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_16/" class="p-2">Exercise 16 (satplan-preconditions-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex16');" href="#"><i id="ch10ex16" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.16);" href="#"><i id="ch10ex16" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Up to now we have assumed that the
plans we create always make sure that an action’s preconditions are
satisfied. Let us now investigate what propositional successor-state
axioms such as ${HaveArrow}^{t+1} {\;\;{\Leftrightarrow}\;\;}{}$
$({HaveArrow}^t
\land \lnot {Shoot}^t)$ have to say about actions whose preconditions
are not satisfied.<br />

1.  Show that the axioms predict that nothing will happen when an action
    is executed in a state where its preconditions are not satisfied.<br />

2.  Consider a plan $p$ that contains the actions required to achieve a
    goal but also includes illegal actions. Is it the case that
$$
initial state \land successor-state axioms \land
p {\models} goal ?
$$

3.  With first-order successor-state axioms in situation calculus, is it
    possible to prove that a plan containing illegal actions will
    achieve the goal?<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_17/" class="p-2">Exercise 17 (strips-translation-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex17');" href="#"><i id="ch10ex17" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.17);" href="#"><i id="ch10ex17" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

Consider how to translate a set of action
schemas into the successor-state axioms of situation calculus.<br />

1.  Consider the schema for ${Fly}(p,{from},{to})$. Write a
    logical definition for the predicate
    ${Poss}({Fly}(p,{from},{to}),s)$, which is true if the
    preconditions for ${Fly}(p,{from},{to})$ are satisfied in
    situation $s$.<br />

2.  Next, assuming that ${Fly}(p,{from},{to})$ is the only action
    schema available to the agent, write down a successor-state axiom
    for ${At}(p,x,s)$ that captures the same information as the
    action schema.<br />

3.  Now suppose there is an additional method of travel:
    ${Teleport}(p,{from},{to})$. It has the additional
    precondition $\lnot {Warped}(p)$ and the additional effect
    ${Warped}(p)$. Explain how the situation calculus knowledge base
    must be modified.<br />

4.  Finally, develop a general and precisely specified procedure for
    carrying out the translation from a set of action schemas to a set
    of successor-state axioms.<br />
</p>
</div>
</div>
<p><br /></p>
<div class="card">
<div class="card-header p-2">
<a href="ex_18/" class="p-2">Exercise 18 (disjunctive-satplan-exercise) </a>
<button type="button" class="btn btn-dark float-right" title="Bookmark Exercise" onclick="bookmark('ch10ex18');" href="#"><i id="ch10ex18" class="fas fa-bookmark" style="color:white"></i></button>
<button type="button" class="btn btn-dark float-right" style="margin-left:10px; margin-right:10px;" title="Upvote Exercise" onclick="upvote('ex10.18);" href="#"><i id="ch10ex18" class="fas fa-thumbs-up" style="color:white"></i></button>
</div>
<div class="card-body">
<p class="card-text">

In the $SATPlan$ algorithm in
Figure <a class="insideBookFigRef" target="_blank" href="https://aimacode.github.io/aima-exercises/figures/satplan-agent-algorithm.png">satplan-agent-algorithm</a> (page <a class="pageRef" title="" href="#">satplan-agent-algorithm</a>,
each call to the satisfiability algorithm asserts a goal $g^T$, where
$T$ ranges from 0 to $T_{max}$. Suppose instead that the
satisfiability algorithm is called only once, with the goal
$g^0 \vee g^1 \vee \cdots \vee g^{T_{max}}$. <br />

1.  Will this always return a plan if one exists with length less than
    or equal to $T_{max}$? <br />

2.  Does this approach introduce any new spurious “solutions”?<br />

3.  Discuss how one might modify a satisfiability algorithm such as $WalkSAT$ so
    that it finds short solutions (if they exist) when given a
    disjunctive goal of this form.<br />
</p>
</div>
</div>
<p><br /></p>

  </div>

<!--   <div class="date">
    Written on 
  </div>
 -->
  
</article>


      </div>
    <label for="sidebar-checkbox" class="sidebar-toggle"></label>
    <script>
      (function(document) {
        var toggle = document.querySelector('.sidebar-toggle');
        var sidebar = document.querySelector('#sidebar');
        var checkbox = document.querySelector('#sidebar-checkbox');
        document.addEventListener('click', function(e) {
          var target = e.target;
          if(!checkbox.checked ||
             sidebar.contains(target) ||
             (target === checkbox || target === toggle)) return;
          checkbox.checked = false;
        }, false);
      })(document);
    </script>
        <script src="/aima-exercises/js/main.js"></script>
        <script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.3/jquery.min.js"></script>
        <script src="/aima-exercises/js/answer.js"></script>
        <script src="/aima-exercises/js/commsol.js"></script>
        <script src="/aima-exercises/js/forms.js"></script>
        <script src="/aima-exercises/js/crossref.js"></script>
        <script src="/aima-exercises/js/bookmark.js"></script>
        <script src="https://cdn.jsdelivr.net/npm/marked/marked.min.js"></script>
  </body>
</html>


<|start_filename|>public/css/style.css<|end_filename|>
.active-pink-2 input[type=text]:focus:not([readonly]) {
  border-bottom: 1px solid #f48fb1;
  box-shadow: 0 1px 0 0 #f48fb1;
}
.active-pink input[type=text] {
  border-bottom: 1px solid #f48fb1;
  box-shadow: 0 1px 0 0 #f48fb1;
}
.active-purple-2 input[type=text]:focus:not([readonly]) {
  border-bottom: 1px solid #ce93d8;
  box-shadow: 0 1px 0 0 #ce93d8;
}
.active-purple input[type=text] {
  border-bottom: 1px solid #ce93d8;
  box-shadow: 0 1px 0 0 #ce93d8;
}
.active-cyan-2 input[type=text]:focus:not([readonly]) {
  border-bottom: 1px solid #4dd0e1;
  box-shadow: 0 1px 0 0 #4dd0e1;
}
.active-cyan input[type=text] {
  border-bottom: 1px solid #4dd0e1;
  box-shadow: 0 1px 0 0 #4dd0e1;
}
.active-cyan .fa, .active-cyan-2 .fa {
  color: #4dd0e1;
}
.active-purple .fa, .active-purple-2 .fa {
  color: #ce93d8;
}
.active-pink .fa, .active-pink-2 .fa {
  color: #f48fb1;
}
#hideandviewanswers {
display: none;
}
#hideandviewcommunitysolution {
display: none;
}
#hideandviewusersolution {
display: none;
}
ul {

  margin: 3px;
  list-style-position: outside;
  list-style-type: none;
  padding-bottom: 10px;
  padding-top: 5px;
}
li {

margin: 3px;
}
ul > li {
/*border-bottom: 3px solid black;*/
font-size: 80%;
}
li > ul > li {
  font-size: 90%;
  border: none;
  color: black;
}
ul > li > ul >li >ul >li {
border-top: 1px solid black;
border-top-color: #534A4A;
color: black;	;
padding-bottom:0px;
}

ul > li > ul > li > ul > li > li{
border: none;
}
ul:first-child ul > li  {
color: black;
}
/*#borderbottom {
border-bottom: 3px solid black;
padding-bottom: 2px;

}
#link{
width:80%;
}

#content{
padding-left:15px;
}

#content p{
border-bottom:1px solid black;
}*/
.hideit{
display:none;
}
.viewusersolution{
padding-top: 0px;
margin-top: 0px;
}

/*




//////////////////////////////////////////////////////////////////
[ FONT ]*/

@font-face {
font-family: Poppins-Regular;
src: url('../fonts/poppins/Poppins-Regular.ttf'); 
}

@font-face {
font-family: Poppins-Medium;
src: url('../fonts/poppins/Poppins-Medium.ttf'); 
}

@font-face {
font-family: Poppins-Bold;
src: url('../fonts/poppins/Poppins-Bold.ttf'); 
}

@font-face {
font-family: Poppins-SemiBold;
src: url('../fonts/poppins/Poppins-SemiBold.ttf'); 
}

/*//////////////////////////////////////////////////////////////////
[ RESTYLE TAG ]*/





/*---------------------------------------------*/


/*---------------------------------------------*/
h1,h2,h3,h4,h5,h6 {
margin: 0px;
}

p {
font-family: Poppins-Regular;
font-size: 20px;
line-height: 1.7;
color: #666666;
margin: 0px;
}

ul, li {
margin: 0px;
list-style-type: none;
font-size: 25px;
}


/*---------------------------------------------*/
input {
outline: none;
border: none;
}

textarea {
outline: none;
border: none;
}

textarea:focus, input:focus {
border-color: transparent !important;
}

input:focus::-webkit-input-placeholder { color:transparent; }
input:focus:-moz-placeholder { color:transparent; }
input:focus::-moz-placeholder { color:transparent; }
input:focus:-ms-input-placeholder { color:transparent; }

textarea:focus::-webkit-input-placeholder { color:transparent; }
textarea:focus:-moz-placeholder { color:transparent; }
textarea:focus::-moz-placeholder { color:transparent; }
textarea:focus:-ms-input-placeholder { color:transparent; }

input::-webkit-input-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}
input:-moz-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}
input::-moz-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}
input:-ms-input-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}

textarea::-webkit-input-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}
textarea:-moz-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}
textarea::-moz-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}
textarea:-ms-input-placeholder { 
font-family: Poppins-Medium;  
color: #555555;
}

/*---------------------------------------------*/
button {
outline: none !important;
border: none;
background: transparent;
}

button:hover {
cursor: pointer;
}

iframe {
border: none !important;
}


/*---------------------------------------------*/
.container {
max-width: 1200px;
}




/*//////////////////////////////////////////////////////////////////
[ Contact ]*/

.container-contact100 {
width: 100%;  
min-height: 100vh;
display: -webkit-box;
display: -webkit-flex;
display: -moz-box;
display: -ms-flexbox;
display: flex;
flex-wrap: wrap;
justify-content: center;
align-items: center;
padding: 15px;
background: transparent;
position: relative;
z-index: 1;
}

.contact100-map {
position: absolute;
z-index: -2;
width: 100%;
height: 100%;
top: 0;
left: 0;
}

.wrap-contact100 {
width: 1170px;
background: #fff;
border-radius: 10px;
padding: 82px 180px 33px 180px;
position: relative;
display: none;
}

.show-wrap-contact100 {
visibility: visible;
opacity: 1;
}


/*==================================================================
[ Form ]*/

.contact100-form {
width: 100%;
display: -webkit-box;
display: -webkit-flex;
display: -moz-box;
display: -ms-flexbox;
display: flex;
flex-wrap: wrap;
justify-content: space-between;
padding-bottom: 68px;

}

.contact100-form-title {
display: block;
width: 100%;
font-family: Poppins-Bold;
font-size: 39px;
color: #333333;
line-height: 1.2;
text-align: left;
padding-bottom: 44px;
}



/*------------------------------------------------------------------
[ Input ]*/

.wrap-input100 {
width: 100%;
position: relative;
border-bottom: 2px solid #d9d9d9;
padding-bottom: 13px;
margin-bottom: 65px;
}

.rs1-wrap-input100 {
width: calc((100% - 30px) / 2);
}

.label-input100 {
font-family: Poppins-Regular;
font-size: 20px;
color: #220101;
line-height: 1.5;
padding-left: 5px;
}

.input100 {
display: block;
width: 100%;
background: transparent;
font-family: Poppins-SemiBold;
font-size: 18px;
color: #555555;
line-height: 1.2;
padding: 0 5px;
}

.focus-input100 {
position: absolute;
display: block;
width: 100%;
height: 100%;
top: 0;
left: 0;
pointer-events: none;
}

.focus-input100::before {
content: "";
display: block;
position: absolute;
bottom: -2px;
left: 0;
width: 0;
height: 2px;

-webkit-transition: all 0.4s;
-o-transition: all 0.4s;
-moz-transition: all 0.4s;
transition: all 0.4s;

background: #ff4b5a;
}


/*---------------------------------------------*/
input.input100 {
height: 40px;
}


textarea.input100 {
min-height: 110px;
padding-top: 9px;
padding-bottom: 13px;
}


.input100:focus + .focus-input100::before {
width: 100%;
}

.has-val.input100 + .focus-input100::before {
width: 100%;
}


/*------------------------------------------------------------------
[ Button ]*/
.container-contact100-form-btn {
width: 100%;
display: -webkit-box;
display: -webkit-flex;
display: -moz-box;
display: -ms-flexbox;
display: flex;
flex-wrap: wrap;
margin-top: -25px;
}

.contact100-form-btn {
display: -webkit-box;
display: -webkit-flex;
display: -moz-box;
display: -ms-flexbox;
display: flex;
justify-content: center;
align-items: center;
padding: 0 20px;
min-width: 160px;
height: 50px;
background-color: #2467be;
border-radius: 25px;

font-family: Poppins-Medium;
font-size: 16px;
color: #fff;
line-height: 1.2;

-webkit-transition: all 0.4s;
-o-transition: all 0.4s;
-moz-transition: all 0.4s;
transition: all 0.4s;

box-shadow: 0 10px 30px 0px rgba(130, 181, 240, 0.5);
-moz-box-shadow: 0 10px 30px 0px rgba(130, 181, 240, 0.5);
-webkit-box-shadow: 0 10px 30px 0px rgba(130, 181, 240, 0.5);
-o-box-shadow: 0 10px 30px 0px rgba(130, 181, 240, 0.5);
-ms-box-shadow: 0 10px 30px 0px rgba(130, 181, 240, 0.5);
}

.contact100-form-btn i {
-webkit-transition: all 0.4s;
-o-transition: all 0.4s;
-moz-transition: all 0.4s;
transition: all 0.4s;
}

.contact100-form-btn:hover {
background-color: #333333;
box-shadow: 0 10px 30px 0px rgba(51, 51, 51, 0.5);
-moz-box-shadow: 0 10px 30px 0px rgba(51, 51, 51, 0.5);
-webkit-box-shadow: 0 10px 30px 0px rgba(51, 51, 51, 0.5);
-o-box-shadow: 0 10px 30px 0px rgba(51, 51, 51, 0.5);
-ms-box-shadow: 0 10px 30px 0px rgba(51, 51, 51, 0.5);
}

.contact100-form-btn:hover i {
-webkit-transform: translateX(10px);
-moz-transform: translateX(10px);
-ms-transform: translateX(10px);
-o-transform: translateX(10px);
transform: translateX(10px);
}


/*------------------------------------------------------------------
[ Responsive ]*/

@media (max-width: 992px) {
.wrap-contact100 {
  padding: 82px 80px 33px 80px;
}
}

@media (max-width: 768px) {
.rs1-wrap-input100 {
  width: 100%;
}
}

@media (max-width: 576px) {
.wrap-contact100 {
  padding: 82px 15px 33px 15px;
}
}


/*------------------------------------------------------------------
[ Alert validate ]*/

.validate-input {
position: relative;
}

.alert-validate::before {
content: attr(data-validate);
position: absolute;
max-width: 70%;
background-color: #fff;
border: 1px solid #c80000;
border-radius: 2px;
padding: 4px 25px 4px 10px;
top: 58%;
-webkit-transform: translateY(-50%);
-moz-transform: translateY(-50%);
-ms-transform: translateY(-50%);
-o-transform: translateY(-50%);
transform: translateY(-50%);
right: 2px;
pointer-events: none;

font-family: Poppins-Medium;
color: #c80000;
font-size: 13px;
line-height: 1.4;
text-align: left;

visibility: hidden;
opacity: 0;

-webkit-transition: opacity 0.4s;
-o-transition: opacity 0.4s;
-moz-transition: opacity 0.4s;
transition: opacity 0.4s;
}

.alert-validate::after {
content: "\f06a";
font-family: FontAwesome;
display: block;
position: absolute;
color: #c80000;
font-size: 16px;
top: 58%;
-webkit-transform: translateY(-50%);
-moz-transform: translateY(-50%);
-ms-transform: translateY(-50%);
-o-transform: translateY(-50%);
transform: translateY(-50%);
right: 8px;
}

.alert-validate:hover:before {
visibility: visible;
opacity: 1;
}

@media (max-width: 992px) {
.alert-validate::before {
  visibility: visible;
  opacity: 1;
}
}


/*==================================================================
[ Contact more ]*/

.contact100-more {
font-family: Poppins-Regular;
font-size: 14px;
color: #999999;
line-height: 1.5;
}

.contact100-more-highlight {
color: #ff4b5a;
}

/*==================================================================
[ Button hide form ]*/

.contact100-btn-hide {
color: #333333;
font-size: 14px;

position: absolute;
display: -webkit-box;
display: -webkit-flex;
display: -moz-box;
display: -ms-flexbox;
display: flex;
justify-content: center;
align-items: center;
width: 30px;
height: 30px;
background-color: #fff;
border: 1px solid #ececec;
border-radius: 50%;
top: -15px;
right: -15px;

-webkit-transition: all 0.4s;
-o-transition: all 0.4s;
-moz-transition: all 0.4s;
transition: all 0.4s;
}

.contact100-btn-hide:hover {
background-color: #333333;
color: #fff;
}


/*==================================================================
[ Button show form ]*/

.contact100-btn-show {
color: #fff;
font-size: 39px;

position: fixed;
z-index: -1;
display: -webkit-box;
display: -webkit-flex;
display: -moz-box;
display: -ms-flexbox;
display: flex;
justify-content: center;
align-items: center;
width: 120px;
height: 120px;
border-radius: 50%;
top: 50%;
left: 50%;
-webkit-transform: translate(-50%, -50%);
-moz-transform: translate(-50%, -50%);
-ms-transform: translate(-50%, -50%);
-o-transform: translate(-50%, -50%);
transform: translate(-50%, -50%);
}

.contact100-btn-show::before {
content: "";
display: block;
position: absolute;
z-index: -2;
width: 100%;
height: 100%;
background-color: #ff4b5a;
border-radius: 50%;

top: 0;
left: 0;

box-shadow: 0 10px 30px 0px rgba(255, 75, 90, 0.5);
-moz-box-shadow: 0 10px 30px 0px rgba(255, 75, 90, 0.5);
-webkit-box-shadow: 0 10px 30px 0px rgba(255, 75, 90, 0.5);
-o-box-shadow: 0 10px 30px 0px rgba(255, 75, 90, 0.5);
-ms-box-shadow: 0 10px 30px 0px rgba(255, 75, 90, 0.5);

-webkit-transition: all 0.4s;
-o-transition: all 0.4s;
-moz-transition: all 0.4s;
transition: all 0.4s;

-webkit-animation: beatbtn 0.9s ease-in-out infinite;
animation: beatbtn 0.9s ease-in-out infinite;
}


@keyframes beatbtn {
0% {
  background-color: rgba(255, 75, 90, 1);
  transform-origin: center;
  -webkit-transform: scale(1);
  -moz-transform: scale(1);
  -ms-transform: scale(1);
  -o-transform: scale(1);
  transform: scale(1);
}

50% {
  background-color: rgba(255, 75, 90, 0.8);
  transform-origin: center;
  -webkit-transform: scale(1.1);
  -moz-transform: scale(1.1);
  -ms-transform: scale(1.1);
  -o-transform: scale(1.1);
  transform: scale(1.1);
}
}

.contact100-form-btn{
margin-left: 40%;
}

#answeridstyle{
border-bottom: 1px solid rgb(90, 88, 88 , 0.3);
margin-top: 0px;

margin-bottom: 0px;
padding-top: 0px;

}

#answeridstyle p:nth-of-type(1){
color: #070101;

padding: 15px;
font-family: Arial,"Helvetica Neue",Helvetica,sans-serif;
font-weight: bold;
}
hr {
display: none;
}



#answeridstyle p:nth-of-type(2){
font-family: Arial,"Helvetica Neue",Helvetica,sans-serif;
font-size: 17px;
color: #070101;
margin-left: 10%;


}
#answeridstyle hr:last-of-type {
display: none;
}

.breadcrumbb{
  background-color: transparent;
  display: flex;
  flex-wrap: wrap;
  padding: .75rem 1rem;
  margin-bottom: 0px;
  list-style: none;
  margin-bottom: 0%;
  margin-top: 5px;

  
  
}
.breadcrumb-text{
  text-transform: uppercase;
}



#bbreadcrumb{
  list-style-type: none;
  display: inline-block;
 }
 
 #bbreadcrumb li{
  float: left;
 }
 
 #bbreadcrumb li a{
  color: #fff;
  display: block;
  background: #000000;
  text-decoration: none;
  position: relative;
  height: 40px;
  line-height: 40px;
  padding: 0 10px 0 5px;
  text-align: center;
  margin-right: 23px;
  margin-bottom: 0px;
 }
 
 #bbreadcrumb li:nth-child(even) a:before{
  border-left-color: transparent;
 }
 
 #bbreadcrumb li:first-child a{
  padding-left: 15px;
  border-radius: 4px 0 0 4px;
 }
 
 #bbreadcrumb li:first-child a:before{
  border: none;
 }
 
 #bbreadcrumb li:last-child a{
  padding-right: 15px;
  border-radius: 0 4px 4px 0;
 }
 
 #bbreadcrumb li:last-child a:after{
  border: none;
 }
 
 #bbreadcrumb li a:before, #bbreadcrumb li a:after{
  content: "";
  position: absolute;
  top: 0;
  border: 0 solid #000000;
  border-width: 20px 10px;
  width: 0;
  height: 0;
 }
 
 #bbreadcrumb li a:before{
  left: -20px;
  border-left-color: transparent;
 }
 
 #bbreadcrumb li a:after{
  left: 100%;
  border-color: transparent;
  border-left-color: #000000;
 }
 
 #bbreadcrumb li a:hover{
  background: #362cc9;
 }
 
 #bbreadcrumb li a:hover:before{
  border-color: #362cc9;
  border-left-color: transparent;
 }
 
 #bbreadcrumb li a:hover:after{
  border-left-color: #362cc9;
 }

.search_container ul li{
  border: 1px solid #c4c4c4;
  margin: 10px 0;
  padding: 10px;
  border-radius: 5px;
}
.search_container ul li:hover{
  background-color: #0000001a;
}
#hiddden{
  display: none;
}