Artificial Intelligence - A Modern Approach Chapter 3
Terms
undefined, object
copy deck
- Exploration Problems
- when the states and actions of the environment are unknown the agent must act to discover them.
- Route Finding Problem
- is defined in terms of specified locations and transitions along links between them
- Iterative Deepening Depth First Search
- depth first search but when all the nodes have been expanded and no solution found the depth limit is increased.
- Measuring Problem Solving Performance
- completeness, optimality, time complexity, space complexity
- Contingency Problems
- 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 contigency that must be planned for.
- Abstraction
- process of removing detail from a representation is called abstraction
- Goal Test
- test which determines if a given state is the goal state
- Problem Formulation
- which actions and states to consider given a goal
- Touring Problem
- visit every node (The Traveling Salesperson problem)
- Breadth-First Search
- root node is expandd first, then all the successors of the root node are expanded next and so on. Expands the shallowest unexpanded node
- Search Algorithm
- takes a problem as input and returns a solution in the form of an action sequence (formulate, search, execute)
- State Space
- The initial state and the successor function implicitly define the state space (all possible states from the initial state)
- Goal Formulation
- based on the current situation and the agent's performance measure, is the first step in problem solving.
- Informed
- search algorithms that have some idea of where to look for solutions
- Branching Factor
- Maximum number of successors to any node
- Uniform Cost Search
- Expands the node n with the lowest path cost (if all step costs are equal, this is identical to a breadth-first search)
- Depth-Limited Search
- same as depth first search but limit the maximum depth allowed (not useful unless the maximum possible depth can be determined)
- Uniformed
- given no information about the problem other than its definition
- Path Cost
- assigns a numeric cost to each path
- Bidirectional Search
- two simultaneous searches, one from the initial state and from the goal state
- Sensorless Problems
- if the agent has no sensors at all, then it could be in one of several possible initial states and each action might therefore lead to one of several possible successor states
- Initial State
- the state that the agent start in
- Problem Solving Agent
- decides what to do by finding sequences of actions that lead to desirable states
- Successor Function
-
a description of possible actions available to the agent. The successor function, given a state, returns
- n-puzzle
- object is to reach a specified goal state, such as the one shown on the right of the figure
- Depth First Search
- always expands the deepest node until the node has no successor
- Step Cost
- the step cost of taking action a to go from state x to state y is denoted by c(x, a ,y)