btauro/aima-python

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

aima-python

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.

Structure of the Project

When complete, this project will have Python implementations for all the pseudocode algorithms in the book, as well as tests and examples of use. For each major topic, such as nlp (natural language processing), we provide the following files:

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

Python 3.4 and up

This code requires Python 3.4 or later, and does not run in Python 2. You can install Python 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. All notebooks are available in a binder environment. Alternatively, visit jupyter.org for instructions on setting up your own Jupyter notebook environment.

Installation Guide

To download the repository:

git clone https://github.com/aimacode/aima-python.git

Then you need to install the basic dependencies to run the project on your system:

pip install -r requirements.txt

You also need to fetch the datasets from the aima-data repository:

cd aima-python
git submodule init
git submodule update

Wait for the datasets to download, it may take a while. Once they are downloaded, you need to install pytest, so that you can run the test suite:

pip install pytest

Then to run the tests:

py.test

And you are good to go!

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 is being 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. Another great place for contributors to start is by adding tests and writing on the notebooks. You can see which algorithms have tests and notebook sections below. If the algorithm you want to work on is covered, don't worry! You can still add more tests and provide some examples of use in the notebook!

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

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, @antmarakis, @Chipe1, @ad71 and @MariannaSpyrakou.