Applying strategic multiagent planning to real-world travel sharing problems

Travel sharing, i.e., the problem of nding parts of routeswhich can be shared by several travellers with different pointsof departure and destinations, is a complex multiagent problem that requires taking into account individual agents' preferences to come up with mutually acceptable joint plans. Inthis paper, we apply state-of-the-art planning techniques toreal-world public transportation data to evaluate the feasibility of multiagent planning techniques in this domain. Thepotential of improving travel sharing technology has greatapplication value due to its ability to reduce the environmental impact of travelling while providing benefits to travellersat the same time.

We propose a three-phase algorithm that utilises performantsingle-agent planners to nd individual plans in a simplieddomain first and then merges them using a best-responseplanner which ensures resulting solutions are individuallyrational. Finally, it maps the resulting plan onto the fulltemporal planning domain to schedule actual journeys.

The evaluation of our algorithm on real-world, multi-modalpublic transportation data for the United Kingdom showslinear scalability both in the scenario size and in the number of agents, where trade-offs have to be made betweentotal cost improvement, the percentage of feasible timetables identified for journeys, and the prolongation of thesejourneys. Our system constitutes the rst implementationof strategic multiagent planning algorithms in large-scaledomains and provides insights into the engineering processof translating general domain-independent multiagent planning algorithms to real-world applications.