Transcript Artificial Intelligence

Artificial Intelligence
Tarik Booker
What we will cover…
History
Artificial Intelligence as Representation
and Search
Languages used in Artificial Intelligence
Applications
History of Artificial
Intelligence
Derives from Logic
Aristotle
Charles Babbage
George Boole
Alan Turing
Turing Test
AI as Representation and
Search
Predicate Calculus
State Space
Heuristic Search
Predicate Calculus
Covered later in presentation (Logic
Programming)
Basics:
Proposition – statement that may or may not
be true
State Space
The structure of the state that you are in
A four-tuple [N, A, S, GD]
Where:
N is the set of nodes (or states) of the graph
A is the set of arcs (links) between nodes
S, a non-empty subset of N, contains the start state(s) of the
problem
GD, a non-empty subset of N contains the goal state(s) of
the problem
A solution path is a path through this graph from a
node S to a node in GD
Heuristics
(From Greek “eurisco” meaning “to
discover”)
A strategy for selectively searching a
problem space
Searches along lines that have a high
probability of success
Not guaranteed to find correct solution
Why use Heuristics?
Problem may not have an exact solution
because of ambiguities
Ex: Medical Diagnosis
Problem may have exact solution, but the
computational cost of finding it may be
prohibitive
Ex: Chess
Heuristics are at the core of AI.
Heuristic Algorithms
Heuristic Measure
Best-first Search
Tic-Tac Toe (on board)
Heuristics Terms
Admissibility
Heuristics that find the shortest path to a goal
whenever it exists are said to be admissible
Informedness
Are any heuristics better that the one we are using?
Monotonicity
When a state is discovered using heuristic search, is
there a guarantee that the same state won’t be
reached with a cheaper cost?
Languages Used in AI
LISP
PROLOG
Applications of AI
Game Playing
Heuristics
Automated Reasoning and Theorem
Proving
Expert Systems
Natural Language Understanding
Planning and Robotics
Machine Learning
Sources
Luger, George F.
Stubblefield, William A.
Artificial Intelligence
(3rd Edition)