CSC 550: Introduction to Artificial Intelligence
CSC 650: Advanced Artificial Intelligence
Spring 2002
Midterm Review
Overview
history of AI
philosophical extremes: neats vs. scruffies, GOFAI vs. emergents, weak vs. strong
Turing test
Logic & logic programming
predicate calculus (PC)
syntax: terms, predicates, sentences
semantics: interpretation, logic consequence, proof procedure
logic programming
program = statements in Horn clause subset of PC (facts & rules)
logic programs define relations, interpreter answers queries
Prolog programming
unification: algorithm for determining instantiations to make expressions match
unification alone can define computation (deductive databases)
resolution (goal reduction): proof procedure for answering queries in Prolog
top-to-bottom search of facts & rules, left-to-right goal ordering
utilizes backtracking when reaches dead-end
procedural vs. declarative readings
need to know proof procedure for efficiency, to avoid cycles
declarative reading more intuitive, relations can be used to test or find
lists
dot functor notation, '|' operator
member, append, is_list, length, nth0, nth1, reverse, delete, select
other built-ins: not, =, \=, =:=, =\=, >, <, >=, =<
user-defined operators
position, precedence, associativity
AI as search
state spaces
must define (1) state representation, (2) start state, (3) goal state,
(4) transitions/moves between states,
(5) control strategy to search for a path from start to goal
tentative vs. bold, informed vs. uninformed strategies
depth first search (DFS)
efficient, but cycles are a problem
can add cycle checking, but still no guarantee of best solution
breadth first search (BFS)
memory intensive, but finds shortest solution if one exists
implementation utilizes bagof predicate, cycle checking easy
DFS with iterative deepening
finds shortest solution without memory requirements of BFS
some duplication of effort, but not very costly
constraint-based problems
Generate&Test vs. Test&Generate
profiling code with the time predicate