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