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!

2013 in ... one post?

Whoops. So it seems I've managed to neglect this blog for almost an entire year. Not intentionally of course, it's just other things seem to take precedent. Anyway a bunch of progress is being made both in my own tiny little section of the UAV-algorithm field, and with UAVs as a whole.

My Stuff
Post progress-report (not transfer thesis: that's next year) I've been thinking more about what first responders actually want or need in a disaster situation. I had set up a meeting with Rescue Global (a sort of... real-life International Rescue) but they had to cancel after needing to dash off to the Philippines. As excuses to miss meetings go, I think "biggest Typhoon in history" is one of the better ones. Hope all is well out there.

I honestly would love to know that work I've done could help in these sorts of situations. Source: Dailymail

Anyway, I came across this interesting assessment from the Red Cross which outlines a bunch of goals and implementations of what is done/what needs doing after a disaster strikes. This actually helped me solve a key question in my work, which goes something like this:

If you're REALLY sure that there's people, in a location, that need help, do you need to bother sending a UAV for imaging anyway?

Put another way: are we taking images for the sake of it, or to work out where people are? Because if it's the latter you can actually ignore parts of the map where you're certain there are people, since you know already.

It turns out, from the wording of the report, that there's merit in imaging anyway: the wording suggests emergency responders value being able to see and assess what situation the victims are in even if they know in advance where they are. That makes sense to me, since it might inform what sort of response is needed (helicopter? boat? ground crew?).

Anyway my ideal system for controlling the UAVs now works something like this: Given an area, with some sort of prior belief of where people are, and some sort of belief about what danger they're in (quantified as an expected death-rate), and given that taking images of these people will let them get rescued more effectively, what's the optimum route to travel around the space, taking pictures, with multiple UAVs, to minimise the overall death rate?

I think the main motivation for phrasing it like this—apart from the fact no-one has done it before and PhD (if nothing else) is supposed to break new ground—is that I'm keen on producing something which is actually practical and useful, and not just an interesting exercise in computer science. I'm increasingly convinced that the idea of discretising the needs of disaster workers into "tasks" is not particularly reflective of the more cohesive picture that can be painted of a disaster area.

Anyway the exact mechanism for this has yet to be decided, but it'll probably be some sort of Monte-Carlo Tree Search with factoring to account for UAV co-ordination. So here's hoping for a paper early next year.

Other stuff
Seems that UAVs have made the news in a few places recently. There's the RAF trying to soften their image as all-purpose killing machines in this BBC article for a bit of interest. Much more bizarrely, there's the recent revelation that Amazon are thinking of using UAVs to deliver packages:

In news next year: People now hunting for Xboxes using rifles. Source: Amazon

On our end, we've also had the Beeb round to film some of our stuff for an upcoming episode of Bang Goes the Theory. I'll post the link up here once it airs, and I might even be in the background. Somewhere. Very briefly.

Anyway there's more out there if you look for it, and it seems UAVs are going to be big business in years to come. Hopefully that'll mean more cheap drones for us to buy and test on :)


I promise I'll be better at updating in the New Year. It'll be a resolution. Or not, since those are so often discarded. Anyway until then, have fun and enjoy your not-yet-delivered-by-drone presents!

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

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

Disasters: the UN report

Been very busy recently. It looks like our group is going to have an independent team looking at UAVs (which is cool). Anyway I've spent some time recently going back-to-basics and having a glance at disaster relief papers to see what sort of requirements might be needed (see my last post).

As a quick addition, here's a nice quote form a UN paper on the issue:

High-resolution imagery—defined here as being able
to see to the level of one meter—has not traditionally
been available at the field level for operating agencies
immediately after a disaster. Imagery can be critical to
making operational decisions, especially in regards
to logistics. But imagery also is time consuming to
process and analyze—a task for which field staff has
precious little time. During the response to the 2004
Indian Ocean tsunami, the UN staff in Aceh had asked
for detailed imagery of bridge outages so that they
could design supply chains around the island. They
had also requested nighttime infrared imagery of the island, hoping that heat of campfires and congregations
of (warm) people would help the UN identify where the
populations of destroyed villages had moved. While
they eventually received some imagery, they never
received a data set that answered their operational
questions.

In the Haiti instance, these images were provided from satellites and overflights, but the requirement for imagery is clearly a vital one, lending credence to the use of UAVs in this way.

Disasters: how to make them less disastrous

It occurred to me yesterday that before coming up with too many esoteric ideas on how to extend the capabilities of a Max-Sum co-ordinated swarm of UAVs, it might be an idea to see if I can find out exactly what first responders might be interested in; and what they need in a disaster area.

To that end, I found a report commissioned in the wake of the Haiti earthquake (see it here) about lessons learned and problems which need addressing. The paper is very broad in scope and deals  in large part with the reconstruction and long-term aftermath of the event, which is not relevant to what I'm studying. There were a number of discussions on the general structure of the relief effort: which is relevant in the sense that it's important to know who might actually be using the final product. It seems that typically relief work is separated into 'clusters' of people who are responsible for certain areas: eg. food, medicine, reconstruction etc etc. They also specifically refer to the work done by ground first responders (USARs) who; in the Haiti case; were grouped into 53 teams which managed to save 211 people.

53 teams inputting different tasks into UAVs would be quite a large task:agent ratio, if one imagines there might be ten or so vehicles in the skies. Clearly this ties in to remarks I read in the earlier paper on extending flight tests to domains where the number of tasks largely outweighs the number of UAVs.

On the software front, it seems language considerations could play a surprisingly important role in rolling out the PDA applications to communicate with the UAVs. Apparently there were even protests against some foreign aid groups who the locals felt were ignoring their cultural and personal considerations. "Ownership" of a relief effort is highlighted as being valuable. In such a case it would make sense that the local first responders (and not just English-speaking international workers) would be able to use the system.

Another software consideration is a system called OneResponse which has been developed as a website to centralise data collection in disaster relief. Basically this was motivated by scattered data being available to different groups in an uncoordinated way in previous scenarios. A centralised repository such as this might be a valuable way of allowing additional parties access to valuable data collected by UAVs.

As much as the paper was a little broader in scope than I was hoping for, it did spur a few ideas about possible utility of the UAVs. Indeed: a section mentioning that initial imagery is currently collected via satellite certainly suggests close-in higher resolution data would be useful. It also got me wondering about the exact nature of the images being collected; would it be worth giving a responder direct control once the UAV was over a target? That way things like angle, and altitude could be adjusted to view things in more detail or more clearly at the discretion of the responder. Something to consider, I think.

-C

Paper: Max Sum algorithm on UAVs. Delle Fave et al

Fully titled: Deploying the Max-Sum Algorithm for Decentralised Coordination and Task Allocation of Unmanned Aerial Vehicles for Live Aerial Imagery Collection

This was the first paper I was asked to read, mostly because it provides a pithy overview of what's so-far been achieved in the field of UAV co-ordination in disaster relief. The content of this post may vary between technical discussion and general overview so I apologise in advance if it seems a bit two-toned. 

The paper introduces a method called the Max-Sum algorithm as a way of co-ordinating UAVs as required, and outlines its virtues. It then mentions several results in simulations before showing some empirical examples from a real-world demonstration involving two hexacopters. 

Picture of a hexacopter from the paper in question

I already mentioned in the introduction a bunch of the challenges of co-ordinating the UAVs (or rather, allowing the UAVs to co-ordinate themselves). The paper re-iterates these and adds that existing co-ordination methods and algorithms don't address the uncertainty of a task's completion: obviously if a UAV fails, if the task changes, or if the emergency services require a different task to take priority this could potentially be a big problem for real-world applications. A first responder isn't going to know precisely how long they require imagery from a location. It could depend on what they see in the first place.

Addressing the problem of the de-centralised nature of the system (ie. no central computer: all shared out) the paper notes that they've included the computing power of the first responders' PDAs in order to help the calculations. Since the imagery will be sent directly to the PDAs, they'll have to be in communication with the UAVs anyway so this seems sensible. 

Max Sum

The best way of beginning to find a solution to a problem like this is to express it mathematically. To that end, the authors of the paper present something called a "Utility function", which essentially gives a numerical value to a task which might be attended to by a UAV. The higher the number, the better. In principle one can imagine the UAVs working out all of these values for every task they can go to, and then working out how to get the highest overall number for the whole system. 

Simple example where each UAV can attend one task

Max Sum is a message-passing algorithm which allows this to happen through UAVs passing messages to their nearest neighbours. As such, no single agent knows the whole "picture"- but by knowing how they affect the system they can all work out the best course of action. 

Explicitly, the paper describes the Utility function of a task i for all agents (UAVs) which can attend the task x_i:

The first two terms codify the priority and urgency of the task at hand (the urgency being dependant on the submission time and the current time). The last term in brackets is the solution to a probability function describing how likely it is that the UAV's battery will run out during the task. The reason this can't be stated exactly is that the paper is enforcing the condition that it's impossible to know in-advance exactly how long a task will take. 

With the utility function designed, the Max-Sum implementation involves the passing of limited messages between 'functions' and 'variables'; which in this case are the PDAs and UAVs respectively. Messages from variables to functions take the form of "here's the maximum values the rest of the system can achieve for the possible task allocations, if you take one of a number of options". For example, if there are three tasks, the variable (UAV) will tell the function (PDA) the maximum utility values for the rest of the system for each possible task assignment of whatever other variables the function is attached to.

The messages from the functions to the variables are similar in the sense that they return values corresponding to what task is taken by the variable they're attached to, and they give the maximum possible utility that their variable can produce. 

By adding together incoming messages, variables reach the stage where they have a series of 'maximums' for each available task that they can undertake. They then choose the highest value available to them. For example if a variable receives messages from all its neighbours for three tasks giving the maximums as (2,19,8) for tasks 1,2 and 3 respectively, then the variable (ie. the UAV) will move to task 2 regardless of what its own individual utility for the task is.

This happens continuously, with the UAVs updating what they're doing all the time. It also doesn't have to happen in a particular order, as UAVs will change their behaviour as soon as information is available to them. That's a particularly non-rigorous explanation of Max-sum and I fear I've grossly understated its utility and robustness for this kind of situation.

Results

Simulations in the paper dealt with a few different scenarios including some where parts of the utility function were left out- for instance some scenarios ignored the urgency of a task. Those experiments where the total function was used produced better results in returning high-priority tasks and avoiding running out of power mid-task. This is important information as it confirms the viability of using this sort of method in real situations where everything needs to be considered. 

Finally empirical evidence is shown of real UAV flight tests conducted in Australia where two UAVs faced three different scenarios: two tasks at the same time, two tasks arriving one after the other (the second with a higher priority), and a situation with three eventual tasks but where one UAV doesn't know about one of the tasks. In brief, the UAVs conducted the tasks properly. A video can be seen here which includes a quick overview of the simulations too. 

Thoughts

Most of the paper seems pretty straightforward and with a  bit of extra reading I'm fairly happy I understand the Max Sum algorithm; which is good since it seems to form the backbone of this project. The videos of the real UAVs is nice as it presents things in a very obvious and straightforward way, but it does raise a few questions. Firstly I'm curious why in the examples the UAVs don't follow a straight path to the tasks, but rather 'wiggle' their way there. It would be interesting to find out if this is a result of the algorithm itself or something to do with the UAVs' hardware. Another curiosity is that for the second example the UAVs actually swap over mid-way to moving to their tasks. Initially they move to the closest target (which makes sense) but thereafter they swap over before settling over the target. 

Possibly, this is because of the battery-life aspect of the utility function (which isn't obvious just from looking at the video), since the only other factor is really the distance to the target. If the battery life was not a  factor this suggests something funny going on with the algorithm that isn't at all intuitive.

The paper finishes suggesting that the scenario needs to be extended to more complex systems with more UAVs: something I'd be very keen to be involved in. 

-C

Welcome and introduction

Hello internet, and welcome to a humble blog about my life as a PhD student, which should hopefully contain a great deal of thoughts and musings on the work I've got myself into for the next three years. The purpose of this is twofold: firstly, this provides me somewhere to share what I understand from reading and learning about the algorithms I'm supposed to be dealing with: and by extension a place for people to tell me how wrong I am. Secondly in the unlikely event you have a vested interest in my life you can use it to keep track of what I'm doing over the next few years.

As a brief summary overview, following my graduation with an MPhys in Physics, I'm now being funded for a PhD in computer science from something called the Orchid Project. This is a big collaboration of companies and Universities which work together in three specific areas of computer science, under the broad umbrella of "Agents".

I have to admit I had no idea what an "agent" was until I went to a seminar on available PhDs. In broad terms, as I understand it an agent is essentially a distinct unit of computation which can act independently and (in the sense that they can be intelligent) autonomously to achieve certain tasks in an environment, and in the presence of other such agents. This actually makes the field extremely broad: covering things from smart-thermostats or forms of bidding software, to fully fledged autonomous unmanned-aerial-vehicles (UAVs).  Specifically Orchid focusses on Smart Grid (energy distribution) work, Citizen Science (which involves crowdsourcing), and Disaster Relief. It was this latter area which piqued my interest; not least because the method they plan on using involves deploying intelligent agents in the form of UAVs to assist first-responders and emergency services in disaster situations; for example earthquake zones.

Orchid is looking to have the UAVs act autonomously: removing the need for that clunky remote control.

The ultimate goal looks something like this: in the event of a disaster, a fleet of UAVs is deployed into the sky above the area. Thereafter, emergency services will have a PDA or smartphone app of some sort, with which they can request imagery of a particular area from the UAVs (which are equipped with cameras), whilst also specifying things like urgency and duration required. This information is sent to the UAVs who then act autonomously to work out between themselves which vehicle goes to which task such that they achieve the best overall coverage that the emergency services need. Clearly they need to co-operate to achieve this.

This is no simple task, for a couple of reasons. Firstly, a great deal needs to be taken into account before simply deciding that UAV 1 will go and look at task 1. Obviously distance to the target is a factor, as well as the task's urgency, priority, and duration. Then there's the issue of battery life, ie. is it possible for the UAV to complete the task before running out of juice? Is it better to send 2 UAVs to the same task to try and maximise effectiveness?

Considering how tricky this exercise would be on paper, implementing them on UAVs is quite a challenge. The vehicles aren't exactly equipped with supercomputers, so computation has to be kept to a fairly simple level. There's also no central-computer to which they all connect. This means they can only compute by talking to each other; and of course the number of available UAVs, tasks, and PDAs is changing all the time. It's not good enough to make a decision and carry it out: the UAVs have to constantly update and check on what else is going on.

Anyway: co-ordinating the little beasts being the ultimate aim, there are (thankfully) some useful existing methods for getting them to work together nicely. I'll go into them in the next post. For now: that's what I'm hoping to contribute to. Let's see how it goes.

-C