Search
Lab
Overview
The purpose of
this lab is as follows:
- Review uninformed search
- Teach you about informed search
- Teach you about the memory and time requirements of various search methods.
- Help you start thinking about the class project
What you should learn
When you complete this lab, you should be an expert in the following search methods:
- Depth-first search
- Breadth-first search
- Uniform-cost search
- Greedy search
- A* search
For each of these methods, you
should be able to talk and write intelligently about the following:
- Memory requirements of
the search method
- Time requirements of
the search method
- Optimality of the
search method
- Completeness of the
search method
- Optimal efficiency of
the search method
- Admissible heuristics,
and what happens when admissibility is violated
And you learn more about Lejos, touch sensors, and visualizing a search with a real robot rather than a simulation.
Description
From an arbitrary position on the challenge table, the robot should
find its way back to base and onto the yellow dot that is inside the
black and gray rectangular area at the front of the base. It
should then trace its way back from the goal to its starting point.
The robot should execute the search using each one of the
algorithms listed above. The robot should report how many search
nodes were allocated, and how much memory was used, for each search.
If the robot runs into obstacles along the way, it should back up and
choose another action/direction. This means you may want to
experiment with the touch sensors and one or more bumpers. This is the
physical analog of asking an oracle if moving into some location is a
"legal move". In other words, if you bump inot something in a
particular location, a predicate like "canMove" (as in a simulation) is
obviously false.
To make things interesting, any square in your grid that contains the
head, the hand or the pizza costs 2 times the other areas to cross.
When we say "search" nodes, we mean the kind of search nodes as
described in your handout Chapter 3, which tracks a "parent node", an
action, and path cost up to that point, for example.
Notes
We are tempted to give the robot a map of the table, let it calculate
the best route for each search, and then follow the route. This is, of
course, what we would do in "real life" with planning software, or a
simulation. In this case, we resist that temptation, because we
want to experiment with having the robot do the work, and have fun in
the process.