You are previewing Artificial Intelligence for Advanced Problem Solving Techniques.
O'Reilly logo
Artificial Intelligence for Advanced Problem Solving Techniques

Book Description

"One of the most important functions of artificial intelligence, automated problem solving, consists mainly of the development of software systems designed to find solutions to problems. These systems utilize a search space and algorithms in order to reach a solution.

Artificial Intelligence for Advanced Problem Solving Techniques offers scholars and practitioners cutting-edge research on algorithms and techniques such as search, domain independent heuristics, scheduling, constraint satisfaction, optimization, configuration, and planning, and highlights the relationship between the search categories and the various ways a specific application can be modeled and solved using advanced problem solving techniques."

Table of Contents

  1. Copyright
  2. Preface
    1. INTENDED AUDIENCE
    2. ORGANIZATION OF THE BOOK
    3. CONCLUSION
  3. Acknowledgment
  4. I. Automated Planning
    1. I. Multi-Vehicle Missions: Architecture and Algorithms for Distributed Online Planning
      1. ABSTRACT
      2. INTRODUCTION
      3. EXAMPLE PROBLEM
        1. Mission Description
        2. UCAV System Description
      4. ARCHITECTURAL CHOICES
        1. Pure Reactive Architectures
        2. Reactive and Deliberative Architectures
        3. Level of Detail in the Plan
        4. Architecture for the Example Problem
      5. PLANNING
        1. Specifying the Mission and the Planning Problem
        2. Motion Planning
        3. Consistent Group Motion
        4. Performing Tasks
        5. Implementation
        6. Computation Time Constraints
      6. EXPERIMENTAL RESULTS
        1. Behavior of the Planning Module
      7. FULL SIMULATION RESULTS
      8. CONCLUSION
      9. ACKNOWLEDGMENT
      10. REFERENCES
    2. II. Extending Classical Planning for Time: Research Trends in Optimal and Suboptimal Temporal Planning
      1. ABSTRACT
      2. INTRODUCTION
        1. Background on Classical Planning
        2. Temporal Planning Motivation
      3. MODELING DURATIVE ACTIONS FOR TEMPORAL PLANNING
        1. Conservative vs. a Nonconservative Model of Actions
        2. Other Nonconservative Models of Actions
      4. TEMPORAL PLANNING IN PLANNING GRAPH APPROACHES
        1. Planning Graphs in Planning
          1. Introduction
          2. Mutual Exclusion (Mutex) Relations
          3. Planning Graphs as a Basis for Heuristic Estimations
          4. Planning for Classical Planning: Graphplan
          5. Pure Planning Graph Approaches
        2. Extension for a Nonconservative Model of Actions
      5. HEURISTIC STATE-BASED APPROACHES
      6. TEMPORAL PLANNING IN POCL APPROACHES
        1. Extending the Classical POCL Algorithm
        2. Cooperation Between POCL Planning and CSP Solving
      7. CONSTRAINT PROGRAMMING FORMULATION FOR TEMPORAL POCL PLANNING
          1. Solving Temporal POCL Planning as Constraint Programming
          2. Discussion
      8. HYBRID APPROACHES
      9. TEMPORAL PLANNERS IN THE INTERNATIONAL PLANNING COMPETITIONS
      10. CONCLUSION
      11. FUTURE DIRECTIONS
      12. ACKNOWLEDGMENT
      13. REFERENCES
      14. ENDNOTES
  5. II. Constraint Satisfaction and Scheduling
    1. III. Principles of Constraint processing
      1. ABSTRACT
      2. INTRODUCTION: WHAT IS CONSTRAINT PROGRAMMING, WHAT ARE ITS ORIGINS AND WHY IS IT USEFUL?
        1. What Is a Constraint?
        2. What Is a Constraint Satisfaction Problem and Its Solution?
        3. A Bit of History
        4. Some Examples
          1. N-Queens
          2. Graph (Map) Colouring
          3. Crypto-Arithmetic
          4. Sudoku
        5. Practical Applications
      3. SYSTEMATIC SEARCH: HOW TO SOLVE CONSTRAINT SATISFACTION PROBLEMS BY SEARCH?
        1. Generate and Test (GT)
          1. Disadvantages
        2. Backtracking (BT)
          1. Disadvantages
        3. Backjumping (BJ)
        4. Backmarking (BM)
        5. Further Reading
      4. CONSISTENCY TECHNIQUES: CAN CONSTRAINTS BE USED MORE ACTIVELY DURING CONSTRAINT SATISFACTION?
        1. Node Consistency (NC)
        2. Arc Consistency (AC)
        3. Directional Arc Consistency (DAC)
          1. From DAC to AC
          2. Is Arc Consistency Sufficient?
        4. Path Consistency (PC)
        5. Directional Path Consistency (DPC)
          1. Why Not Path Consistency?
          2. Path Consistency Still Not Sufficient?
        6. K-Consistency
        7. N-ary and Global Constraints
        8. Further Reading
      5. CONSTRAINT PROGAGATION: CAN WE COMBINE DEPTH-FIRST SEARCH AND CONSISTENCY TECHNIQUES?
        1. Backtracking, Once More
        2. Forward Checking
        3. Partial Look Ahead
        4. Full Look Ahead
        5. Comparison of Propagation Techniques
        6. Further Reading
      6. SEARCH ORDERS AND SEARCH REDUCTION: CAN WE FURTHER IMPROVE EFFICIENCY OF SOLVING ALGORITHMS?
        1. Variable Ordering
        2. Backtrack-Free Search
        3. Value Ordering
        4. Further Reading
      7. CONSTRAINED OPTIMISATION: HOW TO FIND AN OPTIMAL SOLUTION SATISFYING THE CONSTRAINTS?
        1. Branch and Bound
        2. Further Reading
      8. CONCLUSION: WHERE TO GO NEXT?
      9. ACKNOWLEDGMENTS
      10. REFERENCES
    2. IV. Stratified Constraint Satisfaction Networks in Synergetic Multi-Agent Simulations of Language Evolution
      1. ABSTRACT
      2. INTRODUCTION
      3. STRATIFICATION IN LANGUAGE SIMULATIONS
        1. Constraint Satisfaction
        2. Synergetic Linguistics
        3. Inductive Learning and Routinization
        4. Structural Meaning
        5. Referential Meaning
        6. Compositionality
        7. Syntactic Patterns
        8. Synthesis
        9. Distributed Cognition and Alignment in Communication
      4. SPANNING AND STRATIFYING THE CONSTRAINT NETWORK
      5. CONSTRAINT NETWORKING IN A ZIPFIAN PERSPECTIVE
      6. CONCLUSION
      7. ACKNOWLEDGMENT
      8. REFERENCES
      9. ENDNOTES
    3. V. Soft-Constrained Linear Programming Support Vector Regression for Nonlinear Black-Box Systems Identification
      1. ABSTRACT
      2. INTRODUCTION
      3. SOFT-CONSTRAINED LINEAR PROGRAMMING SVR
      4. SIMULATIONS
      5. CONCLUSIONS AND FUTURE WORKS
      6. REFERENCES
  6. III. Machine Learning
    1. VI. Reinforcement Learning and Automated Planning: A Survey
      1. ABSTRACT
      2. INTRODUCTION
      3. BACKGROUND
        1. Planning
          1. Problem Representation
            1. The PDDL Definition Language
          2. Planning Methods
            1. Classical Planning
            2. Neoclassical Planning
        2. Reinforcement Learning
          1. Introduction in Reinforcement Learning
          2. Reinforcement Learning Framework
          3. Optimal Value Functions
        3. Learning and Planning
        4. Reinforcement Learning and Planning
      4. APPROACHES COMBINING PLANNING WITH RL
        1. Planning for Reinforcement Learning
          1. Dyna Architecture
          2. Dyna-Based Methods
            1. Dyna-Q
            2. Queue-Dyna
            3. AHC-Relaxation Planning & Q-Relaxation Planning
            4. Exploration Planning
          3. Prioritized Sweeping-Based Methods
            1. Prioritized Sweeping
            2. Generalized Prioritized Sweeping
            3. Structured Prioritized Sweeping
          4. Other Methods
            1. PLANQ-learning
            2. Reinforcement Learned-TOPs
            3. Teleo-Reactive Q-learning
        2. Reinforcement Learning for Planning
          1. Forward and Bidirectional Planning based on Reinforcement Learning
          2. Extraction of Planning Knowledge from Reinforcement Learners
          3. A Reinforcement Learning Approach to Production Planning
      5. DISCUSSION
      6. REFERENCES
    2. VII. Induction as a Search Procedure
      1. ABSTRACT
      2. INTRODUCTION
      3. A PRAGMATIC APPROACH: VERSION SPACES
        1. A Historical Road Map
        2. Introducing Version Spaces
        3. A Simple Example
      4. INDUCTIVE LOGIC PROGRAMMING THEORY
        1. The Task of ILP
        2. Explanation Semantics
        3. ILP Settings
        4. A Simple Example
        5. Setting Up the Search
          1. Sequential Cover
          2. Clause Generalization Search
          3. The Elements of the Search
        6. Hypothesis Language
          1. Hypothesis Checking
          2. Determinacy
          3. Type and Mode Declarations
        7. Hypothesis Space Traversal
          1. Subsumption
          2. Relative Least General Generalization
          3. Inverse Resolution
          4. Mode-Directed Inverse Entailment
        8. Saturation
        9. Search Strategy
          1. Uninformed Search
          2. Informed Search
        10. Preference Bias and Search Heuristics
          1. Entropy and m-Probability
          2. Bayesian Evaluation
          3. Syntactic Considerations
          4. Positive-Only Evaluation
        11. Other Approaches to ILP
          1. Theory-level Search
          2. Dynamically Changing Search Spaces
          3. Statistical inductive logic programming
      5. EFFICIENT INDUCTIVE LOGIC PROGRAMMING
        1. Reducing the Search Space
          1. Hypothesis Checking and Pruning
          2. Determinacy and Type-mode Declarations
          3. Incremental Search
        2. Efficient Evaluation
        3. Handling Large Datasets
        4. Search Algorithms
        5. Parallelism
      6. APPLICATIONS
        1. Life Sciences
        2. Language Technology
          1. Parser Construction
          2. Phonotactic Modelling
        3. Engineering
      7. CONCLUSION
        1. The Limitations of ILP
        2. The Argument for Prior Knowledge
        3. The Versatility of ILP
        4. Future Directions of ILP
      8. REFERENCES
      9. ENDNOTES
    3. A. APPENDIX: LOGIC PROGRAMMING
    4. VIII. Single- and Multi-Order Neurons for Recursive Unsupervised Learning
      1. ABSTRACT
      2. INTRODUCTION
      3. RELATED THEORY
        1. Higher Order Neurons (HONs)
        2. Evolutionary Self Organizing Maps
      4. EVOLUTIONARY HIGHER ORDER NEURONS (EHONS)
        1. Batch Version of HONs
        2. Chromosome Initialization
        3. Chromosome Structure
        4. Global Search Properties
        5. Fitness Function
      5. RECURSIVE CLUSTERING ALGORITHMS
        1. Notation Used
        2. Overview of Producing Recursive Clustering Ensembles
        3. Splitting the Data
          1. Sorting the Data
          2. Choosing Well-Clustered Data
        4. The Single-Order Recursive Unsupervised Learning Algorithm
        5. The Multi-Order Recursive Unsupervised Learning Algorithm
      6. EXPERIMENTAL RESULTS
        1. Results on Hypothetical Data
      7. RESULTS ON REAL WORLD DATA
        1. Data and Algorithm Descriptions
        2. Correlation with Ground Truth Information in Real World Data
      8. DISCUSSIONS
      9. CONCLUSION
      10. REFERENCES
  7. IV. Optimization
    1. IX. Optimising Object Classification: Uncertain Reasoning-Based Analysis Using CaRBS Systematic Research Algorithms
      1. ABSTRACT
      2. INTRODUCTION
      3. BACKGROUND
      4. CaRBS ANALYSES USING DIFFERENT OBJECTIVE FUNCTIONS
        1. CaRBS Analysis with Objective Function OB1
        2. CaRBS Analyses Using Objective Functions OB2 and OB3
        3. CaRBS Aalyses on Incomplete Company Data Set Using Objective Functions OB2
      5. CONCLUSION
      6. REFERENCES
    2. B. APPENDIX
    3. X. Application of Fuzzy Optimization in Forecasting and Planning of Construction Industry
      1. ABSTRACT
      2. INTRODUCTION
      3. MODIFIED S-CURVE MEMBERSHIP FUNCTION
      4. PROPOSED SYSTEM MODEL
      5. SOLVING POSSIBILISTIC OPTIMIZATION PROBLEMS
        1. Formulation of Problem Statement
        2. Multi Objective Formulations
          1. Index of Quality
          2. Worker Satisfaction Index
          3. Optimization of Objective Function
      6. COMPUTATIONAL RESULTS
      7. DISCUSSION AND SUMMARY
      8. CONCLUSION AND FUTURE WORK
      9. ACKNOWLEDGMENT
      10. REFERENCES
    4. XI. Rank Improvement Optimization Using PROMETHEE and Trigonometric Differential Evolution
      1. ABSTRACT
      2. INTRODUCTION
      3. BACKGROUND
        1. The PROMETHEE Technique
        2. Trigonometric Differential Evolution
      4. MAIN THRUST
        1. Powerstation Data Set
          1. Euclidean Distance
          2. Manhattan Distance
          3. Food Product Data Set
          4. Euclidean Distance
          5. Manhattan Distance
      5. CONCLUSION
      6. REFERENCES
      7. KEY TERMS
        1. Glossary
    5. C. APPENDIX
  8. V. Genetic Algorithms and Programming
    1. XII. Parallelizing Genetic Algorithms: A Case Study
      1. ABSTRACT
      2. INTRODUCTION
        1. Evolutionary Algorithms
        2. Genetic Algorithms
        3. Why They Work: The Schemata Theorem
        4. Premature Convergence
      3. PARALLEL GENETIC ALGORITHMS
        1. Introduction
        2. Classification of Parallel Genetic Algorithms
          1. Micro-Grain GA(mgGA)
          2. Fine-Grain GA (fgGA)
          3. Coarse-Grain GA (cgGA)
            1. Migration Policy
            2. Connection Schemes
            3. Node Structure
          4. Massively Distributed Parallel GA (mdpGA)
      4. CASE STUDY
        1. Ramsey Theory
        2. Approach and Representation
          1. Solution Encoding
          2. Evaluation Function
          3. Crossover
        3. Experiments
          1. Simulated cgGA
          2. Results of Runs for R(3,3,3)
      5. CONCLUSION
      6. REFERENCES
    2. XIII. Using Genetic Programming to Extract Knowledge from Artificial Neural Networks
      1. ABSTRACT
      2. INTRODUCTION
      3. STATE OF THE ART
        1. Genetic Programming
        2. ANN Rule Extraction
      4. KNOWLEDGE EXTRACTION SYSTEMS
        1. Development Premises
        2. System Description
        3. Discovering the Generalization Capacity
        4. Rule Extraction with RANNs for Time Series Forecasts
        5. Optimization of Rules Obtained
      5. GP PARAMETER CONFIGURATION
      6. RESULTS
        1. Redes Feed forward for Classification
        2. Time Series Forecast
      7. CONCLUSION
      8. FUTURE STUDIES
      9. REFERENCES
  9. Compilation of References
  10. About the Contributors