Show Menu

EECS492Mid Cheat Sheet by

Definition of AI

Acting humanly: The Turing Test approach
Thinking humanly: The cognitive modeling approach
Thinking ration­ally: The “laws of thought” approa­ch(­Logic)
Acting ration­ally: The rational agent approach

Turing test

natural language proces­sing to enable it to commun­icate succes­sfully in English;
know­ledge repres­ent­ation to store what it knows or hears;
auto­mated reason­ing to use the stored inform­ation to answer questions and to draw new conclu­sions;
machine learning to adapt to new circum­stances and to detect and extrap­olate patterns.
total Turing test
computer vision to perceive objects;
robo­tics to manipulate objects and move about.

Agents and Enviro­nments

An agent is anything that can be viewed as perceiving its envi­ron­ment through sens­ors and acting upon that enviro­nment through actu­ato­rs. We use the term perc­ept to refer to the agent’s perceptual inputs at any given instant. An agent’s percept sequence is the complete history of everything the agent has ever perceive.

PEAS

Perfor­mance measure, Enviro­nment, Actuators, Sensors

Knowledge Base

Concep­tually, a set of sentences;
.Defined by TELL/ASK interface

Declar­ative Approach

Program an agent by TELLing it things
Equiva­lently, construct and install a KB
Advantages
1.Flex­ibi­lity: knowledge indepe­ndent of how it would be used
2.Tran­spa­rency to humans
3.Agent behavior malleable via language

Knowledge Repres­ent­ation

Know­ledge repres­ent­ation langua­ge: notation for expressing a KB
Consist of
Syntax: defines the legal sentences
Semantics: facts in the world to which sentences corres­pond, an interp­ret­ation for symbols in the logic
Logic: KR language with well-d­efined syntax and semantics
Model: Specifies truth or falsity of sentences

Properties of Sentences

Valid: True in all models
Sati­sfi­able: True in some model
 

Rational agent

For each possible percept sequence, a rational agent should select an action that is expected to maximize its perfor­mance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.

Autonomy

A system is autonomous that its behavior is determined by its own percepts, rather than the prior knowledge of its designer.

Coherence

Actions must be consistent with beliefs and desires. Necessary for knowle­dge­-level unders­tanding of computer programs.

Agent Designs

Table Lookup, Simple Reflex, Model-­based, Goal-b­ased, Utilit­y-b­ased, Learning

Enviro­nment Properties

fully/­par­tially observ­able, single­/multi, determ­ini­sti­c/s­toc­hastic, episod­ic/­seq­uen­tial, static­/dy­namic, discre­te/­con­tin­uous, known/­unknown

Admiss­ibility and Consis­tency

Admi­ssi­bil­ity: h(n) ≤ c(n), where c(n) is the true cost of a solution along the current path through n.
Cons­ist­ency: h(n) ≤ c(n,a,­n'­)+h­(n').
Opti­mal­ity: If h is admissible and consis­tent, A* is optimal.
A* is optimal, complete and optimally efficient among all algorithms that extend search paths from root.

Entailment and Inference

Enta­ilm­ent: α |= β if and only if M(α) ⊆ M(β). Truth of β is contained in α. α |= β if and only if the sentence (α ⇒ β) is valid. α ≡ β if and only if α |= β and β |= α.
Infe­ren­ce: α |- β means β can be derived from α.
An inference algorithm that derives only entailed sentences is called sound.
An inference algorithm is comp­lete if it can derive any sentence that is entailed

FOL to CNF

1.Tran­slate bidire­cti­onals to implic­ations
2.Tran­slate implic­ations to disjun­ctions
3.Move negations inward (Use De Morgan’s laws until only atoms are negated)
4.Stan­dardize variables
5.Elim­inate existe­ntials via skolem­ization
6.Drop universal quanti­fiers
7.Dist­ribute and associate into CNF
 

Uninformed search strategies

Breadt­h-f­irst, Unifor­m-cost, Depth-­first, Depth-­lim­ited, Iterat­ive­-de­epe­ning, Bidire­cti­onal, Graph search

Analysis

Criterion
BFS
UC
Complete
Yes
Yes
Optimal
Yes
Yes
Time
O(bd+1)
O(b1+­flo­or(­C*/e))
Space
O(bd+1)
O(b1+­flo­or(­C*/e))

Analysis

Criterion
DFS
DLDFS
IDDFS
Complete
No
No
Yes
Optimal
No
No
Yes
Time
O(bm)
O(bL)
O(bd)
Space
O(bm)
O(bL)
O(bd)

Informed Search

Priori­ty-­fir­st(­PFS), Greedy, A*, Iterat­ive­-de­epening A*, heuristics and admiss­ibi­lit­y/c­ons­istency

Flavors of PFS

Number of edges from origin: BFS
g(n), the path cost from the initial state(­node) to node n: UCS(Di­jkstra)
h(n), the estimated path cost from node n to goal: Greedy Search
f(n)=g­(n)­+h(n), the estimated cost of a path passing through n: A* search

Memory­-bo­unded heuristic search

iter­ati­ve-­dee­pening A* (IDA*)
Recu­rsive best-first search (RBFS): best first search with linear space

Local search strategies

Hill-c­lim­bin­g/s­toc­hastic, beam, simulated annealing, genetic algorithms

Local search summary

Key advant­ages
1.Very little memory
2.Can often find reasonable solutions in large or infinite state spaces where systematic approaches are unsuitable
3.Better answers the more time spent
Disa­dva­nta­ges
Usually incomplete and not optimal

Constraint propag­ation

Defi­nit­ion: Propag­ating the implic­ations of a constraint on one variable onto other variables.
k-co­nsi­ste­nt: for any consistent assignment of k-1 variables, exists consistent value of any kth(No­de/­Arc­/Path)
Strongly k-cons­ist­ent: j-cons­istent for all j less than or equal to k

Constrain Satisf­action Search

Back­tra­cking
Minimum remaining values heuristic: choose variable with fewest legal values remaining
Degree heuristic: choose variable with largest number of constr­aints
Forward checki­ng: delete incons­istent values ahead
Back­jum­ping
Basic: backtrack to most recent decision
Confli­ct-­Dir­ected: backtrack to most recent variable in conflict with

Download the EECS492Mid Cheat Sheet

2 Pages
//media.cheatography.com/storage/thumb/kirawen_eecs492mid.750.jpg

PDF (recommended)

Alternative Downloads

Share This Cheat Sheet!

 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.