Search
(a subtopic of Reasoning)
 "Search is a problem-solving technique that systematically explores a space of problem states, i.e., successive and alternative stages in the problem-solving process. Examples of problem states might include the different board configurations in a game or intermediate steps in a reasoning process. This space of alternative solutions is then searched to find an answer. Newell and Simon (1976) have argued that this is the essential basis of human problem solving. Indeed, when a chess player examines the effects of different moves or a doctor considers a number of alternative diagnoses, they are searching among alternatives." - from Section 1.2 of Chapter One (available online) of George F. Luger's textbook, Artificial Intelligence: Structures and Strategies for Complex Problem Solving, 5th Edition (Addison-Wesley; 2005). |
Search. From Artificial Intelligence, by David B. Leake, Indiana University [to appear, Van Nostrand Scientific Encyclopedia, Ninth Edition, Wiley, New York, 2002]. "In 1976, Newell and Simon [Newell and Simon1976] proposed that intelligent behavior arises from the manipulation of symbols--entities that represent other entities, and that the process by which intelligence arises is heuristic search. Search is a process of formulating and examining alternatives."
Search lecture slides and accompanying transcripts from Professors Tomás Lozano-Pérez & Leslie Kaelbling's Spring 2003 course, Artificial Intelligence. Available from MIT OpenCourseWare. "Search plays a key role in many parts of AI. These algorithms provide the conceptual backbone of almost every approach to the systematic exploration of alternatives."
Search Definitions and Search Methods from Patrick Doyle. An extensive overview covering topics such as Real-time A*, Constraint-Satisfaction Problems, Game Trees, Alpha-Beta Pruning, Beam Search, Simulated Annealing and Notable Search Programs (Logic Theorist, General Problem Solver, and ABSTRIPS). [Made available via CS 44, Artificial Intelligence, Computer Science Department, Dartmouth College Winter, 1998.]
Cognitive Science 108b: Artificial Intelligence Modeling - Lecture Notes
from John Batali, Associate Professor Department of Cognitive Science,
University of California at San Diego.
Solving Problems by Searching -and- Informed Search Methods. Lecture notes from Dr. Martin Johnson, Massey University, Albany, New Zealand. "This is the essence of search - choosing one option and putting the others aside for later, in case the first choice does not lead to a solution. We continue choosing, testing, and expanding until a solution is found or until there are no more states that can be expanded. The choice of which state to expand first is determined by the search strategy."
"Search encompasses a very general class of algorithms for exploring a problem space in order to find a solution. Virtually every problem can be solved using a search algorithm, although searching can be relatively inefficient for tasks such as arithmetic. Search methods can be divided into systematic and nonsystematic algorithms." From CIRL (The Computational Intelligence Research Laboratory of the University of Oregon). Be sure to follow the links to Subareas at the bottom of their pages for related information.
Searching for Optimal Solutions: the A* Algorithm, IDA* (A Memory-Efficient Variation of A*), and an applet illustrating IDA* with sliding-tile puzzles. An interactive resource from the AIxploratorium.
Search: An Overview. By Ann V. D. L. Gardner. AI Magazine 2(1): 2-6, 23 (Winter 1980). "This article is the second planned excerpt from the Handbook of Artificial Intelligence being complied at Stanford University. This overview of the Handbook chapter on search ... introduces the important ideas and techniques, which are discussed in detail later in the chapter."
A Comparison of Fast Search Methods for Real-Time Situated Agents. By Sven Koenig. In Proceedings of the International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 864-871, 2004. Abstract: "Real-time situated agents, including characters in real-time computer games, often do not know the terrain in advance but automatically observe it within a certain range around them. They have to interleave planning with movement to make planning tractable when moving autonomously to user-specified coordinates. Planning faces real-time requirements since it is important that the agents be responsive to the commands of the users and move smoothly. In this paper, we compare two fast search methods for this task that speed up planning in different ways, namely real-time heuristic search (LRTA*) and incremental heuristic search (D* Lite), resulting in the first comparison of real-time and incremental heuristic search in the literature. We characterize when to choose which search method, depending on the kind of terrain and the planning objective."
- Also see Sven Koenig's Fast Replanning project: "Autonomous agents often need to operate in domains that are only incompletely known or change dynamically. In this case, they need to replan quickly as their knowledge changes. For example, mobile robots or computer-controlled agents in combat games (such as 'Total Annihilation' or 'Warcraft') might observe obstacles in the terrain that they did not know about or their goal locations might change (for example, if they chase moving targets). Replanning from scratch is often very time consuming but combat games have very tight time requirements, need to control many agents, cannot allocate much processor time for the artificial intelligence, and often run on old computers with slow processors. We therefore study planning methods that are incremental versions of heuristic search methods, and analyze their behavior."
All the Needles in a Haystack: Can Exhaustive Search Overcome Combinational Chaos? J. Nievergelt, R. Gasser, F. Maser, C. Wirth. "Exhaustive search is truly a creation of the computer era. Although the history of mathematics records amazing feats of paper-and-pencil computation, as a human activity, exhaustive search is boring, error-prone, exhausting, and never gets very far anyway."
Processing, bottom-up and top-down. Stuart C. Shapiro. 1987. In S. C. Shapiro, editor, Encyclopedia of Artificial Intelligence, 779 - 785. New York: John Wiley & Sons, Inc. "'Bottom-up' vs. 'top-down,' 'forward' vs. 'backward,' and 'data-driven' vs. 'goal-directed' are three pairs of modifiers for terms such as 'chaining,' 'inference,' 'parsing,' 'processing,' 'reasoning,' and 'search.' They express essentially the same distinction, their differences lying in different metaphors drawn from different subareas of computer science and AI. ... One general way to consider the distinction is from within the paradigm of search. The basic issue for all of search is to find a way to get from where you are to where you want to be."
| "The economist Herbert Simon, who reminded us of the futility of trying to consider every possible alternative in a world without end.... It was Simon's ideas - particularly his notion of 'satisficing' - that first got me interested in fiction-writing machines. ... Computers are just as subject as humans to Simon's 'bounded rationality.' Computers cannot create narratives by using brute computational force to mindlessly try every alternative." - from Computers as Authors? Literary Luddites Unite! Essay by Daniel Akst. The New York Times (November 22, 2004). |
AI on the Web: Search and Game Playing. A resource companion to Stuart Russell and Peter Norvig's "Artificial Intelligence: A Modern Approach."
Laboratory Resources on Search and Game Playing. From the 1994 workshop, "Providing and Integrating Educational Resources for Faculty Teaching Artificial Intelligence. LISP program code is offered for A-Star algorithm, the 8-puzzle, Depth-First Search, and many more search methods.
- Decision Trees
- Real-Time Heuristic Search on our Real Time Reasoning page
- Software
- Traveling Salesperson & NP-Complete Problems
Computer Chess and Search. By T.A. Marsland, Computing Science Department, University of Alberta. (Article prepared for the 2nd edition of the Encyclopedia of Artificial Intelligence, S. Shapiro (editor), to be published by John Wiley, 1992.) Sections include: Landmarks in Chess Program Development; Minimax Search; The Alpha-Beta Algorithm; Minimal Game Tree; Forward Pruning; and more.