Exercise 2: Search Agent
For this second exercise, you will again be implementing an agent that solves problems
in the MÆDEN environment.
As the focus of this assignment,
your agent can have internal state
and can use search to find paths to locations in the environment.
This is an individual project.
As always, I encourage you to talk to your peers about ideas or to me and to ask questions.
But the code you submit must be your own code.
Write an agent that solves problems in the MÆDEN environment.
Problems will involve only wall obstacles and will be guaranteed to have solutions.
These sub-tasks are intended to provide a reasonable development path
of increasing complexity and capability.
You may build upon your reactive agent if you wish,
or you may start with a blank slate.
- Search within the visual field.
That is, suppose your agent wants to move forward
but encounters a wall blocking its progress.
If there is a viable path through the visual field to a spot beyond the obstacle,
your search method should find the optimal (least number of moves) such path.
Your method should search for a path from the agent's current location
to any given location in the visual field.
- Subgoal generation.
Given the ability to find a path to an arbitrary location in the visual field,
your agent will need to generate its own subgoals
(e.g., when it encounters obstacles).
Once your agent establishes a new subgoal,
finds a path to it, and successfully follows the path,
it should continue with its original goal (e.g., getting to the food).
Whenever its progress is blocked,
the agent should establish an appropriate subgoal
and use the capability from the previous step
in order to continue making progress.
This version of your agent is not expected to solve every conceivable problem
although a solution will always exist.
- Option: Searching through mental maps.
As your agent moves about (following its nose for example),
it encounters more and more of the world.
Sometimes, an agent must rely on a memory of where it has previously been
in order to solve more challenging problems.
For example, perhaps the agent cannot get around an obstacle using search through the visual field.
You may choose to augment your agent
with the ability to construct mental maps of all the places it has observed.
Once the agent is constructing maps of the explored portion of the environment,
either generalize your search method from above or provide an additional search method
so as to search for paths to an arbitrary location in the mental map.
Having found such a path, your agent should follow it
and then continue with what it was doing (e.g., following its nose).
- Putting everything together.
A recommended approach is for your agent to use a reactive problem-solving strategy (e.g., following its nose)
until it encounters an obstacle.
At that point, it tries to find a path through the visual field.
If that fails, it resorts to searching through the mental map constructed so far.
Finally (if searching through the mental map will not traverse unknown territory),
the agent should move in an exploratory mode in the hopes that an expanded mental map will yield progress.
Your code should be documented thoroughly.
Do not neglect to include an acknowledgments header within your submission.
You may use a language of your choice.
However, I must be able to run your system without
an IDE or installing any specialized libraries.
FYI, I have Racket, Common Lisp, Ruby, Python, Java, and C++ on my machine.
If you want to use something else, talk to me before investing effort on the above tasks.
If you need assistance connecting to MÆDEN via the socket layer,
ask me for help.
You should write a one-page report of your activities and findings associated with this assignment.
Your report should serve as a stand-alone document;
thus, it should describe the problem or focus,
the approach that you employed,
and an indication of how well it performed.
For example, you might describe the worlds you used (and/or created) to test your agent.
If you chose to implement mental maps (described in your activities),
you should report how that improved your agent's performance in terms of worlds completed.
In any case, you should compare your search agent to your reactive agent.
You are welcome to include figures if you think they contribute to the report;
however, make sure your picture really is worth a thousand words.
You should format your one-page report
using a template (either LaTeX or Word) found at the
ACM SIG Proceedings Templates page.
Your affiliation should be “Westmont”;
Whether you use LaTeX or Word,
you should use the template with only the following modifications:
- Remove the first four sections
(Abstract, Categories and Subject Descriptors, General Terms, and Keywords).
- Remove the blank text box at the bottom of the left column
that is reserved for a copyright notice.
- Do not include your phone number in the author section.
When you have completed your report and its formatting,
generate a pdf document to be included in your final submission.
Submit only gzipped tar files.
Name your gzipped tar file with your Westmont emailname and "P2" (no spaces);
for example, someone named Eva Bailey might create a folder called
"evabaileyP2" or "ebaileyP2".
Make sure that inside that folder you have the following:
- documented source file(s) for your agent;
- instructions for loading and running your agent;
this would be a logical location to provide any acknowledgments that are appropriate;
- a one-page pdf report describing your work on this assignment.
Finally, submit the archive containing these on Eureka