1. Define in your own words the following terms: state, state space, search tree
ID: 3804918 • Letter: 1
Question
1. Define in your own words the following terms: state, state space, search tree, search node, goal, action, transition model, and branching factor.
2. Your goal is to navigate a robot out of a maze. The robot starts in the center of the maze facing north. You can turn the robot to face north, east, south, or west. You can direct the robot to move forward a certain distance, although it will stop before hitting a wall.
a. Formulate this problem. How large is the state space?
b. In navigating a maze, the only place we need to turn is at the intersection of two or more corridors. Reformulate this problem using this observation. How large is the state space now?
3. Define in your own words the following algorithms:
a. Local beam search:
b. Simulated annealing algorithm:
c. Genetic algorithm:
4. Discuss how well the standard approach to game playing would apply to games such as tennis, pool, and croquet, which take place in a continuous physical state space.
5. Prove the following assertion: For every game tree, the utility obtained by MAX using minimax decisions against a suboptimal MIN will never be lower than the utility obtained playing agains an optimal MIN. Can you come up with a game tree in which MAX can do still better using a suboptimal strategy against a suboptimal MIN?
Explanation / Answer
a) State
A state is an representation for an agent that can find itself in. These are of two types :
world states:The actual situations in the real time in the real world. Representational state:The
abstract descriptions of the real world that are used by the agent in deliberating about what to
do.
b) State space
A state space is a graph whose nodes are the set of all states, and those links are
actions of the agent that can take the agent from one state into other state.
c) Search tree
A search tree is a tree with no undirected loops in which the root node is
the start state and the set of children for each node consists of the states reachable by taking any
action.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.