Peter Norvig on Terminology - Dictionary of Arguments
Norvig I 8
Terminology/Russell/Norvig: Although decidability and computability are important to an understanding of computation, the notion of tractability has had an even greater impact. Roughly speaking, a problem is called intractable if the time required to solve instances of the problem grows exponentially with the size of the instances. The distinction between polynomial and exponential growth in complexity was first emphasized in the mid-1960s (Cobham, 1964(1); Edmonds, 1965(2)). It is important because exponential growth means that even moderately large instances cannot be solved in any reasonable time.
Norvig I 106
Pattern databases: The idea behind them is to store these exact solution costs for every possible
subproblem instance (…)
Norvig I 108
Def Problem: A problem consists of five parts: the initial state, a set of actions, a transition model describing the results of those actions, a goal test function, and a path cost function. The environment of the problem is represented by a state space. A path through the state space from the initial state to a goal state is a solution.
Norvig I 135
And/or nodes/search trees: or: In a deterministic environment, the only branching is introduced by the agent’s own choices in each state. We call these nodes OR nodes
And: In a nondeterministic environment, branching is also introduced by the environment’s choice of outcome for each action. We call these nodes AND nodes. A solution for an AND–OR search problem is a subtree that (1) has a goal node at every leaf, (2) specifies one action at each of its OR nodes, and (3) includes every outcome branch at each of its AND nodes.
Norvig I 148
Competitive ratio: Typically, the agent’s objective is to reach a goal state while minimizing cost. (Another possible objective is simply to explore the entire environment.) The cost is the total path cost of the path that the agent actually travels. It is common to compare this cost with the path cost of the path the agent would follow if it knew the search space in advance—that is, the actual shortest path (or shortest complete exploration). In the language of online algorithms, this is called the competitive ratio; we would like it to be as small as possible. >Online search/Norvig.
Norvig I 162
Def Pruning: Pruning allows us to ignore portions of the search tree that make no difference to the final choice.
Def Heuristic evaluation functions: allow us to approximate the true utility of a state without doing a complete search.
Def utility function: (also called an objective function or payoff function), defines the final numeric value for a game that ends in terminal state s for a player p. In chess, the outcome is a win, loss, or draw, with values +1, 0, or 1 2 . Some games have a wider variety of possible outcomes; the payoffs in backgammon range from 0 to +192.
Def Zero-sum game: is (confusingly) defined as one where the total payoff to all players is the same for every instance of the game. Chess is zero-sum. “Constant-sum” would have been a better term, but zero-sum is traditional and makes sense if you imagine each player is charged an entry fee of 1/2 .
Norvig I 165
Minimax Algorithm/gaming: The minimax algorithm (…) computes the minimax decision from the current state. It uses a simple recursive computation of the minimax values of each successor state, directly implementing the defining equations. The recursion proceeds all the way down to the leaves of the tree, and then the minimax values are backed up through the tree as the recursion unwinds. The minimax algorithm performs a complete depth-first exploration of the game tree. For real games, of course, the time cost is totally impractical, but this algorithm serves as the basis for the mathematical analysis of games and for more practical algorithms.
Norvig I 208
Def node consistency: A single variable (corresponding to a node in the CSP network) is node-consistent if all the values in the variable’s domain satisfy the variable’s unary constraints.
Def arc consistency: A variable in a CSP is arc-consistent if every value in its domain satisfies the variable’s binary constraints. More formally, Xi is arc-consistent with respect to another variable Xj if for every value in the current domain Di there is some value in the domain Dj that satisfies the binary constraint on the arc (Xi,Xj). >Constraint Satisfaction Problems/CSP/Norvig.
Norvig I 210
Def Path consistency: Arc consistency tightens down the domains (unary constraints) using the arcs (binary constraints). To make progress on problems like map coloring, we need a stronger notion of consistency. Path consistency tightens the binary constraints by using implicit constraints that are inferred by looking at triples of variables.
Norvig I 211
Def K-consistency: Stronger forms of propagation can K-CONSISTENCY be defined with the notion of k-consistency. A CSP is k-consistent if, for any set of k − 1 variables and for any consistent assignment to those variables, a consistent value can always be assigned to any kth variable.
For forward chaining, backward chaining: see >Software agents/Norvig.
Norvig I 266
Propositions: The idea of associating propositions with time steps extends to any aspect of the world changes over time.
Fluent: We use the word fluent (from the Latin fluents, flowing) to refer an aspect of the world that changes. “Fluent” is a synonym for “state variable”.
Norvig I 346
Skolemize: Skolemization is the process of removing existential quantifiers by elimination. In the simple case, it is just like the Existential Instantiation rule (…):
translate ∃x P(x) into P(A), where A is a new constant.
Norvig I 410
Nondeterministic action: The programming languages community has coined the term demonic nondeterminism for the case where an adversary makes the DEMONIC choices, contrasting this with angelic nonde-
Norvig I 411
terminism, where the agent itself makes the choices. We borrow this term to define angelic semantics for HLA descriptions.
Norvig I 468
Closed-world assumption: as implemented in logic programs, provides a simple way to avoid having to specify lots of negative information. It is best interpreted as a default that can be overridden by additional information.
1. Cobham, A. (1964). The intrinsic computational difficulty of functions. In Proc. 1964 International
Congress for Logic, Methodology, and Philosophy of Science, pp. 24–30.
2. Edmonds, J. (1965). Paths, trees, and flowers. Canadian Journal of Mathematics, 17, 449–467._____________Explanation of symbols: Roman numerals indicate the source, arabic numerals indicate the page number. The corresponding books are indicated on the right hand side. ((s)…): Comment by the sender of the contribution. Translations: Dictionary of Arguments The note [Author1]Vs[Author2] or [Author]Vs[term] is an addition from the Dictionary of Arguments. If a German edition is specified, the page numbers refer to this edition.
Stuart J. Russell
Artificial Intelligence: A Modern Approach Upper Saddle River, NJ 2010