Abstract: Ridesharing, that is, the problem of finding parts of routes that can be shared by several travelers with different points of departure and destinations, is a complex, multiagent decision-making problem. The problem has been widely studied but only for the case of ridesharing using freely moving vehicles not bound to fixed routes and/or schedules—ridesharing on timetabled public transport services has not been previously considered. In this article, we address this problem and propose a solution employing strategic multiagent planning that guarantees that for any shared journey plan found, each individual is better off taking the shared ride rather than traveling alone, thus providing a clear incentive to participate in it. We evaluate the proposed solution on real-world scenarios in terms of the algorithm’s scalability and the ability to address the inherent trade-off between cost savings and the prolongation of journey duration. The results show that under a wide range of circumstances our algorithm finds attractive shared journey plans. In addition to serving as a basis for traveler-oriented ridesharing service, our system allows stakeholders to determine appropriate pricing policies to incentivize group travel and to predict the effects of potential service changes.

Citation: J. Hrncir, M. Rovatsos, and M. Jakob. Ridesharing on Timetabled Transport Services: A Multiagent Planning Approach, Journal of Intelligent Transportation Systems, 19(1):89-105, 2015.

Download: http://bit.ly/2ipJ8mP

Abstract: In this paper we present a novel approach to multiagent planning in domains with concurrent actions and associated concurrent action constraints. In these domains, we associate the actions of individual agents with subsets of objects, which allows for a transformation of the problems into single-agent planning problems that are considerably easier to solve. The transformation forces agents to select joint actions associated with a single subset of objects at a time, and ensures that the concurrency constraints on this subset are satisfied. Joint actions are serialised such that each agent performs their part of the action separately. The number of actions in the resulting single-agent planning problem turns out to be manageable in many real-world domains, thus allowing the problem to be solved efficiently using a standard single-agent planner. We also describe a cost-optimal algorithm for compressing the resulting plan, i.e. merging individual actions in order to reduce the total number of joint actions. Results show that our approach can handle large problems that are impossible to solve for most multiagent planners.

Citation: M. Crosby, A. Jonsson, M. Rovatsos. A Single-Agent Approach to Multiagent Planning. Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), Prague, Czech Republic, August 18-22, 2014.

Download: http://bit.ly/2jcNwGT