Define in your own words: (a) intelligence, (b) artificial intelligence, (c) agent, (d) rationality, (e) logical reasoning.
Read Turing’s original paper on AI @Turing:1950. In the paper, he discusses several objections to his proposed enterprise and his test for intelligence. Which objections still carry weight? Are his refutations valid? Can you think of new objections arising from developments since he wrote the paper? In the paper, he predicts that, by the year 2000, a computer will have a 30% chance of passing a five-minute Turing Test with an unskilled interrogator. What chance do you think a computer would have today? In another 50 years?
Every year the Loebner Prize is awarded to the program that comes closest to passing a version of the Turing Test. Research and report on the latest winner of the Loebner prize. What techniques does it use? How does it advance the state of the art in AI?
Are reflex actions (such as flinching from a hot stove) rational? Are they intelligent?
There are well-known classes of problems that are intractably difficult for computers, and other classes that are provably undecidable. Does this mean that AI is impossible?
Suppose we extend Evans’s SYSTEM program so that it can score 200 on a standard IQ test. Would we then have a program more intelligent than a human? Explain.
The neural structure of the sea slug Aplysis has been widely studied (first by Nobel Laureate Eric Kandel) because it has only about 20,000 neurons, most of them large and easily manipulated. Assuming that the cycle time for an Aplysis neuron is roughly the same as for a human neuron, how does the computational power, in terms of memory updates per second, compare with the high-end computer described in (Figure computer-brain-table)?
How could introspection—reporting on one’s inner thoughts—be inaccurate? Could I be wrong about what I’m thinking? Discuss.
To what extent are the following computer systems instances of
artificial intelligence:
- Supermarket bar code scanners.
- Web search engines.
- Voice-activated telephone menus.
- Internet routing algorithms that respond dynamically to the state of
the network.
To what extent are the following computer systems instances of
artificial intelligence:
- Supermarket bar code scanners.
- Voice-activated telephone menus.
- Spelling and grammar correction features in Microsoft Word.
- Internet routing algorithms that respond dynamically to the state of the network.
Many of the computational models of cognitive activities that have been proposed involve quite complex mathematical operations, such as convolving an image with a Gaussian or finding a minimum of the entropy function. Most humans (and certainly all animals) never learn this kind of mathematics at all, almost no one learns it before college, and almost no one can compute the convolution of a function with a Gaussian in their head. What sense does it make to say that the “vision system” is doing this kind of mathematics, whereas the actual person has no idea how to do it?
Some authors have claimed that perception and motor skills are the most important part of intelligence, and that “higher level” capacities are necessarily parasitic—simple add-ons to these underlying facilities.  Do you think that AI’s traditional focus on higher-level cognitive abilities is misplaced?
Why would evolution tend to result in systems that act rationally? What goals are such systems designed to achieve?
Is AI a science, or is it engineering? Or neither or both? Explain.
“Surely computers cannot be intelligent—they can do only what their programmers tell them.” Is the latter statement true, and does it imply the former?
“Surely animals cannot be intelligent—they can do only what their genes tell them.” Is the latter statement true, and does it imply the former?
“Surely animals, humans, and computers cannot be intelligent—they can do only what their constituent atoms are told to do by the laws of physics.” Is the latter statement true, and does it imply the former?
Examine the AI literature to discover whether the following tasks can currently be solved by computers: - Playing a decent game of table tennis (Ping-Pong). - Driving in the center of Cairo, Egypt. - Driving in Victorville, California. - Buying a week’s worth of groceries at the market. - Buying a week’s worth of groceries on the Web. - Playing a decent game of bridge at a competitive level. - Discovering and proving new mathematical theorems. - Writing an intentionally funny story. - Giving competent legal advice in a specialized area of law. - Translating spoken English into spoken Swedish in real time. - Performing a complex surgical operation.
For the currently infeasible tasks, try to find out what the difficulties are and predict when, if ever, they will be overcome.
Various subfields of AI have held contests by defining a standard task and inviting researchers to do their best. Examples include the DARPA Grand Challenge for robotic cars, the International Planning Competition, the Robocup robotic soccer league, the TREC information retrieval event, and contests in machine translation and speech recognition. Investigate five of these contests and describe the progress made over the years. To what degree have the contests advanced the state of the art in AI? To what degree do they hurt the field by drawing energy away from new ideas?
Suppose that the performance measure is concerned with just the first $T$ time steps of the environment and ignores everything thereafter. Show that a rational agent’s action may depend not just on the state of the environment but also on the time step it has reached.
Let us examine the rationality of various
vacuum-cleaner agent functions.
1. Show that the simple vacuum-cleaner agent function described in
Figure vacuum-agent-function-table is indeed
rational under the assumptions listed on page vacuum-rationality-page
2. Describe a rational agent function for the case in which each
movement costs one point. Does the corresponding agent program
require internal state?
3. Discuss possible agent designs for the cases in which clean squares
can become dirty and the geography of the environment is unknown.
Does it make sense for the agent to learn from its experience in
these cases? If so, what should it learn? If not, why not?
Write an essay on the relationship between evolution and one or more of autonomy, intelligence, and learning.
For each of the following assertions, say whether it is true or false
and support your answer with examples or counterexamples where
appropriate.
1. An agent that senses only partial information about the state cannot
be perfectly rational.
2. There exist task environments in which no pure reflex agent can
behave rationally.
3. There exists a task environment in which every agent is rational.
4. The input to an agent program is the same as the input to the
agent function.
5. Every agent function is implementable by some
program/machine combination.
6. Suppose an agent selects its action uniformly at random from the set
of possible actions. There exists a deterministic task environment
in which this agent is rational.
7. It is possible for a given agent to be perfectly rational in two
distinct task environments.
8. Every agent is rational in an unobservable environment.
9. A perfectly rational poker-playing agent never loses.
Exercise 2.4 (PEAS-exercise)
For each of the following activities, give a PEAS
description of the task environment and characterize it in terms of the
properties listed in Section env-properties-subsection
- Playing soccer.
- Exploring the subsurface oceans of Titan.
- Shopping for used AI books on the Internet.
- Playing a tennis match.
- Practicing tennis against a wall.
- Performing a high jump.
- Knitting a sweater.
- Bidding on an item at an auction.
For each of the following activities, give a PEAS
description of the task environment and characterize it in terms of the
properties listed in Section env-properties-subsection
- Performing a gymnastics floor routine.
- Exploring the subsurface oceans of Titan.
- Playing soccer.
- Shopping for used AI books on the Internet.
- Practicing tennis against a wall.
- Performing a high jump.
- Bidding on an item at an auction.
Define in your own words the following terms: agent, agent function, agent program, rationality, autonomy, reflex agent, model-based agent, goal-based agent, utility-based agent, learning agent.
This exercise explores the differences between
agent functions and agent programs.
1. Can there be more than one agent program that implements a given
agent function? Give an example, or show why one is not possible.
2. Are there agent functions that cannot be implemented by any agent
program?
3. Given a fixed machine architecture, does each agent program
implement exactly one agent function?
4. Given an architecture with $n$ bits of storage, how many different
possible agent programs are there?
5. Suppose we keep the agent program fixed but speed up the machine by
a factor of two. Does that change the agent function?
Write pseudocode agent programs for the goal-based and utility-based agents.
Consider a simple thermostat that turns on a furnace when the temperature is at least 3 degrees below the setting, and turns off a furnace when the temperature is at least 3 degrees above the setting. Is a thermostat an instance of a simple reflex agent, a model-based reflex agent, or a goal-based agent?
Implement a performance-measuring environment simulator for the vacuum-cleaner world depicted in Figure vacuum-world-figure and specified on page vacuum-rationality-page. Your implementation should be modular so that the sensors, actuators, and environment characteristics (size, shape, dirt placement, etc.) can be changed easily. (Note: for some choices of programming language and operating system there are already implementations in the online code repository.)
Implement a simple reflex agent for the vacuum environment in Exercise vacuum-start-exercise. Run the environment with this agent for all possible initial dirt configurations and agent locations. Record the performance score for each configuration and the overall average score.
Consider a modified version of the
vacuum environment in Exercise vacuum-start-exercise,
in which the agent is penalized one point for each movement.
1. Can a simple reflex agent be perfectly rational for this
environment? Explain.
2. What about a reflex agent with state? Design such an agent.
3. How do your answers to 1 and 2
change if the agent’s percepts give it the clean/dirty status of
every square in the environment?
Consider a modified version of the
vacuum environment in Exercise vacuum-start-exercise,
in which the geography of the environment—its extent, boundaries, and
obstacles—is unknown, as is the initial dirt configuration. (The agent
can go Up and Down as well as Left and Right.)
1. Can a simple reflex agent be perfectly rational for this
environment? Explain.
2. Can a simple reflex agent with a randomized agent
function outperform a simple reflex agent? Design such an agent and
measure its performance on several environments.
3. Can you design an environment in which your randomized agent will
perform poorly? Show your results.
4. Can a reflex agent with state outperform a simple reflex agent?
Design such an agent and measure its performance on several
environments. Can you design a rational agent of this type?
Repeat Exercise vacuum-unknown-geog-exercise for the case in which the location sensor is replaced with a “bump” sensor that detects the agent’s attempts to move into an obstacle or to cross the boundaries of the environment. Suppose the bump sensor stops working; how should the agent behave?
The vacuum environments in the preceding
exercises have all been deterministic. Discuss possible agent programs
for each of the following stochastic versions:
1. Murphy’s law: twenty-five percent of the time, the Suck action
fails to clean the floor if it is dirty and deposits dirt onto the
floor if the floor is clean. How is your agent program affected if
the dirt sensor gives the wrong answer 10% of the time?
2. Small children: At each time step, each clean square has a 10%
chance of becoming dirty. Can you come up with a rational agent
design for this case?
Explain why problem formulation must follow goal formulation.
Give a complete problem formulation for each of the following problems.
Choose a formulation that is precise enough to be implemented.
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.
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.
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.
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.
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.
1. Formulate this problem. How large is the state space?
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?
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?
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.
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.
1. Formulate this problem in the straightforward way. Compute the size
of the state space.
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?
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.
4. How many solutions does this problem have?
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)?
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.
1. Write a detailed formulation for this search problem. (You will find
it helpful to define some formal notation here.)
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$.
3. Are there completely connected maps for which no solution exists?
4. Are there maps in which all solutions require one friend to visit
the same city twice?
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. (Hint: See @Berlekamp+al:1982.) Devise a procedure to decide which set a given state is in, and explain why this is useful for generating random states.
Consider the $n$-queens problem using the “efficient” incremental formulation given on page nqueens-page. Explain why the state space has at least $\sqrt[3]{n!}$ states and estimate the largest $n$ for which exhaustive exploration is feasible. (Hint: Derive a lower bound on the branching factor by considering the maximum number of squares that a queen can attack in any column.)
Give a complete problem formulation for each of the following. Choose a
formulation that is precise enough to be implemented.
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.
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.
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.
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.
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.
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?
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?
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.
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.
On page non-negative-g, we said that we would not consider problems
with negative path costs. In this exercise, we explore this decision in
more depth.
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.
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.
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?
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.
5. Can you think of a real domain in which step costs are such as to
cause looping?
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 @Amarel:1968.
1. Formulate the problem precisely, making only those distinctions
necessary to ensure a valid solution. Draw a diagram of the complete
state space.
2. Implement and solve the problem optimally using an appropriate
search algorithm. Is it a good idea to check for repeated states?
3. Why do you think people have a hard time solving this puzzle, given
that the state space is so simple?
Define in your own words the following terms: state, state space, search tree, search node, goal, action, transition model, and branching factor.
What’s the difference between a world state, a state description, and a search node? Why is this distinction useful?
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?
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.)
Prove that satisfies the graph separation property illustrated in . (Hint: 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.
Which of the following are true and which are false? Explain your
answers.
1. Depth-first search always expands at least as many nodes as A search
with an admissible heuristic.
2. $h(n)=0$ is an admissible heuristic for the 8-puzzle.
3. A is of no use in robotics because percepts, states, and actions
are continuous.
4. Breadth-first search is complete even if zero step costs
are allowed.
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.
Consider a state space where the start state is number 1 and each state
$k$ has two successors: numbers $2k$ and $2k+1$.
1. Draw the portion of the state space for states 1 to 15.
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.
3. How well would bidirectional search work on this problem? What is
the branching factor in each direction of the bidirectional search?
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?
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?
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.
1. Suppose that the pieces fit together exactly with no
slack. Give a precise formulation of the task as a search problem.
2. Identify a suitable uninformed search algorithm for this task and
explain your choice.
3. Explain why removing any one of the “fork” pieces makes the
problem unsolvable.
4. Give an upper bound on the total size of the state space defined by
your formulation. (Hint: 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.)
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.
On page iterative-lengthening-page,
we mentioned iterative lengthening search,
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.
1. Show that this algorithm is optimal for general path costs.
2. Consider a uniform tree with branching factor $b$, solution depth
$d$, and unit step costs. How many iterations will iterative
lengthening require?
3. Now consider step costs drawn from the continuous range
$[\epsilon,1]$, where $0 < \epsilon < 1$. How many iterations are
required in the worst case?
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.
Describe a state space in which iterative deepening search performs much worse than depth-first search (for example, $O(n^{2})$ vs. $O(n)$).
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?
Consider the vacuum-world problem defined in .
1. Which of the algorithms defined in this chapter would be appropriate
for this problem? Should the algorithm use tree search or graph
search?
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.
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.
4.
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$?
Prove each of the following statements,
or give a counterexample:
1. Breadth-first search is a special case of uniform-cost search.
2. Depth-first search is a special case of best-first tree search.
3. Uniform-cost search is a special case of A search.
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?
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.
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?
Devise a state space in which A using returns a suboptimal solution with an $h(n)$ function that is admissible but inconsistent.
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$.
The heuristic path algorithm @Pohl:1977 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$?
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)$.
1. What is the branching factor $b$ in this state space?
2. How many distinct states are there at depth $k$ (for $k>0$)?
3. What is the maximum number of nodes expanded by breadth-first tree
search?
4. What is the maximum number of nodes expanded by breadth-first graph
search?
5. Is $h = |u-x| + |v-y|$ an admissible heuristic for a state at
$(u,v)$? Explain.
6. How many nodes are expanded by A graph search using $h$?
7. Does $h$ remain admissible if some links are removed?
8. Does $h$ remain admissible if some links are added between
nonadjacent states?
$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.
1. Calculate the size of the state space as a function of $n$.
2. Calculate the branching factor as a function of $n$.
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.
4. Which of the following heuristics are admissible for the problem of
moving all $n$ vehicles to their destinations? Explain.
1. $\sum_{i= 1}^{n} h_i$.
2. $\max\{h_1,\ldots,h_n\}$.
3. $\min\{h_1,\ldots,h_n\}$.
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 up
to $k$ knights simultaneously. We would like to complete the
maneuver in the smallest number of actions.
1. What is the maximum branching factor in this state space, expressed
as a function of $k$?
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?
1. $\min\{h_1,\ldots,h_k\}$.
2. $\max\{h_1,\ldots,h_k\}$.
3. $\sum_{i= 1}^{k} h_i$.
3. Repeat (b) for the case where you are allowed to move only one
knight at a time.
We saw on page I-to-F 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?
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$.
consistent-heuristic-exercise Prove that if a heuristic is consistent, it must be admissible. Construct an admissible heuristic that is not consistent.
tsp-mst-exerciseThe 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.
1. Show how this heuristic can be derived from a relaxed version of
the TSP.
2. Show that the MST heuristic dominates straight-line distance.
3. Write a problem generator for instances of the TSP where cities are
represented by random points in the unit square.
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.
On page Gaschnig-h-page , 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 Gaschnig's heuristic @Gaschnig:1979. 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.
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, @Nilsson:1971, @Mostow+Prieditis:1989, and @Hansson+al:1992. Test these claims by implementing the heuristics and comparing the performance of the resulting algorithms.
Give the name of the algorithm that results from each of the following
special cases:
1. Local beam search with $k = 1$.
2. Local beam search with one initial state and no limit on the number
of states retained.
3. Simulated annealing with $T = 0$ at all times (and omitting the
termination test).
4. Simulated annealing with $T=\infty$ at all times.
5. Genetic algorithm with population size $N = 1$.
Exercise brio-exercise considers the problem of building railway tracks under the assumption that pieces fit exactly with no slack. Now consider the real problem, in which pieces don’t fit exactly but allow for up to 10 degrees of rotation to either side of the “proper” alignment. Explain how to formulate the problem so it could be solved by simulated annealing.
In this exercise, we explore the use of local search methods to solve
TSPs of the type defined in Exercise tsp-mst-exercise
1. Implement and test a hill-climbing method to solve TSPs. Compare the
results with optimal solutions obtained from the A* algorithm with
the MST heuristic (Exercise tsp-mst-exercise)
2. Repeat part (a) using a genetic algorithm instead of hill climbing.
You may want to consult @Larranaga+al:1999 for some suggestions for representations.
Generate a large number of 8-puzzle and 8-queens instances and solve them (where possible) by hill climbing (steepest-ascent and first-choice variants), hill climbing with random restart, and simulated annealing. Measure the search cost and percentage of solved problems and graph these against the optimal solution cost. Comment on your results.
The **And-Or-Graph-Search** algorithm in Figure and-or-graph-search-algorithm checks for repeated states only on the path from the root to the current state. Suppose that, in addition, the algorithm were to store *every* visited state and check against that list. (See in Figure breadth-first-search-algorithm for an example.) Determine the information that should be stored and how the algorithm should use that information when a repeated state is found. (*Hint*: You will need to distinguish at least between states for which a successful subplan was constructed previously and states for which no subplan could be found.) Explain how to use labels, as defined in Section cyclic-plan-section, to avoid having multiple copies of subplans.
Explain precisely how to modify the **And-Or-Graph-Search** algorithm to generate a cyclic plan if no acyclic plan exists. You will need to deal with three issues: labeling the plan steps so that a cyclic plan can point back to an earlier part of the plan, modifying **Or-Search** so that it continues to look for acyclic plans after finding a cyclic plan, and augmenting the plan representation to indicate whether a plan is cyclic. Show how your algorithm works on (a) the slippery vacuum world, and (b) the slippery, erratic vacuum world. You might wish to use a computer implementation to check your results.
In Section conformant-section we introduced belief states to solve sensorless search problems. A sequence of actions solves a sensorless problem if it maps every physical state in the initial belief state $b$ to a goal state. Suppose the agent knows $h^\*(s)$, the true optimal cost of solving the physical state $s$ in the fully observable problem, for every state $s$ in $b$. Find an admissible heuristic $h(b)$ for the sensorless problem in terms of these costs, and prove its admissibilty. Comment on the accuracy of this heuristic on the sensorless vacuum problem of Figure vacuum2-sets-figure. How well does A* perform?
This exercise explores
subset–superset relations between belief states in sensorless or
partially observable environments.
1. Prove that if an action sequence is a solution for a belief state
$b$, it is also a solution for any subset of $b$. Can anything be
said about supersets of $b$?
2. Explain in detail how to modify graph search for sensorless problems
to take advantage of your answers in (a).
3. Explain in detail how to modify and–or search for
partially observable problems, beyond the modifications you describe
in (b).
On page multivalued-sensorless-page it was assumed that a given action would have the same cost when executed in any physical state within a given belief state. (This leads to a belief-state search problem with well-defined step costs.) Now consider what happens when the assumption does not hold. Does the notion of optimality still make sense in this context, or does it require modification? Consider also various possible definitions of the “cost” of executing an action in a belief state; for example, we could use the *minimum* of the physical costs; or the *maximum*; or a cost *interval* with the lower bound being the minimum cost and the upper bound being the maximum; or just keep the set of all possible costs for that action. For each of these, explore whether A* (with modifications if necessary) can return optimal solutions.
Consider the sensorless version of the erratic vacuum world. Draw the belief-state space reachable from the initial belief state $\{1,2,3,4,5,6,7,8\}$, and explain why the problem is unsolvable.
Consider the sensorless version of the erratic vacuum world. Draw the belief-state space reachable from the initial belief state $\{ 1,3,5,7 \}$, and explain why the problem is unsolvable.
We can turn the navigation problem in
Exercise path-planning-exercis into an environment as
follows:
- The percept will be a list of the positions, *relative to the
agent*, of the visible vertices. The percept does
*not* include the position of the robot! The robot must
learn its own position from the map; for now, you can assume that
each location has a different “view.”
- Each action will be a vector describing a straight-line path
to follow. If the path is unobstructed, the action succeeds;
otherwise, the robot stops at the point where its path first
intersects an obstacle. If the agent returns a zero motion vector
and is at the goal (which is fixed and known), then the environment
teleports the agent to a *random location* (not inside
an obstacle).
- The performance measure charges the agent 1 point for each unit of
distance traversed and awards 1000 points each time the goal
is reached.
1. Implement this environment and a problem-solving agent for it. After
each teleportation, the agent will need to formulate a new problem,
which will involve discovering its current location.
2. Document your agent’s performance (by having the agent generate
suitable commentary as it moves around) and report its performance
over 100 episodes.
3. Modify the environment so that 30% of the time the agent ends up at
an unintended destination (chosen randomly from the other visible
vertices if any; otherwise, no move at all). This is a crude model
of the motion errors of a real robot. Modify the agent so that when
such an error is detected, it finds out where it is and then
constructs a plan to get back to where it was and resume the
old plan. Remember that sometimes getting back to where it was might
also fail! Show an example of the agent successfully overcoming two
successive motion errors and still reaching the goal.
4. Now try two different recovery schemes after an error: (1) head for
the closest vertex on the original route; and (2) replan a route to
the goal from the new location. Compare the performance of the three
recovery schemes. Would the inclusion of search costs affect the
comparison?
5. Now suppose that there are locations from which the view
is identical. (For example, suppose the world is a grid with
square obstacles.) What kind of problem does the agent now face?
What do solutions look like?
Suppose that an agent is in a $3 \times 3$
maze environment like the one shown in
Figure maze-3x3-figure. The agent knows that its
initial location is (1,1), that the goal is at (3,3), and that the
actions *Up*, *Down*, *Left*, *Right* have their usual
effects unless blocked by a wall. The agent does *not* know
where the internal walls are. In any given state, the agent perceives
the set of legal actions; it can also tell whether the state is one it
has visited before.
1. Explain how this online search problem can be viewed as an offline
search in belief-state space, where the initial belief state
includes all possible environment configurations. How large is the
initial belief state? How large is the space of belief states?
2. How many distinct percepts are possible in the initial state?
3. Describe the first few branches of a contingency plan for this
problem.
Notice that this contingency plan is a solution for *every
possible environment* fitting the given description. Therefore,
interleaving of search and execution is not strictly necessary even in
unknown environments.
Suppose that an agent is in a $3 \times 3$
maze environment like the one shown in
Figure maze-3x3-figure. The agent knows that its
initial location is (3,3), that the goal is at (1,1), and that the four
actions *Up*, *Down*, *Left*, *Right* have their usual
effects unless blocked by a wall. The agent does *not* know
where the internal walls are. In any given state, the agent perceives
the set of legal actions; it can also tell whether the state is one it
has visited before or is a new state.
1. Explain how this online search problem can be viewed as an offline
search in belief-state space, where the initial belief state
includes all possible environment configurations. How large is the
initial belief state? How large is the space of belief states?
2. How many distinct percepts are possible in the initial state?
3. Describe the first few branches of a contingency plan for this
problem.
Notice that this contingency plan is a solution for *every
possible environment* fitting the given description. Therefore,
interleaving of search and execution is not strictly necessary even in
unknown environments.
In this exercise, we examine hill climbing
in the context of robot navigation, using the environment in
Figure geometric-scene-figure as an example.
1. Repeat Exercise path-planning-agent-exercise using
hill climbing. Does your agent ever get stuck in a local minimum? Is
it *possible* for it to get stuck with convex
obstacles?
2. Construct a nonconvex polygonal environment in which the agent
gets stuck.
3. Modify the hill-climbing algorithm so that, instead of doing a
depth-1 search to decide where to go next, it does a
depth-$k$ search. It should find the best $k$-step path and do one
step along it, and then repeat the process.
4. Is there some $k$ for which the new algorithm is guaranteed to
escape from local minima?
5. Explain how LRTA enables the agent to escape from local minima in
this case.
Like DFS, online DFS is incomplete for reversible state spaces with infinite paths. For example, suppose that states are points on the infinite two-dimensional grid and actions are unit vectors $(1,0)$, $(0,1)$, $(-1,0)$, $(0,-1)$, tried in that order. Show that online DFS starting at $(0,0)$ will not reach $(1,-1)$. Suppose the agent can observe, in addition to its current state, all successor states and the actions that would lead to them. Write an algorithm that is complete even for bidirected state spaces with infinite paths. What states does it visit in reaching $(1,-1)$?
Relate the time complexity of LRTA* to its space complexity.
Suppose you have an oracle, $OM(s)$, that correctly predicts the opponent’s move in any state. Using this, formulate the definition of a game as a (single-agent) search problem. Describe an algorithm for finding the optimal move.
Consider the problem of solving two 8-puzzles.
1. Give a complete problem formulation in the style of
Chapter search-chapter.
2. How large is the reachable state space? Give an exact
numerical expression.
3. Suppose we make the problem adversarial as follows: the two players
take turns moving; a coin is flipped to determine the puzzle on
which to make a move in that turn; and the winner is the first to
solve one puzzle. Which algorithm can be used to choose a move in
this setting?
4. Does the game eventually end, given optimal play? Explain.
(a) A map where the cost of every edge is 1. Initially the pursuer $P$ is at
node b and the evader $E$ is at node d
(b) A partial game tree for this map.
Each node is labeled with the $P,E$ positions. $P$ moves first. Branches marked "?" have yet to be explored.
Imagine that, in Exercise \[two-friends-exercise\], one of
the friends wants to avoid the other. The problem then becomes a
two-player game. We assume now that the players take turns moving. The
game ends only when the players are on the same node; the terminal
payoff to the pursuer is minus the total time taken. (The evader “wins”
by never losing.) An example is shown in Figure.
pursuit-evasion-game-figure
1. Copy the game tree and mark the values of the terminal nodes.
2. Next to each internal node, write the strongest fact you can infer
about its value (a number, one or more inequalities such as
“$\geq 14$”, or a “?”).
3. Beneath each question mark, write the name of the node reached by
that branch.
4. Explain how a bound on the value of the nodes in (c) can be derived
from consideration of shortest-path lengths on the map, and derive
such bounds for these nodes. Remember the cost to get to each leaf
as well as the cost to solve it.
5. Now suppose that the tree as given, with the leaf bounds from (d),
is evaluated from left to right. Circle those “?” nodes that would
not need to be expanded further, given the bounds
from part (d), and cross out those that need not be considered
at all.
6. Can you prove anything in general about who wins the game on a map
that is a tree?
Describe and implement a real-time, multiplayer game-playing environment, where time is part of the environment state and players are given fixed time allocations.
Discuss how well the standard approach to game playing would apply to games such as tennis, pool, and croquet, which take place in a continuous physical state space.
Prove the following assertion: For every game tree, the utility obtained by max using minimax decisions against a suboptimal min will never be lower than the utility obtained playing against an optimal min. Can you come up with a game tree in which max can do still better using a suboptimal strategy against a suboptimal min? Player $A$ moves first. The two players take turns moving, and each player must move his token to an open adjacent space in either direction. If the opponent occupies an adjacent space, then a player may jump over the opponent to the next open space if any. (For example, if $A$ is on 3 and $B$ is on 2, then $A$ may move back to 1.) The game ends when one player reaches the opposite end of the board. If player $A$ reaches space 4 first, then the value of the game to $A$ is $+1$; if player $B$ reaches space 1 first, then the value of the game to $A$ is $-1$.
Consider the two-player game described in
Figure line-game4-figure
1. Draw the complete game tree, using the following conventions:
- Write each state as $(s_A,s_B)$, where $s_A$ and $s_B$ denote
the token locations.
- Put each terminal state in a square box and write its game value
in a circle.
- Put loop states (states that already appear on
the path to the root) in double square boxes. Since their value
is unclear, annotate each with a “?” in a circle.
2. Now mark each node with its backed-up minimax value (also in
a circle). Explain how you handled the “?” values and why.
3. Explain why the standard minimax algorithm would fail on this game
tree and briefly sketch how you might fix it, drawing on your answer
to (b). Does your modified algorithm give optimal decisions for all
games with loops?
4. This 4-square game can be generalized to $n$ squares for any
$n > 2$. Prove that $A$ wins if $n$ is even and loses if $n$ is odd.
This problem exercises the basic concepts of game playing, using
tic-tac-toe (noughts and crosses) as an example. We define
$X_n$ as the number of rows, columns, or diagonals with exactly $n$
$X$’s and no $O$’s. Similarly, $O_n$ is the number of rows, columns, or
diagonals with just $n$ $O$’s. The utility function assigns $+1$ to any
position with $X_3=1$ and $-1$ to any position with $O_3 = 1$. All other
terminal positions have utility 0. For nonterminal positions, we use a
linear evaluation function defined as ${Eval}(s) = 3X_2(s) + X_1(s) -
(3O_2(s) + O_1(s))$.
1. Approximately how many possible games of tic-tac-toe are there?
2. Show the whole game tree starting from an empty board down to depth
2 (i.e., one $X$ and one $O$ on the board), taking symmetry
into account.
3. Mark on your tree the evaluations of all the positions at depth 2.
4. Using the minimax algorithm, mark on your tree the backed-up values
for the positions at depths 1 and 0, and use those values to choose
the best starting move.
5. Circle the nodes at depth 2 that would not be
evaluated if alpha–beta pruning were applied, assuming the nodes are
generated in the optimal order for alpha–beta pruning.
Consider the family of generalized tic-tac-toe games, defined as
follows. Each particular game is specified by a set $\mathcal S$ of
squares and a collection $\mathcal W$ of winning
positions. Each winning position is a subset of $\mathcal S$.
For example, in standard tic-tac-toe, $\mathcal S$ is a set of 9 squares
and $\mathcal W$ is a collection of 8 subsets of $\cal W$: the three
rows, the three columns, and the two diagonals. In other respects, the
game is identical to standard tic-tac-toe. Starting from an empty board,
players alternate placing their marks on an empty square. A player who
marks every square in a winning position wins the game. It is a tie if
all squares are marked and neither player has won.
1. Let $N= |{\mathcal S}|$, the number of squares. Give an upper bound
on the number of nodes in the complete game tree for generalized
tic-tac-toe as a function of $N$.
2. Give a lower bound on the size of the game tree for the worst case,
where ${\mathcal W} = {\{\,\}}$.
3. Propose a plausible evaluation function that can be used for any
instance of generalized tic-tac-toe. The function may depend on
$\mathcal S$ and $\mathcal W$.
4. Assume that it is possible to generate a new board and check whether
it is a winning position in 100$N$ machine instructions and assume a
2 gigahertz processor. Ignore memory limitations. Using your
estimate in (a), roughly how large a game tree can be completely
solved by alpha–beta in a second of CPU time? a minute? an hour?
Develop a general game-playing program, capable of playing a variety of
games.
1. Implement move generators and evaluation functions for one or more
of the following games: Kalah, Othello, checkers, and chess.
2. Construct a general alpha–beta game-playing agent.
3. Compare the effect of increasing search depth, improving move
ordering, and improving the evaluation function. How close does your
effective branching factor come to the ideal case of perfect move
ordering?
4. Implement a selective search algorithm, such as B\* @Berliner:1979,
conspiracy number search @McAllester:1988, or MGSS\*
@Russell+Wefald:1989 and compare its performance to A\*.
Describe how the minimax and alpha–beta algorithms change for two-player, non-zero-sum games in which each player has a distinct utility function and both utility functions are known to both players. If there are no constraints on the two terminal utilities, is it possible for any node to be pruned by alpha–beta? What if the player’s utility functions on any state differ by at most a constant $k$, making the game almost cooperative?
Describe how the minimax and alpha–beta algorithms change for two-player, non-zero-sum games in which each player has a distinct utility function and both utility functions are known to both players. If there are no constraints on the two terminal utilities, is it possible for any node to be pruned by alpha–beta? What if the player’s utility functions on any state sum to a number between constants $-k$ and $k$, making the game almost zero-sum?
Develop a formal proof of correctness for alpha–beta pruning. To do
this, consider the situation shown in
Figure alpha-beta-proof-figure. The question is whether
to prune node $n_j$, which is a max-node and a descendant of node $n_1$.
The basic idea is to prune it if and only if the minimax value of $n_1$
can be shown to be independent of the value of $n_j$.
1. Mode $n_1$ takes on the minimum value among its children:
$n_1 = \min(n_2,n_21,\ldots,n_{2b_2})$. Find a similar
expression for $n_2$ and hence an expression for $n_1$ in terms of
$n_j$.
2. Let $l_i$ be the minimum (or maximum) value of the nodes to the
left of node $n_i$ at depth $i$, whose minimax value
is already known. Similarly, let $r_i$ be the minimum (or maximum)
value of the unexplored nodes to the right of $n_i$ at depth $i$.
Rewrite your expression for $n_1$ in terms of the $l_i$ and
$r_i$ values.
3. Now reformulate the expression to show that in order to affect
$n_1$, $n_j$ must not exceed a certain bound derived from the
$l_i$ values.
4. Repeat the process for the case where $n_j$ is a min-node.
Prove that the alpha–beta algorithm takes time $O(b^{m/2})$ with optimal move ordering, where $m$ is the maximum depth of the game tree.
Suppose you have a chess program that can evaluate 5 million nodes per second. Decide on a compact representation of a game state for storage in a transposition table. About how many entries can you fit in a 1-gigabyte in-memory table? Will that be enough for the three minutes of search allocated for one move? How many table lookups can you do in the time it would take to do one evaluation? Now suppose the transposition table is stored on disk. About how many evaluations could you do in the time it takes to do one disk seek with standard disk hardware?
Suppose you have a chess program that can evaluate 10 million nodes per
second. Decide on a compact representation of a game state for storage
in a transposition table. About how many entries can you fit in a
2-gigabyte in-memory table? Will that be enough for the three minutes of
search allocated for one move? How many table lookups can you do in the
time it would take to do one evaluation? Now suppose the transposition
table is stored on disk. About how many evaluations could you do in the
time it takes to do one disk seek with standard disk hardware?
This question considers pruning in games with chance nodes.
Figure trivial-chance-game-figure shows the complete
game tree for a trivial game. Assume that the leaf nodes are to be
evaluated in left-to-right order, and that before a leaf node is
evaluated, we know nothing about its value—the range of possible values
is $-\infty$ to $\infty$.
1. Copy the figure, mark the value of all the internal nodes, and
indicate the best move at the root with an arrow.
2. Given the values of the first six leaves, do we need to evaluate the
seventh and eighth leaves? Given the values of the first seven
leaves, do we need to evaluate the eighth leaf? Explain
your answers.
3. Suppose the leaf node values are known to lie between –2 and 2
inclusive. After the first two leaves are evaluated, what is the
value range for the left-hand chance node?
4. Circle all the leaves that need not be evaluated under the
assumption in (c).
Implement the expectiminimax algorithm and the \*-alpha–beta algorithm, which is described by @Ballard:1983, for pruning game trees with chance nodes. Try them on a game such as backgammon and measure the pruning effectiveness of \*-alpha–beta.
Prove that with a positive linear transformation of leaf values (i.e., transforming a value $x$ to $ax + b$ where $a > 0$), the choice of move remains unchanged in a game tree, even when there are chance nodes.
Consider the following procedure for choosing moves in games with chance nodes:
- Generate some dice-roll sequences (say, 50) down to a suitable depth (say, 8).
- With known dice rolls, the game tree becomes deterministic. For each dice-roll sequence, solve the resulting deterministic game tree using alpha–beta.
- Use the results to estimate the value of each move and to choose the best.
Will this procedure work well? Why (or why not)?
In the following, a “max” tree consists only of max nodes, whereas an
“expectimax” tree consists of a max node at the root with alternating
layers of chance and max nodes. At chance nodes, all outcome
probabilities are nonzero. The goal is to find the value of the
root with a bounded-depth search. For each of (a)–(f), either
give an example or explain why this is impossible.
1. Assuming that leaf values are finite but unbounded, is pruning (as
in alpha–beta) ever possible in a max tree?
2. Is pruning ever possible in an expectimax tree under the same
conditions?
3. If leaf values are all nonnegative, is pruning ever possible in a
max tree? Give an example, or explain why not.
4. If leaf values are all nonnegative, is pruning ever possible in an
expectimax tree? Give an example, or explain why not.
5. If leaf values are all in the range $[0,1]$, is pruning ever
possible in a max tree? Give an example, or explain why not.
6. If leaf values are all in the range $[0,1]$, is pruning ever
possible in an expectimax tree?1
7. Consider the outcomes of a chance node in an expectimax tree. Which
of the following evaluation orders is most likely to yield pruning
opportunities?
i. Lowest probability first
ii. Highest probability first
iii. Doesn’t make any difference
In the following, a “max” tree consists only of max nodes, whereas an
“expectimax” tree consists of a max node at the root with alternating
layers of chance and max nodes. At chance nodes, all outcome
probabilities are nonzero. The goal is to find the value of the
root with a bounded-depth search.
1. Assuming that leaf values are finite but unbounded, is pruning (as
in alpha–beta) ever possible in a max tree? Give an example, or
explain why not.
2. Is pruning ever possible in an expectimax tree under the same
conditions? Give an example, or explain why not.
3. If leaf values are constrained to be in the range $[0,1]$, is
pruning ever possible in a max tree? Give an example, or explain
why not.
4. If leaf values are constrained to be in the range $[0,1]$, is
pruning ever possible in an expectimax tree? Give an example
(qualitatively different from your example in (e), if any), or
explain why not.
5. If leaf values are constrained to be nonnegative, is pruning ever
possible in a max tree? Give an example, or explain why not.
6. If leaf values are constrained to be nonnegative, is pruning ever
possible in an expectimax tree? Give an example, or explain why not.
7. Consider the outcomes of a chance node in an expectimax tree. Which
of the following evaluation orders is most likely to yield pruning
opportunities: (i) Lowest probability first; (ii) Highest
probability first; (iii) Doesn’t make any difference?
Suppose you have an oracle, $OM(s)$, that correctly predicts the opponent’s move in any state. Using this, formulate the definition of a game as a (single-agent) search problem. Describe an algorithm for finding the optimal move.
Consider carefully the interplay of chance events and partial
information in each of the games in
Exercise game-playing-chance-exercise.
1. For which is the standard expectiminimax model appropriate?
Implement the algorithm and run it in your game-playing agent, with
appropriate modifications to the game-playing environment.
2. For which would the scheme described in
Exercise game-playing-monte-carlo-exercise be
appropriate?
3. Discuss how you might deal with the fact that in some of the games,
the players do not have the same knowledge of the current state.
How many solutions are there for the map-coloring problem in Figure australia-figure? How many solutions if four colors are allowed? Two colors?
Consider the problem of placing $k$ knights on an $n\times n$
chessboard such that no two knights are attacking each other, where $k$
is given and $k\leq n^2$.
1. Choose a CSP formulation. In your formulation, what are the
variables?
2. What are the possible values of each variable?
3. What sets of variables are constrained, and how?
4. Now consider the problem of putting *as many knights as
possible* on the board without any attacks. Explain how to
solve this with local search by defining appropriate ACTIONS and RESULT functions
and a sensible objective function.
Consider the problem of constructing (not solving)
crossword puzzles fitting words into a rectangular grid. The grid,
which is given as part of the problem, specifies which squares are blank
and which are shaded. Assume that a list of words (i.e., a dictionary)
is provided and that the task is to fill in the blank squares by using
any subset of the list. Formulate this problem precisely in two ways:
1. As a general search problem. Choose an appropriate search algorithm
and specify a heuristic function. Is it better to fill in blanks one
letter at a time or one word at a time?
2. As a constraint satisfaction problem. Should the variables be words
or letters?
Which formulation do you think will be better? Why?
Give precise formulations for each of the
following as constraint satisfaction problems:
1. Rectilinear floor-planning: find non-overlapping places in a large
rectangle for a number of smaller rectangles.
2. Class scheduling: There is a fixed number of professors and
classrooms, a list of classes to be offered, and a list of possible
time slots for classes. Each professor has a set of classes that he
or she can teach.
3. Hamiltonian tour: given a network of cities connected by roads,
choose an order to visit all cities in a country without
repeating any.
Solve the cryptarithmetic problem in Figure cryptarithmetic-figure by hand, using the strategy of backtracking with forward checking and the MRV and least-constraining-value heuristics.
Show how a single ternary constraint such as “$A + B = C$” can be turned into three binary constraints by using an auxiliary variable. You may assume finite domains. (*Hint:* Consider a new variable that takes on values that are pairs of other values, and consider constraints such as “$X$ is the first element of the pair $Y$.”) Next, show how constraints with more than three variables can be treated similarly. Finally, show how unary constraints can be eliminated by altering the domains of variables. This completes the demonstration that any CSP can be transformed into a CSP with only binary constraints.
Consider the following logic puzzle: In five houses,
each with a different color, live five persons of different
nationalities, each of whom prefers a different brand of candy, a
different drink, and a different pet. Given the following facts, the
questions to answer are “Where does the zebra live, and in which house
do they drink water?”
The Englishman lives in the red house.
The Spaniard owns the dog.
The Norwegian lives in the first house on the left.
The green house is immediately to the right of the ivory house.
The man who eats Hershey bars lives in the house next to the man with
the fox.
Kit Kats are eaten in the yellow house.
The Norwegian lives next to the blue house.
The Smarties eater owns snails.
The Snickers eater drinks orange juice.
The Ukrainian drinks tea.
The Japanese eats Milky Ways.
Kit Kats are eaten in a house next to the house where the horse is kept.
Coffee is drunk in the green house.
Milk is drunk in the middle house.
Discuss different representations of this problem as a CSP. Why would
one prefer one representation over another?
Consider the graph with 8 nodes $A_1$, $A_2$, $A_3$, $A_4$, $H$, $T$, $F_1$, $F_2$. $A_i$ is connected to $A_{i+1}$ for all $i$, each $A_i$ is connected to $H$, $H$ is connected to $T$, and $T$ is connected to each $F_i$. Find a 3-coloring of this graph by hand using the following strategy: backtracking with conflict-directed backjumping, the variable order $A_1$, $H$, $A_4$, $F_1$, $A_2$, $F_2$, $A_3$, $T$, and the value order $R$, $G$, $B$.
Explain why it is a good heuristic to choose the variable that is *most* constrained but the value that is *least* constraining in a CSP search.
Generate random instances of map-coloring problems as follows: scatter $n$ points on the unit square; select a point $X$ at random, connect $X$ by a straight line to the nearest point $Y$ such that $X$ is not already connected to $Y$ and the line crosses no other line; repeat the previous step until no more connections are possible. The points represent regions on the map and the lines connect neighbors. Now try to find $k$-colorings of each map, for both $k3$ and $k4$, using min-conflicts, backtracking, backtracking with forward checking, and backtracking with MAC. Construct a table of average run times for each algorithm for values of $n$ up to the largest you can manage. Comment on your results.
Use the AC-3 algorithm to show that arc consistency can detect the inconsistency of the partial assignment ${green},V{red}$ for the problem shown in Figure australia-figure.
Use the AC-3 algorithm to show that arc consistency can detect the inconsistency of the partial assignment ${red},V{blue}$ for the problem shown in Figure australia-figure.
What is the worst-case complexity of running AC-3 on a tree-structured CSP?
AC-3 puts back on the queue *every* arc ($X_{k}, X_{i}$) whenever *any* value is deleted from the domain of $X_{i}$, even if each value of $X_{k}$ is consistent with several remaining values of $X_{i}$. Suppose that, for every arc ($X_{k}, X_{i}$), we keep track of the number of remaining values of $X_{i}$ that are consistent with each value of $X_{k}$. Explain how to update these numbers efficiently and hence show that arc consistency can be enforced in total time $O(n^2d^2)$.
The Tree-CSP-Solver (Figure tree-csp-figure) makes arcs consistent starting at the leaves and working backwards towards the root. Why does it do that? What would happen if it went in the opposite direction?
We introduced Sudoku as a CSP to be solved by search over partial assignments because that is the way people generally undertake solving Sudoku problems. It is also possible, of course, to attack these problems with local search over complete assignments. How well would a local solver using the min-conflicts heuristic do on Sudoku problems?
Define in your own words the terms constraint, backtracking search, arc consistency, backjumping, min-conflicts, and cycle cutset.
Define in your own words the terms constraint, commutativity, arc consistency, backjumping, min-conflicts, and cycle cutset.
Suppose that a graph is known to have a cycle cutset of no more than $k$ nodes. Describe a simple algorithm for finding a minimal cycle cutset whose run time is not much more than $O(n^k)$ for a CSP with $n$ variables. Search the literature for methods for finding approximately minimal cycle cutsets in time that is polynomial in the size of the cutset. Does the existence of such algorithms make the cycle cutset method practical?
Consider the problem of tiling a surface (completely and exactly
covering it) with $n$ dominoes ($2\times
1$ rectangles). The surface is an arbitrary edge-connected (i.e.,
adjacent along an edge, not just a corner) collection of $2n$
$1\times 1$ squares (e.g., a checkerboard, a checkerboard with some
squares missing, a $10\times 1$ row of squares, etc.).
1. Formulate this problem precisely as a CSP where the dominoes are
the variables.
2. Formulate this problem precisely as a CSP where the squares are the
variables, keeping the state space as small as possible.
(*Hint:* does it matter which particular domino goes on
a given pair of squares?)
3. Construct a surface consisting of 6 squares such that your CSP
formulation from part (b) has a *tree-structured*
constraint graph.
4. Describe exactly the set of solvable instances that have a
tree-structured constraint graph.
Suppose the agent has progressed to the point shown in
Figure wumpus-seq35-figure(a), page wumpus-seq35-figure,
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 wumpus-entailment-figure, 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:
$\alpha_2$ = “There is no pit in [2,2].”
$\alpha_3$ = “There is a wumpus in [1,3].”
Hence show that ${KB} {\models}\alpha_2$ and
${KB} {\models}\alpha_3$.
(Adapted from @Barwise+Etchemendy:1993 .) Given the following, can you prove that the unicorn is
mythical? How about magical? Horned?
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.
Consider the problem of deciding whether a
propositional logic sentence is true in a given model.
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.)
2. Give three examples of sentences that can be determined to be true
or false in a partial model that does not specify a
truth value for some of the symbols.
3. Show that the truth value (if any) of a sentence in a partial model
cannot be determined efficiently in general.
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 not detected by your algorithm.
5. Investigate whether the modified algorithm makes $TT-Entails?$ more efficient.
Which of the following are correct?
1. ${False} \models {True}$.
2. ${True} \models {False}$.
3. $(A\land B) \models (A{\;\;{\Leftrightarrow}\;\;}B)$.
4. $A{\;\;{\Leftrightarrow}\;\;}B \models A \lor B$.
5. $A{\;\;{\Leftrightarrow}\;\;}B \models \lnot A \lor B$.
6. $(A\land B){\:\;{\Rightarrow}\:\;}C \models (A{\:\;{\Rightarrow}\:\;}C)\lor(B{\:\;{\Rightarrow}\:\;}C)$.
7. $(C\lor (\lnot A \land \lnot B)) \equiv ((A{\:\;{\Rightarrow}\:\;}C) \land (B {\:\;{\Rightarrow}\:\;}C))$.
8. $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B)$.
9. $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B) \land (\lnot D\lor E)$.
10. $(A\lor B) \land \lnot(A {\:\;{\Rightarrow}\:\;}B)$ is satisfiable.
11. $(A{\;\;{\Leftrightarrow}\;\;}B) \land (\lnot A \lor B)$
is satisfiable.
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$.
Which of the following are correct?
1. ${False} \models {True}$.
2. ${True} \models {False}$.
3. $(A\land B) \models (A{\;\;{\Leftrightarrow}\;\;}B)$.
4. $A{\;\;{\Leftrightarrow}\;\;}B \models A \lor B$.
5. $A{\;\;{\Leftrightarrow}\;\;}B \models \lnot A \lor B$.
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)$.
7. $(A\lor B) \land (\lnot C\lor\lnot D\lor E) \models (A\lor B) \land (\lnot D\lor E)$.
8. $(A\lor B) \land \lnot(A {\:\;{\Rightarrow}\:\;}B)$ is satisfiable.
9. $(A\land B){\:\;{\Rightarrow}\:\;}C \models (A{\:\;{\Rightarrow}\:\;}C)\lor(B{\:\;{\Rightarrow}\:\;}C)$.
10. $(C\lor (\lnot A \land \lnot B)) \equiv ((A{\:\;{\Rightarrow}\:\;}C) \land (B {\:\;{\Rightarrow}\:\;}C))$.
11. $(A{\;\;{\Leftrightarrow}\;\;}B) \land (\lnot A \lor B)$
is satisfiable.
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$.
Prove each of the following assertions:
1. $\alpha$ is valid if and only if ${True}{\models}\alpha$.
2. For any $\alpha$, ${False}{\models}\alpha$.
3. $\alpha{\models}\beta$ if and only if the sentence
$(\alpha {\:\;{\Rightarrow}\:\;}\beta)$ is valid.
4. $\alpha \equiv \beta$ if and only if the sentence
$(\alpha{\;\;{\Leftrightarrow}\;\;}\beta)$ is valid.
5. $\alpha{\models}\beta$ if and only if the sentence
$(\alpha \land \lnot \beta)$ is unsatisfiable.
Prove, or find a counterexample to, each of the following assertions:
1. If $\alpha\models\gamma$ or $\beta\models\gamma$ (or both) then
$(\alpha\land \beta)\models\gamma$
2. If $(\alpha\land \beta)\models\gamma$ then $\alpha\models\gamma$ or
$\beta\models\gamma$ (or both).
3. If $\alpha\models (\beta \lor \gamma)$ then $\alpha \models \beta$
or $\alpha \models \gamma$ (or both).
Prove, or find a counterexample to, each of the following assertions:
1. If $\alpha\models\gamma$ or $\beta\models\gamma$ (or both) then
$(\alpha\land \beta)\models\gamma$
2. If $\alpha\models (\beta \land \gamma)$ then $\alpha \models \beta$
and $\alpha \models \gamma$.
3. If $\alpha\models (\beta \lor \gamma)$ then $\alpha \models \beta$
or $\alpha \models \gamma$ (or both).
Consider a vocabulary with only four propositions, $A$, $B$, $C$, and
$D$. How many models are there for the following sentences?
1. $B\lor C$.
2. $\lnot A\lor \lnot B \lor \lnot C \lor \lnot D$.
3. $(A{\:\;{\Rightarrow}\:\;}B) \land A \land \lnot B \land C \land D$.
We have defined four binary logical connectives.
1. Are there any others that might be useful?
2. How many binary connectives can there be?
3. Why are some of them not very useful?
Using a method of your choice, verify each of the equivalences in Table \[logical-equivalence-table\] (page <a href="#"logical-equivalence-table</a>).
Decide whether each of the following
sentences is valid, unsatisfiable, or neither. Verify your decisions
using truth tables or the equivalence rules of
Table \[logical-equivalence-table\] (page logical-equivalence-table).
1. ${Smoke} {\:\;{\Rightarrow}\:\;}{Smoke}$
2. ${Smoke} {\:\;{\Rightarrow}\:\;}{Fire}$
3. $({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) {\:\;{\Rightarrow}\:\;}(\lnot {Smoke} {\:\;{\Rightarrow}\:\;}\lnot {Fire})$
4. ${Smoke} \lor {Fire} \lor \lnot {Fire}$
5. $(({Smoke} \land {Heat}) {\:\;{\Rightarrow}\:\;}{Fire})
{\;\;{\Leftrightarrow}\;\;}(({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) \lor ({Heat} {\:\;{\Rightarrow}\:\;}{Fire}))$
6. $({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) {\:\;{\Rightarrow}\:\;}(({Smoke} \land {Heat}) {\:\;{\Rightarrow}\:\;}{Fire}) $
7. ${Big} \lor {Dumb} \lor ({Big} {\:\;{\Rightarrow}\:\;}{Dumb})$
Decide whether each of the following
sentences is valid, unsatisfiable, or neither. Verify your decisions
using truth tables or the equivalence rules of
Table \[logical-equivalence-table\] (page logical-equivalence-table).
1. ${Smoke} {\:\;{\Rightarrow}\:\;}{Smoke}$
2. ${Smoke} {\:\;{\Rightarrow}\:\;}{Fire}$
3. $({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) {\:\;{\Rightarrow}\:\;}(\lnot {Smoke} {\:\;{\Rightarrow}\:\;}\lnot {Fire})$
4. ${Smoke} \lor {Fire} \lor \lnot {Fire}$
5. $(({Smoke} \land {Heat}) {\:\;{\Rightarrow}\:\;}{Fire})
{\;\;{\Leftrightarrow}\;\;}(({Smoke} {\:\;{\Rightarrow}\:\;}{Fire}) \lor ({Heat} {\:\;{\Rightarrow}\:\;}{Fire}))$
6. ${Big} \lor {Dumb} \lor ({Big} {\:\;{\Rightarrow}\:\;}{Dumb})$
7. $({Big} \land {Dumb}) \lor \lnot {Dumb}$
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.
Use resolution to prove the sentence $\lnot A \land \lnot B$ from the clauses in Exercise convert-clausal-exercise.
This exercise looks into the relationship between
clauses and implication sentences.
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$.
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 Kowalski
form @Kowalski:1979.
3. Write down the full resolution rule for sentences in implicative
normal form.
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.
1. Which of the following are correct representations of this
assertion?
1. $(R\land E)\iff C$
2. $R{\:\;{\Rightarrow}\:\;}(E\iff C)$
3. $R{\:\;{\Rightarrow}\:\;}((C{\:\;{\Rightarrow}\:\;}E) \lor \lnot E)$
2. Which of the sentences in (a) can be expressed in Horn form?
This question considers representing satisfiability (SAT) problems as
CSPs.
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$.
2. How many solutions are there for this general SAT problem as a
function of $n$?
3. Suppose we apply {Backtracking-Search} (page backtracking-search-algorithm) to find all
solutions to a SAT CSP of the type given in (a). (To find
all 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$.)
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 csp-structure-section). Are these two
facts connected? Discuss.
This question considers representing satisfiability (SAT) problems as
CSPs.
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$.
2. How many solutions are there for this general SAT problem as a
function of $n$?
3. Suppose we apply {Backtracking-Search} (page backtracking-search-algorithm) to find all
solutions to a SAT CSP of the type given in (a). (To find
all 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$.)
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 csp-structure-section). Are these two
facts connected? Discuss.
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.
A propositional 2-CNF expression is a conjunction of
clauses, each containing exactly 2 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)\ .$$
1. Prove using resolution that the above sentence entails $G$.
2. Two clauses are semantically distinct if they are not
logically equivalent. How many semantically distinct 2-CNF clauses
can be constructed from $n$ proposition symbols?
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.
4. Explain why your argument in (c) does not apply to 3-CNF.
Prove each of the following assertions:
1. Every pair of propositional clauses either has no resolvents, or all
their resolvents are logically equivalent.
2. There is no clause that, when resolved with itself, yields
(after factoring) the clause $(\lnot P \lor \lnot Q)$.
3. If a propositional clause $C$ can be resolved with a copy of itself,
it must be logically equivalent to $ True $.
Consider the following sentence:
$$[ ({Food} {\:\;{\Rightarrow}\:\;}{Party}) \lor ({Drinks} {\:\;{\Rightarrow}\:\;}{Party}) ] {\:\;{\Rightarrow}\:\;}[ ( {Food} \land {Drinks} ) {\:\;{\Rightarrow}\:\;}{Party}]\ .$$
1. Determine, using enumeration, whether this sentence is valid,
satisfiable (but not valid), or unsatisfiable.
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).
3. Prove your answer to (a) using resolution.
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.
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.
2. Construct an algorithm that converts any sentence in propositional
logic into DNF. (Hint: The algorithm is similar to
the algorithm for conversion to CNF iven in
Sectio pl-resolution-section.)
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.
4. Apply the algorithms in (b) and (c) to the following set of
sentences:
$A {\Rightarrow} B$
$B {\Rightarrow} C$
$C {\Rightarrow} A$
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?
Convert the following set of sentences to
clausal form.
1. S1: $A {\;\;{\Leftrightarrow}\;\;}(B \lor E)$.
2. S2: $E {\:\;{\Rightarrow}\:\;}D$.
3. S3: $C \land F {\:\;{\Rightarrow}\:\;}\lnot B$.
4. S4: $E {\:\;{\Rightarrow}\:\;}B$.
5. S5: $B {\:\;{\Rightarrow}\:\;}F$.
6. S6: $B {\:\;{\Rightarrow}\:\;}C$
Give a trace of the execution of DPLL on the conjunction of these
clauses.
Convert the following set of sentences to
clausal form.
1. S1: $A {\;\;{\Leftrightarrow}\;\;}(B \lor E)$.
2. S2: $E {\:\;{\Rightarrow}\:\;}D$.
3. S3: $C \land F {\:\;{\Rightarrow}\:\;}\lnot B$.
4. S4: $E {\:\;{\Rightarrow}\:\;}B$.
5. S5: $B {\:\;{\Rightarrow}\:\;}F$.
6. S6: $B {\:\;{\Rightarrow}\:\;}C$
Give a trace of the execution of DPLL on the conjunction of these
clauses.
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.
[Exercise 7.28 \[minesweeper-exercise\]](ex_28/) 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 number 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 long-range dependencies such that the contents of a given unprobed square would give information about the contents of a far-distant square. (Hint: consider an $N\times 1$ board.)
How long does it take to prove ${KB}{\models}\alpha$ using {DPLL} when $\alpha$ is a literal already contained in ${KB}$? Explain.
Trace the behavior of {DPLL} on the knowledge base in Figure pl-horn-example-figure when trying to prove $Q$, and compare this behavior with that of the forward-chaining algorithm.
Write a successor-state axiom for the ${Locked}$ predicate, which applies to doors, assuming the only actions available are ${Lock}$ and ${Unlock}$.
Discuss what is meant by optimal behavior in the wumpus world. Show that the {Hybrid-Wumpus-Agent} is not optimal, and suggest ways to improve it.
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$).
1. Write a successor-state axiom for $S^{t+1}$.
2. Convert the sentence in (a) into CNF.
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$.
Section successor-state-section provides some of the successor-state axioms required for the wumpus world. Write down axioms for all remaining fluent symbols.
Modify the {Hybrid-Wumpus-Agent} to use the 1-CNF logical state estimation method described on page 1cnf-belief-state-page. 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?
A logical knowledge base represents the world using a set of sentences
with no explicit structure. An analogical
representation, on the other hand, has physical structure that
corresponds directly to the structure of the thing represented. Consider
a road map of your country as an analogical representation of facts
about the country—it represents facts with a map language. The
two-dimensional structure of the map corresponds to the two-dimensional
surface of the area.
1. Give five examples of *symbols* in the map language.
2. An *explicit* sentence is a sentence that the creator
of the representation actually writes down. An
*implicit* sentence is a sentence that results from
explicit sentences because of properties of the analogical
representation. Give three examples each of *implicit*
and *explicit* sentences in the map language.
3. Give three examples of facts about the physical structure of your
country that cannot be represented in the map language.
4. Give two examples of facts that are much easier to express in the
map language than in first-order logic.
5. Give two other examples of useful analogical representations. What
are the advantages and disadvantages of each of these languages?
Consider a knowledge base containing just two sentences: $P(a)$ and $P(b)$. Does this knowledge base entail $\forall\,x\ P(x)$? Explain your answer in terms of models.
Is the sentence ${\exists\,x,y\;\;} xy$ valid? Explain.
Write down a logical sentence such that every world in which it is true contains exactly one object.
Write down a logical sentence such that every world in which it is true contains exactly two objects.
fol-model-count-exercise Consider a symbol vocabulary that contains $c$ constant symbols, $p_k$ predicate symbols of each arity $k$, and $f_k$ function symbols of each arity $k$, where $1\leq k\leq A$. Let the domain size be fixed at $D$. For any given model, each predicate or function symbol is mapped onto a relation or function, respectively, of the same arity. You may assume that the functions in the model allow some input tuples to have no value for the function (i.e., the value is the invisible object). Derive a formula for the number of possible models for a domain with $D$ elements. Don’t worry about eliminating redundant combinations.
Which of the following are valid (necessarily true) sentences?
1. $(\exists x\ xx) {\:\;{\Rightarrow}\:\;}({\forall\,y\;\;} \exists z\ yz)$.
2. ${\forall\,x\;\;} P(x) \lor \lnot P(x)$.
3. ${\forall\,x\;\;} {Smart}(x) \lor (xx)$.
Consider a version of the semantics for first-order logic in which models with empty domains are allowed. Give at least two examples of sentences that are valid according to the standard semantics but not according to the new semantics. Discuss which outcome makes more intuitive sense for your examples.
Does the fact $\lnot {Spouse}({George},{Laura})$ follow from the facts ${Jim}\neq {George}$ and ${Spouse}({Jim},{Laura})$? If so, give a proof; if not, supply additional axioms as needed. What happens if we use ${Spouse}$ as a unary function symbol instead of a binary predicate?
This exercise uses the function ${MapColor}$ and predicates
${In}(x,y)$, ${Borders}(x,y)$, and ${Country}(x)$, whose arguments
are geographical regions, along with constant symbols for various
regions. In each of the following we give an English sentence and a
number of candidate logical expressions. For each of the logical
expressions, state whether it (1) correctly expresses the English
sentence; (2) is syntactically invalid and therefore meaningless; or (3)
is syntactically valid but does not express the meaning of the English
sentence.
1. Paris and Marseilles are both in France.
1. ${In}({Paris} \land {Marseilles}, {France})$.
2. ${In}({Paris},{France}) \land {In}({Marseilles},{France})$.
3. ${In}({Paris},{France}) \lor {In}({Marseilles},{France})$.
2. There is a country that borders both Iraq and Pakistan.
1. ${\exists\,c\;\;}$
${Country}(c) \land {Border}(c,{Iraq}) \land {Border}(c,{Pakistan})$.
2. ${\exists\,c\;\;}$
${Country}(c) {\:\;{\Rightarrow}\:\;}[{Border}(c,{Iraq}) \land {Border}(c,{Pakistan})]$.
3. $[{\exists\,c\;\;}$
${Country}(c)] {\:\;{\Rightarrow}\:\;}[{Border}(c,{Iraq}) \land {Border}(c,{Pakistan})]$.
4. ${\exists\,c\;\;}$
${Border}({Country}(c),{Iraq} \land {Pakistan})$.
3. All countries that border Ecuador are in South America.
1. ${\forall\,c\;\;} Country(c) \land {Border}(c,{Ecuador}) {\:\;{\Rightarrow}\:\;}{In}(c,{SouthAmerica})$.
2. ${\forall\,c\;\;} {Country}(c) {\:\;{\Rightarrow}\:\;}[{Border}(c,{Ecuador}) {\:\;{\Rightarrow}\:\;}{In}(c,{SouthAmerica})]$.
3. ${\forall\,c\;\;} [{Country}(c) {\:\;{\Rightarrow}\:\;}{Border}(c,{Ecuador})] {\:\;{\Rightarrow}\:\;}{In}(c,{SouthAmerica})$.
4. ${\forall\,c\;\;} Country(c) \land {Border}(c,{Ecuador}) \land {In}(c,{SouthAmerica})$.
4. No region in South America borders any region in Europe.
1. $\lnot [{\exists\,c,d\;\;} {In}(c,{SouthAmerica}) \land {In}(d,{Europe}) \land {Borders}(c,d)]$.
2. ${\forall\,c,d\;\;} [{In}(c,{SouthAmerica}) \land {In}(d,{Europe})] {\:\;{\Rightarrow}\:\;}\lnot {Borders}(c,d)]$.
3. $\lnot {\forall\,c\;\;} {In}(c,{SouthAmerica}) {\:\;{\Rightarrow}\:\;}{\exists\,d\;\;} {In}(d,{Europe}) \land
\lnot {Borders}(c,d)$.
4. ${\forall\,c\;\;} {In}(c,{SouthAmerica}) {\:\;{\Rightarrow}\:\;}{\forall\,d\;\;} {In}(d,{Europe}) {\:\;{\Rightarrow}\:\;}\lnot {Borders}(c,d)$.
5. No two adjacent countries have the same map color.
1. ${\forall\,x,y\;\;} \lnot {Country}(x) \lor \lnot {Country}(y) \lor \lnot {Borders}(x,y) \lor {}$\
$\lnot ({MapColor}(x) = {MapColor}(y))$.
2. ${\forall\,x,y\;\;} ({Country}(x) \land {Country}(y) \land {Borders}(x,y) \land \lnot(x=y)) {\:\;{\Rightarrow}\:\;}{}$\
$\lnot ({MapColor}(x) = {MapColor}(y))$.
3. ${\forall\,x,y\;\;} {Country}(x) \land {Country}(y) \land {Borders}(x,y) \land {}$\
$\lnot ({MapColor}(x) = {MapColor}(y))$.
4. ${\forall\,x,y\;\;} ({Country}(x) \land {Country}(y) \land {Borders}(x,y) ) {\:\;{\Rightarrow}\:\;}{MapColor}(x\neq y)$.
Consider a vocabulary with the following symbols:
> ${Occupation}(p,o)$: Predicate. Person $p$ has occupation $o$.
> ${Customer}(p1,p2)$: Predicate. Person $p1$ is a customer of person $p2$.
> ${Boss}(p1,p2)$: Predicate. Person $p1$ is a boss of person $p2$.
> ${Doctor}$, $ {Surgeon}$, $ {Lawyer}$, $ {Actor}$: Constants denoting occupations.
> ${Emily}$, $ {Joe}$: Constants denoting people.
Use these symbols to write the following assertions in first-order
logic:
1. Emily is either a surgeon or a lawyer.
2. Joe is an actor, but he also holds another job.
3. All surgeons are doctors.
4. Joe does not have a lawyer (i.e., is not a customer of any lawyer).
5. Emily has a boss who is a lawyer.
6. There exists a lawyer all of whose customers are doctors.
7. Every surgeon has a lawyer.
In each of the following we give an English sentence and a number of
candidate logical expressions. For each of the logical expressions,
state whether it (1) correctly expresses the English sentence; (2) is
syntactically invalid and therefore meaningless; or (3) is syntactically
valid but does not express the meaning of the English sentence.
1. Every cat loves its mother or father.
1. ${\forall\,x\;\;} {Cat}(x) {\:\;{\Rightarrow}\:\;}{Loves}(x,{Mother}(x)\lor {Father}(x))$.
2. ${\forall\,x\;\;} \lnot {Cat}(x) \lor {Loves}(x,{Mother}(x)) \lor {Loves}(x,{Father}(x))$.
3. ${\forall\,x\;\;} {Cat}(x) \land ({Loves}(x,{Mother}(x))\lor {Loves}(x,{Father}(x)))$.
2. Every dog who loves one of its brothers is happy.
1. ${\forall\,x\;\;} {Dog}(x) \land (\exists y\ {Brother}(y,x) \land {Loves}(x,y)) {\:\;{\Rightarrow}\:\;}{Happy}(x)$.
2. ${\forall\,x,y\;\;} {Dog}(x) \land {Brother}(y,x) \land {Loves}(x,y) {\:\;{\Rightarrow}\:\;}{Happy}(x)$.
3. ${\forall\,x\;\;} {Dog}(x) \land [{\forall\,y\;\;} {Brother}(y,x) {\;\;{\Leftrightarrow}\;\;}{Loves}(x,y)] {\:\;{\Rightarrow}\:\;}{Happy}(x)$.
3. No dog bites a child of its owner.
1. ${\forall\,x\;\;} {Dog}(x) {\:\;{\Rightarrow}\:\;}\lnot {Bites}(x,{Child}({Owner}(x)))$.
2. $\lnot {\exists\,x,y\;\;} {Dog}(x) \land {Child}(y,{Owner}(x)) \land {Bites}(x,y)$.
3. ${\forall\,x\;\;} {Dog}(x) {\:\;{\Rightarrow}\:\;}({\forall\,y\;\;} {Child}(y,{Owner}(x)) {\:\;{\Rightarrow}\:\;}\lnot {Bites}(x,y))$.
4. $\lnot {\exists\,x\;\;} {Dog}(x) {\:\;{\Rightarrow}\:\;}({\exists\,y\;\;} {Child}(y,{Owner}(x)) \land {Bites}(x,y))$.
4. Everyone’s zip code within a state has the same first digit.
1. ${\forall\,x,s,z_1\;\;} [{State}(s) \land {LivesIn}(x,s) \land {Zip}(x)z_1] {\:\;{\Rightarrow}\:\;}{}$\
$[{\forall\,y,z_2\;\;} {LivesIn}(y,s) \land {Zip}(y)z_2 {\:\;{\Rightarrow}\:\;}{Digit}(1,z_1) {Digit}(1,z_2) ]$.
2. ${\forall\,x,s\;\;} [{State}(s) \land {LivesIn}(x,s) \land {\exists\,z_1\;\;} {Zip}(x)z_1] {\:\;{\Rightarrow}\:\;}{}$\
$ [{\forall\,y,z_2\;\;} {LivesIn}(y,s) \land {Zip}(y)z_2 \land {Digit}(1,z_1) {Digit}(1,z_2) ]$.
3. ${\forall\,x,y,s\;\;} {State}(s) \land {LivesIn}(x,s) \land {LivesIn}(y,s) {\:\;{\Rightarrow}\:\;}{Digit}(1,{Zip}(x){Zip}(y))$.
4. ${\forall\,x,y,s\;\;} {State}(s) \land {LivesIn}(x,s) \land {LivesIn}(y,s) {\:\;{\Rightarrow}\:\;}{}$\
${Digit}(1,{Zip}(x)) {Digit}(1,{Zip}(y))$.
Complete the following exercises
about logical sentences:
1. Translate into *good, natural* English (no $x$s or $y$s!):
$$
{\forall\,x,y,l\;\;} SpeaksLanguage(x, l) \land SpeaksLanguage(y, l)
\implies Understands(x, y) \land Understands(y,x).
$$
2. Explain why this sentence is entailed by the sentence
$$
{\forall\,x,y,l\;\;} SpeaksLanguage(x, l) \land SpeaksLanguage(y, l)
\implies Understands(x, y).
$$
3. Translate into first-order logic the following sentences:
1. Understanding leads to friendship.
2. Friendship is transitive.
Remember to define all predicates, functions, and constants you use.
True or false? Explain.
1. ${\exists\,x\;\;} x{Rumpelstiltskin}$ is a valid
(necessarily true) sentence of first-order logic.
2. Every existentially quantified sentence in first-order logic is true
in any model that contains exactly one object.
3. ${\forall\,x,y\;\;} xy$is satisfiable.
Rewrite the first two Peano axioms in Section Peano-section as a single axiom that defines ${NatNum}(x)$ so as to exclude the possibility of natural numbers except for those generated by the successor function.
Equation (pit-biconditional-equation) on
page pit-biconditional-equation defines the conditions under which a square is
breezy. Here we consider two other ways to describe this aspect of the
wumpus world.
1. We can write [diagnostic rule] leading from observed effects to hidden causes. For
finding pits, the obvious diagnostic rules say that if a square is
breezy, some adjacent square must contain a pit; and if a square is
not breezy, then no adjacent square contains a pit. Write these two
rules in first-order logic and show that their conjunction is
logically equivalent to
Equation (pit-biconditional-equation).
2. We can write [causal rule] leading from cause to effect. One obvious causal rule
is that a pit causes all adjacent squares to be breezy. Write this
rule in first-order logic, explain why it is incomplete compared to
Equation (pit-biconditional-equation), and supply
the missing axiom.
Write axioms describing the predicates
${Grandchild}$, ${Greatgrandparent}$, ${Ancestor}$, ${Brother}$,
${Sister}$, ${Daughter}$, ${Son}$, ${FirstCousin}$,
${BrotherInLaw}$, ${SisterInLaw}$, ${Aunt}$, and ${Uncle}$. Find
out the proper definition of $m$th cousin $n$ times removed, and write
the definition in first-order logic. Now write down the basic facts
depicted in the family tree in Figure family1-figure.
Using a suitable logical reasoning system, it all the sentences you have
written down, and it who are Elizabeth’s grandchildren, Diana’s
brothers-in-law, Zara’s great-grandparents, and Eugenie’s ancestors.
Write down a sentence asserting that + is a commutative function. Does your sentence follow from the Peano axioms? If so, explain why; if not, give a model in which the axioms are true and your sentence is false.
Explain what is wrong with the following proposed definition of the set
membership predicate
$$ {\forall,x,s;;} x \in {x|s} $$ $$ {\forall,x,s;;} x \in s \implies {\forall,y;;} x \in {y|s} $$
Using the set axioms as examples, write axioms for the list domain, including all the constants, functions, and predicates mentioned in the chapter.
Explain what is wrong with the following proposed definition of adjacent squares in the wumpus world: $${\forall\,x,y\;\;} {Adjacent}([x,y], [x+1, y]) \land {Adjacent}([x,y], [x, y+1])\ .$$
Write out the axioms required for reasoning about the wumpus’s location, using a constant symbol ${Wumpus}$ and a binary predicate ${At}({Wumpus}, {Location})$. Remember that there is only one wumpus.
Assuming predicates ${Parent}(p,q)$ and ${Female}(p)$ and constants
${Joan}$ and ${Kevin}$, with the obvious meanings, express each of
the following sentences in first-order logic. (You may use the
abbreviation $\exists^{1}$ to mean “there exists exactly one.”)
1. Joan has a daughter (possibly more than one, and possibly sons
as well).
2. Joan has exactly one daughter (but may have sons as well).
3. Joan has exactly one child, a daughter.
4. Joan and Kevin have exactly one child together.
5. Joan has at least one child with Kevin, and no children with
anyone else.
Arithmetic assertions can be written in first-order logic with the
predicate symbol $<$, the function symbols ${+}$ and ${\times}$, and the
constant symbols 0 and 1. Additional predicates can also be defined with
biconditionals.
1. Represent the property “$x$ is an even number.”
2. Represent the property “$x$ is prime.”
3. Goldbach’s conjecture is the conjecture (unproven as yet) that every
even number is equal to the sum of two primes. Represent this
conjecture as a logical sentence.
In Chapter csp-chapter, we used equality to indicate the relation between a variable and its value. For instance, we wrote ${WA}{red}$ to mean that Western Australia is colored red. Representing this in first-order logic, we must write more verbosely ${ColorOf}({WA}){red}$. What incorrect inference could be drawn if we wrote sentences such as ${WA}{red}$ directly as logical assertions?
Write in first-order logic the assertion that every key and at least one of every pair of socks will eventually be lost forever, using only the following vocabulary: ${Key}(x)$, $x$ is a key; ${Sock}(x)$, $x$ is a sock; ${Pair}(x,y)$, $x$ and $y$ are a pair; ${Now}$, the current time; ${Before}(t_1,t_2)$, time $t_1$ comes before time $t_2$; ${Lost}(x,t)$, object $x$ is lost at time $t$.
For each of the following sentences in English, decide if the
accompanying first-order logic sentence is a good translation. If not,
explain why not and correct it. (Some sentences may have more than one
error!)
1. No two people have the same social security number.
$$\lnot {\exists\,x,y,n\;\;} {Person}(x) \land {Person}(y) {\:\;{\Rightarrow}\:\;}[{HasSS}\#(x,n) \land {HasSS}\#(y,n)].$$
2. John’s social security number is the same as Mary’s.
$${\exists\,n\;\;} {HasSS}\#({John},n) \land {HasSS}\#({Mary},n).$$
3. Everyone’s social security number has nine digits.
$${\forall\,x,n\;\;} {Person}(x) {\:\;{\Rightarrow}\:\;}[{HasSS}\#(x,n) \land {Digits}(n,9)].$$
4. Rewrite each of the above (uncorrected) sentences using a function
symbol ${SS}\#$ instead of the predicate ${HasSS}\#$.
Translate into first-order logic the sentence “Everyone’s DNA is unique and is derived from their parents’ DNA.” You must specify the precise intended meaning of your vocabulary terms. (*Hint*: Do not use the predicate ${Unique}(x)$, since uniqueness is not really a property of an object in itself!)
For each of the following sentences in English, decide if the
accompanying first-order logic sentence is a good translation. If not,
explain why not and correct it.
1. Any apartment in London has lower rent than some apartments
in Paris.
$$
\forall {x} [{Apt}(x) \land {In}(x,{London})]
\implies \exists {y} ([{Apt}(y) \land {In}(y,{Paris})] \implies ({Rent}(x) < {Rent}(y)))
$$
2. There is exactly one apartment in Paris with rent below \$1000.
$$
\exists {x} {Apt}(x) \land {In}(x,{Paris}) \land \forall{y} [{Apt}(y) \land {In}(y,{Paris}) \land ({Rent}(y) < {Dollars}(1000))] \implies (y = x)
$$
3. If an apartment is more expensive than all apartments in London, it
must be in Moscow.
$$
\forall{x} {Apt}(x) \land [\forall{y} {Apt}(y) \land {In}(y,{London}) \land ({Rent}(x) > {Rent}(y))] \implies
{In}(x,{Moscow}).
$$
Represent the following sentences in first-order logic, using a
consistent vocabulary (which you must define):
1. Some students took French in spring 2001.
2. Every student who takes French passes it.
3. Only one student took Greek in spring 2001.
4. The best score in Greek is always higher than the best score
in French.
5. Every person who buys a policy is smart.
6. No person buys an expensive policy.
7. There is an agent who sells policies only to people who are
not insured.
8. There is a barber who shaves all men in town who do not
shave themselves.
9. A person born in the UK, each of whose parents is a UK citizen or a
UK resident, is a UK citizen by birth.
10. A person born outside the UK, one of whose parents is a UK citizen
by birth, is a UK citizen by descent.
11. Politicians can fool some of the people all of the time, and they
can fool all of the people some of the time, but they can’t fool all
of the people all of the time.
12. All Greeks speak the same language. (Use ${Speaks}(x,l)$ to mean
that person $x$ speaks language $l$.)
Represent the following sentences in first-order logic, using a
consistent vocabulary (which you must define):
1. Some students took French in spring 2001.
2. Every student who takes French passes it.
3. Only one student took Greek in spring 2001.
4. The best score in Greek is always higher than the best score
in French.
5. Every person who buys a policy is smart.
6. No person buys an expensive policy.
7. There is an agent who sells policies only to people who are
not insured.
8. There is a barber who shaves all men in town who do not
shave themselves.
9. A person born in the UK, each of whose parents is a UK citizen or a
UK resident, is a UK citizen by birth.
10. A person born outside the UK, one of whose parents is a UK citizen
by birth, is a UK citizen by descent.
11. Politicians can fool some of the people all of the time, and they
can fool all of the people some of the time, but they can’t fool all
of the people all of the time.
12. All Greeks speak the same language. (Use ${Speaks}(x,l)$ to mean
that person $x$ speaks language $l$.)
Write a general set of facts and axioms to represent the assertion “Wellington heard about Napoleon’s death” and to correctly answer the question “Did Napoleon hear about Wellington’s death?”
Extend the vocabulary from Section circuits-section to define addition for $n$-bit binary numbers. Then encode the description of the four-bit adder in Figure 4bit-adder-figure, and pose the queries needed to verify that it is in fact correct.
The circuit representation in the chapter is more detailed than necessary if we care only about circuit functionality. A simpler formulation describes any $m$-input, $n$-output gate or circuit using a predicate with $m+n$ arguments, such that the predicate is true exactly when the inputs and outputs are consistent. For example, NOT gates are described by the binary predicate ${NOT}(i,o)$, for which ${NOT}(0,1)$ and ${NOT}(1,0)$ are known. Compositions of gates are defined by conjunctions of gate predicates in which shared variables indicate direct connections. For example, a NAND circuit can be composed from ${AND}$s and ${NOT}$s: $${\forall\,i_1,i_2,o_a,o\;\;} {AND}(i_1,i_2,o_a) \land {NOT}(o_a,o) {\:\;{\Rightarrow}\:\;}{NAND}(i_1,i_2,o)\ .$$ Using this representation, define the one-bit adder in Figure adder-figure and the four-bit adder in Figure adder-figure, and explain what queries you would use to verify the designs. What kinds of queries are *not* supported by this representation that *are* supported by the representation in Section circuits-section?
Obtain a passport application for your country, identify the rules determining eligibility for a passport, and translate them into first-order logic, following the steps outlined in Section circuits-section
Consider a first-order logical knowledge base that describes worlds
containing people, songs, albums (e.g., “Meet the Beatles”) and disks
(i.e., particular physical instances of CDs). The vocabulary contains
the following symbols:
> ${CopyOf}(d,a)$: Predicate. Disk $d$ is a copy of album $a$.
> ${Owns}(p,d)$: Predicate. Person $p$ owns disk $d$.
> ${Sings}(p,s,a)$: Album $a$ includes a recording of song $s$ sung by person $p$.
> ${Wrote}(p,s)$: Person $p$ wrote song $s$.
> ${McCartney}$, ${Gershwin}$, ${BHoliday}$, ${Joe}$, ${EleanorRigby}$, ${TheManILove}$, ${Revolver}$: Constants with the obvious meanings.
Express the following statements in first-order logic:
1. Gershwin wrote “The Man I Love.”
2. Gershwin did not write “Eleanor Rigby.”
3. Either Gershwin or McCartney wrote “The Man I Love.”
4. Joe has written at least one song.
5. Joe owns a copy of *Revolver*.
6. Every song that McCartney sings on *Revolver* was
written by McCartney.
7. Gershwin did not write any of the songs on *Revolver*.
8. Every song that Gershwin wrote has been recorded on some album.
(Possibly different songs are recorded on different albums.)
9. There is a single album that contains every song that Joe
has written.
10. Joe owns a copy of an album that has Billie Holiday singing “The Man
I Love.”
11. Joe owns a copy of every album that has a song sung by McCartney.
(Of course, each different album is instantiated in a different
physical CD.)
12. Joe owns a copy of every album on which all the songs are sung by
Billie Holiday.
Prove that Universal Instantiation is sound and that Existential Instantiation produces an inferentially equivalent knowledge base.
From ${Likes}({Jerry},{IceCream})$ it seems reasonable to infer ${\exists\,x\;\;} {Likes}(x,{IceCream})$. Write down a general inference rule, , that sanctions this inference. State carefully the conditions that must be satisfied by the variables and terms involved.
Suppose a knowledge base contains just one sentence,
$\exists\,x\ {AsHighAs}(x,{Everest})$. Which of the following are
legitimate results of applying Existential Instantiation?
1. ${AsHighAs}({Everest},{Everest})$.
2. ${AsHighAs}({Kilimanjaro},{Everest})$.
3. ${AsHighAs}({Kilimanjaro},{Everest}) \land {AsHighAs}({BenNevis},{Everest})$\
(after two applications).
For each pair of atomic sentences, give the most general unifier if it
exists:
1. $P(A,B,B)$, $P(x,y,z)$.
2. $Q(y,G(A,B))$, $Q(G(x,x),y)$.
3. ${Older}({Father}(y),y)$, ${Older}({Father}(x),{John})$.
4. ${Knows}({Father}(y),y)$, ${Knows}(x,x)$.
For each pair of atomic sentences, give the most general unifier if it
exists:
1. $P(A,B,B)$, $P(x,y,z)$.
2. $Q(y,G(A,B))$, $Q(G(x,x),y)$.
3. ${Older}({Father}(y),y)$, ${Older}({Father}(x),{John})$.
4. ${Knows}({Father}(y),y)$, ${Knows}(x,x)$.
Consider the subsumption lattices shown
in Figure subsumption-lattice-figure
(page subsumption-lattice-figure
.
1. Construct the lattice for the sentence
${Employs}({Mother}({John}),{Father}({Richard}))$.
2. Construct the lattice for the sentence ${Employs}({IBM},y)$
(“Everyone works for IBM”). Remember to include every kind of query
that unifies with the sentence.
3. Assume that indexes each sentence under every node in its
subsumption lattice. Explain how should work when some of these
sentences contain variables; use as examples the sentences in (a)
and (b) and the query ${Employs}(x,{Father}(x))$.
Write down logical representations for the
following sentences, suitable for use with Generalized Modus Ponens:
1. Horses, cows, and pigs are mammals.
2. An offspring of a horse is a horse.
3. Bluebeard is a horse.
4. Bluebeard is Charlie’s parent.
5. Offspring and parent are inverse relations.
6. Every mammal has a parent.
These questions concern concern issues with substitution and
Skolemization.
1. Given the premise ${\forall\,x\;\;} {\exists\,y\;\;} P(x,y)$, it is
not valid to conclude that ${\exists\,q\;\;} P(q,q)$. Give an
example of a predicate $P$ where the first is true but the second
is false.
2. Suppose that an inference engine is incorrectly written with the
occurs check omitted, so that it allows a literal like $P(x,F(x))$
to be unified with $P(q,q)$. (As mentioned, most standard
implementations of Prolog actually do allow this.) Show that such an
inference engine will allow the conclusion ${\exists\,y\;\;} P(q,q)$
to be inferred from the premise
${\forall\,x\;\;} {\exists\,y\;\;} P(x,y)$.
3. Suppose that a procedure that converts first-order logic to clausal
form incorrectly Skolemizes
${\forall\,x\;\;} {\exists\,y\;\;} P(x,y)$ to $P(x,Sk0)$—that is, it
replaces $y$ by a Skolem constant rather than by a Skolem function
of $x$. Show that an inference engine that uses such a procedure
will likewise allow ${\exists\,q\;\;} P(q,q)$ to be inferred from
the premise ${\forall\,x\;\;} {\exists\,y\;\;} P(x,y)$.
4. A common error among students is to suppose that, in unification,
one is allowed to substitute a term for a Skolem constant instead of
for a variable. For instance, they will say that the formulas
$P(Sk1)$ and $P(A)$ can be unified under the substitution
$\{ Sk1/A \}$. Give an example where this leads to an
invalid inference.
This question considers Horn KBs, such as the following:
$$\begin{array}{l}
P(F(x)) {\:\;{\Rightarrow}\:\;}P(x)\\
Q(x) {\:\;{\Rightarrow}\:\;}P(F(x))\\
P(A)\\
Q(B)
\end{array}$$ Let FC be a breadth-first forward-chaining algorithm that
repeatedly adds all consequences of currently satisfied rules; let BC be
a depth-first left-to-right backward-chaining algorithm that tries
clauses in the order given in the KB. Which of the following are true?
1. FC will infer the literal $Q(A)$.
2. FC will infer the literal $P(B)$.
3. If FC has failed to infer a given literal, then it is not entailed
by the KB.
4. BC will return ${true}$ given the query $P(B)$.
5. If BC does not return ${true}$ given a query literal, then it is
not entailed by the KB.
Explain how to write any given 3-SAT problem of arbitrary size using a single first-order definite clause and no more than 30 ground facts.
Suppose you are given the following axioms:
1. $0 \leq 3$.
2. $7 \leq 9$.
3. ${\forall\,x\;\;} \; \; x \leq x$.
4. ${\forall\,x\;\;} \; \; x \leq x+0$.
5. ${\forall\,x\;\;} \; \; x+0 \leq x$.
6. ${\forall\,x,y\;\;} \; \; x+y \leq y+x$.
7. ${\forall\,w,x,y,z\;\;} \; \; w \leq y$ $\wedge$ $x \leq z$ ${\:\;{\Rightarrow}\:\;}$ $w+x \leq y+z$.
8. ${\forall\,x,y,z\;\;} \; \; x \leq y \wedge y \leq z \: {\:\;{\Rightarrow}\:\;}\: x \leq z$
1. Give a backward-chaining proof of the sentence $7 \leq 3+9$. (Be
sure, of course, to use only the axioms given here, not anything
else you may know about arithmetic.) Show only the steps that leads
to success, not the irrelevant steps.
2. Give a forward-chaining proof of the sentence $7 \leq 3+9$. Again,
show only the steps that lead to success.
Suppose you are given the following axioms:
> 1. $0 \leq 4$.
> 2. $5 \leq 9$.
> 3. ${\forall\,x\;\;} \; \; x \leq x$.
> 4. ${\forall\,x\;\;} \; \; x \leq x+0$.
> 5. ${\forall\,x\;\;} \; \; x+0 \leq x$.
> 6. ${\forall\,x,y\;\;} \; \; x+y \leq y+x$.
> 7. ${\forall\,w,x,y,z\;\;} \; \; w \leq y$ $\wedge$ $x \leq z {\:\;{\Rightarrow}\:\;}$ $w+x \leq y+z$.
> 8. ${\forall\,x,y,z\;\;} \; \; x \leq y \wedge y \leq z \: {\:\;{\Rightarrow}\:\;}\: x \leq z$
1. Give a backward-chaining proof of the sentence $5 \leq 4+9$. (Be
sure, of course, to use only the axioms given here, not anything
else you may know about arithmetic.) Show only the steps that leads
to success, not the irrelevant steps.
2. Give a forward-chaining proof of the sentence $5 \leq 4+9$. Again,
show only the steps that lead to success.
A popular children’s riddle is “Brothers and sisters have I none, but that man’s father is my father’s son.” Use the rules of the family domain (Section kinship-domain-section on page kinship-domain-section to show who that man is. You may apply any of the inference methods described in this chapter. Why do you think that this riddle is difficult?
Suppose we put into a logical knowledge base a segment of the
U.S. census data listing the age, city of residence, date of birth, and
mother of every person, using social security numbers as identifying
constants for each person. Thus, George’s age is given by
${Age}(\mbox443-{65}-{1282}}, {56})$. Which of the following
indexing schemes S1–S5 enable an efficient solution for which of the
queries Q1–Q4 (assuming normal backward chaining)?
- S1: an index for each atom in each position.
- S2: an index for each first argument.
- S3: an index for each predicate atom.
- S4: an index for each combination of predicate and first argument.
- S5: an index for each combination of predicate and second argument and an index for each first argument.
- Q1: ${Age}(\mbox 443-44-4321,x)$
- Q2: ${ResidesIn}(x,{Houston})$
- Q3: ${Mother}(x,y)$
- Q4: ${Age}(x,{34}) \land {ResidesIn}(x,{TinyTownUSA})$
One might suppose that we can avoid the problem of variable conflict in unification during backward chaining by standardizing apart all of the sentences in the knowledge base once and for all. Show that, for some sentences, this approach cannot work. (Hint: Consider a sentence in which one part unifies with another.)
In this exercise, use the sentences you wrote in
Exercise <a href="#>fol-horses-exercise</a> to answer a question by
using a backward-chaining algorithm.
1. Draw the proof tree generated by an exhaustive backward-chaining
algorithm for the query ${\exists\,h\;\;}{Horse}(h)$, where
clauses are matched in the order given.
2. What do you notice about this domain?
3. How many solutions for $h$ actually follow from your sentences?
4. Can you think of a way to find all of them? (Hint:
See @Smith+al:1986.)
Trace the execution of the backward-chaining algorithm in Figure backward-chaining-algorithm (page backward-chaining-algorithm when it is applied to solve the crime problem (page west-problem-page. Show the sequence of values taken on by the ${goals}$ variable, and arrange them into a tree.
The following Prolog code defines a predicate P. (Remember
that uppercase terms are variables, not constants, in Prolog.)
P(X,[X|Y]).
P(X,[Y|Z]) :- P(X,Z).
1. Show proof trees and solutions for the queries
P(A,[2,1,3]) and P(2,[1,A,3]).
2. What standard list operation does P represent?
The following Prolog code defines a predicate P. (Remember
that uppercase terms are variables, not constants, in Prolog.)
P(X,[X|Y]).
P(X,[Y|Z]) :- P(X,Z).
1. Show proof trees and solutions for the queries
P(A,[1,2,3]) and P(2,[1,A,3]).
2. What standard list operation does P represent?
This exercise looks at sorting in Prolog.
1. Write Prolog clauses that define the predicate
sorted(L), which is true if and only if list
L is sorted in ascending order.
2. Write a Prolog definition for the predicate perm(L,M),
which is true if and only if L is a permutation of
M.
3. Define sort(L,M) (M is a sorted version of
L) using perm and sorted.
4. Run sort on longer and longer lists until you lose
patience. What is the time complexity of your program?
5. Write a faster sorting algorithm, such as insertion sort or
quicksort, in Prolog.
This exercise looks at the recursive
application of rewrite rules, using logic programming. A rewrite rule
(or demodulator in terminology) is an
equation with a specified direction. For example, the rewrite rule
$x+0 \rightarrow x$ suggests replacing any expression that matches $x+0$
with the expression $x$. Rewrite rules are a key component of equational
reasoning systems. Use the predicate rewrite(X,Y) to
represent rewrite rules. For example, the earlier rewrite rule is
written as rewrite(X+0,X). Some terms are
primitive and cannot be further simplified; thus, we
write primitive(0) to say that 0 is a primitive term.
1. Write a definition of a predicate simplify(X,Y), that
is true when Y is a simplified version of
X—that is, when no further rewrite rules apply to any
subexpression of Y.
2. Write a collection of rules for the simplification of expressions
involving arithmetic operators, and apply your simplification
algorithm to some sample expressions.
3. Write a collection of rewrite rules for symbolic differentiation,
and use them along with your simplification rules to differentiate
and simplify expressions involving arithmetic expressions,
including exponentiation.
This exercise considers the implementation of search algorithms in Prolog. Suppose that successor(X,Y) is true when state Y is a successor of state X; and that goal(X) is true when X is a goal state. Write a definition for solve(X,P), which means that P is a path (list of states) beginning with X, ending in a goal state, and consisting of a sequence of legal steps as defined by successor. You will find that depth-first search is the easiest way to do this. How easy would it be to add heuristic search control?
Suppose a knowledge base contains just the following first-order Horn
clauses:
$$
Ancestor(Mother(x),x)
$$
$$
Ancestor(x,y) \land Ancestor(y,z) \implies Ancestor(x,z)
$$
Consider a forward chaining algorithm that, on the $j$th iteration,
terminates if the KB contains a sentence that unifies with the query,
else adds to the KB every atomic sentence that can be inferred from the
sentences already in the KB after iteration $j-1$.
1. For each of the following queries, say whether the algorithm
will (1) give an answer (if so, write down that answer); or (2)
terminate with no answer; or (3) never terminate.
1. $Ancestor(Mother(y),John)$
2. $Ancestor(Mother(Mother(y)),John)$
3. $Ancestor(Mother(Mother(Mother(y))),Mother(y))$
4. $Ancestor(Mother(John),Mother(Mother(John)))$
2. Can a resolution algorithm prove the sentence
$\lnot Ancestor(John,John)$ from the original knowledge base?
Explain how, or why not.
3. Suppose we add the assertion that $\lnot(Mother(x)x)$ and
augment the resolution algorithm with inference rules for equality.
Now what is the answer to (b)?
Let $\cal L$ be the first-order language with a single predicate
$S(p,q)$, meaning “$p$ shaves $q$.” Assume a domain of people.
1. Consider the sentence “There exists a person $P$ who shaves every
one who does not shave themselves, and only people that do not
shave themselves.” Express this in $\cal L$.
2. Convert the sentence in (a) to clausal form.
3. Construct a resolution proof to show that the clauses in (b) are
inherently inconsistent. (Note: you do not need any
additional axioms.)
How can resolution be used to show that a sentence is valid? Unsatisfiable?
Construct an example of two clauses that can be resolved together in two different ways giving two different outcomes.
From “Horses are animals,” it follows that “The head of a horse is the
head of an animal.” Demonstrate that this inference is valid by carrying
out the following steps:
1. Translate the premise and the conclusion into the language of
first-order logic. Use three predicates: ${HeadOf}(h,x)$ (meaning
“$h$ is the head of $x$”), ${Horse}(x)$, and ${Animal}(x)$.
2. Negate the conclusion, and convert the premise and the negated
conclusion into conjunctive normal form.
3. Use resolution to show that the conclusion follows from the premise.
From “Sheep are animals,” it follows that “The head of a sheep is the
head of an animal.” Demonstrate that this inference is valid by carrying
out the following steps:
1. Translate the premise and the conclusion into the language of
first-order logic. Use three predicates: ${HeadOf}(h,x)$ (meaning
“$h$ is the head of $x$”), ${Sheep}(x)$, and ${Animal}(x)$.
2. Negate the conclusion, and convert the premise and the negated
conclusion into conjunctive normal form.
3. Use resolution to show that the conclusion follows from the premise.
Here are two sentences in the language of
first-order logic:
- (A)
${\forall\,x\;\;} {\exists\,y\;\;} ( x \geq y )$
- (B)
${\exists\,y\;\;} {\forall\,x\;\;} ( x \geq y )$
1. Assume that the variables range over all the natural numbers
$0,1,2,\ldots, \infty$ and that the “$\geq$” predicate means “is
greater than or equal to.” Under this interpretation, translate (A)
and (B) into English.
2. Is (A) true under this interpretation?
3. Is (B) true under this interpretation?
4. Does (A) logically entail (B)?
5. Does (B) logically entail (A)?
6. Using resolution, try to prove that (A) follows from (B). Do this
even if you think that (B) does not logically entail (A); continue
until the proof breaks down and you cannot proceed (if it does
break down). Show the unifying substitution for each resolution
step. If the proof fails, explain exactly where, how, and why it
breaks down.
7. Now try to prove that (B) follows from (A).
Resolution can produce nonconstructive proofs for queries with variables, so we had to introduce special mechanisms to extract definite answers. Explain why this issue does not arise with knowledge bases containing only definite clauses.
We said in this chapter that resolution cannot be used to generate all logical consequences of a set of sentences. Can any algorithm do this?
Consider a robot whose operation is described by the following PDDL
operators:
$$
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.
2. Assuming that these are the only actions in the world, write a
successor-state axiom for $EmptyHand$.
Describe the differences and similarities between problem solving and planning.
strips-airport-exerciseGiven the action schemas and initial state
from Figure airport-pddl-algorithm, what are all the
applicable concrete instances of ${Fly}(p,{from},{to})$ in the
state described by
$$
At(P_1,JFK) \land At(P_2,SFO) \land Plane(P_1) \land Plane(P_2) \land Airport(JFK) \land Airport(SFO)?
$$
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.