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,
- to structure your code in a modular way that reflects a natural
separation of purpose (generic agent architecture, specific problem
environment, generic search algorithms and specific agent
implementation) and promotes reuse, 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 wordChessPackages.pdf
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) contains
your agent(s) for this domain. It should be possible to replace this
with 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 search
functions that can be used by your agent. Everything in this package
should be independent of any particular problem domain, so that you
can reuse it in other search domains. You make the search specific to
a domain by providing implementations of the NodeInfo and State
interfaces.
Your tasks
Your tasks for this lab are as follows:
- Separate your classes from the previous lab into appropriate packages.
- 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 agents
will need to be passed the required "end word" by the RunPuzzle class
(perhaps in the constructor) and construct a suitable NodeInfo
instance accordingly.
Your agents should now be capable of solving the word puzzles (tho one agent may not terminate). Try
some different puzzles and verify that they succeed. What differences
do 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 problems that
require a large number of steps?
Use the currentTimeMillis() method in java.lang.System
(or similar) to write out the time taken by each node expansion. Plot
these using your favourite plotting package (eg matlab, gnuplot,
excel, etc). What is the trend as the size of the 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?
|
