Book: Intelligent Systems- A Modern Approach

1 Evolution of Modern Computational Intelligence ………………… 1

1.1 Introduction ………………………………………………………………………………….. 1

1.2 Roots of Artificial Intelligence ………………………………………………………… 3

1.3 Modern Artificial Intelligence …………………………………………………………. 7

1.4 Metamodern AI……………………………………………………………………………. 11

2 Problem Solving by Search ……………………………………………. 13

2.1 Introduction ………………………………………………………………………………… 13

2.2 What Is Search? …………………………………………………………………………… 13

2.3 Tree Based Search ……………………………………………………………………….. 16

2.3.1 Terminology ……………………………………………………………………… 16

2.4 Graph Search ………………………………………………………………………………. 17

2.5 Search Methods Classification……………………………………………………….. 19

2.6 Uninformed Search Methods …………………………………………………………. 19

2.6.1 Breadth First Search……………………………………………………………. 20

2.6.2 Depth First Search ……………………………………………………………… 24

2.6.3 Backtracking Search …………………………………………………………… 26

2.6.4 Depth Bounded (Limited) Depth First Search ………………………… 27

2.6.5 Iterative Deepening Depth First Search …………………………………. 29

2.6.6 Branch and Bound (or Uniform Cost Search)…………………………. 32

2.6.7 Bidirectional Search……………………………………………………………. 34

2.7 Performance Evaluation of the Uninformed Search Strategies……………. 36

2.7.1 Remarks and Discussions ……………………………………………………. 36

2.7.2 Repeated States ………………………………………………………………….. 38

Summary………………………………………………………………………………………………… 38

References ……………………………………………………………………………………………… 40

Verification Questions ……………………………………………………………………………… 42

Exercises………………………………………………………………………………………………… 43

3 Informed (Heuristic) Search………………………………………… .. 53

3.1 Introduction ………………………………………………………………………………… 53

3.2 Heuristics ……………………………………………………………………………………. 54

3.3 Best First Search ………………………………………………………………………….. 56

3.4 Greedy Search……………………………………………………………………………… 57

3.5 A* Search …………………………………………………………………………………… 63

3.6 Comparisons and Remarks ……………………………………………………………. 70

3.7 A* Variants…………………………………………………………………………………. 70

3.7.1 Iterative Deepening A* (IDA*) ……………………………………………. 71

3.7.2 Simplified Memory Bounded A* (SMA*) …………………………….. 71

3.7.3 Recursive Best-First Search (RBFS)……………………………………… 75

3.7.4 D* Algorithm…………………………………………………………………….. 75

3.7.5 Beam Search ……………………………………………………………………… 76

Summary………………………………………………………………………………………………… 76

References ……………………………………………………………………………………………… 77

Verification Questions ……………………………………………………………………………… 79

Exercises………………………………………………………………………………………………… 79

4 Iterative Search…………………………………………………………… 83

4.1 Introduction ………………………………………………………………………………… 83

4.2 Hill Climbing………………………………………………………………………………. 84

4.3 Simulated Annealing ……………………………………………………………………. 92

4.4 Tabu Search ………………………………………………………………………………… 98

4.5 Means Ends……………………………………………………………………………….. 103

4.6 Summary…………………………………………………………………………………… 104

References ……………………………………………………………………………………………. 105

Verification Questions ……………………………………………………………………………. 107

Exercises………………………………………………………………………………………………. 108

5 Adversarial Search …………………………………………………….. 111

5.1 Introduction ………………………………………………………………………………. 111

5.2 MIN-MAX Algorithm ………………………………………………………………… 112

5.2.1 Designing the Utility Function……………………………………………. 113

5.3 Alpha-beta Pruning…………………………………………………………………….. 119

5.4 Comparisons and Discussions………………………………………………………. 123

Summary………………………………………………………………………………………………. 123

References ……………………………………………………………………………………………. 125

Verification Questions ……………………………………………………………………………. 125

Exercises………………………………………………………………………………………………. 126

6 Knowledge Representation and Reasoning ………………………….. 131

6.1 Introduction ………………………………………………………………………………. 131

6.2 Propositional Logic…………………………………………………………………….. 132

6.2.1 Logical Operators …………………………………………………………….. 133

6.2.2 Terminology ……………………………………………………………………. 135

6.2.3 Inference …………………………………………………………………………. 137

6.2.3.1 Introduction …………………………………………………………. 138

6.2.3.2 Elimination………………………………………………………….. 138

6.3 First Order Predicate Logic (FOPL) ……………………………………………… 139

6.3.1 Predicate Calculus…………………………………………………………….. 139

6.3.2 FOPL Alphabet ………………………………………………………………… 140

7 Rule-Based Expert Systems ………………………………………….. 149

7.1 Introduction ………………………………………………………………………………. 149

7.2 Elements of a Rule-Based System………………………………………………… 150

7.2.1 Rules ………………………………………………………………………………. 151

7.2.1.1 Rules Classification ……………………………………………… 152

7.3 Structure of a Rule-Based Expert System………………………………………. 154

7.4 Types of Rule-Based Expert Systems……………………………………………. 156

7.4.1 Forward Chaining Systems ………………………………………………… 158

7.4.2 Backward Chaining Systems ……………………………………………… 165

7.4.3 Forward Chaining or Backward Chaining?

Which One Should Apply? ………………………………………………… 172

7.5 Conflict Resolution…………………………………………………………………….. 172

7.6 Benefits and Capabilities of Rule Based Expert Systems …………………. 175

7.7 Types of Expert Systems …………………………………………………………….. 176

7.8 Examples of Expert Systems ……………………………………………………….. 177

Summaries ……………………………………………………………………………………………. 179

References ……………………………………………………………………………………………. 180

Verification Questions ……………………………………………………………………………. 181

Exercises………………………………………………………………………………………………. 181

8 Managing Uncertainty in Rule Based Expert Systems ………… 187

8.1 What Is Uncertainty and How to Deal With It? ………………………………. 187

8.2 Bayesian Theory ………………………………………………………………………… 189

8.2.1 Classical Probability Theory………………………………………………. 189

8.2.2 Bayes’ Rules ……………………………………………………………………. 191

8.2.3 Bayesian Reasoning………………………………………………………….. 193

8.2.4 Bayesian Networks …………………………………………………………… 196

8.2.4.1 Inference in Bayesian Networks …………………………….. 198

8.2.4.2 Variable Ordering in Bayesian Networks ………………… 200

8.2.4.3 Facts about Bayesian Networks ……………………………… 201

8.3 Certainty Factors………………………………………………………………………… 202

8.3.1 Calculating Certainty Factors …………………………………………….. 204

8.3.1.1 Measure of Belief…………………………………………………. 204

8.3.1.2 Measure of Disbelief…………………………………………….. 204

8.3.2 Combining Certainty Factors ……………………………………………… 205

8.3.2.1 Multiple Rules Providing Evidence for the

Same Conclusion …………………………………………………. 205