CMSC 471 Course Project

Building an Intelligent Agent for Search and Rescue


Tournament Results

Project Description



SearchAndRescue, version 0.05

The old versions of the simulator in case anyone needs them. However, your final version of the agent must use the latest version.

Any further versions will only contain bug fixes, and possibly additional gridworlds. I'm also considering creating simulation configuration files to take care of the simulation parameters. This will eliminate all the messy command line arguments when starting the controller. If I do this, it will be optional and the controller will work with the old command line argument format as well, so it won't affect you.



The Gridworld Map Editor

Student-Written Utility Functions (updated 12/05/2007)


Change Log

Version 0.05

Version 0.05 includes additional display features and simulation features requested by 471 students during today's dry run. This distribution contains one change that may affect the development of your agent.

We discovered during the dry run that there was a problem with the simulation being slowed by stalled or crashed agents. 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. If this affects anyone (as in your agent might return more than 5 noops in a row), please talk with me about it immediately.

Version 0.04

Version 0.04 includes additional gridworlds, a display that shows you the status of each victim, the ability to upload your own graphic for your agent, and minor bug fixes. This distribution contains no changes that will affect the development of your agent.

Version 0.03

Version 0.03 includes victim data generation, training data for determining how long a victim will survive, a random-walking lisp agent, more lisp utility functions, and minor bug fixes.

The controller's command line interface now includes one additional parameter to specify the severity of the disaster, and a different classpath.

Version 0.02

Version 0.02 now automates the lisp client processing significantly. All information is automatically parsed into lisp data structures and presented to the intelligent agent. It also includes many utilities for the lisp client, an improved map specification, and many minor bugs fixes.

The command line interface to the display is exactly the same as version 0.01. The controller's command line interface now includes one additional parameter to specify the delay to allow agents to process the initial knowledge, and a different classpath. The lisp client interface includes a number of changes, so be sure to read that section in detail.


Instructions for using Version 0.05

Version 0.02 and later of 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 -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 -classpath "SearchAndRescue.jar;jdom.jar;weka.jar" searchandrescue.Controller 3000 gridworlds/ 1 50 30 5 localhost 2000

The two parameters that changed from versions 0.02 to 0.03 are in bold in the above command line.

The disaster severity is the new 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). Keep in mind, however, that your project will be implemented using lisp. 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

To implement your intelligent agent, 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