• Overview
• Visitor Info
• People

• Publications

• Courses
• GA/SA/MA

• News
• Seminars

Control and Optimization Algorithms for Firefighting in Urban Environments

Firefighting is a challenging dangerous real-life task, involving high risks combined with split-second 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 real-time feedback control strategies.

The Firefighter problem in the optimization community, while clean and quite well-studied, fails to model various important real-life 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 real-life 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 real-life 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 real-life 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:

• Fire dynamics: For any two burning nodes, the fire spreads to the neighboring node with some predefined probability.
• Firefighter motion: The firefighters are able to move along the edges of the graph with some bounded speed.
• Objectives: The firefighters' goal is to perform rescue operation, in which they need to reach certain nodes in the graph before the fire reaches them to collect a "token" and bring it to one of the "safe nodes" in the graph. The location of the tokens and the safe nodes is provided in the input of the problem.

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.

strong background in optimization theory and control

stochastic and combinatorial optimization, dynamic programming and optimal control, stochastic control

Please apply by writing to the advisors and including your CV and transcript of grades at Bachelor and Master's level.

Maryam Kamgapour, Automatic Control Lab, mkamgar@control.ee.ethz.ch
David Adjiashvili, Institute for Operations Research, ETH Zurich, david.adjiashvili@ifor.math.ethz.ch