COURSE OUTLINE: For an autonomous agent to behave in an intelligent manner it must be able to solve problems. This means it should be able to arrive at decisions that transform a given situation into a desired or goal situation. The agent should be able to imagine the consequence of its decisions to be able to identify the ones that work. In this first course on AI we study a wide variety of search methods that agents can employ for problem-solving
Overview
Syllabus
Prologue.
The Winograd Schema Challenge.
Introduction (2013 version).
Can Machines Think?.
The Turing Test.
Language and Thought.
The Willing Suspension of Disbelief.
Machines with Wheels and Gears.
The Notion of Mind in Philosophy.
Reasoning = Computation.
Concepts and Categories.
How did AI get its name?.
The Chess Saga.
A Brief History of AI.
The Worlds in our Minds.
Epiphemona in Computers.
State Space Search.
Domain Independent Algorithms.
Deterministic Search.
DFS and BFS.
Comparing DFS and BFS.
Depth First Iterative Deepening.
Heuristic Search.
Heuristic Functions and the Search Landscape.
Solution Space Search.
The Traveling Salesman Problem.
Escaping Local Optima.
Stochastic Local Search.
Genetic Algorithms: Survival of the Fittest.
Genetic Algorithms and SAT.
Genetic Algorithms for the TSP.
Emergent Systems.
Ant Colony Optimization.
Finding Optimal Paths.
Branch & Bound.
Algorithm A*.
A*: An illustrated example.
Is A* Admissible?.
Admissibility of A*.
Higher, Faster ....
B&B - A* - wA* - Best First.
A*: Leaner Admissible Variations.
The Monotone Condition.
DNA Sequence Alignment.
Divide & Conquer Frontier Search..
Smart Memory Graph Search.
Variations on A*: The story so far.
Breadth First Heuristic Search.
Beam Stack Search.
Game Theory.
Popular Recreational Games.
Board Games and Game Trees.
The Evaluation Function in Board Games.
Algorithm Minimax and Alpha-Beta Pruning.
A Cluster of Strategies.
SSS*: A Detailed Example.
SSS*: A Best First Algorithm.
Automated Domain Independent Planning.
The Blocks World Domain.
State Space Planning: Forward and Backward.
Goal Stack Planning (GSP).
GSP: A Detailed Example.
Plan Space Planning (PSP).
PSP: A Tiny Example.
Multi-Armed Robots.
Means-Ends Analysis.
The Planning Graph.
Algorithm Graphplan.
Problem Decomposition..
Algorithm AO*.
AO*: An Illustration.
Rete Algorithm: Conflict Resolution.
Rete Algorithm: Optimizing the Match.
The Rete Net.
Business Rule Management Systems.
Conflict Resolution.
The OPS5 Language.
The Inference Engine.
Rule Based Expert Systems.
Reasoning in Logic.
Rules of Inference.
Forward Reasoning.
First Order Logic.
Implicit Quantifier Notation.
Backward Reasoning.
Depth First Search on Goal Trees.
Incompleteness....
Constraint Satisfaction Problems.
Binary Constraint Networks.
Interpreting Line Drawings.
Model Based Diagnosis.
Solving CSPs.
Arc Consistency.
Propagation = Reasoning.
Lookahead Search.
Taught by
NPTEL-NOC IITM
