exam 1 Flashcards
Represent in propositional logic: It is hot but not sunny.
H ∧ ¬S
If we used an inadmissible heuristic in A∗ tree search, could it change the completeness of the search?
No, If the heuristic function is bounded, then A∗ would visit all the nodes eventually, and would find
a path to the goal state if there exists one.
Deduction: What is AND introduction
If A is true and B is true, we can say A ∧ B is true
What is the difference between a world state, a state description and a search node? Why is this
distinction useful?
State descriptions are lossy abstractions of the world state.
Search nodes are generated during search, representing a state the search process knows how to reach. They
contain additional information aside from the state description, such as the sequence of actions used to reach this state. This distinction is useful because we may generate different search nodes which have the same state, and because search nodes contain more information than a state representation.
If we used an inadmissible heuristic in A∗ tree search, could it change the optimality of the search?
Yes, It can make the good optimal goal look as though it is very far off, and take you to a suboptimal
goal.
Represent in propositional logic: One should not bike on highways.
H → ¬B
Represent in propositional logic: If one has a fever, one should not go to work.
F → ¬W
How to do resolution-only reduction
- Convert to CNF clauses
- Add the inverse of the query to the clauses
- use the tree to join clauses until proven that no solutions exist (proof by contradiction)
Convert to clausal form: A ↔ (B ∨ E)
(¬A ∨ B ∨ E) ∧ (¬B ∨ A) ∧ (¬E ∨ A)
Form of CNF?
(A u B) n (C u D)
T/F: There exists task environments in which every agent is rational.
True. For example, in an environment with a single state, such that all actions have the same reward,
it doesn’t matter which action is taken. More generally, any environment that is reward-invariant under
permutation of the actions will satisfy this property.
T/F: Suppose an agent selects its actions uniformly at random from a set of possible actions, there exists a
deterministic task environment for which this agent is optimal.
True. This is a special case of (c); if it doesn’t matter which action you take, selecting randomly is
rational.
Represent in propositional logic: Do not drink or text when driving.
C → ¬(D ∨ T )
T/F: It is possible for an agent to be perfectly rational in two distinct environments.
True. For example, we can arbitrarily modify the parts of the environment that are unreachable by
any optimal policy as long as they stay unreachable.
T/F: There exists task environments in which no pure reflex agent can behave rationally
True. A pure reflex agent ignores previous percepts, so cannot obtain an optimal state estimate in
a partially observable environment. For example, correspondence chess is played by sending moves; if the
other player’s move is the current percept, a reflex agent could not keep track of the board state and would
have to respond to, say, a4 in the same way regardless of the position in which it was played.
Give a general advantage that an inadmissible heuristic might have over an admissible one.
The time to solve an A∗ search problem is a function of two factors: the number of nodes expanded,
and the time spent per node.
An inadmissible heuristic may be faster to compute, leading to a solution that is obtained faster due to less
time spent per node. It can also be a closer estimate to the actual cost function (even though at times it will
overestimate!), thus expanding less nodes.
It’s important to remember that we definitely lose the guarantee of optimality by using an inadmissible
heuristic. But sometimes we may be okay with finding a suboptimal solution to a search problem.
Convert to clausal form: E → D
¬E ∨ D
Deduction: What is Modus Ponens
If A and (A → B) is true, then B must be true
T/F: Every agent is implementable by some program/machine combination.
False. For example, the environment may contain Turing machines and input tapes and the agent’s
job is to solve the halting problem; there is an agent function that specifies the right answers, but no agent
program can implement it. Another example would be an agent function that requires solving intractable
problem instances of arbitrary size in constant time.
How to do normal deduction
Use AND introduction and Modus Ponens and rules to derive the formula that needs to be deduced
CNF: Contraposition of (A → B)?
(A → B) = (¬B → ¬A)
CNF equivalency: A ↔ B
(A → B) ∧ (B → A)
T/F: The input to an agent program is the same as the input to agent function.
False. The agent function, notionally speaking, takes as input the entire percept sequence up to that
point, whereas the agent program takes the current percept only.
Convert to clausal form: C ∧ D → ¬B
¬C ∨ D ∨ ¬B
What does it mean when an agent is rational?
When it acts to the optimal move GIVEN the input. This may not be the overall perfect move but it is given the percepts/input/history
T/F: An agent that senses only partial information about the state cannot be perfectly rational.
False. Perfect rationality refers to the ability to make good decisions given the sensor information
received.
CNF equivalency: A → B
¬A ∨ B
