Pragmatic Routing based on Landmarks


Vaidhyanathan Mayilrangam Gopalan
C5 Green Meadows
28/2 Haralur Road
Ambalipura Village
Bangalore
India.
Phone:9341705663
vaidhy@folkmaps.com

A common application of using maps is to figure out routes between places. Most maps, intended for common usage are not designed keeping this in mind. The existing systems focus on translating GIS information into pictorial form and correctly labeling them. These systems provide route information only in terms of absolute directions and distances.

In developing countries like India, such route information is of very low practical value due to various reasons such as difficulties in measuring distances, poor road labeling etc. Furthermore, useful information such as current road conditions, time it takes to travel etc are not available at all.

When we think of routes, we have a mental image of the route that bears very little in common to the route drawn on a map. Our mental image is based on landmarks and approximate distances measured in terms of time or cost. This information is of higher utility value and is more user friendly.

In this paper, we discuss the requirements for a technology based solution that makes is easy to store, represent and manipulate maps based on our mental picture of landmarks, relative distances, relative directions and their properties. We will also discuss how recent advances in networking and mobile connectivity can help in gathering such information.

Introduction
A general mapping service, although useful, may not always be practical (especially in developing countries). Mapping services on the web like MapQuest, YahooMaps and GoogleMaps provide specific information about the route queried. The route is highlighted in the map and precise driving directions are also provided like distances to be traveled, turns to be taken along with their curvatures and the distances between two turns. Yahoo also provides an idea of traffic conditions as well.

Although routing is essentially answering one simple question of “How do I go from A to B?” it is very important to understand the context in which it is being asked. A one-size-fits-all answer that does not take into account the context is not useful. Pragmatic routing is all about providing route inputs that are “practically” useful in the current context of the user.

In this paper we will identify the user context to derive the requirements for a pragmatic routing service. We will then propose an architecture and focus on the data representation aspects. We will also discuss how landmarks based routing is more pragmatic than routing based on absolute distances and /or directions.

Context of User when the routing query is posed

In this section, we identify the context of the user (the person posing the query) surrounding the routing query. User context is primarily a function of the user’s intent, where the user is and the communication modes the user has access to. For simplicity, we consider two primary dimensions and derive the requirements

Understanding who the user is and the intent behind the query

It is important to understand who the user of a routing service is. In particular, whether the user is indeed the traveler of the route; or whether the user is someone who wants others to travel that route. Knowing who the user is, enables the routing service to provide context sensitive answers. In general, the mapping service providers are not concerned about who the user is.

The following paragraphs present various usecases classified by intent.

Travel
If the user is the traveler, the ideal routing service should provide information in a personalized fashion. For example, if the user is known to be a resident of the city the system can perhaps assume that the user knows certain landmarks better than others. It is also likely that a resident is more likely to be interested in ATM’s or eateries compared to lodging accommodations. Such personalization would typically be expected especially when the user is planning – if a user can convey that he is likely to be in a certain neighborhood during a certain time, a smart system can also figure out lunch/dinner options, entertainment avenues etc. If the system is also aware of other activities/transactions that a person performs in that neighborhood (like paying some utility bills) or if it is integrated with the user’s personal calendar, it can perhaps even inform the user the possibility of getting some things done if the user actually travels.

Share
All of us are familiar with invites from our friends and family for a house warming ceremony, which contain an approximate local map of the neighborhood that describes where the new house is along with bus route numbers and nearby landmarks. Here is a prime example, of the host wanting the invitees to know how to reach her place from multiple directions in the vicinity of the meeting place. It is also common for many organizations to have such maps on their websites that give directions to their office from various points in the neighborhood. In both these cases, there is a vested interest for someone to share some approximate partial routes with either a limited group or public in general.

Assist
Another non-obvious user is the agent in a call center that is helping travelers with route information. In this scenario, the actual user of a technology solution may in fact be the agent on behalf of the traveler. Mass transit systems in many developing countries do provide such services and some of these are automated based on IVR technology. However, for pragmatic routing such systems should also be augmented with “current traffic conditions” so that the time constraints of the traveler can also be factored in. Needless to say, in large metropolitan cities there are multiple mass transport systems and multiple options for private transport. Therefore pragmatic routing would also necessitate real time information sharing and integration between each of the transport systems.

Advertise
There is yet another non-obvious use case where the user may want to go beyond sharing. Tour operators (be it walking tours, biking tours, bus rides, cruises, etc.) may want to advertise certain routes to tourists. In this case the pragmatics for the user is around monetizing a certain route. A tour operator would then advertise his routes on a certain routing service platform only if that service platform is “popular”. In addition, the operator would also expect marketing tools to brand and promote his/her tour uniquely, delivery of personalized advertisements to targeted customer demographics and perhaps value added services like ticket sales and customer support services as well.

Manage
There may also be some enterprises and certain kinds of businesses where the user of a routing service is not necessarily the traveler. The user here is usually engaged in planning and/or optimizing the assets-on-the-move of the business. For example a logistics or transport services company may want to centralize manage its fleet of vehicles and crew based on the current location of their assets in a geography. In this case, the user would like to know where each of the assets are within that geography at any given point in time, their current tour plans and constraints and the business importance of the service requests that come in dynamically. It is very important for this user to have a dashboard view of the various routes that each of their assets are currently engaged in and superimpose that with a dynamic request for moving from A to B.

Plan
A rally or treasure hunt organizer designing the game would need the following information for planning
  • Points where the marshals should be placed
  • The landmarks en route and associated trivia based on which cryptic clues can be posed
  • Typical traffic conditions at the time of the day on the day of the rally
Clearly, a generic routing services provider cannot meet the requirements of all these user contexts.

Understanding when the query posed

Before-travel
The routing query posed before the travel is for planning purposes. In such a scenario, the user is unlikely to be unduly perturbed by either a poor response time or information overload. Today mapping services on the web like MapQuest do satisfy this requirement and provide both route information as well as neighborhood/local information such as restaurants, lodging, access to mass transport services, etc. In some countries, mass transport companies like metro rail and bus services also provide a routing help desk to help passengers plan their travel by answering questions over phone. Even in developing countries like India, there are third party information services providers in some cities who provide a variety of information over phone, route information being one of them.

Regardless of who poses the query and who travels, the query will very likely be posed through a computer (web browser) or a phone (voice), and the response is typically obtained over the same communication medium. The results may be delivered in a variety of formats – graphical maps, voice response, textual description of route to be taken, a combination of map and text, etc.

But most importantly, for pragmatic routing one may need more than a presentation of multiple possible routes. An ideal pragmatic routing service must also give “advice” to the user, as in answer the “best” route from A to B. The notion of “best” may be derived from optimizing on any of the cost (benefit) weights associated with the route segments. This could be cost, distance, time, scenic beauty, and so on; and so the system should allow the user to personalize one’s cost function to suit one’s context. An ideal system may even “learn” (hypothesize) this cost function based on the user feedback.

The before-travel query can also be associated with some constraints such as the following:
  • Can start the journey no earlier than a specific time instant
  • Must be at location X in the time period T1 to T2
  • Need to pick up something specific to eat for dinner along the way
  • Don’t want to be at location X between T1 and T2
Needless to say a planning interface must be intuitive and provide the user with the ability to get all routes as well as the best route(s), with or without constraints. Today mapping services don’t seem to solve the optimization problem or the constrained routing problem. Although many of these problems are solved from an algorithm perspective, the bigger challenge is in surfacing these as intuitive, user-friendly features of a routing service on a web browser.

During-travel
Answering the query while the user is on the road is a different problem. A user may want to pose this query for a variety of reasons –
  • To confirm the route while traveling because she could have lost the way
  • I started at A, I don’t know where I am now and I want to reach B
  • I started at A, I know I am near X and I want to go to B from here
  • I am a passenger in the cab and I suspect he is taking me for a ride
Another aspect of the during-travel query is to understand whether the user is walking, driving a vehicle, or being driven in a vehicle as a passenger.

While on the road, absolute distances (like 1.3 km) or absolute directions (like North East) have very little value. Unless one is driving a GPS equipped vehicle, it is virtually impossible to know where one is for all practical purposes. In developing countries, road and location labels are poor or simply non-existent, making even GPS + GIS systems hard to use. As a result, we often rely upon simply asking a person in the neighborhood. We also have the knack of solving our problem by asking a trustworthy person, even if he is remote, to navigate us over a mobile phone. More often than not, this is the only thing that works in developing countries.

A very key aspect of the during-travel query is that the user will want a quick and pointed response, unlike the before-travel query. Sometimes this query may also be under distress, and so the quality of service such as reliability, availability and performance become very important.

To summarize, a pragmatic routing service can serve the user better depending upon whether the query is asked before the travel or during the travel. In the next section we present the requirements for a pragmatic routing service based on this discussion

Why landmark based routing is pragmatic
From our experience, we know that people really need detailed directions only for the last mile around a certain point. While the directions need to be detailed, they need not necessarily be accurate as in exact distances to the tenth of a kilometer or exact orientations as in North-East etc. What is really helpful in this situation is “visible” landmarks that a person can easily find once he reaches that neighborhood. Another interesting point to note here is that these visible landmarks may not be as popular as some of well known landmarks in the city like an airport or railway station. It can be something like a billboard or a convenience store that is well-known or well-recognized locally. In fact, this is exactly how we describe routes to others today in India.

Even if various kinds of routing and optimizing algorithms can be used, at a fundamental level, we propose a model that treats every route as a concatenation of route segments between landmarks.

If a user wants to travel from A to B,
  1. Find out a landmark ‘a’ near A
  2. Find out a landmark ‘b’ near B (for intermediate route segments, a=A and b=B)
  3. Find from the system how to go from ‘a’ to ‘b’ using the most appropriate algorithm
  4. Find locally or from the system, the following small routes - A to ‘a’ and ‘b’ to B
Requirements for a pragmatic routing service
In this section we enumerate the requirements derived from the discussion surrounding pragmatics of the routing query in the previous section.
  1. System must personalize the routing information based on the context of the user.
    1. The system must provide an intuitive and natural user interface for the user to provide hints about the intent behind the query. The system should assume default intents based on profile information stored about the person, as well as from the context such as time of query, point of access, user’s familiarity of certain neighborhoods (specified in profile or derived from user feedback over a period of time).

  2. Ideally system should provide planning tools for doing what if analysis. User can get a sense of impact on cost, schedule, etc for analysis such as
    1. What if I must have lunch between 1 pm and 2 pm
    2. What if I change my itinerary by dropping, or adding or replacing a place?
    3. What if I take the metro rail instead of a cab?

  3. Since pragmatic routing relies upon accuracy and currency of information, the system should have the right data capture mechanisms that ensures this quality of service.
    1. Pragmatic routing relies upon a variety of cost/benefit functions of route segments. The system should therefore provide for efficient input, manipulation, storage and usage of such cost/benefit data models.
    2. Where accuracy or quality of data is suspect, it will be nice if the system can still assume smart defaults (perhaps based on history and probabilistic models) to deal with uncertainty and still provide optimistic/pessimistic/most-likely answers.

  4. System must store useful information about public/private places such as type of business, business hours, products/services that can be purchased or accessed at that location, etc.; so that the user can discover these places as part of a constrained routing query. The system must provide for modeling multiple costs/benefits associated with traversing of through a specific point or taking certain roads, so that the user can figure out the “optimality” of routes based along multiple dimensions.
    1. Needless to say, wherever possible the system should use smart defaults to enable approximate reasoning.
    2. It will also be nice for the system to learn such cost models based on user feedback
    3. A sophisticated system may even support the notion of public, shared and private cost models.

  5. It should be possible for individuals and organizations to share partial and approximate routes to a certain location in a neighborhood.
    1. The routes may be only for the “last mile” journey to reach that location.
    2. Any map should be based on “visible landmarks” in that neighborhood, as opposed to instructions based on absolute distances/directions.
    3. Such sharing can be limited to a group of users or with public in general.
    4. While organizations share such routes, they may also want to include branding aspects and advertise their business

  6. The system may be accessed in multiple modes – web browser, mobile phone, landline, text messaging, email, call center, etc. Therefore the architecture and design should support
    1. Support multiple channels of access as well as information delivery
    2. Support self service as well as human-assisted service delivery
    3. Support the development of enterprise applications that manage the location and movement of assets distributed in a geographical area (like fleet operators, MRO in large manufacturing plants, etc). Such applications may need very specialized dashboard views for monitoring the assets as well as for planning their movement.

  7. The system must support during-travel queries intuitively and efficiently. This means a user interface based on mobile phones (voice based as well as text/graphics based).
    1. One of the challenges in supporting such queries is enabling the user to specify where he currently is. In developed countries the signs on the roads are usually good and can be relied upon, and sometimes people have access to positioning technology such as GPS. That is not true is developing countries like India, and this is where landmarks become extremely important, because we the user can now specify landmarks that he has seen till now and ones that he is currently seeing; and the system can determine where the user is approximately based on such inputs. The other possibility in developing countries is to leverage any location information that a mobile phone services provider may be able to provide.
    2. There are a variety of reasons why this query may be posed during travel and sometimes it could be an emergency situation as well. Therefore the routing service should be reliable, available and scalable meeting expectations of very quick response times. The service should also avoid information overload and be as specific as possible, so that even a person under distress can use it effectively.

  8. Ultimately this system has rich data about various kinds of flows in a geographical area. Therefore it is conceivable that government agencies like emergency response forces (like police, fire, ambulance, counter terrorism) will need to use this to manage and regulate the traffic flows during or post an incident. The system should support broadcasting of commands and information from a centralized control room so that the mobile response forces can implement decisions quickly and effectively. Citizen interfaces can also be provided for alerts and broadcasts delivered over radio, television or SMS messages.

Solution



From the above discussion it is obvious that the solution primarily involves stitching together multiple technologies that are already mature and deployed in other applications successfully. Since data is the key asset here, we would like to focus our attention on the storage and retrieval aspects in this paper. One would normally expect a database with spatial extensions for GIS applications. However these extensions often use sophisticated co-ordinate geometry and are neither required nor adequate for the approximate geometry for our pragmatic routing.

Given that route information
  • Can be approximate
  • Must use friendly concepts such as landmarks and roads as opposed to latitude/longitude, exact distances, etc.
  • Need not always be delivered in terms of pictorial maps
  • Must be augmented with additional information such as cost models for places and roads
  • Must be derived from approximate and uncertain data,
the data model should support the following entities:

An abstract MapElement entity which would contain the following attributes:
  • Name with all aliases
  • Level of visibility (how well known this entity is known to people)
  • Tags to classify this entity under one or more categories
  • Cost Models to quantify various dimensions such as quality, scenery, etc
  • Adjacent elements derived from other known information

An Area is a MapElement which also has:
  • Size
  • Zip code
  • Parent area if this area belongs to another area
  • Direction relative to popular landmarks like Airport, Railway station, etc

A Landmark is also a type of MapElement which contains the following information:
  • Area it belongs to
  • Roads that pass by
  • Direction relative to popular landmarks like Airport, Railway station, etc

Road is also type of MapElement which contains:
  • Areas and landmarks through which it runs
  • Length
  • Type of road (paved, gravel, divided highway etc)
  • Number of lanes
  • Direction of travel (one way/both ways)
  • Presence of footpath

Using these key elements, along with user profile, dynamic data about current conditions like weather, traffic pattern etc., it is possible to provide the users with routing information that goes beyond what can be got from just the map

Summary
In this paper we have analyzed the needs of users in developing countries. It is apparent that existing mapping services do not address many of them, and there is a need for a different type of system that factors in the user context as well as the natural ways to describe routes based on landmarks. We have also explained why, a pragmatic routing service should be based on landmarks for it to be effective.