Serendipity-empowered path planning for predictive task completion

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

1. Introduction

Modern life often involves people that are very busy with a number of everyday tasks related to the home, office and other significant places. The tasks range from buying items to picking up packages. People tend to do their tasks by finding places associated with the tasks in their neighborhood and making time for performing them after work or during the weekend. According to one lifestyle survey, people spend 2.5 hours of extra time doing these types of tasks per day in addition to their regular driving for commuting [10]. Although people can complete a number of everyday tasks by making plans that take extra time and involve extra driving, doing this every day is definitely time-consuming and potentially quite stressful. Furthermore, as people engage in more activities, the number of associated tasks will increase, but they will also have less time to complete the tasks.

In order to help people complete their everyday tasks efficiently, a number of studies have been conducted in task management and path-planning research areas. Location-based task management systems manage tasks and remind people of the tasks at the appropriate time in a predetermined place [2,17] Later work focused on managing and sending reminders about everyday tasks [12] by matching tasks and places and notifying users when a time or place is matched. However, in task management, tasks are temporally or geographically fixed, thus it is difficult to do them in a different time and/or location. In path planning, some of the studies concentrated on having users complete tasks while already driving. A number of these studies investigated the creation of personalized paths to complete tasks. However these are unlikely to be used to complete tasks during a regular commute since preferred routes included a limited set of POIs that correspond to tasks. More recent work has tried to support performing a single task on the way to any destination (i.e., outside of a regular commute) [4]; however, people often have more than one task to perform, which makes real-life path and task planning exponentially more complicated.

We are interested in combining multiple everyday tasks with a person’s daily commute. Commuters who drive on a regular basis have a number of opportunities to complete their tasks along their regular route. Since drivers know their neighborhoods and there are different routes that can be taken to a certain destination, they can find opportunities to perform some of their tasks without taking extra trips. According to a study on family routines, families had an established set of routines in their daily life and 37% of their driving was related to regularly driven routes [15]. In addition, there may be multiple places where a person can accomplish any particular task. These behavioral patterns and knowledge of the local environment can be used to gain insight into how commuters perform their tasks as part of their everyday commute.

In order to overcome the difficulty of managing everyday tasks during regular driving, we propose a serendipity-empowered path-planning system that combines everyday tasks with a route to a chosen destination. Serendipity refers to an unexpected or unplanned but fortunate occurrence. In our path planning, a task can be integrated serendipitously and may or not be completed based on a driver’s preferences and other factors.

The system proactively generates possible alternative paths when given a particular destination and specific tasks. A task whose location is close to the optimal path is selected, and added to build an alternative path. Similarly, more alternative paths are generated for accomplishing more tasks. Finally, the best path is selected after evaluating the quality of the paths with the tasks that were found to be on that path. Thus this type of path planning is able to predict and recommend alternative paths that give users chances to perform tasks on the way to a particular destination by slightly changing the original path. If some tasks are able to be completed on the way to an intended destination, this contributes to reducing the overall amount of driving and time that would be required for completing these tasks at another time. Another result might be the discovery of new places for performing tasks and/or alternative routes to a destination.

In order to validate the effectiveness of our path-planning system, we implemented a path-planning simulation system and evaluated it with local participants. We first collected regular route history and everyday tasks from the local participants who regularly commuted for 3 weeks. We then modeled each driver’s route preference and used it for finding regular routes in the road network. Finally, we evaluated the system with three path-planning scenarios and 12 participants.

We found that the proposed serendipitous path planning reduced the number of trips and time for performing daily tasks and found that drivers tended to perform tasks on the way home from their office when they had more time available. They did not have a preferable ranking strategy for selecting the best route for performing the tasks.

This paper is organized as follows. We first introduce related work in terms of location-based task management and personalized path planning. We then propose our path planning approach described above, and describe our evaluation procedure and results. Finally, we conclude with future work.

2. Related work

We first analyze related work that has focused on task completion in terms of location-based task management and personalized path planning.

2.1. Location-based task management

Task management and scheduling strategies have mostly dealt with scheduling tasks to help busy workers. As there are a large number of research projects focusing on task scheduling, we focused more on location-based task management that exploits geographic information, similar to our approach.

CybreMinder is a context-based reminder system that allows users to manage and receive reminder messages when specified times and locations are matched [2]. Place-Its is a location-based reminder which runs on mobile phones [17]. It allows users to create post-its related to places and reminds them of the posts when they approach those places. Castaway is a context-aware task management system [1] that finds locations associated with particular tasks. It visualizes the tasks on the map and reminds users of these tasks via SMSs when specified times and locations are matched. PlaceMail is a functional location-based reminder application that integrates a location-based reminder service with task scheduling [12]. Users are asked to schedule each of their everyday tasks with a certain location and time and then they are reminded with a message when they are near any of their locations. This system allows users to manage their tasks and lists (a set of “to-dos”) and to increase the possibility of completing the tasks by reminding them even when they have no plans to travel to those places. The main advantage of this system is that it gives users a simple reminder message about upcoming tasks that can be completed nearby to their current location. However, the tasks must be geographically fixed at certain locations and times and thus there will not be other reminders for these tasks and they cannot be completed at an alternative location.

Although tasks are geographically scheduled by these task management schemes, the places where the tasks can be completed are fixed. However, there are often a number of places that are related to a user’s tasks that are near the areas through which they commute. While one’s dry cleaning must be picked up at the place it was dropped off, other tasks such as buying milk, for example, can take place at any grocery store, not just one particular store. Furthermore, users regularly have multiple tasks or errands that they need to perform, often distributed across different places. As users manage a number of everyday tasks, scheduling and performing these tasks is cumbersome.

2.2. Personalized path planning

While path-planning studies typically focus on finding the best path which satisfies drivers’ preferences, there are a number of studies that combine tasks with geographic information. Path planning, which is a system finds the best path for drivers, has a long research history. Initial studies focused on finding the fastest route between a given starting location and destination in a large road network (e.g., [11]). Recently, a number of studies have focused on finding personalized paths that take the driver’s context into consideration. MyRoute generates personalized paths by exploiting a user’s familiar landmarks and routes [9]. It first builds a personal profile consisting of landmarks and preferred route data. Using route compression and rerouting it then generates the best route with respect to known landmarks in the profile. Route compression reduces the route by using the known landmarks, and the rerouting strategy combines familiar routes with unfamiliar routes to find the best alternative if there are no known end points.

As an alternative, PROCAB predicts the best path for vehicle navigation by exploiting context-dependent utilities and probabilistic reasoning [3]. It models path utilities based on a number of contexts involving path features and driver preference and probabilistically reasons about the best path based on a Markov decision model. The inventors of this technique evaluated their proposed path-planning model by collecting data from a number of taxi drivers and found that it predicts the best path in terms of turns, route and destination more accurately than other competing methods. Going-My-Way is a mobile user-aware routing system that collects GPS data and provides directions using automatically selected landmarks [6]. This system is useful when drivers do not know much about the areas through which they are driving. This system recommends recognizable landmarks in the vicinity of the destination. The researchers found that people tend to use landmarks to recognize their destinations.

Horvitz and Krumm introduce opportunistic routing for drivers to help them complete a task when the final destination is uncertain [4]. Their system works as follows: A user has a final destination, but has not explicitly specified it to the system. The user has one task to complete and thus needs to visit a place related to this task. Research questions were designed to find the best point-of-interest (POI) associated with one task (e.g., gas station) and to decide when to ask a user to specify his/her destination. For this purpose, the path planning system selected the route that had the smallest deviation from the planned route to the destination. Furthermore, in order to obtain the best path with minimum user input, it asks the user to specify his/her destination, but only when the extra driving cost for an uncertain destination is higher than the expected minimal cost of extra driving from having to learn the destination.

Finally, there are multi-object path planning approaches that find the best routes by exploring multiple factors such as travel time, travel length, and turns [8,18]. This approach requires making trade-offs between those factors through multi-criteria optimization.

Thus, most existing path-planning strategies have focused on finding the best or fastest routes. While this path may be the best or fastest, users are still often required to take an additional trip to complete their remaining task according to upcoming route. Furthermore, although there are many places to accomplish a task near their routes, they may miss other opportunities to complete additional tasks located on alternative routes nearby. Horvitz and Krumm’s work describes a system that provides the best solution to date. Their system supports drivers in completing a single task while driving to a particular destination. The limitation of the approach they describe is that it only considered the possibility of a single task being performed during each trip. However, people usually have a number of tasks to perform at any given time (evident from the popularity of task management apps on smartphones) with varying priorities and time requirements. They may, at any time, choose to perform a subset of these, and postpone the others. Any real-world solution must account for these issues.

Our approach is to combine everyday tasks with daily commutes in order to allow users to complete these tasks on their way to their destination. In terms of the path planning, performing tasks on the way to a certain destination will reduce the extra cost of doing these tasks. In terms of task management, serendipitous routes enable users to perform their tasks without explicit planning or large unexpected delays. Therefore, our proposed approach allows users to complete their tasks more flexibly by temporally and geographically rescheduling them according to their regular driving routes. We also validated our approach by collecting driving data and task management and simulating three path planning strategies with 12 participants.

In order to support combining everyday tasks with daily commutes, we are interested in the following research questions:

Is it possible to combine daily tasks with commuting routes?

What are the benefits of performing tasks during daily commutes?

Which alternative path is the best for a given route to complete a set of tasks?

Through answering these questions, we will be able to build a serendipity-empowered path planner that combines tasks with daily commuting routes. These tasks will be used as factors that influence the selection of the best paths that will reduce extra driving and support task completion.

3. Predictive task completion scenario

We are interested in supporting everyday tasks that regularly happen and require users to drive. These tasks are often on some kind of list and are completed at an available time and location. In other words, the location or time is often not fixed at the time of the task creation. We consider being able to complete these tasks as serendipity as they can be scheduled geographically and temporally as part of driving an everyday route. As serendipity means unexpected happiness, we refer to these as serendipitously accomplished tasks since the user is able to accomplish tasks without deviating much from their regular route.

Here is an example of serendipitous task completion during a daily commute. John lives in a home with his family and works at a company. He regularly shops for goods and food for himself and his family. We will assume that John regularly commutes to his office located in a downtown area and has regular tasks such as buying groceries and withdrawing money from his bank’s ATM. He is on his way home and has tasks to complete. He regularly first drives home and then decides to do the tasks which need to be done first. He drives to buy groceries since he knows that there is a Costco in his neighborhood. He is unable to drop by a bank on this trip because his bank is too far away. He thus postpones the task of withdrawing money. However, our Serendipity Planner combines the tasks with his commuting routes. It first generates alternative paths that include places associated with the tasks. It then evaluates the alternatives based on their cost and utility. Finally, it visualizes the alternative path as a serendipitous route on the way home. As a result, the route home includes his bank and Costco. Thus John is able to accomplish the tasks on his way home. He is therefore free from the necessity of accomplishing his tasks after coming home and can spend the time he saved on his family or his hobbies.

4. Serendipity-empowered path planning

In answering these questions, we propose a serendipity-empowered path recommendation method that generates paths by combining tasks with regular routes, and ranks them with respect to trip information and user’s preferences. Figure 1 shows the overall procedure of our path recommendation method.

Fig. 1.

Serendipity-empowered path planning.

As can be seen in Fig. 1, the serendipity-empowered path recommendation starts with tasks managed by the user when the user starts to drive. It first predicts the driver’s destination using previous route preferences and the driver’s current location. It then generates the optimal and expected path from the current location to the destination based on the user’s route preferences [3]. Next, for each user task, it selects the best place where the task can be accomplished and whose cost of traveling is lower than other potential places. It then extends the optimal path to include the selected place. It continually repeats this process extending the route until all tasks are included in the path. Finally, the planning system evaluates the serendipitous route selected based on multiple factors such as travel distance, time, turns, and number of tasks that can be performed on this route to find the most optimal serendipitous route. The system visualizes this best route with tasks on the map.

4.1. Task and place selection

As we expect that there are a number of places associated with tasks near by the driver’s route from starting her place to her destination, we select places that are close to this route. For measuring the extra cost of visiting intermediate places, we use the extra cost method used by Horvitz and Krumm, which considers the additional cost required to perform a task [4]. The previous work only considered the distance of task-related places from the current location and predicted destination. In our work, we extend it to support multiple tasks and use the distance from every intersection of each predicted route. We first define the extra cost for completing a task and then select the place associated to a task which has the lowest extra cost.

Let Loc_Current, Loc_Dest, Loc_place be the current location, predicted destination, and the location of a place associated with a task. The function $Cost (x, y)$ returns the driving cost from location x to location y. Here cost can be travel distance or travel time for the path between the two points. The extra cost of each place is calculated by subtracting the original driving cost of the preferred route from the total cost required for performing a task at the place, as shown in Eq. (1). $\begin{array}{l} ExtraCost ({path}_{k}, {place}_{i}) \\ = (Cost ({Loc}_{current}, {Loc}_{{place}_{i}}) \\ + Cost ({Loc}_{{place}_{i}}, {Loc}_{Dest})) \\ - Cost ({Loc}_{current}, {Loc}_{dest}) . & (1) \end{array}$

Then the place associated with a given task that has the lowest extra cost will be selected as shown in Eq. (2). As there is more than one task and there are a number of POIs that can apply to each task, we efficiently apply this equation. Initially, we assume that this POI selection step starts with POIs for the city the user is currently in. Even though there are a large number of POIs, only a subset of these are related to the user’s tasks. We first select the subset of POIs that correspond to the given tasks and build a Quadtree according to their location to reduce the search cost. We then filter the set of POIs to those whose distance from a point on the current path is less than 1.5 times the distance of two consecutive edges of the current path. This is because the extra path should not deviate significantly from the original path. We then select the POI whose extra distance is minimal and use it to build an alternative path with respect to the original path and task. $\begin{array}{l} {place}^{*} \\ = \underset{{place}_{i} \in POIs}{argmin} (ExtraCost ({path}_{k}, {place}_{i})) . & (2) \end{array}$

4.2. Serendipitous path generation

As there are a number of possible routes from a given start to a given destination, it is necessary to find serendipitous paths that enable users to visit places related to tasks. There are two types of path-finding strategies for a given trip. Well-known path-finding approaches such as $A^{*}$ and Dijkstra focus on finding the shortest path from the start to the end point. Instead, the k-path generation approach finds k number of alternative paths from the start to the end point [5]. However, its resulting paths do not include tasks because this method generates paths by repeatedly breaking and combining sub-routes without regard to tasks [7,14].

Our approach is to consider this path generation to be a selective traveling salesman problem and thus build alternative paths by adding intermediate destinations related to tasks [5]. For this purpose, this approach extends routes by repeatedly selecting and adding places using the cost function as illustrated in Algorithm 1. Initially, this algorithm has the POI selected by Eq. (2) and the visiting list consisting of start location, intermediate POIs, and destination. The goal is to find a path including ${place}^{*}$ as well as the points of the visiting list. It first finds the optimal route without regard to tasks in order to find serendipitous routes similar to the user’s preferred route. For this purpose, it selects the position in the visiting list whose distance is smaller than the others. It builds extra paths for visiting ${place}^{*}$ from the places before and after the position found. It then extends the path of the visiting list by adding the extra path. For obtaining k paths, it repeatedly adds nearby places associated with given tasks and builds serendipitous routes whenever ${place}^{*}$ is selected. It continues this path generation step until all the tasks are included in these routes. Finally, it obtains k number of paths, each of which includes 1 to k tasks. Algorithm 1 shows the overall procedure of our path generation approach. In order to build more diverse alternative paths, costtype of buildAStarPath() could be changed and more paths can be obtained with respect to given tasks. For example, costtype could be travel time or distance of a path.

Algorithm 1 4.3. Path ranking

As there are a number of serendipitous paths to a given destination that include a given set of tasks, we must determine an appropriate method for finding the best path for a trip that includes these tasks. This problem can be considered one of multi-criteria recommendation, since a number of factors affect the quality of the paths generated [13]. These factors may include time, length, turns, and the number of and specific tasks included. In order to deal with these factors together, linear optimization and active learning could be applied. However, determining constraints of linear equations might be difficult in a number of path scenarios and active learning still requires user inputs for customizing parameters to be learned.

Thus we are interested in a simple way of ranking which does not require additional learning of a user’s preferences. There are several methods with which to deal with multiple factors. The first strategy is an average utility strategy (AvgUtility) that sums up all the factors. This strategy is simple to calculate and is frequently used in multi-criteria recommendation. Yet it doesn’t consider the deviation among factors. For example, one path includes 5 turns and takes 5 minutes while another path includes 3 turns and 7 minutes. These two paths are considered to be the same rank in the AvgUtility. In the path ranking, multiple factors might affect the quality of each path. We use a ranking method called multiplicative utilitarian (MultiUtility) that multiplies all values. As this strategy is multiplicative, the route with higher values and lower deviation among these values will be selected. In other words, the deviation among these values affects the quality of a path.

5. Evaluation

We evaluated our path recommendation strategy with 12 local participants living in Pittsburgh, PA, USA. We collected GPS traces of their regular route and task history by deploying an Android app on users’ smartphone. On average, we collected data for 24.5 days from our participants. One participant had 15 days worth of data collected, seven participants had more than 21 days collected, and four participants had more than 28 days collected. After completing the data collection, we then modeled their route preferences [3], and produced a simulation with three path recommendation scenarios. This section describes how we evaluated the path recommendation approach based on our simulation.

5.1. Hypotheses

We hypothesized methods and factors for building and selecting the best alternative paths that include daily tasks. We were first interested in wether:

Serendipitous routes will decrease the number of trips and overall travel length required to complete tasks.

Users will prefer to complete tasks as early as possible if the tasks are planned.

In addition, we expected that:

Serendipitous routes that will be selected more frequently than the best path which includes no tasks.

Users who will consider both the average score and the deviation of multiple factors in selecting the best path.

5.2. Path-planning simulation prototype

We built a path-planning simulation prototype that consists of a path generation and evaluation server and a mobile client as seen in Fig. 2. The path generation and evaluation system provides general path-planning services and was implemented on an Ubuntu server. It manages 9120 places of interest that are located in a local county in the United States and are classified into 12 big categories such as stores, banks, auto services, post offices. It used the road network for this county consisting of approximately 2 million edges and 3 million nodes. We used $A *$ search with Fibonacci heap to quickly generate a number of routes [14]. We implemented the client on a Samsung GalaxyTab 10.1 which has a large screen similar to car navigation systems. The client manages a user’s tasks and requests routes by suggesting places to accomplish tasks and providing travel information. The server collects path requests from the clients, and generates and evaluates serendipitous paths between the original location and the predicted destination. The server then generates and ranks serendipitous routes including daily tasks from a given travel request from the client via HTTP. Finally the client then visualizes the routes provided by the server using Google Maps.

Fig. 2.

Architecture of the serendipity-empowered path planning.

Our prototype generates and recommends predictive task routes based on the k-path generation and path ranking. First of all, the prototype shows task information, travel information and a map showing the starting point, destination, and POIs for tasks, as seen in Fig. 3. The task information includes the current tasks of users to be completed and the travel information includes the current location and destination. Users are then asked to specify their regular destination. It then presents the best path ranked by the ranking algorithms. For the purpose of validating the ranking algorithms, it recommends six types of routes with/without the tasks when users click “Find My Best Route” and asks the user to rank the recommended routes. Afterwards, the user’s current location is updated to the destination and the next trip is suggested to the user. In addition, we add two modes to the prototype to supports semi-automatic path building and regular route strategy in order to compare the performance of our method and task completion. The semi-automatic path-building strategy generates routes and asks users to select POIs for completing tasks. Rather than asking the user to rank the routes, the user can build the best route by adding POIs related to tasks. For this purpose, a new path is created from the current location to the destination via a list of selected POIs when the user clicks a POI balloon (green icons on the map). The regular route strategy asked users to enter both destinations for commuting and performing tasks. With this planning mechanism, the user is asked to specify extra destinations for completing tasks as well as their regular travels such as home and office.

Fig. 3.

UI of serendipity-empowered path planning: UI with 6 routes (top) and selected route (bottom).

5.3. Evaluation procedure

Our evaluation of the proposed path planning method was twofold: preference learning and path planning simulation with the simulation prototype. Preference learning models users’ route preferences and collects their tasks. The simulation generated and evaluated serendipitous routes with the participants.

Target users We recruited 12 participants who owned Android phones, lived in our local city and regularly drove. Eight were male and four were female. They reported that they drive everyday to commute to their jobs and to perform tasks.

Preference learning For simulating predictive task completion on daily commuting routes, we first modeled users’ preferences based on a user’s preferred routes and a list of their daily tasks. In order to model their preferences and learn their preferred routes, we developed a logging app on Android phones that recorded the GPS locations of their cars and managed their daily tasks. The logging app automatically recorded participants’ GPS locations and allowed users to manually enter their tasks for a period of three weeks. Afterwards, we extracted destinations and tasks and then post-processed the routes to extract users’ preferences. Finally, we obtained preferences over attributes of the road network such as lane type, speed limit, etc.

Task and place setting Soon after the preference learning, we collected preferred tasks and places for simulating paths. As people usually perform different tasks, we derived a list of 20 tasks common across our participants and a number of candidate places related to each task. The participants were asked to specify their preferred tasks from among the tasks and connect their tasks to places using the UI of the simulation prototype.

Regular destinations We then asked the participants to create a driving schedule for a regular week, matching the driving conditions for our serendipitous path recommendation and the two comparative path building strategies we gave them in the main study.

Main study We then conducted the main study, which consisted of a comparison of three recommendation strategies. We first applied the regular path recommendation strategy in order to know how they commute and complete tasks. For this purpose, each participant was asked to commute and perform tasks for a week with the simulation prototype. To ensure the scenario was realistic, three tasks were added to their task list every day. To maintain a range of tasks, two of the tasks had a two-day deadline and the remaining task had a one-week deadline. The tasks are maintained in the list until they are completed, otherwise they may be delayed. Participants were asked to commute according to their regular schedule in order to make the travel similar to their routines. As the tasks and related POIs are given to the participants during every trip, the participants may or may not make a plan to perform a task if they have been given tasks that they usually do. For example, on the first day, the participants received their three tasks while at home and were asked to go to their office or to complete tasks. This commute and task completion were repeated for all seven days of the week.

We then applied the semi-automatic path recommendation strategy and serendipity-empowered path recommendation strategy with our prototype. In the semi-automatic path recommendation, participants were asked to add POIs to complete tasks on their regular route and also could complete tasks by making additional trips. In the semi-automatic path recommendation, only one best route was recommended to the participant together with places close to the regular route where tasks could be accomplished. Participants were asked to add the places to perform the tasks (POIs) by clicking them on the map. In the serendipity path recommendation, the participant was given six types of alternative routes: minimum cost (MinCost), minimum time (MinTime), minimum cost with one task (MinTask), minimum cost with maximum tasks (MaxTask), average utilitarian route (AvgUtility), and multiplicative utilitarian route (MultiUtility). The participant was asked to rank the quality of the routes with a six-level Likert scale.

We recorded the trip and task information from each trip to measure quality of routes and to know the task statuses. The trip information included current location and destination, route, turns, tasks, length and travel time. The task information included start time, end time, deadline, and completion status of tasks. During the path ranking of the serendipity path recommendation, the information of the alternative routes and ranking values were recorded in the same way.

Final interview Finally, after the main study, we conducted short interviews to collect more qualitative information about how participants selected and ranked routes in their trips.

6. Evaluation results

6.1. Path planning performance

We first measured the performance of the path-planning strategies in terms of the number of trips, total travel time and number of tasks completed. The number of trips accounts for how many trips each driver made for completing tasks or commuting per week, the total travel time indicates how much the driver drives during the trips, and the number of tasks completed represents how many task are performed during the trips. As seen in Fig. 4, the average number of trips and the total travel time of the serendipity path recommendation strategy was less than the semi-automatic and regular path recommendation strategies. Also, the number of tasks completed in the serendipity path recommendation was higher than in the semi-automatic and regular path recommendation strategies. Therefore it is clear that the serendipity path recommendation was able to combine performing tasks with driving to a destination on a regular commute and reduced extra driving needed for performing these tasks compared to the other two strategies.

Fig. 4.

The performance of the path planning strategies: (left) average number of trips, (center) total travel time and (right) average number of tasks completed.

6.2. Task completion performance

We analyzed the task-completion performance of the serendipity path recommendation. The task completion time was measured by calculating the interval between when a task was added to the task list and when the task was completed.

Fig. 5.

Task completion performance: (top) average completion time and (bottom) number of tasks completed.

As seen in Fig. 5, the average time spent to complete tasks using the serendipity path, semi-automatic and regular path recommendation strategies were 1.4 days, 1.6 days and 2.1 days per task respectively. Thus the average time required for completing tasks in the serendipity path-planning scenario was less than in the semi-automatic and regular path recommendations. In addition, the number of completed tasks was evenly distributed over all days of a week in the serendipity and semi-automatic path recommendations. The number of completed tasks was the highest on Saturday in the regular path recommendation. Users tended to do more of their tasks all together on one day using this strategy, while the tasks were more evenly completed over all days of a week with the serendipity path recommendation strategy.

6.3. Task completion performance

As seen in Fig. 6, paths with the minimum cost or travel time were preferred for all routes (i.e., both routes that involved tasks and those that did not). The routes with minimum cost (MinCost) and travel time (MinTime) were frequently selected when we only consider the routes without any task. However, the routes with the maximum average utility (AvgUtility), minimum cost with a single task (MinTask), and multiplicative utility (MultiUtility) were similarly selected when we consider routes that include tasks. The route with maximum tasks (MaxTask) was less frequently selected than others. It is clear that users generally consider travel time and cost during their regular trips, but also consider other factors, such as availability, place preference, the number of tasks in a route and distance (or deviation) of a task from the route, according to their situation.

Fig. 6.

Preferable route ranking strategies according to task completion.

In addition, we found that the start and destination locations affected task completion. As seen in Fig. 7(left), the participants tended to complete tasks when they were returning to their homes. They were more unlikely to complete tasks when they were going to other places, such as restaurants or the gym. They also had a tendency to complete tasks when they were coming from their office, shown in Fig. 7(right). Otherwise, it was unclear whether they preferred to perform tasks when coming from or going to locations other than the home or workplace.

Fig. 7.

Task completion according to locations: (left) the percent of routes selected for completing tasks according to destination and (right) the percent of routes selected for completing tasks according to start locations.

6.4. Individual opinion

Through individual interviews after the main study, we collected various opinions about how the participants ranked routes and completed their tasks. First of all, three participants (S4, S8, and S10) reported that they had specific routines in place for completing tasks. They tended to perform tasks near regular destinations (e.g., home, office). They also preferred to perform multiple tasks in places such as malls when they were in those places. Furthermore, three participants (S4, S6, and S8) reported that time availability is very important when performing their tasks. Since they are in more of a hurry on their way to work or an appointment, they felt more free to perform tasks on the way home. Users expected that future routes would probably include places where tasks could more easily be performed. Two participants (S9 and S12) tended to perform tasks when their preferences matched with POIs associated with the tasks, and otherwise waited to perform the tasks using the next set of provided serendipity routes.

7. Implication

We proposed a serendipity-empowered path recommendation strategy that combines daily tasks with commuting routes and showed how it improved task completion compared to regular task completion approaches. We now discuss some implications of our proposed path recommendation for developing new types of path and task planning systems.

First of all, the serendipitous tasks combined with routines are very important for busy people. Originally, people tend to complete their tasks by taking extra driving trips or even completing most of them on a specific day of week. They even frequently delay tasks and/or forget to complete tasks. In our path planning strategy, we combined the tasks with regular routes that enabled users to perform their tasks on the routes close to their regular routes. They were able to perform a number of their tasks on the way to their destination. The serendipitous path recommendation scheduled the tasks on their commuting routes and thus decreased the number of trips, travel time and total distance required to accomplish the tasks. In addition, serendipitous routes play a role of discovery of local knowledge with serendipitous tasks. Users presumably think that they know a lot about their neighborhoods they visit over time. However, they only partially know their neighborhoods and commuting areas since POIs and route statuses are continuously changing. As we reported in the final interview, people tended to look for POIs near their regular routes and destinations. The serendipitous paths not only provide local POIs that users frequently visit, but also incorporate unknown POIs that might be preferred by the users.

A task schedule that is both spatially and temporarily flexible is useful for people that regularly commute between their home and a workplace. In previous task planning systems, POIs related to tasks have been fixed and users were reminded of their tasks when close to those areas. However, it is difficult to know whether they will visit any of these areas and whether the POIs are the best for completing tasks in upcoming routes. With our path planning strategy, tasks were scheduled at any POI and at any time, combining both a task scheduler and task reminder for users. In addition, users also try to see whether the POIs in given recommended route match their tasks and preferences. They would consider other routes when their task preferences were not matched with the POIs suggested.

Path ranking involves various contexts in terms of routes, POIs, etc. As we reported, there did not appear to be a dominant path-ranking strategy for path ranking. Users preferred the fastest way to a destination when they did not want to complete any task. However they used a number of different strategies (except performing many tasks) when they wanted to complete some tasks. For identifying the best ranking strategy, a follow-up study that studies this issue in detail could be performed. In addition, a combination of different strategies might be useful for finding the best serendipitous routes or parameter optimization could be applied for finding the best weights for each ranking strategy.

8. Conclusion

In this paper, we proposed a serendipity-empowered path planning approach that augmented tasks on regular routes for performing daily tasks efficiently. For this purpose, our path planning method generated a number of alternative routes considering current tasks and destination and selected the best route. We implemented and evaluated the path planning approach by recruiting local drivers. We found that our path planning strategy reduced the number of trips and total travel distance while it increased the number of tasks completed. As a result, the tasks were completed earlier when using our serendipity path planner than their own (regular) task completion strategy and an alternative semi-automatic path planning approach. We also found that there was no dominant strategy in ranking routes, but that ranking was related to various factors, such as time or location. This study is an important initial step toward combining daily tasks with regular routes. Further work will include real deployment of our system and long-term observation to validate the usefulness of our planning method.

Footnotes

Acknowledgements

This work was supported by the Ministry of Science, ICT, and Future Planning grant funded by the Korea government (No. 2014-044-026-001).

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.