lv. 3 - CS37 Flashcards
An entity that perceives its environment and acts upon that environment.
Agent
A configuration of an agent in its environment.
State
The state from which the search algorithm starts.
Initial State
Choices that can be made in a state.
Actions
A description of what state results from performing any applicable action in any state.
Transition Model
The set of all states reachable from the initial state by any sequence of actions.
State Space
The condition that determines whether a given state is a goal state.
Goal Test
A numerical cost associated with a given path.
Path Cost
A sequence of actions that leads from the initial state to the goal state.
Solution
A solution that has the lowest path cost among all solutions.
Optimal Solution
contains the following data:
* A state
* Its parent node, through which the current node was generated
* The action that was applied to the state of the parent to get to the current node
* The path cost from the initial state to this node
node
the mechanism that “manages” the nodes
frontier
search algorithm that exhausts each one direction before trying another direction
Depth-First Search
search algorithm where the frontier is managed as a stack data structure
Depth-First Search
search algorithm that will follow multiple directions at the same time, taking one step in each possible direction before taking the second step in each direction.
Breadth-First Search
search algorithm where the frontier is managed as a queue data structure
Breadth-First Search
A type of algorithm that considers additional knowledge to try to improve its performance
Informed Search Algorithm
search algorithm that expands the node that is the closest to the goal, as determined by a heuristic function h(n).
Greedy Best-First Search
ignores walls and counts how many steps up, down, or to the sides it would take to get from one location to the goal location
Manhattan Distance
function that estimates how close to the goal the next node is, but it can be mistaken.
heuristic function
The efficiency of the greedy best-first algorithm depends on
how good a heuristic function is
considers not only h(n), the estimated cost from the current location to the goal, but also g(n), the cost that was accrued until the current location.
A* Search
For a* search to be optimal, the heuristic function has to be:
Admissible & Consistent
In the heuristic function h(n) of an A* search algorithm, it is consistent if
for every node n and successor node n’ with step cost c, n ≤ n’ + c
In the heuristic function h(n) of an A* search algorithm, what does it mean to be admissible?
Never overestimates the actual cost to reach a goal from any node
algorithm that faces an opponent that tries to achieve the opposite goal.
Adversarial Search
represents winning conditions as (-1) for one side and (+1) for the other side.
Minimax
Recursively, the algorithm simulates all possible games that can take place beginning at the current state and until a terminal state is reached. Each terminal state is valued as either (-1), 0, or (+1).
Minimax
an optimization technique for minimax that skips some of the recursive computations that are decidedly unfavorable
Alpha-Beta Pruning
Minimax that considers only a pre-defined number of moves before it stops, without ever getting to a terminal state.
Depth-Limited Minimax
estimates the expected utility of the game from a given state, or, in other words, assigns values to states.
Evaluation function
agents that reason by operating on internal representations of knowledge.
Knowledge-Based Agents
an assertion about the world in a knowledge representation language
Sentence
based on propositions, statements about the world that can be either true or false
Propositional Logic
letters that are used to represent a proposition.
Propositional Symbols
logical symbols that connect propositional symbols in order to reason in a more complex way about the world.
Logical Connectives
List all logical connectives:
Not (¬)
And (∧)
Or (∨)
Implication (→)
Biconditional (↔)
inverses the truth value of the proposition.
Not
connects two different propositions
And
is true as as long as either of its arguments is true.
Or
represents a structure of “if P then Q.”
Implication
In the case of P implies Q (P → Q), P is the ____
Antecedent
In the case of P implies Q (P → Q), Q is the ____
Consequent
an implication that goes both directions
Biconditional
an assignment of a truth value to every proposition.
Model
set of sentences known by a knowledge-based agent.
Knowledge Base (KB)
a relation that means that if all the information in α is true, then all the information in β is true.
Entailment (⊨)
the process of deriving new sentences from old ones.
Inference
Define the Model Checking algorithm
Model Checking algorithm.
the process of figuring out how to represent propositions and logic in AI
Knowledge Engineering