Artificial Intelligence Homework 3

Ed Smart

CSC 375

Homework 3

3.1 Explain why problem formulation must follow goal formulation.

Problem formulation must follow goal formulation because goal formulation narrows the focus of the problem to an extent that it may be solved within a reasonable amount of time. If a problem is formed without a goal, depending on the problem, an agent may have a near infinite number of decisions or options to choose from and must determine which is the most beneficial to it.

For example, if an agent is sitting at a desk with a computer and a textbook but has no specific goal formulated, what will it do? It may use the computer to surf the web or play video games, it may read random pages or sections of the textbook, it may go to sleep, or it may just get up and go outside, to name a few of the options. If it has a goal, however, to complete a specific homework assignment, such as chapter 6, problems 1 to 10, from the textbook using the computer, the agent’s scope of possible action choices narrows greatly. With this goal, any action that does not result in the completion of problems 1 to 10 from chapter 6 of the textbook using the computer is immediately dismissed. This way, the only courses of action left to choose from are the ones that result in the agent’s assignment being completed.

Without the formulation of a goal preceding the formulation of a problem, the problem typically becomes much more difficult to find a solution to, as there is nothing to point the agent in the proper direction, so to speak. As taken verbatim from page 65 of the textbook, “Goals help organize behavior by limiting the objectives that the agent is trying to achieve and hence the actions it needs to consider.”

3.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, south, east, or west. You can direct the robot to move a certain distance, although it will stop before hitting a wall.

a. Formulate this problem. How large is the state space?

The initial state of this problem is the center of the maze, where the robot starts and is facing north. The robot is capable of facing north, south east, or west and can move a certain distance as directed by the user controlling it. It will stop, however, if it comes too close to a wall, in order to avoid hitting it. Since the robot can move a certain distance and is capable of facing north, south, east, or west, it is able to move a certain distance north, south, east, or west. Given these options, with any direction the robot moves in, it will either stop upon reaching a wall to avoid hitting it, or progress further through the maze. The robot has a total of five possible actions; face north, face south, face east, face west, and move. It can move in the direction it is facing unless it reaches a wall. In which case, it will stop before hitting the wall. So, there are two possible outcomes for any action is takes; the robot can either move in the direction it is facing or it cannot because it has reached a wall. Since there are 4 possible directions that the robot can move in, for a location of size n, there are 4n possible world states.

Problem Formulation    (using the problem formulation format found here http://w5.cs.uni-saarland.de/teaching/ss12/ki/slides/pre-handouts/ai03-search-pre-handout-4up.pdf)

Initial state: Middle of the maze, facing north. Following the textbook’s format, (In (start), face(n))

Successor function: (In (state), face(x))                           //x = n, s, e, or w

State space: n possible locations, 4 possible directions to move in, so there are 4n possible world states

Actions: face north, face south, face east, face west, move

Goal: reach any location outside of the maze

b. In navigating a maze, the only place we need to turn is at the intersection of two or more corridors. Reformulate the problem using this observation. How large is the state space now?

If the intersections of the corridors make up some part of the n locations that the state consists of (n – i), and there still only 2 possible outcomes for an action performed at a state (2(n – i)), but the 4 different direction-facing actions that the robot can do are now determined only at intersections (meaning the 4n in the previously mentioned state space now becomes 4i), the new state space is 4i + 2(n – i).

To clarify:

Since the robot only turns at the locations of intersections of corridors (which I’ve represented with i) instead of at any location in the state (represented by n), the state space, which was 4n in part a, now becomes 4i.

Furthermore, since the intersections are obviously part of the locations of the state, i is contained within n. And since the robot performs its direction changes at only i, it must be moving at all other n except for i, which is where (n – i) comes from. Finally, the only 2 possible outcomes of the robot’s movement (move forward or stop upon reaching a wall) are included, making the total state space 4i + 2(n – i).

c. From each point in the maze, we can move in any of the four directions until we reach a turning point, and this is the only action we need to do. Reformulate the problem using these actions. Do we need to keep track of the robot’s orientation now?

If the robot now has the ability to move on its own in any direction and the only action that needs to be performed is now turning, then the 4 and the 2(n-i) previously included in the state space can be removed. This is due to the fact that the 4 represented the 4 directions in which the robot is capable of moving, while the 2(n-i) represented the locations within the state that the robot moved and the possible outcomes of those movements, all of which have been excluded in this part of the problem. Thus, all that is left to represent the state space is i. Another byproduct of all of these actions being excluded is that we do not need to keep track of the robot’s orientation now, since it performs all of its actions without the user’s control.

d. In our initial description of the problem we already abstracted from the real world, restricting actions and removing details. List three such simplifications we made.

The first missing detail I noticed was the lack of information about the robot’s design, considering that it can apparently turn, but cannot move diagonally at all, only in a straight line in 4 different directions. There was also a lack of detail about the maze itself. If the maze has any dead ends, the robot would be stuck due to the fact that it can only turn at intersections. This problem also assumes that the robot’s sensors work flawlessly 100% of the time and the robot never hits a wall.