There's a great question on Quora that asks people to explain their theses in layman's terms. (Every Ph.D. should be expressible in a single sentence, and some of the answers here have this down to a fine art!) It certainly isn't simple to explain where I blew three and a half years of my life, but here's my attempt.
My research answered the question of how you solve problems when the problem itself is changing while you try to solve it. Imagine you're trying to work out the fastest route from one side of your city to the other, but while you're working it out people keep having car accidents that block roads, tow trucks keep clearing previously blocked roads, and the local council is constantly building new roads (really really quickly!) Adding to that, even when you've worked out what you think is a good route, while you're driving it the roads are still changing constantly.
My work showed that in most interesting applications of this problem (not just roads and driving, it applies in lots of other contexts as well), the time you spent working out a solution is quite large. If you want the 'perfect' solution, it could be so large that you would have been better off to drive a slower route but not spend so much time thinking about it in the first place.
I found a way to quantify all these factors, and a way to solve what you really want; not "find me the fastest route across the city", but rather "get me to the other side of my city as fast as possible". I was also able to prove that my method was guaranteed to be at least as fast as any other method, and most of the time was much faster.
Oh yeah, and I built a robot to do the driving... :-)
My research answered the question of how you solve problems when the problem itself is changing while you try to solve it. Imagine you're trying to work out the fastest route from one side of your city to the other, but while you're working it out people keep having car accidents that block roads, tow trucks keep clearing previously blocked roads, and the local council is constantly building new roads (really really quickly!) Adding to that, even when you've worked out what you think is a good route, while you're driving it the roads are still changing constantly.
My work showed that in most interesting applications of this problem (not just roads and driving, it applies in lots of other contexts as well), the time you spent working out a solution is quite large. If you want the 'perfect' solution, it could be so large that you would have been better off to drive a slower route but not spend so much time thinking about it in the first place.
I found a way to quantify all these factors, and a way to solve what you really want; not "find me the fastest route across the city", but rather "get me to the other side of my city as fast as possible". I was also able to prove that my method was guaranteed to be at least as fast as any other method, and most of the time was much faster.
Oh yeah, and I built a robot to do the driving... :-)
In a lot more detail, here's how the technique actually works. (And I'm not just being self-indulgent here - somebody actually asked for this...) Everything comes down to time. If we stick with the driving example that'll help. What you really want is to get to the other side of the city in the shortest amount of timing, starting RIGHT NOW!
Let's focus on just the one decision point right at the start - whether to set off instantly on a beeline for your destination, or to sit and plan a better path for a few minutes and then set off. Let's use some easy numbers and say it's 100 minutes drive across the city via the best route, and 200 minutes via the worst route (the one you can calculate instantly.) Let's also say it takes 20 minutes to calculate that best route.
Your two options are:
a) Planning time of zero, plus driving time of 200 minutes = 200 minutes.
b) Planning time of 20 minutes, plus driving time of 100 minutes = 120 minutes.
Obviously, b) is the better option. But actually, this isn't just a binary decision. There are many other options in the middle ground. (Straying away from common parlance, there's a class of algorithms called anytime planners that help find these middle points.) Often, problems turn out to have a solution that takes perhaps 1 minute of calculation time, but results in a driving time of 101 minutes. So, it's not the best route, but the total time is 102 minutes which is better than the total time for the best route. (In technical language, this is the Pareto optimal decision.)
The key point is that the "best" route is not the best route when you take the planning time into account. (Except when it is. But that doesn't happen much in practice!)
Ok, let's step it up a notch. There's actually a catch here too - assessing all the possible points on the spectrum between the worst and best routes also takes time. Let's call that the Decision Making time. Since that counts for the total time too, you'll need to minimise it as well, which might mean that it's better to only think about perhaps 5 options, rather than 50.
Perhaps...
Alternatively if the right option was one of the 45 you didn't consider, then maybe it would have been better to spend the Decision Making time to find that option, and then ... ARRRGGGHHH!!!
If you're thinking this is all getting a bit meta, you're exactly right. This class of problems is called Meta-computing.
Ok, let's step it up yet another notch! In the driving example I discussed in my answer, the roads keep changing while you're driving. Ignoring a few of the less interesting considerations, this effectively means that you have to go through the same decision making process all the bloody time!
So the best you can do is to start moving (as long as it's in roughly the right direction) and keep adjusting your route while you're driving. Whenever you settle upon a new choice of route, start driving it, and simultaneously start thinking about what you might want to do next. Do that until you reach your destination, at which point you can collapse in an exhausted heap, completely unable to think of anything else. Why did you need to drive there again?
In terms of what you actually need to do with all the choices you make, it comes down to the problem at hand. First you guess how much Decision Making time to spend, then you spend it evaluating the options - which involves guessing how much Planning and Driving time each option will require. Then, you pick the option you've guessed is the best, and you start planning it. Finally, you take the plan and start driving it. Then you repeat.
It's at this point that you re-read that last paragraph and ask "so what's with all the guessing?" Well, unfortunately, reasoning about time is reasoning about the future. You don't know how long something is going to take until you've actually done it, by which point it's too late to use that information because you've just done the thing you had to do to get the time it was going to take to do the thing you were just having about to had been done. I think...
The only solution to this is to guess. Much of the contribution of my thesis was designing and testing a whole bunch of different ways of doing these guesses.
In the end, what you can say about this technique is that it is guaranteed to be no worse than any other technique that has access to the same information. I proved that. It probably doesn't sound like much, but it's actually very important because a lot of the time you're actually much better than other techniques if you use my technique. And since you're not going to be worse, you might as well use mine, just in case it's better!
So that's the common parlance explanation. In mathematical terms it's:
where y* is the optimal set of parameters to apply to the system out of the set Y of all possible sets of parameters, and the 't's are the Decision Making, Planning, and Driving times respectively, summed over all future time until the destination is reached.
Let's focus on just the one decision point right at the start - whether to set off instantly on a beeline for your destination, or to sit and plan a better path for a few minutes and then set off. Let's use some easy numbers and say it's 100 minutes drive across the city via the best route, and 200 minutes via the worst route (the one you can calculate instantly.) Let's also say it takes 20 minutes to calculate that best route.
Your two options are:
a) Planning time of zero, plus driving time of 200 minutes = 200 minutes.
b) Planning time of 20 minutes, plus driving time of 100 minutes = 120 minutes.
Obviously, b) is the better option. But actually, this isn't just a binary decision. There are many other options in the middle ground. (Straying away from common parlance, there's a class of algorithms called anytime planners that help find these middle points.) Often, problems turn out to have a solution that takes perhaps 1 minute of calculation time, but results in a driving time of 101 minutes. So, it's not the best route, but the total time is 102 minutes which is better than the total time for the best route. (In technical language, this is the Pareto optimal decision.)
The key point is that the "best" route is not the best route when you take the planning time into account. (Except when it is. But that doesn't happen much in practice!)
Ok, let's step it up a notch. There's actually a catch here too - assessing all the possible points on the spectrum between the worst and best routes also takes time. Let's call that the Decision Making time. Since that counts for the total time too, you'll need to minimise it as well, which might mean that it's better to only think about perhaps 5 options, rather than 50.
Perhaps...
Alternatively if the right option was one of the 45 you didn't consider, then maybe it would have been better to spend the Decision Making time to find that option, and then ... ARRRGGGHHH!!!
If you're thinking this is all getting a bit meta, you're exactly right. This class of problems is called Meta-computing.
Ok, let's step it up yet another notch! In the driving example I discussed in my answer, the roads keep changing while you're driving. Ignoring a few of the less interesting considerations, this effectively means that you have to go through the same decision making process all the bloody time!
So the best you can do is to start moving (as long as it's in roughly the right direction) and keep adjusting your route while you're driving. Whenever you settle upon a new choice of route, start driving it, and simultaneously start thinking about what you might want to do next. Do that until you reach your destination, at which point you can collapse in an exhausted heap, completely unable to think of anything else. Why did you need to drive there again?
In terms of what you actually need to do with all the choices you make, it comes down to the problem at hand. First you guess how much Decision Making time to spend, then you spend it evaluating the options - which involves guessing how much Planning and Driving time each option will require. Then, you pick the option you've guessed is the best, and you start planning it. Finally, you take the plan and start driving it. Then you repeat.
It's at this point that you re-read that last paragraph and ask "so what's with all the guessing?" Well, unfortunately, reasoning about time is reasoning about the future. You don't know how long something is going to take until you've actually done it, by which point it's too late to use that information because you've just done the thing you had to do to get the time it was going to take to do the thing you were just having about to had been done. I think...
The only solution to this is to guess. Much of the contribution of my thesis was designing and testing a whole bunch of different ways of doing these guesses.
In the end, what you can say about this technique is that it is guaranteed to be no worse than any other technique that has access to the same information. I proved that. It probably doesn't sound like much, but it's actually very important because a lot of the time you're actually much better than other techniques if you use my technique. And since you're not going to be worse, you might as well use mine, just in case it's better!
So that's the common parlance explanation. In mathematical terms it's:
where y* is the optimal set of parameters to apply to the system out of the set Y of all possible sets of parameters, and the 't's are the Decision Making, Planning, and Driving times respectively, summed over all future time until the destination is reached.
RSS Feed