Consider the vacuum-cleaning problem outlined below: Here we have a vacuum-clean

Question

Consider the vacuum-cleaning problem outlined below:

Here we have a vacuum-cleaning agent that can sense the environment and perform actions to move around and vacuum-clean dirty squares.

We make the following assumptions:

• We assume a 3 by 3 grid world known to the agent. The environment is fully observable: the percepts give complete information about the Dirty/Clean status of every square and the agent’s location.

The environment is deterministic: A clean square remains clean and a dirty square remains dirty unless the agent cleans it up.

The actions available for the agent are: Left, Right, Up, Down, Suck. Each action takes place in one time "step".

The actions and percepts are perfectly reliable.

Each of the actions will incur a penalty of 1 point.

The agent will get a penalty of -2 points per dirty square per time step,

The agent’s performance is measured by the sum of negative points received on reaching a state with all squares in the environment being "Clean". As usual, a rational agent should max- imize its performance score.

(a) Define the vacuum-cleaning problem as a state-space search problem. Specify the states, actions, the transition model, and the goal state(s). The initial state could be any of the states in the state space.

You should also specify a cost function COST (n, a, n) > 0, which defines the cost of one step transition from node n to node n by applying action a, such that the cost of a path in the search tree should be exactly the absolute value of the sum of penalty points due to dirty square(s) and moves.

(Hint: COST (n, a, n) should be related to w, the number of dirty squares at the state s for noden, and related to the fact whether the action a is "Suck", and the current square is dirty or not).

(b) Which of the algorithms defined in Chapter 3 would be appropriate for this problem? Should the algorithm use tree search or graph search?

(c) You are asked to define an admissible (hopefully also consistent) heuristic function h to be used with the A* algorithm for solving the problem of searching for an optimal sequence of moves that maximize the agent’s performance score.
(Hint: your h(n) should be related to w, the number of dirty squares at the state for node n, andd, the shortest distance between the current square and a dirty square, etc.)

You should also define an alternative admissible heuristic function h2 (which is different fromh), such that h2(n) is always lower than or equal to h(n) for any node n, namely h dominatesh2.

(d) Show the first level of a search tree starting from the initial state in which the top 3 squares, and the 3 right-most squares are dirty, and the agent is at the left bottom corner square. The frontier nodes at the first level should consist of three nodes, one is obtained from the initial state (root node) by the action "Up", one is obtained by the action "Right", and one is obtained by the action "Suck". Write the action as well as the edge cost along each edge from the root node to a frontier node. Then write down below each frontier node n: g(n), h(n) and h2(n).

3:26 sl moodle3.Isu.edu c) Questions 3.2a) and 3.2Hb) in the les book 40%]. Consider the vaceumcleaning probliem olinod below around and vacum ckan dirty sqars We make the ellowing assumpions We assame a 3 by 3 grid world knows to the apcnt The viybe the location dirty unless the apent clcans i u in one tinesp Each of the actions wi incur a penalty of- po The actions available for the apn ane Le,Rigp Sk Eachaston takes place The actions and pencpts are perfectly nelable The apent's perfoemance is mcawared by the sum of sepbe poimss secciod on reaching ue with all squanes in eemionnent being Oanr. AsuuLiliul ag mine its parformance score. should tus- Define the vacuum-clcaning problem as a state-gace sh poiam Specity the saes The initialuld be any of the states actions, the transition model, and the goal stat in the state space iu should also specify a cost fanction cos7ta,a,x)>e,wih dindecast of one dep ach tre should be exactly the absolute (Hint: COST", a,"p should be related to w, value of the m of plty ds to dirty tu her efátyqure, theutifr nede is "Sock". nd omat "purendirty or tati ,and related tothe t whether the action b) Which of the algorithres defined in Chapcr3 would be appeoperin or thisbe Should the algorithmt scanch or graph scanch You are askod to ine an admissible (hopefully also cesis nction à to be used with the ..d. algorithm for solving the problem of sodeg tr and-sequence of moves that maiie the agent's perfomance scone (Hint: your A(a> should be relaledtow,the m.ierofdrty sp esatthe 1t fe mka.and d, the shetest dislance betwecn the current sqeare and a dity sa You should alse defise an ahemative adisble heurisilc fuionwich isfferens o fd) Show the first level ef a search tee statig hem the mtul .k n which top 3 spares. evel shouild coesisn ef sune (oot sode) by the action one is oained by the aion "Rigl,and one is obained Hons 20 Question 330 in ext hook

Explanation / Answer

a) Agent without state information cannot be completely rational due to the obvious reason (Since it doesn't know initially which square has more dirt distribution).

PROGRAM Agent:

START

PROCEDURE CheckAndClean :

IF Status Of Current Square is Dirty

THEN CALL Suck;

END IF

END PROCEDURE

CALL CheckAndClean;

IF location is A

THEN

CALL Right;

CALL CheckAndClean;

CALL Right;

CALL CheckAndClean;

END IF

ELSE IF location is B

THEN

CALL CheckAndClean;

CALL Left;

CALL CheckAndClean;

CALL Right;

CALL Right;

CALL CheckAndClean;

END IF

ELSE IF location is C

THEN

CALL CheckAndClean;

CALL Left;

CALL CheckAndClean;

CALL Left;

CALL CheckAndClean;

END IF

END

b) Yes, it can be perfectly rational if it has the capability to maintain states.

PROGRAM RationalAgent:

START

PROCEDURE CheckAndClean :

IF Status Of Current Square is Dirty

THEN CALL Suck;

END IF

END PROCEDURE

CALL CheckAndClean;

IF the location of the square is A

IF Square B is Dirty // Use a mapping table.

THEN

CALL Right;

CALL Suck;

END IF

IF Square C is Dirty

THEN

CALL Right;

CALL Suck;

END IF

END IF

IF the location of the square is B

IF Square A is Dirty

THEN

CALL LEFT;

CALL Suck;

IF Square C is Dirty

THEN

CALL Right;

CALL Right;

CALL Suck;

END IF

END IF

ELSE IF Square C is Dirty

THEN

CALL Right;

CALL Suck;

END IF

END IF

IF the location of the squre is C

IF Square B is Dirty

THEN

CALL LEFT;

CALL Suck;

IF Square A is Dirty

THEN

CALL Left;

CALL Suck;

END IF

END IF

ELSE IF Square A is Dirty

THEN

CALL Left;

CALL Left;

CALL Suck;

END IF

END IF

END

c) Yes. Equivalent  to b, only difference is that it will get the status dynamically every single time. Pseudocode also remains same as B.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.