Task 3

Updated Mission Strategy

Tyler Jordan, Michael Vegh

Through the vast improvements in the simulation software, in-depth analysis of a few mission strategies has been generated. The initial aggressive algorithm was used with a new search pattern, leading to some modest improvement. A fire containment algorithm was then added. The simulation results seem somewhat promising, although they may be somewhat misleading, as there could be significant issues when it comes to actual implementation.

New Search Pattern

Some regressions were performed on the initial search path from Problem Set 2 to determine potential changes that might prove beneficial to the overall mission score. In this case, the figure below shows results from constraints on turn radius and climb rate vs. number of drops required to extinguish all fires, in order to determine the sensitivity of mission effectiveness to aircraft performance. To obtain each data point, the mission simulation was run 500 times for a given set of aircraft dynamics, and the mean scores and water drops recorded.

Figure 2: Search Path Comparison

Bear in mind that the initial search path ensured coverage of all cells assuming the aircraft is always at maximum altitude; this updated algorithm allows for a high degree of confidence that all cells will be searched, even taking into account picture radius/altitude limitations. Note that both search paths initialize in the center of the mission field and immediately begin by heading in the general direction of the wind to attempt to find the largest threat, then continue on to other cells until the entire grid is searched. Furthermore, all further simulations assume a climb rate of 1.5 m/s and turn radius of 5 m unless otherwise specified.

Some optimization was attempted with this algorithm using the current MATLAB-based simulation code, but it was found that for a single optimization iteration (which runs the simulation 500 times for a given set of conditions), the code takes 10+minutes per iteration. While this allows for some incremental improvement, a more aggressive approach is needed. To that end, as a stretch goal, this code is being ported over to a C++-based framework, in attempt to allow for real improvement and optimization of the search path. Work has already begun on this front, although extensive debugging is required, and the first priority is to ensure that it runs on the PixHawk.

Aggressive Algorithm

The initial algorithm uses an aggressive strategy, following manually-selected strategic way-points, taking pictures at each one. When the aircraft locates one or more fires, it flies to the nearest one and douses it, continuing on to the next. When all visible fires are put out, it returns to the search state where it follows the waypoints then searches all previously unsearched cells.

The main advantages of this algorithm is that it is simple, relatively easy to implement, and performs decently (it manages to contain any fire within the allotted time). The disadvantage is that it has the potential to require too much water; rather than strategically fighting the fire, it just puts out as many cells as it can. This can lead to ineffective containment and allow a fire that had already been spotted to spread dramatically, unknown to the airplane until it becomes too large to control.

Figure 3: Aggressive algorithm example. The algorithm puts out fires as the plane sees them without exploring downwind or conserving water. After the second turn in the upper right part of the circle, the plane extinguishes some fires, but lets it spread and has to fight it later.

The aggressive algorithm was simulated more than 20,000 times to attain the results in Figure 4. The upper plot shows the distribution of the potential fires and the number of douses used to attain a score of 100 %. The upper left plot shows a heat-map of the distribution of scenarios. One can see that many of the simulations had fires with a potential size of about 25 and used about 17 douses of water. Additionally, one may never use more water than the total fire count for a mission without an aircraft, and large fire sizes and douse usages are unlikely. The larger the fire, the less the distribution of proportional douses is. The bottom chart shows that one need approximately 1 douse for every 2 fires. This distribution is quite center-weighted indicating that this value can vary equally up and down.

Figure 4: Aggressive algorithm statistics.The simulation was run 20,000 times and only the ones with scores of 100 were considered. The upper left plot shows the probability distribution of both the potential fire size and the number of douses used. The upper right chart shows a distribution of the mission occurrences and how often a certain number of douses was used on a certain potential fire size. The bottom plot shows the distribution of the number of douses needed to put out a particular fire size.

Contain Algorithm

After seeing the statistics and watching a multitude of missions play out, it was clear that using a more complex strategy might help. These statistics were used to test whether or not a new method is an improvement over the "Aggressive" strategy. After detecting fires, the contain algorithm sorts them into potential edge fires and contained fires. Edge fires are fires whose neighbors in the direction of the wind and adjacent directions are dry. If they are unsearched, it is called a potential edge fire. The algorithm then finds the fire that is furthest downwind and sets a waypoint there to extinguish it. On the way to that downwind fire, the aircraft will also douse potential edge-fires. This downwind-weighted extinguishing strategy helps the plane contain the fires that could spread while emphasizing extinguishing the fire-front. After all cells are explored, the plane aggressively fights the remaining contained fires.

Figure 5: Contain algorithm example. On the first fire the aircraft encounters, the plane pursues downwind, eliminating the first fire. When encountering the second fire, the algorithm detects which cells can spread and extinguishes those first, saving time and preventing more spread. After all fires are contained, the plane returns to search state until all cells are searched, then extinguishes the remaining contained fires in the same method as the aggressive algorithm.

Though the fires are still capable of spreading quite far even with the contain algorithm implemented, the contain algorithm still does a measurably better job. The results can be seen in Figure 6 below.

Figure 6: Contain algorithm statistics.The simulation was run 20,000 times and only the ones with scores of 100 were considered. The upper left plot shows the probability distribution of both the potential fire size and the number of douses used. The upper right chart shows a distribution of the mission occurrences and how often a certain number of douses was used on a certain potential fire size. The bottom plot shows the distribution of the number of douses needed to put out a particular fire size.

The upper left plot demonstrates that the contain algorithm outperforms the aggressive algorithm, at least in terms of water douse efficiency. The douse mean is now 18 with a more concentrated, lower distribution. The upper right chart shows that the contain algorithm favorably scales with potential fire size as the distribution is lower compared to Figure 4. The bottom distribution illustrates that it takes less douses to put out more potential fires. This distribution is more weighted towards 0 which shows both an improvement in efficiency as well as a more likely negative variance.

Score Improvements

Both algorithms were tested with water douse limits to more accurately measure their potential performance. Figure 6 illustrates a marked improvement with these constraints

Figure 6: Score vs douse limit: The simulation was run 300 times for each douse limit and the mean and variance of at each limit is shown in the above figure. The variance error bars are scaled by 100 to fit inside the plot.

Figure 6 above shows the relation of average score to a douse limit. They both asymptotically approach 100 % near 50 douses. This relation has improved dramatically with the introduction of the Contain algorithm. The actual score distributions can be seen in Figure 7 below.

Figure 7: Scores distribution at various douse limits. The same data in Figure 5 is shown in better detail here as we can see the entire distribution at each douse limit.

Whereas the score distribution tends towards 100 as the douse limit increases to 50, the contain algorithm converges quicker and has a more desirable distribution. For example: the aggressive version has two modes in the douse limit = 10 case while the contain algorithm has one mode at 100 with a monotonically increasing probability.

Analysis and Conclusions

These simulations and analysis have given profound insight and a measurable way to improve the search algorithms. However, this strategy is far from finalized. In an ideal world, the aircraft would be capable of flying with 50 douses available to achieve the statistically-guaranteed 99.9 % score, the aircraft design subteam has communicated that the plane may climb with as much as a 180 g ballast but that a 150 g ballast is preferable. Interpolating from Figure 6, the average score with 15 douses is about 88 %. Additionally, because these simulations were completely random and it is expected that the instructors will assign higher concentration of difficult fires, an additional 10 % loss is expected. Furthermore these regressions assumed a climb rate of 1.5 m/s, which is somewhat optimistic. Also, the aircraft may have to fly slightly below the maximum altitude to avoid being knocked out of the mission field by thermals. For these reasons the team is looking to improve the algorithm incrementally once the code has been interfaced into the PixHawk and flown.