Sage Journals: Discover world-class research

Abstract

People spend a great deal of time driving and performing daily tasks. Although a number of studies have focused on personalized path planning and task management, people tend to miss out on the opportunities to complete some tasks that could be accomplished on their regular drive. We are interested in supporting serendipity: completing other necessary tasks on the way to a destination. As there are a number of places to complete tasks around a driver’s regular commute, combining tasks and regular paths gives people opportunities to find places where they can complete tasks without extra planning and time. For this purpose, we propose a serendipity-empowered path recommendation that combines daily tasks with drivers’ regular routes for predictive task completion. The proposed approach first generates a number of diverse or serendipitous paths by iteratively extending routes to consider the given tasks of drivers and corresponding point of interests. It then selects the best path by ranking the serendipitous routes with their properties. Using the best path, users are then able to perform their daily tasks on the way to their originally planned destination. We evaluated the proposed approach by modeling regular routes and tasks from 12 local drivers, and simulating serendipitous routes with a simulation prototype. We found that using serendipitous routes reduced the number of trips and time required for completing the tasks. We also found that the drivers tended to do their tasks when they moved from their office to their home and had no preferred ranking strategy for selecting the best route.

Keywords

Task management path planning personalized route

Get full access to this article

View all access options for this article.

References

[1]

Kessell and

Chan, Castaway: A context-aware task management system, in: CHI ’06 Extended Abstracts on Human Factors in Computing Systems, ACM, New York, NY, USA, 2006, pp. 941–946.

[2]

A.K.

Dey and

G.D.

Abowd, CybreMinder: A context-aware system for supporting reminders, in: Proc. Symposium on Handheld and Ubiquitous Computing, LNCS, Vol. 1927, Springer-Verlag, Berlin, Heidelberg, 2000, pp. 172–186.

[3]

B.D.

Ziebart,

A.L.

Maas,

A.K.

Dey and

J.A.

Bagnell, Navigate like a cabbie: Probabilistic reasoning from observed context-aware behavior, in: Proc. of the 2008 ACM Conference of Ubiquitous Computing, ACM, New York, NY, USA, 2008, pp. 322–331.

[4]

Horvitz and

Krumm, Some help on the way: Opportunistic routing under uncertainty, in: Proc. of the 2012 ACM Conference on Ubiquitous Computing (UbiComp ’12), ACM, New York, NY, USA, 2012, pp. 371–380.

[5]

Laporte and

Martello, The selective travelling salesman problem, Elsevier Discrete Applied Mathematics26 (1990), 193–207.

[6]

Chung and

Schmandt, Going my way: A user-aware route planner, in: Proc. of the SIGCHI Conference on Human Factors in Computing Systems (CHI ’09), ACM, New York, NY, USA, 2009, pp. 1899–1902.

[7]

Hershberger,

Maxel and

Suri, Finding the k shortest simple paths: A new algorithm and its implementation, ACM Transactions on Algorithms (TALG)3 (2007), 1–45.

[8]

Fujimura, Path planning with multiple objectives, IEEE Robotics and Automation Society Magazine3 (1996), 33–38.

[9]

Patel,

M.Y.

Chen,

Smith and

Landay, Personalizing routes, in: Proc. of the 19th Annual ACM Symposium on User Interface Software and Technology (UIST ’06), ACM, New York, NY, USA, 2006, pp. 187–190.

10.

[10]

N.E.

Klepesis,

W.C.

Nelson,

W.R.

Ott,

J.P.

Robinson,

A.M.

Tsang,

Switzer,

J.V.

Behar,

S.C.

Hern and

W.H.

Engelmann, The National Human Activity Pattern Survey (NHAPS): A resource for assessing exposure to environmental pollutants, Journal of Exposure Analysis Environmental Epidemiology11 (2001), 231–252.

11.

[11]

Jing,

Y.W.

Huang and

E.A.

Rundensteiner, Hierarchical encoded path views for path query processing: An optimal model and its performance evaluation, IEEE Transactions on Knowledge and Data Engineering10 (1998), 409–432.

12.

[12]

P.J.

Ludford,

Frankowski,

Reily,

Wilms and

Terveen, Because I carry my cell phone anyway: Functional location-based reminder applications, in: Proc. of the SIGCHI Conference on Human Factors in Computing Systems (CHI ’06), ACM, New York, NY, USA, pp. 889–898.

13.

[13]

Statnikov and

J.B.

Matusov, Multicriteria Optimization and Engineering, Springer, 1995.

14.

[14]

Ebendt,

Sohr,

L.C.T.

Tcheumadjeu and

Wagner, Utilizing historical and current travel times based on floating car data for management of an express truck fleet, in: Proc. of 5th International Scientific Conference, 2010, pp. 283–291.

15.

[15]

Davidoff,

Zimmerman and

A.K.

Dey, How routine learners can support family coordination, in: Proc. of the SIGCHI Conference on Human Factors in Computing Systems (CHI ’10), ACM, New York, NY, USA, 2010, pp. 2461–2470.

16.

[16]

Vanhove and

V.F.

Ugent, Fast generation of many shortest path alternatives, in: Proc. of 6th International Conference on Geographic Information Science (GIScience 2010), Extended Abstracts.

17.

[17]

Sohn,

K.A.

Li,

Lee,

Smith,

Scott and

W.G.

Griswold, Place-Its: A study of location-based reminders on mobile phones, in: Proc. of the 7th International Conference on Ubiquitous Computing (UbiComp’05), Springer-Verlag, Berlin, Heidelberg, 2005, pp. 232–250.

18.

[18]

Blue,

Adler and

List, Real-time multiple-objective path search for in-vehicle route guidance systems, Transportation Research Record Board1588 (1997), 10–17.

Serendipity-empowered path planning for predictive task completion

Abstract

Keywords

Get full access to this article

References