Ai Midterm

Front 1

the ability to apply knowledge and reasoning in order to perform well in an environment

Back 1

Intelligence

Front 2

the study and construction of agent programs that perform well in a givern environment for a given agent architecture

Back 2

ai

Front 3

an entity that computes and takes an action in response to percepts from an environment

Back 3

agent

Front 4

the property of a system that does the right thing given what it knows and perceives

Back 4

rationality

Front 5

An agent that seses only partial information about the state cannot be perfectly rational

Back 5

False. Perfect rationality refers to the ability of an agent to make good decisions given what sensor information is received

Front 6

There exist task environments in which no pure reflex agent can behave rationally

Back 6

True. A pure reflex agent ignores previous percepts, so might not obtain an optimal state estimate in a partially observable environment

Front 7

There exists a task environment in which every agent is rational

Back 7

True.For example, an environment that always gives the same state no matter what action the agents chooses

Front 8

The input to an agent program is the same as the input to the agent function

Back 8

False. The agent function takes the entire percept sequence up to that point as input, whereas the agent program takes the current percept only.

Front 9

Every agent function is implementable by some program/machine combination

Back 9

False. For example, if the agent’s job is to act as a universal Turing machine to determine the result of the halting problem, then it is not implementable.

Front 10

Using only four colors, you have to color a planar map in such a way that no two adjacent regions have the same color

Back 10

- Initial state: No regions colored.

- Agent actions: Assign a color to an uncolored region.

- Transition model: resultant colored map after assigning a color to a region.

- Goal test: All regions colored, no two adjacent regions have the same color, and the total number of colors is at most 4.

Front 11

directed graph whose nodes are the set of all states and whose arcs are actions that transform one state into another

Back 11

State space

Front 12

a tree in whish the root node is the initial state and the set of children for each node consists of those states reachable from current state by taking any action

Back 12

search tree

Front 13

specifies how the environment transitions from one state to the next through agent actions

Back 13

transition model

Front 14

branching factor

Back 14

number of actions available to the agent

Front 15

depth first search always expands at least as many nodes as A* search with an admissible heuristic

Back 15

False

Front 16

A* is of no use in robotics because percepts, states, and actions are continuous

Back 16

False: the continuous spaces can be discretized

Front 17

breadth first search is complete even if zero step costs are allowed

Back 17

True. Depth of solution matters for breadth-first search, not cost

Front 18

is h= |u-x| + |v - y| an admissible heuristic for a state at (u, v)?

Back 18

Yes, this is manhattan distance.

Front 19

Does manhattan distance remain admissible if some links are removed?

Back 19

Yes, in this case h is still a lower bound

Front 20

PEAS stands for

Back 20

Performance measures, environment, actuators, sensors

Front 21

each state of the world is indivisible and has no internal structure

Back 21

Atomic representation

Front 22

each state is split into fixed set of variables or attributes, each of which have a value. Constraint satisfaction algorithms are based on factored representations

Back 22

factored representation

Front 23

objects and their relationships can be described explicitly. It underlies first order logic, natural language understanding, etc.

Back 23

structured representation

Front 24

Select actions on the basis of the current percept, ignoring percept history

Back 24

Reflex agent

Front 25

Agent needs goal information that describes situations that are desirable

Back 25

Goal based agent

Front 26

Agent should keep track of the part of the world it can’t see now. Maintain internal state that depends on percept history. Requires two kinds of knowledge: Info about how the world evolves independently of the agent and info about how agents own actions affect the world

Back 26

Model based agent

Front 27

A utility function maps a state onto a real number which describes the associated degree of happiness

Back 27

Utility based agent

Front 28

If there is a goal state, the algorithm will always return a solution

Back 28

Complete

Front 29

Returns a goal state with the shortest path cost, when there are multiple goal states

Back 29

Optimal

Front 30

Number of nodes generated

Back 30

time complexity

Front 31

max number of nodes in memory

Back 31

Space complexity

Front 32

the number of children at each node, the outdegree

Back 32

branching factor

Front 33

BFS time complexity

Back 33

O(b^d)

Front 34

BFS Space complexity

Back 34

O(b^d)

Front 35

DFS Time complexity

Back 35

O(b^m)

Front 36

DFS Space complexity

Back 36

O(bm)