Brainscape's Knowledge GenomeTM

Browse over 1 million classes created by top students, professors, publishers, and experts.


See full index

CPSC 322: Artificial Intelligence > Final: Logic > Flashcards

Final: Logic Flashcards

1
Q

(L18) Explain the STRIPS assumption

A

All features not explicitly changed by an action stay unchanged

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

(L18) Represent a planning problem with the STRIPS representation

A

Preconditions: Set of assignments must be satisfied for the action to be legal
Effects: Assignments caused by the action

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q 
(L18) Planning problem:
State
Goal
Successor function
Solution
A

State: Agent in a possible world. All variables have an assignment
Goal: A possible world with specific assignments
Successor function: Actions that take agent from one state to the other
Solution: A sequence of actions to the goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

(L18) What are arcs, and plan?

A

Arcs: Actions that are legal from that state
Plan: A sequence of actions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

(L18) What is empty-delete-list?

A

Remove all the effects that make a variable false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

(L18) What is a subgoal?

A

Particular assignment in the goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

(L18) What simplifications do we take for Forward Planning under STRIPS?

A
  1. All features are binary: T/F

2. Preconditions and goals can only be assignments to T

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

(L18) Heuristic for planning

A

Number of actions from a state to the goal

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

(L18) What are the steps to translate a planning problem represented in STRIPS into a CSP problem (and vice versa? (3 steps)

A
  1. Construct a CSP variable for each STRIPS variable at each time step
    from 0 to k.
  2. Construct a boolean CSP variable (action taken of not taken) for each STRIPS action (eg. a_1, a_2) at each time step from 0 to k - 1.
  3. Construct CSP constraints corresponding to start and goal values, preconditions and effects of actions.
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

(L18) What type of constraints are needed to translate from STRIPS to CSP problem?

A
  1. Initial constraints: Constrain state variable at time 0.
  2. Goal constraints: constrain state variables at time k.
  3. Precondition constraints
    between states and actions at time t
    specify which actions may be taken (ONE PER ACTION VARIABLE)
  4. Effect constraints:
    Between state, actions variables at time t and state variables at time t + 1. (ONE PER STATE VARIABLE AT TIME T + 1)
    Explains Actions(t) + State(t) → State(t+1)
  5. Mutual Exclusion constraints: Actions that cannot occur simultaneously
  6. State constraints:
    Between variables at the same time step
    Capture physical constraints of the system
    Can encode maintenance goals
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

(L18) Solve a planning problem with CSP by expanding the horizon.

A

Expand the constraint network one “time step” at a time. (i.e. “unrolling the horizon”), until a solution is found.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

(L18) Given that the CSP return a solution, are there shorter solutions?

A

IF THE CSP STOPS AND RETURNS A SOLUTION OF LENGTH K, THEN THERE ARE NO SHORTER SOLUTIONS

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

(L18) How do we know a logical statement belongs to the language of full propositional logic?

A

~ Negation, and conjunction, or disjunction, –> implication, biconditional

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

(L18) How do we use logics to make inferences?

A

Using logics to Make inferences
1. Begin with a task domain
Distinguish those things you want to reason about
Choose symbols in the computer to denote propositions
Tell the system knowledge about the domain
Ask the system whether new statements about the domain are true or false

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
15
Q

(L18) When a logical statement belongs to the language of propositional definite clauses?

A
  1. True statements

2. True statements given other true statements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
16
Q

(L18) Benefits of propositional definite clause

A
  1. Adequate in many domains (with some adjustments)
  2. Reasoning is easy to follow by humans
  3. Inference linear in the size of your set of statements.
  4. Used in cognitive architectures
17
Q

(L18) What is an atom?

A

lower case letter symbol

18
Q

(L18) What is a body?

A

an atom or b1 ^ b2, where b1, and b2 are bodies

19
Q

(L18) What is a definite clause?

A
  1. an atom

2. a rule of the form head ← body

20
Q

(L18) What is a knowledge base?

A

A set of facts and logical formulas that are true

21
Q

(L18) What is an interpretation?

A

An interpretation assigns a truth value to each atom / possible world

22
Q

(L19) How do we know an interpretation is a model of a Knowledge Base?

A

An interpretation is a model when it is true for all set of clauses in the KB

23
Q

(L19) When a conjunction of atoms G is a logical consequence of a knowledge base?

A

When G is true in every model of KB, then KB ⊧ G. Also, when there is no interpretation in which KB is true and G is false.

KB entails G
G logically follows from KB
G is a logical consequence of KB

24
Q

(L19) What does KB ⊦ G mean?

A

G can be derived by my proof procedure from KB.

25
Q

(L19) What is soundness?

A

if KB ⊦ G implies KB ⊧ G. (doesn’t make mistakes) (derived) → (entailed)

26
Q

(L19) What is completeness?

A

if KB ⊧ G implies KB ⊦ G. (finds everything that is entailed) (entailed) → (derived)

27
Q

(L19) What is the bottom-up proof procedure?

A

if h ← b_1 ^ … ^ b_3 is a clause in the knowledge base, and b_i has been derived, then h can be derived.

28
Q

(L19) KB ⊦ G, using bottom up

A

Let C be the set of all things that the Bottom-Up procedure can derive
KB ⊦ G if G is a subset of C at the end of the bottom-up proof procedure

29
Q

(L20) Prove that the Bottom-Up proof procedure is both sound and complete

A

Soundness of Bottom-Up Proof Procedure

  1. Suppose Bottom-Up is not sound → there is one element C that is not entailed by KB
  2. Let h de the first atom added to C that is not entailed by KB
  3. Let M be a model of KB
  4. Suppose h isn’t true in M
  5. There must be a clause of the form h ← b_1 … b_2 = F ← T…T
  6. Then, M is false
  7. Thus M is not a model of KB (CONTRADICTION)
  8. No such h exists, and the Bottom-up procedure is sound
30
Q

(L20) Given that a domain can be represented with n propositions, how many interpretations?

A

2^n interpretations (possible worlds)

31
Q

(L20) What is the minimal model?

A

Interpretation in which every element of C is true, and every other atom is false.

32
Q

(L20) Prove that the Bottom-Up proof procedure is complete

A
  1. Suppose KB ⊧ G
  2. Then G is true in all models of KB
  3. Thus G is true in the minimal model
  4. Thus G ⊆ C
  5. Thus KB ⊦ G
33
Q

(L20) Prove that if G is true in the minimal model, then G is derived from KB by the Bottom-Up algorithm

A

We define a particular interpretation I such that iff G is true in I, then G is derived from KB by the Bottom-Up procedure.

Proof by Contradiction:

  1. Assume that I is not a model of KB
  2. Then there must exist a clause h ← b_1, …, b_m, where b_i = T and h = F (i.e. h is not in C)
  3. But if b_i belonged to C, Bottom-Up would have added h to C.
  4. So there is no clause in KB that is false in interpretation I
  5. Thus I is a model of KB.
34
Q

Model a relatively simple domain with propositional definite clause logic (PDCL)

A
  1. Define relevant propositions (objects)
  2. Define relevant rules
  3. Establish known facts
  4. Put together the knowledge base
35
Q

What is the SLD resolution (Rule of inference)?

A

Given an answer clause of the form:
yes ← a_1, …, a_m
a_i ← b_1, …, b_p

Then, yes ← a_1, …, a_i-1, b_1, …, b_p, a_i+1, …, a_m

36
Q

What do we gain from turning propositions into relations applied to individuals?

A
  1. More natural to consider individuals and their properties/ relationships
    up(switch2), up(switch3), ok(circuitbreaker1)
  2. Express knowledge that holds for a set of individuals (using variables)
    live(W) ← connected_to(W, W1), live(W1), wire(W), wire(W1)
  3. We can ask generic queries
    ? connected_to(W, w1)
37
Q

What heuristics can we use for top-down search graphs? Justify admissibility

A
  1. Number of unique atoms in the answer clause –> il will take at least number of atoms to solve the clause, it will never be an overestimate.
  2. Minimizing answer clause length –> replace atoms for shorter clauses, longer clauses –> bigger trees –> more chances to get stuck
  3. If the body of an answer clause contains a symbol that does not match the head of any clause in the KB, then the heuristic value for that answer clause is INFINITY
38
Q

What is an variable, constant, term, predicate symbol, atom, definite clause, knowledge base in DataLog?

A
  • Variable: is a symbol with uppercase letter (X, Y)
  • Constant: symbol with a lowercase letter or sequence of digits (alan, w1)
    term: either a variable or a constant (X, Y, alan, w1)
  • Predicate symbol: symbol starting with a lower-case letter. (i.e. live, connected, part-of, in)
  • Atom: symbol of the form p or p(t1, …, tn), where is a proposition or predicate symbol. (i.e. sunny, in(alan))
  • Definite clause: an atom or h ← b1, …, bm
  • Knowledge base: is a set of definite clauses

CPSC 322: Artificial Intelligence (2 decks)

Brainscape helps you reach your goals faster, through stronger study habits.
© 2024 Bold Learning Solutions. Terms and Conditions