DrTomAllen.com
tom@jugglethis.net
  • Dr Tom
  • Now
  • Consulting
    • Testimonials
  • Robotics
    • Publications & Videos
  • Startups
    • Cubescape
    • Triple Point Robotics
  • Game Design
    • Bounces
    • Dodgy Wiring
    • Half the Battle
    • Road to Nowhere
    • Summon the Swarm
    • Evil Robots
    • Spelled
  • Blog

Solving problems that change while you're solving them.

7/7/2014

 
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... :-)
Picture
Picture
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.

Why I Quit My Job, Killed a Company in Six Weeks, And Still Feel Great!

7/8/2012

 
Picture
This was my last job. That's me, in a helicopter, telling an eight-wheeled killer death robot what to do. And getting paid handsomely for the privilege.

It was awesome! So why the hell did I quit?

Well, I had an itch. I thought I wanted to start a company and ride the coming robotics revolution to fun and profit. The reality was something quite different to that, I just didn't know it at the time. Everybody I knew (and I really mean everybody) advised me that this was foolish. That I had a four month old child to support and a wife who wasn't working. That I had a mortgage to pay. That I had a seriously awesome job and an obvious career path into one of the largest and highest paying companies in the country. That the startup lifestyle is hard work, stressful, and nine times out of ten - fails.

They were all right, but I couldn't listen. I had to learn this lesson for myself.

Picture
So I started a company (well, actually, we didn't get around to incorporating it, which turned out to be a good call) with two friendly colleagues, quit my job, and didn't think much about step two. We had some plans for synchronised collaborative whiteboards, and started plotting how to get funding to make this happen. We approached a business incubator who were very keen on us, less keen on the idea, but put in a lot of their time getting us to take a customer development approach.

We did, and it was horrible. Over the next three weeks we talked to lots of potential customers - less than our advisers wanted, but more than enough to discover that our product was too expensive for the marginal improvements over related products. We moved onto product number two, followed the same approach but faster, and found the product to be less useful to people than we'd thought it would. At this point, one of my co-founders decided he'd have much more fun just building things without worrying about whether or not they'd make money, and promptly left.

Product number three actually had a lot of interest. We found a great niche of customers with a big problem, and our product would have fixed it beautifully. Unfortunately, despite the customer development process looking good here, from a product point of view we concluded we couldn't make it cheap enough. (On the up side, in a few more years time all the components should be cheaper and better, so its something worth revisiting in the future.)

After three rounds of this disappointment, my remaining co-founder lost interest and went AWOL. I can't blame him. I'd sold the vision of an awesome startup company building amazing technology and enjoying the process. Instead we'd experienced what is likely much more typical; hard work, disappointment, and not much to show for it other than the knowledge that it was better for these ideas to fail sooner rather than later.

At this point I burnt out. In true burn out fashion I didn't realize this, and kept pushing on with coding, meeting people, talking to customers, and the like until my body engaged in a cunning plan to weaken my immune system and make me get sick so I'd stop. It took a full week of not doing anything at all before I realized what should have been obvious at the outset: I don't care enough about money to run a startup business.

I want to work on cool, innovative, novel, and exciting projects with interesting, motivated, and motivating people. Provided I can earn enough by doing that (and enough isn't even that much in the grand scheme of things) I'm not too bothered whether I work for myself or for someone else.

This begs the question however; why did I quit a job that met all these criteria? The easy answer is that I knew I didn't want to be an academic. But since the job was a stepping stone to a similar, higher paying job in industry, there's a more complex answer hiding away in here somewhere. Ultimately, I think it's that I want to move a bit faster, have more opportunity for learning, and to see my work get used by real people. Academia is slow, procedural, and if more than ten people care about your work, you're probably doing well. As an example, since quitting my job, a paper I wrote eighteen months earlier has only just been accepted.
This whole post has told the story through a lens of failure, but that's not the only way to read it. I recently stumbled upon Robbie Abed's article on how to find your dream job. Roughly summarised; quit, start a company, expect it to fail, tell everyone about it, build a new network, talk up your product (not yourself), help people out, and finally "Accept Failure. Ask For Help." Sure, I didn't set out like this, but if I tell this same story through that lens instead, then I'm already up to step eight and ready to rock whatever opportunity comes knocking.

Maybe it's your company - if you need an inventive, capable, problem-solving engineer, get in touch.

Stop Anthropomorphising Design

10/5/2012

 
Picture
Anthropomorphisation is the attribution of human-like qualities to another thing. People often do this with robots, saying things like 'it wants to drive over there' or 'it saw me and turned around!'. When this happens naturally it can be a great indication of user friendly robot. But note that it happens when the robot is in the hands of end users. By contrast, anthropomorphisation of design happens at the beginning of a project. The concept crops up in design and engineering all too often in the guise of 'well this is how humans do X, so our system should emulate that'. In many cases, and especially so in robotics, this is a bad thing™.

Why? Because it limits the space of possibilities that the designers might consider, and worse, it leads to systems that fail to exploit their strengths and instead compete with the strengths of a completely different system.
As an example, someone commented recently on an IEEE Spectrum article about Google's autonomous vehicles: "No doubt it's a great step ahead in automation... but but but. Something is wrong.. because ... We [Drivers] has no computers in our heads, so we don't measure lengths, compute logarithms nor adding two numbers when we drive."

In all fairness, this commenter might not have been an engineer or designer, but this is backwards thinking. And on the Hacker News post about the same article, more people suggested that Google's team should focus on visual sensing, with such comments as "the technology is impressive, but humans drive okay without LIDAR, radar, or GPS." (Again to be fair, this commenter clarified his thoughts later, pointing out that he meant they should look at visual sensing as well.)

Fortunately, Sebastian Thrun and his team are designing an autonomous vehicle to drive at and beyond the abilities of a human. They are not designing an autonomous vehicle to mimic what a human would do. They realise that computers are incredibly good at computation over massive amounts of data, and pretty lousy at almost everything to do with vision. Humans are pretty slow at calculations, but our eye/brain combination is amazing at spotting patterns, detecting changes, and spotting moving objects in clutter. So Thrun's team plays to computers' strengths - they pre-scan the world ahead of time (incidentally this is a very smart move by Google - their competitors will struggle with the scale required to do this) and then have the two comparatively simple jobs of working out where their current sensor picture fits into that map, and what the differences are. They don't use visual SLAM, they use a particle filter and (as far as I can tell), ICP for scan matching - computationally intensive, but again, playing to their strengths.

This is just one example, but this kind of thinking turns up again and again. When we talk to customers about mobile robots in their homes, and mention that we have a very neat omni-directional wheeled platform, they often ask why we're not using legs to avoid the dreaded stairs problem. This is constrained thinking, led by anthropomorphic tendencies. Why are legs the first solution people think of? Why not flying robots? (don't laugh too hard - four out of the first fifty people we spoke with suggested this! Relax, we're not going there...) Why not a flexi-track like a packbot? Why not a stair lift? Why not just bank on robots being cheap enough to have one on each level?

Picture
Humans work well with legs, machines don't. Don't ignore wheels just because nature did.

And that's the take-away message from all this: play to your strengths. Don't emulate nature unless your system is well suited to doing so. Stop anthropomorphising design. 

    This blog is very seldom updated. Having kids will do that.
    ​

    Archives

    October 2022
    August 2021
    October 2019
    June 2019
    February 2016
    July 2015
    July 2014
    June 2014
    February 2014
    October 2013
    September 2013
    May 2013
    April 2013
    March 2013
    November 2012
    September 2012
    August 2012
    June 2012
    May 2012

    Categories

    All
    Coffee
    Hacking
    Programming
    Projects
    Rants
    Robots
    Startups
    Thoughts

    RSS Feed