Thornton / Du Boulay Artificial Intelligence Through Search

Erscheinungsjahr 2012
ISBN: 978-94-011-2836-0
Verlag: Springer Netherland
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 365 Seiten, eBook

This is an important textbook on artificial intelligence that uses the unifying thread of search to bring together most of the major techniques used in symbolic artificial intelligence. The authors, aware of the pitfalls of being too general or too academic, have taken a practical approach in that they include program code to illustrate their ideas. Furthermore, code is offered in both POP-11 and Prolog, thereby giving a dual perspective, highlighting the merits of these languages. Each chapter covers one technique and divides up into three sections: a section which introduces the technique (and its usual applications) andsuggests how it can be understood as a variant/generalisation of search; a section which developed a `low'-level (POP-11) implementation; a section which develops a high-level (Prolog) implementation of the technique. The authors also include useful notes on alternative treatments to the material, further reading and exercises. As a practical book it will be welcomed by a wide audience including, those already experienced in AI, students with some background in programming who are taking an introductory course in AI, and lecturers looking for a precise, professional and practical text book to use in their AI courses. About the authors: Dr Christopher Thornton has a BA in Economics, an Sc in Computer Science and a DPhil in Artificial Intelligence. Formerly a lecturer in the Department of AI at the University of Edinburgh, he is now a lecturer in AI in the School of Cognitive and Computing Sciences at the University of Sussex. Professor Benedict du Boulay has a BSc in Physics and a PhD in Artificial Intelligence. Previously a lecturer in the Department of Computing Science at the University of Aberdeen he is currently Professor of Artificial Intelligence, also in the School of Cognitive and Computing Sciences, University of Sussex.

Zielgruppe

Research

Autoren/Hrsg.

Thornton, Chris

Du Boulay, Benedict

Inhaltsverzeichnis

1 Search-Related Techniques in AI.- Why search.- Objectives.- Problem-solving systems.- State space search and problem reduction.- Blind search and heuristic search.- Graphs and trees.- Organisation of the book.- Searching for a solution path in a state space.- Problem reduction.- A very brief comparison of POP-11 and Prolog.- Further reading.- 2 Simple State Space Search.- Path-finding.- Setting up the database.- Setting up the path-finding function.- The generality of search.- Search spaces and search trees.- Constructing an explicit representation of the search-tree.- Search graphs.- Node terminology.- Backwards v. forwards searching.- OR-tree search in Prolog.- Reading.- Exercises.- 3 State Space Search.- The water jugs problem.- Constructing successor nodes.- The problem space.- Searching for a solution path.- Problem space exploration strategies.- Breadth-first search.- Agendas.- Implementing depth-first search using an agenda.- Iterative deepening.- Water jugs in Prolog.- Agendas in Prolog.- Iterative deepening in Prolog.- Reading.- Exercises.- Notes.- 4 Heuristic State Space Search.- The 8-puzzle.- Constructing 8-puzzle successors.- Heuristic search.- Hill-climbing search.- Heuristic breadth-first search.- Ordered search and the A* Algorithm.- Heuristic Search in Prolog.- Reading.- Exercises.- Notes.- 5 Heuristic Search of Game Trees.- Computing successors in the game of nim.- Minimax evaluation.- Worked example.- Alpha-beta cutoffs.- Implementing a nim-playing program.- Minimaxing in Prolog.- Reading.- Exercises.- Notes.- 6 Problem Reduction (AND/OR-tree search).- Problem-reduction and the Tower of Hanoi.- Implementing arbitrary AND/OR-trees.- Implementing the AND/OR-tree search function.- Implementing planning as AND/OR-tree search.- Implementing reasoning asAND/OR-tree search.- Loops in the search space.- Solution tree.- The AND/OR search tree.- State space search and problem reduction.- Forward AND/OR-tree search.- Terminology.- Production systems.- AND/OR Search in Prolog.- Reading.- Exercises.- Notes.- 7 Planning (microworld search).- Operators.- Strategies for microworld search.- Implementing the new search function.- Difference tables.- Goal interactions.- Operators containing variables.- Simple plan finding in Prolog.- Reading.- Exercises.- 8 Parsing (search as analysis).- Solution trees as analyses.- Parsing.- Data-driven (bottom-up) parsing.- Building trees bottom-up.- Advantages of bottom-up search.- Backwards and forwards parsing in Prolog.- The Prolog grammar rule formalism.- Bottom-up parsing in Prolog.- Why is parsing useful.- Building a top-level interpreter.- Meaning in Prolog.- Reading.- Exercises.- 9 Expert Systems (probabilistic search).- Probabilistic rules.- Basic probability theory.- Fuzzy set theory.- MYCIN-like search.- Implementing certainty-factors.- Forwards or backwards.- Probabilistic search in Prolog.- Reading.- Exercises.- 10 Concept learning (description search).- Generalisation hierarchies.- Deriving extensions.- Quantifying generality.- Concept learning.- Implementing the generalisation mechanism.- The focussing algorithm.- Focussing in Prolog.- Generalisation as search.- Reading.- Exercises.- 11 Prolog (search as computation).- Search rules as predicates.- The use of variables in search rules.- Data structures.- Unification.- Implementing the unification matcher.- Machinery to deliver output.- The search function.- Programming in Toyplog.- A sample interaction with Toyplog.- Reading.- Exercises.- Notes.- References.- Appendix A: Introduction to POP-11.- Starting POP-11.- POP-11 as a calculator.- Variables.- Functions.- Defining functions.- Local variables.- Boolean expressions.- Conditionals.- Words and lists.- Hats.- For loops.- Applist.- Syssort.- Matching.- Restriction procedures.- The matcher arrow.- The database.- Readline.- Functions calling functions.- Recursion.- Tracing.- Showtree.- Exiting from a function.- Partial application.- Concluding comment.- Appendix B Where to get the source code.