CT71                                                    Artificial Intelligence

 

Structure

 

1.     Introduction to Artificial Intelligence

2.     Problem Solving, Search and Control Strategies                                                                       

3.     Problem Reduction and Game playing

4.     Logic Concepts and Prolog programming       

5.     Advanced Problem Solving – Planning

6.     Knowledge Representation Techniques                      

7.     Expert Systems and Applications       

8.     Handling Uncertainty

9.     Machine Learning

10.  Evolutionary Computation

11.  Intelligent Agents    

12.  Natural Language Processing           

 

 

 

Detailed Contents of the course                                            No of Hours (42)

     

1.    Introduction to Artificial Intelligence                                                      2

1.1. General Issues and overview of AI

1.2. Intelligent Systems

1.3. Foundations of AI

1.4. Characteristics of AI systems

1.5. Sub-areas of AI 

1.6. Applications

 

2.    Problem Solving, Search and Control Strategies                                    5                      

2.1. General Problem Solving

2.1.1.   Production System

2.1.2.   State Space Search         

2.1.3.   Control Strategies

2.2. Exhaustive Searches      

2.2.1. Breadth First Search         

2.2.2. Depth-First Search

2.2.3. Depth First Iterative Deepening     

2.2.4. Bi-Directional Search         

2.2.5. Analysis of Search methods           

2.3. Heuristic Search Techniques       

2.3.1. General Purpose Heuristics

2.3.2. Branch and Bound Search (Uniform Cost Search)     

2.3.3. Hill Climbing         

2.3.4. Beam Search        

2.3.5. Best First Search  

2.3.6. A* Algorithm        

2.3.7. Optimal solution by A* Algorithm    

2.4. Iterative–Deepening A* 

2.5. Constrained satisfaction

 

3.    Problem Reduction and Game playing                                                     3         

3.1. Problem Reduction        

3.2. Game Playing   

3.2.1. Game Problem verses State Space Problem

3.2.2. Status Labeling Procedure 

3.3. Bounded Look-ahead and use of Evaluation Functions      

3.3.1. Using Evaluation Function  

3.3.2. MINIMAX Procedure         

3.4. Alpha-Beta Pruning        

3.4.1. Refinements to a-b pruning           

3.4.2. Alternative to a-b pruning MINMAX

3.4.3. Iterative Deepening          

3.4.4. Two Player Perfect Information Games

 

4.    Logic Concepts and Prolog  programming                                              6         

4.1. Propositional Calculus

4.1.1. Truth table

4.1.2. Equivalence Laws

4.2. Propositional Logic

4.2.1. Resolution Refutation in PL

4.2.2. Conversion of a formula into set of clauses

4.2.3. Resolvent of Clauses

4.3. Predicate Logic

4.3.1. Predicate Calculus

4.3.2. Transformation of Formula into Prenex Normal Form

4.3.3. Conversion of Formula into PNF notation

4.3.4. Prenex Normal Form and Skolemization

4.3.5. Resolution Refutation in Predicate Logic

4.4. PROLOG Programming

4.4.1. General Syntax and Prolog Control Strategy

4.4.2. Execution of a Prolog Query

4.5. Programming Techniques in Prolog

4.5.1. Recursive Programming

4.5.2. Iterative Programming

4.6. Lists Manipulation

4.7. Redundancy and Termination Issues

4.8. Effect of Rule and Goal orders

4.9. Cut, Fail predicates

 

5.    Advanced Problem Solving - Planning                                                     3         

5.1. Types of Planning Systems

5.1.1. Operator Based Planning   

5.1.2. Planning Algorithms          

5.1.3. Case Based Planning         

5.1.4. State Space Linear Planning           

5.2. Block World Problem Description

5.3. Logic Based Planning     

5.4. Linear Planning Using a Goal Stack         

5.5. Means-Ends Analysis (MEA)       

5.6. Nonlinear Planning Strategies     

5.6.1. Goal Set Method   

5.6.2. Partial Ordering Planning   

 

6.    Knowledge Representation Techniques                                                  4

6.1. Approaches to Knowledge Representation           

6.2. KR using Semantic Network       

6.2.1. Inheritance in Semantic Net           

6.3. Knowledge Representation using Frames 

6.3.1. Inheritance in Frames       

6.3.2. Implementation of Frame Knowledge         

6.3.3. Representation of Frames in Prolog

6.4. Conceptual Dependency 

6.4.1. Conceptual Primitive Actions          

6.4.2. Conceptual category         

6.4.3. Rules for Conceptualization blocks in CD     

6.4.4. Generation of CD representation    

6.4.5. Conceptual Parsing           

6.4.6.  Inferences Associated with Primitive Act    

 

7.    Expert Systems and Applications                                                 3         

7.1. Phases in building ES

7.1.1. Knowledge Engineering

7.1.2. Knowledge Representation

7.1.3. Characteristics of ES

7.2. Expert System Architecture

7.2.1. Knowledge base

7.2.2. Inference Engine

7.2.3. Knowledge acquisition

7.2.4. User interfaces

7.2.5. Explanation module

7.3. Rule Based Expert System

7.3.1. Expert System Shell in Prolog

7.3.2. Problem Independent Forward Chaining

 

8.    Handling Uncertainty                                                                              5

8.1. Introduction

8.2. Probabilistic Reasoning and Uncertainty

8.2.1. Probability theory

8.2.2. Bayes’ Theorem

8.2.3. Extensions of Bayes' Theorem

8.2.4. Probabilities in Rules and Facts of Production System

8.3. Bayesian Belief Network

8.3.1. Formal Definition of Bayesian Belief Network          

8.3.2. Inference using Bayesian Network 

8.3.3. Example of Simple Bayesian network          

8.3.4. Structure Learning

8.3.5. Advantages and Disadvantages of Bayesian Network           

8.4. Certainty Factor

8.5. Dempster-Shafer (D-S) theory    

8.5.1. Dempster Theory Formalism         

8.5.2. Dempster's rule of combination      

8.6. Fuzzy sets and Fuzzy Logic        

8.6.1. Fuzzy Sets           

8.6.2. Various fuzzy set operations

8.6.3. Various Types of Membership Functions

8.6.4. Methods for Determining Membership Functions      

8.6.5. µ-cut        and Representation of Fuzzy Set   

8.6.6. Multi-Valued Logic

8.6.7. Fuzzy logic           

8.6.8. Linguistic Variables and Hedges     

8.6.9. Fuzzy propositions

8.6.10.   Inference Rules for Fuzzy Propositions    

8.6.11.   Fuzzy Systems and Neuro Fuzzy system 

 

9.    Machine Learning                                                                         4

9.1. Concept of Learning

9.2. Component of Learning System

9.3. Major Learning Paradigm

9.3.1. Inductive Learning

9.3.2. Example Based Learning

9.3.3. Supervised Learning

9.3.4. Unsupervised Learning

9.3.5. Deductive Learning

9.4. Neural Networks

9.4.1. Perceptrons

9.4.2. Multilayer Feedforward Networks

9.4.3. Back Propagation Algorithm

9.4.4. Recurrent Network

9.4.5. Hopfield Network

 

10.  Evolutionary Computation                                                                        2         

10.1.       Genetic Algorithm

10.1.1.   Biological evolutionary process

10.1.2.   Search Space

10.1.3.   Description of Genetic Algorithm

10.1.4.   Operators of GA

10.2.       Applications of GA

10.3.       Genetic programming Concepts

10.3.1.   Genetic programming

10.4.       Evolutionary programming

10.5.       Introduction to Swarm intelligence 

 

 

11.  Intelligent Agents                                                                                     2

11.1.       Properties of Agents

11.2.       Agent Classifications

11.3.       Agent Architecture

11.4.       Learning Agents

11.5.       Multi Agents System

 

12.  Natural Language Processing                                                                 3

12.1.       Introduction

12.2.       Parsing techniques

12.3.       Context-free grammar

12.4.       Recursive Transitions Nets (RTN)

12.5.       Augmented Transition Nets (ATN)

12.6.       Case Grammar

12.7.       Definite Clause Grammar (Logic grammar)

 

Text Books

1.     Elaine Rich and Kevin Knight, “Artificial Intelligence”, Tata McGraw-Hills, Reprint 2003.

2.     S Russell and Peter Norvig, Artificial Intelligence – A Modern Approach, Pearson Education, Reprint 2003.

3.     Saroj Kaushik, “Logic and Prolog Programming” , New Age International Ltd, publisher, 2007.

 

 Reference Books

1.     N J. Nilsson, “Artificial Intelligence: A New Approach”, Morgan Kaufmann, Reprint 2003

2.     Dan W. Patterson, “Introduction to Artificial Intelligence and Expert Systems”, Prentice all of India, 1992.

3.     L. Sterling & E. Shapiro, “Art of Prolog, Advanced Programming Techniques, Prentice Hall of India, reprint 1996.