MIT Investigator(s): Daniela RUS
Develop models and algorithms to configure dynamically portions of the public transportation service network to meet mobility demands in real- time; the objective is to provide passenger-centric, timely service while minimizing costs and maximizing system efficiency.
- We will develop a solution to the problem in which an agent (human or robot) is tasked to travel among a set of spatially distributed point-of-interests (POIs) and collect information. The quality of the information collected at each POI is characterized by some sensory (reward) function of time. With limited time, the agent must balance between spending time traveling to more POIs and performing time-consuming sensing activities at the visited POIs to maximize the overall reward. In a dual formulation, the agent may be required to acquire a minimum mount of reward with the least amount of time. We propose an anytime planning algorithm for solving these two NP-hard problems to arbitrary precision for arbitrary reward functions. The algorithm will be effective on large instances with tens to hundreds of POIs.
- In this project we will develop an incrementally optimal method to assign Multiple Tasks to Multiple Vehicles, where a vehicle can perform several tasks in parallel. In particular, we will apply it to ride sharing (car pooling) with several passengers per vehicle. We propose a flexible and general optimization framework with constraints such as maximum waiting time and trip delay. Building on the concept of shareability networks we first compute a pair-wise graph of requests and vehicles, which can be combined. This will followed by a search of trips that can be executed by a vehicle. Finally, the optimal assignment between trips and vehicles is solved via an Integer Linear Program. The method, which can be parallelized and incrementally searches for an optimal solution, is applied to continuous fleet management. We perform experiments with a New York City dataset of historical requests, with up to 1000 vehicles and 7,000 requests per hour and up to four passengers per vehicle. Our method shows real time performance and quantifies the benefits of increased vehicle capacity.