CS 63 Course Project

Building an Intelligent Agent for Search and Rescue

 

Project Description

 

Downloads

SearchAndRescue, version 0.05

There will likely be updated versions released over the next few weeks that will contain bug fixes and new gridworlds. I will send e-mail and post updates here when they are available.

This current version of the simulator does not contain the longsense and shortsense options. In this version, the results of the longsense action are always available, and shortsense is simply called sense. Also, the long-range sensors identify a rectangular region; in the next version, it will likely be a circular region.

 

Resources

The Gridworld Map Editor

 

Change Log

Version 0.05

Stalled or crashed agents may potentially disrup the simulator. To compensate for this, if an agent doesn't return an action for more than 5 timesteps (noops are not considered actions), then the simulation will ignore that agent for the purposes of determining whether to step the simulation. Whether the action fails or succeeds is irrelevant -- even an action that fails is acceptable. The easiest way to avoid this problem is simply to have your agent return an action every timestep of the simulation.

 

Instructions for using Version 0.05

The simulator, lisp client, and gridworld display provide a solid interface for you to begin building your intelligent agent in lisp. It may still contain some bugs (there are some Known Issues with this release), so if you encounter one, please send Eric an e-mail to let him know. The simulator and display are both based in Java 1.5, so you will need java installed on the computer you use for development.

To use the distribution, download and uncompress the archive available under Downloads. For all of these commands to work, you must be in the top level folder for the files you just uncompressed. The software must be started in this order: display, simulation controller, and then any clients. Each component runs in its own terminal, so you will need to open three terminals. Below are instructions for starting each component.

Try not to modify any files included in the releases. This way, you can just unzip new releases directly into the same directory, overwriting older versions of the files. If you do this, be certain to backup your previous version. If you do need to modify any files, be certain to store copies outside of the directory so they aren't accidentally overwritten.

Note to Linux/Mac users: To make the example command lines below work on your operating system, don't put the classpath specification in quotes and use a colon to separate the jar files instead of the semicolon.

 

Starting the display

The display requires only a port argument, and you can optionally specify the size of the display (although, it is really unnecessary, as you can resize the window). Here is an example command that will start the display on port 2000:

java -Djava.security.policy=searchandrescue.policy -classpath SearchAndRescue.jar searchandrescue.display.Display 2000

The display and controller connect using java RMI, which requires a security policy defined in the file searchandrescue.policy. If you need to modify this file, please let me know the changes you needed to make so I can try and make a policy file which works on everyone's system. I've only tested it with all components running on one machine; later versions will support running each component on a different computer.

Starting the simulation controller

The controller requires various configuration parameters, a port to listen on for clients, and a link to the display. Here is an example command that will start the controller on port 3000 using a simple gridworld with one client running for 50 timesteps (and processing the initial knowledge for 30 seconds) with a link to the display:

java -Djava.security.policy=searchandrescue.policy -classpath "SearchAndRescue.jar;jdom.jar;weka.jar" searchandrescue.Controller 3000 gridworlds/simple.gw 1 50 30 5 localhost 2000

The disaster severity is the parameter that comes before the "localhost." It ranges from 0-10 and controls the level of injuries of the victims. 10 results in an insane amount of injuries (I doubt we'll ever go above 6 or 7 in the competition), and 0 corresponds to a very slight disaster which may minorly injure some victims.

Starting the client

I've provided a manual agent that allows you to manually navigate around the gridworld. It requires a link to the simulator and the name of your agent. Here is an example command that will start the client from lisp.

(cd "lispclient") ; changes into the lispclient directory

(load "load-manual-agent.lisp") ; loads the manual agent

(main "localhost" 3000 "LispClient")

If you wish to have a custom graphic displayed for your agent, include the filename of that graphic file as the optional fourth argument to main. The display should support a number of image formats, but be sure to test your image to make certain that it works.

(main "localhost" 3000 "LispClient" "image.bmp")

There is also a java version of the manual client available as searchandrescue.ManualClient. They are very very similar and require the same arguments (including the optional filename of the image for the agent). Here is an example starting the java manual client.

java -classpath "SearchAndRescue.jar;jdom.jar" searchandrescue.ManualClient localhost 3000 JavaClient

 

Instructions for Implementing your Agent in LISP

* Note: instructions for implementing your agent in Java will be available in a few weeks with the release of the java client library. However, they will be roughly analogous, and involve completing similar abstract functions.

To implement your intelligent agent in lisp, follow these steps.

  1. Copy the load-manual-agent.lisp file to another filename. Currently, it loads all the required files for the manual agent. You will modify this copy to load the lisp source files for your own agent. Use your modified copy in place of the load-manual-agent.lisp file in the instructions above to start your own agent.
  2. Write a Lisp source file that provides implementations for the following lisp functions:

    initialize() This function will be called upon registering the agent with the simulator. Note that it no longer includes any arguments, unlike the definition of this function in the project description. All of the same information is now available to your agent via global lisp parameters, simplifying your job of implementation. The return value does not matter.

    choose-action(perceptions) This function will be called during each perception-response cycle. It takes in a perceptions data structure which represents the agent's current perceptions. It must return an action data structure.

    process-result(score) This function will be called at the end of the simulation to inform the agent of its score. You do not have to override this function if your agent does not need performance feedback. It takes in a number; the return value does not matter.

  3. Do not modify any of the other files -- these might get overwritten or changed in future releases. If you absolutely must provide a new version of a function or data structure, you can override the previous definition by redefining the function or data structure and then having Lisp load it after the file that contains the original definition. However, I do not recommend doing this. Instead, you should consider simply writing your own function with a different name.

You can look at the manual-agent.lisp file if you would like to see an example implementation of these functions. Skeleton versions of these functions are also provided in the client.lisp file.

 

Search and Rescue API for Lisp

This section describes the programming interface that your code will use to interact with various provided Lisp data structures. These are all contained in the utilities.lisp file, so that is the only source code file you should need to read in detail.

 

Data Structures and Associated Accessor Functions

This section provides an overview of the data structures defined in utilities.lisp. Additionally, many of the data structures have additional accessor functions that allow you to access structure members without calling the built-in accessors. For example, you can call the coordinates() function on a cell, an object, or an agent and Lisp will return the coordinates of the appropriate data structure.

There is also a global parameter *current_time* which is kept up-to-date with the current simulation timestep.

The Initial Knowledge and the Gridworld Map

Before the simulation starts, the simulator sends the client initial information about the gridworld, including the location of walls and the various exits. The client code automatically processes this information into a set of data structures which your code can access. After it does this processing, it calls the initialize() function.

The wall locations and the size of the gridworld are efficiently represented as adjacency lists, making your implementation simpler. This allows you immediately know which coordinates you can move to from a location. The set of walls restricts movement in the gridworld, so this is a representation of the gridworld as a graph, with the vertices being coordinates and the edges providing coordinates that your agent can move between. The adjacency lists are stored in the global hash-table *adjacent_coordinates*, which maps from a given coordinates data structure to a list of coordinates which are adjacent to it. This adjacency information DOES NOT take into account coordinates which are blocked by objects in the gridworld. The following utility functions are provided for interacting with the map:

Locations on the gridworld can also have various markers (which are represented as strings) which identify specific locations. Initially, the only marked coordinates are the exits. These coordinates are marked using the string "EXIT" by the simulator. During the course of the simulation, you can add your own markers to specific locations (for example, your agent could mark locations which are doorways). Markers are stored in the global hash-table *marked_coordinates*. The following utility functions allow you to interact with the map markers:

Interacting with the Agent's Perceptions

The choose-action(perceptions) function that you need to override while implementing your agent takes in a perceptions data structure that contains the agent's perceptions. While you can directly interact with this data structure, we've provided several utility functions that might make your job easier:

 

Known Issues with Version 0.05