So much typing...

Doing corrections day in day out is pretty demoralising... I'm always torn between having noise in the background or seeing if I can concentrate without any. I tend to land in column A. Well in any case it needs doing, and the upside is I've read a decent number of recent papers that are pretty interesting, and one that I can't believe got published. It's a bit surreal seeing a publication that purposely ignores the work of your colleagues (and me too I guess, but I don't imagine I'm very sought-after).

Anyway this paper... let's call it "On decentralized coordination for spatial task allocation and scheduling in heterogeneous teams" because that's its name, is noticeably lacking in any mention of max-sum or its ilk. Very odd given its ubiquity.

Here's one last random thing. Threw these together to back up my literature review: they're examples of belief-data overlaid on spatial maps. It's the kind of thing you can create from crowd reports of building damage and the like, and shows nicely how you could use it to make path plans for a UAV to follow in those cases. There you go.

Belief maps, in various forms

Nearly done

Home stretch...

Updated my website recently to add my publications (two accepted... phew) and I'm a few corrections away from finishing—which is surreal. I think as a treat I'll start writing out my acknowledgements; something I'm taking quite seriously. Acknowledgements sections can be an absolute joy when they're not generic "Ooh I'm ever so grateful to ___ for being nice/reliable/trustworthy/there for me" statements in unending lists. I'd like something more personal than that.

More like this

Well here goes nothing. Oh and if anyone has any advice on how to make this image below more clear, do write in on a postcard.

XKCD's "Simplewriter" presents, my research

The chances are good (since you're reading a blog about PhD research) you're at least vaguely familiar with the excellent xkcd webcomic, and you may know that the creator recently started producing books of labelled diagrams of various types described entirely with only the thousand most-common used words in the English language. If you're not familiar, check this out first. If you are, you'll be delighted to know there's now a simple filter that you can use to try your hand at the art of minimalist explanation. I attempted to explain my research. Here's what I came up with:

My work, using only the the ten hundred most used words in our language: "I am a computer using person, and I work on writing computer-words to make small flying machines (with no person doing the flying) fly around. I want them to fly in a not-stupid way so that if there is a bad event in the world, they can make a group of flying machines and look all over the place where the bad-event happened to find people who are in trouble. They need to be not-stupid so that they find the people quickly, or they might die. It is hard to do because they only have little computers on them and so can't do hard number-work, and they can only talk to other flying machines a little bit (and not all the time). Sometimes there might be a map of where people are and where bad-things are, and we can use this map to help the flying-machines go to the best places where there are people in trouble."

UAV Demo Vid

I made a video. Lucky me! Not much of my work in it, but it was a nice distraction from the day-to-day.

Three Minute Thesis

First, quick thank you to everyone who gave me supportive and thoughtful comments on my last post.

Second, a few months ago I competed in the Faculty of Physical Science and Engineering "Three Minute Thesis" competition, where I had only 3 minutes to outline what I do and what my research represents. I managed to come away with £50 and a second place position, and now (no thanks to the people who uploaded the video without telling me) my little talk is available online. Enjoy!

Latest ideas in brief

In light of the continuing plans for the Mosaic project (check out the new website here) I've been trying to flesh out more of an idea for what I can contribute to this field in the coming years. Thankfully with confirmation from my supervisors that it's not a stupid idea (always worth knowing!) I'm beginning to build more of a concrete plan of what I can (at least try) to implement.

Mosaic project logo. Not representative of our choice of UAVs...

The logic behind it:
It looks very much like the Mosaic demonstrator we're planning for next summer will consist of heterogenous UAVs: specifically fixed wing gliders and some form of 'copters. Given that these clearly have very different capabilities, speeds, durations in the air etc; how best can they act as a team to find the targets in a space? There has been work on this area already, specifically in coalition formation, but there doesn't seem to be much emphasis on a message-passing hierarchy between different forms of UAV. The kind of example I envisage is where a high-level glider does a few passes over a search area and generates some initial guesses for locations of search-objects (in real life, these might be casualties), before passing this on to the lower-level 'copters to deal with in some way, perhaps as a max-sum task allocation since the framework for this already exists. In a non-discretised case, where perhaps it would be best not to treat individual locations as point-like tasks, I'd also be interested in using rapidly-exploring random trees as a basis for working out optimal routes over a probability map produced by the glider to maximise some utility in finding objects.

Animation of a rapidly-exploring random tree. After growth is complete the UAV can pick an optimal path to follow.

Well that's the summary. Now comes the hard part of making all of this actually tenable! Back to work...

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

Some disjointed thoughts on UAV deployment

In lieu of our continuing group efforts to have a separate UAV project which links Orchid work with collaboration with UAV engineers in the University (entitled MOSAIC), I've been scouring papers for various suggestions on how to implement UAV co-ordination in a selection of scenarios.

In essence, since we might end up with a few different scenarios it'd be beneficial if we had a range of options we could refer to in a reference-like way. "Hey! I want to get some UAVs to do this task" says an enquirer. "Ok", says we, "we think This is the best algorithm, for these reasons given your situation, hardware, environment etc etc". Since I'm ideally placed to research existing work in this area I'm trying to start gathering methods, reviews, tests, trials, and all the various pitfalls of different algorithms into a coherent lump that may end up as a literature review.

A couple of papers caught my eye recently in the specific area of search and rescue of a missing person in some given terrain area or wilderness location. While specific, they do list a few useful classes of problem which could be given future thought.

Supporting Search and Rescue Operations with UAVs -S Waharte and N Trigoni

This is a nice paper giving a very broad overview of three approaches to searching for a missing person with an evaluation of their respective efficacy in a simulation. Nearly all such scenarios can be categorised by the exploitation-vs-exploration payoff, which goes something like this:

How much time should I spend searching areas I haven't yet searched, compared to looking more closely at areas I have searched?

Clearly both extremes are undesirable: you would not want your UAV to zip quickly over a huge area and miss the missing person because of lack of attention to detail, nor would you want it to spend four hours staring ever closer at a person-shaped rock.

Like this one, on Mars.

Unlike the Max-Sum utility, the methods here deal only with minimising the time of finding the missing person: a difference in that there is typically only one overriding 'task' (albeit split into possible sub-tasks) for the UAVs to undertake. Nonetheless it is important to consider the algorithms outlined to avoid being funnelled into one specific line of thinking:

Greedy Heuristics
Each UAV maximises its own utility (ie search coverage) in a Bayesian way, developing its own guesses as to the location of the missing person and acting on them. Various methods for route-choosing were explored including those maximising immediate gain and those that actually plan into the future slightly.

Potential Heuristics
Areas of interest are modelled as attractive potentials on a 2D surface, and less accessible areas as repulsive potentials. Force is calculated (as in physics) as the negative of the potential gradient. Potential increases with subsequent visits to discourage loitering, and some message-passing is allowed.

POMDPs
Partially observable Markov decision making problems are a well known branch of decision making in computer science and provide a forward-looking strategy for action based on noisy data which may not actually represent the situation of reality. For instance, the chance of recording a fake positive result is increased with decreased height and the model takes this into account. The question then becomes one of maximising coverage with a view to doing so in future, given uncertainty of existing data. Again some message-passing was allowed, but in a very computationally intensive way: with UAVs sharing their entire belief set periodically when they came in range of another UAV.

Despite the very simple scenario and simulation (only a few tens of square meters of simulated woodland) the tests showed clear advantages to a POMDP method including message passing. A brief concluding thought here is that such a method has two very big problems: a terribly costly message overhead, and required computing power which increases exponentially with the grid size (since essentially every possible path is considered). Possible, but unwieldy without some serious solution space pruning.

More thoughts to follow

-C

Few videos of interest

Couple of interest videos related to decentralised co-ordination (in the second case, there is an overhead from a UAV).


This is a nice talk and demo from Vijay Kumar at the TED talks, showing agile flight control, formation flying and (more interestingly from my point of view) decentralised co-ordination. Definitely worth a read of some papers from here. He talks at one point about disaster relief work although I think the reference is to lower-level building infiltration. The video concludes with the now well-known James Bond theme played by drones.

This second video shows an interesting amalgamation of a flying co-ordinator sending instructions to co-operative ground based agents. I'm wondering if this could be applied to our forest fire scenario where both UAV and UGV agents will be working together. Also, the colour algorithm they demonstrate would surely be improved using simple number-selection and passing algorithms wirelessly, rather than visible light? This will negate the need for line-of-sight visibility as long as each robot can broadcast some kind of identifier.

Food for thought I think.

-C

Disaster news out of Italy

In a pretty shocking turn of events, the BBC today reported that seven Italian scientists have been sentenced to imprisonment for "falsely reassuring" people about the possibility of an earthquake, despite their statements being qualified by the fact that such predictive work is extremely difficult.

I think this is an appalling turn of events which can only damage the resolve of future research into the vital areas of disaster relief and prediction. Certainly if in three years I've managed to make a contribution to UAV co-ordination and this verdict stands, I would feel uncomfortable seeing any project involved in a country which persecutes those trying to act for the public good.

News story here: http://www.bbc.co.uk/news/world-europe-20039769

Anyway, I shall leave it at that, and go and simmer in my outrage.

-C