***WARNING: THE FOLLOWING IS AN APPROXIMATE SCHEDULE--WE MAY GO FASTER OR SLOWER THAN THIS. YOU CAN USE IT TO GET AN IDEA OF WHAT WILL HAPPEN IN THE COURSE. *****THIS IS WHAT HAPPENED WHEN I TAUGHT THE COURSE LAST YEAR**** [Aug 22, 2000] Course overview Spiffy Multimedia Introduction. Definitions of AI. Applications of AI. [Aug 24, 2000] Rational agency. Environment types. Agent types. Motivating course topics in terms of agent types. Applications of the couse topics. [Aug 29, 2000] Problem solving agents. Types of search --Single state --multiple state --contingency search --interleaving Problem formulation [Aug 31, 2000] Search General search Useful properties of Search Algorithms importance of spcae complexity b Blind search BFS, DFS, DLDFS, IDDFS [Sep 5, 2000] More on IDDFS It is too pessimistic Uniform cost search (BFS with non-uniform operator costs) Definition of g(n), C(n,n') Proof of its optimality Improving space complexity of Uniform Cost Search Iterative version of Uniform Cost search Cut tree using g bounds Improving time complexity of Uniform Cost search Use h(n)--an estimate of future cost of going from the current node to the goal node 1. What are required properties of h(n)? --Admissibility (h(n) must be a lowerbound on h*(n)) --Informedness h(n) should be as close to h*(n) as possible 2. Where do heuristics come from? Straightline distance, #misplaced tiles etc. [Sep 7, 2000] Formal proof that admissibility implies optimal solution Discussion of search contours and how they are modified and narrowed with heuristics Discussion of monotonicity (local consistency) of heuristics, and how the Path-max idea corrects non-mononotic heuristics Memory consumption -b^d with any uniform heuristic (including h=0) IDA* --and the idea of doing iterative search with f-value bounds --discussion of how a heuristic that gives unique values for each node will wind up forcing b^d iterations instead of d iterations in IDA* --Sktech of the SMA* algorithm idea (Not discussed completely) Where heuristics come from --relaxed models --removing constraints in the problem --tradeoff between heuristic computaion cost and the search cost. --pattern database idea (Admissibility requires only that the heuristic does not over-estimate the goodness of the good nodes. Effectiveness also requires that the heuristic differentiate between good and bad nodes.) [Sep 8, 2000] CSP class (Makeup class for Sep 26th) Followed the slides from the textbook site CSP problems Binary CSPs and Constraint graphs tree structured constraint graphs and poly-solvability Connection between CSP and Satisfiability CSP examples CSP applications CSP search --straightforward problem-solving search why DFS is the preferred method --improving by not bactracking on the variable order --Efficiency improvements Forward checking (anticipate failures) Variable ordering heuristics Most constrained variable first in conjunction with forward checking, we get dynamic variable ordering Value ordering heuristics Least constraining value [Sep 12, 2000] Discussion of project 1 questions (~15minutes) Monotonicity and Triangle law of inequality f(n_child)+C(n, n_child) >= f(n) f=wg+(1-w)h Looping issue and connections between A* and Dijkstra's algorithm ============ Local search---hill climbing--why it works -->two ways to improve hill climbing --> do better steps --> do restart Discussion on why hill-climbing search works well --Tension between systematicity and local gradient following [Sep 14, 2000] A* complexity... Genetic Algorithms --what do they do Radomized systematic search strategies --Heavy tailed distributions. ============= Gametree search start [Sep 19, 2000] Project 1 discussion --about the comparison between informed heuristics Min-max doing minmax with depthfirst search Alpha-beta pruning The example of Alpha-beta pruning. The best case analysis of alpha-beta pruning. [Sep 21, 2000] Completion of depth-limited minimax State of the art in deteministic games Discussion of RTA* and LRTA* handling dynamic worlds with single agent search Brief discussion of non-determinstic games Expectimax Quick buzzword review for exam Combine SAT discussion and prop logic discussion Inference and Search... [Sep 26, 2000] *********No class. Class made-up on Sep 8th [Sep 28, 2000] Exam 1. In class [Oct 3, 2000] Knowledgebased agents. types of logics Commitments in logics Ideas of entailment.. [Oct 5, 2000] Illustration of ideas of entailment for propositional logic Computation of entailment for propositional logic Complexity of entailment COnnection between entailment/theoremproving and CSP/model checking Forward checking as inference Complexity of entailment for propositional logic Equivalent to Conjugate of model finding (showing there is _no_ model) Co-NP complete (since model finding--boolean csp is np-complete) Inference procedures and their properties.. modus ponens modus tollens Resolution as a complete inference procedure Doing propositional theorem proving Forward resolution Resolution refutation --with set of support Comparing resolution refutation to A* search --you don't need to consider all possible inferences at each step-- (since every inference that can be done on KB can also be done on a KB that comes from doing an inference on KB) just do one inference at a time. [Oct 10, 2000] case analysis and resolution talk about davis putnam -- unit propagation -- variable ordering for unit propagation Phase transition discussion [Oct 12, 2000] First order logic--Syntax and semantics Beginning of inference [Oct 17, 2000] Unification Prolog--backward chaining Project 2 discussion [Oct 19, 2000] Prolog-- negation as failure Depth first/left to right inference Completeness of prolog as a language Incompleteness of prolog as an inference procedure discussion about defeasible (non-monotonic infereces) --connection to probabilistic logic --the tweety example tweety is a bird -tweety flies --tweety wears a red shirt? Resolution refutation--clausal form Clausal form [Oct 24, 2000] Resolution refutation--example Answer extraction Situation Calculus Frame problem [Oct 26, 2000] Review of Situation calculus Frame problem Strips (state vaiable) representation Progression Regression [Oct 31, 2000] [[Digression into what is systematic search, and also into the connections between deductive databases and prolog plus some discussion about project 2 took up close to 35min..]] Review of progression/regression Discussion of heuristics -set difference heuristic --its disadvantages -- using planning graph to estimate cost of individual literals --estimating the cost of sets of literals: --by summing their individual costs --by using the notion of level [Nov 2, 2000] Completing the discussion on planning graph based heuristics --mutex propagation stuff Using PG to do planning as CSP. [Nov 7,2000] --PG for CSP Reasoning with uncertainity start [Nov 9,2000] Review of probabilistic reasoning Upto bayes rule [Nov 14,2000] Bayes rule/Bayes networks [Nov 16,2000] Bayes networks [Nov 21,2000] Learning 1 [Nov 28,2000] Learning 2 [Nov 30,2000] Learning 3 [dec 5, 2000] Learning end... Review. Review. [Dec 14, 2000] Rao skips country