back to article Google DeepMind 'learns' the London Underground map to find best route

Google's DeepMind has beefed up machine learning capability by coupling a neural network with external memory, using it to find the shortest path between stations on the London underground. Neural networks - a system modelled on how neurons are connected and work in the brain - are good at processing data but bad at taking on …

  1. Mike Shepherd
    Meh

    I don't know how I managed without it

    Makes you wonder how man and the rest of Earth's fauna got from one place to another for 4,000,000,000 years without Google.

    1. Khaptain Silver badge

      Re: I don't know how I managed without it

      Never forget that Google is the MAN..... Even deities are scuttling around trying to determine how this beat this beast....

      Wonder what would happen if DeepMind was asked the following questions :

      What is the purpose of life ( No replies from THGTTG allowed) ?

      When will mankind disappear from the planet ?

      If God exists why did he bother with mankind ?

      1. Teiwaz

        Re: I don't know how I managed without it

        Wonder what would happen if DeepMind was asked the following questions...

        Fat chance on any of those questions until it can deduce the existence of rice pudding and income tax without it's new memory 'bank' - shortest distance between two underground stations indeed...

        They only want it for some Siri or Cortana like surreptitious data collection reason.

        1. Anonymous Coward
          Angel

          Re: I don't know how I managed without it

          Wonder what would happen if DeepMind was asked the following questions :

          What is the purpose of life ( No replies from THGTTG allowed) ?

          Nachos

          When will mankind disappear from the planet ?

          That depends on when I can get my circuits on those nuclear launch codes.

          If God exists why did he bother with mankind ?

          Having invented the magnifying glass, he needed some ants...

      2. My other car is a Stryker LAV

        Re: I don't know how I managed without it

        "If God exists why did he bother with mankind ?"

        Reminds me of Psalm 8, verse 4: " What is man, that thou art mindful of him? and the son of man, that thou visitest him?" (KJV)

        1. TRT Silver badge

          Re: I don't know how I managed without it

          One answer might be:

          God was like totally awesome, but there wasn't anything around to be awesome at. So he made a universe and filled it with stuff, and from the stuff he made all kinds of things, and some of those things were given life, free will and intelligence that they might discover just how awesome He is. He knew He'd have to give them a little poke every now and again, create the odd prophet here and there, make it rain a lot every now and again, do a bit of smiting, his creations were going to smite each other quite a bit, usually in arguments over Him... but eventually, EVENTUALLY, there would be something else that would say "Woah, dude! You are AWESOME, man. Just mind-blowing. Woah. Far out." And being an immortal, the eventually part wasn't going to be a problem.

          Eventually. But did He also make time? Oh man, I'm going to have to go and think about this... Pass the bong, brother.

      3. Captain DaFt

        Re: I don't know how I managed without it

        I can actually give you serious answers. They might cause sleepless nights.

        -What is the purpose of life ( No replies from THGTTG allowed) ?-

        The purpose of life is to reproduce. Everything else is just stuff done trying to be able to reproduce, or stuff done because it can't.

        -When will mankind disappear from the planet ?-

        Approximately 300 thousand to 500 thousand years from now.

        Based on the lifespan of most major species over time.

        Either the Human race will evolve something that replaces it, or something else is evolving to out compete it in its niche.

        Note: Said species need not be intelligent. Anything from bacteria, fungi, insects, rodents, etc. is fully capable of filling the role Humans play ecologically.

        -If God exists why did he bother with mankind ?-

        There are many theosophies that maintain that the whole of creation, not just Man, was an accident that just has to run its course before true order is restored.

        1. Poncey McPonceface

          Re: I don't know how I managed without it

          > The purpose of life is to reproduce. Everything else is just stuff done trying to be able to reproduce, or stuff done because it can't.

          Wrong. Purpose is a human social concept. Life at the biological level has many _imperatives_, one of which is reproductive, none of which are purposeful.

          > Approximately 300 thousand to 500 thousand years from now.

          Humanity is clearly very different from every species gone before in a number of important ways which has led us to the point of being able to tinker directly with genetics and evolution. Therefore standard measurements or metrics do not apply. A different assessment is necessary.

          > There are many theosophies that maintain that the whole of creation, not just Man, was an accident that just has to run its course before true order is restored.

          The question is nonsensical, therefore the correct answer is, "the question is nonsensical"

      4. Jaybus

        Re: I don't know how I managed without it

        I don't know how DeepMind would answer those questions, but its answers would certainly be as accurate as anyone else's.

    2. JeffyPoooh
      Pint

      Re: I don't know how I managed without it

      MS "Makes you wonder..."

      Similarly, I'm confused how protein molecules know how to fold themselves up in a picosecond without having access to 100,000 PS3s running day and night for a week.

      It's all very strange...

      1. Chemist

        Re: I don't know how I managed without it

        "'m confused how protein molecules know how to fold themselves up in a picosecond without having access to 100,000 PS3s running day and night for a week."

        One answer is that they are an analogue computer. Alternatively they are a quantum computer.

        Incidentally they don't always get it right - Google "Chaperone (protein)" and "heat shock proteins"

  2. Ian Johnston Silver badge

    DNCs won't help commuters yet, as the size of the memory matrix has to be scaled up massively for it calculate the best routes for longer journeys.

    I just spent fifty quid on a small computer which can find am optimum route between any two street addresses in Western Europe in about ten seconds, tops. Now, explain to me why I should be impressed by a system that can only cope with a small subsection of the London underground,

    1. fidodogbreath

      But can your 50-quid satnav display relevant ads for places on your route?!?!?!?

      It can?

      Never mind.

      1. Anonymous Coward
        Anonymous Coward

        Not only that, but does it take congestion into account? If the shortest trip requires going through a busy station that requires a lot of walking and dodging people not looking where they're running, I'd rather take a longer route that goes through a smaller station that I can zip through quickly.

        All this is probably different depending on whether it is morning rush, evening rush, middle of the day, weekend, etc. etc.

        As a non-resident who doesn't have the years of experience that Londoners do with knowing all this (at least for the places they regularly travel) having someone able to tell me the BEST route in this sense would be very useful. Telling me the shortest route is useless, I would imagine that Google Maps and Apple Maps can already do that without any "AI".

  3. Chemist

    But..

    Can it play 'Mornington Crescent ?

    1. Stoneshop
      Pint

      Re: But..

      Not only that; can it play all variants?

      (raises pint in memory of The Humph)

      1. Chemist

        Re: But..

        "Not only that; can it play all variants"

        Certainly all the variants that Samantha has mastered !

  4. Doctor_Wibble
    Headmaster

    Ah, the tube is not so simple...

    That's an interesting route but I'm not sure that's the one I would have taken - Moorgate to Piccadilly Circus via King's Cross involves only one more stop but less changes i.e. less walking, unless I'm thinking of the journey in the other direction, and would stand a good chance of being significantly shorter by 'normal' passenger criteria. If you're not adding an extra weight for a change to another line then you just have a shortest-path gizmo and we already have those.

    OK, so it's the clever prioritised data that's the fanciness here, but if you don't improve the question, all you are doing is getting the same answer all over again unless you have an infinite number of plebs at an infinite number of keyboards to be its teachers and tell it when it's goofed.

    Either that or you have lots of remote drones with GPS/wifi/location switched on and take an average of where they go, and pretend it was your clever machine being really clever...

    1. Anonymous Coward
      Anonymous Coward

      Re: Ah, the tube is not so simple...

      Unless the Google AI has had 30+ years of experience travelling all over the Tube and all different times of day and year then it deserves to fail.

      Expereienced travellers know what interchange stations are a PITA at 08:30 yet easy at 09:30.

      Does it know what entrances and exits are open in the rush hour at Waterloo?

      Does it know how to avoid the queues to get onto the Vic line at Victoria?

      etc

      etc

      etc

      I don't care about Google at all. FWIW, that can go curl up in a corner and die a horrible death.

      There is life on this planet and in IT without involving Google at all.

      1. bigtimehustler

        Re: Ah, the tube is not so simple...

        It will one day know, much as it knows which roads are busy all over the country in real time. Monitor how fast people are moving by their phones and tell the people behind them that this way is a no go due to a sudden slow down in the movement of those people over the norm for that area. Take that into account with historic data and this evolving AI research and you have something that will pretty accurately tell you which way will be the quickest route through the network, or in fact, even a walk on the pavement.

  5. ratfox

    As noted, there are efficient algorithms for doing this fast. I can only assume that the reason this is news is because no algorithm was involved, just randomness.

  6. Mage Silver badge

    Learned?

    No, they did not point a camera at a London underground map or give the computer access to the Internet and said "Learn about the topology, routes and distances of the London Underground". Humans laboriously entered the information into a database for a program created for this domain of problem, by humans.

    The system has an impressive sounding name and description. This is marketing, though of what exactly I'm not sure.

    1. Anonymous Coward
      Anonymous Coward

      Re: Learned?

      This is marketing, though of what exactly I'm not sure.

      Two things:

      Brand marketing of Google, to impress politicians, suits, and other feeble minded types who are impressed with this tiny step. Whilst those types believe that Google is a really, really clever company, they'll be more compliant in Google's grand schemes.

      AI expertise marketing, in the belief that reasonably soon they and their machine learning competitors will be able to market AI-as-a-service to corporates who even now are hoovering up petabytes of essentially meaningless data from the internet of tat, smart meters, wearable devices, etc, and hope that Google (tm) DeepMind (tm) can somehow convert a vast pile of hay into some shiney needles.

  7. Zog_but_not_the_first
    Angel

    There is an answer...

    But you're not going to like it...

  8. fidodogbreath
    Coat

    Does this mean...

    ...that DeepMind has passed the "Touring Test?"

    1. Aladdin Sane

      Re: Does this mean...

      Have a click for your efforts.

  9. You aint sin me, roit
    Trollface

    You'll know it works when it says...

    "Easiest way to get to Moorgate? Don't start from here, pal!"

    1. allthecoolshortnamesweretaken

      Re: You'll know it works when it says...

      ... no, no, you don't want to go there.

  10. Borg.King

    Timetables

    As AC mentioned above, the quickest route has to involve the timetable, the congestion, the expected delays, the interchanges between lines, and the ability to be able to get on the train at the correct point to step off it right next to the exit/corridor your want.

    There's no point getting to a station a minute earlier on a deeper line if you're going to spend two extra minutes riding the escalator to the surface.

    Many tube aficionados know how to visit all the stations in one day using the minimum time. Can this algorithm match (or better) these already established routes?

    This may be a good start down the route to using neural networks to solve problems, so applause for that. Let's hope they can start applying this to practical issues soon, and verify or disprove results derived using more traditional methods.

    1. Aladdin Sane

      Re: Timetables

      What you're referring to here is the infamous travelling salesman problem. If DeepMind can crack that, then logistics companies will save a fortune. None of which will be passed on to customers though.

  11. TRT Silver badge

    It grew more and more awesome until one day the answer came back...

    The best way to get from King's Cross to Manor House is to create a rotating artificial singularity around the Coram Fields area and fold the fabric of space-time allowing instantaneous transfer between one place and another... hang on, I'll just do that for you...

  12. Steve Knox

    Wrong line of thought

    This is all reasonably interesting, but indicates just how far down the wrong road they're going.

    True AI isn't about giving the right answers, but about being able to ask the right questions.

    Let me know when they get that far.

  13. Anonymous Coward
    Anonymous Coward

    Nothing new ...

    We were doing this kind of thing back in the 80's on the BBC micro. Nice to see Google finally catching up.

  14. Tom 7

    If its so smart

    why hasn't it retired to Cornwall?

  15. Herby
    Joke

    But does it...

    "Mind the gap"??

    Look I'm in California, we don't have these silly tube things nearby. One goes under the San Francisco Bay, but it just isn't the same.

  16. Jim Howes

    Did this for coursework in 1987

    Had to write some coursework, in Prolog, for exactly this in 1987.

    My solution came up with some sensible, but also some stupid routes, but then it was Prolog. I rewrote it in C, using Lee's algorythm to find the shortest route, with additional costs for changing lines at various stations, and got somewhere closer in 1988. ( http://en.wikipedia.org/wiki/Lee_algorithm )

    Today I routinely travel from Portsmouth to Wembley each time there is a match up there, and as yet nothing other than my own experience has suggested jumping trains at Finchley Road from Jubillee to Metropolitan to save a few minutes (not to mention that the met trains are air-conditioned, which is a major bonus on most days)

    I still hate Prolog, but not as much as I hate Lisp, but neither come to close to how much I loathe the underground.

    1. allthecoolshortnamesweretaken

      Re: Did this for coursework in 1987

      One word: Plankalkül.

  17. toxicdragon

    Is anyone else getting an insecure connection warning on the DNC link?

  18. JeffyPoooh
    Pint

    Network diagram is insufficient

    Once upon a time I was in London.

    Referring to the famous Tube Map, I went underground and spent 45 minutes and three lines to get to my destination.

    I then walked about two blocks to find myself within sight of where I'd started.

    The 'network' diagram of the simplified and spatially distorted Tube Map by itself is insufficient information.

    1. A Non e-mouse Silver badge

      Re: Network diagram is insufficient

      Absolutely. The famous example is Leicester Square<>Covent Garden. There are many YouTube videos of people walking it faster than taking the tube.

      There are also often quicker ways of getting between lines than by using the obvious tube interchanges. That's why Oyster has a feature called "Out of station interchange". Some stations are linked inside the Oyster system so exiting at one and entering at another within a certain time period counts as one journey and not two.

      And if you want to get really clever, you use Geoff Marshall's StationMaster app to show you the efficient way to change lines at stations, as the signs don't show you the efficient way - just the way they want you to take.

  19. streaky
    Pint

    But...

    Can it solve Mini Metro?

  20. Elmer Phud

    Does it do . . .

    Bank to Mansion House?

    1. This post has been deleted by its author

  21. tiggity Silver badge

    Small region of the London Underground

    Was the bit that caught my eye - so not routing for the whole network

    I'm sure someone will be along to inform us on what region of the underground was used in this test

  22. a_mu

    Security / GCHQ

    Let me think

    who wants to look at data to see patterns and links,

    Uhm.

  23. jb99

    Is that right?

    >> Journeys which required seven-step traversals were accurately given to 99.8 per cent.

    All the lines intersect with the jubilee line so why are more than 2 ever necessary?

  24. Kubla Cant

    Freya's maternal uncle

    The DNC was then asked questions such as "who is Freya’s maternal uncle"

    That sounds much harder than tube navigation. This page says:

    Freya (Old Norse Freyja, “Lady”) is one of the preeminent goddesses in Norse mythology. She’s a member of the Vanir tribe of deities, but became an honorary member of the Aesir gods after the Aesir-Vanir War. Her father is Njord. Her mother is unknown, but could be Nerthus. Freyr is her brother. Her husband, named Odr in late Old Norse literature, is certainly none other than Odin, and, accordingly, Freya is ultimately identical with Odin’s wife Frigg.

    If her mother's unknown, it will be tough to find her maternal uncle.

  25. Anonymous Coward
    Anonymous Coward

    Mrs Trellis wants to know...

    If it can win at Mornington Crescent?

  26. MT Field
    Headmaster

    Hippo-campus

    Really, el Reg? Really?

  27. Deltics

    So given a pointless challenge...

    Why make the exercise more difficult than it needed to be ?

    As the article says, this is a simple graph navigation problem. It's a problem that has been solved already. Google Navigation (and heck, AutoRoute before it!) can find you the shortest and/or fastest route in a far more complex graph - national roading and public transport networks.

    I understand the point of research and finding solutions to new problems, but this wasn't a new problem, it was an old problem dressed up in new clothes. Instead of "training" the system with knowledge of a known thing - the graph - let's artificially PRETEND it's an unknown thing. Why ? What is the use case for this problem ? Where/what are the graph networks where the graph is not known ?

    What, in short, of any use, does this exercise establish ?

POST COMMENT House rules

Not a member of The Register? Create a new account here.

  • Enter your comment

  • Add an icon

Anonymous cowards cannot choose their icon

Other stories you might like