Interactive traffic-aware route search on smartphones

Route search is an application for planning an efficient route via points of interest specified by search terms. Essentially, the search requires to find the fastest route, from the location of the user to a specified destination, through geographical entities whose type is indicated by the search terms, e.g., a route via a "Coffee Shop" and a "Pharmacy". To that end, it is essential to take into account traffic conditions and temporal constraints, such as opening and closing hours of institutes and businesses. We assume that the search is applied under conditions of uncertainty where a user may discover that she is unsatisfied with the visited entity only upon arrival at the point of interest. Thus, it may be required to visit several entities of the same type till discovering one that satisfies the user. In an interactive search, the user provides feedback after visiting an entity, to indicate when there is no need to go via additional entities of the same type. We show how interactive route search, suitable to be applied on smartphones, can be used for traffic aware route search under conditions of uncertainty and we provide effective heuristics for computing a route interactively.