Transcript Review for Final - Columbia University

Final Exam



Tuesday, December 21st, 4:10-7pm
717 Hamilton
Cumulative exam
•
Slightly more focus on second half of class
• Logic and inference
• First order logic
• Planning
• Probabilistic Reasoning and Bayes Nets
• Machine learning
• Robotics
• Vision
• Natural Language processing
1
Review for Final
Propositional Logic
First Order Logic
Planning
Logics



A logic is
• Formal language for representing knowledge
• Mechanism for reasoning
Propositional vs. first-order logic
• Atomic facts vs. objects and relations
Connectives and evaluating truth tables
• ⌐ΛV
3
Semantics in propositional logic

Model = A possible world
• an assignment of truth values to each propositional
symbol

A model of a sentence is an
interpretation in which the sentence
evaluates to True
4
Syntax of FOL: basic elements







Constants: Hari, Michel, Elena
Predicates: knows, adjacent, >
Functions: Sqrt, father-of
Variables: x,y,a,b
Connectives: Λ,V,⌐,→,↔
Equality: =
Quantifiers: ,
5
Universal quantification



<variables> <sentence>
Everyone at Columbia is smart:
x At(x,Columbia)  Smart(x)
x P is true in a model m iff P with x being
each possible object in the model
At (Helen, Columbia)  Smart(Helen)
At (Ramya, Columbia)  Smart (Ramya)
At (Melissa, Columbia)  Smart (Melissa)
At (Anya, Columbia)  Smart (Anya)
…..
6
Existential Quantification




<variables> <sentence>
Someone at Columbia is smart
x At(x,Columbia) Smart(x)
 x P is true in a model m iff P with x being each possible
object in the model
Equivalent to the disjunction of instantiations of P
•
At(Helen, Columbia) ΛSmart(Helen)
V At(Ramya, Columbia) Λ Smart(Ramya)
V At(Melissa, Columbia) Λ Smart(Melissa)
V At (Dina, Columbia) Λ Smart(Dina)
V At (Anya, Columbia) Λ Smart(Anya)
7
Inference

Entailment
• A KB entails α iff every model of KB is also a model of

Inference by enumeration
Inference as search

Inference rules

• E.g., goal-directed
• E.g., and-elimination, or-elimination, modus ponens, unit
resolution, resolution


α
Backward chaining, forward chaining
Resolution
8
9
10
To Make Inferences in FOL

Method 1

Method 2
• Unification of variables with literals (in the KB)
• Generalized Modus Ponens
• Forward-chaining or Backward-chaining
• Resolution
11
Refutation/Resolution




Introduce negated sentence
Convert to a CNF (disjunction of terms, or
“literals”)
Apply resolution search to determine
satisfiability (SAT) or unsatsifiability (UNSAT)
SAT, then not entailed
• Semi-decidability implies there may be a SAT
solution we can never find

UNSAT, then entailed
12
Inference Properties

Inference method A is sound (or truthpreserving) if it only derives entailed sentences

Inference method A is complete if it can derive
any sentence that is entailed

A proof is a record of the progress of a sound
inference algorithm.
13
Required Planning Components

Expressive Formal Language:
• Initial state of world
• Description of the agent’s goal
• Description of the possible actions that can be
performed

Solver generates a sequence of actions
which achieve the goal
• Key idea will be to use structure to extract
admissable heuristics automatically
14
STRIPS language
(Fikes&Nilsson 71)

State is a conjunction of positive ground literals

Goal is a conjunction of positive ground literals

Action schemas

To know:
• No variables and no functions
• AT(,Kathy,Gate70), Weight-limit-lifted(CO36)
• At(Kathy,Denver)Λ⌐onboard(Kathy,C036)
• Conjunction of positive literals as preconditions
• Conjunction of positive and negative literals as effects
• Closed world assumption
• Limits on expressibility
15
Action Schema



Action: Go(p,x,y)
Precond: At(P,x)
Effect: ⌐At(p,x)
At(p,y)
delete list add list
16
Planning Algorithms


Forward vs. Backward search
Partial-order vs. Total-order
• Partial: search in plan space
• Can work on several subgoals independently, solve
and then combine subplans
• Total: search in state space
• Search linear sequence of actions directly
connected to the start or the goal
17
Forward State Space Search





State: positive ground literals
Initial state: set of initial world literals
Search operator:
Choose an action A that
•
•
1.preconditions are satisfied (perhaps finding a unifier)
Construct the new search state
• Add all positive effects; remove all negative effects
Solution: when current state is goal state
18
Backward State-Space Search



State: set of positive ground literals
Initial state: set of goal literals
Search operator:
choose an action A that
1. Is relevant; has one of the goal literals in its effect set
2. Is consistent; does not negate another literal
Then perform regression
3. Construct the new search state
•
•

Remove all positive effects of A that appear in G
Add all preconditions, unless already appears
Solution: when current state is initial world state
19
Heuristics
Neither forward or backward search efficient without
heuristics
 No precondition assumption
•



Remove all preconditions from actions
Subgoal independence
•
Cost of solving a conjunction of subgoals is estimated by cost
of each subgoal
No negative effects assumption
•
Remove all negative effects from actions
Set covering
•
Find the minimal actions such that the union of effects covers
the goal
20
Partial Order Planning

Problem decomposition

Flexibility in order of plan construction
Least commitment

• Work on subgoals independently
• Solve subgoals with subplans
• Combine subplans
21
Partial Plans

A set of actions, including Start and
Finish
A set of ordering constraints (e.g., AB)
A set of causal links

Set of open preconditions


• A→pB: “A achieves p for B”
22