Search Lab

Purpose:

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 apply search to the class project
  

The first part of this lab will be accomplished in an environment similar to the Capture the Flag environment used for the class project.  This environment will help you visualize how the searches occur.  The second part of this lab will have you use your search code in the BZFlag environment.  Write good modular code so that you can transfer your search structures between applications.

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

You'll also gain some experience in using a technique called probabilistic roadmaps.   We'll use the probabilistic roadmaps to create a "good enough" discretization of the world, plan a path through this discretization, and then use potential fields to follow the path.

For each of these search 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

For the probabilistic roadmaps, you should be able to talk and write intelligently about how you should sample the world to create a good path.

Description of the Programs used to Test and Visualize the Search Algorithms:

In previous semesters, various TAs and students worked to create a simple graphics world with trees, hills, agents, and flags. The objective is to have your agent search, from some arbitrary starting position, through the world until it finds the flag.  I know that you've programmed some search methods before, but to help increase your understanding and build your intuition about search, we have included simple animation that allows you to visualize the evolution of a search method and to see the path returned by a particular search method.  The animation is built around a two dimensional grid with agent and flag positions specified by (x,y) coordinates

The graphics world is made up of two packages: a World class, which does the animation and which calls your search routines, and a Search file, which contains "main" and simply initializes and calls the animation function.  (FYI, the animation is performed using OpenGL routines.)  You will fill out two classes that we have framed for you: an Agent class, that performs the search (and performs maintenance routines like managing search queues and requesting user input), and a Node class, that defines the domain of the search.  The World and Search classes as well as templates for the Agent and Node classes are available in zipped form here.  Please do not change what is pre-included in the Agent and Node classes as this is important for the graphics to work correctly.

From within the World  class, a call to agent->Search is made which will return a pointer to the path from the flag to your agent's starting position (this path is actually a linked list from the flag's node to the agent's node) and NULL if it fails.  In addition to finding a path, your program should also update the variable "totalnodes"; this variable is the total number of nodes that your search tries. A public function GetTotalNodes() should be part of your agent class; this function returns the value of the totalnodes variable, and is called by the World to determine the efficiency of your search. Your program will prompt the user to input a search method using something like the following:

Choose a search method from the following list:
[1]=DFS [2]=BFS [3]=UCS [4]=GS [5]=A*

For each search method, the World class will draw a yellow path from the agent to the flag and will report the number of nodes expanded, the amount of memory used, the path cost, the path length, and the amount of elapsed time used for your search (note that elapsed time will vary as a function of OS behavior and CPU workload --- remember this stuff from CS380?).

There are some functions defined in World.cpp and declared in World.h that you will probably find useful.  Note that these functions are not part of the World class, but are instead provided to act as an interface between your Agent code and the World code.  The functions include:

• GetPathCost(Node *node, Ops dir);  This function returns the cost of moving from the given node in the direction of dir. The datatype "Ops" is an enumerated type containing UP, DOWN, LEFT, and RIGHT. The path cost depends on the difference in altitude of the adjacent square in the specified direction and the current square. It also includes a factor that penalizes for going through dense trees.
• CanMoveDirection(Node *node, Ops dir); This function returns true if the agent can move from the current node->state to a new position by executing direction dir. See GetPathCost for a description of possible directions.
• IsGoalState(State state); This function returns true if state is the position of the flag. The "State" datatype is a structure of x and y positions. Since our world is a two-dimensional grid of x and y positions, State is sufficient to describe agent and flag positions.
• IsGoalState(Node *node); This function returns true if node->state is the position of the flag. This is helpful for determining if you have reached your goal.
• DrawLinkToParent(Node *node); This function draws a red line from the current node to its parent. It is useful for watching the search frontier expand (and helps to build intuition about the lab).

Make sure you build this with opengl32.lib and glut32.lib (glaux.lib can be excluded).  There are several .txt files included in the zip file.  These files represent different types of world that you can use to test your code.  When you begin the program, you will be asked to select which world you will use.

How to Apply Search in the BZFlag Environment:

What you should turn in:

When you are done, you should schedule a time to pass off the lab with the TAs.  They will post a sign up sheet outside of their offices.  After passing off the lab, send the lab write-up to cs470ta@cs.byu.edu.  During passoff, we will run your code on a world you have never seen (plus some of the worlds that you have seen), and give you a grade.  Please be assured that the unknown world will be big, so be careful using magic numbers to define search queue sizes, etc.  We will be grading on accuracy of path costs, correctness of number of nodes expanded, amount of time to complete search, and memory use.

The lab write-up should include

1. the amount of time you and your partner each spent on the lab,
2. a summary of what you learned,
3. a discussion of the heuristics you tried on your informed search,
4. a discussion of what happens when a non-admissible heuristic is used, and
5. a discussion of how you applied probabilistic roadmaps in the Capture the Flag world including
• good ways to sample the world -- nodes uniformly spaced, or at higher density near obstacles or in narrow corridors
• good ways to follow the path
• heuristics you used to select the number of nodes used
• heuristics you used to cull edges
  

This write-up can be either an email attachment or just regular ol' text in the body of your email.  Do, however, check for spelling, grammar, and readability.

Make it work with VC++ 2005:

The project should compile fine in VC++ 2003. If you plan to do your work with VC++ 2005, some extra work is required:

1. You might need some additional header files. You can find them here and here.
2. To get rid of the warnings, put in "#define _CRT_SECURE_NO_DEPRECATE 1" at the top of the World.cpp file.
3. To fix the errors in "error C2668: 'pow' : ambiguous call to overloaded function," simply change "pow (something, 2)" to "pow (something, 2.0)."

Lab 2 Passoff Sheet Posted:

You can download it here.