Project progress, search patterns, and a DIY UAV

Following more meetings on our shiny new UAV project we've begun to thrash out a few more of the scenario details including a loosely defined goal of having a working prototype demonstrator next summer which involves multiple UAVs locating some sort of object (perhaps radio beacons) in a predefined search space. The ultimate goal is to scale this up over coming years into something resembling a radiation/chemical leak response package which could meet a number of targets, for example locating people in the path of the contaminant, alerting emergency services to their location, etc.

With that in mind I've been focussing my reading more around the search-pattern, search-algorithm area and trying to find out about existing methods and their relative pros and cons. Bayesian methods make a recurring appearance simply because having some pre-conceived belief and then updating it as you find more data is an extremely logical approach to the problem. There's also the issue of what can be achieved with multiple drones, and how best to confirm a target's identity once a potential sighting has been made. To that end I've had a few thoughts and ideas on possible approaches, based partly on existing work:

Utilising multiple similar UAVs in a heterogenous way
Given a few different types of UAV in a situation it's clearly logical to treat them differently. But what if you have identical drones that can perform different tasks? For example, given three drones and a search space, rather than having them all running search patterns independently at the same height (so the same detail) would it be advantageous to have a hierarchy where one (or more) UAVs takes high altitude, low-detail images and then co-ordinates the other drone/s towards possible matches?

This...

... vs this

This introduces a quasi-centralised system - which would obviously need to be robust enough that if the higher UAV fails the search can still continue (perhaps reverting to the first arrangement). It would also need to be established if there is any benefit to this method.

Inter-UAV task allocation

Going on the basis that the MaxSum algorithm mentioned in previous posts is an extremely versatile task-allocation tool, I've been considering if there's scope for its implementation in this area. For example, say a search pattern is being carried out by a swarm of UAVs using either of the two arrangements given above, and a possible sighting is made. Could then, the co-ordination switch from Bayesian searching to a MaxSum task assignment as one UAV creates a task of "go and take a closer look at this location" and broadcasts it to surrounding vehicles? In the same-height arrangement it might turn out that such a method would be moot as it would maximise the utility function if each UAV checks out its own possible sightings, but with the second method the higher altitude drone could easily interrupt the search of the lower UAVs by creating a task of looking in detail at a location. 

The bottom line of this is that the UAVs could have two modes; a Bayesian search method and a MaxSum task mode; designed to compliment each other

Prior planning and search space restriction

One might imagine a number of these situations where, once establishing the area to be searched, time could be saved in the co-ordination stage by assigning each UAV a portion of the area to search which they are then restricted to (barring a MaxSum task being received). Indeed there need not even be awareness between the UAVs of the other drones' behaviour, since each could have its own Bayesian belief map of their portion. If the designated target is found by one UAV they then need only communicate this to the others for them to stop searching. This could also reduce message overhead. A pithy summary then, is "do the UAVs actually need the information gained by the other UAVs in the area?".

More questions:

The seemingly simple task of "find some objects in an area" actually has considerable elements that need to be accounted for in any solution. As well as the things mentioned above, the formalised problem has the following points to contemplate:

• What uncertainty will the UAVs' images produce (presumably related to sensor resolution and altitude)?
• How accurately do they need to know a target's position to consider it a successful task?
• Is there any other metric to measure success beyond "finding the targets quickly"?
• Do the UAVs know in advance how many targets there are?
• If the answer to the above is "no", will they ever stop their search or is it actually desirable that they keep looking indefinitely?

A final word, from a DIY unmanned vehicle search team

For interest, I found the blog of a team from Australia who competed (and almost aced) a competition held there to find a missing person and drop a water bottle for them in a pre-defined search space using an unmanned aerial vehicle. While not offering a huge amount of inspiration on the co-ordination front (a simple "lawnmower" search pattern was used with a recognition algorithm) it still makes interesting reading. I'm thoroughly impressed by how well it all worked considering it was an amateur effort done essentially by hobbyists. Check it out!

-C

Some disjointed thoughts on UAV deployment 2

Using a Mini UAV to Support Wilderness Search and Rescue: Practices for Human Robot Teaming -Goodrich et al

Carrying on from yesterday, with the added caveat that following a meeting it seems we may be looking more into the realms of radiation leak scenarios (which actually holds a lot of overlap for this sort of thing. More on that later), this is the second paper I meant to ramble about yesterday but didn't get a chance to.

The unique perspective provided by this publication is that it uses actual search and rescue data and methods and examines how UAVs could augment these searches. The basic process is Bayesian, with an initial belief system which is then updated with various different time horizons in mind. As before there are considerations about terrain, paths, undergrowth etc which directly affect how a person might behave.

Terrain mapping

There are three methods outlined which detail how a plan of action is carried out by the various members of a search and rescue team. At this stage these are all scenarios where the UAV has a human pilot controlling it directly (albeit remotely).

Sequential:

• A search plan is designed by a mission planner or director based on initial beliefs
• This is then carried out by an overhead UAV
• Any signs of the missing person are followed up by ground crews 
• If the person isn't found, a new plan is though of and the process begins again

This method is especially useful over inaccessible terrain where a ground team can't easily move to track the missing person on foot, and where the area is very large. 

Remote-Led:

• A ground team performs a search as quickly as possible from the last known location of the missing person, following any clues of their whereabouts
• The UAV is tasked with orbiting overhead and tracking the ground team, extending their effective range of vision
• Telemetry is sent back to the mission director on the ground to further the search

A good plan for cases where the missing person has left evidence of their location or the area is quite local.

Base-Led:

• Bayesian pattern based on waypoints chosen
• UAV carries out pattern sending back data to base. Circles waypoints looking for missing person evidence.
• Ground crew then follows the UAV's search pattern ready to close in on potential signs of missing person, but otherwise remaining central to UAV circles.

Plan works well for easily mobile ground crews who don't have access to enough information to perform a remote-led search.

The paper also outlines in-brief a stochastic approach for modelling likely search positions (essentially calculating the initial probability distribution to then be updated in a Bayesian fashion) by modelling a probabilistic quasi-random walk with functions taking into account terrain direction and environment.

So- what's useful here?

Well clearly I now have a potential new context to think about (radiation or chemical leaks). It might even be worth asking the emergency services what sort of process they would carry out in this case, and then seeing whether it resembled the above at all. The initial probability distribution generation is worth considering as one might potentially have more computing power available (consider calculating it remotely and then transmitting to the UAV?). More broadly, it highlights the need for the consideration of the command structure of an operation when deciding what the UAVs need to do and who they need to report to. In any case, a Base-led or Sequential process for mapping out an emerging pollutant cloud might not be a bad starting point.

-C