Foundations of Artificial Intelligence
Instructions: Answer all questions
Part A: True/False. Indicate whether the following statements are True or False. [10]
- The traditional Turing Test is an interactive test consisting of exactly two artificial agents and one human agent.
- Depth-first search is always slower than breadth-first search.
- A* search is always faster than hill climbing.
- A newborn baby comes pre-wired with intelligence.
- Learning is an attribute of intelligence.
- For an agent to adapt to a new environment it needs to be intelligent.
- Draughts (checkers) and Scrabble are both deterministic games.
- When playing games, the horizon effect can be solved by limiting the search depth.
- A rational intelligent agent acts in such a way as to minimize its expected value of performance measure given the percept sequence to date.
- “Two primary school children, Dennis and Sarut are playing the Tic-tac-toe game. Dennis makes the first move (starts the game).” The minimum number of moves Sarut could make is 2 for Dennis to win the game.
Part B: Multiple-choice. Select the most suitable answer. [6]
- What is the space complexity of breadth-first search with branch factor b, solution depth d, and maximum search depth m?
(A) O (bd/2) (B) O (bd) (C) O (bm) (D) O (bd) (E) O (bm)
- Which term describes a case in heuristic search where the positive gradient in the heuristic evaluation function lies along a small region of the state space?
- Plateau problem
- Ridge problem
(C) Foothill problem (local optima that are not global optima)
(D) (A), (B) but not (C)
(E) (A), (B) and (C)
- Natural language understanding is used in
(A) natural language interfaces
(B) natural language front ends
(C) text understanding systems
(D) All of the above
(E) (B) and (C) above
- What is the term used for describing the judgmental or commonsense part of problem solving?
(A) Heuristic
(B) Critical
(C) Value based
(D) Analytical
(E) None of the above
- A computer program that contains expertise in a specific domain is called an:
(A) intelligent planner
(B) automatic processor
(C) expert system
(D) operational symbolizer
(E) None of the above
- A search method that examines the values associated with the immediate successor nodes and goes to the node with the highest value, is
(A) sequential search
(B) minimax search
(C) hill-climbing search
(D) heuristic search
(E) None of the above
Part C: Work out. [9]
- Using the A* algorithm work out a route from town A to town M. Use the following cost functions. [7]
g(n) = The cost of each move as the distance between each town (shown on map).
h (n) = The straight line distance between any town and town M. These distances are given in the table below.
Provide the search tree for your solution and indicate the order in which you expanded the nodes. Finally, state the route you would take and the cost of that route.
Straight Line Distance to M
| A | 223 | E | 165 | I | 100 | M | 0 | |||
| B | 222 | F | 136 | J | 60 | |||||
| C | 166 | G | 122 | K | 32 | |||||
| D | 192 | H | 111 | L | 102 |
- The straight line distance heuristic used above is known to be an admissible heuristic. What does this mean and why is it important? [2]
