Title: Theory / Important / CS / Algo / Artificial intelligence / Introduction{ / 1 Introduction;
Tags: fromMath mathToDef examplesSwitchExample1 fromAlgorithm hasNotNewEffectReturnsMeaning Programming oldAlgoNewName mathToSee effectToImplementation hasSeenConjDef computer_to_instruction defToCS list typeToSuperType FromInstruction automaticImplies closed doublon instructionToImplementation keepAlgo

Name: Natural language processing
Definition: To enable it to communicate successfully in English.
Page: 002
Chapter: 1
Section: 1.1

Name: knowledge representation
Definition: To store what it knows or hears;
Page: 002
Chapter: 1
Section: 1.1

Name: Automated reasoning
Definition: To use the stored information to answer questions and to draw new conclusions.
Page: 003
Chapter: 1
Section: 1.1

Name: Turing Test
Definition: A computer passes the test if a human interrogator, after posing some written questions, cannot tell whether the written responses come from a person or from a computer.
Page: 003
Chapter: 1
Section: 1.1

Name: Computer vision
Definition: To perceive objects
Page: 003
Chapter: 1
Section: 1.1

Name: Robotics
Definition: To manipulate objects and move about.
Page: 003
Chapter: 1
Section: 1.1

Q: An [...] is [...]
A: agent; anything that can be viewed as perceiving its environment through sensors and acting upon that environment through actuators.
Page: 004
Chapter: 1
Section: 1.4

Name: A sensor
Definition: Object used to perceive environment.
Page: 034
Chapter: 2
Section: 1
Example: Camera
Example2: mic
Example3: keyboard

Name: Actuator
Definition: Object used to act on the environment.
Page: 034
Chapter: 2
Section: 1
Example: motors, wheel
Example2: sound system
Example3: Screen
Example4: manipulation of the virtual world

Name: The percept
Definition: Agent's perceptual input at any given instant.
Page: 034
Chapter: 2
Section: 1
Example: Text
Example2: image
Example3: sound

Name: The percept sequence
Definition: Everything the agent has peirceved
Page: 034
Chapter: 2
Section: 1

Name: The performance measure
Definition: Evaluates the sequence of environment states.
Page: 037
Chapter: 2
Example: For the vacuum cleaner: one point by clean location at each step
Extra: Not we evaluate environment and not agent.

Name: A rational agent
Definition: An agent such that, for each possible percept sequence, it selects an action that is expected to maximize its performance measure, given the evidence provided by the percept sequence and whatever built-in knowledge the agent has.
Page: 037
Chapter: 2
Section: 2.1

Name: Omnicient agent
Definition: Agent which knows the actual outcomes of its actions.
Page: 038
Chapter: 2
Section: 2.2

Name: Information gathering
Definition: An action performed to modify future percepts.
Page: 039
Chapter: 2
Section: 2.2
Example: Exploration of other locations, for the vacuum cleaner

Name: Autonomous agent
Definition: An agent which learns to compensate for partial or incorrect prior knowledge.
Page: 039
Chapter: 2
Section: 2.2

Name: A task environement
Definition: Performance measure
Page: 040
Chapter: 2
Section: 3.1
Definition2: Environment
Conjdef: All of
Definition3: Actuators and Sensors

Name: A fully observable environment
Definition: An environnement to which agent's sensors have acces to the complete state at each point in time.
Page: 042
Chapter: 2
Section: 3.2
Example: Chess

Name: A partially observable environment
Definition: An environment which is not fully observable nor unobservable.
Page: 042
Chapter: 2
Section: 3.2
Example: Most card game

Name: An unobservable environment
Definition: An environment in which the agent has no sensors.
Page: 042
Chapter: 2
Section: 3.2

Name: A competitive multi-agent environment
Definition: A multi-agent environment where increasing one agent's performance measure decrease the performance measure of other agents.
Page: 043
Chapter: 2
Section: 3.2
Example: Chess

Name: A cooperative multi-agent environment
Definition: An environment in which increasing one agent's performance measure increases the performance measure of other agents.
Page: 043
Chapter: 2
Section: 3.2
Example: Avoiding collisions of cars

Name: A partially competitive multi-agent environment
Definition: A multi-agent environment which is competitive for some measures and cooperative for some other measures.
Page: 043
Chapter: 2
Section: 3.2
Example: Parking

Name: A deterministic agent environment
Definition: An agent whose next state is completely determined by the current state and the action executed by the agent.
Page: 043
Chapter: 2
Section: 3.2
Example: Chess

Name: A stochastic agent environment
Definition: An agent environment which is not deterministic.
Page: 043
Chapter: 2
Section: 3.2
Example: Driving

Name: An episodic task
Definition: A task such that each action does not depends on the previous actions.
Page: 043
Chapter: 2
Section: 3.2
Example: Chess

Name: A sequential task
Definition: A task whose actions depend on the previous actions.
Page: 043
Chapter: 2
Section: 3.2
Example: Vaacum world

Name: A static environment
Definition: An environement which does not change while the agent is deliberating.
Page: 044
Chapter: 2
Section: 3.2
Example: Chess

Name: A dynamic environment
Definition: An environment which changes while the agent is deliberating.
Page: 044
Chapter: 2
Section: 3.2
Example: Driving

Name: Semidynamic task
Definition: A task where the environment is static but the performance count changes while the agent is deliberating.
Page: 044
Chapter: 2
Section: 3.2
Example: Chess with a clock

Name: Discrete problem
Definition: A problem which has a finite number of possible value.
Page: 044
Chapter: 2
Section: 3.2
Example: Chess

Name: Continuous
Definition: Something which has an infinite number of possible value.
Page: 044
Chapter: 2
Section: 3.2
Example: Driving

Name: An (un)known environment
Definition: An environment whose outcomes or outcomes probabilities are (un)know.
Page: 044
Chapter: 2
Section: 3.2

Name: The architecture of \(A\)
Definition: Its computing device with sensors and actuators.
Page: 046
Chapter: 2
Section: 4
Variables: \(A\) an agent

Name: A condition-action rule
Definition: A rule of the form «if condition then action».
Page: 048
Chapter: 2
Section: 4.2
Example: If car in front is braking then brake

Name: A model of \(A\)
Definition: A representation of how the word works.
Page: 050
Chapter: 2
Section: 4.3
Variables: \(A\) an agent

Name: A model-based agent
Definition: An agent which has an internal state based on a model of the word.
Page: 050
Chapter: 2
Section: 4.3

Name: A goal-based agent
Definition: An agent which tries to attein a goal.
Page: 052
Chapter: 2
Section: 4.4
Example: Taxi
Example2: chess

Name: Internalization of the performance measure
Page: 053
Chapter: 2
Section: 4.5
Example: Decreasing time, cost

Name: The critic of \(A\)
Definition: Gives feedback about how the performance element should be modified to do better in the future.
Page: 055
Chapter: 2
Section: 4.6
Variables: \(A\) a learning agent.

Name: The learning element
Definition: The part of a learning agent responsible for making improvements.
Page: 055
Chapter: 2
Section: 4.6

Name: The performance element
Definition: The part of a learning agent responsible for choosing actions.
Page: 055
Chapter: 2
Section: 4.6

Name: The problem generator of \(A\)
Definition: The part responsible for suggesting actions that will lead to new and informative experiences.
Page: 056
Chapter: 2
Section: 4.5
Variables: \(A\) a learning agent

Question: The performance standard distinguishes part of the incoming percept as
Answer: a reward or penalty.
Page: 055
Chapter: 2
Section: 4.5

Name: Atomic representation of the world
Definition: Each state of the word is indivisible.
Page: 057
Chapter: 2
Section: 4.7

Name: A goal of \(P\)
Typ: A set of world state
Page: 065
Section: 1
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Name: Problem formulation
Definition: The process of deciding what actions and states to consider, given a goal.
Page: 065
Section: 1

Smaller0: \(P\) is discrete,
Greater0: a fixed sequence of actions
Page: 065, 066
Section: 1
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
Prefix Greater: the solution to
Smaller1: deterministic,
Smaller2: single-agent,
Smaller3: with a known, observable environment

Name: Search
Definition: The process of Looking for a sequence of actions that reaches the goal.
Page: 066
Section: 1

Name: A solution
Definition: A sequence of actions returned by \(S\).
Page: 066
Section: 1
Variables: \(S\) a search algorithm
Context: AI

Name: An open loop system
Definition: An agent which ignores its percepts while executing the solution sequence.
Page: 066
Section: 1

Name: An action applicable in \(s\)
Definition: An action which can be used when the state is \(s\).
Page: 067
Chapter: 3
Section: 1.2
Context: AI

Name: A transition model
Definition: A description of what each action does.
Page: 067
Chapter: 3
Section: 1.2

Name: The succesor of \(s\)
Definition: The set of states accessible after a single action (generated or not) from \(s\).
Page: 067
Chapter: 3
Section: 1.2
Variables: \(P\) a problem
\(s\) a state.

Name: The object-level state space of \(P\)
Definition: The directed graph composed of possible state of \(P\), with an edge from \(s\) to \(t\) if \(t\) is a successor of \(s\).
Page: 067
Chapter: 3
Section: 1.2
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
Context: Artificial inteligence
Name2: The state space of \(P\)

Definition: \(s\) is the initial state of the problem.
Page: 067
Chapter: 3
Section: 1.2
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
\(s\) a state
Notation: \(In(s)\)

Definition: The set of actions applicable in \(s\).
Page: 067
Chapter: 3
Section: 1.2
Variables: \(s\) a state.
Notation: \(\texttt{Actions}(s)\)

Definition: The result from doing \(a\) in state \(s\).
Page: 067
Chapter: 3
Section: 1.2
Variables: \(s\) a state and \(a\) an action.
Notation: \(\texttt{Result}(s,a)\)

Name: A path in \(P\)
Definition: A sequence of states connected by a sequence of actions.
Page: 067
Chapter: 3
Section: 1.2
Variables: \(P\) a state space

Name: The goal test
Definition: Determining whether a given state is a goal state.
Page: 067
Chapter: 3
Section: 1.2

Name: A path cost
Definition: A function assigning a numeric cost to each path.
Page: 068
Chapter: 3
Section: 1.2

Name: The step cost
Definition: The function assigning the numeric cost in order to go from \(s\) to \(s'\) by doing \(a\).
Page: 068
Chapter: 3
Section: 1.2
Variables: \(s,s'\) states
\(a\) an action
Notation: \(c(s,a,s')\)

Name: Abstraction
Definition: The process of removing detail from a representation.
Page: 069
Chapter: 3
Section: 1.2

Name: A valid abstraction of \(P\)
Definition: An abstraction of \(P\) whose any solution can be expanded into a concrete solution.
Page: 069
Chapter: 3
Section: 1.2
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Name: A real word problem
Definition: A problem people actually care about.
Page: 069
Section: 1.2

Name: Search tree
Definition: The possible action sequences starting at the initial state.
Page: 075
Section: 3
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Name: A complete algorithm
Definition: An algorithm which always find a solution if there is one.
Page: 080
Chapter: 3
Section: 3.2
Variables: \(P\) a problem

Name: An algorithm which has the optimality property
Definition: An algorithm which always find an optimal solution, if there is one.
Page: 080
Chapter: 3
Section: 3.2
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Name: The space/time complexity of \(A\)
Definition: The amount of memory/time used to find a solution.
Page: 080
Chapter: 3
Section: 3.2
Variables: \(A\) an algorithm.

Name: Informed search algorithm
Definition: A search algorithm whose strategies contain information about the state apart from its goal status.
Page: 081
Name2: Heuristic search algorithm

Definition: The optimal value of \(C\).
Chapter: 3
Section: 4.2
Variables: \(C\) a cost.
Notation: \(C^*\)

Page: 088
Implementation: DFS with a bound on the depth of the search
Section: 4.4
Chapter: 3
Variables: \(l\) the bound, and
\(b\) a branching factor
Name: Depth limited search
Time complexity: \(O(b^l)\)
Typ: Not complete and not optimal.
Space complexity: \(O(bl)\)

Page: 088
Implementation: Depth-limited search, repeated with the limit increasing.
Section: 4.5
Chapter: 3
Variables: \(d\) the depth of a goal,
\(b\) a branching factor
Name: Iterative deepening depth-first seach
Time complexity: \(O(b^d)\)
Typ: complete and optimal
Space complexity: \(O(bd)\)

Page: 086
Implementation: searching through a graph going to the deepest nodes first.
Section: 4.3
Chapter: 3
Variables: \(m\) the depth of the search tree,
\(b\) the branching factor
Name: Depth-first seach
Time complexity: \(O(b^m)\)
Typ: not complete not optimal.
Space complexity: \(O(bm)\)

Page: 081
Implementation: States are expanded, level by level.
Section: 4.2
Chapter: 3
Name: Breadth-first seach
Time complexity: \(O(b^d)\)

Question: Is Breadth-first seach optimal ?
Answer: yes.
Page: 081
Chapter: 3
Section: 4.2

Question: Is Breadth-first seach complete ?
Answer: yes.
Page: 081
Chapter: 3
Section: 4.2

Page: 084
Implementation: states are expanded according to their distance, in a labelled graph.
Section: 4.2
Chapter: 3
Variables: For \(\epsilon\) the minimal step cost,
\(C^*\) the minimal length to a goal
\(b\) a branching factor
Name: Uniform-cost seach
Time complexity: \(O(b^{1+C^*/\epsilon})\)
Typ: complete and optimal.

Page: 090
Implementation: Searching from the initial state and from the goal(s) with one side at least in breadth-first search.
Section: 4.6
Chapter: 3
Variables: \(d\) the minimal length to a goal
\(b\) a branching factor
Name: Bidirectional seach
Time complexity: \(O(b^{d/2})\)
Typ: Complete and optimal

Name: An heuristic
Definition: A function associating to each state an approximation of the cost of the cheapest path from the state to a goal state.
Page: 092
Section: 3.5

Name: An informed search strategy
Definition: A strategy with an evaluation function \(f\) on states, where the node \(n\) with the lowest \(f(n)\) is expanded first.
Page: 092
Section: 3.5
Name2: An heuristic search strategy

Name: The greedy best-first search
Definition: Always expanding the node closest to the goal.
Page: 093
Chapter: 3
Section: 5.1
Property: not complete and not optimal.

Name: The \(A^*\) search
Definition: Always expanding the node \(n\) such that the cost to reach the node plus \(h(n)\) is minimal.
Page: 094
Chapter: 3
Section: 5.2
Typ: Optimally efficient

Name: An admissible heuristic
Definition: An heuristic which never overestimates the cost to reach the goal.
Page: 094
Chapter: 3
Section: 5.2
Example: number of misplaced tiles
Example2: Distance between each tiles and its final position.

Name: A consistent heuristic
Definition: An heuristic such that, for each nodes \(n,n'\) and each action \(a\), \(h(n)\le h(n')+c(n,a,n')\).
Page: 095
Chapter: 3
Section: 5.2
Example: The optimal cost of a relaxation of this problem.
Name2: A monotonic heuristic

Smaller0: \(h\) is consistent
Greater0: \(h\) is admissible
Page: 097
Chapter: 3
Section: 5.2
Variables: \(h\) an heuristic.

Smaller0: \(h\) is admissible
Greater0: tree search version
Page: 097
Chapter: 3
Section: 5.2
Variables: \(h\) an heuristic.
Hide middle: yes
Prefix Greater: the
Greater1: optimal
Connect Greater0: of \(A^*\) is

Smaller0: \(h\) is consistent
Greater0: graph search version of
Page: 097
Chapter: 3
Section: 5.2
Variables: \(h\) an heuristic.
Hide middle: yes
Prefix Greater: the
Greater1: optimal
Connect Greater0: \(A^*\) is

Name: Expanding \(s\)
Definition: Generating the set of successors of \(s\).
Page: 075
Chapter: 3
Variables: \(t\) a search tree and
\(s\) a node of \(t\).

Name: The children of \(s\)
Definition: The generated states accessible with a single action from \(s\).
Page: 075
Chapter: 3
Variables: \(t\) a search tree and \(s\) a node of \(t\).

Name: A leaf node
Definition: A node which does not have any child
Page: 075
Chapter: 3
Variables: \(t\) a search tree.
Example: A node which is not expanded

Name: The frontier of \(t\)
Definition: the set of leaves nodes which are not expanded.
Page: 075
Chapter: 3
Name2: Open list
Assuming: a search tree

Name: Tree search
Definition: takes as input a problem, return a solution or failure.
Initialize the frontier using the initial state of problem
loop:
if the frontier is empty, return failure
choose a leaf node and remove it from the frontier
if the node is a goal, then return the corresponding solution
expand the chosen node, adding the resulting nodes to the frontier
Page: 077
Chapter: 3
Index: 7
Kind: Fig

Name: Graph search
Definition: takes as input a problem, return a solution or failure.
Initialize the frontier using the initial state of problem
loop:
if the frontier is empty, return failure
choose a leaf node, remove it from the frontier and add it to the set of explored set
if the node is a goal, then return the corresponding solution
expand the chosen node.
for each successor, if it is not in the explored set, add it to the frontier
Page: 077
Chapter: 3
Index: 7
Kind: Fig

Name: A repeated state
Definition: A node \(n\) whose state appear in an ancestor of \(t\).
Page: 076
Chapter: 3
Variables: \(t\) a search tree
\(n\) a node in \(t\).

Name: Loopy path
Definition: The path from the first occurence of the state of \(n\) to \(n\).
Page: 076
Chapter: 3
Variables: \(t\) a search tree and \(n\) a node corresponding to a repeated state in \(t\).

Name: A redundant path
Definition: A path such that there is a more efficient path with same source and destination.
Page: 076
Chapter: 3
Variables: \(t\) a search tree and \(p\) a path in \(t\) from a state \(s\) to a state \(s'\).

Name: The explored set
Definition: set of expanded states.
Page: 077
Chapter: 3
Name2: closed list
Assuming: search graph

Page: 079
Name: A queue
Chapter: 3
Invariant: A data structure with contains a set of elements. The three operations: Empty?, Pop and Insert(element).

Page: 079
Name: A FIFO queue
Chapter: 3
French: File
Invariant: A queue which pop the oldest added element.

Function: IsEmpty
Page: 079
Name: A LIFO queue
Function2: Insertion
Chapter: 3
Function3: pop the earliest added element.
Subtype of: Set
French: Pile
Initialization: Empty

Function: pop efficiently element with highest priority
Page: 080
Name: A priority queue
Function2: isEmpty
Chapter: 3
Extends: Set
Section: 3.1
Subtype of: Set of elements with priorities

Name: A contour (AI)
Definition: A set of the form \(f^{-1}(c)\) for some real constant \(c\)
Page: 097, 449
Chapter: 3 AI introduction, 8 Zorich
Section: 5, 3.4
Variables: \(m\in\mathbb N\)
\(G\subseteq\mathbb R^m\)
\(f:G\to\mathbb R\)
Name2: A level set of \(f\) (analysis)

Question: The nodes expanded by A* are:
Answer: the nodes with \(f(n)<C^*\) and some nodes with \(f(n)=C^*\)
Page: 097
Chapter: 3
Section: 5
Variables: \(h\) an admissible heuristic.

Name: Optimally efficient search algorithm
Definition: A search algorithm such that no other algorithm is garanteed to expand fewer nodes.
Page: 098
Chapter: 3
Section: 5

Name: The absolute error
Definition: \(h^*-h\).
Page: 098
Chapter: 3
Section: 5
Variables: \(h\) a value to optimize
Notation: \(h^\Delta\)

Name: The relative error
Definition: \(\frac{h^*-h}{h^*}\).
Page: 098
Chapter: 3
Section: 5
Variables: \(h\) a value to optimize.
Notation: \(h^\epsilon\)

Name: Iterative deepening \(A^*\)
Definition: \(A^*\) with cut-off based on the \(f\)-value. At each iteration, the cut-off is increased to the next found \(f\)-value.
Page: 099
Chapter: 3
Section: 5

Name: Recursive best-first search
Definition: At each step, a branch is expanded, plus the successors of each node of the branch. To each node \(n\) is associated \(v(n)\) the least value \(f(n)\) found in the descendant of \(n\).
The frontier node \(n\) with \(v(n)\) minimal is expanded and all neighboors of \(n\) are pruned.
Page: 100
Chapter: 3
Section: 5.3

Name: Simple Memory-bounded A*
Definition: To each frontier node \(n\) is associated the best value \(v(n)\) of visited descendant of \(n\).
At each step, the newest frontier node \(f\) with \(v(n)\) minimal is extended. If there is no memory left, the oldest node \(n\) with \(f(n)\) maximal is pruned.
Page: 100
Chapter: 3
Section: 5.3

Name: The metalevel state space
Definition: The state space whose states are the internal (computational) state of a program.
Page: 102
Chapter: 3
Section: 5.4

Name: Vacuum world
Definition: States: the position of the vacuum and the set of dirty places
Inital state: any
Actions: Left, Right, Suck
Transition model: as expected.
Goal test: all states are clean
Path cost: 1 for each step
Page: 070
Chapter: 3
Section: 3.2

Name: 8-Puzzle
Definition: states: The position of the 8 tiles
Inital state: any state
Actions: Left, Right, Up, Down
Transition model: move the blank space as descirbed.
Goal test: Whether the 8 tiles are in the correct order
Path cost: 1 for each step
Page: 071
Chapter: 3
Section: 3.2

Name: \(n\)-queen problem
Definition: states: On a \(n\times n\)-board, for \(0\le m\le n\), arrangement of \(m\) queens on the \(m\)-leftmost columns.
Inital state: The empty board
Actions: an integer between 1 and \(n\)
Transition model: add the \((m+1)\)-th queen to column \(m+1\) and line \(n\).
Goal test: Whether there are \(n\) queens with no queen attacking another
Path cost: none
Page: 072
Chapter: 3
Section: 3.2
Variables: \(n\in\mathbb N\).

Question: Examples of Problem with infinite number of state
Answer: states: Integers
Inital state: 4
Actions: floor, square root, factorials
Transition model: apply the function to the number, factorial only if the number is an integer
Goal test: any fixed integer
Path cost: none.
Page: 073
Chapter: 3
Section: 3.2

Name: The effective branching factor
Definition: The least \(i\) such that \(\sum_{i=0}^d \left(b\right)^i=N+1\).
Page: 104
Chapter: 3
Section: 6
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
\(d\) the depth of \(P\)
\(N\) nodes generated by an \(A^*\)
Notation: \(b^*\)

Name: A relaxed problem
Definition: A problem with fewer restrictions on the actions.
Page: 105
Chapter: 3
Section: 6.2
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Q: [...] is [...].
A: The cost of the optimal solution in \(P'\); a consistent heuristic for \(P\)
Page: 105
Chapter: 3
Section: 6.2
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
\(P'\) a relaxation of \(P\).

Name: Admissible heuristic
Page: 106
Section: 6.2
Chapter: 3
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
Under: taking the maximum of admissible heuristic

Name: A subproblem of \(P\)
Definition: \(P\) with an augmented set of goal states
Page: 106
Chapter: 3
Section: 6.3
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Name: A pattern database
Definition: Storing the exact solution costs for every possible subproblem instance.
Page: 106
Chapter: 3
Section: 6.3
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
Typ: A consistent heuristic

Name: A disjoint pattern database
Definition: The union of pattern database when each action affect only the cost of one of the subproblems.
Page: 107
Chapter: 3
Section: 6.3
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost

Name: Local search
Definition: A search method which does not remember the path.
Page: 122
Chapter: 4
Section: 1
Extra: stochastique ?

Name: Optimization problem
Definition: A problem whose goal is to maximize an objective function
Page: 122
Chapter: 4
Section: 1

Name: A state-space landscape
Definition: Locations defined by the state and elevation defined by the heuristic or objective function.
Page: 122
Chapter: 4
Section: 1

Name: The global minimum
Definition: The state whose objective value is minimal.
Page: 122
Chapter: 4
Section: 1

Name: Hill climbing search (steepest-ascent version)
Definition: At each step, the action leading to the higest valued successor is chosen
Page: 123
Chapter: 4
Section: 1.1
Name2: Greedy local search

Q: [...].
A: A state that is lower than each of its neighboring state but higher than the global minimum
Page: 123
Chapter: 4
Section: 1.1
Name: A local minimum

Name: Ridge
Definition: A sequence of local maxima that are not directly connected to each other. All neighbors are downhill
Page: 124
Chapter: 4
Section: 1.1

Name: Plateau
Definition: A flat area of the state-space landscape
Page: 124
Chapter: 4
Section: 1.1

Name: Stochastic hill climbing
Definition: At each step, choose randomly an huphill move
Page: 125
Chapter: 4
Section: 1.1

Name: First-choice hill climbing
Definition: Generate move until it finds an uphill move. Select it
Page: 125
Chapter: 4
Section: 1.1

Page: 125
Implementation: Generate a random initial state
Section: 1.1
Chapter: 4
Name: Random-restart hill climbing
Implementation2: apply hill climbing
Implementation3: If the local maximum is not a goal state, goto 1

Name: Gradient descente
Definition: Minimizing cost
Page: 126
Chapter: 4
Section: 1.2

Page: 125
Implementation: Choose a random step. If it decreases, take it. If it increases, accept with probability exponentially decreasing with time and with the uphill
Section: 1.2
Chapter: 4
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
Name: Simulated annealing
Returns: The minimum state for \(P\)
Extra: no jump
French: Recuit simulé

Name: Stochastic beam search
Definition: Initialization: take \(k\) states randomly.
Loop: Expand all of the \(k\) states. If there is a goal chose it. Otherwise, select the successor randomly, with probability increasing with its value. End loop.
Page: 127
Chapter: 4
Section: 1.3

Name: The population
Definition: The set of considered states.
Page: 128
Chapter: 4
Section: 1.4
Context: genetic algorithm

Name: an individual
Definition: a state.
Page: 128
Chapter: 4
Section: 1.4
Context: In a genetic algorithm

Name: The fitness function
Definition: The objective function.
Page: 128
Chapter: 4
Section: 1.4
Context: Genetic algorithm

Name: The crossover
Definition: The place where a pair is cut, to mix them.
Page: 128
Chapter: 4
Section: 1.4
Variables: In a genetic algorithm
Context: Genetic algorithm

Name: A mutation
Definition: A change in an invidual.
Page: 128
Chapter: 4
Section: 1.4
Context: In a genetic algorithm

Name: A schema
Definition: A partial description of states.
Page: 128
Chapter: 4
Section: 1.4
Variables: In a genetic algorithm,

Q: In a genetic algorithm, [...] is [...]
A: an instance of \(s\); a state matching \(s\)
Page: 129
Chapter: 4
Section: 1.4
Variables: \(s\) a schema

Name: Genetic algorithm
Definition: Initial state:
-Selecting a state of initial population,
Loop:
-choosing some pairs where each elements occur with a probability increasing with its fitness function,
-Crossover
-Mutation
Page: 129
Chapter: 4
Section: 1.4

Name: Discretization
Definition: Transforming a continuous problem into a discrete one.
Page: 132
Chapter: 4
Section: 2
Example: Selecting a fixed distance and a fixed number of direction

Name: Line search
Definition: Doubling the size of the steps until the objective function decreases.
Page: 133
Chapter: 4
Section: 2
Context: AI problem
Assuming: In a continuous problem.

Name: Gradiant of \(f\)
Definition: The \(n\)-tuple [$]\left(\partialderivative{f}{x_1},\partialderivative{f}{y_1},\partialderivative{f}{x_2},\partialderivative{f}{y_2},\partialderivative{f}{x_3},\partialderivative{f}{y_3}\right)[/$].
Page: 131
Chapter: 4
Section: 2
Variables: \(f\) an objective function,
parametrized by variables \(x_1,\dots,x_n\).
Notation: \(\nabla f\)
Intuition: the magnitude and direction of the steepest slope

Smaller0: \((y_1,\dots,y_n)\) is a local maximum or minimum for \(f\)
Greater0: \(\nabla f(y_1,\dots,y_n)=0\)
Page: 132
Chapter: 4
Section: 2
Variables: \(f\) an objective function, parametrized by variables \(x_1,\dots,x_n\) and \(n\) values \((y_1,\dots,y_n)\).
Smaller to greater: iff

Name: Steepest ascent hill climbing
Definition: \(\vec x\leftarrow \vec x+\alpha\nabla f(\vec x)\) with \(\alpha\) a small constant.
Page: 133
Chapter: 4
Section: 2
Variables: \(f\) an objective function, parametrized by \(n\) variables \(\vec x\).

Name: The step size
Definition: The number \(\alpha\).
Page: 132
Chapter: 4
Section: 2
Variables: \(f\) an objective function, parametrized by variables \(\vec x\).
\(\alpha>0\).
\(\vec x\leftarrow \vec x+\alpha\nabla f(\vec x)\)

Name: Newton-Raphson method
Definition: Repeat \(x\leftarrow x-f(x)/f'(x)\) until approximation is good enough
Page: 133
Chapter: 4
Section: 2
Variables: \(f\) a function, parametrized by variables \(\vec x\) and \(n\) values \(\vec y\).
Intuition: approximate and find roots

Name: Constrained optimization
Definition: Optimization problem where the set of answer must satisfy some constraint
Page: 133
Chapter: 4
Section: 2

Name: Convex optimization
Definition: An optimization problem whose search space is a convex set and whose objective function is a convex function
Page: 134
Chapter: 4
Section: 2
Example: least-squares problem
Example2: Linear programming problem

Name: Contingency plan
Definition: What to do depending on what percepts are received
Page: 134
Chapter: 4
Section: 3
Name2: Strategy

Name: Erratic vacuum word
Definition: Similar to vacuum word, but the vacuum may clean the adjacent square our deposit dirt
Page: 135
Chapter: 4
Section: 3

Name: And-or search tree
Definition: A tree of states, where each node is labelled alternatively with «and» or «or». Actions labels the or nodes
Page: 136
Chapter: 4
Section: 3.2

Name: A solution to \(T\)
Definition: A subtree choosing a succesor of each or node and all succesors of the and nodes, where each leaf is a goal state.
Page: 136
Chapter: 4
Section: 3.2
Variables: \(T\) an and-or tree
Context: and-or tree.

Name: Slippery vacuum word
Definition: Vacuum word where movement sometime fails
Page: 138
Chapter: 4
Section: 3.2

Name: Belief-state
Definition: agent's current belief about the possible physical states it might be in.
Page: 139
Chapter: 4

Name: A sensorless problem
Definition: A problem such that the agent's percepts provide no information at all.
Page: 139
Chapter: 4
Section: 4.1
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
Name2: A conformant problem

Name: Coercing the world into \(s\)
Definition: A fixed sequence of actions such that the state is \(s\) after those actions whatever is the initial state.
Page: 139
Chapter: 4
Section: 4.1
Variables: \(P\) a problem with:
-Input
-Actions
-Transition model
-Goal test
-Path cost
\(s\) a state

Name: Prediction
Definition: Generating a belief state.
Page: 140
Chapter: 4
Section: 4.1
Variables: \(P\) a partially observable problem with a physical model.

Name: Incremental belief-state search
Definition: For each physical state \(s_1,\dots,s_p\) in the belief state, generate the solutions for \(s_1\), for each solution, checks whether it is a solution for the other states. Accept the first solution to each state.
Page: 142
Chapter: 4
Section: 4.1
Variables: \(P\) a partially observable problem with a physical model.

Name: Update
Definition: Restricting the belief set to states compatible with the observation.
Page: 143
Chapter: 4
Section: 4.1
Variables: \(P\) a partially observable problem with a physical model.

Name: Monitoring
Definition: Maintening one's belief state.
Page: 146
Chapter: 4
Name2: Filtering
Name3: State estimation

Name: Recursive state estimation
Definition: A state estimation which computes its new belief from the previous one.
Page: 146
Chapter: 4

Name: Localization problem
Definition: Figuring out where one is, given percepts and a map of the word
Page: 146
Chapter: 4

Name: Online search
Definition: A problem where computation must be done while the input data are received
Page: 148
Chapter: 4
Section: 5

Name: Competitive ratio
Definition: The ratio of the actual distance over the optimal distance assuming the state-space is known
Page: 148
Chapter: 4
Section: 5
Variables: \(P\) an online search problem

Name: Irreversible action
Definition: An action \(a\) such that \(s\) is not reachable after executing \(a\).
Page: 150
Chapter: 4
Section: 5
Variables: \(s\) a state

Name: A dead end
Definition: A state which admits no successor.
Page: 150
Chapter: 4
Section: 5
Variables: \(s\) a state.

Name: Safely explorable state space
Definition: A state space such that some state is accessible from each state.
Page: 150
Chapter: 4
Section: 5

Page: 151
Implementation: Selecting randomly an action, possibly prefering the one not yet tried.
Section: 5
Chapter: 4
Effect: Visiting states
Name: Random walk

Name: Game
Definition: An adversial search
Page: 163
Chapter: 5
Section: 1

Name: Perfect information game
Definition: Game deterministic, fully observable
Page: 163
Chapter: 5
Section: 1

Name: Zero sum game
Definition: A game in which the utility function of both agents are opposite
Page: 163
Chapter: 5
Section: 1

Name: Pruning
Definition: Ignoring portions of the search tree that make no difference to the final choice
Page: 163
Chapter: 5
Section: 1

Name: Ply
Definition: The move of a single player
Page: 163
Chapter: 5
Section: 1
Variables: \(G\) a game
Name2: Half move

Page: 166
Implementation: The function \(f\) from state to value, such that,
-\(f(s)=\text{Utility}(x)\) if \(x\) is terminal
-\(\max_{a\in Actions(s)}f(\text{Result}(s,a))\) if \(\text{Player}(s)=\text{Max}\)
-\(\min_{a\in Actions(s)}f(\text{Result}(s,a))\) if \(\text{Player}(s)=\text{Min}\)
Section: 1
Chapter: 5
Variables: \(G\) a game
Name: Minimax
Time complexity: \(O(b^d)\)
Typ: optimal against optimal opponent
Assuming: successors can be generated one at a time
Space complexity: \(O(d)\)

Page: 172
Implementation: Similar to minimax, but alpha and beta, the value of the best (highest/lowest-value) along the path to MAX/MIN is kept as parameter. In a Max move, alpha is updated with the maximum values of subtree. If the max is greatest than beta, it is immediatly returned (other branches are pruned)
Section: 3
Chapter: 5
Variables: \(G\) a game
Name: Alpha-Beta pruning

Question: «Alpha-beta's pruning» average complexity, assuming nodes are chosen in best-first, is
Answer: \(O(b^{m/2})\) time.
Page: 171
Chapter: 5
Section: 3.1
Variables: \(G\) a game with branching factor \(b\) and depth \(m\).

Question: «Alpha-beta's pruning» average complexity, considering successor in a random order, is
Answer: \(O(b^{3m/4})\) time.
Page: 171
Chapter: 5
Section: 3.1
Variables: \(G\) a game with branching factor \(b\) and depth \(m\).

Name: Killer move
Definition: Best move
Page: 172
Chapter: 5
Section: 3.1
Variables: \(G\) a game.

Name: Transposition table
Definition: Hashtable of previously seen position
Page: 173
Chapter: 5
Section: 3.1
Variables: \(G\) a game.

Name: Transposition
Definition: Two identical positions obtained by different sequences of moves
Page: 172
Chapter: 5
Section: 3.1
Variables: \(G\) a game.

Name: Cutoff-Test
Definition: A function which, given a state, and its depth, states whether the search should halts
Page: 173
Chapter: 5
Section: 4

Name: Evaluation function
Definition: A function which, given a state, returns an estimate of the expected utility of the game
Page: 173
Chapter: 5
Section: 4.1
Example: Partitionning the state-space into easy-to-compute components. Returning, for each components, its expected value.
Example2: Decomposing the state into distinct features. According a material value to each feature.

Name: A quiescent state
Definition: A state which is unlikely to exhibit wild swings in value in the near future.
Page: 176
Chapter: 5
Section: 4.2
Variables: \(G\) a game
\(p\) a position
Context: IA

Name: Quiescence search
Definition: A search which does not cutoff on non-quiescent state.
Page: 176
Chapter: 5
Section: 4.2
Variables: \(G\) a game

Name: Horizon effect
Definition: When the oponent have an unavoidable move creating serious dommage, which can be temporarily avoided by delaying tactics.
Page: 176
Chapter: 5
Section: 4.2
Variables: \(G\) a game

Name: Singular extension
Definition: A move that is clearly better.
Page: 176
Chapter: 5
Section: 4.2
Variables: \(G\) a game

Name: Forward pruning
Definition: Some moves at a given node are pruned immediately.
Page: 176
Chapter: 5
Section: 4.3
Variables: \(G\) a game

Name: Stochastic game
Definition: A game which contains a random element.
Page: 179
Chapter: 5

Name: Chance node
Definition: In a tree, a node where each leaving edge is assigned a probability
Page: 179
Chapter: 5
Variables: \(G\) a game

Name: Expectiminimax
Definition: Minimax, where the value of chance node is the expectation of the values of its successor
Page: 180
Chapter: 5
Variables: \(G\) a stochastic game

Question: The time complexity of the tree search is
Answer: \(O\left((bn)^m\right)\).
Page: 181
Chapter: 5
Variables: \(G\) a game, with \(b\) branching factor, \(m\) maximal depth and \(n\) the number of distinct rolls.

Name: Kriegspiel
Definition: Variant of chess where each player only know the position of its pieces, whether a king is in check, in which direction, and whether a piece is taken.
Page: 182
Chapter: 5
Section: 6

Name: Guaranteed checkmate
Definition: A strategy which wins whatever the oponent's choice are.
Page: 183
Chapter: 5
Section: 6
Variables: \(G\) a partially observable game

Smaller0: \(S\) is a garanteed checkmate
Greater0: \(S\) wins when the opponents see the player's side
Page: 183
Chapter: 5
Section: 6
Variables: \(G\) a partially observable game and \(S\) a strategy.
Smaller to greater: iff

Name: Probabilistic checkmate
Definition: A strategy which wins based on some probabilistic expectation about the opponents.
Page: 184
Chapter: 5
Section: 6
Variables: \(G\) a partially observable game.

Name: Accidental checkmate
Definition: A strategy which wins on only some of the positions of the belief state.
Page: 185
Chapter: 5
Section: 6
Variables: \(G\) a partially observable game

Question: The fundamental difference between the optimal strategy for the partially observable version and the fully observable version is:
Answer: the stategy should be random, otherwise it gives the opponents information. Hence, it must contains plays which are not optimal in the fully observable version.
Page: 185
Chapter: 5
Section: 6
Variables: \(G\) a partially observable game.

Name: Averaging over clairvoyance
Definition: Assume all randomness is choseen at start, apply minimax to all deterministic game where the random part is fixed, and average by the probability distribution.
Page: 186
Chapter: 5
Section: 6
Variables: \(G\) a partially observable stochastic game.

Name: Game where averaging over clairvoyance is not optimal
Page: 187
Chapter: 5
Section: 6
Example: Road A leads to gold, B to a fork. In game 1 (2, 3), (left, right, some) fork leads to more gold, the other to a bus

Name: Null move
Definition: Assuming that the opponents plays twice when the game start.
Page: 188
Chapter: 5
Section: 7
Variables: \(G\) a game

Question: Null move is
Answer: a lower bound on the value of a position.
Page: 188
Chapter: 5
Section: 7
Variables: \(G\) a game

Name: Metareasoning
Definition: Reasoning about what computation to do.
Page: 191
Chapter: 5
Section: 8
Context: AI

Q: \(D\) can be given:
-[...],
-[...].
A: As an explicit set; As a set of abstract relations
Page: 206
Chapter: 6
Section: 1
Variables: \((X,D,C)\) a CSP

Name: A state of this CSP
Definition: A partial assignment of the variables of some \(X_i\) into \(D_i\).
Page: 207
Chapter: 6
Section: 1
Variables: \((X,D,C)\) a CSP

Name: A consistent assignment
Definition: An assignment which does not violate any constraint.
Page: 207
Chapter: 6
Section: 1
Variables: \((X,D,C)\) a CSP and
\(P\) a partial assignment.

Name: A complete assigment
Definition: An assignment which assign a value to each variables.
Page: 207
Chapter: 6
Section: 1
Variables: \((X,D,C)\) a CSP and
\(P\) a partial assignment.

Name: A solution of \((X,D,C)\)
Definition: A complete consistent assignment of \((X,D,C)\).
Page: 207
Chapter: 6
Section: 1
Variables: \((X,D,C)\) a CSP

Name: The constraint graph of the CSP
Definition: The graph with the variables as nodes, and edge between two variables belonging to a constraint.
Page: 207
Chapter: 6
Section: 1.1
Variables: \((X,D,C)\) a CSP.

Name: A constraint
Definition: A pair \((X',Y)\) with \(X'\subseteq X\) and \(Y\subseteq\Pi_{i\in X'}D_i\).
Page: 206
Chapter: 6
Section: 1.1
Variables: \((X,D,C)\) a CSP.

Name: Map coloring
Definition: A problem of the form:
-\(X=\{X_1,\dots,X_n\}\)
-\(D_1=\dots=D_n\) finite,
-each \(C_k\) is of the form \(X_i\ne X_j\).
Page: 207
Chapter: 6
Section: 1.1

Name: Job shop scheduling
Definition: \(X\) a set of task taking time \(t_i\). \(D_1=\dots=D_n\) the possible start time, and \(C_i\) time constraint of the form \(X_i+t_i\le X_j\) when \(X_i\) must occur before \(X_j\).
Page: 208
Chapter: 6
Section: 1.2

Name: A linear constraint
Definition: Some inequality \(x+d\le y\), with \(x,y\) variables and \(d\) constant
Page: 209
Chapter: 6
Section: 1.3
Extra: Formally, they are affine inequality

Question: The complexity of checking whether there is a solution is
Answer: undecidable.
Page: 209
Chapter: 6
Section: 1.3
Variables: \((X,\mathbb Z,L)\) with \(L\) a list of equation.
Assuming: \(L\) is not linear

Name: Linear programming
Definition: A CSP where domains are real and constraints are linear.
Page: 210
Chapter: 6
Section: 1.3

Name: A unary constraint
Definition: A constraint which contains a only variable.
Page: 210
Chapter: 6
Section: 1.3
Variables: \((X,D,C)\) a CSP

Name: A binary constraint
Definition: A constraint which contains exactly two variables.
Page: 210
Chapter: 6
Section: 1.3
Variables: \((X,D,C)\) a CSP

Name: A global constraint
Definition: A constraint which contains an arbitrary number of variables.
Page: 210
Chapter: 6
Section: 1.3
Variables: \((X,D,C)\) a CSP

Name: Alldiff
Definition: All variables in the constraints are distinct.
Page: 210
Chapter: 6
Section: 1.3
Variables: \((X,D,C)\) a CSP

Name: Cryptarithmetic
Definition: -Variables: a set of letters, and \(\left(C_{10^i}\right)_{0\le i\le k}\)
-Domains: the digits
-Constraints: Alldiff(letters) and \(\left(L_{i,1}+L_{i+2}+C_{10^i}=L_{i,3}+C_{10^{i+1} }\right)_{0\le i<k}\), for letters \(L_{i,j}\) and \(C_{10^k}=L_{k,3}\).
Page: 210
Chapter: 6
Section: 1.3
Variables: \((X,D,C)\) a CSP

Name: Preference constraint
Definition: A constraint which is preferred but not mandatory.
Page: 211
Chapter: 6
Section: 1.3

Name: A constraint optimization problem
Definition: A CSP with preference constraints.
Page: 211
Chapter: 6
Section: 1.3

Name: Constraint propagation
Definition: Using the constraints to reduce the number of legal values for a variable.
Page: 212
Chapter: 6
Section: 2
Variables: \((X,D,C)\) a CSP

Name: Node consistent variable
Definition: A variable such that all values of its domain satisfy the variable's unary constraints.
Page: 208
Chapter: 6
Section: 2.1
Variables: \((X,D,C)\) a CSP
\(x\in X\)
Definition2: A 1-consistent variable

Name: Path consistent variable with respect to \(y\)
Definition: Two variables \(x,z\) such that for each of their possible values, there is a value for each, such that the assigments for \(x,y\) and for \(y,z\) holds.
Page: 208
Chapter: 6
Section: 2.3
Variables: \((X,D,C)\) a CSP
\(y\in X\)

Name: Arc consistent variables
Definition: A pair of variables such that value in its domain satisfies the variable’s binary constraints
Page: 208
Chapter: 6
Section: 2.2
Variables: \((X,D,C)\) a CSP
Definition2: A 1-consistent variable

Name: arc-consistent problem
Definition: Every variable \(x\in X\) of the problem is arc- consistent.
Page: 212
Chapter: 6
Section: 2.1
Definition2: A 2-consistent problem

Name: Node/path/\(k\)-consistent problem
Definition: Every variable \(x\in X\) of the problem is node/path/\(k\)- consistent.
Page: 212
Chapter: 6
Section: 2.1

Name: A variable which is (generalised) arc consistent
Definition: A variable which is (generalised) arc consistent with respect to every other variables.
Page: 212
Chapter: 6
Section: 2.2
Variables: \(P=(X,D,C)\) a (binary) CSP

Name: \(x_i,x_j\) is path consistent
Definition: For each \(x_k\in K\), \(v_i\in D_i\) and \(v_j\in D_j\), \(\left(C_{i,k}\times \{v_j\}\right)\cap \left(\{v_i\}\cap C_{k,j}\right)\) is not empty.
Page: 214
Chapter: 6
Section: 2.3
Variables: \(P=(X,D,C)\) a binary CSP, with \(c\) constraints,
\(x_i,x_j\in X\)

Name: A \(k\)-consistent binary CSP
Definition: A binary CSP \(P=(X,D,C)\) such that, for each \(k\) variables and a consistent assignation for the \(k-1\)th first variable, a consistent value can be assigned to the \(k\)-th variable.
Page: 215
Chapter: 6
Section: 2.4
Variables: \(P=(X,D,C)\) a binary CSP, \(k\in\mathbb N\)

Name: Strongly \(k\)-consistent CSP
Definition: A \(1-,\dots,k-\)consistent CSP.
Page: 215
Chapter: 6
Section: 2.4
Variables: \(k\in\mathbb N\)

Smaller0: \(|X|\)
Greater0: \(P\) is satisfiable
Page: 215
Chapter: 6
Section: 2.4
Variables: \(P=(X,D,C)\) a binary CSP.
Smaller to greater: iff
Prefix Smaller: \(P\) is
Suffix Smaller: -consistent

Name: Resource constraint
Definition: The sum of the interpretation of the \(n\) variables is at most \(m\).
Page: 216
Chapter: 6
Section: 2.5
Notation: \(atmost(m,P_1,\dots, P_n)\)

Name: Bound propagation
Definition: Computing the bound of the domains of solution using the bounds on the constraints.
Page: 216
Chapter: 6
Section: 2.5
Variables: \(P=(X,D,C)\) a CSP with \(D_i\subseteq \mathbb R\)

Name: Bound consistent poblem
Definition: For every variable \(X\), for both the lower-bound and upper-bound values of \(X\), there exists some value of \(Y\) that satisfies the constraint between \(X\) and \(Y\) for every variable \(Y\).
Page: 216
Chapter: 6
Section: 2.5
Variables: \(P=(X,D,C)\) a CSP with \(D_i\subseteq \mathbb R\)

Name: Sudoku
Definition: Variables: \(\{X_{i,j,k,l}\mid 1\le i,j,k\le 3\}\)
Page: 216
Chapter: 6
Section: 2.6
Definition2: Values: [1,9]
Conjdef: All of
Definition3: Constraints:\(\{Alldiff(\{X_{i,j,k,l}\mid 1\le i,j,k,l\le 3\})\mid\text{fix $i,j$, $i,k$ or $j,l$}\}\cup A\) where \(A\) is a set of constraint of the form \(X_{i,j,k,l}=m\).

Name: A commutative problem
Definition: A problem such that the order of applications of any given set of actions has no effect on the outcome.
Page: 218
Chapter: 6
Section: 3
Example: CSP

Name: Backtracking search
Definition: Depth first search that chooses values for one variable at a time and backtracks when a variable has no legal value left to assign.
Page: 219
Chapter: 6
Section: 3
Variables: \(P\) a CSP.

Name: Degree heuristic
Definition: Selecting the variable with greatest degree.
Page: 220
Chapter: 6
Section: 3.1
Variables: \(P\) a CSP with backtracking search

Name: Least constraining value heuristic
Definition: Selecting for the variable \(x\) the value which leaves as many possible value possible for the neighbors of \(x\).
Page: 221
Chapter: 6
Section: 3.1
Variables: \(P\) a CSP with backtracking search

Name: Forward checking
Definition: When a variable \(X\) is assigned, arc consistency is checked for \(X\)'s neighbors.
Page: 221
Chapter: 6
Section: 3.2
Variables: \(P\) a CSP with backtracking search

Name: Maintening arc consistency
Definition: When a variable \(X_i\) is assigned, AC-3 s called, with the \((X_j,X_i)\) in the inialization set. That is, check consistency only for neighbors of variables which have been changed.
Page: 222
Chapter: 6
Section: 3.2
Variables: \(P\) a CSP with backtracking search

Name: Chronological backtracking
Definition: Backtracking to the last chosen variable.
Page: 222
Chapter: 6
Section: 3.3
Variables: \(P\) a CSP with backtracking search

Name: The conflict set for \(x\)
Definition: A set of variables whose assignement is in conflict for \(x\) (and potentially the variable assigned after \(x\)).
Page: 223
Chapter: 6
Section: 3.3
Variables: \(P=(X,D,C)\) a CSP with backtracking search,
\(x\in X\) and
\(A\) a partial assignment containing \(x\).

Name: Backjumping
Definition: Backtracks to the most recent assignment in the conflict set of the last assigned variable.
Page: 223
Chapter: 6
Section: 3.3
Variables: \(P=(X,D,C)\) a CSP with backtracking search.

Name: Conflict-directed Backjumping
Definition: Backtracks to the most recent assignemnt in the (extended) conflict set of the last assigned variable.
Page: 224
Chapter: 6
Section: 3.3
Variables: \(P=(X,D,C)\) a CSP with backtracking search.

Name: Constraint learning
Definition: Finding a minimum set of variables from the conflict set that causes the problem.
Page: 220
Chapter: 6
Section: 3.3
Variables: \(P=(X,D,C)\) a CSP with backtracking search.

Name: No-good
Definition: A minimal set of variables causing a conflict, and their assignation.
Page: 224
Chapter: 6
Section: 3.3
Variables: \(P=(X,D,C)\) a CSP with backtracking search.

Name: Local search for \(P\)
Definition: Initial state: a random assignment,
Transition: changing the value of a variable.
Page: 224
Chapter: 6
Section: 4
Variables: \(P=(X,D,C)\) a CSP

Name: Min-conflicts
Definition: Local search where the chosen transition is: selects a random variable with conflicts and chose a position with minimal number of conflicts.
Page: 225
Chapter: 6
Section: 4
Variables: \(P=(X,D,C)\) a CSP

Name: Tabu search
Definition: Keeping a small list of recently visited state, forbidding to go back to them.
Page: 226
Chapter: 6
Section: 4

Name: Constraint weighting
Definition: Assigning a weight to each variable. Initially 1. At each turn, incrementing the weight of the variables in conflict. Choosing an action reducing the sum of the weight of the variables in conflict.
Page: 226
Chapter: 6
Section: 4
Variables: \(P=(X,D,C)\) a CSP

Question: Constraint weighting advantage is:
Answer: add topography to the search.
Page: 226
Chapter: 6
Section: 4
Variables: \(P=(X,D,C)\) a CSP
Answer2: Gives high weight to variable which are often in violation.

Name: Independant subproblem of \(P\)
Definition: A partition \(\mathcal C\) of the variables of \(P\) such that each constraint belong to a single class of \(\mathcal C\).
Page: 227
Chapter: 6
Section: 5
Variables: \(P=(X,D,C)\) a CSP

Name: Directed arc consistency
Definition: Assuming an order on the variables, \(X_i\) is arc consistent with \(X_j\) for each \(i<j\).
Page: 227
Chapter: 6
Section: 5
Variables: \(P=(X,D,C)\) a CSP

Page: 227
Implementation: -choose an order on variables
-transform the problem in a directed arc consistent graph
-for each \(X_i\) in increasing order, select a variable compatible with the preceding variables (it must exists it is directed arc consistent).
Section: 5
Chapter: 6
Effect: A solution of the CSP
Variables: \(P=(X,D,C)\) a CSP
\(n\) variables and \(d\) values
Time complexity: \(O(nd^2)\)
Assuming: the constraint graph is a tree

Name: A cycle cutset
Definition: A set \(S\) of nodes such that \(G_{\mid E\setminus S}\) is a forest.
Page: 225
Chapter: 6
Section: 5
Variables: \(G=(E,V)\) a graph

Name: Topological sort
Definition: An order of the node such \((x,y)\in G\) implies \(x<y\).
Page: 227
Chapter: 6
Section: 5
Variables: \(G\) a directed graph

Name: Connected component
Definition: A maximal set of nodes pairwise accessible from each other.
Page: 227
Chapter: 6
Section: 5
Variables: \(G\) a graph

Page: 227
Implementation: -Chosing a cutset \(S\),
-For each assignment of \(S\):
--Make \(X\setminus S\) arc-consistent
--apply TREE-CSP-Solver to \(X\setminus S\),
--Return an assignment of \(S\) and \(X\setminus S\) if one is found.
Section: 5
Chapter: 6
Variables: \(P=(X,D,C)\) a CSP
\(d\) possible values,
\(n\) variables and
a cutset of size \(c\)
Name: Cutset conditionning
Time complexity: \(O(d^c(n-c)d^2)\)

Name: A tree decomposition
Definition: \(\bigcup_{V'\in\mathcal V'}V'=V\)
Page: 225
Chapter: 6
Section: 5
Variables: \(G=(V,E)\) a graph
Definition2: for each \((x,y)\in E\), there exists \(V'\in\mathcal V'\) such that \(\{x,y\}\subseteq V'\)
Conjdef: A tree \(T=(\mathcal V',E')\) with \(\mathcal V'\subseteq\mathcal P(V)\) such that
Definition3: for each \(x\in V\), if \(x\in V'_1,V'_2\in\mathcal V'\) then \(x\) appears in each vertices of the path \(vTv'\).
Extra: Note that, in general, \(V'_i\) is not a partition

Name: Tree decomposition algoritm
Definition: -Create a tree \(T=(V,E)\) decomposition of the graph
-Solve each subproblem,
-Associate to each node \(v_i\) of the tree a variable whose domain is the set \(d_i\) of solution to this subproblem
-Solve the CSP stating that the neighbors are consistent in the assignation of them variables.
Page: 230
Chapter: 6
Section: 5
Variables: \(P=(X,D,C)\) a CSP

Name: The tree width of the decomposition \(T\)
Definition: The maximal cardinal of the nodes of \(T\), minus 1.
Page: 230
Chapter: 6
Section: 5
Variables: \(G=(V,E)\) a graph and
\(T\) a tree decomposition

Name: Tree width of \(G\)
Definition: The minimum tree-width of the tree decompositions of \(G\).
Page: 230
Chapter: 6
Section: 5
Variables: \(G=(V,E)\) a graph

Name: Value symmetry
Definition: The set of symmetry under which the set of solution of \(P\) is closed under.
Page: 230
Chapter: 6
Section: 5
Variables: \(P=(X,D,C)\) a CSP

Name: Symmetry breaking constraint
Definition: Reducing the number of possible value/fixing a value of some variables, in order to decrease the number of symmetry of the set of solution without removing existence of solutions.
Page: 230
Chapter: 6
Section: 5
Variables: \(P=(X,D,C)\) a CSP
Example: \(n\)-coloring is symmetric under permuting the color. Finding a clique, and assigning a color to each element of the clique.

Question: What is the interest of Toy problems ?
Answer: They admit concise exact description.
Page: 69
Chapter: 1
Section: 2

Page: 212
Implementation: -Variables: A set of sets \(D'_i\subseteq D_i\), initialized to \(D_i\)
-Keep a set with all arcs to be considered, initialized with all pair of variables
-For each arc \((X_i,X_j)\) in the set:
--This arc is removed from the set,
--\(D'_i\) becomes the projection of \(C_{i,j}\cap D'_i\otimes D'_j\) to \(D_i\). If \(D'_i\),
--If \(D'_i\) is empty, the algorithm returns false,
--If \(D'_i\) has changed, all arcs \((X_j,X_k)\) are added to the set.
Section: 2.2
Chapter: 6
Variables: \(P=(X,D,C)\) a binary CSP,
\(c\) constraints
and \(d\) values.
Name: AC3
Time complexity: \(O(cd^3)\)
Returns: Transform \(P\) into an arc-consistent CSP with the same solutions, with restricted domains for each variables.

Name: Constraint satisfaction problem
Definition: A set \(X=\{X_1,\dots,X_n\}\) of variables,
Page: 206
Chapter: 6
Section: 1
Definition2: A set \(D=\{D_1,\dots,D_n\}\) of domains
Conjdef: Simultaneously
Definition3: \(C=\{C_1,\dots,C_m\}\) a set of constraints.

Name: Monte-Carlo strategy
Definition: Assume all random choices are done before the game start.
Chooses \(N\) samples of the random, evaluate the value of each move according to those \(N\) samples and average.
Page: 186
Chapter: 5
Section: 6
Variables: \(G\) a partially observable stocastic game.

Name: The agent function
Definition: The function which maps any given percept sequence to an action.
Page: 035
Chapter: 2
Section: 1

Name: A toy problem
Definition: A problem intended to illustrate or exercise various problem-solving methods.
Page: 069
Section: 1.2

Name: Local Beam Search
Definition: Initialization: take \(k\) states randomly.
Page: 126
Chapter: 4
Section: 1.3
Definition2: Loop: Expand all of the \(k\) states. If there is a goal chose it. Otherwise, select the \(k\) best successors. End loop.
Conjdef: The algorithm
Intuition: simulated annealing with \(k\) states rather than 1
French: Recherche en faisceau

Name: A problem
Definition: the initial state.
Page: 066
Chapter: 3
Section: 1.1
Context: AI
Definition2: description of the possible actions
Conjdef: A tuple containing
Definition3: the transition model
Definition4: the goal test
Definition5: the path cost

Name: A learning agent
Definition: A critic
Page: 055
Chapter: 2
Section: 4.6
Definition2: a learning element
Conjdef: A tuple with
Definition3: a performance element
Definition4: problem generator

Name: blind search algorithm
Definition: A search algorithm whose strategies do not contain information about the state apart from its goal status
Page: 081

Name: A partial assigment
Definition: An assignment does not assign a value to each variables.
Page: 207
Chapter: 6
Section: 1
Variables: \((X,D,C)\) a CSP and \(P\) a partial assignment.

Name: Sensorless problem
Definition: Belief states: the set of subsets of states
Page: 140
Chapter: 4
Section: 4.1
Variables: \(P\) a partially observable problem with a physical model.
Definition2: Initial state: the set of possible initial state
Conjdef: All of
Definition3: Actions: the union of actions, if forbidden actions are acceptable, otherwise their intersections
Definition4: Transition: The union of the effect of the action on each states
Definition5: Goal test: a set whose all states are goals
DefType: A problem
Definition6: Path cost:Difficult

Name: An agent
Definition: architecture
Page: 046
Chapter: 2
Section: 4
Definition2: Program
Conjdef: A pair

Name: Minimum-remaining-values heuristic
Definition: Selecting the variable with smallest domain.
Page: 220
Chapter: 6
Section: 3.1
Variables: \(P\) a CSP with backtracking search
Abbreviation: MRV heuristic

Name: The parameters of \(n\) are
Definition: \(n\).State
Page: 079
Chapter: 3
Variables: \(t\) a search graph
\(n\) a node of \(t\).
Definition2: \(n\).Parent
Definition3: \(n\).action: action applied to the parent to generate \(n\)
Definition4: \(n\).Path-Cost: the cost from the initial state to \(n\).

Page: 153
Implementation: Keeping in memory all visited states and their estimation (initialized to the heuristic function). Moving to the neighboor with least estimation. When a state \(s\) is left, its estimation is updated, as maximal of (cost action+estimation of result\((s,a)\)) for each action \(a\) applicable at \(s\).
Section: 3
Chapter: 2
Name: Learning Real-Time A*
Time complexity: \(O(n^2)\)
Typ: complete for finite space, safely explorable
Abbreviation: LRTA*

Smaller0: \(G\) is finite
Greater0: random walk on \(G\) is complete
Page: 151
Chapter: 4
Section: 1
Variables: \(G\) a graph
Smaller1: \(G\) is of dimension 1 or 2
Connect Smaller0: or

Name: Empirical gradiant
Definition: Evaluating the response to small increments and decrements in each coordinate.
Page: 132
Chapter: 4
Section: 2
Variables: \(f\) an objective function, parametrized by variables \(x_1,\dots,x_n\).

Name: Knowledge representation language
Definition: The language in which are expressed the sentences
Page: 235
Chapter: 7
Section: 1
Context: Knowledge based agent

Question: A minimal cycle cutset of
Answer: \(\{SA\}\)
Page: 224
Chapter: 6
Section: 5

Question: A tree decomposition of
Page: 226
Chapter: 6
Section: 5