SatNav

• Navigation


  A complex problem
• How a satnav system solves navigation

  1. Break the problem up into several simpler problems

  2. Work out where we are

  3. Have mapping data to know where we are in relation to where we want to go, and be aware of geographical features

  4. Work out the best way to get from where we are to where we want to go
• What computers are good at

  • Being fast, consistent, accurate
• What computers are bad at

  • Anything involving judgement, estimation, or taking account of feelings or other 'intangible' benefits
• How a satnav system solves navigation

  1. Where are we - GPS

  2. Mapping - maintain vast databases

  3. Route planning - process information to find the best way
• Global Positioning System (GPS)


  A system of satellites in orbit around the Earth that a GPS device can pick up signals from to work out its location
• How GPS works


  1. GPS device picks up signals from satellites including the time

  2. The further away the satellite, the longer the signal takes to travel

  3. By looking at the delay, the device can work out how far away the satellite is

  4. If the device can see multiple satellites, it can work out where it is using trilateration
• Abstraction


  Getting rid of some of the (unnecessary) detail from a problem so as to simplify it and make it easier to solve
• Abstraction in mapping


  • A map doesn't need to show every single tree or road marking
  • A computer 'map' may just represent places and roads as straight lines marked with times (or distances)
• Example of abstraction in mapping


  • The London tube map
• Dijkstra's algorithm


  An algorithm that finds the shortest route between two points
• Steps in Dijkstra's algorithm

  1. Mark the starting node with a distance of zero, and all the other nodes as being 'infinity' distance away

  2. Go to the unvisited node with the lowest distance value

  3. Update any nodes attached to the current node with the total distance to travel to that node, if smaller than the existing value

  4. Mark the current node as 'visited'

  5. If there are still unvisited nodes, repeat from step 2
• Example of using Dijkstra's algorithm

  • The correct route is A-C-B-D-E-Z