Mapping Multi-Agent Pathfinding to Combinatorial Auctions


/Title Mapping Multi-Agent Pathfinding to Combinatorial Auctions /Author Put All Your Authors Here, Separated by Commas



The Multi-Agent PathFinding (MAPF) problem and the Combinaturical Auction (CA) problem have both been the focus of independent studies in AI. Next, definitions for both problems are given.

The multi-agent path finding (MAPF) problem is a generalization of the single-agent path finding problem for \(k > 1 \) agents. It consists of a graph \(G(V,E)\). A number of agents \(K\). For each agent \(k_i\), a unique start state \(s_i\), and a unique goal state \(g_i\), are given. The task is to find paths for all agents from their start states to their goal states, under the constraint that agents cannot collide during their movements. In many cases there is an additional goal of minimizing a cumulative cost function such as the sum of the time steps required for every agent to reach its goal. MAPF has practical applications in video games, traffic control  (Silver 2005, Dresner 2008), robotics (citation not found: DBLP:journals/ras/BennewitzBT02) and aviation (citation not found: DBLP:journals/trob/PallottinoSBF07).