The objective of this proposal is to develop novel algorithms that are required to deploy unmanned aerial vehicles for better understanding the structure of forest ecosystems in relation to fire risk assessment. The algorithms will enable unmanned aerial vehicles to assist in identifying high fire-risk regions in a given area, aid fire managers to monitor and respond to fire propagation in real-time and map large areas for post-fire assessment. The approach is to 1) develop algorithms for creating surface fuel maps using tools by remote sensing, 2) develop approximation algorithms and heuristics to efficiently allocate the resources and plan the motion of the vehicles such that the regions that need to be monitored are visited within a desired time. Intellectual Merit: With regards to remote sensing, the proposed methods will provide an affordable way of obtaining precise estimates of forest surface and canopy fuels that is currently not available. With regards to resource allocation and motion planning, the methods will advance the state of art in the development of fast, sub-optimal algorithms. Broader impacts: Fire managers will be able to swiftly identify high fire-risk regions in a given area using the developed tools and efficiently respond to fire propagation in real-time. Controlled burning has ecological, societal and economic benefits: enhanced ecological processes in fire-dependent ecosystems, abated risk of catastrophic fires, reduced property damage and loss of life. This project will provide an opportunity for students to learn tools from diverse disciplines and valuable teaching material for courses in remote sensing and robotics.
What this project was about: This project dealt with the development of new algorithms for routing Unmanned Aerial Vehicles with motion constraints so as to enable them to gather data from different locations with limited on-board resources (such as fuel). The project also dealt with ways to build surface fuel maps that will aid fire managers to identify high fire-risk regions in a given area. What was accomplished: Routing: The problem of routing UAVs is complicated by the following factors: (1) motion constraints, (2) fuel constraints and (3) heterogeneity among UAVs. The problem involves assigning a set of targets(locations) to each UAV and then finding an optimal sequence to visit each of the targets. In this problem, the motion constraints such as the bounded yaw rate of a UAV couple the sequence of targets to be visited and the approach conditions of a UAV for each target. The problem of partitioning targets to assign to each UAV and the problem of sequencing targets for each UAV to visit are known to be difficult combinatorial problems by themselves. For this reason, we were interested in developing easily computable but suboptimal solutions with computable suboptimality bounds. We have specifically accomplished the following Novel suboptimal routing algorithms for a collection of heterogeneous UAVs: We use the distance traveled as a proxy for the fuel consumed and our objective for routing is to minimize the total distance traveled by the collection. We provide an a-priori guarantee that the developed algorithm will produce a real-time implementable solution within a specified factor of optimum; note that while the optimum is difficult to compute, the suboptimality guarantee is independent of the ability to compute the optimum. For a general collection of heterogeneous UAVs, this guarantee increases linearly with the number of UAVs (and not the targets). If the collection of UAVs have different turning radii but are traveling at the same velocity, the guarantee is also independent of the size of the collection. Lower Bounding the optimum: Since the computation of optimum is not known to be computationally tractable, we focused on obtaining an easily computable lower bounds for the optimum. If the lower bound is tight, it can be used as a proxy for the optimum in the evaluation of heuristics for this problem. The novel feature of our work is that it involves lower bounding a problem that is quintessentially a combination of variational and combinatorial optimization problems. Suboptimal routing with limited fuel-tank for each UAV while allowing refueling: We developed novel, easy to compute suboptimal solutions that enable a collection of heterogeneous UAVs to be routed when their fuel tank capacities and locations of the refueling stations are known a priori. Suboptimal routing of UAVs with information constraints: Since power on-board is limited, a pair of UAVs may not be able to communicate unless they are within a specified distance of each other. In GPS-denied environments, the problem of localizing UAVs is a difficult problem; in this problem, we dealt with routing UAVs with beacons on the ground that can communicate with UAVs only if they are in their proximity so as to enable UAVs to localize. Each UAV not in the proximity of a beacon can localize only if it can triangulate its location with other localized UAVs. We developed real-time implementable suboptimal routing algorithms for UAVs in such GPS-denied environments while providing a guarantee on the suboptimality. Building surface fuel maps: The graduate student support provided by the NSF IDR grant funded a PhD student in the ESSM department (Ecosystem Science and Management). As part of the research investigations conducted by Dr. Popescu and the graduate students in his lab, the group accomplished several goals associated with the project: (1) developed methods to characterize the three-dimensional structure of vegetation; (2) developed algorithms for processing airborne Lidar data to map forest fuels; and (3) investigated sensors integration on a rotary platform-UAS, an octocopter with a payload of 6 lbs. Webpage with the papers detailing algorithms and software: https://sites.google.com/site/srathinam/publications Workshop conducted based on the results from this project: https://sites.google.com/site/srathinam/workshop
