p.21 Games can generate extremely large search spaces. These are large and complex enough to require
powerful techniques for determining what alternatives to explore in the problem space. These techniques are called
heuristics and constitute a major area of AI research. A heuristic is a useful but potentially fallible problem-solving
strategy... Much of what we commonly call intelligence seems to reside in the heuristics used by humans to solve problems.
p.27 While humans plan effortlessly, creating a computer program that can do the same is a difficult challenge.
p.31 As we mentioned in the discussion of agent-oriented problem solving, objects take on meaning
through their relationships with other objects.
p.35 From an engineering perspective, the description of artificial intelligence presented
in Section 1.3 may be summarized as the study of representation and search through which intelligent activity
can be enacted on a mechanical device. This perspective has dominated the origins and growth of AI.
p.37 The function of any representation scheme is to capture - often called abstract
out - the critical features of a problem domain and make that information accessible to a problem-solving procedure.
Abstraction is an essential tool for managing complexity as well as an important factor in assuring
that the resulting programs are computationally efficient.
p.41 Given a representation, the second component of intelligent problem solving is search.
Humans generally consider a number of alternative strategies on their way to solving a problem. A chess player typically
reviews alternative moves, selecting the "best" according to criteria such as the opponent's possible responses or the degree
to which various moves support some global game strategy.
p.44 Chess, for example, has approximately 10 [to the power of] 120 different board states... Search of
this space is beyond the capabilities of any computing device... Humans use intelligent search: a chess player considers
a number of possible moves, a doctor examines several possible diagnoses, a computer scientist entertains different
designs before beginning to write code. Humans do not use exhaustive search: the chess player examines only
moves that experience has shown to be effective... Human problem solving seems to be based on judgmental rules that
guide search to those portions of the state space that seem most "promising".
These rules are known as heuristics, and they constitute one of the
central topics of AI research. A heuristic (the name is taken from the Greek word "to discover") is
a strategy for selectively searching a problem space. It guides search along lines that have a high probability of
success while avoiding wasted or apparently stupid efforts. Human beings use a large number of heuristics in problem solving...
State space search gives us a means of formalizing the problem-solving process, and heuristics allow us to infuse that formalism
with intelligence... In summary, state space search is a formalism, independent of any particular search strategies, and used
as a launch point for many problem solving approaches.
p.123 Intelligence for a system with limited processing resources consists in making wise choices
of what to do next. . . . - Newell and Simon, 1976, Turing Award Lecture
p.124 A problem may have an exact solution, but the computational cost of finding it may be prohibitive.
In many problems (such as chess), state space growth is combinatorially explosive, with the number of possible states
increasing exponentially or factorially with the depth of the search. In these cases, exhaustive, brute-force
search techniques such as depth-first or breadth-first search may fail to find a solution within any practical length of time.
Heuristics attack this complexity by guiding the search along the most "promising" path through the space. By eliminating
unpromising states and their descendants from consideration, a heuristic algorithm can (its designer hopes) defeat this combinatorial
explosion and find an acceptable solution. [JLJ - Yes, but complexity unfortunately conspires to create situations which
initially look unpromising, but due to unexpected interactions at the micro level, there emerge unexpected global effects.
We must construct resilient positions full of adaptive capacity to protect against (or anticipate) the unknown and the unforeseen.]
p.159 In the attempt to bring down the branching of a search or otherwise constrain the search space, we
presented the notion of more informed heuristics. The more informed the search, the less the space that must be searched
to get the minimal path solution. As we pointed out in Section 4.4, the computational costs of the additional information
needed to further cut down the search space may not always be acceptable. In solving problems on a computer, it is not enough
to find a minimum path. We must also minimize total cpu costs.
p.161 The search spaces for interesting problems tend to grow exponentially; heuristic search is
a primary tool for manging this combinatorial complexity... The discipline of complexity theory has essential ramifications
for virtually every branch of computer science, especially the analysis of state space growth and heuristic pruning. Complexity
theory examines the inherent complexity of problems (as opposed to algorithms applied to these problems). The key conjecture
in complexity theory is that there exists a class of inherently intractable problems. This class, referred to as NP-hard (Nondeterministically
Polynomial), consists of problems that may not be solved in less than exponential time without resorting to the use of heuristics.
Almost all interesting search problems belong to this class.
p.277 The first principle of knowledge engineering is that the problem-solving power exhibited by
an intelligent agent's performance is primarily the consequence of its knowledge base, and only secondarily a consequence
of the inference method employed. Expert systems must be knowledge-rich even if they are methods-poor. This
is an important result and one that has only recently become well understood in AI. For a long time AI has focused its attention
almost exclusively on the development of clever inference methods; almost any inference method will do. The power
resides in the knowledge. - Edward Feigenbaum, Stanford University
p.364 One approach, Bayesian belief networks or BBNs (Pearl 1988), offers a computational model
for reasoning to the best explanation of a set of data in the context of the expected causal relationships of a problem domain.
Bayesian belief networks can dramatically reduce the number of parameters of the full Bayesian
model and show how the data of a domain (or even the absence of data) can partition and focus reasoning. Furthermore, the
modularity of a problem domain often allows the program designer to make many independence assumptions not allowed in a full
Bayesian treatment.
p.557 An important insight supporting the design of graphical models is that we can very often determine
that several variables exhibit independencies with respect to each other in the context of the problem being modeled. Since
the complexity of inference in Bayesian belief networks depends on the number of dependencies between variables in the model,
we wish to have as few dependencies as possible while still preserving the validity of the model. In other words, we want
to prune away an many (unnecessary) dependencies as possible from the fully connected graph.
p.675 Based on our experience of the last 15 chapters, we offer a revised definition of artificial intelligence:
AI is the study of the mechanisms underlying intelligent behavior through the construction and evaluation
of artifacts designed to enact those mechanisms.
p.678 Heuristics are the third component, along with representation and search, of symbol-based AI. A
heuristic is a mechanism for organizing search across the alternatives offered by a particular representation. Heuristics
are designed to overcome the complexity of exhaustive search, the barrier to useful solutions for many classes of
interesting problems. In computing, just as for humans, intelligence requires the informed choice of "what to do next".
