Lab Sheet 1: Uninformed Search Algorithms The aims of this lab are: - to implement and test a range of uninformed search algorithms as special cases of the general search algorithm as discussed in lectures,
- to use these in agents to solve the the WordPuzzle game that you implemented in the previous lab, and
- to investigate the time and space performance of the uninformed search algorithms.
Provided Classes Begin by downloading the search package from the unit website. The search package archive provides the following: -
class Node.java A Node stores the problem state, a list of actions for recording the path from the start state (node) to this node, and the path cost. It also contains a clone method which can be used for generating successors or "children". -
class State.java The State class provides the state information in a Node. The State class is designed to be useful for searches. Therefore it has methods for getting the possible actions from that state, updating itself with an action, and cloning itself (which is in turn used by Node's clone method for generating successors). -
interface NodeInfo.java A class implementing the NodeInfo interface contains methods for determining the status of a node: in particular it can assign a value or utility, determine whether it represents a goal state, and determine whether the search should terminate at this node. Note: These tests could be incorporated directly within a search algorithm. However implementing them as a separate object that is passed as a parameter to a search algorithm allows the same search to be used on many different problems, simply by passing an appropriate NodeInfo instance. -
(abstract class) GeneralSearch.skeleton The body of this class has been provided for you with the exception of the search() method, which you are required to complete so that it implements the General Search Algorithm discussed in the Lecture Notes. You need not include an occurs check at this stage, but should check the terminal condition in this method. If the search completes successfully the method should return the goal node found (which includes the path, or "plan", to reach that goal) otherwise it should return null. The remaining methods select() and insert(Node node) should be defined in any implementing subclass. It is these methods that tailor the General Search to a particular search strategy. isTerminal(Node node) should be defined in the NodeInfo instance. Modular Package Structure The file contains a class diagram (and notes on the second page) showing the modular package structure that should be used for this and subsequent labs. The agent package is provided, and is generic to all agents and problem domains. The wordChess package is written by you and contains implementations of interfaces from agent defining this particular problem domain. It can be replaced by other problem domains. The package wordPlayer (or whatever you choose to call it) containsyour agent(s) for this domain. It should be possible to replace thiswith another package of agent(s) (yours or someone elses) without "breaking"anything in the above two packages. The package search is partly provided, and contains generic searchfunctions that can be used by your agent. Everything in this packageshould be independent of any particular problem domain, so that youcan reuse it in other search domains. You make the search specific toa domain by providing implementations of the NodeInfo and Stateinterfaces. Your tasks Your tasks for this lab are as follows: - Complete the search method of the General Search class as described above.
- Implement subclasses DepthFirstSearch, BreadthFirstSearch and DepthLimitedSearch of GeneralSearch that implement the corresponding search strategies covered in the Lecture Notes.
This should be achievable simply by implementing the select and insert methods in the subclass, and (for depth limited) the isTerminal method in the NodeInfo instance. - Develop WordSmith agents that use the various searches. The agentswill need to be passed the required "end word" by the RunPuzzle class(perhaps in the constructor) and construct a suitable NodeInfoinstance accordingly.
Your agents should now be capable of solving the word puzzles. Trysome different puzzles and verify that they succeed. What differencesdo you observe between the three agents in terms of performance? - Add an occurs check to your depth first agent (perhaps by modifying the isTerminal method in the NodeInfo instance that it uses). Do you see a noticable slowdown for long search paths?
Use the getTimeInMillis() method in java.util.Calendar(or similar) to write out the time taken by each node expansion. Plotthese using your favourite plotting package (eg matlab, gnuplot, excel, etc). What is the trend as the depth of search increases? - Add write statements to your code to output the maximum number of nodes stored during a search, and the length of the solution path found. Generate these figures for both breadth-first and depth-first searches for the same word problems, and plot the results.
Compare the performance of the two strategies in terms of space usage and quality of solution. Are they as you expected? |
