guni edited sectionReducing_Opti.tex  over 9 years ago

Commit id: 7da07cfe24725f832d9db282dada6edc415e055b

deletions | additions      

       

\section{Reducing MAPF to the Bundling Problem}  Different BP solvers provide different gurentees, e.g. social whelfer, truthfulness, [[More...]]. Solving MAPF using a BP solver provides these guarntees for MAPF.  A solution for the MAPF problem is composed from a set of paths, one per agent. each single agent path is composed from a set of \{vertex, time step\} pairs.  MAPF can be reduced to BP as follows.  The item set $M$, in the corresponding BP are the catisien product of all time steps and all vertices $V$.   Bundles are paths. Utility is UpperBound*k minus path cost..