The V-World Workbook

Donald Nute
Artificial Intelligence Center
The University of Georgia
Athens, GA 30605
donald@nute.ws

Copyright 2005 Donald Nute

<Previous> <Workbook Home Page> <Next>


Exercise 5: Search Methods

To improve bumble's performance significantly, he needs to be able to remember where he has seen objects in his world and he needs to be able to find his way back to the resources he needs to survive. In later exercises, we will develop a version of Bumble that explores his world systematically and creates a map. But first, we will look at how Bumble can use a map to find a path to some object in his world.

Start WIN-PROLOG and open the file search.pl. At the bottom of this file, you will find clauses for the predicate mymap/3. Each clause mymap(X,Y,Object)includes an X and a Y coordinate, and the durable object (if any) located at those coordinates in test7.vw. The square that corresponds to the coordinates (0,0) marks the spot where an agent finds itself when it is loaded into test7.vw. All other coordinates are marked off from this first location of the agent.

The predicate search/2 defines a general search algorithm in Prolog. search/2 is designed to search the nodes in a search space until it finds a solution to the search space problem. At any given time, search/2 is passed a list of nodes that have been reached during the search as its first argument. In the first clause for search/2, the first node in the list is tested to see if it is a solution to the problem. If it is, then this node is unified with the second argument for search/2. Otherwise, the first node in the list is replaced by all the nodes below it in the search space and the search continues.

We get different kinds of search depending on how new nodes are inserted into the list of nodes yet to be processed. Blind search, whether depth-first, depth-first, or iterative deepening, does this without taking into account any information about the domain. Heuristic search methods like best-first or A* use domain information to determine the order new nodes will be explored.

We will use search methods together with our map of test7 to find paths from any location to the location of any kind of object in this virtual world.

The way new nodes are generated during search depends on the domain and determines the search space that corresponds to our problem. In this case, each node represents a path in our virtual world, and new nodes will be paths which extend a previous path by a single step. We can only add a new location to a path if that location is empty (marked on the map with o) or if it is occupied by some object that the agent can either pick up or consume (recorded in clauses for the predicate can_remove/1.) We have used a little bit of domain knowledge in defining generate_new_nodes/2 since we do not allow paths which loop back upon themselves.

For depth-first search, the new nodes are inserted at the beginning of the list of nodes to be processed. For breadth-first search, they are inserted at the end of the list. For heuristic search, we must calculate the estimated goodness of each node and use that to decide where each node goes in the list. In our Prolog code, we assert depth_first/0 or breadth_first/0 to tell insert_nodes/2 which method to use.

When we call find_path(+SearchType,+Goal,+Start,-Path), we replace SearchType with depth_first or breadth_first to tell Prolog which search method to use. Goal is replaced by tree, cross, or any other object we want to find. Start is replaced by a list of initial paths [[(X,Y)]] where (X,Y) are the coordinates of the agent's current location. If the routine is success, Path is matched to a path from the agent's current location to the location of a goal item.

Compute the actual cost of any path by adding 10 for each horizontal or lateral move and 14 for each diagonal move (the strength it would cost Bumble to follow the path.) Come up with a reasonable heuristic for computing the least additional cost it would take to extend any path to the goal location nearest to the current end of the path. Now when we generate new nodes in our search, we will include an extra element at the head of the list of moves: a number representing either the actual cost of the path (g), the estimated cost of completing the path (h), or a combination of the two (g + h). We can then use this value to sort any set of nodes (paths). Use these ideas to define new clauses for generate_new_nodes/2 and insert_nodes/2 that will implement uniform cost search, best first search, and A* search. These new clauses should have uniform_cost, best_first, and a_star as conditions. When you are finished, you should be able to use find_path/4 to perform any of these three kinds of search by providing the right value for SearchType.

5.1 Try out the different search methods. What are your observations. Which will you use in later versions of Bumble? Why?


Last revised 9/21/2005.