The invention relates in general to the interactive process of locating and tracking a traveller, and more particularly to helping a pedestrian traveller to their destination by providing route guidance in a convenient manner.

Means currently exist to present route information or navigational guidance to a mobile user using an electronic device such as a personal computer or mobile phone. Generally these comprise an application that delivers either a static list of textual directions (e. g. "After 120 metres turn left into Harbridge Road") or an image in traditional map view showing an area of streets with start, finish and route (1) highlighted, as shown in Figure 1.

A static list of directions suffers from the necessity for the user to interpret text into geometric relationships (e. g. estimating distances), requires the user to track their current location within the specified route and only allows for positive feedback (e. g. "a petrol station is passed on your right. ") by complicating and lengthening the list of instructions.

Map images require large, high-resolution displays to come close to the ability to convey the information of a paper map. Otherwise, as is especially true on mobile devices with small displays, intricate user control is needed to zoom and pan the map to both display large enough areas to convey relative position and small enough areas to convey the necessary detail for making street-by-street turn decisions. Maps also cause problems for many users in requiring them to perform mental orientation from the usual"North (2) is up"orientation, as illustrated in Figure 2, in order to make them relevant to their current location.

These problems could be alleviated, as they are in many modern car satellite navigation systems, by the use of sensors to detect the user'gurrent position. This allows a more focussed presentation of information to the traveller based on their sensed location, for instance, giving only the next turn instruction or orienting a map of their current position (3) so that"forwards is up", as shown in Figure 3.

However, current sensor technologies such as GPS, network location through cell ID or triangulation or local-area sensors have many disadvantages to the traveller, especially on foot or on public transport or in cities. Variously these technologies require extra network bandwidth, require extra device hardware with an associated cost implication, are of limited accuracy, provide one-off locations rather than a constantly updated track and degrade in performance (or stop working altogether) when out of range or sight of their transmitters.

These are factors that are especially detrimental when targeting a small, lightweight mobile device to be used by an individual traveller.

The purpose of the invention is to provide a means of tracking an on-foot traveller and of delivering turn-by-turn directions or other location-relevant information to them in an efficient and easy-to-use manner, which does not suffer from the disadvantages of the prior art described above.

The invention provides for a method of providing real-time location information to a traveller, said real-time information indicating the traveller's progress along a predetermined route, the method comprising approximating the traveller's speed ; and adjusting a progress approximation according to position and/or speed related feedback information provided manually by the traveller; displaying said progress on the display of a mobile device.

The invention also provides for a corresponding device and computer program for providing real-time location information to a traveller.

Further advantageous aspects of the invention are presented in the dependent claims.

The invention will now be described in greater detail with reference to the accompanying drawings in which: Figure 1 represents a prior art approach to the presentation of route information to a traveller in map form.

Figure 2 shows a map section in the"North is up"orientation.

Figure 3 shows a map of a route section in the"forwards is up"orientation.

Figure 4 shows an aspect of the invention where reference bearings are depicted on the display of a mobile device to provide additional route-finding information to the user.

Figures 5 to 24 represent an embodiment of the invention illustrated by way of specific example: Figure 5 depicts reception of a message on an example mobile phone device.

Figure 6 shows user initiation of the example navigation application.

Figure 7 illustrates the main location query screen of the example application.

Figure 8 shows text entry of a destination.

Figure 9 reflects user confirmation of precise destination.

Figure 10 represents a list of possible current locations based on the previously entered text.

Figure 11 depicts the application querying the desired route type.

Figure 12 shows display of two possible routes for the user to choose from.

Figure 13 illustrates presentation of detail of the previously selected route.

Figure 14 gives a screen depiction of the example application being temporarily suspended.

Figure 15 shows the main navigation screen format, depicting the start of the selected route and current position.

Figure 16 illustrates the use of the application to skip forward the approximated position marker to obtain information about the route ahead.

Figure 17 depicts changeover from pedestrian to bus navigation modes, including on-screen instructions for accessing the bus service.

Figure 18 shows the mobile phone display giving a"zoomed out"view of the entire route.

Figure 19 illustrates access to a function that allows fast acquisition of on-route location based on entering the first letters of an on-route street or point of interest.

Figure 20 shows an on-bus location as found by the aforementioned feature.

Figure 21 reflects the example application instructing the user to get off the bus and commence walking on the illustrated route.

Figure 22 represents user recognition and correction of a discrepancy in approximated and actual current position.

Figure 23 gives a representative screenshot of an upcoming right route turn, including nearby streets and associated street names.

Figure 24 illustrates the display of the end of a route and final destination.

As mentioned above, the primary concept of the invention is the provision of useful location information to a traveller without the need for costly and cumbersome external sensors, and results from the observation that surprisingly good results can be achieved simply by approximation, provided occasional position feedback is provided by the traveller.

The accurate tracking of the user allows a detailed, small-area, map representation of their current location on their route, giving simple indication of their relation to nearby reference points (such as side-streets being passed, or icons for particular buildings and other features), thereby giving positive on-route feedback, removing the need to display irrelevant map or route data, allowing a"forwards is up"orientation of the display and removing the need for constant user interaction to access the next turn instruction in navigation applications.

Practical implementation of the invention can be achieved by means of a software application running on a mobile device, allowing this tracking without the use of extra hardware or network bandwidth, and removes the problems of availability and accuracy associated with the use of sensors.

The primary application of the method is to support provision of navigation services for a pedestrian-that is to provide an indication of a route and/or turn instructions in a timely and relevant manner to a user.

The invention relies on the fact that usually a person'svalking pace remains relatively constant within an individual journey. Allied with information from maps accurate to a few metres, this allows prediction of the location of an unhindered pedestrian to a useful level of accuracy in an average urban environment-useful in that it is precise enough to allow visual confirmation of displayed waypoint and/or route information (e. g. the name of a street to pass or to turn into) giving the user confidence that they are on their intended route or approaching a turn to be made, or giving indication that they have taken a wrong turn and should re- acquire their current location and request another route.

If the user keeps on the assumed route, any errors introduced by the speed approximation or their obstruction can be corrected for by that user. For example, if they are currently passing a particular side street they might correct a lagging estimated position by manually adjusting it to be exactly adjacent to the side street. A large degree of aid is presented to the user controlling this correction, for two principal reasons; firstly, since position is represented by only 1 dimension (distance along route) only forwards and backwards controls are necessary; and, secondly, the amount of correction required will generally be of only a few metres, due to the position estimation mechanism.

Forwards/backwards calibration-where the user makes positional adjustments forwards or backwards in the route to bring the estimate as close as possible to the user's actual position- is the basic, preferred interface. It is the preferred arrangement because it is the simplest and most obvious in terms of the feedback it gives to the user. An alternative is to use direct adjustment of estimated speed by the user (based on, for example, numerical, audio or graphical representation of pace) as the primary control mechanism, but its effects are less obvious as they are only apparent to the user over time (unlike with positional adjustment, where the user can easily see if their inputs are bringing the estimate more or less into correlation with reality) and are generally more confusing ("if the estimate is behind me, do we need to speed up or slow down ?")-factors which could easily result in incorrect adjustment.

Estimated speed can be automatically calculated based on the forwards/backwards positional adjustments made, e. g. if user moves estimated position forwards, to"catch up"with their actual location, the overall estimated speed can be increased by some amount (roughly inversely proportional to the time elapsed since speed last adjusted) as the estimate is obviously too low.

The basic algorithm for estimation of user position is to take the user'estimated walking pace, multiply it by the amount of time that the route has been followed since the last known fix (the time elapsed since the user indicated the start of walking or a specific change in position or speed), thereby calculating the distance along the route since the last known fix, and thereby the distance along a particular street on a route and an exact co-ordinate within map space.

Approximation of walking pace is initially made using an estimation of an average user's walking pace in their particular environment. Variations in walking pace tend to be either at distinct points in a journey or, for a particular user, between different journey types, e. g. whether walking to a business or leisure engagement.

The walking pace may be further determined or calibrated by knowledge of the user's walking habits, additional sensors, feedback from the user (either directly or by positional adjustments forwards or backwards in the route) or by knowledge of congested areas and average speed.

The efficiency of the invention degrades with (i) greater distances between street junctions; (ii) sparsity of visible street names; and (iii) obstruction of the user's phial progress.

Since the primary intended application, that of route-finding, is by nature targeted primarily at urban environments due to the relative difficulty (due to many possible turns) and frequency of occurrence (more people, particularly non-local people), consideration of difficulties in towns and cities is key.

The decreased accuracy of positional estimates due to increased distances (i) is of decreased relevance when considering urban situations.

Lack of street signs (ii) is a difficulty to most route delivery means, although the immediate- locality map feature of the invention copes better in this regard than static maps and particularly text directions. In situations where the individual's viking pace has already been gauged by the invention, the user can identify specific waypoints merely by their location relative to the estimate, reducing the reliance on street signs. Use of the invention's position approximation demands much less skill of the user than using alternative indicators, e. g. relating physical position to a stated distance (e. g. "turn left after 230 metres").

Focussing on urban usage indicates that (iii) obstruction of the user's physical progress is the most significant disturbance to the estimation of position. The most common forms of this obstruction in towns and cities are distractions, crossing roads and pedestrian congestion.

Effects from distractions such as stopping to look in shop windows or stopping to receive a phone call or whatever reason, can result in an estimated distance along the route beyond the user's actual position.

Crossing roads presents a more complicated scenario. Like distractions they can be seen as discrete events that cause an absolute stop to travel and then at some later time resumption of progress. This is especially true for major crossings, which have a large variation in the amount of time they can disrupt progress for. Unlike major crossings and distractions, making several minor crossings (where the potential delays are not so significant compared to the time taken to walk between each crossing unhindered) can usefully be accommodated with a reduction in estimated overall pace.

Pedestrian congestion presents a different scenario again in that this either results in a consistent but slowed walking pace (as user adapts to the speed of the crowd) or a variable pace as the user attempts to retain their unhindered rate but is intermittently held up. A consistent, slower speed can more easily be tracked by the invention than a highly variable one, but either way, pedestrian congestion is going to require increased feedback from the user to retain accurate tracking. Pedestrian congestion is, however, a somewhat predictable phenomenon and recognition that certain thoroughfares at specific times on known days have certain levels of congestion may allow approximation of these effects, allowing automatic reduction in estimated speed on these sections.

Mitigation of obstruction within the invention is largely dependent upon greater levels of user feedback than when a journey is unhindered. The invention does benefit, however, from the simple interface required to perform this correction-in that the estimated position will always be ahead of their actual position and that only one control needs to be activated, the "move estimate backwards"control. The amount of backwards estimate movement required will also be directly proportional to the amount of time the user is held for, allowing for intuitive correction for the obstruction.

Use of backwards correction of estimated route progress presents a further potential problem when allied with automatic calibration of estimated speed based on positional feedback; for example, in a situation where the user is held for a long time at a single major road crossing, the user can subsequently re-calibrate their position by moving the estimated position backwards. If using a very simple algorithm to calculate speed based on total distance and time travelled, this re-calibration could result in a lowering of the estimated walking pace and contribute to inaccuracy in subsequent unhindered travel. Where a higher level of accuracy is required it may be necessary to employ a further level of heuristics in interpretation of necessary speed adjustments to be made, dependent on the pattern of positional corrections.

For instance, small positional adjustments backwards and forwards, spread over the route, will normally be used to adjust the estimated speed downwards and upwards respectively.

However, a heuristic could recognise that a large positional adjustment backwards, following a period of only small positional adjustments, indicates that the user was obstructed, and therefore should result in no overall change to estimated speed.

Access to a"pause"function, whereby the individual can indicate that they are temporarily stopped or have resumed their journey, can accurately compensate for stop-go interruptions.

This does however add a further control that the user must use, to a certain extent further complicating the feedback interface and burden on the user and also adding a potential mode of error in which the pause function remains enabled when the user has resumed their journey. Aiding correct use of a pause function could alleviate this effect-this could be done by an audiovisual indicator that a major road crossing is expected or reminder that the pause function has been enabled, prompting the user to check whether the pause function is being correctly employed. With or without specific assistance of this nature, a pause function is a useful and important feature of the invention.

A particularly useful feature of the invention is the ability to provide an accurate estimate of journey time (and distance) to the destination. Due to the system'nature of accurately measuring average travelling pace, this can be determined with a high degree of confidence.

For a connected device, a useful aspect of this is the ability, were the estimated travel time exceed some acceptable limit for the user, to use the application to query journey times using other travel modes, e. g. local buses, or to request personal transit, such as a taxi, by submission of the intended journey details to a transport service provider.

The invention'position estimation mechanism can be aided by sensor information sourced, for example, from a mobile phone network or from a GPS receiver attached to, or integral to, a device utilising the method. This could make determination of a first known point (e. g. starting location as current position for a route request) easier, as well as providing extra automatic calibration of approximated walking pace and absolute position on-route where sensor coverage and accuracy allows, whilst still providing a means of tracking the user in the absence of sensor availability. Furthermore, in a device utilising a position sensor as its primary means of tracking a traveller, the invention's nzhanism could usefully be applied in situations where position information from the sensor is unavailable or not sufficiently precise.

In order to ascertain a known fix-that is a known location at a certain point in time-and in the most likely scenario of not having access to this location from a sensor, it will preferably be implemented by capturing text entered by the user. In order to reduce the burden on the user, who is most likely attempting to enter their location via a small device with limited input capabilities, entry can be accepted by various shorthand means-for example: by selection from a list of previous or commonly used locations; by entry of a specific postcode or narrowing of the possible location set by using a partial postcode; by entry of town (or confirmation of previously used town) to narrow possible location set; by use of an approximated sensed position (such as a mobile phone cell coverage area) to narrow the possible location set; by entry of the first few characters of a street name, and selection from a possible list; or, a particularly useful mechanism in cities, by entry of the first few characters of two streets intersecting at a particular corner and selection of possible matches.

On a limited wireless device, these mechanisms will mainly rely on network requests made against a central server optimised for these street and town name searches.

Further applications and features The invention is primarily aimed at a user travelling streets in a city, though it can also be used in other areas of calculable or specifiable route, such as indoors in shopping centres, hospitals, libraries, airports or railway stations etc.

The invention integrates well with public transport and multi-modal routing and as an aid to passenger navigation. This is both as a matter of situation-journeys are often multi-modal in nature-and that passenger transport systems bring their own, route-related decision- making problems for the traveller.

There currently exist queryable services for multi-modal routing, often preferentially accessed through an Internet browser on a desktop terminal. An example of such can be found at http\\ : journeyplanner. tfl. gov. uk. Routes provided by these services usually contain at least one on-foot section. Integration of these services with the invention provides several potential overall benefits; the main advantage of integration being the use of the invention as a portable, automatic means of storing and delivering the route instructions generated from the browser solution. Without electronic means such as the invention, paper printouts or commitment to memory are necessary. For walking parts of a route the benefits of the invention over existing alternatives are already asserted. Another advantage to accessing a multi-modal route, containing walking segments, via the invention, is the removal of the need to individually request those segments. A further benefit can be achieved by use of the extra interactivity and input capabilities of a browser-based solution, in order to make initial destination and (optionally) location set-up easier than on a handheld device.

In-transport modes will keep the forwards/backwards positional adjustment interface (although using coarser adjustment mechanisms to reflect the higher rates of speed and lower level of speed predictability) and keep the same"forwards is up"orientation for street-level transport types. In keeping a similar interface focussing on its simplicity and a route's 1- dimensionality, using estimated speed where possible due to timetabling or real-time feeds, allows the user to acquire usage skills and confidence in one mode and transfer them to the other transport types.

With regards use of public transport, since it can be assumed that a bus or train will on the one hand not go the wrong way (given the user has boarded the correct service), but on the other that the chances of maintaining accurate tracking diminish (due to less predictability in speeds), it becomes more important for the user to be able to re-acquire their current location on a route. This could be done by augmenting the invention with extra on-route position finding services. E. g. entering the first letter or two of the name of a stop or point of reference could quickly determine the user'location and indicate relative position and estimated time to point of departure from the service. For instance, if a user on a bus does not know where on the route they are, but can see they are passing"Haymarket Street", typing in"H"to a position-finding function will cause a list containing all on-route streets or stops beginning with H to be shown, allowing rapid re-acquisition of position as user chooses the desired name. This feature will also be useful in other modes, for example, in reacquisition of location on a pedestrian route where the user has stopped but forgotten to use the pause feature.

With regards use by a passenger in private transport, similar coarser-grained positional adjustment and on-route position finding features may also be useful. Further, a facility for the passenger using the application to set the position-estimating speed becomes more relevant, as on unhindered sections of road this could be entered based on the in-vehicle speed display. Another useful feature in this mode is whereby the private transport's odometer (distance travelled meter) reading can be entered at a known point-usually at the start of the route, with the default value being zero to cater for the case of the user zero-ing the odometer-and then at any approximated point of the route, the figure the odometer should be at can be displayed by the application. Further, if the currently approximated position is thought incorrect, the current odometer reading can be entered by the user to allow the implementing application to update the approximated position to the location corresponding to the odometer reading.

Use of the invention in a situation with absolute location sensing will have a relatively greater benefit in these non-pedestrian transport modes. In an effect similar to the primary pedestrian mode of the invention, consideration of location information in conjunction with the known 1-dimensional route of a particular public transport service, relaxes somewhat the level of location accuracy required. For example, in a dense urban environment, locating a mobile phone to a particular network cell (to a radius of a couple of hundred metres) may allow determination of a bus user'surrent nearest stop down to one or two alternatives.

Further, use of the invention in its preferred embodiment, in a device without a location sensor, could be augmented by sensor information sourced from the transport vehicle, for example by local wireless network from a bus or train.

Use of a location sensor, such as by wireless or cabled connection to a GPS situated within a private vehicle will enable use of the invention directly by the vehicle driver for the in- vehicle portion of a route, acting more like a traditional in-vehicle GPS navigation device.

As an alternative to absolute, automatic sensing of location, by assuming the route taken, combined with a feed of distance travelled, such as from a car's internal management system or from a cycle trip computer, accurate, automatic tracking can be performed by substituting the sensed distance travelled for the distance otherwise approximated by the application or specified by the user.

There currently exist many means for route specification-that is input of destination, current location and routing options (such as selection of shortest or simplest, or definition of waypoints, i. e. locations for the route to go via, e. g. if user requires use of a cashpoint, that could be factored into the journey). These are not necessarily through standard data-entry facilities (usually UI menus, text entry elements, selection of options from lists) on the device implementing the invention. Media for route specification include voice calls to operators, emails to operators, website link specific to a location (e. g. from a business'contact page), sending of a properly formatted text message, etc. The invention is essentially independent of these means, but is made more effective by their appropriate usage. For example, the option to use a voice call can be a great aid to a user that finds difficulty using the device's standard entry mechanisms (this can be quite common with use of small devices or for users not proficient in the use of the device) or the ability to use a fixed browser terminal-with its implicitly larger display and easier input mechanisms (e. g. mouse and full size keyboard)-to either directly determine route specification or via shortcut links (e. g. automatic destination registration on the contact page of a business) is also useful. Voice call set-up will allow the user to talk to an operator with access to a map terminal and the ability to register the user's intended destination and/or current location with the central server-the user will then be able to easily select the registered locations as options on next use of the system. Another useful configuration for destination set-up is where a user of the invention can forward a particular destination to other users (so that it can be selected from a list on their next use of the invention) or the use can forward a URL (in a message such as an SMS text message) to a downloadable implementation of the invention, which will upon its first use automatically use the forwarded destination.

A useful feature of a navigation application of the invention is the ability to provide useful information on a particular destination without entering a start location to route from. This is particularly useful in providing the relative distances to nearby transport links in an application which provided no, or only limited, multi-modal routing.

An advantageous feature of a navigation application of the invention is the ability to provide route advice to third parties from the current location. This could take the form a text or visual description of the route, and could optionally be forwarded to the person requesting the advice. This could be particularly effective in promoting the usage of the invention, since it accurately caters for the needs of the person requesting the advice-as part of the forwarded advice (in, for instance, a text message) could be a URL link to download the implementing application.

Route selection gives potential for a number of approaches particular to the invention. The obvious factor deciding the optimal route to a pedestrian'destination is shortest distance.

This usually directly equates to the fastest route (often not true in considering vehicular routing). Known congested routes could be avoided. Routes could be made even easier to follow by simplifying them. This could be achieved by considering every turn to add to the extra cost of a potential route, when considering cost-based routing. In general there will be some trade-off between all these factors-distance, congestion, obstructions, popularity and simplicity.

Feedback to a central server from uses of the invention on wireless devices could provide useful feedback for route selection data and algorithms and position estimation algorithms.

For instance, the range and distribution of delays on particular routes and streets and at particular road crossings could be sampled and approximated more accurately.

The invention is not specific to the location of the raw data or where the route-finding process has taken place. The device may store the map data and calculate its routes internally. However, being characterised by its particular usefulness in small devices, and the general utility in being able to run an application on a small portable device, it is therefore preferable to run the application in a classic client-server configuration, using a wireless connection to a central server to obtain location and route information. This allows the use of a fewer resources on the mobile device, increases the breadth and depth of map and supplementary data that may be accessed and increases the complexity achievable in route- finding and other necessary processes. This configuration is increasingly a practical option given the widespread and increasing availability of wireless connectivity in portable, intelligent devices.

The invention is not specific to devices with small displays (i. e. displays on which detailed street maps covering a reasonable area for most pedestrian journeys, e. g. quarter of a mile- approximately 400 metres-can be easily viewed in their entirety), it is however characterised by being particularly suited to displays of this size.

Providing a"zoom"feature-that is the ability for the scale of the local map display to change-is particularly useful on small devices, where there is sometimes the need to see small area geometries (for example, in trying to discern the correct exit from a complicated intersection) and at other times the need to see a large section of map (for example, to visually match the street ahead to the display in order to gauge where the next turn is located). This zoom could be manually controlled by the user. Since the need to zoom in or out can be associated with certain situations, it may be useful to provide an automatic zooming feature whereby the implementing application will, for instance, zoom in when approaching an area of high street density or, in another example, zoom out to show an obvious landmark ahead if one is being approached.

The preferred configuration for display of the map data is one that is largely geometrically and topologically correct for the immediate streets of the route.

Alternative embodiments could use stylised, non-geometric, textual or iconic representation of the route bringing their own advantages-in clarity of turn indication or in allowing interfaces that can be implemented on simpler devices.

For example, sections of road without side roads or reference points could be displayed at smaller scale than sections with more relevant points. In another example, no map is displayed at all, but a textual or iconic (e. g. right arrow for right turn) description is made of route instructions and relative distances to side-streets and other points of reference are described explicitly (e. g. "Passed Road A 12m, Passing Road B Now, To pass Road C 5m") and updated regularly. These alternatives however bring their own disadvantages, for example, by introducing errors in relative distances, relying on users'gsp of absolute distance measurements or providing a less than intuitive interface.

Another possible feature is to augment the preferred view with lst-person view images of key locations. This may be particularly useful in key situations such as complicated intersections or in the process of initial orientation of the user.

Other possible geometrically-correct views of the user's lodity and way ahead are possible.

One way is to provide a"birds-eye view"of the street ahead, although if required this can be achieved largely by the user physically angling a portable device in standard top-view map display to lie parallel with the ground. Another possible display method is to construct 3-D representations of the locality, principally displayed from the 1st person point of view. This may give some benefits for users who have great difficulty interpreting a top-view map representation or perhaps in the initial orientation process. On the down side this complicates the implementation, requires more resources and it makes it more difficult to represent some information (e. g. relative distance from the side-street just passed and to the side-street being approached). Also, by relying more on matching of the display image to the actual view of the street, extra data may be needed about street geometries, street furniture and the outlines and facades of buildings to make the image match reality. These factors point to more likely usage of 3D in the future.

An interesting aspect of this invention is the highly accurate tracking of individual users, based on that user'collaboration resulting from their desire to cooperate to perform a useful function to themselves.

This tracking is made more useful in that it also provides the possibility of tracking in areas where previously no common location system has been thought to work-underground, within buildings etc. provided that knowledge of the geometry and topology of those areas has previously been determined and can be used in route generation.

This highly accurate and universal tracking can be the basis for other features and applications. These location sensitive services have been widely talked about, but have been limited in potential applicability due to lack of tracking technology accurate or widespread enough.

For example, information relevant to the immediate proximity of the user, such as advertisements or promotional opportunities for nearby businesses can be presented. These messages can be further targeted based on the identity or profile of the user. In the preferred scenario of a navigation device wirelessly connected to a central server, feedback can be captured from the user expressing interest or disinterest in the promotion. An extension to this idea is the ability to allow the user to request directions to a promoted service not currently on-route.

Other possible applications enabled by the invention include notification of proximity of friends or other pre-selected individuals, social introduction services where pre-registered people can be identified as they pass others on the street, etc. These applications, previously widely postulated, are increased in effectiveness due to the ubiquity and accuracy of the tracking mechanism.

Use of the invention has been found to be intuitive and emotionally appealing, exhibiting little cognitive friction. It is thought to be extremely easy for an untrained individual to follow directions provided by the invention. One reason for this is the high level of constant positive feedback while on route-the user can see an analogue for their current real-world situation moving through the representation on the display. Because keeping to the route displayed is a relatively simple task, it therefore makes the task of initial orientation-where the user must determine which direction from their current location is represented by straight- ahead on the display-the most difficult usage task.

Navigation instructions can be provided through graphical annotation of the route (different colour or marking), text description, a spoken instruction or even through appropriate audio tones or sounds. Audio warning of upcoming turns (or departure from a particular mode of transport) is a useful supplement to this whereby appropriate sounds are output just before arriving at a turn, helping ensure that turns are not missed due to an approximated position lagging behind the actual user location.

Another feature is that by alerting the user with specific noises (based on, for example, direction of turn or reference point-left vs. right-or significance of reference point-to pass a road vs. to turn into a road) the user can be helped to use the application without taking the device out of their pocket.

Audio alerts could also be augmented or replaced by physical feedback, e. g. from the vibration alert function of many popular mobile phones, performing a similar function less intrusively or in conditions where an audio alert may not be heard.

The preferred implementation with a geometrically correct display is based upon storage, determination or retrieval of a data structure reflecting the two-dimensional co-ordinates of street nodes, connected by straight-line street-centre segments. These could be further augmented with other geometric and topographic information. For example: by addition of curved or spline segments; use of other street attributes-width, pavement markings etc.; area-type objects for representing squares, parks and lakes.

In providing preferred or alternative routes across traversable open areas that do not have a network of known pathways across them-such as town squares-possible straight line paths could be assumed between known entry and exit points or leading from the breaks in (or edges of) known obstructions such as fences.

Due to various practical issues, the map data source that is relied on for generating routes and possible paths will likely contain errors. In implementations on wirelessly networked devices, a useful co-operative feature allows for users to when they come across incorrect, spurious or missing map data. This can be an easy to access feature that does not overly burden the user, but provides the operators of the system with specific information as to where potential errors are situated, which can then be surveyed for verification and/or correction. At the point where the user indicates a possible error, that is submitted to a central server. This submission can be checked against previously reported errors and, probably after a check against the accuracy history of the particular user, can be augmented with a verbal description captured by phoning or otherwise contacting the user.

A special case of map data error, or of some other implementation problem in a navigation application, would be that the user cannot physically continue along the path shown as it is blocked or non-existent. In this case the application can request a new route avoiding the missing path or prompt an operator to call the user to give them some specific advice to help their progress.

In a navigation application, the tracking method of the invention relies on a known route specified by a route-finding sub-system at the start of the navigation process. The location mechanism is not restricted to navigation in its usefulness. The invention can also be utilised in another mode: that of tracking the user's actual location without a known intended route.

This is essentially done by having the user specify their actual route by some means.

By provision of an appropriate feedback mechanism, the user can specify their route decisions whilst travelling. On starting the tracking process, the user selects the intended segment to travel on next from their current location and indicates that they have started walking. Without feedback from the user, the application assumes their route-for example, this could be that they continue to travel through each potential turning point by selecting the closest exiting segment to straight-ahead (a purely tracking mode) or that they will continue to follow a suggested route (a navigation application with the ability to detour). At a junction (or very close to it) the user may indicate that they are turning, for example by hitting the "left"or"right"button-if there is more than one left or right, the correct one can be selected by pressing more than once. If the user's route usually assumed as straight-ahead, it may be necessary in some circumstances (for example, approaching a T-junction) to prompt the user for feedback as to their turn decision. A separate about-turn feedback feature may be necessary to cover the special case where a user can turn when not at a junction.

In a navigation application with the ability to detour, use of the above turn feedback mechanism could trigger automatic re-routing of the user to avoid the next part of route turned away from. This could be a useful way of coping with impossible or blocked routes or sections of a route that for whatever reason the user does not want to pass along.

On a wireless device using a central server for general map storage, tracking will require requests to be made for sections of local area data to allow initial direction selection and subsequently as the user begins to move out of the already-downloaded area. The specific map area to download will be selected to provide adequate data for the assumed route ahead, combined with enough data about side-streets to allow requests to be made for more data should the user decide to turn down one of them.

Whether the map data is downloaded or held locally, a potential feature of the tracking application is the ability to closely monitor the path and progress of the user at the server. By ensuring that the application sends information on any speed or position or route adjustment to it, the server can use the same or similar algorithms to those employed in the client to approximate their position at any point in time. This may be augmented with regular "heartbeat"messages to give confidence that the user is on-course and can still maintain their network connection.

Indications of compass directions (2), visible landmarks (4) (such as a tall building in the distance), as-the-crow-flies direction to the destination or the bearing of the sun (5) or moon (6) could be displayed as reference directions. Preferably, these will be displayed at the edge of the visible screen, at the appropriate bearing w. r. t. forwards, as shown in Figure 4.

In order to better understand the invention in a practical context, a number of typical application examples will now be described.

Personal navigation example Here follows an example usage of an implementation of the invention as a navigation application on a mobile phone (7), illustrated in Figures 5 to 24. The navigation application runs as a Java program that has been downloaded by the user onto their phone from a WAP (Wireless Application Protocol) site.

The user is outside their local post office in Camberwell, London when they receive a text message on their phone, shown in Figure 5, from a friend suggesting a meeting at"pig in sky pub, wl @ 5: 30"-an hour from the current time. Unsure of the exact location of the pub or of getting around the"W1"postal area, the user selects (8)"Navigation"from the phone's "Applications"menu, as represented in Figure 6.

As Figure 7 depicts, the application starts and displays three text entry fields (9): for"Town", "Destination"and"Current location". The town field shows"London"as its value-this has defaulted to its value at last use-which is correct. Using the phone's cursor (10,11) and "OK" (12) keys, the user skips over the town field to select (8) the destination field and types in"pig pub"as in Figure 8. Internally the application sends the text"pig pub"as a parameter in an HTTP request to a predefined URL for destination lookup on a background thread. For current location the user enters"orp", since they are standing next to a road signed as "Orpheus Street". Internally, similarly to the destination lookup, the application retrieves possible matching locations for"orp"via a request to a predefined URL using another background thread.

Whilst the user was entering the current location search text, the destination lookup request has returned a set of possible London public houses ("pubs") containing the word"pig", as a list of pairs of variables-one string variable giving a title for each possible destination and also an associated unique identification number for each. The user is prompted with a list that shows the full public house name, street and postcode area, displayed as shown in Figure 9. Scrolling a highlight down the list with the down cursor key (11), only one is appropriate -'The Pig in the Sky, Cork Street, Wl". This is selected by pressing"OK" (12) when highlighted. Internally the application stores the selected destination title to an internal string variable, but also stores its associated identification number.

Whilst the user was choosing the exact destination, the current location lookup request has returned a set of matching locations and their identification numbers. The user is first presented with a list of possible streets (all London streets beginning with"orp"). The user selects"Orpheus street, Camberwell, SE5", then is presented (see Figure 10) with the downloaded locations that lie on that street, listed as further options of"at Daneville Rd","at Denmark Hill", "at house number...","at middle of street"or"not on this street". User selects (8) "at Denmark Hill"as they know they are at the intersection of Denmark Hill and Orpheus Street. Internally the application stores the identification number associated with that location as being the destination.

The application presents (Figure 11) the user with three options:"Go direct", "Go via cashpoint"or"Go using options...". Selecting"Go using options..."will allow the user to request a route (or routes) tailored to specific requirements-such as allowable modes of transport, importance of cost and speed, number of optional routes to return, multiple locations to visit, etc. Selecting"Go direct"will retrieve a route (or routes) using a default set of requirements or the last options specified on a previous usage, as stored by the application on the central server and cached in the phone'persistent memory. In this instance the user is short on money and selects (8) "Go via cashpoint"which behaves as"Go direct"except for the obvious addition of visiting the en-route cashpoint that requires least detour. Internally, the application sends a request for the specified route passing the stored identification numbers of the location and destination as parameters. The central server calculates multi-modal routes based on the user's default criteria from its vector street map.

The best-fit route is then analysed to build a list of straight-line street segments that are on the route or in close proximity to it (to provide visual reference when the user views it in local map form) and stores the data about those segments and supplementary information (e. g. about bus route details) into a stream of bytes in a terse binary format. The response sent back to the application is headed by descriptions of the available routes followed by the data detailing the best-fit route. As the response begins to arrive at the mobile device the application displays, as shown in Figure 12, a summary of the optimal route-via bus taking approximately 50 minutes and costing £1-and also of an alternative via train and tube taking 40 minutes and costing £3. 50-in this case the extra speed of the alternative route is unnecessary so they select the bus route. Internally, the selected best-fit bus route has been downloading while the user was reading the route summaries, and the application is constructing a spatial index for the segments as their data are downloaded. While internally the route finishes downloading and processing into displayable form, further route information is displayed to the user as depicted in Figure 13: such as that the total walking time is 10 minutes and that the bus journey is on a number 12 that runs every 3 minutes and will last 40 minutes.

The user switches from the navigation application (Figure 14) to send a reply text message to their friend confirming the meeting. Re-starting the application, it internally looks up in persistent memory a variable representing the last screen displayed and returns the user to the detailed route information screen, as shown in Figure 13. Selecting an available"View" command (13) by pressing its associated button (14) the user is presented with an overhead map view, illustrated in Figure 15, of the vicinity of their approximated current location, rotated so that the route (1) to the bus stop is shown as towards the top of the screen, with a clear marker for their current location horizontally central in it (3). Internally, to achieve this, the application has calculated the area of map necessary to fill the screen at its default zoom level and used its spatial index to retrieve the data of each segment within that area.

Internally the coordinates of each street segment are transformed from map units to screen pixels based on the current zoom scale and angle of rotation necessary to display the first on- route segment at a bearing of zero degrees. The segments are rendered using standard line- drawing routines that are part of the Java programming interface. The route segments (1) are rendered using a different colour and thickness to differentiate them from side roads (15). A sense of scale and zoom level is conveyed by the rendered width of the roads.

Since the user knows the way around their current locality, they hold down"forwards" (the up cursor button (10) of their four-way cursor control pad) to skip their approximated position-and thereby the displayed local area, as a single frame on the way is illustrated in Figure 16-from the current location down the street to show the location of the precise bus stop to board at. The user notices that the display shows a cash icon indicating that there's a cashpoint (16) on the right before the bus stop. Once the position has skipped to show the precise bus stop (17), as the display represents in Figure 17, the user releases the up cursor (10), suspends the application and puts away their phone, confident that they know where they are going. Over the next few minutes the user walks down to the bus stand, stopping on the way at the cashpoint the application had reminded them of.

Once at the bus stop, awaiting the next number 12, the navigation application is resumed by the user. The application restarts at the last point of suspension-waiting at the bus stop.

The display is annotated with information (18) of the intended destination stop to ask for, what the fare should be and estimated time on-route. The bus arrives and the user gets on and buys a ticket. Once seated the traveller utilises the"zoom out"feature, by pressing the left-cursor (19), to show more of the map ahead, as replicated in Figure 18, determining that the destination bus stop (its position indicated by an appropriate icon (20) ) is after the river (21) (shown in blue where it intersects the route and an obvious feature even when zoomed out); confident that they can recognise crossing the river they put away the phone and relax.

Time passes and after half an hour or so the bus passes the river. At that point the user wishes to check their location relative to their destination-seeing that they have arrived in "Parliament Square", they access an on-route quick find feature and enter (22)"p"for "Parliament"as shown in Figure 19. The application displays a list (23) of the 2 or 3 streets beginning with that letter and the user selects Parliament Square from it; the approximated position (3) now jumps to close to their current position in the square, as depicted by Figure 20. The application estimates their time to arrive at the destination stop based upon the bus timetable and displays (24) the updated bus journey time, of 7 minutes remaining, on the application status bar. The user now uses the"forward"feature on the up-cursor button (10) (which now behaves in a much coarser fashion than the pedestrian journey segments, moving several times as far for each keypress) to move their location marker (3) and locality map in sync with the actual bus position till they see the indicated destination stop (20) ahead, shown in Figure 21. The user gets off the bus at the intended stop, shown as on Regent Street (25).

The application is now approximating position as just before the bus stop. The user presses "forward" (10) to the bus stop and the application displays (26) "Now on foot"to show that it is now in pedestrian mode again. The indicated route (1) faces along the street coinciding with the bus route direction. The user presses the stop/start (a. k. a. pause) button (27) to indicate that they have started walking and sets off down the road. Seeing that the next turn (28) is the first on the left, they put away the phone. As they approach the first left, the phone sounds a long tone to alert them of the impending turn, confirming the side road they were heading for.

Once the user has turned the corner they get out the phone again to view the application, which appears as in Figure 22-it is already oriented for this street after the turn (28) but, seeing that the approximated position (3) is already a few metres further along the street, clicks"back" (11) on the down-cursor once to make the position more accurate (see reference number (29) in Figure 22-the arrow referenced is not actually displayed but represents the resultant shift in approximated position relative to the local environment). Internally at that point the application adjusts the approximated speed down slightly to reflect that it is probably in excess of the user'actual speed. The application status bar displays (30) that it is just 2 minutes to the destination. The user sees from the map, which automatically zooms out to show the next turn on this new street, that the turn is on the right in three or four streets. They put away the phone and continue to walk forwards at their normal pace.

As progress is made, the phone beeps as it passes streets alternatively on left and right, the short length of the beeps indicates that they are for passed side streets. The tones also give audio clues that the user has learnt to recognise for whether the streets are on the left or the right. A little further on the phone is checked again and the display shows, as in Figure 23, that the turn (31) is in 2 streets on the right-into"Cork Street" (32) after"Old Burlington" (33). The next road comes into view, it is called"Old Burlington", so they put the phone away confident of the next turn. The user then receives a short phone call that causes the application to suspend, but they continue to walk as normal. Whilst in the call they turn into "Cork Street"which was indeed the next street. After ending the call they switch back to the navigation application-as Figure 24 depicts, now showing their position (3) to be on"Cork Street" (32) -and the display has automatically zoomed out to show that the destination, marked by an appropriate icon (20), is on this road; the user can see the"Pig in the Sky"sign ahead and so exits the application, puts away their phone and walks the final few metres to their destination.

Personal safety device example Another example implementation of the invention, again as a downloadable program on a mobile phone, is as a personal safety reassurance application which tracks the position of the user, allowing quick and easy messaging of their exact location to user-specified recipients or, if the user feels threatened or has problems, to an emergency operator.

In this example, the user is visiting a friend but late at night in an area they have previously visited only in the daytime, and have some doubts about their safety on the journey. On initiation of the application, the user enters their current location in a similar manner to the navigation example. No destination is entered. The user has previously entered via a website the mobile phone numbers of possible recipients of their location messages, and now selects the recipient (the person they are visiting) for this journey. The application downloads a map of their immediate vicinity and displays it, allowing the user, by pressing the left and right cursor buttons, to select the direction from their current location that they are to proceed on.

Once the appropriate direction towards their destination is selected, with that direction shown as upwards on the display, they click on the stop/go button to start their journey. Internally, a request is posted to the central server showing the direction selected and that the user has started the journey-the server now sends an appropriate text message to the user'friend informing them of the start of the journey, time and location. The application now functions much as the navigation application, except it always shows the route as being straight ahead at every junction-this is the assumed route. As the user nears the edge of the known map data, the application requests more map data in that direction from the server so that there is always enough data to track the user for a few minutes walking. As the user makes any adjustments to the approximated speed or position or starts or stops the application, that change is notified, with an accurate timestamp, to the central server that allows central tracking of the user. If no adjustments are made within a certain timeout period of, for instance, a minute then the application sends a"heartbeat"message to the server to keep high the confidence in the server-side tracking accuracy. In the event that the application does not communicate for a time significantly in excess of the heartbeat timeout, an operator can call the user to check correct functioning of the application and ensure they do not need any assistance.

The user is now approaching a turn away from the assumed route, to turn right, and so clicks on the right cursor. The next street on the right as depicted on the display starts flashing and the user confirms with the stop/go button. Now the route is shown as turning right at the next junction, and subsequently tracks the user as they turn down that road. Upon turning the application internally downloads more map data along that road and its side roads from the central server. The user estimates that they are halfway to their destination and so decides to let their friend know. They select the"Notify'OK feature that triggers the sending of another text message to their friend, giving their location and current time and that they are doing fine. Similar to this notification feature, the application can also convey different messages to the recipient along with their location-such as a request for the recipient to come out and meet them-or either a"assistance"or"emergency"feature that sends their message direct to an operator, who will call the user back (with urgency appropriate to feature selected) on reception of the message-that operator can then give help or pass on details direct to emergency services as relevant. The user completes their journey without incident.

Tourist aid example Another example embodiment of the invention, this time as an application on a Personal Digital Assistance type of device, with a palm-sized display, is as part of an interactive tourist aid. Focused on one particular city, the guide application is stored in the device's own memory and the city data on a removable memory card. The guide provides the same basic navigation facilities within its known area as the first navigation example above. The guide provides optimal predefined itineraries that take in multiple sights at a time. The application shows extra information about points of interest on-route as they are approached. For example, when about to pass a particular historic building the application sounds a tone to alert the user-the application is showing a relevant icon at the building's loation along with a brief description of its relevance, for example"Building marks start of Great Fire"which can be clicked on for more information-some extra text and pictures and perhaps a short video clip about the building's history.

Standard route navigation is provided but is augmented with the tracking aspects of the invention in this implementation to allow a"wander"feature whereby the tourist can specify a detour (i. e. they indicate a turn of the assumed, precalculated route) but will still receive location-specific information about their new route and can at any point recalculate a route to their next intended destination.

Another feature of this tourist aid is its ability to direct them to shopping locations relevant to their needs (specified at sign-up for the application) and provide them with other promotional opportunities.

Location-based game example In this final example implementation, the user-tracking mechanism of the invention is incorporated into a co-operative game based on real physical location where players face a virtual enemy that travels the same streets. The tracking method is employed by a downloadable game application running on a mobile phone.

The rules of the game are formulated to make location a relevant and interesting part of the gameplay, to make the gameplay co-operative instead of confrontational (since players are potentially going to come into close contact) and to promote or enforce accurate location reporting (since the tracking method is completely consensual this could give large possibilities for undesirable cheating if not addressed-of course, the ability to sometimes cheat could be built into a different game as an intrinsic part of the play).

In the game rules points are scored by defeating'dual' (they have no physical presence in the playing area) enemies. Location is woven into the gameplay in that enemies are located on, and move along, the same paths (or streets) as the players, the enemies can only be seen on short-range radar and are most effectively attacked from close-range by multiple players, preferably from the rear. Co-operative gameplay is hence promoted by this advantage of acting as a team-the players can see all the other players on their radar and use that to arrange mutually beneficial tactics.

Physical location accuracy can be enforced or encouraged by cross-referencing against coarser-grained location methods (such as mobile phone cell location) and temporary opportunities to pick up and register codenames or words situated at physical locations- these can be bonuses or codes required to continue in game. These codes could be static (e. g. colour of door of a particular house) or dynamic-e. g. randomly generated and displayed on a wireless terminal in a shop-to limit avoidance measures.

As illustrated above, the basic concept of providing routing or tracking information based on an estimation of a user's position supplemented with user feedback has many applications, and the examples described above are by no means intended to limit the scope of the appended claims.