Control and Optimization Algorithms for Firefighting in Urban Environments 

Student(en): 
Betreuer: Maryam Kamgarpour, David Adjiashvili 
Beschreibung: Introduction Firefighting is a challenging dangerous reallife task, involving high risks combined with splitsecond decision making. In most cases the firefighters use their experience combined with a limited knowledge of the burning structure to decide the strategy for fighting the fire. In this thesis we would like to consider models and methods from the fields of control and optimization that could aid decision making in complex firefighting situations.
Literature on models and methods for various abstractions of the firefighting problem is existent in various fields, including combinatorial optimization and optimal control. The simplest studied model in the fields of combinatorial optimization is called the Firefighter Problem. In this problem the environment is modeled as a graph, where the nodes represent objects that may catch fire, and the edges represent the means by which fire spreads. Starting from an initial node, the fire spreads deterministically to the neighboring edges, unless the neighboring node is protected. The goal is to decide which nodes the firefighters should save in every time step in order to maximize the number of saved nodes. There has been recent advances in combinatorial optimization developing computationally tractable approaches to solve this problem. Our goal is to build on these successes, and extend the results to more realistic models as well as realtime feedback control strategies.
Project Description
The Firefighter problem in the optimization community, while clean and quite wellstudied, fails to model various important reallife aspects of firefighting. The main two drawbacks are the deterministic dynamics for fire propagation and the implicit assumption that the firefighters are able to move from any node in the graph to any other node in a single unit of time. Another important reallife aspect of firefighting not modeled by the Firefighter problem is the fact that in many cases, firefighters are more concerned with saving people in the burning structure than blocking the spread of the fire. Additional minor disadvantages of the model include the fact that protection of nodes is deterministic, that protected nodes remain protected forever.
In this project we plan to study a more elaborate model, incorporating some additional aspects of reallife firefighting, with the hope that such a model can serve the basis of a real decision support system for firefighting. For simplicity, and based on typical reallife networks, we will restrict the class of graphs that is considered to simple classes, such as grid, or partial grid graphs. This may also lead to more tractable models from the computational complexity point of view. In particular, a stochastic variant of the Firefighter problem with the following additional set of restrictions will be considered: Considering the above model, we will develop computationally tractable algorithms for the firefighter problems. We will build on existing algorithms in combinatorial optimization and in control theory.
Required Skills
Acquired Skills
Procedure
Advisors
David Adjiashvili, Institute for Operations Research, ETH Zurich, david.adjiashvili@ifor.math.ethz.ch Weitere Informationen 
Professor: Maryam Kamgarpour 
Projektcharakteristik: Typ: Art der Arbeit: Voraussetzungen:  
Anzahl StudentInnen: Status: open  
Projektstart: Semester: 