Karimi H.A. Universal Navigation on Smartphones

Подождите немного. Документ загружается.

100 5 Anywhere Navigation

Fig. 5.4

Indoor-outdoor algorithm cases. a Indoor-outdoor algorithm. b Indoor-outdoor algorithm

(non-overlapping case). c Indoor-outdoor algorithm for overlap but R not entirely within G case

101

Pgps  current position obtained

from GPS

Pgps = null

NUMgps– NUMrfid > 0?

t < Specified time?

Prfid  current position obtained

from RFID

Pgps = null

Prfid = null

Yes

NUMgps  NUMgps + 1

NUMrfid  NUMrfid + 1

t  t +1

Yes

User exits building

Yes

t 0

NUMgps  0

NUMrfid  0

Pgps  current position obtained by

GPS

Yes

Start

Yes

End

Fig. 5.4 Continued

5.4 Algorithms

Openmirrors.com

102

the destination. Even when all three sets of user’s preferences for the first building, the

outdoor, and the second building are the same (i.e., the user has the same routing pref-

erences in the buildings and in the outdoor), the computation still has to perform three

steps: one for finding a route in the first building (origin and entrance/exit door pair), a

second one for finding a route in the outdoor (entrance/exit door of the first building and

Fig. 5.5 A route from indoor to outdoor

Fig. 5.6 A route from outdoor to indoor

5 Anywhere Navigation

103

entrance/exit door of the second building pair), and the third one for finding a route in

the second building (entrance/exit door and destination pair).

5.5 Summary

In this chapter, the anywhere feature of UNAVIT is discussed. Anywhere is defined

as the ability of UNAVIT for providing navigation assistance regardless of user’s

location, indoor or outdoor. Possible cases for navigation assistance are indoor navi-

gation, outdoor navigation, indoor-outdoor navigation, outdoor-indoor navigation,

and indoor-outdoor-indoor navigation. Two algorithms, one for transition from in-

door to outdoor and one for transition from outdoor to indoor, are discussed and

analyzed. Although these two algorithms are based on GPS and RFID as the geo-

positioning sensors for determining user’s location in outdoors and indoors, respec-

tively, they can easily be adjusted for other geo-positioning sensors.

Further Readings

104

Bessho M, Kobayashi S, Koshizuka N, Sakamura K (2008) uNavi: Implementation and deploy-

ment of a place-based pedestrian navigation system. In: Proceedings of International Computer

Software and Applications, pp 1254-1259.

Feliz R, Zalama E, García-Bermejo JG (2009) Pedestrian tracking using inertial sensors. Journal

of Physical Agents 3:35-42.

Holone H (2007) Users are doing it for themselves: Pedestrian navigation with user generated

content. In: Proceeding of the 2007 International Conference on Next Generation Mobile Ap-

plications, Services and Technologies (NGMAST 2007), pp 91-99.

Huang C, Liao Z, Zhao L (2010) Synergism of INS and PDR in self-contained pedestrian tracking

with a miniature sensor module. IEEE Sensors Journal 10:1349-1359.

Mahler T, Reuff M, Weber M (2007) Pedestrian navigation system implications on visualization.

In: Proceedings of the 4th international conference on Universal access in human-computer

interaction: ambient interaction Beijing, China.

May AJ, Ross T, Bayer SH, Tarkiainen MJ (2003) Pedestrian navigation aids: information require-

ments and design implications. Personal and Ubiquitous Computing 7.

Retscher G, Thienelt M (2004) NAVIO- A Navigation and Guidance Service for Pedestrians. Jour-

nal of Global Positioning Systems 3:208-217.

Stirling R, Fyfe K, Lachapelle G (2005) Evaluation of a new method of heading estimation for

pedestrian dead reckoning using shoe mounted sensors. Journal of Navigation 58:31-45.

5 Anywhere Navigation

105

6.1 Introduction

Anytime navigation, a capability of universal navigation, refers to UNAVIT’s abil-

ity that provides navigation assistance based on the requirements and constraints

of different times in a day, different days in a week, different months, and different

seasons given specific locations. In other words, UNAVIT is capable of providing

navigation assistance based on both spatial and temporal variations. For example,

for an origin-destination pair, the least congested route during rush hours and the

safest route during the night hours may be considered.

Figure 6.1 shows time and situation as two factors influencing navigation in

outdoors. For example, a route optimal for navigation during rush hours is different

than the one which is optimal for navigation during non-rush hours. Similarly, a

route optimal for navigation on a dry road is different than the one which is optimal

for navigation on a wet road.

Anytime feature of universal navigation mainly concerns outdoor navigation,

based on such factors and criteria as summarized in Table 6.1. The table shows that

navigation could be influenced by time of day, day of week, and month and season.

Depending on a time of travel and the factor(s) influencing navigation based on a

specific mode of travel, UNAVIT will take into account different criteria for naviga-

tion and routing.

Factors influencing navigation during a day include non-rush hours, rush hours,

daylight, and dark. Factors influencing navigation in a week include weekdays,

weekends, holidays, and events. Factors influencing navigation in a season include

weather, dry condition and wet condition. Each time and mode of travel (i.e., driv-

ing, biking, and walking) requires consideration of a different set of navigation

criteria. Such criteria include congestion, safety, and accident.

Another important consideration in anytime navigation is purpose of trip, which

could be commute, leisure, or emergency. This means that the factors and criteria

in Table 6.1 may be modified depending on purpose of trip. For example, when

purpose of trip is commute, rush hours may be a factor, and when purpose of trip is

leisure, driving through scenic areas may be preferred.

Chapter 6

Anytime Navigation

H. A. Karimi, Universal Navigation on Smartphones,

DOI 10.1007/978-1-4419-7741-0_6, ©

Springer Science+Business Media, LLC 2011

106

Unlike navigation in outdoors, where factors at different times may influence

navigation activities, time has no impact on navigation activities in indoors. For

example, change of weather, rain or sun, does not impact the way one would walk

in a building. The only concern, however, in indoor navigation is accessibility at

different times. For public buildings, different times that could impact accessibil-

ity are weekdays, weekends, and holidays, where during certain hours the entire

building, certain floors, or certain rooms may not be accessible to all or some users.

Fig. 6.1 Factors influencing navigation in outdoors

Navigation

Environment

Origin-Destination

Situation

Wet road

Dry road

Route

optimal for

wet roads

Route

optimal for

dry roads

Route

optimal for

rush hours

Route

optimal for

non-rush hours

Non-rush

hours

Rush hours

Time

Table 6.1 Time factors influencing navigation

Time Factors Mode of Travel (Navigation Criteria)

Driving Biking Walking

Day Regular hours

Rush hours

Day

Night

Congestion

Safety

Congestion

Safety

Week Weekdays

Weekends

Holidays

Events

Congestion Congestion Safety

Season Weather

Dry condition

Wet condition (rain, snow)

Congestion

Slippage

Accident

Congestion

Slippage

Accident

Safety

6 Anytime Navigation

107

6.2 Ontology

Figure 6.2 shows an ontology for anytime navigation. The ontology represents vari-

ous concepts including time, situation, mode of travel, and type of network. In this

ontology, situation is a high-level concept that contains three sub-concepts: day,

time, and weather. Day may include weekday, weekend holiday and event. Time

may include day, night, and rush hour. Weather could be sunny or snowy. The mode

of travel concept, which could be driving, walking, or biking, uses different net-

works. The networks for navigation in outdoors could be road networks or sidewalk

networks, where each network segment (road or sidewalk) is either of primary or

secondary category.

6.3 Requirements

Table 6.2 shows time, event, and weather condition when navigation needs of driv-

ers may change. The table shows that drivers during non-rush hours typically prefer

shortest and fastest routes and prefer to avoid main roads and congested roads dur-

ing rush hours. During holidays, drivers usually would prefer to avoid congested

Fig. 6.2 An ontology for anytime navigation

User

Request

Navigation

Influenced-byInfluenced-by

Situation

Mode of

travel

Is-a

Day

Time

Weather

Include

Snowy

Sunny

Night

Rush

hour

Day

Weekday

Secondary

Primary

Secondary

Sidewalk

Road

Network

Holiday/

Events

Weekend

Include

Use

Is-a

Is-a Is-a Is-a

Is-a

Driving

Walking

Biking

6.3 Requirements

108

roads and those roads within close proximity to shopping centers. Similarly, in the

case of an event, such as a sport game, a show, or a concert, drivers would typically

prefer to avoid congested roads and those roads within close proximity to the loca-

tion of the event. Depending on weather condition, if roads are slippery due to rain

or snow, drivers would prefer to drive through main roads and avoid those roads

that have high slope. When driving at night, drivers usually prefer to drive through

well-lit roads.

Table 6.3 shows time, event, and weather condition when navigation needs of

pedestrians may change. The table shows that pedestrians during non-rush hours

typically prefer shortest routes and prefer to avoid sidewalks through main roads

during rush hours. During holidays, pedestrians usually would prefer to avoid con-

gested sidewalks and those sidewalks within close proximity to shopping centers.

Similarly, in the case of an event, such as a sport game, a show, or a concert, pe-

destrians would typically prefer to avoid congested sidewalks and those sidewalks

Table 6.2 Navigation needs of drivers in outdoors in different times/situations

Time/Situation Navigation Needs

Day Time Rush hours Avoid main roads

Avoid congested roads

Non-rush hours Usually:

Shortest distance route

Fastest time route

Event Holidays Avoid congested roads

Avoid roads within close proximity to shop-

ping centers

Game/Show/Concert Avoid congested roads

Avoid roads within close proximity to loca-

tion of the event

Weather

condition

Snowy/Rainy Route through main roads

Avoid roads with high slope

Night Route through well-lit roads

Table 6.3 Navigation needs of pedestrians in outdoors in different times/situations

Time/Situation Navigation Needs

Day Time Rush hours Avoid sidewalks through main roads

Avoid congested sidewalks

Non-rush hours Usually:

Shortest distance route

Event Holidays Avoid congested sidewalks

Avoid sidewalks within close proximity to

shopping centers

Game/Show/Concert Avoid congested sidewalks

Avoid sidewalks within close proximity to

the location of the event

Weather

condition

Snowy/Rainy Route through sidewalks on main roads

Avoid sidewalks with high slope

Night Route through well-lit sidewalks

6 Anytime Navigation

109

within close proximity to the location of the event. Depending on weather condi-

tion, if sidewalks are slippery due to rain or snow, pedestrians would prefer to walk

on sidewalks of main roads and avoid those sidewalks that have high slope. When

walking at night, pedestrians usually prefer to walk through well-lit sidewalks.

Unlike navigation in outdoors, which could adversely be impacted by environ-

mental factors such as change of time, event, or weather condition, navigation in

indoors is rarely impacted by environmental factors. However, it is conceivable that

change of time and occurrence of events may cause interruption or delay in navi-

gation in indoors. Table 6.4 shows time and event as two factors that may require

change in navigation needs of pedestrians or wheelchair riders. As shown in this

table, pedestrians or wheelchair riders during non-rush hours typically prefer short-

est routes and prefer to avoid congested hallways during rush hours (e.g., before a

class time in a school). In the case of an event, such as a class, a seminar, or a talk,

pedestrians and wheelchair riders would typically prefer to avoid congested hall-

ways within close proximity to the location of the event.

6.4 Algorithm

In general, there are two factors that may impose computation of new routes in

UNAVIT, as shown in Figure 6.3. One factor is change of time which may lead to

change of navigation needs. An example is a route that is optimal during daylight

but may not be optimal at dark. Another example is a route that offers fastest travel

time during the summer months when most schools are closed but is not fastest

route during the school months, typically in fall and spring terms, when schools are

open. An example event that may require a different route than shortest distance is

a football game where the roads near the location of the stadium are expected to be

congested during a period of time.

Routes can be computed based on three general situations at a given location:

fixed-time, new-event, and new-time-new-event. In the fixed-time situation both

location and time are fixed. In this situation, a route R

at time t

for a pair of origin

and destination locations can be computed and expressed as

(

−

) →

Table 6.4 Navigation needs of pedestrians and wheelchair riders in indoors in different times/

situations

Time/Situation Navigation Needs

Day/Night Time Rush hours

(e.g., before class time)

Avoid congested hallways

Non-rush hours Usually:

Shortest route

Event Class/Seminar/Talk Avoid hallways within close proximity

to the location of the event

6.4 Algorithm