Using State Evaluation and Artificial Neural Networks to solve the Firefighter Problem

Abstract

The Firefighter Problem (FFP) on graphs is a model for fighting the spread of a fire through a city. At each time step d nodes can be defended from the fire, before the fire spreads to all undefended nodes adjacent to a burning node. In this thesis we investigate the application of State Evaluation to this problem, creating an ANN called SEANN for this purpose. We also describe a second neural network, called CLANN that solves FFP more directly by classifying which node should be protected at the current time step. To solve the FFP we created several solvers that use some form of State Evaluation, and we compare these to the optimal solution found by solving an ILP model and to a greedy algorithm in case of trees. Our experiments show that State Evaluation works very well for FFP, especially a Greedy State Evaluation algorithm that uses a Greedy Look-ahead algorithm to evaluate potential future states. The CLANN network, however, performs worse than basic greedy heuristics.