Intelligent System

Part – A
1. There are well-known classes of problems that are intractably difficult for computers, and other classes that are provably undecidable. Does this mean AI is impossible? (2) No, it means that AI systems should avoid trying to solve intractable problems. Usually this means they can only approximate optimal behavior. Notice that even humans do not solve NP- complete problems. Sometimes they are good at solving specific instances with a lot of structure , perhaps with the aid of background knowledge. AI systems should attempt to do the same

2. “A rational agent need not be omniscient, but it has to be autonomous”. Do you agree with the statement? Justify your answer. (2) In real world scenario, knowing the actual outcome of the action and acting accordingly is impossible. Rationality depends on the percept sequence to date and hence omniscience is not compulsory. As a rational agent should learn what it can, so that it can compensate partial/incorrect prior knowledge, it must depend on its own percepts rather than prior knowledge supplied by the designer. Hence it should be autonomous.

3. For each of the following activities, give a PEAS description of the task environment a) Playing soccer.
Performance measure: To play, make goals and win the game.
Environment: Soccer field, teammates and opponents, referee, audience. Actuator: Navigator, legs of robot, view detector for robot. Sensors: Camera, communicators, sensors.(0.5)

b) Exploring the subsurface oceans of Titan
Performance measure: Surface area mapped, extraterrestrial life found Environment: subsurface oceans of Titan
Actuator: steering, accelerator, break, probe arm,
Sensors: camera, sonar, probe sensors. (0.5)

c) Shopping for used AI books on the Internet
Performance measure: Cost of book, quality/relevance/correct edition
Environment: Internet’s used book shops.
Actuator: key entry, cursor
Sensors: website interfaces, browser(0.5)

d) Playing a tennis match
Performance measure: Win/Lose
Environment: Tennis court
Actuator: Tennis racquet, Legs
Sensors: Eyes, Ears.(0.5)

4. Are reflex actions (such as moving your hand away from a hot stove) rational? Are they intelligent?(2) Yes, they are rational, because slower, deliberate actions would tend to result in more damage to the hand. If “intelligence” means “applying knowledge” or “using thought and reasoning” then it does not require intelligence to make a reflex action.

5. Does a finite state space always lead to a finite search tree? If not,Give an example where a finite state space leads to an infinite search tree. How could you avoid an infinite tree?(2) No finite search space does not always lead to a finite search tree. Consider a state space with two states, both of which have actions that lead to the other. This yields a infinite search tree , because we can go back and forth many number of times. However if the search tree is a finite search tree or a finite DAG, then there can be no loops, and the search tree is finite. 6.

i. Consider a state space where states are describes by integers. The initial state is 1 and the successor function for state n returns two states 2n and 2n+1.Draw the portion of the state space that contains the initial state and all states that can be reached from the initial state down to depth 3.(2)

ii. Let the goal state be 11. List the order in which nodes are visited by breadth-first search, depth-first search limited to depth 3, and iterative deepening search. BFS: 12 3 4 5 6 7 8 9 10 11

DLS: 1 2 4 8 9 5 10 11
IDFS: 1; 1 2 3;1 2 4 5 3 6 7;1 2 4 8 9 5 10 11( 2+2+2)
iii. Would backward search be appropriate for this problem? Describe how it would work? (2) It is appropriate, since there is only one successor of n in the reverse direction, this helps to focus the search.

Part – B
7.
a) Consider a vacuum cleaner agent is in an environment, in which the geography of the environment (its extent, boundaries and obstacles) and the initial dirt distribution is unknown. Assume the agent can do go UP, Down, Left and Right actions. I. Can a simple reflex agent be perfectly rational for this environment? Explain. No . Because the agent does not know the geography. It perceive only the location and the dirt. It will get stuck forever against a wall when it tries to move in a direction that is blocked.(2) II. Can a simple reflex agent with a randomized agent function outperform a simple reflex agent? Explain. When its function is randomized, it may get a chance to get away from the blocked direction and move in another direction

(3)

b) Write the agent program for model-based reflex agent. Describe its advantage over simple reflex agent A model-based reflex agent program

function reflect_agent_model(percept) returns an action
static: state, rules, action
state=UPDATE_STATE(state, action, percept) rule=RULE_MATCH (state, rules)
action=RULE_ACTION(rule)
return action(2)

Simple reflex agent is very simple, it has very limited knowledge. This works if the current percept is sufficient to decide the action, which makes
this agent to work only in the fully observable environment. In partially observable environment where there is some unobserved data, the simple reflex agent cannot decide on the action. However, the model based reflex agent, the current percept is combined with the old internal state to generate the updated description of the current state. It helps the agent to interpret the new percept in the light of existing knowledge about the state, thus the agent gets the unobserved data of the environment and decide the action.(3)

8. The missionaries and cannibals problem is as follows. Three missionaries and three cannibals are on one side of a river, along with a boat. The boat can hold one or two people (and obviously cannot be paddled to the other side of the river with zero people in it). The goal is to get everyone to the other side, without ever leaving a group of missionaries outnumbered by cannibals. Your task is to formulate this as a search problem a) Define a state representation(2)

There are many possibilities. One example is:
Represent the missionaries by M and the cannibals by C. Let the boat be B. Each state can be represented by the items on each side, e.g. Side1 {M, M, C, C}, Side2 {M, C, B}. b) Give the initial and goal states in this representation.(2)

Initial state: Side1 {M, M, M, C, C, C, B}, Side2 {} Goal state: Side1 {}, Side2 {M, M, M, C, C, C, B}
c) Define the successor function.(2)
A set of missionaries and/or cannibals (call them Move) can be moved from Sidea to Sideb if: * The boat is on Sidea.
* The set Move consists of 1 or 2 people that are on Sidea. * The number of missionaries in the set formed by subtracting Move from Sidea is 0 or it is * Greater than or equal to the number of cannibals.

* The number of missionaries in the set formed by adding Move to Sideb is 0 or it is greater than or equal to the number of cannibals.

d) What is the cost function in your representation?(1) Each move has unit cost.

e) What is the total number of reachable states?(3)
16
1. Side1{M,M,M,C,C,C,B}, Side2{}
2. Side1{}, Side2{M,M,M,C,C,C,B}
3. Side1{M,M,M,C,C,B}, Side2{C}
4. Side1{M,M,M,C,C}, Side2{C,B}
5. Side1{M,M,M,C,B}, Side2{C,C}
6. Side1{M,M,M,C}, Side2{C,C,B}
7. Side1{M,M,C,C,B}, Side2{M,C}
8. Side1{M,M,C,C}, Side2{M,C,B}
9. Side1{M,C,B}, Side2{M,M,C,C}
10. Side1{M,C}, Side2{M,M,C,C,B}
11. Side1{C,C,C,B}, Side2{M,M,M}
12. Side1{C}, Side2{M,M,M,C,C,B}
13. Side1{C,C,B}, Side2{M,M,M,C}
14. Side1{C,C,B}, Side2{M,M,M,C}
15. Side1{M,M,M}, Side2{C,C,C,B}
16. Side1{C,B}, Side2{M,M,M,C,

9. Consider the problem of finding the shortest path between two points on a plane that has convex polygonal obstacles as shown in Figure1. This is an idealization of the problem that a robot has to solve to navigate in a crowded environment.

Define the necessary functions to implement the search problem, including an ACTIONS function that takes a vertex as input and returns a set of vectors, each of which maps the current vertex to one of the vertices that can be reached in a straight line. Use the straight-line distance for the heuristic function. Develop the algorithm for same.

Introduce suitable map representations
* Graph
* Topological Map
* Occupancy grid map
* Adjacency or incidence list/matrix.
* Any one methodology can use(5)
Can use any heuristically informed search like
Heuristic DFS or BFS
A*, D*, Rapidly-Exploring Random Trees