Problem 1 (4 points): For the following tasks determine the simplest kind of agent (from the four basic kinds) that could perform the task. Justify your answers.

The four basic kinds of agents are:

• Simple reflex
• Model-based reflex
• Goal-based
• Utility-based

1. Play to win a game of checkers against a human opponent.

A simple reflex agent would need a set of condition-action rules that give the right move for every possible board state, which would be impractically large. All of the information the agent needs is present on the board so a history of past moves, or a model-based reflex agent, is not needed. On the other hand this is a game, so we need to know about our goal state. Theoretically this is enough, but in reality the state space for checkers is too large for a brute force (a.k.a uninformed) search. So my answer is that the highest level agent, utility-based, that can assess the value of a particular move for a player is required for this problem.

2. Select the mode of transportation (walk, drive, fly) most appropriate for a human traveler based on the distance to a goal location.

Note that the question stated that the selection of the most appropriate mode of transportation would be based on the distance to a goal location. If this is all the information available to an agent (e.g. an online travel planner) then there is little use in implementing more than a simple reflex agent. Three rules like the following would suffice:

• if distance > 500 then fly
• if 2 < distance <= 500 then drive
• if distance <= 2 then walk

3. Find the shortest path (along paved roads) between two given U.S. cities.

The shortest path can be found by either best-first search or A*, depending on the level of map detail (interstates only versus all roads) required to connect the two cities. An agent using search is necessarily a goal-based agent.

4. Find news articles online that a user with a given set of interests is likely to read. Assume that users can select from a predetermined set of interests (e.g. sports, politics, and/or entertainment).

News websites can be crawled (a.k.a searched) for potential articles. Since the set of interests is known in advance, goal states (e.g. number of recurrances of sports-related keywords) can be defined without the need for a utility measure. Therefore my answer would be that a goal-based agent is required for this task as well.

Problem 2 (6 points): A solution to the problem requires the following:

• Reading the start configuration from a file.
• Creating a successor function.
• Creating a procedure to check if a state is a goal state.
• Implementing a search algorithm, A* search recommended.
• Creating a node structure (may or may not use parent pointers to form a tree) to facilitate search and solution generation.
• Creating a procedure for determining the cost or priority of each node.
• Creating a procedure to print the solution.

Again your solutions may differ from mine. Since optimality was optional, this time they were only checked for validity, not cost.

Extra credit: If your program found optimal solutions for at least four of the examples, then you earned one point of extra credit. If your program found optimal solutions for all of the examples, then you earned two points of extra credit. The extra credit was applied directly to this assignment.