Search

Search Results

• 1. [Article] Planning Under Uncertainty for Unmanned Aerial Vehicles

  Unmanned aerial vehicle (UAV) technology has grown out of traditional research and military applications and has captivated the commercial and consumer markets, showing the ability to perform a spectrum ...

  Citation × Citation Citation Abstract Copy Title: Planning Under Uncertainty for Unmanned Aerial Vehicles Author: Skeele, Ryan Unmanned aerial vehicle (UAV) technology has grown out of traditional research and military applications and has captivated the commercial and consumer markets, showing the ability to perform a spectrum of autonomous functions. This technology has the capability of saving lives in search and rescue, fighting wildfires in environmental monitoring, and delivering time dependent medicine in package delivery. These examples demonstrate the potential impact this technology will have on our society. However, it is evident how sensitive UAVs are to the uncertainty of the physical world. In order to properly achieve the full potential of UAVs in these markets, robust and efficient planning algorithms are needed. This thesis addresses the challenge of planning under uncertainty for UAVs. We develop a suite of algorithms that are robust to changes in the environment and build on the key areas of research needed for utilizing UAVs in a commercial setting. Throughout this research three main components emerged: monitoring targets in dynamic environments, exploration with unreliable communication, and risk-aware path planning. We use a realistic fire simulation to test persistent monitoring in an uncertain environment. The fire is generated using the standard program for modeling wildfire, FARSITE. This model was used to validate a weighted-greedy approach to monitoring clustered points of interest (POIs) over traditional methods of tracking a fire front. We implemented the algorithm on a commercial UAV to demonstrate the deployment capability. Dynamic monitoring has limited potential if if coordinated planning is fallible to uncertainty in the world. Uncertain communication can cause critical failures in coordinated planning algorithms. We develop a method for coordinated exploration of a multi-UAV team with unreliable communication and limited battery life. Our results show that the proposed algorithm, which leverages meeting, sacrificing, and relaying behavior, increases the percentage of the environment explored over a frontier-based exploration strategy by up to 18%. We test on teams of up to 8 simulated UAVs and 2 real UAVs able to cope with communication loss and still report improved gains. We demonstrate this work with a pair of custom UAVs in an indoor office environment. We introduce a novel approach to incorporating and addressing uncertainty in planning problems. The proposed Risk-Aware Graph Search (RAGS) algorithm combines traditional deterministic search techniques with risk-aware planning. RAGS is able to trade off the number of future path options, as well as the mean and variance of the associated path cost distributions to make online edge traversal decisions that minimize the risk of executing a high-cost path. The algorithm is compared against existing graphsearch techniques on a set of graphs with randomly assigned edge costs, as well as over a set of graphs with transition costs generated from satellite imagery data. In all cases, RAGS is shown to reduce the probability of executing high-cost paths over A*, D* and a greedy planning approach. High level planning algorithms can be brittle in dynamic conditions where the environment is not modeled perfectly. In developing planners for uncertainty we ensure UAVs will be able to operate in conditions outside the scope of prior techniques. We address the need for robustness in robotic monitoring, coordination, and path planning tasks. Each of the three methods introduced were tested in simulated and real environments, and the results show improvement over traditional algorithms. Title: Planning Under Uncertainty for Unmanned Aerial Vehicles Author: Skeele, Ryan Unmanned aerial vehicle (UAV) technology has grown out of traditional research and military applications and has captivated the commercial and consumer markets, showing the ability to perform a spectrum of autonomous functions. This technology has the capability of saving lives in search and rescue, fighting wildfires in environmental monitoring, and delivering time dependent medicine in package delivery. These examples demonstrate the potential impact this technology will have on our society. However, it is evident how sensitive UAVs are to the uncertainty of the physical world. In order to properly achieve the full potential of UAVs in these markets, robust and efficient planning algorithms are needed. This thesis addresses the challenge of planning under uncertainty for UAVs. We develop a suite of algorithms that are robust to changes in the environment and build on the key areas of research needed for utilizing UAVs in a commercial setting. Throughout this research three main components emerged: monitoring targets in dynamic environments, exploration with unreliable communication, and risk-aware path planning. We use a realistic fire simulation to test persistent monitoring in an uncertain environment. The fire is generated using the standard program for modeling wildfire, FARSITE. This model was used to validate a weighted-greedy approach to monitoring clustered points of interest (POIs) over traditional methods of tracking a fire front. We implemented the algorithm on a commercial UAV to demonstrate the deployment capability. Dynamic monitoring has limited potential if if coordinated planning is fallible to uncertainty in the world. Uncertain communication can cause critical failures in coordinated planning algorithms. We develop a method for coordinated exploration of a multi-UAV team with unreliable communication and limited battery life. Our results show that the proposed algorithm, which leverages meeting, sacrificing, and relaying behavior, increases the percentage of the environment explored over a frontier-based exploration strategy by up to 18%. We test on teams of up to 8 simulated UAVs and 2 real UAVs able to cope with communication loss and still report improved gains. We demonstrate this work with a pair of custom UAVs in an indoor office environment. We introduce a novel approach to incorporating and addressing uncertainty in planning problems. The proposed Risk-Aware Graph Search (RAGS) algorithm combines traditional deterministic search techniques with risk-aware planning. RAGS is able to trade off the number of future path options, as well as the mean and variance of the associated path cost distributions to make online edge traversal decisions that minimize the risk of executing a high-cost path. The algorithm is compared against existing graphsearch techniques on a set of graphs with randomly assigned edge costs, as well as over a set of graphs with transition costs generated from satellite imagery data. In all cases, RAGS is shown to reduce the probability of executing high-cost paths over A*, D* and a greedy planning approach. High level planning algorithms can be brittle in dynamic conditions where the environment is not modeled perfectly. In developing planners for uncertainty we ensure UAVs will be able to operate in conditions outside the scope of prior techniques. We address the need for robustness in robotic monitoring, coordination, and path planning tasks. Each of the three methods introduced were tested in simulated and real environments, and the results show improvement over traditional algorithms. Close