COMP6032 - AI Flashcards
What are the 5 types of Agent and what is the difference between them?
Simple Reflex Agents
- Acts solely what it can see.
- Cannot solve problems requiring memory.
Agents with State
- Has basic memory, so can act on previous percepts as well as current.
Goal-based Agents
- Choose an action based on the goal.
- Doesn’t just react, but also plans.
Utility-based Agents
- Extended Goal-based which looks for an optimal solution.
Learning Agents
- Behaviour changes based on feedback from the environment.
What are some examples of Informed and Uninformed Search?
Informed
- Dijkstra’s Algorithm
- A*
Uninformed
- BFS
- DFS
- Iterative Deepening
What is the difference between Weak AI and Strong AI?
Weak AI is designed to a Goal or a Behaviour whereas Strong AI actually has a mind and complete human-like autonomy.
Strong AI does not exist in the real world.
What does PEAS stand for?
Performance Measure - criteria for success.
Environment
Actuators
Sensors
What is the Minimax algorithm?
Minimax is a Game Theory algorithms with 2 agents.
The maximiser will make decisions to maximise their score.
The minimiser will make decisions to minimise the maximiser’s score.
Both players know that the other will play their move by the opposite extreme, and will make their own decisions accordingly
It can be computed recursively.
What is Alpha-Beta Pruning?
Alpha-Beta Pruning is an optimisation over the Minimax algorithm where branches that have not been fully evaluated may be dismissed based on a partial evaluation.
When we compute the decision for a particular turn, rather than computing all of the results and selecting the minimum/maximum, we update a temporary state after every option is computed; <= or >= x.
Consider a 1-turn-per-player game with 2 choices per turn where the maximiser starts.
The 4 possible options that the second player (minimiser) can choose from on the final turn are 3, 4, 2 and 5.
The maximiser will evaluate their first choice as min(3,4) = 3.
When computing the second turn, they will see the 2 and know that the value of that choice is <= 2.
If x <= 2, we know that 3 > x; therefore the 5 (or any number of subsequent branches) does not need to be considered.
What is Propositional Logic?
The simplest type of Logic.
There are two tokens:
= Sentences / statements
= Connectives / operators
== Conjunction (AND ‘∧’)
== Disjunction (OR ‘∨’)
== Implication (‘⇒’)
=== If A is true, B must also be true for the output to be true.
=== If A is false, then the output is just true.
== Biconditional (‘⇔’)
=== Output is true if A and B are equal.
Are the following equivalent?
(P=>Q)∨(¬Q)
¬P∨Q
(Propositional Logic)
No.
The first is a Tautology (always True).
The second if False when P = True, Q = False.
What is Modus Ponens?
With propositions:
- A => B
- A is true
We can conclude B is true.
What is Modus Tollens?
With propositions:
- A => B
- B is false
We can conclude that A is false.
Determine whether the following argument is valid using logical reasoning:
= Premises:
== If it rains, then the ground is wet.
== The ground is not wet.
= Conclusion:
== It did not rain.
(Propositional Logic)
Premises:
- R => W
- ¬W is true
Modus Tollens:
A => B and ¬B is true implies A is false
Therefore:
- R is false.
- The stated conclusion is correct.
Determine whether the following argument is valid using logical reasoning:
= Premises:
== If it rains the ground is wet.
== If the ground is wet the match is cancelled.
== It is raining.
= Conclusion:
== The match is not cancelled.
(Propositional Logic)
Premises:
- R => W
- W => C
- R is true
Modus Ponens:
A => B and A is true implies B is true.
Therefore:
- W is true.
- C is true.
- The stated conclusion is incorrect.
What is Validity and Satisfiability?
The expression is valid if the output is always true across different variable values.
e.g. A ∨ ¬A
The output is satisfiable if there is at least one permutation of input values that causes the output to be true.
e.g. A ∨ B
What is the Resolution Rule?
Resolution is a Propositional Logic rule that allows us to infer a new clause from two clauses with complementary literals.
Given:
- A ∨ B
- ¬A ∨ C
We can infer
- B ∨ C (‘resolving on A’)
What is Forward Chaining?
- Given an initial set of facts (Knowledge Base), a set of inference rules, and a conclusion to be verified.
- Apply rules to Knowledge Base to infer new facts.
- Add new facts to the Knowledge Base.
- Repeat until you are able to verify or disprove the conclusion. (May not be possible).
What is Backward Chaining?
- Given an initial set of facts (Knowledge Base), a set of inference rules, and a conclusion to be verified.
- Starting with the conclusion, apply inference rules to create assumptions.
- Repeatedly work backwards with the assumptions until you can disprove or validate the conclusion. (May not be possible).
What a Horn Clause?
What is its significance?
A logic clause consisting of only disjunction (OR) and containing zero or one positive literals.
The significance is that – using first-order resolution – the resolution of two horn clauses is another horn clause. This means that any number of horn clauses can be resolved down to one, increasing the efficiency in proving a theorem.
What is CNF?
What is its significance?
Conjunctive Normal Form.
A conjunction of one or more clauses, where a clause is a disjunction of literals.
They are required for Boolean Satisfiability solvers (SAT problems) as well as other applications in Resolution and beyond.
Are these Expressions in CNF? If not, why not?
- ¬(A∧B)
- (A∨¬B∨¬C)∧(¬D∨E∨F∨D∨F)
- ¬(A∨B)∧C
- A∧(B∨(D∧E))
- No, because it contains a non-literal inside of a NOT.
- Yes.
- No, because it contains a non-literal inside of a NOT.
- No, because it contains a conjunction within a disjunction.
What are the 3 main categories of Logic and their complexities?
Propositional Logic - simplest
[comprised only of statements and the operators: conjunction, disjunction, implication, and biconditional]
Predicate Logic aka Predicate Calculus aka First-order Logic
[Introduces variables, predicates, and quantifiers]
Higher-order Logic - most complex
[Allows quantification over predicates and functions]
What is Unification in First-order logic?
A type of Automated Reasoning that looks for a variable substitution configuration to equate two expressions.
e.g. (variables are lower case)
P(A, x)
P(y, B)
Unifying substitution:
{ y↦A, x↦B }
What are Quantifies in First-order logic?
Operators that describe the number of individuals that the following statement describes
∀ - Universal - Applies to everything
∃ - Existential - Applies to at least one
What is the goal of a Constraint Satisfaction Problem?
To assign each Variable a Value such that no restrictions are violated.
A constraint might be that the sum of two Variables must not exceed 10; thus the variables may not both have a value of 6.
What is AC-3?
(Constraint Satisfaction Problem (CSP))
Arc Consistency Algorithm 3.
Reduces the search space by eliminating values from variables that cannot result in a solution.
Looks at pairs of variables.
Runs in O(e * d^2) time
e = constraints
d = max domain size
Does not always completely solve a CSP, but is often used as a preprocessing step.
