Fast and efficient rendezvous in street networks

Abstract

We address the problem of rendezvous between two agents in urban street networks. Specifically, we consider the case where the agents have variable speeds and they need to schedule a rendezvous or a meeting under uncertainty in their travel times. Examples of such a scenario range from everyday life where two people would like to coordinate a meeting while going from office to home; to a futuristic case where automated taxis would like to meet each other for load balancing passengers. The scheduling for such scenarios can easily become challenging with uncertainties such as delayed departures, road blocks due to construction or traffic congestion. Any solution for such a task is required to minimize the waiting time and the planning overhead. In this paper, we propose an algorithm that optimizes the total travel time and the waiting time for two agents to complete their respective paths from start to rendezvous and from rendezvous to goal locations subject to delays along their paths. We validate our approach with a street network database which has a cost associated with every query made to the database server. Thus our algorithm intelligently optimizes for rendezvous trajectories that effectively mitigate the scourge of traffic delays, while simultaneously limiting the number of queries through careful analysis of the informative value of each potential query.