How to Control Bushfires Leveraging Graph Algorithms

External Member

Ahad N. Zehmakan

Description

 
 
Motivation. Bushfires can cause poor air quality, which can affect human and animal health, and can have long-lasting impacts on soil and water quality. Bushfires can also have devastating impacts on plants, animals and ecosystems. Furthermore, the changes in climate (caused by the drastic increase in carbon dioxide level in the atmosphere) create warmer, drier conditions which are boosting the frequency and intensity of the bushfires. Consequently, development of methods to monitor and control bushfires is very essential.
 
Computational Perspective. There has been an ongoing effort in the field of computer science to design effective methods to monitor and control the spread of wildfires, using computer vision tools, wireless sensor networks, unmanned aerial vehicles, and machine learning algorithms. This project aims to leverage the graph theory and algorithm design techniques to make advancement in our knowledge on the control of bushfires.
 
Bushfire Spread Model. Consider an n*n grid, where initially each cell is unburned, burning, or burned. In each discrete-time round: (i) a burned cell remains burned, (ii) a burning cell switches to burned if it has been in the burning state during the last t rounds, (iii) an unburned cell becomes burning with some probability p if it is adjacent to a burning cell. The values of t and p can be set according to the set-up that model attempts to mimic. One can, of course, add different parameters to the aforementioned basic model and consider other network structures to capture the real-world bushfires spread process more comprehensively.
 

Contact Information

 
Please feel free to contact me if you have any questions. I would be glad to have a discussion on whether this project suits you.

 

Goals

There are different methods which are used to make some areas of the forest (corresponding to cells in our model) fire-proof, such as digging a small ditch, pulling up some plants, and burning some cells deliberately just inside a control line.
Assume that we have the budget and capacity to make k cells fire-proof prior to the occurrence of any bushfire. What are the cells that we should choose to minimize the spread of the fire assuming it starts at a random cell?
 
Assume that the fire has started and you have f firefighters and each firefighter can turn off one cell in each round. What is the best strategy to minimize the number of burned cells?
 
The goal of the project is to mathematically formulate the above model and problems, and attempt to address the aforementioned questions (and similar ones) by presenting theoretical findings (building on graph theory, probability theory, and optimization techniques) and conducting various experiments.
 

Requirements

  • A good understanding of graph theory and probability theory. (Familiarity with different random graph models and Markov chains is a plus, but not required.)
  • Good programming skills.
  • Have taken/taking at least two of the following courses: COMP1100, MATH1005, COMP1600, COMP3600, COMP4600, MATH2301

Keywords

Controlling Bushfires, Graph Algorithms, Markov Chains, Multiagent Systems, Artificial Intelligence, Algorithm Design.

Updated:  10 August 2021/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing