/aima-python

Python implementation of algorithms from Russell And Norvig's "Artificial Intelligence - A Modern Approach"

Primary LanguageJupyter NotebookMIT LicenseMIT



aima-python Build Status Binder

Python code for the book Artificial Intelligence: A Modern Approach. You can use this in conjunction with a course on AI, or for study on your own. We're looking for solid contributors to help.

Python 3.4

This code is in Python 3.4 (Python 3.5 and later also works, but Python 2.x does not). You can install the latest Python version or use a browser-based Python interpreter such as repl.it. You can run the code in an IDE, or from the command line with python -i filename.py where the -i option puts you in an interactive loop where you can run Python functions.

In addition to the filename.py files, there are also filename.ipynb files, which are Jupyter (formerly Ipython) notebooks. You can read these notebooks, and you can also run the code embedded with them. See jupyter.org for instructions on setting up a Jupyter notebook environment.

Structure of the Project

When complete, this project will have Python code for all the pseudocode algorithms in the book. For each major topic, such as logic, we will have the following three files in the main branch:

  • logic.py: Implementations of all the pseudocode algorithms, and necessary support functions/classes/data.
  • logic.ipynb: A Jupyter (IPython) notebook that explains and gives examples of how to use the code.
  • tests/test_logic.py: A lightweight test suite, using assert statements, designed for use with py.test, but also usable on their own.

Index of Algorithms

Here is a table of algorithms, the figure, name of the algorithm in the book and in the repository, and the file where they are implemented in the repository. This chart was made for the third edition of the book and needs to be updated for the upcoming fourth edition. Empty implementations are a good place for contributors to look for an issue. The aima-pseudocode project describes all the algorithms from the book. An asterisk next to the file name denotes the algorithm is not fully implemented.

Figure Name (in 3rd edition) Name (in repository) File Tests
2.1 Environment Environment agents.py
2.1 Agent Agent agents.py Done
2.3 Table-Driven-Vacuum-Agent TableDrivenVacuumAgent agents.py
2.7 Table-Driven-Agent TableDrivenAgent agents.py
2.8 Reflex-Vacuum-Agent ReflexVacuumAgent agents.py Done
2.10 Simple-Reflex-Agent SimpleReflexAgent agents.py
2.12 Model-Based-Reflex-Agent ReflexAgentWithState agents.py
3 Problem Problem search.py Done
3 Node Node search.py Done
3 Queue Queue utils.py Done
3.1 Simple-Problem-Solving-Agent SimpleProblemSolvingAgent search.py
3.2 Romania romania search.py Done
3.7 Tree-Search tree_search search.py Done
3.7 Graph-Search graph_search search.py Done
3.11 Breadth-First-Search breadth_first_search search.py Done
3.14 Uniform-Cost-Search uniform_cost_search search.py Done
3.17 Depth-Limited-Search depth_limited_search search.py Done
3.18 Iterative-Deepening-Search iterative_deepening_search search.py Done
3.22 Best-First-Search best_first_graph_search search.py
3.24 A*-Search astar_search search.py Done
3.26 Recursive-Best-First-Search recursive_best_first_search search.py Done
4.2 Hill-Climbing hill_climbing search.py
4.5 Simulated-Annealing simulated_annealing search.py
4.8 Genetic-Algorithm genetic_algorithm search.py Done
4.11 And-Or-Graph-Search and_or_graph_search search.py Done
4.21 Online-DFS-Agent online_dfs_agent search.py
4.24 LRTA*-Agent LRTAStarAgent search.py Done
5.3 Minimax-Decision minimax_decision games.py Done
5.7 Alpha-Beta-Search alphabeta_search games.py Done
6 CSP CSP csp.py Done
6.3 AC-3 AC3 csp.py Done
6.5 Backtracking-Search backtracking_search csp.py Done
6.8 Min-Conflicts min_conflicts csp.py
6.11 Tree-CSP-Solver tree_csp_solver csp.py Done
7 KB KB logic.py Done
7.1 KB-Agent KB_Agent logic.py Done
7.7 Propositional Logic Sentence Expr logic.py Done
7.10 TT-Entails tt_entails logic.py Done
7.12 PL-Resolution pl_resolution logic.py Done
7.14 Convert to CNF to_cnf logic.py Done
7.15 PL-FC-Entails? pl_fc_resolution logic.py Done
7.17 DPLL-Satisfiable? dpll_satisfiable logic.py Done
7.18 WalkSAT WalkSAT logic.py Done
7.20 Hybrid-Wumpus-Agent HybridWumpusAgent logic.py*
7.22 SATPlan SAT_plan logic.py Done
9 Subst subst logic.py Done
9.1 Unify unify logic.py Done
9.3 FOL-FC-Ask fol_fc_ask logic.py Done
9.6 FOL-BC-Ask fol_bc_ask logic.py Done
9.8 Append
10.1 Air-Cargo-problem air_cargo planning.py Done
10.2 Spare-Tire-Problem spare_tire planning.py Done
10.3 Three-Block-Tower three_block_tower planning.py Done
10.7 Cake-Problem have_cake_and_eat_cake_too planning.py Done
10.9 Graphplan GraphPlan planning.py
10.13 Partial-Order-Planner
11.1 Job-Shop-Problem-With-Resources job_shop_problem planning.py Done
11.5 Hierarchical-Search hierarchical_search planning.py
11.8 Angelic-Search
11.10 Doubles-tennis double_tennis_problem planning.py
13 Discrete Probability Distribution ProbDist probability.py Done
13.1 DT-Agent DTAgent probability.py
14.9 Enumeration-Ask enumeration_ask probability.py Done
14.11 Elimination-Ask elimination_ask probability.py Done
14.13 Prior-Sample prior_sample probability.py
14.14 Rejection-Sampling rejection_sampling probability.py Done
14.15 Likelihood-Weighting likelihood_weighting probability.py Done
14.16 Gibbs-Ask gibbs_ask probability.py
15.4 Forward-Backward forward_backward probability.py Done
15.6 Fixed-Lag-Smoothing fixed_lag_smoothing probability.py Done
15.17 Particle-Filtering particle_filtering probability.py Done
16.9 Information-Gathering-Agent
17.4 Value-Iteration value_iteration mdp.py Done
17.7 Policy-Iteration policy_iteration mdp.py Done
17.7 POMDP-Value-Iteration
18.5 Decision-Tree-Learning DecisionTreeLearner learning.py Done
18.8 Cross-Validation cross_validation learning.py
18.11 Decision-List-Learning DecisionListLearner learning.py*
18.24 Back-Prop-Learning BackPropagationLearner learning.py Done
18.34 AdaBoost AdaBoost learning.py
19.2 Current-Best-Learning current_best_learning knowledge.py Done
19.3 Version-Space-Learning version_space_learning knowledge.py Done
19.8 Minimal-Consistent-Det
19.12 FOIL
21.2 Passive-ADP-Agent PassiveADPAgent rl.py Done
21.4 Passive-TD-Agent PassiveTDAgent rl.py Done
21.8 Q-Learning-Agent QLearningAgent rl.py Done
22.1 HITS HITS nlp.py Done
23 Chart-Parse Chart nlp.py
23.5 CYK-Parse CYK_parse nlp.py Done
25.9 Monte-Carlo-Localization monte_carlo_localization probability.py Done

Index of data structures

Here is a table of the implemented data structures, the figure, name of the implementation in the repository, and the file where they are implemented.

Figure Name (in repository) File
3.2 romania_map search.py
4.9 vacumm_world search.py
4.23 one_dim_state_space search.py
6.1 australia_map search.py
7.13 wumpus_world_inference logic.py
7.16 horn_clauses_KB logic.py
17.1 sequential_decision_environment mdp.py
18.2 waiting_decision_tree learning.py

Acknowledgements

Many thanks for contributions over the years. I got bug reports, corrected code, and other support from Darius Bacon, Phil Ruggera, Peng Shao, Amit Patil, Ted Nienstedt, Jim Martin, Ben Catanzariti, and others. Now that the project is on GitHub, you can see the contributors who are doing a great job of actively improving the project. Many thanks to all contributors, especially @darius, @SnShine, @reachtarunhere, @MrDupin, and @Chipe1.