|
Size: 64280
Comment:
|
← Revision 10 as of 2020-01-26 20:54:40 ⇥
Size: 109
Comment:
|
| Deletions are marked like this. | Additions are marked like this. |
| Line 1: | Line 1: |
| These are all the glosary terms from my AI class ["Csce876"] | From the Tex File: [[attachment:AIGlossary.tex]] |
| Line 3: | Line 3: |
| {{{#!latex \usepackage{amsmath}% \setcounter{MaxMatrixCols}{30}% \usepackage{amsfonts}% \usepackage{amssymb}% \usepackage{graphicx} \usepackage{geometry} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in} %%end-prologue%% \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline $A^*$ Search & The most widely-known form of the best-first search, $A^*$ evaluates nodes using the evaluation function: \[ f(n) = g(n) + h(n) \] $A^*$ has several nice properties. Using the Tree-Search Algorithm and an {\em admissible} heuristic function we have: \begin{itemize} \item Optimality \item Complete \item Optimally efficient \end{itemize} If the heuristic function is consistent, then we have: \begin{itemize} \item Optimality \item Complete \end{itemize} \\ \hline $C^*$ & This is the actual cost of the optimal solution path. \\ \hline $f(n)$ (Evaluation Function) & The evaluation function is "the" problem-specific knowledge beyond the definition of the problem itself that is used to determine which node is chosen for expansion in the search process. \\ \hline $g(n)$ (Cost to node function) & This function gives the actual cost to reach node $n$ on the current path. \\ \hline $h(n)$ (Heuristic function) & The estimated cost of the cheape4st path from $n$ to a (the) goal. \\ \hline $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 $k^{th}$ variable. CITATION(aitextbook) (p 147) \\ \hline $n$-queens problem & The the goal of the $n-queens$ problem is to place $n$ queens on an $n \times n$ chess board where no queen is in a position to attack another queen. \\ \hline Abstraction (definition, goal, example) & The process of removing detail from a representation is called abstraction. We say the abstraction is valid if we can expand any abstract solution into a solution in the more detailed world. \\ \hline Admissible Heuristic & $h(n)$ is an admissible heuristic provided that $h(n)$ never overestimates the cost to reach the goal. The direct consequence of this is that $f(n)$ for $A^*$ never overestimates the true cost of a solution through $n$. \\ \hline Agent & An agent is just something that acts CITATION(aitextbook) \\ \hline Alldiff constraint & A constraint that indicate that all involved variables must be assigned a different value. CITATION(aitextbook) (p 140) \\ \hline Alliances & Alliances occur in many games involving more than two players. Alliances involve a group of players that are cooperating in a competitive environment. CITATION(aitextbook) (p 166) \\ \hline Alpha-beta pruning & This procedure is based on a DFS. Consider a node $n$ somewhere in the tree such that Player has a choice of moving to that node. If Player has a better choice $m$ either at the parent node of $n$ or at any choice point further up, then $n$ {\em will never be reached in actual play}. So once we have found out enough about $n$ (by examining its descendants in a DFS) to reach this conclusion, we can prune it. Alpha-beta pruning gets its name from the two parameters: \begin{description} \item[$\alpha =$] The value of the best choice we have found so far at any choice point along the path for $\max$. \item[$\beta =$] The value of the best choice we have found so far at any choice point along the path for $\min$. \end{description} CITATION(aitextbook) (p~168-169) \\ \hline And-elimination & $\frac{A \wedge B}{A}$ CITATION(aitextbook) (p 211) \\ \hline Anytime algorithm & An anytime algorithm is an algorithm whose output quality improves gradually over time, so that it has a reasonable decision ready whenever it is interrupted. CITATION(aitextbook) (p 971). \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Arc consistency & An arc from $X$ to $Y$ is consistent if, for every value $x$ of $X$ there is some value $y$ of $Y$ that is consistent with $x$. CITATION(aitextbook) (p 145) \\ \hline Arity (of a relation or a function) & Arity is the number of arguments CITATION(aitextbook) (p 246) \\ \hline Assertion & A FOL logic sentence added to the KB are called an assertion. CITATION(aitextbook) (p 253) \\ \hline Atmost constraint & The atmost constraint has a number $P$ and variables $P_1,...,P_k$ that are assigned numbers such that $\sum_{i=1}^{k} P_i \leq P$. CITATION(aitextbook) (p 148) \\ \hline Atomic sentences & Consists of a single proposition symbol. CITATION(aitextbook) (p 204) \\ \hline Autonomy (autonomous agent) & Not relying on prior knowledge of its designer, but rather on its own precepts. CITATION(aitextbook) \\ \hline Axiom & Axioms provide the basic factual information form which conclusions can be derived. CITATION(aitextbook) (p 255) \\ \hline Background knowledge & This is the sentences of information that a knowledge base is initialized with. CITATION(aitextbook) (p 196) \\ \hline Backjumping & The backjumping method backtracks to the most recent variable in the conflict set. CITATION(aitextbook) (p 149) \\ \hline Backtracking Search & A variant of the depth-first search it uses still less memory. In backtracking, only on successor is generated at a time rather than all successors; each partially expanded node remembers which successor to generate next. Thus the memory requirement is only $O(m)$ instead of $O(bm)$. \\ \hline Backtracking search & The backtracking search is a depth-first search that chooses values for one variable at a time and backtracks when a variable has no legal values left to assign. CITATION(aitextbook) (p 141) \\ \hline Backward chaining & Backward chaining starts with the query for the fact $q$ and finds those implications in the knowledge base that conclude $q$. If all of the premises of one of these implications can be proved true (through backward chaining), then $q$ is true. CITATION(aitextbook) (p 220) \\ \hline Belief State & When in a sensorless problem, the agent may only know what states it can possibly start in. By applying the successor function to each of these states it can determine a set of states that could be reached by a specific action. The set of states that the agent could be in at any one time is the {\em belief state}. \\ \hline Best-first Search & Best-first search is an instance of the general Tree-Search or Graph-Search algorithm in which a node is selected for expansion based on an evaluation function, $f(n)$. \\ \hline Biconditional & $A \Leftrightarrow B$ is a biconditional that states that $A$ is true if and only if $B$ is true or alternately if $A \Rightarrow B$ and $B \Rightarrow A$. CITATION(aitextbook) (p 205) \\ \hline Bidirectional search & The strategy is to run two simultaneous searches, one from the initial state forward and one from the goal state backwards. This is not always possible, and requires that the successor function be invertible. This should cut the search depth by a factor of two so that the storage requirements are $O(b^{d/2}) << b^d$. \\ \hline Binary constraint & A binary constraint relates two variables. CITATION(aitextbook) (p 140) \\ \hline Binding list & When posing a query $\exists x~Predicate(x)$, answering yes is not very helpful. The standard form of an answer to such a query includes a set of values that satisfy the query. This set is called a substitution or binding list. CITATION(aitextbook) (p 254) \\ \hline Blind Search & See Uninformed search \\ \hline Body (of a Horn clause) & The negative literals of a horn clause form the body. CITATION(aitextbook) (p 218) \\ \hline Boolean CSPs & Boolean CSPs are CSPs where the domains of the variables are either true or false. CITATION(aitextbook) (p 139) \\ \hline Bounded differences (constraint of) & A bounded difference constraint has the form of $const_1 ~~ \theta ~~ x-y ~~ \theta ~~ const_2$ where $\theta \in {<,>,\leq,\geq}$. CITATION(ainotes) \\ \hline Bounds Propagation & We say that a CSP is bounds-consistent if for every variable $X$, and 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$. This kind of constraint propagation is called {\em bounds propagation}. CITATION(aitextbook) (p 148) \\ \hline Branching Factor & The {\em branching factor} is the maximum number of successors of any node. \\ \hline Breadth-first Search & The BFS expands nodes from a FIFO queue. That is, as each node is discovered it is put into a FIFO queue. This results in all nodes being expanded at each level before a new level is expanded. The storage requirement is $O(b^{d+1})$. This requirement is prohibitive. \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Chinese room experiment & The system consists of a human, who understands only English (CPU), equipped with a rule book (PROGRAM), written in English, and various stacks of paper, some blank, some with indecipherable inscriptions (memory). The system is inside a room with a small opening to the outside. Through the opening appear slips of paper with indecipherable symbols. The human finds matching symbols in the rule book, and follows the instructions. The instructions may include writing symbols on new slips of paper, finding symbols in the stacks, rearranging the stacks and so on. Eventually, the instructions will cause one or more symbols to be transcribed onto a piece of paper that is passed back to the outside world with the correct response. Searle argues against the Turing test in that just running the right program does not generate understanding. CITATION(aitextbook) \\ \hline Chronological backtracking & The process of a backtrack search where we backup to the preceding variable and try a different value is called chronological backtracking, because the most recent decision point is revisited. CITATION(aitextbook) (p 148) \\ \hline Coercion & Coercion is the ability of an agent to reach a goal state even in a sensorless problem. The agent knows that it starts in any of the states but can reach a goal by reasoning about sets of states. See the Vacuum cleaner agent on p84 for a good example. \\ \hline Cognitive science & The interdisciplinary field of cognitive science brings together computer models from AI and experimental techniques from psychology to try to construct precise and testable theories of the workings of the human mind. CITATION(aitextbook) \\ \hline Competitive Agent & In a multiagent system, when one's performance depends upon the performance of another in an inverse relationship, then the two agents are in competition and may be called competitive agents. \\ \hline Complementary literals & Literals such that one is a negation of the other. CITATION(aitextbook) (p 214) \\ \hline Complete-state formulation & A {\em complete-state formulation} starts with a complete proposed solution and then changes to it to find a solution that satisfies the goal test. \\ \hline Completeness & If the exists a solution, then the algorithm is guaranteed to find a solution. \\ \hline Completeness (of inference) & An inference $i$ is complete if whenever KB $\models \alpha$, it is also true that KB $\vdash_i \alpha$. That is, the procedure will answer any question whose answer follows from what is know by the KB. CITATION(ainotes) (10.23) \\ \hline Compositional (languages) & In a compositional language, the meaning of a sentence is a function of the meaning of its parts. CITATION(aitextbook) (p 241) \\ \hline Compositionality & In a compostional language, the meaning of a sentence is a function of the meaning of its parts. CITATION(aitextbook) (p 241) \\ \hline Condition-action rule & A condition action rule is a tuple (Condition, Action). When the condition is matched by the sensor input, the Simple Reflex agent will perform the "Action". \\ \hline Conflict set & A more intelligent approach to backtracking than chronological backtracking is to go all the way back to one of the set of variables that {\em caused the failure}. This set is called the {\bf conflict set}. CITATION(aitextbook) (p 148) \\ \hline Conflict-directed backjumping & The backtracking method that backs up to the source of a conflict that prohibits the finding of a consistent assignment to the remaining variables. CITATION(ainotes,aitextbook) (p 149) \\ \hline Conjunctive normal form & A sentence expressed as a conjunction of disjunctions of literals is said to be in conjunctive normal form. CITATION(aitextbook) (p 215) \\ \hline Connectionism & Connectionism models mental or behavioral phenomena as the emergent processes of interconnected networks of simple units. There are many different forms of connectionism, but the most common forms utilize neural network models. CITATION(Wikipedia:Connectionism) \\ \hline Consistency (as a property of the $h$ function) & A heuristic $h(n)$ is consistent if, for every node $n$ and every successor $n'$ of $n$ generated by any action $a$, the estimated cost of reaching the goal from $n$ is no greater than the step cost of getting to $n'$ plust the estimated cost or reaching the goal from $n'$: \\ \hline Consistent assignment & An assignment that does not violate any constraints is called a consistent or legal assignment. CITATION(aitextbook) (p 137) \\ \hline Constant symbol & A symbol in FOL that stand for objects. CITATION(aitextbook) (p 246) \\ \hline Constraint graph & A graph where nodes correspond to the variables of the problem and arcs correspond to the constraints. CITATION(aitextbook) (p 138) \\ \hline Constraint hypergraph & A constraint hypergraph contains two types of nodes: variables and constraints. arcs from constraint nodes to variable nodes indicate that the variable is involved in the constraint. This is used for representing constraints with an arity greater than 2. CITATION(ainotes) \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Constraint propagation & This is the general term for propagation the implications of a constraint on one variable onto other variables. CITATION(aitextbook) (p 145) \\ \hline Constraint scope & The scope of a constraint is the set of variables that are involved in the constraint CITATION(ainotes). \\ \hline Constructive Search & This is the standard search process were we assign a value to a variable at each node starting from the first variable to the last. CITATION(ainotes). \\ \hline Contingency problem & If the environment is partially observable or if actions are uncertain, then the agent's percepts provide new information after each action. Each possible percept defines a {\em contingency} that must be planned for. A contingency problem is {\em adversarial} if the uncertainty is caused by the actions of other agents. \\ \hline Continuous domains & Where the variables require continuous values such as the real numbers we say we are using continuous domains. Problems that require precise values often require continuous domains. CITATION(aitextbook) (p 139) \\ \hline Contours & The fact that $f$-costs are nondecreasing along any path also means that we can draw contours in the state space, just like the contours in a topographic map. \\ \hline Crossover & In genetic algorithms when you cross two states you choose a point to split the states and "cross" the two states. State 1's first half with state 2's second half, and similarly for the second state. The split point is called the "crossover" point. \\ \hline Current State & Local search algorithms operate using a single "current state" and generally move only to neighboring states. The current state is then a complete description of a solution that may not meet all of the constraints or may not be optimal. (Of course it could be optimal too, but then it would be a solution) \\ \hline Cutset conditioning & Cutset conditioning is the process of finding the smallest cycle cutset. CITATION(aitextbook) (p 154) \\ \hline Cycle cutset & A subset $S$ called the cycle cutset is a set of variables of a CSP such that the constraint graph becomes a tree after the removal of $S$ CITATION(aitextbook) (p 153). \\ \hline Data driven & Data driven reasoning is reasoning in which the focus of attention starts with the known data. CITATION(aitextbook) (p 219) \\ \hline Data Mining & Data mining, also known as knowledge-discovery in databases (KDD), is the practice of automatically searching large stores of data for patterns. CITATION(Wikipedia:Datamining) \\ \hline Decision problem & Is any problem that must be answered yes or no. \\ \hline Deduction & Logical inference. That is to use the rules of logic to infer a conclusion. We say a conclusion is reached by deduction if it is logically inferred by the premise(s). \\ \hline Deduction theorem & For any sentences $\alpha$ and $\beta$, $\alpha \models \beta$ if and only if the sentence $(\alpha \Rightarrow \beta)$ is valid. CITATION(aitextbook) (p 210) \\ \hline Definite clause & Horn clauses with exactly one positive literal are called definite clauses. CITATION(aitextbook) (p 218) \\ \hline Degree (ordering heuristic) & Attempts to reduce the branching factor by selecting the variable that is involved in the largest number of constraints. CITATION(aitextbook) (p~144) \\ \hline Depth-First Search & This strategy expands nodes from a LIFO queue, also known as a stack. This results in nodes being expanded as deep as they can before exploring other nodes at the same level. Thus it is called the DFS. The space requirements for DFS are $O(bm)$. There is no guarantee that this will ever find a goal state because it may get caught in a loop. \\ \hline Depth-Limited Search & This is just a DFS search where we limit the depth that the search may descend to. It is also not guaranteed to find a solution in general, but we may guarantee a goal state is found if we know a goal exists within a certain depth. This has the same requirements as DFS \\ \hline Diameter (of a graph) & Given a graph $G=(V,E)$, the distance between two vertices $u$ and $v$ in $G$, denoted $d(u,v)$, is the length of the shortest $u-v$ path in $G$. The {\em diameter} of $G$, denoted diam$(G)$, is the maximum distance between any two vertices in $G$. CITATION(GraphTheoryThulasiramanSwamy) \\ \hline Domain (of a model) & The domain of a model is the set of objects that it contains. CITATION(ainotes) (p 245) \\ \hline Domain (of a variable) & Given a CSP the domain of a variable are the values that the variable may be assigned CITATION(ainotes,aitextbook) (p 137) \\ \hline Domain/degree heuristics (not in textbook) & The degree heuristic chooses the variable to assign that is involved in the largest number of constraints on other unassigned variables. CITATION(aitextbook) (p 144 - it is in the book) \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Domination (of two functions) & We say a heuristic function $h_1(n)$ dominates another heuristic function $h_2(n)$ if \[ h_1(n) \geq h_2(n) \] \\ \hline Effective branching factor CITATION(ainotes) & One way to characterize the quality of a heuristic is using the {\em effective branching factor}. In words this is the the branching factor that a uniform tree of depth $d$ would have in order to contain $N+1$ nodes. Where $d$ is the depth of the search tree and $N$ is the number of nodes generated. That is at each depth starting at $0$ we have: \[ N = 1 + b^* + (b^*)^2 + ... + (b^*)^d = \frac{(b^*)^{d+1}-1}{b^* - 1} \] \\ \hline Entailment & Let KB be a knowledge base of sentences and let $\alpha$ be a sentence. $\alpha$ is entailed by a KB if the models of the KB are {\em all} models of $\alpha$. CITATION(ainotes) (11.5) For my own notes: Entailment is similar to implication except the domain of the variables are sentences (or propositions). KB $\models \alpha$ iff all models of KB are models of $\alpha$. ($i.e., M(KB) \subseteq M(\alpha)$) CITATION(ainotes) (11.5) \\ \hline Environment: Deterministic vs. Stochastic & If the next state of the environment is completely determined by the current state and the action executed by the agent, then we say the environment is deterministic, otherwise we say it is stochastic. \\ \hline Environment: Discrete vs. Continuous & The discrete/continuous distinction can be applied (1) to the state of the environment - is it constantly changing?, (2) to the way {\em time} is handled - is it continuous in the application or is it handled as discrete points?, and (3) to the {\em percepts} and {\em actions} of the agent - How can the agent perceive the environment, and how does it act (continuously or discretely)?. \\ \hline Environment: Episodic vs. Sequential & If the agents experience is broken up into atomic episodes that do not affect actions in previous episodes, we call it episodic. If on the other hand current actions depend upon the sequence of actions taken previously, then we call the task environment sequential. \\ \hline Environment: Observable: Fully vs Partially & A task environment is effectively fully observable if the sensors detect all aspects that are {\em relevant} to the choice of action. Otherwise we say the task environment is partially observable. \\ \hline Environment: Single agent vs. Multiagent & The key distinction is whether an agent's behavior is best described as maximizing a performance measure whose value depends on other agents' behavior. \\ \hline Environment: Static vs. Dynamic & If the environment can change while the agent is deliberating, we say the environment is \textbf{dynamic}. If the environment does not change while the agent is deliberating, we call the environment \textbf{static}. If the score changes (decreases) as the agent deliberates in a static environment, we call the environment \textbf{semidynamic}. \\ \hline Environment: Strategic & If the environment is deterministic except for the actions of other agents, we say that the environment is strategic. (This was under Deterministic vs Stochastic in the book.) \\ \hline Epistemological level & Abstract description of what the agent knows about the world. CITATION(ainotes) (10.4) \\ \hline Exploration Problem & When the states and actions of the environment are unknown (e.g. you are dropped somewhere where you don't speak the language) the agent must act to discover them. This type of problem can be viewed as an extreme case of the contingency problem. \\ \hline Extended interpretation & An extended interpretation specifies a domain element in addition to the mapping given by the interpretation. CITATION(aitextbook) (p 249). \\ \hline Extensively defined constraint (not in textbook) & Extensionally defined constraints: all allowed tuples are listed. This is practical for defining arbitrary constraints. CITATION(ainotes) \\ \hline Factoring & Factoring is the last step in resolution and involves removing multiple copies of literals from the expression. CITATION(aitextbook) (p 214) \\ \hline Finite domains & Variables with finite (or discrete) domains are the simplest kind of CSPs. CITATION(aitextbook) (p 139) \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline First-Order Logic & First-Order logic adds to propositional \begin{itemize} \item symbols: Objects, properties, functions and relations \item connectives: quantifiers $\exists$ and $\forall$ \end{itemize} CITATION(ainotes) (12.4,5) \\ \hline Fitness function & In genetic algorithms each state produced in the next generation is evaluated or rated using a fitness function. This determines how "good" the produced state is. \\ \hline Fixed point & The point at which applying inference rules produces no new facts. CITATION(aitextbook) (p 218) \\ \hline Forward chaining & If all the premises of an implication are known, then its conclusion is added to the list of known facts. The process continues until the desired fact is known. This process of chaining horn clauses together is called forward chaining. CITATION(aitextbook) (p 218) \\ \hline Forward Checking & Whenever a variable $X$ is assigned, the forward checking process looks at each unassigned variable $Y$ that is connected to $X$ by a constraint and deletes from $Y$'s domain any value that is inconsistent with the value chosen for $X$. CITATION(aitextbook) (p 144) \\ \hline Fringe & The collection of nodes that have been generated but not yet expanded is called the fringe (p 70). \\ \hline Function & In terms of FOL, a function is a relation in which there is only one "value" for a given "input." CITATION(aitextbook) (p 242) \\ \hline Function (mathematical definition) & A relation $f:A \rightarrow B$ is said to be a function if and only if $f$ maps each $a \in A$ to only one value in $B$. (Dr. Anderson) \\ \hline Genetic algorithm & A genetic algorithm is a variant of stochastic beam search in which successor states are generated by combining two parent states. \\ \hline Global constraint & Involves all the variables in a CSP. CITATION(ainotes) \\ \hline Global optimum (maximum or minimum) & If elevation in a state space landscape corresponds to cost, then the aim is to find the lowest valley (minimum). If the landscape corresponds to an objective function, then the aim is to find the highest peak. \\ \hline Goal Test & The goal test determines whether a given state is a goal state. \\ \hline Goal-directed reasoning & Goal directed reasoning is useful for answering specific questions such as "What shall I do now?" and "Where are my keys?" Backward chaining is an example of goal directed reasoning. CITATION(aitextbook) (p 220) \\ \hline Gradient ascent & The gradient defines the direction of the steepest ascent (in this case) or descent. (From calculus) \\ \hline Greedy Algorithm & A greedy algorithm always makes the choice that looks best at the moment. CITATION(IntroToAlgorithms) The Best-first search, also called the "greedy search" or "greedy best-first search", tries to expand the node that is closest to the goal, on the grounds that this is likely to lead to a solution quickly. Thus it evaluates nodes by using just the heuristic function \[ f(n) = h(n) \] \\ \hline Greedy local search & Hill climbing is sometimes called a greedy local search because it grabs a good neighbor state without thinking ahead about where to go next. \\ \hline Ground term & A term with no variables is called a ground term. CITATION(aitextbook) (p 249) \\ \hline Grounding & Grounding is the process of determining if the logical reasoning processes and the real environment in which the agent exists are consistent. The question is, "how do we know that KB is true in the real world?" Of course if you worried about this, you would never have time to worry about anything else. CITATION(aitextbook) (p 204) \\ \hline Hanhatten distance & This is the sum distances to the object in each dimension. Sometimes called the city block distance because you can't cut through the buildings. \\ \hline Head (of a Horn clause) & The positive literal of a horn clause is called the head. CITATION(aitextbook) (p 205) \\ \hline Heuristic Function & See $h(n)$. \\ \hline Heuristic Search & See "Informed search" \\ \hline Higher-Order Logic & Higher-Order logic views the relations and functions in first-order logic as objects in themselves. CITATION(aitextbook) (p 244) \\ \hline Hill climbing: first choice & Implements stochastic hill climbing by generating successor randomly until one is generated that is better than the current state. \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Hill climbing: random restart & Because hill climbing will find it harder and harder to find a better state as time goes on, we may stop the search process and start it from a new random location. This is called random restart. \\ \hline Hill climbing: stochastic & Stochastic hill climbing chooses at random from among the uphill moves where the probability of selection can vary with the steepness of the uphill move. \\ \hline Horn clauses & A horn clause is a disjunction of literals of which at most one is positive. CITATION(aitextbook) (p 204) \\ \hline Incremental formulation & An incremental formulation involves operations that augment or {\em build} the state description. The goal is to build a state that satisfies the goal test and at any point in the process, if we find we can not satisfy the goal state using the last augmentation, we may back track.\\ \hline Induction & General rules aquired by exposure to repeated associations between their elements. CITATION(aitextbook) \\ \hline Inference & Deriving new sentences from old. In the case of logical agents, inference must obey the fundamental requirement that when one asks a question of the knowledge base, the answer should follow from what has been told the knowledge base previously. CITATION(aitextbook) (p 195) \\ \hline Infinite domains & Domains where the size of the set is infinite. This can include discrete domains such as the integers. CITATION(aitextbook) (p 139) \\ \hline Informed Search & Strategies that know whether one non-goal state is more promising than another non-goal state are called informed or heuristic searches. \\ \hline Initial State & The state that the agent starts in. \\ \hline Instantiated variable & A variable is instantiated if it has been assigned a value from its domain. CITATION(ainotes) \\ \hline Intended interpretation & The intended interpretation is the one possible interpretation that we specify. CITATION(aitextbook) (p 246) \\ \hline Intensively defined constraint (not in textbook) & Intensionally defined constraints are used when it is not practical or even possible to list all tuples. This is the form we normally see using variables and relationship predicates. CITATION(ainotes) \\ \hline Interpretation & The semantics of FOL must relate sentences to models in order to determine truth. An interpretation specifies exactly which objects, relations and functions are referred to by the constant, predicate and function symbols.CITATION(aitextbook) (p 246) An {\em interpretation} for a set $X$ of formulas {\bf is a domain} $D$ together with a rule that \begin{itemize} \item assigns to each $n$-place predicate symbol (that occurs in a formula) of $X$ an $n$-place predicate in $D$; \item assigns to each $n$-place operation symbol of $X$ an $n$-place operation in $D$; \item assigns to each constant symbol of $X$ an element of $D$; \item assigns to $=$ the identity predicate $=$ in $D$, defined by: $a=b$ is true if and only if $a$ and $b$ are the same. CITATION(FOML) \end{itemize} \\ \hline Intractability & We say an algorithms is intractable if the time to run the algorithm increases exponentially as a function of the size of the problem. (From 310 or 823?) \\ \hline Intractability & A problem is called intractable if the time required to solve instance of the problme grows exponentially with the size of the instances. (p 8) \\ \hline Iterative-Deepening Search & Also called the {\em Iterative deepening depth-first search}, this is just a DFS performed to a depth $d$ where $d$ iteratively increases from $0$ to some limiting value $l$ until a goal is found. this will occur when $d$ reaches the shallowest goal state. Space complexity will be the same as the DFS $O(bd)$. Unlike DFS it is complete and finds the optimal goal when the path cost is a non-decreasing function of the depth of the node. {\em In general, iterative deepening is the preferred uninformed search method when there is a large search space and the depth of the solution is not known}. \\ \hline Iterative-Lengthening Search & Identical to the Iterative-Deepening Search except that the search uses an increasing path-cost limit instead of an increasing depth limit. This guarantees optimality while avoiding expensive memory requirements. \\ \hline k-CNF & A sentence expressed as a conjunction of disjunctions of literals is said to be in conjunctive normal form. A sentence is $k-$CNF if it has exactly (or at most) $k$ literals per clause. CITATION(aitextbook) (p 215) \\ \hline \end{tabular} }}} {{{#!latex2 \usepackage{amsmath}% \setcounter{MaxMatrixCols}{30}% \usepackage{amsfonts}% \usepackage{amssymb}% \usepackage{graphicx} \usepackage{geometry} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in} %%end-prologue%% \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Knowledge acquisition & Knowledge acquisition is the process of acquiring knowledge. This can be done by exploration or by (p261) applying to an outside expert to retrieve the knowledge required. \\ \hline Knowledge base & A set (conjunction) of sentences that represent facts about the world. CITATION(aitextbook) (p 195) \\ \hline Knowledge representation & One of the six disciplines of AI dedicated to the "representation" of knowledge that an entity knows or senses. CITATION(aitextbook) \\ \hline Knowledge representation language & A formal language used to represent sentences of information in the knowledge base. CITATION(aitextbook) (p 195) \\ \hline Leaf Node & A leaf node is an element of the fringe, that is, a node with no successors in the tree. \\ \hline Limited rationality & It is not always possible to do precisely the right thing in complicated environments do to high computational demands. CITATION(aitextbook) \\ \hline Linear constraints & Constraints in which each variable appears only in linear form. CITATION(ainotes) \\ \hline Linear Programming & Linear programming involves CSPs where constraints must be linear inequalities forming a convex region. CITATION(aitextbook) p 140 \\ \hline Literal & A literal is single symbol or its negation. CITATION(aitextbook) (p 204) \\ \hline Local Optimum & This corresponds to a peak or a valley in the state space landscape that is not the best solution. This is were a search may get stuck and need a random restart. \\ \hline Local Search & Local searches do not care about the path too the solution, and so they don't keep track of where they have been. The use very little memory and they can often find solutions in large or infinite (continuous) state spaces for which systematic algorithms are unavailable. \\ \hline Logical connectives & Not, conjunction, disjunction implication, biconditional which are respectively: $\neg \wedge, \vee, \Rightarrow, \Leftrightarrow$. CITATION(aitextbook) (p 204-205) \\ \hline Logical equivalence & Two sentences $A$ and $B$ are logically equivalent if they are true in the same set of models. This is written: $A \equiv B$. CITATION(aitextbook) (p 210) \\ \hline Min-conflict heuristic & The min-conflicts heuristic chooses a value for a variable that causes the fewest conflicts with other variables. CITATION(ainotes) \\ \hline Minimax algorithm & The minimax algorithm computes the minimax decision form 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 recursions unwinds. CITATION(aitextbook) (p 165) \\ \hline Minimax decision & When the Minimax value has been computed for each child node in the tree for the current node, the Minimax decision is the largest value of the child nodes. That is we choose the action that is the optimal choice (max value) because it guarantees the highest minimum value. CITATION(aitextbook) (p 165) \\ \hline Minimax value & \begin{equation} Minimax\text{-}Value(n)=\left\{ \begin{array}[c]{ll} Utility\left(n\right) & \text{if }n\text{ is a terminal state}\\ \max_{s\in Succ(n)}Minimax\text{-}Val(s) & \text{if }n\text{ is a }\max\text{ node}\\ \min_{s\in Succ(n)}Minimax\text{-}Val(s) & \text{if }n\text{ is a }\min\text{ node.} \end{array} \right. \end{equation} \\ \hline Minimum remaining values (a.k.a. least domain variable) & A heuristic that chooses the variable with the fewest legal values.CITATION(aitextbook) (p 143) \\ \hline Missionaries and cannibals problem & Three missionaries and three cannibals are on one side of a river, along with a both that can hold one or two people.. Find a way to get everyone to the other size without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place (p 90). \\ \hline Model (in general) & A model is a world in which a sentence is true under a particular interpretation. CITATION(ainotes) (11.4) \\ \hline Model checking & Given a knowledge base KB and a sentence $\alpha$, model checking enumerates all possible models to check that a sentence $\alpha$ is true in all models in which KB is true. OR, model checking ensures that $\alpha$ is true in each model contained in KB. CITATION(aitextbook) (p 202) \\ \hline Model in propositional logic & A model is a mapping from proposition symbols directly to truth or falsehood. The models of a sentence are the mappings that make the sentence true. CITATION(ainotes) \\ \hline Modus ponens & $\frac{\alpha \Rightarrow \beta,~~ \alpha}{\beta}$ CITATION(aitextbook) (p 211) \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Monotonicity (as a property of the $h$ function & A heuristic function $h(n)$ is said to be monotone if it satisfies: \[ h(n) \leq c(n,n') + h(n') \forall n,n' | n' \in SCS(n) \] where $SCS(n)$ gives the successors of $n$. \\ \hline Monotonicity (of inference) & Monotonicity says that the set of entailed sentences can only increase as information is added to the knowledge base. CITATION(aitextbook) (p 213) \\ \hline Mutation & In genetic algorithms after a crossover between two states has been completed we will sometimes randomly change the state by randomly changing one element of the state. This is called a mutation. \\ \hline Natural Language Processing & The ability of the computer to process English or some other natural language to communicate successfully. CITATION(aitextbook) \\ \hline Node consistency & A term meaning that a CSP is 1-consistent, or that any node by itself is consistent. CITATION(aitextbook) (p 147) \\ \hline Node expansion (in search) & After we examine a state (node) $x$ and determine that it is not a goal state, we determine the successor states (nodes) using the successor function. These set of states (nodes) are the expansion of $x$ (p 69). \\ \hline NP-completeness & The theory of NP-completeness, provides a method to reconize an intractable problem. Any problem class to which the class of NP-complete problems can be reduced is likely to be intractable. Cook and Karp showed the existence of large classes of canonical combinatorial search and resoning problems that are NP-complete. CITATION(aitextbook) \\ \hline Objective function & Objective functions are part of the description of an optimization problem that measures states to determine the best state. (from Glossary 6) \\ \hline Objective function (in optimization problem) & Objective functions are part of the description of an optimization problem that measures states to determine the best state. \\ \hline Occam's (or Ockham's) razor & is a principle attributed to the 14th-century English logician and Franciscan friar, William of Ockham. It forms the basis of methodological reductionism, also called the principle of parsimony or law of economy. In its simplest form, Occam's Razor states that one should make no more assumptions than needed. Put into everyday language, it says: Given two equally predictive theories, choose the simpler. CITATION(Wikipedia:OccamsRazor) \\ \hline Omniscience & Literally "all knowing". In the AI sense it means knowing all the information necessary to make the best choice that optimizes the performance measure. \\ \hline Open-loop & When given a {\bf static}, {\bf observable}, {\bf discrete}, {\bf deterministic} environment, solutions can be executed without pay attention to the percepts. Thus an agent carries out its plan with its eyes closed. Control theorists call this an {\bf open-loop} because it breaks the loop between agent and environment. \\ \hline Operator & Successor functions gives a description of the possible actions available to the agent. An alternate formulation uses a set of operators that can be applied to a state to generate successors. (p 62) \\ \hline Optimal solution & According to AIAMA: The optimal solution has the lowest path cost among all solutions. \\ \hline Optimally efficient & If an algorithm is optimally efficient it means that no other optimal algorithm is guaranteed to expand fewer nodes except possibly through tie-breaking among nodes with $f(n)=C^*$. {\em We note that $A^*$ is optimally efficient {\bf and} that it is also exponential in practice.} \\ \hline Optimization Problem & Optimization problem define as a goal to find the best state according to an objective function. \\ \hline Path & A {\em path} in the state space is a sequence of states connected by a sequence of actions. \\ \hline Path consistency & Any pair of adjacent variables can always be extended to a third neighboring variable - also called $3-$consistency. CITATION(aitextbook) (p 147) \\ \hline Path Cost & A {\em path cost} function assigns a numeric cost to each path from the root node to any node in the tree. \\ \hline Pathmax Equation CITATION(astar) & The PathMax function is an optimization routine that ensures monotonicity: \[ \hat{f}(m)=\max\{f(n),f(m)\} \] for all $m \in \{succ(n)\}$. \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Payoff function & Also called the {\bf objective function} or {\bf utility function}, it gives the numeric value for the terminal states. (Objective and utility functions generally give a value to each state). CITATION(aitextbook) (p 163) \\ \hline Percept Sequence & An agent's percept sequence is the complete history of everything the agent has ever perceived. \\ \hline Performance Measure & A performance measure embodies the criterion for success of an agent's behavior. \\ \hline Planning & Planning is the process of finding a sequence that achieves a desired effect given a suitable constructive inference algorithm (p 330). \\ \hline Plateau & An area in the state space landscape where the evaluation function is flat. I could be a flat local maximum or a shoulder. \\ \hline Ply & This is essentially a turn in a turn taking game. One move is made up of two different players in a two player game each taking a turn. Each turn is called a half move or ply. CITATION(aitextbook) (p 163) \\ \hline Predecessors & Predecessors of a state $x$ are all those states that have $x$ as a successor. \\ \hline Predicate symbol & Stand for relations in FOL. CITATION(aitextbook) (p 246) \\ \hline Premise & The premise or antecedent is the left hand side of an implication ($\Rightarrow$). CITATION(aitextbook) (p 205) \\ \hline Problem Formulation & Problem formulation is the process of deciding what actions and states to consider, given a goal. A problem can be defined formally by four components: \begin{enumerate} \setlength{\topsep}{0in} \setlength{\parsep}{0in} \setlength{\parskip}{0in} \setlength{\itemsep}{0in} \item initial state \item successor function \item goal test \item path cost \end{enumerate} \\ \hline Proof & A sequence of applications of inference rules is called a proof. CITATION(aitextbook) (p 212) \\ \hline Property & Unary relations CITATION(aitextbook) (p 242) \\ \hline Proposition symbol & A symbol that can be assigned true or false which represents a proposition (or statement). CITATION(aitextbook) (p 204) \\ \hline Propositional logic & Propositional logic is a very simple language consisting of proposition symbols and logical connectives. It can handle propositions that are known true, known false, or completely unknown. CITATION(aitextbook) (p 233) Propositional logic is made up of a set of symbols and boolean connectives $\wedge, \vee, \neg, \Rightarrow, \Leftrightarrow$ formed into sentences using the formal grammar form: Backus-Naur Form. The semantics are defined by the operation of the connectives as either True or False. CITATION(ainotes) (11.3, 11.7) \\ \hline Pruning & When a node $n'$ is explored and placed in the fringe as part of a node expansion of $n$ and $h(n') > h(n)$ then $A^*$ will not never expand this node, because $f(n') > C^*$. When this happens we say that $n'$ is {\em pruned}. \\ \hline Pruning (in general) & Pruning is the process of eliminating possibilities from consideration without having to examine them. In a tree structure we often say that we prune a subtree or branch by eliminating it from consideration. CITATION(aitextbook) (p 100) \\ \hline Rationality & Rationality (restricted rationality) is the ideal concept of intelligence (restrcited rationality is listed above) It simply means to do the right thingCITATION(aitextbook) \\ \hline Reduction ad absurdum & Proving $\beta$ from $\alpha$ by checking the unsatisfiability of $(\alpha \wedge \neg \beta)$ corresponds exactly to the standard mathematical proof technique of {\em reductio ad aburdum}. This is also called refutation: $\alpha \models \beta$ if and only if the sentence $(\alpha \wedge \neg \beta)$ is unsatisifiable. CITATION(aitextbook) (p 211) \\ \hline Refutation completeness & Any complete search algorithm, applying only the resolution rule, can derive any conclusion entailed by any knowledge base in propositional logic. There is a caveat: resolution is complete in a specialized sense. Given that $A$ is true, we can not use the resolution to automatically generate the consequence $A \vee B$ is true. This is called {\bf refutation completeness}, meaning that resolution can always be used to either confirm or refute a sentence, but it cannot be used to enumerate true sentences. CITATION(aitextbook) (p 214) \\ \hline Relation & A relation between $A$ and $B$ is defined as $R_{A,B} \subseteq A \times B$ or $R_{A,B} \subseteq \{ (x,y) | x \in A, y \in B\}$ CITATION(ainotes) \\ \hline Relation (mathematical definition) & A relation between $A$ and $B$ is defined as $R_{A,B} \subseteq A \times B$ or $R_{A,B} \subseteq \{ (x,y) | x \in A, y \in B\}$ CITATION(ainotes) \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Relaxed problem & A problem with fewer restrictions on the actions is called a {\em relaxed problem}. The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem. \\ \hline Resolution & If $l_i$ and $m_j$ are complementary literals, then we have resolution defined as: \begin{equation} \frac{l_1 \vee ... \vee l_k, ~~~~ m_1 \vee ... \vee m_n} {l_1 \vee ... \vee l_{i-1} \vee l_{i+1} \vee ... \vee l_k \vee m_1 \vee ... \vee m_{j-1} \vee m_{j+1} \vee ... \vee m_n} \end{equation} CITATION(aitextbook) (p 214) \\ \hline Resolution closure & Given a set of clauses $S$, resolution closure is the set of all derivable clauses. CITATION(aitextbook) (p 217) \\ \hline Route-finding problem & The Route-finding problem is defined in terms of locations and transitions along links between them. \\ \hline Satisfiability & A sentence is satisfiable if it is true in some model. CITATION(aitextbook) (p 211) \\ \hline Search & The search process consists of finding a path from the initial state to a goal state (p 60). The essence of a search is to check a state (node) to determine if it satisfies the goal state and expanding it to find other options to examine later if it does not. (p 69) \\ \hline Search cost (vs. total cost) & Search cost typically depends on the time complexity , but can also include a term for memory usage. Total cost combines the search cost and the path cost of the solution found (p 72). \\ \hline Search node & The search node corresponds to the node representing the initial state. (p69) \\ \hline Search Strategy & The {\em search strategy} determines which which state to expand next. \\ \hline Search Tree & A tree structure generated from the initial state and children found using the successor function defines the search tree. \\ \hline Semantics (of a logic) & The semantics of the language defines the truth of each sentence with respect to each possible world. CITATION(aitextbook) (p 207) \\ \hline Sensorless problem & (Also called conformant problems) If an agent has no sensors at all, then it could be in one of several possible initial states, and each action might lead to one of several possible successor states. To know that a goal state has been reached, all states in the successor set must be goal states. \\ \hline Sentence & A sentence is a representation of a fact in the world in a {\em formal language}. CITATION(ainotes) (10.3) \\ \hline Sideway move & When reaching a shoulder, we can not find a state to move to that is better than the state we are in. To fix this we allow moving to states that are equal in hopes of finding a way off a shoulder. This is called a sideways move. \\ \hline Simulated annealing & This combines hill climbing with random walk in such a way that the amount of randomness slowly decreases (cools) over time. \\ \hline Size of a CSP & The size of a CSP is characterized by the number of constraints. CITATION(ainotes) \\ \hline Solution quality & Solution quality is measured by the path cost function. \\ \hline Soundness (of inference) & An inference algorithm that derives only entailed sentences is called sound. CITATION(aitextbook) (p 203) \\ \hline State space & Together, the initial state and successor function implicitly define the state space which is the set of all states reachable from the initial state. \\ \hline Step Cost & The step cost is the cost of taking an action $a$ to go from state $x$ to state $y$ is denoted by $c(x,a,y)$. \\ \hline Straight-line distance & The shortest distance between two points. This is an especially interesting heuristic, because it will always be optimistic no mater how we define points and measures we use for distance in our problem since the shortest distance between two points is a straight line. \\ \hline Strong $k-$consistency & A graph is strongly $k-$consistent if it is $i-$consistent for $i \in {1,..,k}$. CITATION(aitextbook) (p 147) \\ \hline Substitution & When posing a query $\exists x~Predicate(x)$, answering yes is not very helpful. The standard form of an answer to such a query includes a set of values that satisfy the query. This set is called a substitution or binding list. CITATION(aitextbook) (p 254) \\ \hline Successor Function (in search) & The successor function is a function $S:x \in {s_i} \rightarrow S(s_i):\{<A_j , S_{i+1}^j>^*\}$ where $s_i$ is a state, $A_j$ are actions and $S_{i+1}^j$ is a state. [notes] \\ \hline Syllogism & A Syllogism is an inference in which one proposition (conclusion) follows necessarily from two other premises. It is irrefutable reasoning processes (or patterns) that consequently always yield correct conclusions. CITATION(aitextbook) \\ \hline \end{tabular} }}} {{{#!latex2 \usepackage{amsmath}% \setcounter{MaxMatrixCols}{30}% \usepackage{amsfonts}% \usepackage{amssymb}% \usepackage{graphicx} \usepackage{geometry} \newtheorem{theorem}{Theorem} \newtheorem{acknowledgement}[theorem]{Acknowledgement} \newtheorem{algorithm}[theorem]{Algorithm} \newtheorem{axiom}[theorem]{Axiom} \newtheorem{case}[theorem]{Case} \newtheorem{claim}[theorem]{Claim} \newtheorem{conclusion}[theorem]{Conclusion} \newtheorem{condition}[theorem]{Condition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{criterion}[theorem]{Criterion} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{exercise}[theorem]{Exercise} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{notation}[theorem]{Notation} \newtheorem{problem}[theorem]{Problem} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{remark}[theorem]{Remark} \newtheorem{solution}[theorem]{Solution} \newtheorem{summary}[theorem]{Summary} \newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}} \geometry{left=0.5in,right=0.5in,top=0.5in,bottom=0.5in} %%end-prologue%% \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Syntax (of a logic) & Defines the sentences in a language (grammar) CITATION(ainotes) (10.16) \\ \hline Task Environment$^*$ & PEAS: Performance, Environment, Actuators, Sensors. \\ \hline Tautology & A sentence that is valid. CITATION(aitextbook) (p 210) \\ \hline Term & A term is a logical expression that referes to an object. CITATION(aitextbook) (p 248) \\ \hline Terminal states & States where the game has ended are called terminal states. CITATION(aitextbook) (p 163) \\ \hline Terminal test & A terminal test determines when the game is over. CITATION(aitextbook) (p 163) \\ \hline Ternary constraint & A constraint involving 3 variables. CITATION(ainotes) \\ \hline Theorem & Theorems are sentences entailed by axioms. CITATION(aitextbook) (p 255) \\ \hline Total Turing test & A human judge engages in a natural language conversation with two other parties, one a human and the other a machine; if the judge cannot reliably tell which is which, then the machine is said to pass the test. To this "Turing test" we add a video signal and the opportunity to pass physical object "through the hatch" to get a total Turing test. \cite{Wikipedia:TuringTest, aitextbook} \\ \hline Touring Problem & Visit every city (vertice) given at least once starting and ending at a specific city. Or more precisely given a graph $G=(V,E)$ and an initial vertex $v_0$ give a sequence of edges such that each vertex is visited at least once (p 67). \\ \hline Toy Problems & A toy problem is intended to illustrate or exercise various problem-solving methods. It can be given a concise, exact, description and is easily used by different researchers to compare the performance of algorithms. \\ \hline Transpositions & In games, repeated states occur frequently because of transpositions which are different permutations of the move sequence that end up in t6he same position (or state). CITATION(aitextbook) (p 170) \\ \hline Traveling Salesperson Problem (TSP - give a {\em formal} definition) CITATION(NPCompleteness) & INSTANCE: A finite set $C={c_1,c_2,...,c_m}$ of cities, a distance $d(c_i,c)j) \in Z^+$ for each pair of cities $c_i,c_j \in C$, a bound $B \in Z^+$. QUESTION: Is there a "tour" of all the cities in $C$ having total length no more than $B$, that is, an ordering $<c_{\pi(1)},c|{\pi(2)},...,c_{\pi(m)}>$ of $C$ such that \begin{equation} \left(\sum_{i=1}^{m-1}d(c_{(i)},c_{(i+1)})\right)+d(c_{\pi(m)},c_{\pi(1)}=B? \end{equation} \\ \hline Tree decomposition (of a CSP) & The process of decomposing a constraint graph into a tree of connected components. A tree decomposition must satisfy the following three requirements: (1) Every variable in the original problem appears in at least one of the subproblems. (2) If two variables are connected by a constraint in the original problem, they must appear together (along with the constraint) in at least one of the subproblems. (3) If a variable appears in two subproblems in the tree, it must appear in every subproblem along the path connecting the those subproblems. CITATION(aitextbook) (p 154) \begin{definition} A \emph{tree-decomposition} of a graph $G$ is a tree $T$ whose nodes, called bags, are subsets of $V\left( G\right) $ such that: \begin{enumerate} \item $\cup _{x\in V\left( T\right) }X=V\left( G\right) ;$ \item $\forall \left\{ u,v\right\} \in E\left( G\right) $, $\exists X\in V\left( T\right) $ such that $u,v\in X;$ and \item $\forall X,Y,Z\in V\left( T\right) $, if $Y$ is on the path from $X$ to $Z$ in $T$ then $X\cap Z\subseteq Y$. From Dourisboure and Gavoille CITATION(doorisboure03) \end{enumerate} \end{definition} \\ \hline Tree width of a graph (check a book on graph theory) & Let $T$ be a tree-decomposition fo a graph $G$. The width of $T$ is \begin{equation} width(T) =\max_{X\in T}\{ \left\vert X\right\vert -1\} \end{equation} Let $D$ be the set of all decompositions of the tree $T$. Then the tree width is $\min_{T\in D}width\left( T\right) $. CITATION(doorisboure03) \\ \hline Triangle inequality & In AI we say \[ h(n) \leq c(n, a, n') + h(n') \] is the triangle inequality for paths from one node to another in the search tree. \\ \hline Truth table & A truth table specifies the truth value of a complex sentence for each possible assignment of truth values. CITATION(aitextbook) (p 206) \\ \hline \end{tabular} }}} {{{#!latex2 \noindent \begin{tabular}[c]{|p{2in}|p{4.75in}|}\hline Turing machine & A Turing machine is a 7-tuple, $\left( Q,\Sigma ,\Gamma,\delta,q_{0},q_{accept},q_{reject}\right) $, where $Q$ is the set of start states, $\Sigma$ is the input alphabet not containing the blank symbol, $\Gamma$ is the tape alphabet, where $\_\in\Gamma$ and $\Sigma\subseteq\Gamma $, $\delta : Q\times\Gamma\rightarrow Q\times\Gamma\times\left\{ L,R\right\} $ is the transition function, $q_{0}\in Q$ is the start state, $q_{accept}\in Q$ is the accept state, and $q_{reject}\in Q$ is the reject state, where $q_{accept}\neq q_{reject}$. CITATION(IntroToTheTheoryOfComputation2) \\ \hline Turing test & A human judge engages in a natural language conversation with two other parties, one a human and the other a machine; if the judge cannot reliably tell which is which, then the machine is said to pass the test. CITATION(Wikipedia:TuringTest) \\ \hline Unary constraint & The simplest kind of constraint which restricts a single variable. CITATION(aitextbook) (p 140) \\ \hline Uniform-cost search & This strategy expands the node $n$ with the lowest path cost. Thus this will use a $min-priority-queue$ to determine which nodes to explore and expand next. If all step costs are equal this is identical to the BFS. Let $C^*$ be the cost of the optimal solution, and assume that every action costs at least $\epsilon$. Then the algorithms's worst-case time and space complexity is $O(b^{1+\lfloor C^*/\epsilon \rfloor})$ which can be much greater than $b^d$. \\ \hline Uninformed search & These types of searches have no information beyond what is given in the problem definition (this is also called the blind search). All they can do is generate successors and distinguish a goals state from a non-goal state. There are five given in Section 3.4: BFS, Uniform-Cost Search, DFS, Depth-limited Search, Iterative deepening depth-first search, and bidirectional search. \\ \hline Unit clause & A unit clause is a cloause with just one literal. CITATION(aitextbook) (p 221) \\ \hline Universal constraint & A statement that the two variable are not involved in a constraint together. CITATION(ainotes) \\ \hline Utility Function & A utility function maps a state (or sequence of states) onto a real number, which describes the associated degree of happiness. This allows rational decisions to be made when goals are inadequate. (1) When goals conflict and (2) When uncertainty is attached to several goals the utility function can give a way to determine which is goal is most likely achievable. \\ \hline Validity & A sentence is valid if it is true in all models. CITATION(aitextbook) (p 210) \\ \hline Validity (of a logical sentence) & A sentence is valid if it is true in all models. CITATION(ainotes) \\ \hline World Value ordering heuristic & Determines the order in which you choose values to assign to a variable from the domain. CITATION(aitextbook) (p 143) \\ \hline Variable (of a CSP) & Variables are part of a CSP that can take values defined by their domains. CITATION(aitextbook) (p 137) \\ \hline Variable ordering heuristic & Determines the order in which you assign variables. CITATION(aitextbook) (p 143) \\ \hline Zero-sum games & Means environments in which the utility values at the end of the game are always equal and opposite. CITATION(aitextbook) (p 161) \\ \hline \end{tabular} \bigskip All definitions without a citation come from CITATION(aitextbook) }}} |
<<EmbedObject(AIGlossary.pdf,width=100%,height=600px)>> |
From the Tex File: AIGlossary.tex