Applying Strategic Multiagent Planning to Real-World Travel Sharing Problems

Travel sharing, i.e., the problem of finding parts of routes which can be shared by several travellers with different points of departure and destinations, is a complex multiagent prob-lem that requires taking into account individual agents ’ pref-erences to come up with mutually acceptable joint plans. In this paper, we apply state-of-the-art planning techniques to real-world public transportation data to evaluate the feasi-bility of multiagent planning techniques in this domain. The potential of improving travel sharing technology has great application value due to its ability to reduce the environmen-tal impact of travelling while providing benefits to travellers at the same time. We propose a three-phase algorithm that utilises performant single-agent planners to find individual plans in a simplified domain first and then merges them using a best-response planner which ensures resulting solutions are individually rational. Finally, it maps the resulting plan onto the full temporal planning domain to schedule actual journeys. The evaluation of our algorithm on real-world, multi-modal public transportation data for the United Kingdom shows linear scalability both in the scenario size and in the num-ber of agents, where trade-offs have to be made between total cost improvement, the percentage of feasible timeta-bles identified for journeys, and the prolongation of these journeys. Our system constitutes the first implementation of strategic multiagent planning algorithms in large-scale domains and provides insights into the engineering process of translating general domain-independent multiagent plan-ning algorithms to real-world applications