Shared Flashcard Set

Details

Artificial Intelligence a Modern Approach
Vocabulary and concepts from the book
65
Computer Science
Undergraduate 4
08/29/2011

Additional Computer Science Flashcards

 


 

Cards

Term
PEAS
Definition
Performance Measure
Environment
Actuators
Sensors
Term
Rational Agent
Definition
For each possible percept sequence, a rational agent should select an action that is ex-
pected to maximize its performance measure, given the evidence provided by the percept
sequence and whatever built-in knowledge the agent has.
Term
Performance Measure
Definition
As a general rule, it is better to design performance measures according to what one actually
wants in the environment, rather than according to how one thinks the agent should behave.
Term
Autonomy
Definition
To the extent that an agent relies on the prior knowledge of its designer rather than
on its own percepts, we say that the agent lacks autonomy. A rational agent should be
AUTONOMY
autonomous—it should learn what it can to compensate for partial or incorrect prior knowl-
edge. For example, a vacuum-cleaning agent that learns to foresee where and when additional
dirt will appear will do better than one that does not. As a practical matter, one seldom re-
quires complete autonomy from the start: when the agent has had little or no experience, it
would have to act randomly unless the designer gave some assistance. So, just as evolution
provides animals with enough built-in reflexes to survive long enough to learn for themselves,
it would be reasonable to provide an artificial intelligent agent with some initial knowledge
Term
Task Environment
Definition
PEAS
Term
Task Environment properties
Definition
Fully observable vs. partially observable: If an agent's sensors give it access to the complete state of the environment at each point in time, then we say that the task environ-ment is fully observable.

Single agent vs. multiagent
Term
Multi Agent Task Environment vs 1 agent in a multi object/factor Task environment
Definition
The key distinction is whether B's behavior is best described as maximizing a performance measure whose value depends on agent A's behavior. For example, in chess, the opponent entity B is trying to maximize its performance measure, which, by the rules of chess, minimizes agent As per-formance measure. Thus, chess is a competitive multiagent environment.
Term
Deterministic Task Environment
Definition
If the next state of the environment is completely deter-mined by the current state and the action executed by the agent, then we say the environment
is deterministic; otherwise, it is stochastic.
Term
Uncertain Task Environment
Definition
We say an environment is uncertain if it is not fully observable or not deterministic.
Term
Difference between stochastic task environment and none deterministic task environment
Definition
Stochastic environment often is characterized by probabilities instead of certainties. None deterministic is not characterized by probabilities but has a set of possible outcomes.
Term
Episodic task environment
Definition
current precept and action by agent has no connection with either past or future precepts or actions
Term
Sequential task environment
Definition
Agents current precept and action has a connection to either or both future and past precepts and actions.
Term
Static versus Dynamic task environment
Definition
If the environment changes while the agent is deliberating, it's dynamic, otherwise it's static.
Term
Discrete vs Continuous task environment
Definition
digital vs analog applied to the environment state, such as chess positions vs the dashboard dials on a robot taxi.
Term
Known vs Unknown task environment
Definition
Whether the laws of physics or operation in the environment or known or unknown. Similar to encountering a video game and it's unknown buttons for the first time. Different than observable vs unobservable environment
Term
Hardest case task environment
Definition
the hardest case is partially observable, multiagent, stochastic,
sequential, dynamic, continuous, and unknown.
Term
Observable vs Unobservable task environment
Definition
Self describes. Also semi observable.
Term
agent=?
Definition
architecture + program
Term
What is an agent function?
Definition
The set of all input to output matches
Term
What is an agent program?
Definition
A program that embodies the agent function
Term
Why is a table driven agent program not realistic for the large majority of agents?
Definition
Because the table would end up being too big to store or create for most agent functions.
Term
What is a key challenge for AI regarding methods for creating an agent program for a given agent function?
Definition
The key challenge for AI is to find out how to write programs that,to the extent possible, produce rational behavior from a smallish program rather than from a vast table. We have many examples showing that this can be done successfully in other areas: for example, the huge tables of square roots used by engineers and schoolchildren prior to the 1970s have now been replaced by a five-line program for Newton's method naming
on electronic calculators. The question is, can AI do for general intelligent behavior what Newton did for square roots? We believe the answer is yes.
Term
What is a simple reflex agent?
Definition
These agents select actions on the basis
SIMPLE REFLEX
AGENT
of the current percept, ignoring the rest of the percept history.
Term
what is a model based reflex agent?
Definition
it tracks world state in it's memory, in particular currently unobservable factors as they were last observed. It's action reflex is determined not only by the current percept, but also by it's memory of the world state.
Term
What is a goal based agent?
Definition
It uses both it's internal model and a set of goals to to choose actions which are best suited to achieve it's goals.
It does that by attempting to answer these questions:
"What will happen if I do such-and-such?" and "Will that make me happy?"
Term
What is a utility based agent?
Definition
Partial observability and stochasticity are ubiquitous in the real world, and so, therefore,is decision making under uncertainty. Technically speaking, a rational utility-based agent chooses the action that maximizes the expected utility of the action outcomes—that is, the EXPECTED UTILITY utility the agent expects to derive, on average, given the probabilities and utilities of each
outcome.
Term
What is a learning based agent?
Definition
Learning in intelligent agents
can be summarized as a process of modification of each component of the agent to bring the components into closer agreement with the available feedback information,(in pursuit of goals and utility) thereby improv-
ing the overall performance of the agent.
Term
What are the 4 parts of a learning agent?
Definition
Critic, Learning Element, Problem Generator, Performance Element
Term
What is the purpose of the problem generator in the learning agent?
Definition
It varies the actions chosen by the performance element for the purpose of learning more about the environment. Such as for example stepping on the brakes of a robot car in order to see how fast they stop the car on a wet road.
Term
Ch 3
What is a problem solving agent?
Definition
A type of goal based agent in which the world state is atomic.
Term
What is a planning agent?
Definition
a goal based agent that uses a factored or structured world representation.
Term
Ch 3 pre-review
What is polynomial time?
Definition
In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the size of the input to the problem. The time complexity of an algorithm is commonly expressed using big O notation, which suppresses multiplicative constants and lower order terms. When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity. For example, if the time required by an algorithm on all inputs of size n is at most 5n3 + 3n, the asymptotic time complexity is O(n3).
Term
ch 3 pre-review
What is a complexity class?
Definition
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
Term
ch 3 pre-review
What is a none deterministic algorithm?
Definition
In computer science, a nondeterministic algorithm is an algorithm that can exhibit different behaviors on different runs, as opposed to a deterministic algorithm.
Term
ch 3 pre-review
What is NP and NP-Complete?
Definition
In computational complexity theory, NP is one of the most fundamental complexity classes. The abbreviation NP refers to "nondeterministic polynomial time."

Intuitively, NP is the set of all decision problems for which the instances where the answer is "yes" have efficiently verifiable proofs of the fact that the answer is indeed "yes." More precisely, these proofs have to be verifiable in polynomial time by a deterministic Turing machine. In an equivalent formal definition, NP is the set of decision problems where the "yes"-instances can be recognized in polynomial time by a non-deterministic Turing machine. The equivalence of the two definitions follows from the fact that an algorithm on such a non-deterministic machine consists of two phases, the first of which consists of a guess about the solution which is generated in a non-deterministic way, while the second consists of a deterministic algorithm which verifies or rejects the guess as a valid solution to the problem.[2]

The complexity class P is contained in NP, but NP contains many important problems, the hardest of which are called NP-complete problems, for which no polynomial-time algorithms are known. The most important open question in complexity theory, the P = NP problem, asks whether such algorithms actually exist for NP-complete, and by corollary, all NP problems. It is widely believed that this is not the case.
Term
Ch 3 pre-review
What is NP-Complete?
Definition
A decision problem C is NP-complete if:

1. C is in NP, and
2. Every problem in NP is reducible to C in polynomial time.
Term
ch 2 summary
What is the first step in designing an agent?
Definition
A task environment specification includes the performance measure, the external environment, the actuators. and the sensors. In designing an agent, the first step must always be to specify the task environment as fully as possible.
Term
ch 2 summary
How many basic designs of an agent program are there?
Definition
The agent program implements the agent function_ There exists a variety of basic agent-program designs reflecting the kind of information made explicit and used in the decision process. The designs vary in efficiency, compactness, and flexibility. The
appropriate design of the agent program depends on the nature of the environment.


alternative answer at a rougher resolution level-5:
• Simple reflex agents;
• Model-based reflex agents;
• Goal-based agents; and
• Utility-based agents.
* Learning agents
Term
ch 2
What's the difference in how an agent and the (abstract) agent function deal with percepts?
Definition
2.4.1 Agent programs
The agent programs that we design in this book all have the same skeleton: they take the current percept as input from the sensors and return an action to the actuators. Notice the
difference between the agent program, which takes the current percept as input, and the agent
function, which takes the entire percept history.
Term
What are the 5 components of a problem definition?
Definition
* the agents initial state
*A description of the possible actions available to the agent Given a particular state
*A description of what each action does; the formal name for this is the transition model
*The goal test
*path cost
Term
What is the solution to a defined problem?
Definition
A solution to a problem is an action sequence that leads from the initial state to a goal state. Solution quality is measured by the path cost function, and an optimal solution has the lowest path cost among all solutions.
Term
abstraction
Definition
The process of removing detail from a representation
is called abstraction.
Term
valid abstraction
Definition
The abstraction is valid if we can expand any abstract solution into a solution in the more detailed world;
Term
useful abstraction
Definition
The abstraction is useful if carrying out each of the actions in the solution is easier than the original problem
Term
Good abstraction
Definition
The choice of a good abstraction thus involves removing as much detail as possible while retaining validity and ensuring that the abstract actions are easy to carry out. Were it not for the ability to construct useful abstractions, intelligent agents would be completely swamped by the real world.
Term
state space
Definition
Together, the initial state, actions, and transition model implicitly define the state space
of the problem—the set of all states reachable from the initial state by any sequence of actions.
Term
Transition Model
Definition
initial states, matched to given actions, matched to resulting states
Term
If a problem is NP-Complete, does that mean it's most optimal known algorithm solution is closer to the worst or best possible algorithm solutions for similar problems?
Definition
It will be closer to the worst.
Term
Is the sliding block puzzle NP-Complete or NP?
Definition
NP-Complete
Term
incremental formulation
Definition
adds to a state while searching for a solution
Term
complete state formulation
Definition
moves state elements around while searching for a solution
Term
P=NP?
Definition
The P versus NP problem is a major unsolved problem in computer science. Informally, it asks whether every problem whose solution can be efficiently checked by a computer can also be efficiently solved by a computer
Term
NP-Hard
Definition
NP-hard problems are those at least as hard as NP-complete problems, meaning that all NP-problems can be reduced to them, but NP-hard problems need not be in NP and thus need not have solutions verifiable in polynomial time.
Term
Touring problem
Definition
find a route on a map to visit each city at least once
Term
Traveling sales person problem
Definition
find the Shortest route on a map to visit each city only once.
Term
Automated Assembly sequencing
Definition
In assembly problems, the aim is to find an order in which to assemble the parts of some object.
Term
Protein design
Definition
Another important assembly problem is protein design, in which the goal is to find a sequence of amino acids that will fold into a
PROTEIN DESIGN
three-dimensional protein with the right properties to cure some disease.
Term
frontier
Definition
The set of all leaf nodes available for expansion at any given point is called the frontier.
Term
leaf node
Definition
a node with no (currently expanded) children on the tree
Term
Search Strategy
Definition
The process of expanding nodes on the frontier continues until either a solution is found or there are no more states to expand. The general TREE-SEARCH algorithm is shown informally in Figure 3.7. Search algorithms all share this basic structure; they vary primarily according to how they choose which state to expand next—the so-called search strategy.
Term
General Tree Search pseudo code.
Definition
function TREE-SEARCH( problem) returns a solution, or failure
initialize the frontier using the initial state of problem
loop do
if the frontier is empty then return failure
choose a leaf node and remove it from the frontier
then return the corresponding solution
if the node contains a goal state
expand the chosen node, adding the resulting nodes to the frontier
p 77
Term
How can algorithms avoid search redundant paths?
Definition
As the saying goes, algorithms that, oget their history are doomed to repeat it. The
way to avoid exploring redundant paths is to remember where one has been. To do this, we augment the TREE-SEARCH algorithm with a data structure called the explored set (also
aPLORED set known as the closed list), which remembers every expanded node.
Term
Difference between nodes and states
Definition
Up to now, we have not been very careful to distinguish between nodes and states, but in writing detailed algorithms it's important to make that distinction. A node is a bookkeeping data structure used to represent the search tree. A state corresponds to a configuration of the world. Thus, nodes are on particular paths, as defined by PARENT pointers, whereas states are not. Furthermore, two different nodes can contain the same world state if that state is
generated via two different search paths.
Term
Data structure of a node
Definition
* node.STATE: the state in the state space to which the node corresponds;
* node.PARENT: the node in the search tree that generated this node;
* node.ACTION: the action that was applied to the parent to generate the node;
* node.PATH-COST: the cost, traditionally denoted by y(ti), of the path from the initial state to the node, as indicated by the parent pointers.
Term
exponential complexity search problems
Definition
exponential-complexity search problems
cannot be salved by uninformed methods for any but the smallest instances.
Supporting users have an ad free experience!