Task 3

Updated Mission Strategy

Michael Vegh, Tyler Jordan

Fire Dynamics and Representation:

The fire is modeled as an n by m matrix, where n is the number of cells, while m is the number of time steps; time is represented here as a vector from 0 to 600 in steps of 20. The state of the fire at time step j is represented by an integer, where 0 means the cell is not on fire, 1 means the cell is on fire, and 2 means that the cell has been doused with water, and thus, cannot catch fire. Each cell i corresponds to an entry in an n by 2 matrix, with the first entry as the x coordinate of the cell center, while the second entry is the y coordinate of the cell. Fire propagation is based on the following formula

propagation_direction=round(wind_direction+ FIRE_STD*randn(1))

Where randn is a Gaussian probability distribution function from MATLAB (centered at 1), FIRE_STD is the standard deviation of propagation (the competition rules set this at .3). propagation_direction as well as wind_direction are integer variables extending from 0 to 7, as Figure 1 displays below.

Figure 1: Direction Chart (taken from competition rules)

1-2 fires are initially located in random cells at the start of the mission, and propagated throughout the grid based on the choices the aircraft makes in dumping water. Some sample plots of the grid, as well as initial and final fire distributions can be seen below.

Figure 2: Initial Fire Distribution and Grid Setup

Figure 3: Propagated Fire Distribution

Figure 4: Sample Final Fire Distribution with Unconstrained Trajectory

In Figures 2-4, the red diamond indicate the presence of a fire, the blue squares indicate that the cell has been doused by the aircraft, while the green circles in Figure 4 indicate that the cell has been scouted. Additionally, in Figure 4, the aircraft trajectory ( in blue), as well each “snapshot” (the faint cyan circles) are shown. Now, it should be noted that the aircraft trajectory was discretized under a different timestep than the fire, which is elaborated on in the Aircraft Dynamics section of this task.

Decision Algorithm:

Currently the algorithm is essentially a state machine with two states: search and fight. The search state makes the plane fly to predetermined, efficient waypoints to take photos which maximize the aircraft's field of view, capturing 9 cells' status' at a time. The algorithm switches to the fight state whenever a fire is spotted in which a waypoint is set to the centroid of the closest fire. When the plane arrives in the cell it extinguishes the fire then moves on to the next fire in the same manner until no fires are left to fight at which point it switches back to the search state and resumes following the predetermined waypoints. The mission setup converts these waypoints to radial coordinates and rotates them based on the prevailing wind direction in order to ensure that the problem being solved is essentially the same at every iteration.

Aircraft Dynamics:

The aircraft time is discretized based on time steps of .1 seconds from 0 to 600 (corresponding to the 10 minute time limit on the mission), with a corresponding n by p by 2 matrix of information the aircraft knows at a given time step, where n is the cell number, and p is the number of time steps; the first index refers to the knowledge the aircraft has of the cell (i.e. whether it’s on fire, put out, explored but not on fire, or not yet explored), while the second index refers to the time at which the cell as scouted (if any). Aircraft dynamics are handled at each timestep, where the MATLAB function takes in the aircraft location, heading, velocity, as well as the target waypoint, at a given timestep and outputs the position, heading, and velocity at the beginning of the next time step; a simple linear discretization is used, with an option for a turning constraint; some sample plots of aircraft trajectories are shown below, with different turning radius constraints.

Figure 5:Flight Path, no turning constraint

Figure 6: Flight Path, 5m turning radius

Figure 7:Flight Path, 10 m turning radius

Preliminary Results:

The mission was simulated within MATLAB with a time-step of 0.1 seconds, speed of 10 m/s, and an unconstrained turning radius. The statistics below were computed by running the simulation 4042 times. The average score is 97 % and the mean number of water drops used is 20. Rssentially, under ideal conditions, the aircraft could put out the fires every time, assuming it could carry enough water weight. Assuming the aircraft could carry 20 units of water, 43 % of the simulations would not have been contained. The code is extensible, and improvements are being made in both improving the fidelity, e.g. modeling climb results, as well as adding additional modes (such as containment), which can be tuned as part of a larger optimization problem

Next Steps:

Next steps include implementing a new state to not just fight the fire, but to contain it so that the plane may conserve water. This new algorithm will only put out fires with a potential to spread therefore conserving water and time to find and fight the second fire. Secondly an attempt will be made to implement some convex optimization algorithms to enable more efficient path planning. Right now the Fight state makes the plane take sharp turns because the trajectory is towards the centroid of the closest fire (black arrows), but convex optimization would allow for a straighter smoother path if instead of setting the waypoint to the centroid, the waypoint would be limited by the grid square so that plane only needs to fly over the cell to extinguish it (red arrow).

Taking these steps to conserve water with the contain state, and fly more efficient paths with convex optimization will allow the aircraft to more effectively complete the mission by working smarter, not harder. Additionally, a global optimization framework is currently being set up and tested to inform the choice of waypoints for the initial path, to not only ensure consistently high scores, but also reduce the required number of "douses," adding constraints such as climb and power consumption to allow for realistic integration with the aircraft configuration.