View Item 
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        •   Utrecht University Student Theses Repository Home
        • UU Theses Repository
        • Theses
        • View Item
        JavaScript is disabled for your browser. Some features of this site may not work without it.

        Browse

        All of UU Student Theses RepositoryBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

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

        Thumbnail
        View/Open
        Master_Thesis.pdf (921.1Kb)
        Publication date
        2022
        Author
        Lambooij, Nikè
        Metadata
        Show full item record
        Summary
        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.
        URI
        https://studenttheses.uu.nl/handle/20.500.12932/42024
        Collections
        • Theses
        Utrecht university logo