Python code for Artificial Intelligence: Foundations of ...

1

Python code for Artificial Intelligence

Foundations of Computational Agents

David L. Poole and Alan K. Mackworth

Version 0.9.12 of February 13, 2024.

?David L Poole and Alan K Mackworth 2017-2024. All code is licensed under a Creative Commons Attribution-NonCommercial-

ShareAlike 4.0 International License. See: by-nc-sa/4.0/deed.en

This document and all the code can be downloaded from or from

The authors and publisher of this book have used their best efforts in preparing this book. These efforts include the development, research and testing of the theories and programs to determine their effectiveness. The authors and publisher make no warranty of any kind, expressed or implied, with regard to these programs or the documentation contained in this book. The author and publisher shall not be liable in any event for incidental or consequential damages in connection with, or arising out of, the furnishing, performance, or use of these programs.



Version 0.9.12

February 13, 2024

Contents

Contents

3

1 Python for Artificial Intelligence

9

1.1 Why Python? . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

1.2 Getting Python . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.3 Running Python . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.4 Pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5 Features of Python . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.1 f-strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

1.5.2 Lists, Tuples, Sets, Dictionaries and Comprehensions . . 12

1.5.3 Functions as first-class objects . . . . . . . . . . . . . . . . 13

1.5.4 Generators . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

1.6 Useful Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.1 Timing Code . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2 Plotting: Matplotlib . . . . . . . . . . . . . . . . . . . . . 16

1.7 Utilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.1 Display . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

1.7.2 Argmax . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.7.3 Probability . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.8 Testing Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

2 Agent Architectures and Hierarchical Control

25

2.1 Representing Agents and Environments . . . . . . . . . . . . . 25

2.2 Paper buying agent and environment . . . . . . . . . . . . . . 27

2.2.1 The Environment . . . . . . . . . . . . . . . . . . . . . . . 27

2.2.2 The Agent . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

3

4

Contents

2.2.3 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3 Hierarchical Controller . . . . . . . . . . . . . . . . . . . . . . . 31

2.3.1 Environment . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.3.2 Body . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.3 Middle Layer . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.4 Top Layer . . . . . . . . . . . . . . . . . . . . . . . . . . . 35 2.3.5 Plotting . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Searching for Solutions

41

3.1 Representing Search Problems . . . . . . . . . . . . . . . . . . 41

3.1.1 Explicit Representation of Search Graph . . . . . . . . . . 43

3.1.2 Paths . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

3.1.3 Example Search Problems . . . . . . . . . . . . . . . . . . 47

3.2 Generic Searcher and Variants . . . . . . . . . . . . . . . . . . . 53

3.2.1 Searcher . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

3.2.2 GUI for Tracing Search . . . . . . . . . . . . . . . . . . . . 55

3.2.3 Frontier as a Priority Queue . . . . . . . . . . . . . . . . . 59

3.2.4 A Search . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

3.2.5 Multiple Path Pruning . . . . . . . . . . . . . . . . . . . . 62

3.3 Branch-and-bound Search . . . . . . . . . . . . . . . . . . . . . 64

4 Reasoning with Constraints

69

4.1 Constraint Satisfaction Problems . . . . . . . . . . . . . . . . . 69

4.1.1 Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

4.1.2 Constraints . . . . . . . . . . . . . . . . . . . . . . . . . . 70

4.1.3 CSPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

4.1.4 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

4.2 A Simple Depth-first Solver . . . . . . . . . . . . . . . . . . . . 83

4.3 Converting CSPs to Search Problems . . . . . . . . . . . . . . . 84

4.4 Consistency Algorithms . . . . . . . . . . . . . . . . . . . . . . 86

4.4.1 Direct Implementation of Domain Splitting . . . . . . . . 89

4.4.2 Consistency GUI . . . . . . . . . . . . . . . . . . . . . . . 91

4.4.3 Domain Splitting as an interface to graph searching . . . 93

4.5 Solving CSPs using Stochastic Local Search . . . . . . . . . . . 95

4.5.1 Any-conflict . . . . . . . . . . . . . . . . . . . . . . . . . . 97

4.5.2 Two-Stage Choice . . . . . . . . . . . . . . . . . . . . . . . 98

4.5.3 Updatable Priority Queues . . . . . . . . . . . . . . . . . 101

4.5.4 Plotting Run-Time Distributions . . . . . . . . . . . . . . 102

4.5.5 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

4.6 Discrete Optimization . . . . . . . . . . . . . . . . . . . . . . . 105

4.6.1 Branch-and-bound Search . . . . . . . . . . . . . . . . . . 106

5 Propositions and Inference

109

5.1 Representing Knowledge Bases . . . . . . . . . . . . . . . . . . 109

5.2 Bottom-up Proofs (with askables) . . . . . . . . . . . . . . . . . 112



Version 0.9.12

February 13, 2024

Contents

5

5.3 Top-down Proofs (with askables) . . . . . . . . . . . . . . . . . 114 5.4 Debugging and Explanation . . . . . . . . . . . . . . . . . . . . 115 5.5 Assumables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 5.6 Negation-as-failure . . . . . . . . . . . . . . . . . . . . . . . . . 122

6 Deterministic Planning

125

6.1 Representing Actions and Planning Problems . . . . . . . . . . 125

6.1.1 Robot Delivery Domain . . . . . . . . . . . . . . . . . . . 126

6.1.2 Blocks World . . . . . . . . . . . . . . . . . . . . . . . . . 128

6.2 Forward Planning . . . . . . . . . . . . . . . . . . . . . . . . . . 130

6.2.1 Defining Heuristics for a Planner . . . . . . . . . . . . . . 132

6.3 Regression Planning . . . . . . . . . . . . . . . . . . . . . . . . 135

6.3.1 Defining Heuristics for a Regression Planner . . . . . . . 137

6.4 Planning as a CSP . . . . . . . . . . . . . . . . . . . . . . . . . . 138

6.5 Partial-Order Planning . . . . . . . . . . . . . . . . . . . . . . . 142

7 Supervised Machine Learning

149

7.1 Representations of Data and Predictions . . . . . . . . . . . . . 150

7.1.1 Creating Boolean Conditions from Features . . . . . . . . 153

7.1.2 Evaluating Predictions . . . . . . . . . . . . . . . . . . . . 155

7.1.3 Creating Test and Training Sets . . . . . . . . . . . . . . . 157

7.1.4 Importing Data From File . . . . . . . . . . . . . . . . . . 157

7.1.5 Augmented Features . . . . . . . . . . . . . . . . . . . . . 160

7.2 Generic Learner Interface . . . . . . . . . . . . . . . . . . . . . 162

7.3 Learning With No Input Features . . . . . . . . . . . . . . . . . 163

7.3.1 Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

7.4 Decision Tree Learning . . . . . . . . . . . . . . . . . . . . . . . 167

7.5 Cross Validation and Parameter Tuning . . . . . . . . . . . . . 171

7.6 Linear Regression and Classification . . . . . . . . . . . . . . . 175

7.7 Boosting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181

7.7.1 Gradient Tree Boosting . . . . . . . . . . . . . . . . . . . . 184

8 Neural Networks and Deep Learning

187

8.1 Layers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187

8.1.1 Linear Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 188

8.1.2 ReLU Layer . . . . . . . . . . . . . . . . . . . . . . . . . . 190

8.1.3 Sigmoid Layer . . . . . . . . . . . . . . . . . . . . . . . . . 190

8.2 Feedforward Networks . . . . . . . . . . . . . . . . . . . . . . . 191

8.3 Improved Optimization . . . . . . . . . . . . . . . . . . . . . . 193

8.3.1 Momentum . . . . . . . . . . . . . . . . . . . . . . . . . . 193

8.3.2 RMS-Prop . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

8.4 Dropout . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

8.4.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

9 Reasoning with Uncertainty



Version 0.9.12

201 February 13, 2024

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download