A Guided Tour of Artificial Intelligence Research: Ai Algorithms: Volume II: AI Algorithms

General Presentation of the Guided Tour of Artificial Intelligence Research
Contents
Preface: AI Algorithms
Foreword: Algorithms for Artificial Intelligence
Heuristically Ordered Search in State Graphs
	1 Introduction
	2 From Graphs of Subproblems to State Graphs
	3 Sliding-Puzzles, a Fertile Challenge for Heuristically Ordered Search
	4 At the Beginning Was A*
		4.1 Guiding Search With Heuristic Estimates
		4.2 Conditions Under Which A* Stops When Discovering a Minimal Path
		4.3 Comparison Between Algorithms A* When Their Heuristics h Are Underestimating
		4.4 Comparison Between Algorithms A* When Their Heuristics h Are Underestimating and Monotone
	5 Variants in the Programming of A*
	6 Bidirectional Heuristically Ordered Search A*
	7 Relaxations of A*: Sub-admissible Algorithms
	8 Fortunately IDA* Came
	9 Inventing Heuristics as Improvements of Those Already Known
	10 Combining the Heuristic Estimates Obtained  for Subproblems
	11 Formalizing in Order to Open Other Application Fields and Other Solving Methods
		11.1 State Graphs: We Can Be Less Demanding
		11.2 Length of a Path: We Can Get off the Beaten Track
		11.3 States to be Developed: Other Informed Choices
		11.4 Heuristics: Some Other Relaxations Can Preserve Some Guarantees
	12 Conclusion
	References
Meta-heuristics and Artificial Intelligence
	1 Introduction
	2 Perturbative Meta-heuristics
		2.1 Genetic Algorithms
		2.2 Local Search
	3 Constructive Meta-heuristics
		3.1 Greedy Randomised Algorithms
		3.2 Estimation of Distribution Algorithms
		3.3 Ant Colony Optimisation
	4 Hybrid Meta-heuristics
		4.1 Memetic Algorithms
		4.2 Hybridisation Between Perturbative and Constructive Approaches
	5 Intensification Versus Diversification
	6 Applications in Artificial Intelligence
		6.1 Satisfiability of Boolean Formulas
		6.2 Constraint Satisfaction Problems
	7 Discussions
	8 Conclusion
	References
Automated Deduction
	1 Introduction
	2 First-Order Logic
	3 The Resolution Method
		3.1 Transformation to Clausal Form
		3.2 Unification
		3.3 The Superposition Calculus
		3.4 Redundancy Elimination
		3.5 Implementation Techniques
		3.6 Termination: Some Decidable Classes
		3.7 Proof by Instantiation
		3.8 Equational Unification
		3.9 Model Building
	4 Semantic Tableaux
		4.1 Propositional Tableaux
		4.2 Tableaux for First Order Logic
		4.3 Free Variable Tableaux
	5 Non Classical Logics
		5.1 An Implicit Tableaux Calculus
		5.2 An Explicit Tableaux Calculus
	6 Dealing with Incompleteness
		6.1 Induction
		6.2 Logical Frameworks or Proof Assistants
	7 Conclusion
	References
Logic Programming
	1 Introduction
	2 Logic Programming
		2.1 From Logic to Logic Programming
		2.2 Logic Programming with Horn Clauses
		2.3 The Prolog Language
		2.4 Beyond Logic Programming in Horn Clauses
	3 Constraint Logic Programming
		3.1 The CLP Scheme and CLP(mathcalR)
		3.2 CLP(FD)
		3.3 Writing Your Own Solver with CLP
		3.4 Some CLP Systems
	4 Answer Set Programming
		4.1 Theoretical Foundations
		4.2 ASP and (More or Less) Traditional Logic
		4.3 Knowledge Representation and Problem Resolution  in ASP
		4.4 ASP Solvers
		4.5 Discussion
	5 Conclusion
	References
Reasoning with Propositional Logic: From SAT Solvers to Knowledge Compilation
	1 Introduction
	2 Reasoning in Propositional Logic
		2.1 SAT: Searching for Models
		2.2 Reasoning is Proving a Semantic Consequence
		2.3 Simplifications and Normalized Rewritings of Sub-formulas
		2.4 Reasoning by Calculus: The Resolution Rule
	3 What Kind of Problems Can Typically be Tackled by SAT?
		3.1 SAT from a Theoretical Point of View
		3.2 SAT from a Practical Point of View
	4 Pragmatic Approaches to Attack SAT
		4.1 Incomplete Algorithms
		4.2 Complete, Systematic Algorithms
		4.3 Preprocessing of Formulas
		4.4 Exotic Methods
		4.5 On the Limits and Challenges for Sat Solvers
	5 Knowledge Compilation
		5.1 Principles of KC
		5.2 The ``Beginnings\'\' of KC: Prime Implicates and Implicants
		5.3 Approximation of Knowledge Bases
		5.4 Abstraction of KC Principles
		5.5 Examples of KC Applications: ATMS and Model-Based Diagnosis
	6 Quantified Boolean Formulas
		6.1 Solving QBF in Practice
	7 Conclusion
	References
Constraint Reasoning
	1 Introduction
	2 Definitions
	3 Chronological Backtracking
	4 Constraint Propagation
		4.1 Consistency on One Constraint at a Time
		4.2 Strong Consistencies
	5 Polynomial Cases
	6 Solution Synthesis and Decompositions
	7 Improving Chronological Backtracking
		7.1 Look Back
		7.2 Look Ahead
		7.3 Variable and Value Ordering Heuristics
	8 Other Techniques to Improve Search
		8.1 Non-standard Backtracking Search
		8.2 Large Neighborhood Search
		8.3 Symmetries
	9 Global Constraints
	10 Conclusion
	References
Valued Constraint Satisfaction Problems
	1 Introduction
	2 Valued Constraint Networks
		2.1 Valuation Structure
		2.2 Cost Function Networks
		2.3 Operations on the Cost Functions
		2.4 Links with Other Approaches
	3 Dynamic Programming and Variable Elimination
		3.1 Partial Variable Elimination or ``Mini-Buckets\'\'
	4 Search for Optimal Solutions
	5 Propagation of Valued Constraints
	6 Complexity and Tractable Classes
	7 Solvers and Applications
	8 Conclusion
	References
Belief Graphical Models for Uncertainty Representation and Reasoning
	1 Introduction
	2 Preliminary Concepts and Definitions
		2.1 Probability Theory
		2.2 Conditional Independence
		2.3 Graph Concepts
		2.4 Graphical Encoding of Independence Relations
	3 Probabilistic Graphical Models
		3.1 Bayesian Networks
	4 Reasoning and Inference in Bayesian Networks
		4.1 Main Reasoning Tasks
	5 Learning and Classification with Bayesian Networks
		5.1 Parameter Learning
		5.2  Structure Learning
		5.3 Hybrid Learning
		5.4 Classification
	6 Main Variants of Probabilistic Graphical Models
		6.1 Influence Diagrams
		6.2 Dynamic Bayesian Networks
		6.3 Credal Networks
		6.4 Markov Networks
	7 Non Probabilistic Belief Graphical Models
		7.1 Possibilistic Graphical Models
		7.2 Kappa Networks
	8 Applications
		8.1 Main Application Domains
		8.2 Applications in Computer Security
		8.3 Software Platforms for Modeling and Reasoning with Probabilistic Graphical Models
	9 Conclusion
	References
Languages for Probabilistic Modeling Over Structured and Relational Domains
	1 Introduction
	2 Probabilistic Logics: The Laws of Thought?
	3 Bayesian Networks and Their Diagrammatic  Relational Extensions
	4 Probabilistic Logic Programming
	5 Probabilistic Logic, Again; and Probabilistic  Description Logics
	6 Markov Random Fields: Undirected Graphs
	7 Probabilistic Programming
	8 Inference and Learning: Some Brief Words
	9 Conclusion
	References
Planning in Artificial Intelligence
	1 Introduction
	2 Classical Planning
		2.1 Propositional STRIPS Planning Framework
		2.2 A Language for the Description of Planning Problems: PDDL
		2.3 Structural Analysis of Problems in Classical Planning
		2.4 Main Algorithms and Planners
	3 Probabilistic Planning with Intensional Representations
		3.1 The Markov Decision Processes Framework
		3.2 Intensional Representation of MDPs
		3.3 Algorithms and Planners
	4 Other Extensions to the MDP Framework in Artificial Intelligence
		4.1 Partially Observed Markov Decision Processes
		4.2 Markov Decision Processes and Learning
		4.3 Qualitative Approaches to Markov Decision Processes
	5 Conclusion
	References
Artificial Intelligence for Games
	1 Introduction
	2 Minimax, Alpha-Beta and Enhancements
		2.1 Minimax
		2.2 Alpha-Beta
		2.3 Transposition Table
		2.4 Iterative Deepening
		2.5 MTD(f)
		2.6 Other Alpha-Beta Enhancements
		2.7 Best First Search
	3 Monte Carlo Search
		3.1 Monte Carlo Evaluation
		3.2 Monte Carlo Tree Search
	4 Puzzles
		4.1 A*
		4.2 Monte Carlo
		4.3 Further Readings
	5 Retrograde Analysis
		5.1 Endgame Tablebases
		5.2 Pattern Databases
		5.3 Further Topics
	6 AI in Video Games
		6.1 Transitioning from Classical Games to Video Games
		6.2 AI in the Game Industry: Scripting and Evolution
		6.3 Research Directions: Adaptive AI and Planning
		6.4 New Research Directions for Video Game AI
	7 Conclusion
	References
Designing Algorithms for Machine Learning and Data Mining
	1 Introduction
	2 Classical Scenarios for Machine Learning
		2.1 The Outputs of Learning
		2.2 The Inputs of Learning
	3 Designing Learning Algorithms
		3.1 Three Questions that Shape the Design of Learning Algorithms
		3.2 Unsupervised Learning
		3.3 Supervised Learning
		3.4 The Evaluation of Induction Results
		3.5 Types of Algorithms
	4 Clustering
		4.1 Optimization Criteria and Exact Methods
		4.2 K-Means and Prototype-Based Approaches
		4.3 Generative Learning for Clustering
		4.4 Density-Based Clustering
		4.5 Spectral Clustering, Non Negative Matrix Factorization
		4.6 Hierarchical Clustering
		4.7 Conceptual Clustering
		4.8 Clustering Validation
	5 Linear Models and Their Generalizations
	6 Multi-layer Neural Networks and Deep Learning
		6.1 The Multi-layer Perceptron
		6.2 Deep Learning: The Dream of the Old AI Realized?
		6.3 Convolutional Neural Networks
		6.4 The Generative Adversarial Networks
		6.5 Deep Neural Networks and New Interrogations on Generalization
	7 Concept Learning: Structuring the Search Space
		7.1 Hypothesis Space Structured by a Generality Relation
		7.2 Four Illustrations
	8 Probabilistic Models
	9 Learning and Change of Representation
	10 Other Learning Problems
		10.1 Semi-supervised Learning
		10.2 Active Learning
		10.3 Online Learning
		10.4 Transfer Learning
		10.5 Learning to Rank
		10.6 Learning Recommendations
		10.7 Identifying Causality Relationships
	11 Conclusion
	References
Formal Concept Analysis: From Knowledge Discovery to Knowledge Processing
	1 Introduction
	2 The Basics of Formal Concept Analysis
		2.1 Context, Concepts and the Concept Lattice
		2.2 Rules and Implications
		2.3 Algorithms for Computing Concepts
		2.4 The Stability Measure
	3 Pattern Structures
		3.1 Introduction
		3.2 Interval Pattern Structures
		3.3 Projections and Representation Context for Pattern Structures
	4 Relational Models in FCA
		4.1 Relational Concept Analysis
		4.2 Graph-FCA
	5 Triadic Concept Analysis
	6 Applications
	7 Conclusion
	References
Constrained Clustering: Current  and New Trends
	1 Introduction
	2 Constrained Clustering
		2.1 Cluster Analysis
		2.2 User Constraints
	3 Extensions of Classic Clustering Algorithms to User Constraints
		3.1 k-Means
		3.2 Metric Learning
		3.3 Spectral Graph Theory
	4 Declarative Approaches for Constrained Clustering
		4.1 Overview
		4.2 Integer Linear Programming
		4.3 Constraint Programming
	5 Collaborative Constrained Clustering
		5.1 Ensemble Clustering
		5.2 Collaborative Clustering
	6 New Trends
		6.1 Interactive and Incremental Constrained Clustering
		6.2 Beyond Constraints: Exploratory Data Analysis
	7 Conclusions
	References
Afterword—Artificial Intelligence  and Operations Research
1 Operations Research
2 Artificial Intelligence
3 The Common Fight of OR and AI against Complexity
4 Conclusion
	References
Index