Ebook: Search in Artificial Intelligence

Search is an important component of problem solving in artificial intelligence (AI) and, more generally, in computer science, engineering and operations research. Combinatorial optimization, decision analysis, game playing, learning, planning, pattern recognition, robotics and theorem proving are some of the areas in which search algbrithms playa key role. Less than a decade ago the conventional wisdom in artificial intelligence was that the best search algorithms had already been invented and the likelihood of finding new results in this area was very small. Since then many new insights and results have been obtained. For example, new algorithms for state space, AND/OR graph, and game tree search were discovered. Articles on new theoretical developments and experimental results on backtracking, heuristic search and constraint propaga­ tion were published. The relationships among various search and combinatorial algorithms in AI, Operations Research, and other fields were clarified. This volume brings together some of this recent work in a manner designed to be accessible to students and professionals interested in these new insights and developments.

---

This book brings together some new insights and recent developments on the topics of search procedures in Artificial Intelligence and the relationships among search methods in Artificial Intelligence, Operations Research, and Engineering. The purpose of the book is to present these new insights and recent developments in a manner accessible to students and professionals in Computer Science, Engineering, Operations Research, and Applied Mathematics. The articles should provide the reader with a broad view of recent developments on search in AI and some of the relationships among branch and bound, heuristic search, and dynamic programming. New models for discrete optimization problems, new results on the average case of complexity of the well known A* algorithm, new results on the conditions under which A* is optimal over other search algorithms, use of different sources of knowledge in heuristic search, new results on the constraint satisfaction problem, and a result showing the minimax back up rule does not do as well as the product rule in some real games.

---

This book brings together some new insights and recent developments on the topics of search procedures in Artificial Intelligence and the relationships among search methods in Artificial Intelligence, Operations Research, and Engineering. The purpose of the book is to present these new insights and recent developments in a manner accessible to students and professionals in Computer Science, Engineering, Operations Research, and Applied Mathematics. The articles should provide the reader with a broad view of recent developments on search in AI and some of the relationships among branch and bound, heuristic search, and dynamic programming. New models for discrete optimization problems, new results on the average case of complexity of the well known A* algorithm, new results on the conditions under which A* is optimal over other search algorithms, use of different sources of knowledge in heuristic search, new results on the constraint satisfaction problem, and a result showing the minimax back up rule does not do as well as the product rule in some real games.
Content:
Front Matter....Pages i-x
The CDP: A Unifying Formulation for Heuristic Search, Dynamic Programming, and Branch-and-Bound....Pages 1-27
An Algebra for Search Problems and Their Solutions....Pages 28-90
A General Branch-and-Bound Formulation for AND/OR Graph and Game Tree Search....Pages 91-130
Average-Case Analysis of Heuristic Search in Tree-Like Networks....Pages 131-165
The Optimality of A*....Pages 166-199
Network Search Algorithms with Modifiable Heuristics....Pages 200-222
Optimal Path-Finding Algorithms....Pages 223-267
Developments with GPS....Pages 268-286
Tree Search and ARC Consistency in Constraint Satisfaction Algorithms....Pages 287-342
Backtrack-Free and Backtrack-Bounded Search....Pages 343-369
Network-Based Heuristics for Constraint-Satisfaction Problems....Pages 370-425
Fundamental Properties of Networks of Constraints: A New Formulation....Pages 426-449
Comparison of the Minimax and Product Back-Up Rules in a Variety of Games....Pages 450-471
Back Matter....Pages 473-482

---

This book brings together some new insights and recent developments on the topics of search procedures in Artificial Intelligence and the relationships among search methods in Artificial Intelligence, Operations Research, and Engineering. The purpose of the book is to present these new insights and recent developments in a manner accessible to students and professionals in Computer Science, Engineering, Operations Research, and Applied Mathematics. The articles should provide the reader with a broad view of recent developments on search in AI and some of the relationships among branch and bound, heuristic search, and dynamic programming. New models for discrete optimization problems, new results on the average case of complexity of the well known A* algorithm, new results on the conditions under which A* is optimal over other search algorithms, use of different sources of knowledge in heuristic search, new results on the constraint satisfaction problem, and a result showing the minimax back up rule does not do as well as the product rule in some real games.
Content:
Front Matter....Pages i-x
The CDP: A Unifying Formulation for Heuristic Search, Dynamic Programming, and Branch-and-Bound....Pages 1-27
An Algebra for Search Problems and Their Solutions....Pages 28-90
A General Branch-and-Bound Formulation for AND/OR Graph and Game Tree Search....Pages 91-130
Average-Case Analysis of Heuristic Search in Tree-Like Networks....Pages 131-165
The Optimality of A*....Pages 166-199
Network Search Algorithms with Modifiable Heuristics....Pages 200-222
Optimal Path-Finding Algorithms....Pages 223-267
Developments with GPS....Pages 268-286
Tree Search and ARC Consistency in Constraint Satisfaction Algorithms....Pages 287-342
Backtrack-Free and Backtrack-Bounded Search....Pages 343-369
Network-Based Heuristics for Constraint-Satisfaction Problems....Pages 370-425
Fundamental Properties of Networks of Constraints: A New Formulation....Pages 426-449
Comparison of the Minimax and Product Back-Up Rules in a Variety of Games....Pages 450-471
Back Matter....Pages 473-482
....