0 votes
in Artificial Intelligence by

Suppose that an agent is in a 3×3 maze environment like the one shown in Figure 4.19. The agent knowsthat its initial location is (1,1), that the goal is at (3,3), and that the actions Up, Down, Left , Right have their usual effects unless blocked by a wall. The agent does not know where the internal walls are. In any given state, the agent perceives the set of legal actions; it can also tell whether the state is one it has visited before.

a. Explain how this online search problem can be viewed as an offline search in belief-state space, where the initial belief state includes all possible environment configurations. How large is the initial belief state? How large is the space of belief states?

b. How many distinct percepts are possible in the initial state?

c. Describe the first few branches of a contingency plan for this problem. How large (roughly) is the complete plan?

Notice that this contingency plan is a solution for every possible environment fitting the given description. Therefore, interleaving of search and execution is not strictly necessary even in unknown environments.


1 Answer

0 votes

a) In online search, an agent interleaves the computation with action, first an action is taken and then the next action is computed.

In online search problem, assume a deterministic, fully observable environment. The agent knows:

• Action(s)- the list of actions which are followed to reach from the source state to the goal state.

• Step-cost function-it involves the cost involved in executing each action.

• Goal Test

The main objective is to reach the goal state while minimizing the cost and the cost is the total path cost of the path travelled by the agent.

The online search problem can be viewed as an offline search space. The belief state is a set of all possible wall configurations. There are 12 possible locations for the internal walls so there are image = 4096 configurations.

The agent can be in any of 9 different squares, so there are image  belief states.

After few percepts and actions, the agent learns about the locations of new wall. The huge space can be represented in compact form.

So, the initial belief states are image, the space of belief states is image

b) The distinct percepts which are possible in the initial state are: LEFT, RIGHT, UP and DOWN. The percepts LEFT and DOWN are illegal but the states UP and DOWN can be legal or not.

c) The first few branches of a contingency plan for this problem are as follows:

Picture 2

The agent does not know about the walls and perceives all adjacent walls. The diagram starts with 4 possible states. The agent is aware that which action is legal and there are up to 3 binary percepts, so 8 states can be formed.

The complete plan size is image  because the longest plan when the goal state can be reached is 13.

Related questions

Welcome to CPEN Talk
Solution-oriented students of computer engineering on one platform to get you that


If you try to kill -9 Chuck Norris's programs, it backfires.