Imagine that you have won a shopping spree sweepstake at the local Walmart. Assuming that you know the layout of the store pretty well and have common sense on how much general merchandises are worth. Now for the next 2 minutes anything you grab are yours to keep for free, what would you do? Would you just start grabbing everything that are close to you such as orange juice, eggs, sausages, and breakfast cereals, or would you dash straight to that 60-inch LCD TV (or that 5 Carat diamond ring if you are a woman) at the furthest corner of the store? What is the best path you should take to maximize the total monetary value of the shopping spree?
Now just to make it a little bit more complicated, what if you only have 1 minute to grab things? Maybe you are asked to start from the cashier's lane and must return to the cashier's lane before your time runs out? What if your shopping cart was tinkered with and it doesn't roll backward? What if getting that 5 Carat diamond ring required a Walmart employee to unlock three things before you can get to it? What if you forgot to bring your glasses and everything looked totally blurry in front of your eyes? Looks like the wonderful dream of winning the sweepstake has just turned into a nightmare! "Why are you making it so hard for me?" you moan. And I shrug and tell you that those are all the challenges I face when I plan a coverage path for a UAV in support of Wilderness Search and Rescue operations.
The benefit of adding a UAV to the Wilderness Search and Rescue team is that now you have an eye in the sky and you can cover large areas quickly and also reach areas that are difficult for human on foot to reach sooner. When planning a coverage path for the UAV with a gimbaled camera, what we really care about is the path of the camera footprint. In our path-planning approach, we use a 4-connect grid to represent the probability distribution of where it is likely to find the missing person. Even though a fix-wing UAV might need to roll and follow a curvy path when it turns, the gimbaled camera can automatically adjust itself to always point straight down and the path of the camera footprint can include sharp 90 degrees turns. As the camera footprint covers an area, it "vacuums up" the probability within that area, and obviously the more probability we can "vacuums up" along the path, the more likely the UAV can spot the missing person.
When we evaluate how good a UAV path is, we focus on two factors: flight time and the amount of probability accumulated along the path. If a desired flight time is set (maybe due to the fact that the battery on the UAV only lasts for one hour), then the more probability we can accumulate, the better the path. If a desired amount of probability is expected (e.g., 80% probability of spotting the person from the UAV), then the sooner we can reach that goal, the better the path. My research focuses on the first type of case only where we plan a path for a given flight duration.
So how good or efficient is the path generated by our algorithm? A natural way to evaluate this is to compare the amount of probability the UAV accumulates along our path against what the UAV can accumulate along the best possible path and compute a percentage. A path with 50% efficiency means the path is half as good as the best we can do. The irony here is that we don't know what the best possible (optimal) path is, and searching for this optimal path might take a long time (years) especially when the probability distribution is complex (like how it is in real search and rescue scenarios), and it defeats the purpose of finding the missing person quickly. Many factors can also affect how the optimal path might turn out and change the total amount of probability accumulated if the UAV follows that path. Here I'll list the ones we must deal with.
1. Desired flight time
If the search region is very small, the UAV has 100% probability of detection (say we are searching in the Bonneville Salt Flats), and you have plenty of UAV flight time to completely comb the area many times, then life gets easier and you can be pretty sure that you will spot the missing person if the UAV follows a lawnmower or Zamboni flight pattern (assuming the missing person stays in a fixed location). If the search region is very large and you have a very short UAV flight time, then maybe there are areas you simple can never reach given the short flight duration. Remember the 2-minute shopping spree vs. a 1-minute one?
2. Starting position and possibly the ending position
If the UAV starts from the middle of the search region, the optimal path will most definitely not be the same as the one when the UAV starts from the edge of the search region. And if the UAV must return to a desired ending position (maybe for easy retrieval or returning to command base), time must be allocated for the UAV for the return flight. Ideally, while flying back, the UAV should still try to cover areas with high probabilities. In the example of the shopping spree case, if you are required to start from the cashier's lane and also return there before time runs out, you probably still want to grab things on your way back, maybe choosing a different route back.
3. Type of UAV (fix-wing vs. copter)
A fix-wing UAV must keep moving in the air in order to get enough lift to maintain airborne. It also cannot fly backward. But a copter type UAV doesn't have these restrictions. It can hover over a spot or fly backward anytime it wants. Therefore, the type of UAV we use can really change how the optimal path looks like. Remember the shopping cart that was tinkered with in your shopping experience?
4. Task difficulty (probability of detection)
Although the UAV provides the bird's eye view of the search area, some times we look but we don't see. Maybe because the dense vegetation makes spotting the missing person a very difficult task; maybe the weather is really bad with lowers the visibility; maybe the missing person is wearing a green jacket that blends in with the surroundings. This means the probability of detection might vary from case to case and search area to search area. When the probability of detection is low, maybe we should send the UAV to cover the area multiple times so we can search better. This factor really adds complexity to the evaluation of a UAV's path's efficiency. When it takes 30 seconds for the Walmart employee to unlock everything and get that 5 Carat diamond ring for you, is it worth the wait? Or maybe grabbing all those unlocked watches at $50 a piece in the neighboring section sounds like a better idea now?
Given all these complicated factors, I still need to find out how well my path-planning algorithm is performing in different search scenarios. In the following blog posts in this series, I'll go through each factor and discuss how we can reasonably evaluate the efficiency of a search path without knowing the optimal solution.
Video of the Day:
A video my friend Bev made when I showed her around the BYU campus!
