CSSE 413: Forest Fire Rescue Programming Assignment

This assignment is adapted from an assignment given by Andrew W. Moore, in an AI course at Carnegie-Mellon University.

Problem

In the Forest-Fire Rescue problem, you control a set of trucks. Your objective is to rescue people who are trapped in a forest fire in an expeditious manner. Below is an example state of this world.

+----------+
| F  P     |
| F    T   |
|          |
|T       P |
|  FFF     |
+----------+

In this world there are:

People (P), trucks (T) and fires (F).
An m x n grid representing the location.
A state in this world consists of people, trucks, and fires, placed on mutual exclusive grid positions.
Fires do not grow or shrink.
People do not move.
Trucks can move up, down, left, or right by exactly one position per state transition.
Two trucks may not occupy the same position.
A truck may not move into a fire square.
As many trucks as you choose may move per turn.
When a truck moves into a position occupied by a person, the person is automatically loaded on board and disappears from the map.
A truck may exit to safety by moving to the left from the left-most column. In this case, it disappears form the map. Trucks may not move off the map in any other direction.
Since it is uncomfortable to be near a raging fire, for each turn in which a person is not picked up, their distress-level goes up. They start out with a distress-level of zero. Their distress level increases by 1 plus the 1/d(t) to the nearest fire, where d(t) is the Manhattan distance. In other words, the closer to the fire, the more distressed people are going to be and the longer it takes for them to be rescued, the higher their distress level is going to be.
The objective is to rescue all people, while minimizing their distress level. A goal state is a state in which there are no remaining people to be picked up, and in which all trucks have exited to safety.

Examples

Specifics

Develop a heuristic and a cost function for this problem. Design a data-type for states. Design and implement a program that uses A* to search the search space. Implement your program in either Scheme or Java.

Your grade will depend on the quality of your solution and code. You want to ensure that your algorithm finds an optimal solution with the smallest amount of effort possible.

To make testing easier, please have your program read a file called start.txt which contains data about the start state. Please click on the link for more information. Alternatively, if you want to make life more fun for the graders, provide a clickable GUI, enabling the user to set up a start state.

Your program should output the following:

Display instructions on where each truck moves on each state-transition. Display row number before column number. Alternatively, you may wish to display the states leading to a goal state. ASCII graphics would be fine.
Display the amount of distress that the people accumulated.
Display the length of an optimal solution, where length is the path length from the start state to an optimal goal state.
Display the number of nodes that your program expanded.

Turnin

The most important aspect of this problem is the heuristic function and the data-type for representing states. You want to focus a good amount of energy on these up-front. The deadline for the design sketch of your data-type as well as the algorithm for your heuristic and an argument showing that it is admissible is Friday, September 7, at the beginning of class. Turn in a write-up, describing the design of your data-type as well as your heuristic. Furthermore, provide an argument that your heuristic is admissible.

The deadline for the entire project is Wednesday September 12th at midnight.

Name your program forestfire.* zip it up and submit to the appropriate drop box on Angel.