Due: Tuesday, January 27, 2004

- To practice good
*problem formulation*: appropriate states, actions, and state space - To implement, compare, and contrast
*uninformed search algorithms*

**Part (a)**should be completed before you write any code. You need to think about the problem the right way first. When it asks you to formulate precisely, be sure to include answers to the following in your writeup: what is an appropriate state here? What are appropriate actions? What are the initial state(s) and the goal state(s)? What is the goal test? What is the path cost? (hint: you're trying to get everybody across the river in as few "moves" as possible.) Then diagram the complete state space. Remember, you're trying to abstract away everything in the "real world" that does not contribute to the solving of the problem given the actors in the problem itself. Is your abstraction both*valid*and*useful*?**Part (b)**is the implementation itself, which should be a lot easier with the questions in Part (a) answered. Remember, you're building a**problem-solving agent**, so the solution (the output) is going to be a*sequence of actions*leading from the initial state to a goal state. For this assignment, your output could also take the form of a sequence of states starting with the initial state and ending with a goal state since it should be relatively easy to determine what action occurred based on the previous state and the next state.I want you to implement this twice using

different uninformed search algorithms. You must pick two*two*__optimal__algorithms, as "optimal" is defined in the text, but otherwise, the choice is up to you. Then compare and contrast the two search methods by displaying- the number of fringe nodes expanded by each algorithm
- the time it takes for your agent to find a solution under each algorithm (most programming languages provide a way for you to calculate execution time)

Discuss the results in your writeup.

**Part (c)**should be answered after your implementation is finished and working. That way, you can look at actual solutions to help you formulate a response.

- Remember, you can use any programming language you wish.
- Be sure to include a README file or something similar that lets me
know which
search algorithms you implemented and how to run
your agent with each algorithm.
- Be sure to tell me if your agent checks for repeated states or not.
(It's not mandatory
that you do.)
**Extra Credit:**make your agent modular enough so that checking for repeated states can be toggled on and off. Then run the experiments above to find the number of expanded nodes and the agent running time with the toggle on and then off. Is there a big difference? Why or why not?

- correct implementations of your search algorithms
- an optimal correct solution
- understanding of problem-formation and uninformed search as displayed in your writeup

I'm *not* looking for:

- mistakes or inefficiencies in the design of your code. This isn't a programming class, after all. However, if an error is so egregious that I catch it anyway without even looking for it, points may still be deducted.

Please hand in both an electronic copy of your project on BlackBoard and a paper copy.

Return to Project Index