A Guided Tour of Artificial Intelligence Research: Knowledge Representation and Reasoning: Volume I: Knowledge Representation, Reasoning and Learning

General Presentation of the Guided Tour of Artificial Intelligence Research
Contents
Preface: Knowledge Representation, Reasoning and Learning
Foreword: Knowledge Representation and Formalization of Reasoning
Elements for a History of Artificial Intelligence
	1 Introduction
	2 The First Steps: From Antiquity to the XVIth Century
	3 The XVIIth Century: Preliminary Steps Towards Modernity
	4 The XVIIIth Century: The Age of Enlightenment
	5 The XIXth Century: The Rise of Modern Logic
	6 The First Half of the XXth Century: From Mathematical Logic to Cybernetics
	7 The Beginnings of the AI Era
	8 Conclusion
	References
Knowledge Representation: Modalities, Conditionals, and Nonmonotonic Reasoning
	1 Introduction
	2 Two Basic Modal Logics
		2.1 The Modal Logic K
		2.2 The Modal Logic S5
	3 Two Logics of Conditionals
		3.1 The Normal Conditional Logic CK and Its Extensions
		3.2 The Logic of Lewis–Burgess CL and Its Extensions
	4 From Default Logic to Two Classes of Nonmonotonic Formalisms
		4.1 Preferential Formalisms
		4.2 Rational Formalisms
	5 Conditional Logics in the Light of Dynamic Epistemic Logics
		5.1 Dynamic Epistemic Logics: Public Announcement Logic
		5.2 Public Announcement Logic as a Conditional Logic
		5.3 Discussion
	6 Conclusion
	References
Representations of Uncertainty  in Artificial Intelligence: Probability  and Possibility
	1 Introduction
	2 Imprecision, Contradiction, Uncertainty, Gradualness, and Granularity
		2.1 Imprecise Information
		2.2 Contradictory Information
		2.3 Uncertain Information
		2.4 Graduality and Fuzzy Sets
		2.5 Degree of Truth Versus Degree of Certainty: A Dangerous Confusion
		2.6 Granularity and Rough Sets
	3 Uncertainty: The Probabilistic Framework
		3.1 Frequentists Versus Subjectivists
		3.2 Conditional Probabilities
		3.3 Bayes Rule: Revision Versus Prediction
		3.4 Probability Distributions and Partial Ignorance
		3.5 Conditional Events and Big-Stepped Probabilities
	4 Possibility Theory
		4.1 General Setting
		4.2 Qualitative Possibility Theory
		4.3 Quantitative Possibility and Bridges to Probability
	5 The Cube of Opposition: A Structure Unifying Representation Frameworks
	6 Conclusion
	References
Representations of Uncertainty in AI: Beyond Probability and Possibility
	1  Introduction
	2 Theory of Belief Functions
		2.1 Random Code Semantics
		2.2 Basic Set Functions
		2.3 Combination Rules
		2.4 Imprecision, Specialization and Information Measures
		2.5 Criteria for Decision Under Uncertainty
		2.6 Applications to Statistical Learning and Data Analysis
	3 Imprecise Probabilities
		3.1 Basic Definitions and Interpretations
		3.2 Two Types of Conditioning
	4 Conclusion
	References
Qualitative Reasoning
	1 Introduction
	2 Qualitative Physics
		2.1 Historical Outline
		2.2 Different Aspects of Qualitative Reasoning
		2.3 Evolutions and Trends
	3 Qualitative Spatial and Temporal Reasoning
		3.1 An Overview of the Field
		3.2 Qualitative Calculi
		3.3 Main Problems and Results
		3.4 Perspectives
		3.5 Alternative Approaches
		3.6 Applications of Qualitative Spatial and Temporal Reasoning
	4 Conclusion
	References
Reasoning with Ontologies
	1 Introduction
	2 Description Logics
		2.1 Preliminaries: DL Syntax and Semantics
		2.2 Lightweight Description Logics: mathcalFL0 and mathcalEL
		2.3 DL-Lite: Another Lightweight Description Logic
		2.4 mathcalALC: The Prototypical Description Logic
		2.5 From mathcalALC to mathcalSHIQ to mathcalSROIQ: Highly Expressive DLs
	3 Conceptual Graphs
		3.1 The Kernel: Basic Conceptual Graphs
		3.2 Simple Extensions of the Support
		3.3 Conceptual Graph Rules
		3.4 Conceptual Graph Constraints
		3.5 Relationships with Description Logics
	4 Existential Rules
		4.1 The Existential Rule Framework
		4.2 Relationships with Database Theory
		4.3 Decidability Results
	5 Conclusion
	References
Compact Representation of Preferences
	1 Introduction
	2 Compact Preference Representation Languages
	3 Graphical Languages and Ordinal Preferences: CP-Nets, Variants and Extensions
		3.1 Preferential Independence
		3.2 CP-Nets
		3.3 Semantics of CP-Nets
		3.4 CP-Nets: Comparison and Optimisation
		3.5 Constrained CP-Nets
		3.6 Extensions and Variants of CP-Nets
		3.7 Elicitation and Learning
		3.8 Applications
	4 Graphical Languages and Cardinal Representations  of Preferences: Utility Networks
		4.1 Additively Decomposable Utilities
		4.2 Graphical Models Associated with a Decomposable Utility Function
	5 Logical Languages
		5.1 Logics, Priorities and Weights
		5.2 Preference Logics
	6 Conclusion
	References
Norms and Deontic Logic
	1 Introduction
	2 Obligation to Be and Obligation to Do
		2.1 Standard Deontic Logic
		2.2 Deontic Logic of Actions
	3 Conditional and Contextual Obligations
		3.1 Dyadic Deontic Logic
		3.2 Exceptions
		3.3 Violations
	4 Obligations with Delays
		4.1 The Several Models for Obligations with Delays
		4.2 Criteria and Choice Points for Designing an Operator
	5 Collective Obligation
	6 Conclusion
	References
A Glance at Causality Theories  for Artificial Intelligence
	1 Introduction
	2 Causality in Artificial Intelligence: Issues and Problems
		2.1 Basic Issues and Principles Underlying Causal Links
		2.2 The Use of Causality in AI
	3 Formalizing Causality
		3.1 Relational Models of Causality
		3.2 Modal Logic Setting for Counterfactual Causality
		3.3 Probabilistic Modeling of Causality
		3.4 Causal Bayesian Networks and Interventions
		3.5 Shafer Trees Approach to Causal Conjectures
		3.6 The Preferential Approach to Plausible Causality  and Abnormality
		3.7 Actual Causality: Action Logic
		3.8 The Halpern and Pearl Approach
		3.9 Psychological Models
		3.10 Towards Comparing Models
	4 Conclusion
	References
Case-Based Reasoning, Analogy,  and Interpolation
	1 Introduction
	2 Case-Based Reasoning
		2.1 Basic Notions Related to CBR
		2.2 The CBR Steps
		2.3 Knowledge Acquisition for a CBR System
		2.4 Some CBR Systems
	3 Reasoning by Analogy and Analogical Proportions
		3.1 Analogy in Terms of Mappings
		3.2 Analogy in Terms of Proportions
		3.3 Proportional Analogy in Boolean Logic
		3.4 Analogical Proportions Between Sequences
	4 Interpolative Reasoning
		4.1 Fuzzy Sets and Approximate Reasoning
		4.2 Graduality and Interpolation
		4.3 Similarity-Based Qualitative Reasoning
	5 Conclusion
	References
Statistical Computational Learning
	1 Introduction
	2 Statistical Learning Problems
		2.1 Tasks
		2.2 Models
		2.3 Objective Functions
		2.4 The Framework
	3 Complexity Measures
		3.1 Sample Complexity
		3.2 Runtime Complexity
	4 Learning as Optimization
		4.1 Optimization Principles
		4.2 Conditions for Learnability
	5 Concept Learning
		5.1 VC-Dimension
		5.2 Realizable Concept Learning
		5.3 Agnostic Concept Learning
		5.4 Bagging and Boosting
	6 Convex Learning
		6.1 Convex Learning Problems
		6.2 Convex Learning Algorithms
		6.3 Support Vector Machines
	7 Conclusion
	References
Reinforcement Learning
	1 Introduction
	2 Background for RL
	3 Value-Based Methods with Function Approximation
		3.1 Stochastic Gradient Descent Methods
		3.2 Least-Squares Methods
		3.3 Iterative Projected Fixed-Point Methods
		3.4 Value-Based Deep Reinforcement Learning
	4 Policy-Search Approaches
		4.1 Model-Free Policy Search
		4.2 Model-Based Policy Search
	5 Extensions: Unknown Rewards and Risk-sensitive Criteria
		5.1 Reward Learning
		5.2 Preference-Based Approaches
		5.3 Risk-Sensitive Criteria
	6 Conclusion
	References
Argumentation and Inconsistency-Tolerant Reasoning
	1 Introduction
	2 Reasoning from Inconsistent Information
		2.1 Introduction
		2.2 Models for Reasoning from Inconsistency
	3 Reasoning Based on Virtual Restoration of Consistency
		3.1 Introduction
		3.2 Presentation of Some Variants
		3.3 An Illustrative Example
		3.4 Discussion
	4 Paraconsistent Logics
		4.1 Foundations
		4.2 Paraconsistent Inference
		4.3 An Example: In the Beginning Was the Egg…
	5 Argumentation
		5.1 Introduction
		5.2 Architecture of an Argumentation System
	6 Reasoning in Peer-to-Peer Inference Systems
		6.1 Peer-to-Peer Inference Systems
		6.2 Inconsistency in Peer-to-Peer Inference Systems
		6.3 Illustrative Example
	7 Conclusion
	References
Main Issues in Belief Revision, Belief Merging and Information Fusion
	1 Introduction
	2 Belief Revision
		2.1 Principles and Belief Revision Approaches
		2.2 The AGM Approach and its Variants
		2.3 Representation Theorems
	3 Iterated Revision
		3.1 Postulates for Iterated Revision
		3.2 Extension to Partial Pre-orders
		3.3 Comments on Iterated Revision
	4 Logical Approaches to Merging
		4.1 Semantic Approach to Merging Under Constraint
		4.2 Families of Merging Operators
		4.3 Prioritized Merging, Merging and Iterated Revision
		4.4 Merging in Other Logical Frameworks
	5 Non-Boolean Approaches to Information Revision  and Fusion
		5.1 Valued Revision
		5.2 Information Fusion
		5.3 Semantic Fusion of Weighted Knowledge Bases
	6 Conclusion
	References
Reasoning About Action and Change
	1 Introduction
	2 Reasoning About Action: Models
		2.1 Basic Concepts and the Corresponding Models
		2.2 Types of Reasoning and Their Implementations
	3 Reasoning About Action: Languages
		3.1 Problems Related to the Representation of Actions
		3.2 The Situation Calculus
		3.3 Propositional Action Languages
		3.4 Dynamic Logic
		3.5 Dynamic Bayesian Networks
	4 Reasoning About Change: Update
	5 Conclusion
	References
Multicriteria Decision Making
	1 Introduction
	2 Multicriteria Decision Problems
	3 Preference Aggregation
	4 Decision Models in the CA Approach
		4.1 Dominance Relations
		4.2 Concordance Relations
	5 Decision Models in the AC Approach
		5.1 The Weighted Mean
		5.2 The Weighted Tchebycheff Norm
		5.3 The Ordered Weighted Average (OWA)
		5.4 The Weighted OWA (WOWA)
		5.5 The Choquet Integral
		5.6 The Sugeno Integral
	6 Conclusion
	References
Decision Under Uncertainty
	1 Introduction
	2 The Expected Utility Criterion (EU)
		2.1 von Neumann-Morgenstern\'s Axiomatic Foundation
		2.2 Risk Measures
		2.3 Attitude of Agents with Respect to Risk
		2.4 Some Descriptive Limits of the EU Model
	3 Non-linear Models for Decision Under Risk
	4 Decision Models Outside the Probabilistic Framework
		4.1 Qualitative Decision Models Under Uncertainty
	5 Sequential Decision Models
	6 Conclusion
	References
Collective Decision Making
	1 Introduction
		1.1 Collective Decision Making Problems
		1.2 The Basic Model: Ordinal Preferences
		1.3 The Utilitarian Model, or the Model of Quantitative Preferences
		1.4 Centralized Versus Distributed CDM
		1.5 Discussion
	2 Voting
		2.1 Introduction to Voting Theory
		2.2 Computing Voting Rules
		2.3 Voting on Combinatorial Domains
		2.4 Computational Barriers to Strategic Behaviour
		2.5 Incomplete Knowledge and Communication
		2.6 Some Other Issues
	3 Fair Allocation
		3.1 Fair Allocation Problems
		3.2 Some Real World Fair Allocation Problems
		3.3 How to Define Fairness?
		3.4 Main Aggregation Functions
		3.5 Procedural Allocation of a Divisible and Heterogeneous Resource (Cake-Cutting)
		3.6 Fair Division and Computer Science
	4 Combinatorial Auctions
		4.1 From Classical to Combinatorial Auctions
		4.2 Bidding Languages
		4.3 The Winner Determination Problem
	5 Conclusion
	References
Formalization of Cognitive-Agent Systems, Trust, and Emotions
	1 Introduction
	2 Cognitive-Agent Formal Systems
		2.1 Short History of BDI Systems
		2.2 Basic Concepts
	3 Formalization of Trust
		3.1 Logic-based Trust Models
		3.2 Numerical Models of Trust
		3.3 Applications of Trust Systems
	4 Formalization of Emotions
		4.1 Logical Formalization of Emotions
		4.2 Numerical Models of Emotions
		4.3 Applications of Emotion Models
	5 Conclusion
	References
Negotiation and Persuasion Among Agents
	1 Introduction
	2 Parameters of the Negotiation Process
		2.1 Money
		2.2 Domains of Negotiation
		2.3 Number of Agents
		2.4 Deadlines
	3 Bilateral Negotiation
		3.1 The Axiomatic Perspective
		3.2 Protocols and Strategies for Bilateral Negotiation
	4 Multilateral Negotiation
		4.1 Coordinating Negotiation with a Mediator
		4.2 Extending Bilateral Protocols to the Multilateral Setting
		4.3 Multilateral Negotiation by Local Deals
	5 Persuasion-Based Negotiation
		5.1 Agent Theory
		5.2 Negotiation Dialogues
	6 Conclusion
	References
Diagnosis and Supervision: Model-Based Approaches
	1 Introduction
	2 Logical Framework for Diagnosis
		2.1 Consistency-Based Logical Approach
		2.2 Abductive Approach
		2.3 Extensions
	3 Diagnosis of Discrete Event Systems
		3.1 Temporal Representation and Diagnosis
		3.2 Models of Discrete Event Systems
		3.3 Faults, Observations and Diagnosis of DES
		3.4 Diagnoser Approach and Other Centralized Approaches
		3.5 Distributed and Decentralized Approaches
		3.6 Diagnosability
	4 Bridge Between Model-Based Diagnosis Rooted in AI  and in Automatic Control
		4.1 FDI Community and Approaches for Continuous Systems: Quick Panorama
		4.2 Comparative Analysis and Concept Mapping  for the Model-Based Logical Diagnosis Approach  and the Analytical Redundancy Approach
		4.3 Approaches Taking Advantage of Techniques of Both Fields
	5 Conclusion
	References
Validation and Explanation
	1 Introduction
	2 Validation: Issues and Solutions
		2.1 Different Validation Approaches
		2.2 Knowledge Base Coherence
		2.3 Models Validation
		2.4 Validation, Refinement and Incoherencies Explanation
	3 Explanation: Issues and Solutions
		3.1 From the Track/log of Reasoning to the Explanation
		3.2 Explanation as a Specific Task
		3.3 From Reactive Explanation to Explanatory Dialogue
		3.4 The Dialogical Explanation: the Limits of One Paradigm
	4 Current Issues
		4.1 Validation and Systems Engineering
		4.2 Validation, Explanation and Semantic Web
		4.3 Validation and Ontology
	5 Conclusion
	References
Knowledge Engineering
	1 Introduction
	2 Knowledge Modelling
		2.1 The Notion of Conceptual Model
		2.2 Problem Solving Models
		2.3 From Conceptual Models to Ontologies
	3 Issues and Major Results
		3.1 Knowledge Sources
		3.2 From Knowledge Sources to Models: Research Issues
		3.3 Designing Models: Techniques, Methods and Tools
		3.4 Model Reuse
		3.5 Knowledge Representation in Models
	4 Methodological Issues and Today\'s Applications
		4.1 Linking Language, Knowledge and Media
		4.2 Coping with Data Explosion
		4.3 Managing Distributed Data
		4.4 Leveraging New Knowledge Sources
		4.5 Coping with Knowledge Evolution
		4.6 Collective Versus Personal Knowledge
		4.7 Model Quality Assessment
	5 Conclusion
	References
Afterword – From Formal Reasoning to Trust
Index